An Exact Label-Correcting Algorithm for the Online Shortest Path Problem in Cyclic Transportation Networks

The online shortest path (OSP) problem is a type of stochastic shortest path network problem in which certain arc costs are revealed en route, and the path updated accordingly to minimize expected cost, which has important applications in evaluating network-level impacts of real-time traffic information systems. In cyclic graphs where arc costs are reset after each traversal, the problem can be solved exactly by a label-setting algorithm, and approximately by a label-correcting algorithm converging to the correct solution in the limit. This article develops a finite label-correcting algorithm for the same problem, recognizing the role of cycles in determining finite convergence. A faster heuristic is also proposed, as well as a method for detecting graphs in which OSP is unbounded below. The new notion of a hypercycle is introduced to address the latter. Finally, the new algorithm is demonstrated on a medium-sized transportation network, indicating a speedup of approximately 75% as compared to existing label-correcting methods.

Language

  • English

Media Info

  • Media Type: Digital/other
  • Features: Figures; References;
  • Pagination: 16p
  • Monograph Title: TRB 91st Annual Meeting Compendium of Papers DVD

Subject/Index Terms

Filing Info

  • Accession Number: 01373281
  • Record Type: Publication
  • Report/Paper Numbers: 12-3915
  • Files: TRIS, TRB
  • Created Date: Jun 21 2012 2:15PM