2005/10/31 by Marc Schoenauer, Schoenauer, Marc, Yann Semet +1
Computer Science · Decision Sciences · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Railway Engineering and Dynamics #Railway Systems and Energy Efficiency #Scheduling and Timetabling Solutions #cs.AI
paper · pdf · doi:10.48550/arxiv.cs/0510091
arxiv created 2005/10/31 · openalex publication_date 2005/10/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 the other following the permutation. This algorithm can be hybridised with ILOG commercial MIP programming 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 one million variables and 2 million constraints. Results are surprisingly good as the evolutionary algorithm, alone or hybridised, produces excellent solutions much faster than CPLEX alone.