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

Simin Chai, Jiateng Yin, D’Ariano, Andrea, Ronghui Liu, Lixing Yang and Tao Tang

Transportation Research Part B: Methodological, 2024, vol. 181, issue C

Abstract: 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, we investigate the scheduling of train platoons for urban rail networks with time-dependent demand to mitigate passenger inconvenience. We 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, we develop a customized branch-and-cut solution algorithm, based on the analysis of mathematical properties of our MILP model, to generate (near-)optimal solutions more efficiently. In particular, we propose three sets of valid inequalities that are dynamically added to the model to strengthen the linear relaxation bounds at each node. We 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 our approach. The results demonstrate that our 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, our approach with flexible coupling strategies can reduce the passenger dissatisfaction by over 15%.

Keywords: Transportation; Train scheduling; Flexible coupling; Passenger dissatisfaction; Branch-and-cut (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524000158
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:181:y:2024:i:c:s0191261524000158

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.102891

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().