Finding Multiple Dissimilar Reliable Routes in Linear Time Complexity under Travel Time Uncertainties
There are considerable literatures on route travel time reliability and most of which are based on the stochastic characteristics of traffic networks. This paper studies reliable routing under travel time uncertainty with limited information available. Since a-prior shortest path (SP) may incur higher delays in an uncertain network, the route travel time reliability is considered to seek for reliable routes. Due to complexity and data availability, many sophisticated reliable routing algorithms are not suitable for large scale applications. In this paper, an algorithm finding several dissimilar routes ranked by their reliability indices based on a risk-averse hyperpath is proposed. For being searched on the pre-calculated hyperpath, which is a directed acyclic graph (DAG), the path-finding can be completed with a linear complexity.
-
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:
- Ma, Jiangshan
- Fukuda, Daisuke
-
Conference:
- Transportation Research Board 94th Annual Meeting
- Location: Washington DC, United States
- Date: 2015-1-11 to 2015-1-15
- Date: 2015
Language
- English
Media Info
- Media Type: Digital/other
- Features: Figures; References;
- Pagination: 22p
- Monograph Title: TRB 94th Annual Meeting Compendium of Papers
Subject/Index Terms
- TRT Terms: Algorithms; Reliability; Routing; Travel time; Uncertainty
- Subject Areas: Planning and Forecasting; Transportation (General); I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 01557042
- Record Type: Publication
- Report/Paper Numbers: 15-4376
- Files: TRIS, TRB, ATRI
- Created Date: Mar 16 2015 11:36AM