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.