### Abstract

Original language | English |
---|---|

Place of Publication | Eindhoven |

Publisher | Technische Universiteit Eindhoven |

Number of pages | 36 |

Publication status | Published - 2013 |

### Publication series

Name | BETA publicatie : working papers |
---|---|

Volume | 423 |

ISSN (Print) | 1386-9213 |

### Fingerprint

### Cite this

*Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach*. (BETA publicatie : working papers; Vol. 423). Eindhoven: Technische Universiteit Eindhoven.

}

*Dynamic shortest path problem with travel-time-dependent stochastic disruptions : hybrid approximate dynamic programming algorithms with a clustering approach*. BETA publicatie : working papers, vol. 423, Technische Universiteit Eindhoven, 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.

Research output: Book/Report › Report › Academic

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 -