An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling
| dc.creator | Schoenauer, Marc | |
| dc.creator | Semet, Yann | |
| dc.date | 2005-10-31 | |
| dc.date.accessioned | 2026-07-07T06:46:20Z | |
| dc.date.available | 2026-07-07T06:46:20Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0510091 | |
| dc.identifier | http://arxiv.org/abs/cs/0510091 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103300 | |
| dc.subject | Artificial Intelligence | |
| dc.title | An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling | |
| dc.type | text |