Itinerary planning with time budget for risk-averse travelers

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. (C) 2017 Elsevier B.V. All rights reserved.