Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks

摘要

We propose in this article an adaptive algorithm for optimal and robust guidance for the users of the road networks. The algorithm is based on the Stochastic On Time Arrival (SOTA) family of routing algorithms, which is appropriate for taking into account the variability of travel times through the road networks. The SOTA approach permits the derivation of the maximum cumulative probability distribution of the time arrival toward a given destination in the network. Those distributions allow the selection of the most reliable origin-destination paths under given travel time budgets. We investigate here the introduction of robustness against link and path failures in the criterion of the guidance strategy selection. Our algorithm takes into account the reliability of itinerary travel times, since it is based on a SOTA approach. In addition, the algorithm takes into account itinerary robustness, by favoring itineraries with possible and reliable alternative diversions, in case of link failures, with respect to itineraries without or with less reliable alternatives. We first analyze the algorithm in its static version, without considering the traffic dynamics, and show some interesting properties. We then combine the robust guidance algorithm with a dynamic traffic model by using the traffic simulator SUMO (Simulation of Urban Mobility), and illustrate its effectiveness in some dynamic scenarios. (C) 2018 Elsevier B.V. All rights reserved.