Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation Systems

Abstract

We propose a hierarchical algorithm for approximating shortest paths between all pairs of nodes in a large-scale network. The algorithm begins by extracting a high-level subnetwork of relatively long links (and their associated nodes) where routing decisions are most crucial. This high-level network partitions the shorter links and their nodes into a set of lower-level subnetworks. By fixing gateways within the high-level network for entering and exiting these subnetworks, a computational savings is achieved at the expense of optimality. We explore the magnitude of these tradeoffs between computational savings and associated errors both analytically and empirically with a case study of the Southeast Michigan traffic network. An order-of-magnitude drop in computation times was achieved with an on-line route guidance simulation, at the expense of less than 6% increase in expected trip times.