TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 04261

Algorithmic Methods for Railway Optimization

( Jun 20 – Jun 25, 2004 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/04261

Organizers
  • Leo G. Kroon (Erasmus Univ. - Rotterdam, NL)
  • Dorothea Wagner (KIT - Karlsruher Institut für Technologie, DE)
  • Frank Wagner (Deutsche Bahn - Berlin, DE & Freie Univ. Berlin, DE)
  • Christos Zaroliagis (CTI & University of Patras, GR)





Motivation

The main topic of the seminar is algorithmic methods for analyzing and solving problems arising in railway optimization. Special focus will be on the interplay between railway and other public transport systems. Beside algorithmics and mathematical optimization the relevance of formal models and the influence of application aspects for the problem modelling are considered as well.

Problems arising from the validation and improvement of the railway networks as well as other public transport systems will stand in the center of the discussion. Examples of such problems are: Network planning and Evaluation, Line planning, Timetable construction, Rolling stock circulation, Crew scheduling, Shunting, Delay Management or Timetable information. For analyzing and solving these interesting and challenging problems, typically techniques from network and combinatorial optimization and efficient algorithms must be provided. Transposing these into practical and applicable methods and implementations is a task to be undertaken by computer scientists. However, the high complexity of transport systems requires a coordinated interdisciplinary effort from mathematicians, computer scientists, traffic engineers, and people from railway companies. Actually, we are expecting intensive knowledge exchange between those groups during the seminar. Aspects to be discussed during the seminar are for example:

  • knowledge exchange about problems and methods applied so far in different national railway companies;
  • adaptation of techniques and methods already developed according to the requirements and conditions of different national railway systems as well as other transport systems like road traffic or airline transport;
  • study of new problems arising from the integration of national railway systems in a European context;
  • study of problems arising from the coordination of different transport systems.

Transport systems can be modelled in a uniform way as network systems. Planning and optimization in this context are typical examples of structured, combinatorial problems, such as scheduling, network flows, shortest paths and routing problems. However, the conditions and circumstances are induced by real-world demand. Therefore, a first step consists of transforming such complex practical problems into simplified models still describing their most important characteristics. After a model has been established, efficient methods and techniques are studied to develop solutions. Although mathematical solution methods and theoretically well-studied algorithms are available, the integration of many different optimization criteria and constraints calls for their talented and sophisticated use. Moreover, a combination of such mathematical methods with experiences from algorithms engineering and with extensive experimental studies, and of course new ideas, are essential.

Examples of research topics to be discussed are:

Timetable Construction
Although nice theoretical models for automatic timetable construction are found in the scientific literature, railway companies still mainly rely on non-automatic or at most semi-automatic systems for timetabling. There are few exceptions like the timetable construction system CADANS developed at CWI in cooperation with Railned and NS Reizigers. This package may serve as an example to other railway companies regarding its scientific content and innovative character in general. A long-term goal could be automatic timetabling for several European countries across national boundaries or even different public transport systems.
Timetable Information
Timetable information is a typical example of an optimization problem to be solved not only in national but also in a European context and not only for railway systems but for public transport in general. At the current state, the timetable information system Hafas, developed by the German company HaCon and provided by DB Systems is used by most European countries. Due to the huge size of the underlying data set, which is still increasing, the improvement of the algorithmic kernel of such a system is still a challenge. Moreover, providing dynamic timetable information is still a great challenge.
Network Planning and Evaluation
National railway companies are starting to apply algorithms and methods from combinatorial optimization in order to evaluate the quality of their network respectively of planned extensions of it. Relevant aspects in this area are the facilitation of the projected growth of the demand in the near future and the trade-off between customer service and operational costs. One research direction is the study of the applicability and the relevance of network flow methods for analyzing these problems. A long term goal is the development of evaluation methods for the European railway network across national boundaries.
Dynamic Systems
An interesting and challenging issue is the dynamic setting of algorithmic problems arising in transport systems. For all research topics in transport systems, time is an important aspect, because modelling parameters and constraints vary over the time. Examples are dynamic aspects of network planning and evaluation or delay management. This subject also includes automatic reactions to distortions, a problem that may be studied as a distributed combinatorial optimization problem.

Participants
  • Erwin Abbink (NS Reizigers - Utrecht, NL)
  • Norbert Ascheuer (Intranetz - Berlin, DE)
  • Ralf Borndörfer (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
  • Elias Dahlhaus (DB Systems GmbH - Frankfurt, DE) [dblp]
  • David De Almeida (SNCF - Paris, FR) [dblp]
  • Gabriele Di Stefano (University of L'Aquila, IT)
  • Rainer Feldmann (Universität Paderborn, DE)
  • Robert Firla (DB Mobility Logistics AG - Frankfurt am Main, DE)
  • Matteo Fischetti (University of Padova, IT) [dblp]
  • Frank Geraets (Deutsche Bahn - Berlin, DE)
  • Sven Grothklags (Universität Paderborn, DE)
  • Horst W. Hamacher (TU Kaiserslautern, DE)
  • Ronny Hansmann (TU Braunschweig, DE)
  • Florian Heinitz (FH Erfurt, DE)
  • Dennis Huisman (NS Reizigers - Utrecht, NL) [dblp]
  • Johann Hurink (University of Twente, NL)
  • Cor Hurkens (TU Eindhoven, NL)
  • Laura Ingolotti (Universidad Politécnica - Valencia, ES)
  • Riko Jacob (ETH Zürich, CH) [dblp]
  • Julie Jespersen Groth (DSB S-Tog - Copenhagen, DK) [dblp]
  • Niklas Kohl (Carmen Consulting, DK)
  • Goran Konjevod (Arizona State University - Tempe, US)
  • Leo G. Kroon (Erasmus Univ. - Rotterdam, NL) [dblp]
  • Christian Liebchen (TU Berlin, DE)
  • Alberto Marchetti-Spaccamela (Sapienza University of Rome, IT) [dblp]
  • Nicolas Marcos (SNCF - Paris, FR)
  • Gabor Maroti (CWI - Amsterdam, NL) [dblp]
  • Dick Middelkoop (Prorail - Utrecht, NL)
  • Rolf H. Möhring (TU Berlin, DE) [dblp]
  • Matthias Müller-Hannemann (TU Darmstadt, DE) [dblp]
  • Evangelia Pyrga (CTI & University of Patras, GR) [dblp]
  • Tomasz Radzik (King's College London, GB)
  • Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Anita Schöbel (Universität Göttingen, DE) [dblp]
  • Frank Schulz (KIT - Karlsruher Institut für Technologie, DE)
  • Leena Suhl (Universität Paderborn, DE) [dblp]
  • Kavitha Telikepalli (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Georgios Tsatsaronis (CTI & University of Patras, GR)
  • John van den Broek (TU Eindhoven, NL)
  • Dorothea Wagner (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Thomas Willhalm (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Christos Zaroliagis (CTI & University of Patras, GR) [dblp]
  • Uwe Zimmermann (TU Braunschweig, DE)

Related Seminars
  • Dagstuhl Seminar 16171: Algorithmic Methods for Optimization in Public Transport (2016-04-24 - 2016-04-29) (Details)