An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling

摘要

Train timetabling is a difficult and very tightly constrained combinatorial problem that deals with the construction of train schedules. We focus on the particular problem of local reconstruction of the schedule following a small perturbation, seeking minimisation of the total accumulated delay by adapting times of departure and arrival for each train and allocation of resources (tracks, routing nodes, etc.). We describe a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic to gradually reconstruct the schedule by inserting trains one after another following the permutation. This algorithm can be hybridised with ILOG's commercial mixed integer programming (MIP) tool CPLEX in a coarse-grained manner: the evolutionary part is used to quickly obtain a good but suboptimal solution and this intermediate solution is refined using CPLEX. Experimental results are presented on a large real-world case involving more than 1 million variables and 2 million constraints. On this particular problem instance, results are surprisingly good in the early part of the search where the evolutionary algorithm reaches excellent, although suboptimal, solutions much faster than CPLEX alone. Over the whole search, although the hybridized version is less efficient on average, it does better and faster in a non negligible minority of cases.