10.4230/OASICS.ATMOS.2011.15
Corman, Francesco
Francesco
Corman
D'Ariano, Andrea
Andrea
D'Ariano
Pacciarelli, Dario
Dario
Pacciarelli
Pranzo, Marco
Marco
Pranzo
A bilevel rescheduling framework for optimal inter-area train coordination
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
Train Delay Minimization
Schedule Coordination
Bilevel Programming
Caprara, Alberto
Alberto
Caprara
Kontogiannis, Spyros
Spyros
Kontogiannis
2011
2011-09-19
2011-09-19
2011-09-19
en
urn:nbn:de:0030-drops-32636
10.4230/OASIcs.ATMOS.2011
978-3-939897-33-0
2190-6807
10.4230/OASIcs.ATMOS.2011
OASIcs, Volume 20, ATMOS 2011
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
2012
20
2
15
26
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Caprara, Alberto
Alberto
Caprara
Kontogiannis, Spyros
Spyros
Kontogiannis
2190-6807
Open Access Series in Informatics (OASIcs)
2011
20
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
403523 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers' work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management.
This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.
OASIcs, Vol. 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pages 15-26