Robust Routing Using Electrical Flows

Generating alternative routes in road networks is an application of significant interest for online navigation systems. A high quality set of diverse alternate routes offers two functionalities - a) support support multiple (unknown) preferences that the user may have; and b) robust to changes in network conditions. We address the latter in this paper. The main techniques that produce alternative routes in road networks are the {\em penalty} and the {\em plateau} methods, with the former providing high quality results but being too slow for practical use and the latter being fast but suffering in terms of quality. In this work we propose a novel method to produce alternative routes that is fundamentally different from the aforementioned approaches. Our algorithm borrows concepts from electrical flows and their decompositions. We provide an analysis that proves theoretical properties of our algorithm and evaluate it against the penalty and plateau methods, showing that it is as fast as the plateau method while also recovering much of the headroom towards the quality of the penalty method. The metrics we use to evaluate performance include the {\em stretch} (the average cost of the routes), the {\em diversity}, and the {\em robustness} (the connectivity between the origin and destination) of the induced set of routes.

• Algorithms and Theory

• Networking