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.
Dynamic shortest path problem, Approximate Dynamic Programming, Disruption handling, Clustering
|Name||BETA publicatie : working papers|