An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling
<|reference_start|>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 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.<|reference_end|>
@article{schoenauer2005an,
    title={An efficient memetic, permutation-based evolutionary algorithm for
  real-world train timetabling},
    author={Marc Schoenauer (INRIA Futurs), Yann Semet (INRIA Futurs)},
    journal={arXiv preprint arXiv:cs/0510091},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0510091},
    primaryClass={cs.AI}
}