PATH ENUMERATION BY FINDING THE CONSTRAINED K-SHORTEST PATHS
One of the first steps in analyzing transport problems is the explicit enumeration of the paths to be considered. In realistically-sized networks, the number of paths that can be constructed is virtually infinite. This article addresses the path generation problem, defined as the problem of generating a path-set of manageable size that contains the most relevant paths for a specific transport problem. The authors begin with an overview of existing algorithmic approaches to the path enumeration problem, then focuses on K-shortest path algorithms in general and Lawler's algorithm in particular. Next, the new CKSP (constrained K-shortest paths) algorithm is proposed in a description that is largely parallel to the explanation of Lawler's algorithm. The authors also provide a numerical example in the context of path enumeration. Constraints are defined that eliminate all overly circuitous and strongly overlapping paths. The authors conclude that, as opposed to the conventional method, the proposed implementation of the CKSP method displays only a limited sensitivity to the level of restriction of the constraints. Thus, the proposed method can enumerate paths for realistically sized networks.
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
-
Corporate Authors:
The Boulevard, Langford Lane
Kidlington, Oxford United Kingdom OX5 1GB -
Authors:
- Van der Zijpp, N J
- Catalano, S F
- Publication Date: 2005-7
Language
- English
Media Info
- Features: Figures; References; Tables;
- Pagination: p. 545-563
-
Serial:
- Transportation Research Part B: Methodological
- Volume: 39B
- Issue Number: 6
- Publisher: Elsevier
- ISSN: 0191-2615
- Serial URL: http://www.sciencedirect.com/science/journal/01912615
Subject/Index Terms
- TRT Terms: Algorithms; Network analysis (Planning); Numerical analysis; Shortest path algorithms
- Uncontrolled Terms: Lawler's algorithm
- Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting;
Filing Info
- Accession Number: 00988898
- Record Type: Publication
- Files: TRIS, ATRI
- Created Date: Apr 4 2005 12:00AM