Efficient algorithm for finding k shortest paths based on re-optimization technique

Bi Yu Chen, Xiao Wei Chen, Hui Ping Chen, William H.K. Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

This study proposes an efficient deviation path algorithm for finding exactly k shortest simple paths without loops in road networks. The algorithm formulates the deviation path calculation process as repeated one-to-one searches for the shortest path in a dynamic network, where only a node and a link are restored at each search. Using this formulation, the proposed algorithm maintains and updates a single shortest path tree rooted at the destination. A re-optimization technique, lifelong planning A*, is incorporated into the algorithm to efficiently calculate each deviation path by reusing the shortest path tree generated at the previous search. To verify the efficiency of the proposed algorithm, computational experiments were conducted using several real road networks, and the results showed that the proposed algorithm performed significantly better than state-of-the-art algorithms.

Original languageEnglish
Article number101819
JournalTransportation Research Part E: Logistics and Transportation Review
Volume133
DOIs
Publication statusPublished - Jan 2020

Keywords

  • K shortest path problem
  • Lifelong planning A*
  • Re-optimization technique

ASJC Scopus subject areas

  • Business and International Management
  • Civil and Structural Engineering
  • Transportation

Cite this