The dynamic shortest path problem with time-dependent stochastic disruptions

Derya Sever; Lei Zhao; Nico Dellaert; Emrah Demir; Tom Van Woensel; Ton De Kok

doi:10.1016/j.trc.2018.04.018

The dynamic shortest path problem with time-dependent stochastic disruptions

Derya Sever, Lei Zhao, Nico Dellaert, Emrah Demir, Tom Van Woensel, Ton De Kok

Management Science & Engineering

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.

Original language	British English
Pages (from-to)	42-57
Number of pages	16
Journal	Transportation Research Part C: Emerging Technologies
Volume	92
DOIs	https://doi.org/10.1016/j.trc.2018.04.018
State	Published - Jul 2018

Keywords

Approximate dynamic programming
Dynamic shortest path problem
Lookahead policy
Time-dependent disruption
Value function approximation

Access to Document

10.1016/j.trc.2018.04.018

Cite this

@article{ca997709a4994827ab9555d39b1adb12,

title = "The dynamic shortest path problem with time-dependent stochastic disruptions",

abstract = "The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.",

keywords = "Approximate dynamic programming, Dynamic shortest path problem, Lookahead policy, Time-dependent disruption, Value function approximation",

author = "Derya Sever and Lei Zhao and Nico Dellaert and Emrah Demir and {Van Woensel}, Tom and {De Kok}, Ton",

note = "Funding Information: This research was partially supported by The National Natural Science Foundation of China (NSFC) under Project No. 71771137 . The authors would like to thank the Editor-in-Chief and two anonymous reviewers for their helpful comments. Appendix A The paired t-test results and multivariate analysis are given in , respectively. Tables 8 and 9 Publisher Copyright: {\textcopyright} 2018 Elsevier Ltd",

year = "2018",

month = jul,

doi = "10.1016/j.trc.2018.04.018",

language = "British English",

volume = "92",

pages = "42--57",

journal = "Transportation Research Part C: Emerging Technologies",

issn = "0968-090X",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - The dynamic shortest path problem with time-dependent stochastic disruptions

AU - Sever, Derya

AU - Zhao, Lei

AU - Dellaert, Nico

AU - Demir, Emrah

AU - Van Woensel, Tom

AU - De Kok, Ton

N1 - Funding Information: This research was partially supported by The National Natural Science Foundation of China (NSFC) under Project No. 71771137 . The authors would like to thank the Editor-in-Chief and two anonymous reviewers for their helpful comments. Appendix A The paired t-test results and multivariate analysis are given in , respectively. Tables 8 and 9 Publisher Copyright: © 2018 Elsevier Ltd

PY - 2018/7

Y1 - 2018/7

N2 - The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.

AB - The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.

KW - Approximate dynamic programming

KW - Dynamic shortest path problem

KW - Lookahead policy

KW - Time-dependent disruption

KW - Value function approximation

UR - http://www.scopus.com/inward/record.url?scp=85046356153&partnerID=8YFLogxK

U2 - 10.1016/j.trc.2018.04.018

DO - 10.1016/j.trc.2018.04.018

M3 - Article

AN - SCOPUS:85046356153

SN - 0968-090X

VL - 92

SP - 42

EP - 57

JO - Transportation Research Part C: Emerging Technologies

JF - Transportation Research Part C: Emerging Technologies

ER -

The dynamic shortest path problem with time-dependent stochastic disruptions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this