A multi-objective framework for strategic railway timetabling: integration of ant colony optimisation and mixed integer programming
The paper presents an algorithmic framework to perform automatic timetabling, developed within the research project Tools for mathematical optimisation of strategic railway timetable models funded by the Norwegian Railway Directorate and carried out by Trenolab SRLS and Gustave Eiffel University.
A prototype tool to automatically generate timetable drafts is presented, intended to help planners to perform such tasks as capacity studies and strategic timetable planning.
The paper describes the algorithmic core of the tool, called Automatic Timetabler with Multiple Objectives (ATMO). It implements a Paretian multi-objective approach, which returns the user a set of timetables representing the optimal trade-off according to given Key Performance Indicators. ATMO is composed by a Multi-Objective Ant Colony Optimisation (MOACO) algorithm integrated with a Mixed Integer Linear Programming (MILP) formulation.
MOACO performs a fast-but-coarse exploration of the solution space, populating and maintaining a set of Pareto-Optimal timetables. The timetables generated by MOACO are then fed to a MILP formulation which performs a further refinement, finally providing feasible, high-quality timetables.
The paper describes the framework from an algorithmic perspective, explaining how the proposed approach represents a novel contribution to the field of Automatic Timetabling methods. A series of application tests are discussed as well, based on case studies driven from real practice in Norway.