Determining capacity of shunting yards by combining graph classification with local search

Arno J.G. van de Ven, Y. Zhang, Wan-Jui Lee, H. Eshuis, A.M. Wilbik

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

2 Citations (Scopus)
78 Downloads (Pure)

Abstract

Dutch Railways (NS) uses a shunt plan simulator to determine capacities of shunting yards. Central to this simulator is a local search heuristic. Solving this capacity determination problem is very time consuming, as it requires to solve an NP-hard shunting planning problem, and furthermore, the capacity has to determined for a large number of possible scenarios at over 30 shunting yards in The Netherlands. In this paper, we propose to combine machine learning with local search in order to speed up finding shunting plans in the capacity determination problem. The local search heuristic models the activities that take place on the shunting yard as nodes in an activity graph with precedence relations. Consequently, we apply the Deep Graph Convolutional Neural Network, which is a graph classification method, to predict whether local search will find a feasible shunt plan given an initial solution. Our experimental results show our approach can significantly reduce the simulation time in determining the capacity of a given shunting yard. This study demonstrates how machine learning can be used to boost optimization algorithms in an industrial application.

Original languageEnglish
Title of host publication11th International Conference on Agents and Artificial Intelligence (ICAART 2019)
EditorsLuc Steels, Jaap van den Herik, Ana Rocha
PublisherSCITEPRESS-Science and Technology Publications, Lda.
Pages285-293
Number of pages9
Volume2
ISBN (Electronic)978-989-758-350-6
DOIs
Publication statusPublished - 2019
Event11th International Conference on Agents and Artificial Intelligence, ICAART 2019 - Prague, Czech Republic
Duration: 19 Feb 201921 Feb 2019
http://www.icaart.org/

Conference

Conference11th International Conference on Agents and Artificial Intelligence, ICAART 2019
Abbreviated titleICAART2019
CountryCzech Republic
CityPrague
Period19/02/1921/02/19
Internet address

    Fingerprint

Keywords

  • Classification
  • Convolutional Neural Networks
  • Local Search
  • Machine Learning
  • Planning and Scheduling

Cite this

van de Ven, A. J. G., Zhang, Y., Lee, W-J., Eshuis, H., & Wilbik, A. M. (2019). Determining capacity of shunting yards by combining graph classification with local search. In L. Steels, J. van den Herik, & A. Rocha (Eds.), 11th International Conference on Agents and Artificial Intelligence (ICAART 2019) (Vol. 2, pp. 285-293). SCITEPRESS-Science and Technology Publications, Lda.. https://doi.org/10.5220/0007398502850293