Dynamic journeying under uncertainty

Research output: Scientific - peer-reviewArticle

Standard

Dynamic journeying under uncertainty. / Häme, Lauri; Hakula, Harri.

In: European Journal of Operational Research, Vol. 225, No. 3, 16.03.2013, p. 455-471.

Research output: Scientific - peer-reviewArticle

Harvard

APA

Vancouver

Author

Häme, Lauri; Hakula, Harri / Dynamic journeying under uncertainty.

In: European Journal of Operational Research, Vol. 225, No. 3, 16.03.2013, p. 455-471.

Research output: Scientific - peer-reviewArticle

Bibtex - Download

@article{a9db4edca35c46ad913b92fdaa82f895,
title = "Dynamic journeying under uncertainty",
abstract = "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.",
keywords = "Itinerary planning problem, Markov decision processes, Stochastic processes, Stochastic shortest path problem, Transportation",
author = "Lauri Häme and Harri Hakula",
year = "2013",
month = "3",
doi = "10.1016/j.ejor.2012.10.027",
volume = "225",
pages = "455--471",
journal = "EUROPEAN JOURNAL OF OPERATIONAL RESEARCH",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "3",

}

RIS - Download

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

VL - 225

SP - 455

EP - 471

JO - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

T2 - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

JF - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

SN - 0377-2217

IS - 3

ER -

ID: 12920056