D6.1 Report on the description of algorithms for longterm timetabling, short-term timetabling and rolling stock planning

This deliverable describes the main developments carried out in WP6, with focus on models and algorithms to improve long-term and short-term timetabling of the railway network. The activities in WP6 aim at increasing infrastructure and transport utilisation capacity through optimised and robust timetables, synchronized with rolling stock planning. These objectives have been targeted through:

1. The development of advanced algorithms for the generation and adjustment of timetables and rolling stock planning, which will be further developed and completed in WP7
2. The definition a suitable family of use cases, which will be demonstrated in WP
3. The implementation of specific technical enablers.

Addressed technical enabler and the defined use cases and demonstrators are synthetically reported in the background Section 3 of this document. All the timetabling and rolling stock planning problems tackled in WP6 require to find good quality solutions fulfilling various physical and logical requirements, and the business rules of the railway infrastructure managers and railway undertakings. As such, they can be viewed as optimization problems, which can be modelled and solved by means of mathematical optimization, an AI discipline which concerns the making of optimal decisions. With few exceptions, the models developed in WP6 are based on Mixed Integer Linear Programming or Constraint Programming, solved then by means of specialized commercial solvers (as CPLEX, or GUROBI), or by ad-hoc heuristic algorithms, such as local search, genetic algorithms, simulated annealing. Mathematical decomposition and graph theory are also exploited to model and solve various problems.

Although the algorithms developed in WP6 are not yet fully completed – they will be in the first year of WP7 – still some interesting and promising conclusions can be drawn. In fact, tests on realistic instances have been performed. It turns out that the developed methods work well for the size and the type of instances for which they are designed. In turn, this implies that we can expect they will tackle the instances arising in the demonstrations of the planned use-cases. Ultimately, this means that in general the approaches will be able to support human planners in their activities, and to automatize segments of the current planning process. Preliminary results show that solutions of high quality can be produced in short computing time. One limit is that, since the algorithms will be completed and demonstrated in WP7, these conclusions are still very preliminary. Also, the solution of full integrated problems appears to be still out of reach, and we need to content ourselves with tackling suitable subproblems. For instance, we can possibly compute an optimal or quasi-optimal timetable for the entire Norwegian network, and subsequently calculate an associated optimal rolling stock rotation, and solve the stabling problem, but we are still far from being able to solve to optimality the three problems jointly.