© 2020 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
Vehicle scheduling and rescheduling are central challenges for the planning and operation of railways. Even though these problems have been the subject of many research and development over several decades, railways still – with good reason – at the end of the day rely on well-trained and experienced personnel to provide practical solutions to these problems. Over the last couple of years, novel techniques based on machine learning have been used to propose solutions to problems such as image and speech recognition that could not have been imagined previously. The aim of machine learning is to design algorithms that can improve automatically through experience. The experience possessed by traffic dispatchers is often their greatest tool. It is, therefore, not implausible that machine learning techniques could also be used to provide better automation or support to the railway scheduling and rescheduling problems. This article describes the results of a study conducted to evaluate the extent to which solutions to the scheduling and rescheduling problems could be improved using a machine learning technique called reinforcement learning. The solutions obtained using this technique are compared with solutions obtained using classical algorithmic and constraint-based search techniques. The initial results have been obtained under a simulated environment developed by Swiss Federal Railways for the public Flatland Challenge competition. This research has been ranked number 4 in this international competition. Although these initial results have been obtained under simulated conditions and using limited computational resources, they look promising compared to classical scheduling and rescheduling solutions and suggest that further work in this direction could be worthwhile
deadlock avoidance, machine learning, multi-agent path finding, neural network, railway operation, reinforcement learning, rescheduling, scheduling, traffic management
[1] Cohen, L., Wagner, G., Kumar, T.S., Choset, H. & Koenig, S., Rapid randomized restarts for multi-agent path finding solvers, 2017.
[2] Andreychuk, A., Yakovlev, K., Atzmon, D. & Stern, R., Multi-agent pathfinding with continuous time, 2019.
[3] Barták, R., Švancara, J. & Vlk, M., A scheduling-based approach to multi-agent path finding. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 748-756, 2018.
[4] Sharon, G., Stern, R., Felner, A. & Sturtevant, N.R., Conflict-based search for optimal multi-agent pathfinding. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pp. 563-569, 2012.
[5] Standley, T., Finding optimal solutions to cooperative pathfinding problems. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, pp. 173-178, 2010.
[6] Standley, T. & Korf, R., Complete algorithms for cooperative pathfinding problems. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 668-673, 2011.
[7] Cáp, M., Novák, P., Kleiner, A. & Selecký, M., Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering, 12, pp. 835-849, 2015.
[8] Li, J.-Q., Mirchandani, P.B. & Borenstein, D., The vehicle rescheduling problem: model and algorithms. Networks: An International Journal, 50, pp. 211-229, 2007.
[9] Zuo, X., An immune algorithm based robust scheduling methods. Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies, pp. 124-140, 2009.
[10] Gawrilow, E., Klimm, M., Möhring, R.H. & Stenzel, B., Conflict-free vehicle routing: load balancing and deadlock prevention. EURO Journal on Transportation and Logistics, 1, pp. 87-111, 2012.
[11] Wälter, J., Existing and novel approaches to the vehicle rescheduling problem, HSR University of Applied Science Rapperswil: Switzerland, https://eprints.hsr.ch/855/, 2020.