An efficient algorithm for building min-path trees for all origins in a multi-class network

Robert B. Dial

Transportation Research Part B: Methodological, 2006, vol. 40, issue 10, 851-856

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.

Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(06)00002-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:40:y:2006:i:10:p:851-856

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().