A Network Contraction Algorithm Using an Iterative Learning Approach for Path Finding Problem in Stochastic Time-Varying Networks Considering Travel Time Correlations

The path finding problem has a broad application in different fields of science and engineering. Travel time uncertainty is a critical factor affecting both this problem and the route choice of transportation users. The major shortcoming of the existing algorithms for the reliable path finding problem is their inefficiency in terms of computational time. The aim of this study is to develop a network contraction approach to reduce the network size of each specific origin and destination (OD) pair in stochastic time-dependent networks. The network contraction is based on the comparison of optimistic/pessimistic solutions resulting from minimum/maximum travel time realizations of a Monte-Carlo simulation-based (MCS) approach. In this regard, a learning approach is proposed to utilize the information of the realizations from the early iterations of the MCS approach. The network is iteratively contracted, comparing the pessimistic travel time of each OD pair with the optimistic travel times of the OD pair through any node in the network. A learning factor is also introduced in order to provide options for more computational gain at the expense of accuracy. The performance and accuracy of the proposed approach is validated for the Salt Lake City network by comparing the number of nodes and the objective functions against those of the approach without any network contraction. The results demonstrate significant computational improvements using the learning approach with an acceptable accuracy level relative to the approach without network contraction.

• Supplemental Notes:
  • This paper was sponsored by TRB committee ADB30 Standing Committee on Transportation Network Modeling.
• Corporate Authors:

  Transportation Research Board

  ,    
• Authors:
  • Fakhrmoosavi, Fatemeh
  • Zockaie, Ali
  • Abdelghany, Khaled
  • Hashemi, Hossein
• Conference:
  • Transportation Research Board 98th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2019-1-13 to 2019-1-17
• Date: 2019

Language

• English

Media Info

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

Subject/Index Terms

• TRT Terms: Iterative methods; Learning; Network links; Origin and destination; Shortest path algorithms; Stochastic processes; Travel time
• Uncontrolled Terms: Path finding
• Subject Areas: Highways; Planning and Forecasting;

Filing Info

• Accession Number: 01698247
• Record Type: Publication
• Report/Paper Numbers: 19-02992
• Files: TRIS, TRB, ATRI
• Created Date: Mar 1 2019 3:51PM