Ranking One Million Simple Paths in Road Networks

Antonio Sedeño-Noda ()
Additional contact information
Antonio Sedeño-Noda: Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, C. P. 38271, San Cristóbal de La Laguna, Santa cruz de Tenerife, España

Asia-Pacific Journal of Operational Research (APJOR), 2016, vol. 33, issue 05, 1-20

Abstract: In this paper, we address the problem of finding the K best paths connecting a given pair of nodes in a directed graph with arbitrary lengths. We introduce an algorithm to determine the K best paths in order of length when repeat nodes in the paths are allowed. We obtain an O(m + nlog n + K(n +log K)) time and O(K + m) space algorithm to implicitly determine the K shortest paths in a directed graph with n nodes and m arcs. Empirical results where the algorithm was used to compute one hundred million paths in USA road networks are reported. A non-trivial modification of the previous algorithm is performed obtaining an O(k1(nm +log k1)) time method to compute paths without repeat nodes and to answer the next question: how many paths k1 in practice are needed to identify K simple paths using the previous algorithm? We find that the response is usually O(K) based on an experiment computing one million paths in USA road networks. The determination of a theoretical tight bound on k1 remains as an open problem.

Keywords: Combinatorial optimization; shortest path algorithms; K best solutions (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595916500421
Access to full text is restricted to subscribers

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:wsi:apjorx:v:33:y:2016:i:05:n:s0217595916500421

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595916500421

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().