Journal
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
Volume 94, Issue -, Pages 97-120Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.trb.2016.09.007
Keywords
Rolling stock scheduling; Train unit scheduling; Integer multicommodity flow problems; Branch-and-price
Categories
Funding
- Engineering and Physical Sciences Council (EPSRC) [EP/M007243/1]
- Engineering and Physical Sciences Research Council [EP/M007243/1] Funding Source: researchfish
- EPSRC [EP/M007243/1] Funding Source: UKRI
Ask authors/readers for more resources
We propose a branch-and-price approach for solving the integer multicommodity flow model for the network-level train unit scheduling problem (TUSP). Given a train operator's fixed timetable and a fleet of train units of different types, the TUSP aims at determining an assignment plan such that each train trip in the timetable is appropriately covered by a single or coupled train units. The TUSP is challenging due to its complex nature. Our branch-and-price approach includes a branching system with multiple branching rules for satisfying real-world requirements that are difficult to realize by linear constraints, such as unit type coupling compatibility relations and locations banned for coupling/decoupling. The approach also benefits from an adaptive node selection method, a column inheritance strategy and a feature of estimated upper bounds with node reservation functions. The branch-and-price solver designed for TUSP is capable of handling instances of up to about 500 train trips. Computational experiments were conducted based on real-world problem instances from First ScotRail. The results are satisfied by rail practitioners and are generally competitive or better than the manual ones. (C) 2016 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available