10th Workshop on
Algorithmic Approaches forTransportation Modelling,Optimization, and Systems
ATMOS’10, September 9, 2010, Liverpool, United Kingdom

Edited byThomas Erlebach
Marco Lübbecke

O A S I c s – V o l . 1 4 – AT M O S ’ 1 0

www.dagstuhl.de/oasics

Editors
Thomas Erlebach
Department of Computer Science
University of Leicester
Leicester, UK
t.erlebach@mcs.le.ac.uk

Marco Lübbecke
FB Mathematik, AG Optimierung
Technische Universität Darmstadt
Darmstadt, Germany
luebbecke@mathematik.tu-darmstadt.de

ACM Classification 1998
F.2 Analysis of Algorithms and Problem Complexity, G.1.6 Optimization, G.2.2 Graph Theory, G.2.3
Applications

ISBN 978-3-939897-20-0
Published online and open access bySchloss Dagstuhl – Leibniz-Center for Informatics gGmbH, Dagstuhl Publishing, Saarbrücken/Wadern,Germany.

Publication date
September, 2010.

Bibliographic information published by the Deutsche Nationalbibliothek
The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed
bibliographic data are available in the Internet at http://dnb.d-nb.de.
LicenseThis work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works license:
http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode.
In brief, this license authorizes each and everybody to share (to copy, distribute and transmit) the work
under the following conditions, without impairing or restricting the author’s moral rights:
Attribution: The work must be attributed to its authors.
Noncommercial: The work may not be used for commercial purposes.
No derivation: It is not allowed to alter or transform this work.
The copyright is retained by the corresponding authors.

Digital Object Identifier: 10.4230/OASIcs.ATMOS.2010.i

ISBN 978-3-939897-20-0

ISSN 2190-6807

http://www.dagstuhl.de/oasics

iii

OASIcs – OpenAccess Series in Informatics
OASIcs aims at a suitable publication venue to publish peer-reviewed collections of papers emerging froma scientific event. OASIcs volumes are published according to the principle of Open Access, i.e., they areavailable online and free of charge.

Editorial Board
Dorothea Wagner (Editor-in-Chief, Karlsruhe Institute of Technology)

ISSN 2190-6807

www.dagstuhl.de/oasics

AT M O S ’ 1 0

ContentsPreface
Thomas Erlebach and Marco Lübbecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

Invited Paper
Almost 20 Years of Combinatorial Optimization for Railway Planning: from Lagrangian
Relaxation to Column Generation
Alberto Caprara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1Regular Papers
Railway Track Allocation by Rapid Branching
Ralf Borndörfer, Thomas Schlechte, and Steffen Weider . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Robust Train Routing and Online Re-scheduling
Alberto Caprara, Laura Galli, Leo Kroon, Gábor Maróti, and Paolo Toth . . . . . . . . .

24

Heuristics for the Traveling Repairman Problem with Profits
T. Dewilde, D. Cattrysse, S. Coene, F.C.R. Spieksma, and P. Vansteenwegen . . . .

34

Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale
Train Timetabling
Frank Fischer and Christoph Helmberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Vertex Disjoint Paths for Dispatching in Railways
Holger Flier, Matúš Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych . . .

61

Engineering Time-Dependent Many-to-Many Shortest Paths Computation
Robert Geisberger and Peter Sanders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

Fast Detour Computation for Ride Sharing
Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, and Lars Volker

88

An Empirical Analysis of Robustness Concepts for Timetabling
Marc Goerigk and Anita Schöbel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Traffic Signal Optimization Using Cyclically Expanded Networks
Ekkehard Köhler and Martin Strehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Column Generation Heuristic for a Rich Arc Routing Problem
Sébastien Lannez, Christian Artigues, Jean Damay, and Michel Gendreau . . . . . . . . 130
The Team Orienteering Problem: Formulations and Branch-Cut and Price
Marcus Poggi, Henrique Viana, and Eduardo Uchoa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
The Complexity of Integrating Routing Decisions in Public Transportation Models
Marie Schmidt and Anita Schöbel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10).
Editors: T. Erlebach, M. Lübbecke; pp. v–vi
OpenAccess Series in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Preface
Transportation networks give rise to very complex and large-scale network optimization
problems requiring innovative solution techniques and ideas from mathematical optimization,
theoretical computer science, and operations research. Applicable tools and concepts include
those from graph and network algorithms, combinatorial optimization, approximation andonline algorithms, stochastic and robust optimization. Since 2000, the series of ATMOS
workshops brings together researchers and practitioners who are interested in all aspectsof algorithmic methods and models for transportation optimization and provides a forum
for the exchange and dissemination of new ideas and techniques. The scope of ATMOS
comprises all modes of transportation.
The 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10) was held in connection with ALGO 2010, hosted by
University of Liverpool, United Kingdom, on September 9, 2010. Topics of interest for
ATMOS ’10 were all optimization problems for passenger and freight transport, including – but not limited to – Infrastructure Planning, Vehicle Scheduling, Crew and Duty
Scheduling, Rostering, Routing in Road Networks, Novel Applications of Route PlanningTechniques, Demand Forecasting, Design of Tariff Systems, Delay Management, Mobile Applications, Humanitarian Logistics, Simulation Tools, Line Planning, Timetable Generation,and Routing and Platform Assignment. Of particular interest were: the successful integrationof several (sub)problems or planning stages, algorithms operating in an online/realtime
or stochastic setting, and heuristic approaches (including approximation algorithms) for
real-world instances.
In response to the call for papers we received 30 submissions, all of which were reviewed
by at least three referees. The submissions were judged on originality, technical quality, andrelevance to the topics of the conference. Based on the reviews, the program committee
selected the 12 papers which appear in this volume. Together, they quite impressively
demonstrate the range of applicability of algorithmic optimization to transportation problems
in a wide sense. In addition, Alberto Caprara kindly agreed to complement the programwith an invited talk entitled Almost 20 Years of Combinatorial Optimization for Railway
Planning: from Lagrangian Relaxation to Column Generation.
We would like to thank all the authors who submitted papers to ATMOS ’10, Alberto
Caprara for accepting our invitation to present an invited talk, and the local organizers for
hosting the workshop as part of ALGO 2010.

September 2010

Thomas Erlebach
Marco Lübbecke

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10).
Editors: T. Erlebach, M. Lübbecke; pp. vii–viii
OpenAccess Series in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Organization
Program Committee
Gabriele Di Stefano
Thomas Erlebach (co-chair)
Andrea Lodi
Marco Lübbecke (co-chair)
Matúš Mihalák
Petra Mutzel
Louis-Martin Rousseau
Heiko SchillingPeter Sanders
Maria Grazia Speranza
Frits Spieksma

University of L’Aquila
University of Leicester
University of Bologna
TU Darmstadt
ETH Zürich
TU Dortmund
Polytechnique Montreal
TomTom NVKarlsruher Institut für Technologie
University of Brescia
KU Leuven

Additional Reviewers
Nitin Ahuja
Ralf Borndörfer
Valentina Cacchiani
Serafino Cicerone
Sofie Coene
Gianlorenzo D’Angelo
Daniel Delling
Matteo Fischetti
Holger Flier
Laura Galli
Robert Geisberger
Clemens Gröpl
Carsten Gutwenger

Diego Klabjan
Christian Liebchen
Dennis Luxen
Jannick Matuschke
Jens Maue
Alfredo Navarra
Thomas Pajor
Maria Grazia ScutellàAndrea Tramontani
Daniele Vigo
Renato Werneck
Bernd Zey
Anna Zych

10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10).
Editors: T. Erlebach, M. Lübbecke; pp. ix–ix
OpenAccess Series in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany