Geographic Decomposition of the Shortest Path Problem, with an Application to the Traffic Assignment Problem
Zachary F. Lansdowne, David W. Robinson
Management Science · 1982 · Volume 28 · Issue 12
Abstract
An algorithm, which can be applied to loosely connected networks, is given for geographically decomposing the shortest path problem. The algorithm is applicable to the traffic assignment problem when it is solved as a series of shortest path problems by the Frank-Wolfe algorithm. Numerical results for a large 1287 node, 3752 arc traffic assignment problem for Washington, D.C., indicate that using geographical decomposition can reduce computer memory storage requirements or program run time.
Keywords
networks/graphs: distance algorithms, programming: large scale systems, transportation: traffic assignment
Enable JavaScript for citation tools and additional paper interactions.