Decomposition of Stochastic Time-Varying Networks for the Path-Finding Problem Considering Travel Time Correlations and Heterogeneity of Users

Shortest path finding in stochastic networks hasattracted the attention of transportation researchers in recent years. Multiple optimal path finding problems are defined in the literature based on different reliability rules.The co-author Zockaie has recently developed an algorithm to solve such reliability-based path finding problems in static and time-dependent networks. Considering link travel time correlations and heterogeneity of travelers in terms of reliability valuation is the main superiority of this algorithm. The proposed algorithm includes a stage that requires solving deterministic shortest path problems for different link travel time realizations to create a set of candidate paths. This stage is the most complex computational part since it finds all-to-one shortest path trees for multiple destinations in each realization, even if only certain Origin-Destination pairs are interested. This study aims to improve the computational efficiency by extracting a sub-network for each interested Origin-Destination pair. The network size reduction results in a better performance of the algorithm. The network extraction is based on the comparison of pessimistic and optimistic solutions resulting from minimum and maximum travel times in all network links. This approach can also benefit from running the shortest path algorithms for different Origin-Destination pairs of interest in parallel.The algorithm is implemented on the large-scale Chicago downtown network. Resultantly, the optimal path, its travel time distribution,and the required execution time are compared between cases with and without network extraction.The results demonstrate significant computational improvement, especially when specific Origin-Destination pairs are interested. Impacts of different parameters, such as distance and optimistic/pessimistic travel time bounds on the accuracy of results and computational benefits are presented in the numerical results section.

• Supplemental Notes:
  • This paper was sponsored by TRB committee ADB30 Standing Committee on Transportation Network Modeling.
• Authors:
  • Fakhrmoosavi, Fatemeh
  • Zockaie, Ali
  • Abdelghany, Khaled
  • Hashemi, Hossein
• Conference:
  • Transportation Research Board 97th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2018-1-7 to 2018-1-11
• Date: 2018

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References;
• Pagination: 20p

Subject/Index Terms

• TRT Terms: Heterogeneity; Networks; Origin and destination; Stochastic processes; Travel time
• Geographic Terms: Chicago (Illinois)
• Subject Areas: Planning and Forecasting; Transportation (General);

Filing Info

• Accession Number: 01660908
• Record Type: Publication
• Report/Paper Numbers: 18-06556
• Files: TRIS, TRB, ATRI
• Created Date: Feb 22 2018 9:17AM