Introducing flexibility in any-start-time safe interval path planning
a case study on the Dutch railway network
E.A. Kemmeren (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Mathijs M. de Weerdt – Mentor (TU Delft - Algorithmics)
Issa K. Hanou – Graduation committee member (TU Delft - Algorithmics)
Rob M P Goverde – Graduation committee member (TU Delft - Transport, Mobility and Logistics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
During the daily operation of the railway network, ProRail is responsible for handling delays and planning ad hoc train movements. Train handling documents aid the traffic controllers in common situations. But when multiple trains are delayed, and these documents do not apply, they are left to their own expertise.
In this thesis, we introduce FlexSIPP, an algorithm to plan or replan agents in an existing multi-agent plan. FlexSIPP builds upon the prior works of any-start-time safe interval path planning, where the current routes of the agents are seen as moving obstacles. FlexSIPP loosens this restriction by introducing flexibility: the ability for an agent to delay its plan while minimally impacting other agents.
This algorithm is evaluated on the Dutch railway network. By finding tipping points, that is, the moment it is better to switch the order of two trains on the track to minimize the delay, we can recreate train handling documents. We show that FlexSIPP finds the same solutions within a minute in the case that no other trains are delayed. This implies that FlexSIPP is also able to aid traffic controllers in the case that other trains are delayed