Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1132952 | Transportation Research Part B: Methodological | 2006 | 6 Pages |
Abstract
Urban transportation planning models consume untold hours of computer time building zillions of min-path trees. Their networks have tens of thousands of arcs, accommodate several trip classes, and solve the traffic equilibrium problem via many, many iterations of min-path calculations for thousands of origins and destinations. This paper presents a simple algorithm that couples restricted reduced-cost analysis with label-correcting, which can reduce this min-path tree building time substantially. For a given origin, the algorithm rapidly transforms a tree for one class to that for next class. Test results using synthetic data suggest that its application to real networks should experience speedups of at least a factor of 2.0 and perhaps beyond 5.0.
Related Topics
Social Sciences and Humanities
Decision Sciences
Management Science and Operations Research
Authors
Robert B. Dial,