Itinerary planning with time budget for risk-averse travelers

Yu Zhang and Jiafu Tang

European Journal of Operational Research, 2018, vol. 267, issue 1, 288-303

Abstract: Itinerary planning problem (IPP) in public transport networks has witnessed to be a fundamental and important problem in public transport operations management. Although empirical studies show that time budgets are usually prescribed by travelers, the time budget is rarely considered in literature related to IPP under stochastic travel times. In this paper, we study the IPP with time budget (IPPB) in public transport networks with stochastic travel times, which consists of planning an itinerary from an origin to a destination that helps risk-averse travelers mitigate uncertainty and effectively meet their time budgets. A mathematical model (MRHA-IPPB) is developed for the IPPB, in which we use the utility theory to characterize travelers’ risk-averse behaviors. Since minimizing the lateness probability or the expected lateness duration is intractable, we propose a new decision criterion, maximizing risk-hedging ability (short for MRHA hereafter) while guaranteeing that the corresponding certainty equivalent of itinerary travel time would not exceed the time budget. The model MRHA-IPPB is shown theoretically and numerically to consider both the lateness probability and the lateness duration. We show NP-completeness of the IPPB with fully correlated arc travel times and study two tractable scenarios, i.e., the IPPB with independent arc travel times and that with partially correlated arc travel times. We decompose an IPPB as a two-stage problem and efficiently solve it through a binary search scheme with a label-setting algorithm embedded. We demonstrate the effectiveness of the MRHA-IPPB model through an illustrative example and show that the MRHA-based decomposition approach requires only less than one second per query over a real-world public transport network.

Keywords: Uncertainty modeling; Itinerary planning with time budget; Utility theory; Decomposition; Network modification (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717310342
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:267:y:2018:i:1:p:288-303

DOI: 10.1016/j.ejor.2017.11.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().