An efficient algorithm for building min-path trees for all origins in a multi-class network |
| |
Authors: | Robert B Dial |
| |
Institution: | a14820 Oak Vine Drive, Lutz, FL 33559, United States |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|