Data-Driven Policy on Feasibility Determination for the Train Shunting Problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

62 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
Title of host publicationThe European Conference on Machine Learning and Principles (ECML2019) and Practice of Knowledge Discovery in Databases (PKDD2019)
EditorsUlf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet
Place of PublicationBerlin
PublisherSpringer
Pages719-734
Number of pages16
ISBN (Print)9783030461324
DOIs
Publication statusPublished - 30 Apr 2020
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019 - Wurzburg, Germany
Duration: 16 Sep 201920 Sep 2019

Publication series

NameLecture Notes in Artificial Intelligence
Volume11908 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019
CountryGermany
CityWurzburg
Period16/09/1920/09/19

Keywords

  • Graph classification
  • Local search
  • Planning and scheduling
  • Train shunting

Fingerprint Dive into the research topics of 'Data-Driven Policy on Feasibility Determination for the Train Shunting Problem'. Together they form a unique fingerprint.

Cite this