Train routing selection problem: Ant colony optimization versus integer linear programming

The real-time Railway Traffic Management Problem (rtRTMP) is the problem of detecting and solving time-overlapping conflicting request done by multiple trains on the same track resources. It typically consists in taking retiming, reordering or rerouting train actions in such a way that the propagation of disturbances in the railway network is minimized. The rtRTMP is an NP-Hard problem and finding good strategy to simplifying its solution process is paramount to obtain good quality solutions in a short computation. Solving the Train Routing Selection Problem (TRSP) aims to do so, by limiting the number of routing variables through a pre-processing that selects the most promising routing alternatives among the available ones for each train in order to reduce the size of rtRTMP instances. This paper studies the performance of an Ant Colony Optimization (ACO) algorithm for the same problem. An integer linear programming formulation for the TRSP is presented and solved using a commercial software, and it is considered as a benchmark. Computational experiments are performed on two practical case studies of the French railway infrastructure: the line near the city of Rouen and the Lille terminal station area. ACO and the commercial solver perform comparably only on small instances and both are able to find optimal solutions. However, on larger instances, the ACO algorithm outperforms the commercial software, both in terms of computation time and solution quality.