Our paper:

The dynamic shortest path problem with time-dependent stochastic disruptions

Co-authored with Derya Sever, Lei Zhao, Emrah Demir, Nico Dellaert and Ton de Kok is published in Transportation Research Part C: Emerging Technologies. The publisher gave full access for a few weeks via this link.

Having real-time traffic information from Intelligent Transportation Systems (ITS) and taking into account the stochastic nature of disruptions can significantly reduce time delays, congestion and air pollution. As a trade-off, for networks with many disruption levels, computing dynamic routing decisions takes very long computational time. In order to improve the speed of computation, real-life applications (e.g., navigation devices) require fast and high quality algorithms as we propose one in this paper. The problem at hand is named as dynamic and stochastic shortest path problem.

In this paper, we formulate the dynamic shortest path problem with time-dependent stochastic disruptions as an MDP and propose a hybrid ADP algorithm with the clustering approach. The algorithm uses both a deterministic lookahead policy and a value function approximation. To our knowledge, the hybrid ADP algorithm with the clustering approach has not yet been thoroughly investigated for the dynamic shortest path problem. We propose and compare several variations of ADP algorithms for networks with many disruption levels which are similar to real-life traffic situations.