Heuristic shortest path algorithms for transportation applications: State of the art

L. Fu, D. Sun, L. R. Rilett

Research output: Contribution to journalArticle

188 Scopus citations


There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortest paths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortest paths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience.

Original languageEnglish (US)
Pages (from-to)3324-3343
Number of pages20
JournalComputers and Operations Research
Issue number11
StatePublished - Nov 2006


  • Artificial intelligence
  • Heuristic shortest path algorithm
  • Heuristics
  • In-vehicle route guidance system (RGS)
  • Intelligent transportation systems (ITS)
  • Shortest path algorithm
  • Traffic network

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Heuristic shortest path algorithms for transportation applications: State of the art'. Together they form a unique fingerprint.

  • Cite this