A branch-and-cut algorithm for scheduling train platoons in urban rail networks

With the emerging of virtual coupling technologies, the concept of train platoon, where different vehicles can be flexibly and dynamically grouped or decoupled, has become a hot research topic. In this study, the authors investigate the scheduling of train platoons for urban rail networks with time-dependent demand to mitigate passenger inconvenience. The authors propose a mixed-integer linear programming (MILP) model that simultaneously optimizes the train-platoon (de)coupling strategies, arrival/departure times at each station, and the running orders of trains, while considering limited rolling stock resources at the depots and the safety of trains at cross-line zones. To tackle computational challenges in real-world instances, the authors develop a customized branch-and-cut solution algorithm, based on the analysis of mathematical properties of the authors' MILP model, to generate (near-)optimal solutions more efficiently. In particular, the authors propose three sets of valid inequalities that are dynamically added to the model to strengthen the linear relaxation bounds at each node. The authors also design a customized branching rule in the search tree by imposing to branch on the key decision variables regarding the train orders at the cross-line zones. Real-world case studies based on the operational data of Beijing metro network are conducted to verify the effectiveness of the authors' approach. The results demonstrate that the authors' branch-and-cut-based approach evidently outperforms commercial solvers in terms of solution quality and computational efficiency. Compared to the current train schedule with fixed compositions in practice, the authors' approach with flexible coupling strategies can reduce the passenger dissatisfaction by over 15%.

• Record URL:
  • https://doi.org/10.1016/j.trb.2024.102891
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0191261524000158
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • © 2024 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Chai, Simin
  • 0000-0002-2219-5561
  • Yin, Jiateng
  • D’Ariano, Andrea
  • Liu, Ronghui
  • Yang, Lixing
  • Tang, Tao
• Publication Date: 2024-3

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: 102891
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 181
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Couplers; Rail transit; Scheduling; Traffic platooning; Train operations; Travel time reliability
• Geographic Terms: Beijing (China)
• Subject Areas: Operations and Traffic Management; Public Transportation; Railroads;

Filing Info

• Accession Number: 01909875
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 26 2024 3:42PM