Skip to Main content Skip to Navigation
Conference papers

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

Marc Schoenauer 1 Yann Semet 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Train timetabling is a difficult and very tightly constrained combinatorial prob lem that deals with the construction of train schedules. We focus on the particu lar problem of local reconstruction of the schedule following a small perturbati on, seeking minimisation of the total accumulated delay by adapting times of dep arture and arrival for each train and allocation of resources (tracks, routing n odes, etc.). We describe a permutation-based evolutionary algorithm that relies on a semi-gre edy heuristic to gradually reconstruct the schedule by inserting trains one afte r the other following the permutation. This algorithm can be hybridised with ILO G commercial MIP programming tool CPLEX in a coarse-grained manner: the evolutio nary part is used to quickly obtain a good but suboptimal solution and this inte rmediate 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000538
Contributor : Marc Schoenauer <>
Submitted on : Monday, October 31, 2005 - 6:30:55 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on: : Friday, April 2, 2010 - 6:12:35 PM

Identifiers

Collections

Citation

Marc Schoenauer, Yann Semet. An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling. Congress of Evolutionary Computation, IEEE, Sep 2005, Edinburgh. ⟨inria-00000538⟩

Share

Metrics

Record views

458

Files downloads

987