High Quality Approximation Algorithms for Vehicle Synchronization in Transit Systems

This paper introduces efficient algorithms to synchronize vehicles in a transit network so as to minimize the total passenger transfer time. The authors first formulate the problem as an optimization problem with congruence constraints. They show that the problem is non-deterministic polynomial-time (NP)-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, the authors show that the general problem is equivalent to the well-studied MAX CUT problem. As such, they use two well-known approximation algorithms for the max cut problem to solve the vehicle synchronization problem, and assess their quality on a real case study.

• Supplemental Notes:
  • This paper was sponsored by TRB committee AP050 Standing Committee on Bus Transit Systems.
• Corporate Authors:

  Transportation Research Board

  ,    
• Authors:
  • Abdolmaleki, Mojtaba
  • Masoud, Neda
  • Yin, Yafeng
• 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; Maps; References;
• Pagination: 7p

Subject/Index Terms

• TRT Terms: Approximation (Mathematics); Optimization; Public transit; Synchronous control; Transfers
• Subject Areas: Operations and Traffic Management; Passenger Transportation; Planning and Forecasting; Public Transportation;

Filing Info

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