On the Benefits of Inoculation, an Example in Train Scheduling

Yann Semet 1 Marc Schoenauer 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : The local reconstruction of a railway schedule following a small perturbation of the traffic, seeking minimization of the total accumulated delay, is a very difficult and tightly constrained combinatorial problem. Notoriously enough, the railway company's public image degrades proportionally to the amount of daily delays, and the same goes for its profit! This paper describes an inoculation procedure which greatly enhances an evolutionary algorithm for train re-scheduling. The procedure consists in building the initial population around a pre-computed solution based on problem-related information available beforehand. The optimization is performed by adapting times of departure and arrival, as well as allocation of tracks, for each train at each station. This is achieved by a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic scheduler to gradually reconstruct the schedule by inserting trains one after another. Experimental results are presented on various instances of a large real-world case involving around 500 trains and more than 1 million constraints. In terms of competition with commercial math ematical programming tool ILOG CPLEX, it appears that within a large class of instances, excluding trivial instances as well as too difficult ones, and with very few exceptions, a clever initialization turns an encouraging failure into a clear-cut success auguring of substantial financial savings.
Type de document :
Communication dans un congrès
Mike Cattolico et al. GECCO-2006, Jul 2006, Seattle, United States. ACM Press, pp.1761-1768, 2006
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00116345
Contributeur : Marc Schoenauer <>
Soumis le : dimanche 26 novembre 2006 - 12:21:21
Dernière modification le : mercredi 25 avril 2018 - 10:45:27
Document(s) archivé(s) le : mardi 6 avril 2010 - 20:02:02

Fichiers

semetGECCO06.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Yann Semet, Marc Schoenauer. On the Benefits of Inoculation, an Example in Train Scheduling. Mike Cattolico et al. GECCO-2006, Jul 2006, Seattle, United States. ACM Press, pp.1761-1768, 2006. 〈inria-00116345〉

Partager

Métriques

Consultations de la notice

254

Téléchargements de fichiers

755