About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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. © 1998 INFORMS.