TY - JOUR
T1 - Dynamic journeying under uncertainty
AU - Häme, Lauri
AU - Hakula, Harri
PY - 2013/3/16
Y1 - 2013/3/16
N2 - We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.
AB - We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.
KW - Itinerary planning problem
KW - Markov decision processes
KW - Stochastic processes
KW - Stochastic shortest path problem
KW - Transportation
UR - http://www.scopus.com/inward/record.url?scp=84870252383&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2012.10.027
DO - 10.1016/j.ejor.2012.10.027
M3 - Article
AN - SCOPUS:84870252383
SN - 0377-2217
VL - 225
SP - 455
EP - 471
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -