Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach

Research output: Book/ReportReportAcademic

51 Downloads (Pure)

Abstract

We consider a dynamic shortest path problem with stochastic disruptions in the network. We use both historical information and real-time information of the network for the dynamic routing decisions. We model the problem as a discrete time nite horizon Markov Decision Process (MDP). For networks with many levels of disruptions, the MDP faces the curses of dimensionality. We rst apply Approximate Dynamic Programming (ADP) algorithm with a standard value function approximation. Then, we improve the ADP algorithm by exploiting the structure of the disruption transition functions. We develop a hybrid ADP with a clustering approach using both a deterministic lookahead policy and a value function approximation. We develop a test bed of networks to evaluate the quality of the solutions. The hybrid ADP algorithm with clustering approach signicantly reduces the computational time, while stil providing good quality solutions. Keywords: Dynamic shortest path problem, Approximate Dynamic Programming, Disruption handling, Clustering
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages36
Publication statusPublished - 2013

Publication series

NameBETA publicatie : working papers
Volume423
ISSN (Print)1386-9213

Fingerprint Dive into the research topics of 'Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach'. Together they form a unique fingerprint.

Cite this