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:
  • Date: 2019


  • English

Media Info

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

Subject/Index Terms

Filing Info

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