Identifying multiple reasonable alternative routes: Efficient vector labeling approach

Dongjoo Park, Shyam Lal Sharma, Laurence R. Rilett, Myungsoon Chang

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


An exact approach for identifying multiple reasonable paths in a transportation network is proposed. It is motivated by the deficiencies of heuristic approaches and K-shortest-path algorithms that have been used historically. The proposed algorithm is based on the so-called efficient vector labeling approach. The search space is pruned using a resource constraint. A route constraint is applied for maintaining the reasonableness of alternative routes. In addition, a dominance-checking concept is introduced to avoid identifying candidate subpaths at nodes that cannot satisfy travel time or route uniqueness requirements. The approach was demonstrated on a transportation network from Austin, Texas. It was found that the proposed algorithm can efficiently identify multiple reasonable alternative routes in transportation networks and has a number of advantages as compared with traditional K-shortest-path algorithms and heuristic approaches.

Original languageEnglish (US)
Pages (from-to)111-118
Number of pages8
JournalTransportation Research Record
Issue number1783
StatePublished - 2002
Externally publishedYes

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Identifying multiple reasonable alternative routes: Efficient vector labeling approach'. Together they form a unique fingerprint.

Cite this