Algorithms for Robust and online Railway optimization:
Improving the Validity and reliAbility of Large scale systems (ARRIVAL)

European commission ARRIVAL Project coordination


Neu! Shortcut to ARRIVAL/MATHEON Fall School 2006 on Timetabling and Line Planning!


Duration: 2006 - 2009
Site Leader: Prof. Dr. Rolf H. Möhring
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Germany
Tel: +49 (0)30 - 2 45 94
email: moehring@math.tu-berlin.de
Researchers: Christian Liebchen
Dr. Marco Lübbecke
for address, see above
emails: {liebchen,luebbeck}@math.tu-berlin.de
Support: 6th Framework Programme of the European Commission


General Project Summary and Goals.

Algorithmic methods have reached a state of maturity as a consequence of decades of research where real-world problems were posed to the algorithms community triggering important developments in the field. Despite this success, the current state of algorithmic research still faces severe difficulties, or cannot cope at all, with highly-complex and data-intensive applications as those dealing with optimization issues in large-scale communication and transportation networks. The complexity and size of such optimization problems pose new challenges for algorithmic research, and their efficient solution requires a radically new foundational paradigm.

In this project, we are interested in establishing such a new paradigm and considerably advance the current state of algorithmic research by attacking optimization questions in perhaps the most complex and largest in scale (transportation) setting: that of railway systems. Railway optimization deals with planning and scheduling problems over several time horizons. We focus on two important and actually unexplored facets of planning that pose even harder optimization questions: robust planning and online (real-time) planning. These two, tightly coupled, facets constitute a proactive and a reactive approach, respectively, to deal with disruptions to the normal operation.

Our main goal is to develop the necessary foundational algorithmic research in order to provide ingenious and sound answers to the fundamental efficiency and quality issues encapsulated in robust and online planning of complex, large-scale systems as those in railways. We will endeavour to develop a thorough understanding of the fundamental issues that make robust and online railway optimization problems hard and to subsequently develop new algorithmic and complexity principles to deal with hardness through an integrated, interdisciplinary approach drawn from algorithmic, operations research, and constraint programming techniques.

Work Package 1: New Models for Robust and Online Planning.

We proceed in three interdependent stages, with increasing scientific challenge, innovation, and risk. In the robust planning stage, the full planning process of railways is reconsidered under the perspective of robust and online optimization; in the integral planning stage, separately considered problems so far are simultaneously approached and integrated; in the new models stage, new computational and combinatorial models for robust and online planning of large-scale systems are developed.

Work Package 3: Robust and Online Timetabling and Timetable Information Updating.

Our aim is to understand and advance the state-of-the-art of methods from computer science and operations research that can help to solve robust and online timetable problems for large-scale (multi-national) railway networks. Main computer science topics that will be addressed are the integration of optimization and stochasticity, fast approximation algorithms and heuristics for generating alternative timetables in case of disruptions, and dependable methods for disseminating the alternative plans to the involved actors.

Cooperation.

For a complete list of project partners within ARRIVAL, please consult the ARRIVAL web page.


Events.

[1] ARRIVAL Kick-off Meeting
[2] Neu! ARRIVAL/MATHEON Fall School 2006 on Timetabling and Line Planning