Path enumeration by finding the constrained K-shortest paths
N.J. van der Zijpp and
S. Fiorenzo Catalano
Transportation Research Part B: Methodological, 2005, vol. 39, issue 6, 545-563
Abstract:
This paper deals with algorithms for finding the constrained K-shortest paths (CKSP) and their application to the path enumeration problem. An attractive property of using Constrained Shortest Paths for path enumeration is that paths can be selected based on objective criteria. The conventional way of finding these paths is to compute a sufficiently large number of overall shortest paths, and deleting the ones that do not satisfy the constraints. However for realistically sized networks, combined with restrictive constraints this method becomes unfeasible because of CPU time restrictions. A new method is proposed that finds the feasible shortest paths directly and can be applied in combination with a wide class of constraints. The paper explains how this CKSP algorithm can be implemented using the ordinary shortest path computation as its elementary operation. An example is provided in which the method is used to enumerate paths while avoiding strongly overlapping and overly circuitous paths. In this context the computational performance of the CKSP method is compared with that of the conventional method. On a network consisting of 200 nodes a speed-up factor exceeding 62 has been demonstrated on a problem that involves finding the 200 constrained shortest paths. The speed-up factor increases sharply with the size of the network and the level of restriction of the constraints. 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. While the conventional method could only deal with small networks, the proposed method can also enumerate paths for more realistically sized networks.
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(04)00102-X
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:39:y:2005:i:6:p:545-563
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 ().