A column generation approach to train timetabling on a corridor |
| |
Authors: | Valentina Cacchiani Alberto Caprara Paolo Toth |
| |
Institution: | (1) D.E.I.S., University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy |
| |
Abstract: | We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that
are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable
for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which
each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose
LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that
the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous
approaches, and of solving some small-size instances to proven optimality.
|
| |
Keywords: | Train timetabling ILP-formulation Column generation Separation Constructive heuristics Experimental results |
本文献已被 SpringerLink 等数据库收录! |