Boosting local search using machine learning: a study on improving local search by graph classification in determining capacity of shunting yards

Arno van de Ven, Yingqian Zhang, Wan-Jui Lee

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

Abstract

Determining the maximum capacities of shunting yards is an important problem at Dutch Railways (NS). Solving this capacity determination problem is computational expensive as it requires to solve an NP-hard shunting planning problem. Currently, NS uses a shunt plan simulator where a local search heuristic is implemented to determine such capacities.

In this paper, we study how to combine machine learning with local search in order to speed up finding shunting plans in the capacity determination problem. We investigate this in the following two ways. In the first approach, we propose to use the Deep Graph Convolutional Neural Network (DGCNN) to predict whether local search will find a feasible shunt plan given an initial solution. Using instances generated from the simulator, we build a classification model and show our approach can significantly reduce the simulation time in determining the capacity of a given shunting yard.

In the second approach, we investigate whether we can use machine learning to help local search decide which promising areas to explore during search. Therefore, DGCNN is applied to predict the order of search operators in which the local search heuristic should evaluate. We show that accurately predicting the evaluation order could find improved solutions faster, and may lead to more consistent plans.
Original languageEnglish
Title of host publicationAgents and Artificial Intelligence - 11th International Conference, ICAART 2019, Revised Selected Papers
EditorsJaap van den Herik, Ana Paula Rocha, Luc Steels
Place of PublicationCham
PublisherSpringer
Pages183-203
Number of pages21
ISBN (Electronic)978-3-030-37494-5
ISBN (Print)978-3-030-37493-8
DOIs
Publication statusPublished - Dec 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringerlink
Volume11978
NameLecture notes in artificial intelligence
Volume11978

Keywords

  • Classification
  • Local search
  • Machine learning - Convolutional neural networks
  • Planning and scheduling

Fingerprint

Dive into the research topics of 'Boosting local search using machine learning: a study on improving local search by graph classification in determining capacity of shunting yards'. Together they form a unique fingerprint.

Cite this