Data-driven policy on feasibility determination for the train shunting problem (extended abstract)

Research output: Contribution to conferenceAbstractAcademic

6 Downloads (Pure)

Abstract

Parking, matching, scheduling, and routing are common problems in train maintenance. In particular, train units are commonly maintained and cleaned at dedicated shunting yards. The planning problem that results from such situations is referred to as the Train Unit Shunting Problem (TUSP). This problem involves matching arriving train units to service tasks and determining the schedule for departing trains. The TUSP is an important problem as it is used to determine the capacity of shunting yards and arises as a sub-problem of more general scheduling and planning problems. In this paper, we consider the case of the Dutch Railways (NS) TUSP. As the TUSP is complex, NS currently uses a local search (LS) heuristic to determine if an instance of the TUSP has a feasible solution. Given the number of shunting yards and the size of the planning problems, improving the evaluation speed of the LS brings significant computational gain. In this work, we use a machine learning approach that complements the LS and accelerates the search process. We use a Deep Graph Convolutional Neural Network (DGCNN) model to predict the feasibility of solutions obtained during the run of the LS heuristic. We use this model to decide whether to continue or abort the search process. In this way, the computation time is used more efficiently as it is spent on instances that are more likely to be feasible. Using simulations based on real-life instances of the TUSP, we show how our approach improves upon the previous method on prediction accuracy and leads to computational gains for the decision-making process.
Original languageEnglish
Number of pages2
Publication statusPublished - 2019
Event31st Benelux Conference on Artificial Intelligence and the 28th Belgian Dutch Conference on Machine Learning, BNAIC/BENELEARN 2019 - Brussels, Belgium
Duration: 6 Nov 20198 Nov 2019

Conference

Conference31st Benelux Conference on Artificial Intelligence and the 28th Belgian Dutch Conference on Machine Learning, BNAIC/BENELEARN 2019
CountryBelgium
CityBrussels
Period6/11/198/11/19

Keywords

  • Planning and Scheduling
  • Graph Classification
  • Deep Learning
  • Local Search
  • Train Shunting

Fingerprint Dive into the research topics of 'Data-driven policy on feasibility determination for the train shunting problem (extended abstract)'. Together they form a unique fingerprint.

Cite this