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

Research output: Book/ReportReportAcademic

36 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

Travel time
Dynamic programming

Cite this

@book{2a0503617dc0468a8657fd081f184ca8,
title = "Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach",
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",
author = "D. Sever and L. Zhao and N.P. Dellaert and {Woensel, van}, T. and {Kok, de}, A.G.",
year = "2013",
language = "English",
series = "BETA publicatie : working papers",
publisher = "Technische Universiteit Eindhoven",

}

Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach. / Sever, D.; Zhao, L.; Dellaert, N.P.; Woensel, van, T.; Kok, de, A.G.

Eindhoven : Technische Universiteit Eindhoven, 2013. 36 p. (BETA publicatie : working papers; Vol. 423).

Research output: Book/ReportReportAcademic

TY - BOOK

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

AU - Sever, D.

AU - Zhao, L.

AU - Dellaert, N.P.

AU - Woensel, van, T.

AU - Kok, de, A.G.

PY - 2013

Y1 - 2013

N2 - 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

AB - 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

M3 - Report

T3 - BETA publicatie : working papers

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

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -