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.
| Language | English |
|---|---|
| Title of host publication | 11th International Conference on Agents and Artificial Intelligence (ICAART 2019) |
| Editors | Luc Steels, Ana Rocha, Jaap van den Herik |
| Publisher | SCITEPRESS-Science and Technology Publications, Lda. |
| Pages | 285-293 |
| Number of pages | 9 |
| Volume | 2 |
| ISBN (Electronic) | 9789897583506 |
| State | Published - 2019 |
| Event | 11th International Conference on Agents and Artificial Intelligence, ICAART 2019 - Prague, Czech Republic Duration: 19 Feb 2019 → 21 Feb 2019 http://www.icaart.org/ |
Conference
| Conference | 11th International Conference on Agents and Artificial Intelligence, ICAART 2019 |
|---|---|
| Abbreviated title | ICAART2019 |
| Country | Czech Republic |
| City | Prague |
| Period | 19/02/19 → 21/02/19 |
| Internet address |
Fingerprint
Keywords
- Classification
- Convolutional Neural Networks
- Local Search
- Machine Learning
- Planning and Scheduling
Cite this
}
Determining capacity of shunting yards by combining graph classification with local search. / van de Ven, Arno J.G.; Zhang, Y.; Lee, Wan-Jui ; Eshuis, H.; Wilbik, A.M.
11th International Conference on Agents and Artificial Intelligence (ICAART 2019). ed. / Luc Steels; Ana Rocha; Jaap van den Herik. Vol. 2 SCITEPRESS-Science and Technology Publications, Lda., 2019. p. 285-293.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Determining capacity of shunting yards by combining graph classification with local search
AU - van de Ven,Arno J.G.
AU - Zhang,Y.
AU - Lee,Wan-Jui
AU - Eshuis,H.
AU - Wilbik,A.M.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Classification
KW - Convolutional Neural Networks
KW - Local Search
KW - Machine Learning
KW - Planning and Scheduling
UR - http://www.scopus.com/inward/record.url?scp=85064832609&partnerID=8YFLogxK
M3 - Conference contribution
VL - 2
SP - 285
EP - 293
BT - 11th International Conference on Agents and Artificial Intelligence (ICAART 2019)
PB - SCITEPRESS-Science and Technology Publications, Lda.
ER -