A Local Search Algorithm for Train Unit Shunting with Service Scheduling
In this paper the authors consider the train unit shunting problem extended with service task scheduling. This problem originates from Dutch Railways, which is the main railway operator in the Netherlands. Its urgency stems from the upcoming expansion of the rolling stock fleet needed to handle the ever-increasing number of passengers. The problem consists of matching train units arriving on a shunting yard to departing trains, scheduling service tasks such as cleaning and maintenance on the available resources, and parking the trains on the available tracks such that the shunting yard can operate conflict-free. These different aspects lead to a computationally extremely difficult problem, which combines several well-known NP-hard problems. In this paper, the authors present the first solution method covering all aspects of the shunting and scheduling problem. They describe a partial order schedule representation that captures the full problem, and they present a local search algorithm that utilizes the partial ordering. The proposed solution method is compared with an existing mixed integer linear program in a computational study on realistic instances provided by Dutch Railways. The authors show that their local search algorithm is the first method to solve real-world problem instances of the complete shunting and scheduling problem. It even outperforms current algorithms when the train unit shunting problem is considered in isolation, that is, without service tasks. Although the authors' method was developed for the case of the Dutch Railways, it is applicable to any shunting yard or service location, irrespective of its layout, that uses self-propelling train units and that does not have to handle passing trains.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
-
Supplemental Notes:
- Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
-
Authors:
- van den Broek, Roel
- Hoogeveen, Han
- van den Akker, Marjan
- Huisman, Bob
- Publication Date: 2022-2
Language
- English
Media Info
- Media Type: Web
- Features: References;
- Pagination: pp 141-161
-
Serial:
- Transportation Science
- Volume: 56
- Issue Number: 1
- Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
- ISSN: 0041-1655
- Serial URL: http://transci.journal.informs.org/
Subject/Index Terms
- TRT Terms: Algorithms; Cleaning; Optimization; Scheduling; Train operations; Vehicle maintenance
- Identifier Terms: Nederlandse Spoorwegen
- Subject Areas: Maintenance and Preservation; Operations and Traffic Management; Planning and Forecasting; Railroads; Vehicles and Equipment;
Filing Info
- Accession Number: 01835801
- Record Type: Publication
- Files: TRIS
- Created Date: Feb 10 2022 5:05PM