Author
Listed:
- Wang, Dian
- D’Ariano, Andrea
- Zhao, Jun
- Zhan, Shuguang
- Peng, Qiyuan
Abstract
This study investigates the joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines with multiple depots, multiple line services, and multiple compositions. The rotation planning aims at connecting the given train trips into train sequences (each of which is served by an individual rolling stock) and determining the routing plan of rolling stocks to pass through visited turnback stations while connecting train trips. The task of the depot deadhead scheduling is to determine conflict-free deadhead routes and deadhead timetables of rolling stocks between the origin/destination of each train sequence and corresponding depot. We formulate the studied problem as a generalized set partitioning-type model containing an exponential number of variables, by using a new time-space network representation and by proposing a novel modelling method for the departure–arrival headway requirement to control the number of constraints. Owing to the complexity of this model, a column generation-based algorithm is adopted to solve efficiently practical-size problems. We enhance a standard column generation (to compute tight lower bound) by further incorporating procedures of variable rounding and halted column generation, to strengthen the capability of searching for better quality solutions. Customized acceleration mechanisms are also explored to speed up the convergence of column generation and the computation of best-known integer solution. We compare our approach with three benchmark approaches and the trial-and-error-based empirical method used by rail dispatchers in practice. Computational results reveal that our approach outperforms these benchmark approaches by computing (near-)optimal solutions. Our optimized solution for a large real-world instance (computed within a practically reasonable computation time) is better than the empirical solution, in terms of all the considered objective function parts.
Suggested Citation
Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhan, Shuguang & Peng, Qiyuan, 2024.
"Joint rolling stock rotation planning and depot deadhead scheduling in complicated urban rail transit lines,"
European Journal of Operational Research, Elsevier, vol. 314(2), pages 665-684.
Handle:
RePEc:eee:ejores:v:314:y:2024:i:2:p:665-684
DOI: 10.1016/j.ejor.2023.10.012
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:314:y:2024:i:2:p:665-684. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.