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.
-
Supplemental Notes:
- This paper was sponsored by TRB committee ADB30 Transportation Network Modeling
-
Corporate Authors:
500 Fifth Street, NW
Washington, DC United States 20001 -
Authors:
- Boyles, Stephen D
-
Conference:
- Transportation Research Board 91st Annual Meeting
- Location: Washington DC, United States
- Date: 2012-1-22 to 2012-1-26
- Date: 2012
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
- TRT Terms: Driver information systems; Evaluation; Networks; Real time information; Shortest path algorithms; Stochastic processes
- Uncontrolled Terms: Label-correcting; Online method
- Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 01373281
- Record Type: Publication
- Report/Paper Numbers: 12-3915
- Files: TRIS, TRB
- Created Date: Jun 21 2012 2:15PM