Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Corman, Francesco; D'Ariano, Andrea; Pacciarelli, Dario; Pranzo, Marco http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-32636
URL:

; ; ;

A bilevel rescheduling framework for optimal inter-area train coordination

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{corman_et_al:OASIcs:2011:3263,
  author =	{Francesco Corman and Andrea D'Ariano and Dario Pacciarelli and Marco Pranzo},
  title =	{{A bilevel rescheduling framework for optimal inter-area train coordination}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--26},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Alberto Caprara and Spyros Kontogiannis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3263},
  URN =		{urn:nbn:de:0030-drops-32636},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2011.15},
  annote =	{Keywords: Train Delay Minimization, Schedule Coordination, Bilevel Programming}
}

Keywords: Train Delay Minimization, Schedule Coordination, Bilevel Programming
Seminar: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI