A Local Search Algorithm for Train Unit Shunting with Service Scheduling

Roel van den Broek (), Han Hoogeveen (), Marjan van den Akker () and Bob Huisman ()
Additional contact information
Roel van den Broek: Department of Information and Computing Sciences, Universiteit Utrecht, 3584 CC Utrecht, Netherlands
Han Hoogeveen: Department of Information and Computing Sciences, Universiteit Utrecht, 3584 CC Utrecht, Netherlands
Marjan van den Akker: Department of Information and Computing Sciences, Universiteit Utrecht, 3584 CC Utrecht, Netherlands
Bob Huisman: Nederlandse Spoorwegen, 3511 ER Utrecht, Netherlands; Department of Software and Computer Technology, Delft University of Technology, 2628 XE Delft, Netherlands

Transportation Science, 2022, vol. 56, issue 1, 141-161

Abstract: In this paper we 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, we present the first solution method covering all aspects of the shunting and scheduling problem. We describe a partial order schedule representation that captures the full problem, and we 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. We show that our 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 our 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.

Keywords: shunting; local search; scheduling (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1090 (application/pdf)

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:inm:ortrsc:v:56:y:2022:i:1:p:141-161

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().