Abstract
The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time.
Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones.
After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path.
Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chen YL (1994) Finding the K quickest simple paths in a network. Inf Process Lett 50:89–92
Chen YL, Chin YH (1990) The quickest path problem. Comput Oper Res 17(2):153–161
Katoh N, Ibaraki T, Mine H (1982) An efficient algorithm for K shortest simple paths. Networks 12:411–427
Martins EQV, Santos JLE (1997) An algorithm for the quickest path problem. Oper Res Lett 20:195–198
Moore MH (1976) On the fastest route for convoy-type traffic in flowrate-constrained networks. Trans Sci 10:113–124
Pascoal MMB, Captivo MEV, Clímaco JCN (2004) On the quickest path problem. Working paper n 15, CIO (http://cio.fc.ul.pt/files/15.2004.pdf)
Pascoal MMB, Captivo MEV, Clímaco JCN (2005) An algorithm for ranking quickest simple paths. Comput Oper Res 32(3):509–520
Pascoal MMB, Captivo MEV, Clímaco JCN (2006) A comprehensive survey on the quickest path problem. Ann Oper Res 147(1):5–21. Special issue on Multiple Objective Combinatorial and Discrete Optimization
Rosen JB, Sun SZ, Xue GL (1991) Algorithms for the quickest path problem and the enumeration of quickest paths. Comput Oper Res 18(6):571–584
Yen JY (1971) Finding the K shortest loopless paths in a network. Manag Sci 17:712–716
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pascoal, M., Captivo, M.E. & Clímaco, J.C. Computational experiments with a lazy version of a K quickest simple path ranking algorithm. TOP 15, 372–382 (2007). https://doi.org/10.1007/s11750-007-0033-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-007-0033-0