Implementation issues for the reliable a priori shortest path problem

Xing Wu, Yu Marco Nie

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Solution techniques are studied for the problem of finding a priori paths that are shortest to ensure a specified probability of on-time arrival in a stochastic network. A new discretization scheme called α-discrete is proposed. The scheme is well suited to large-scale applications because it does not depend on problem-specific parameters. A procedure for evaluating convolution integrals based on the new scheme is given, and its complexity is analyzed. Other implementation strategies also are discussed to improve the computational performance of the exact yet nondeterministic polynomial label-correcting algorithm. These include an approximate method based on extreme dominance and two cycle-avoidance strategies. Comprehensive numerical experiments are conducted to test the effects of the proposed implementation strategies using different networks and different distribution types.

Original languageEnglish (US)
Pages (from-to)51-60
Number of pages10
JournalTransportation Research Record
Issue number2091
StatePublished - 2009

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Implementation issues for the reliable a priori shortest path problem'. Together they form a unique fingerprint.

Cite this