Shortest paths and time-dependent stochastic travel times

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.

1-s2.0-S0968090X1830531X-gr1

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.