Dynamic Routing Considering Network Disruptions

In this research, we consider routing problems where there are stochastic disruptions in the networks due to accidents, bottlenecks that lead to significantly higher travel time. In this routing problem, the aim is to develop dynamic routing decisions to minimise the expected total travel time for a single origin-destination pair. We model the problem as a discrete time finite horizon Markov Decision Process (MDP) and solve the problem with a Dynamic Programming (DP) approach. For the routing decisions, the DP approach provides a practical framework to find routing decisions for multiple stages. However, for large-scale networks, finding the optimal solution suffers from the curse of dimensionality. For this purpose, we develop computationally efficient hybrid routing policies considering both online and historical information for the limited part of the network. To test the efficiency of different routing policies, we develop a test bed of networks based on a number of characteristics and analyse the results in terms of routes, solution quality and calculation times. Our results show that a significant part of the cost reduction can be obtained by considering only a limited part of the network in detail at online level.

Considering these results, in the next research we  include the propagation effect of disruptions for the dynamic shortest path problems. When a disruption occurs at a certain link, due to the limited capacity, the effect of the disruption propagates to upstream links. We denote this as the spillback effect. To have better routing decisions, we should capture these dynamics. We consider the spillback effect in the hybrid routing policies. We analyse the effect of considering and not considering the spillback effect in different routing policies.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars