A branch-and-price approach for solving the train unit scheduling problem. (December 2016)

• Record Type: Journal Article
• Authors: Lin, Zhiyuan; Kwan, Raymond S.K.
• Is Part Of: Transportation research. Volume 94(2016)
• Page Start: 97
• Page End: 120
• Publication Date: 2016-12
• Subjects: Rolling stock scheduling -- Train unit scheduling -- Integer multicommodity flow problems -- Branch-and-price; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2016.09.007
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: 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.