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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Uittreksel

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.

TaalEngels
Titel11th International Conference on Agents and Artificial Intelligence (ICAART 2019)
RedacteurenLuc Steels, Ana Rocha, Jaap van den Herik
UitgeverijSCITEPRESS-Science and Technology Publications, Lda.
Pagina's285-293
Aantal pagina's9
Volume2
ISBN van elektronische versie9789897583506
StatusGepubliceerd - 2019
Evenement11th International Conference on Agents and Artificial Intelligence, ICAART 2019 - Prague, Tsjechië
Duur: 19 feb 201921 feb 2019
http://www.icaart.org/

Congres

Congres11th International Conference on Agents and Artificial Intelligence, ICAART 2019
Verkorte titelICAART2019
LandTsjechië
StadPrague
Periode19/02/1921/02/19
Internet adres

Vingerafdruk

Learning systems
Simulators
Industrial applications
Neural networks
Planning
Local search (optimization)

Trefwoorden

    Citeer dit

    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, A. Rocha, & J. van den Herik (editors), 11th International Conference on Agents and Artificial Intelligence (ICAART 2019) (Vol. 2, blz. 285-293). SCITEPRESS-Science and Technology Publications, Lda..
    van de Ven, Arno J.G. ; Zhang, Y. ; Lee, Wan-Jui ; Eshuis, H. ; Wilbik, A.M./ Determining capacity of shunting yards by combining graph classification with local search. 11th International Conference on Agents and Artificial Intelligence (ICAART 2019). redacteur / Luc Steels ; Ana Rocha ; Jaap van den Herik. Vol. 2 SCITEPRESS-Science and Technology Publications, Lda., 2019. blz. 285-293
    @inproceedings{ae9adbd7e4894d79ad0771794c4e9f15,
    title = "Determining capacity of shunting yards by combining graph classification with local search",
    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.",
    keywords = "Classification, Convolutional Neural Networks, Local Search, Machine Learning, Planning and Scheduling",
    author = "{van de Ven}, {Arno J.G.} and Y. Zhang and Wan-Jui Lee and H. Eshuis and A.M. Wilbik",
    year = "2019",
    language = "English",
    volume = "2",
    pages = "285--293",
    editor = "Luc Steels and Ana Rocha and {van den Herik}, Jaap",
    booktitle = "11th International Conference on Agents and Artificial Intelligence (ICAART 2019)",
    publisher = "SCITEPRESS-Science and Technology Publications, Lda.",

    }

    van de Ven, AJG, Zhang, Y, Lee, W-J, Eshuis, H & Wilbik, AM 2019, Determining capacity of shunting yards by combining graph classification with local search. in L Steels, A Rocha & J van den Herik (redactie), 11th International Conference on Agents and Artificial Intelligence (ICAART 2019). vol. 2, SCITEPRESS-Science and Technology Publications, Lda., blz. 285-293, Prague, Tsjechië, 19/02/19.

    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). redactie / Luc Steels; Ana Rocha; Jaap van den Herik. Vol. 2 SCITEPRESS-Science and Technology Publications, Lda., 2019. blz. 285-293.

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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 -

    van de Ven AJG, Zhang Y, Lee W-J, Eshuis H, Wilbik AM. Determining capacity of shunting yards by combining graph classification with local search. In Steels L, Rocha A, van den Herik J, redacteurs, 11th International Conference on Agents and Artificial Intelligence (ICAART 2019). Vol. 2. SCITEPRESS-Science and Technology Publications, Lda.2019. blz. 285-293.