Constraint modelisation and heuristic for the evaluation of the railway infrastructure
Modélisation par contraintes et heuristiques pour l'évaluation de la capacité d'infrastructures ferroviaires
Résumé
In comparison with others transportation system, the railway transport has many advantages in terms of cost and sustainable development. Nonetheless, transportation is a highly competitive field and the benefits of rail are not sufficient to enable it to prevail. Thus, the SNCF (French National Railway Society) must improve the efficiency of rail transport and the quality of services to clients. Punctuality, train frequency and prices are a central concern. A important work resource on planning is necessary. The problem of assessing the capacity of rail infrastructure sets limits on the network and the impact of modification in the infrastructure. In order to provide solutions to the SNCF, this problem has been modelled in a Constraint Satisfaction Problem. The exact resolution of this problem, with the ILOG SOLVER libraries, shows limits, so improvements are proposed for both the model and the resolution. The improvements focus on reducing the number of constraints, the rewriting of the temporal constraints, suppression of symmetries, cuts and an upper bound. An approached resolution algorithm is proposed, it uses the principles of the meta-heuristics Large and Variables Neighbourhood Search, and the Depth-bounded Discrepancy Search algorithms. The different algorithms and each improvement are validated on a set of random instance and on real data from the railway junction of Pierrefite-Gonesse. The results are the best known
Comparativement aux autres moyens de transport, le transport ferroviaire présente de nombreux avantages tant du point de vue coût que développement durable. Malgré cela, le transport est un domaine fortement concurrentiel et les avantages du ferroviaire ne sont pas suffisant pour lui permettre de s'imposer. Ainsi, la SNCF (Société Nationale des Chemins de fer Français) se doit d'améliorer l'efficacité du transport ferroviaire et la qualité des services aux clients. La ponctualité, la fréquence des trains et le prix sont au centre des préoccupations. Un travail conséquent de planification des ressources est nécessaire. Le problème d'évaluation de la capacité d'infrastructures ferroviaires permet de situer les limites du réseau et d'étudier l'impact de modification d'infrastructure. Afin de proposer des solutions à la SNCF, ce problème a été modélisé en un problème de satisfaction de contraintes. La résolution exacte de ce problème par les bibliothèques d'ILOG SOLVER montre des limites, aussi des améliorations sont proposées tant au niveau du modèle que de la résolution. Les améliorations portent sur la réduction du nombre de contraintes, la réécriture des contraintes temporelles, la suppression de symétries, des coupes et une borne supérieure. Un algorithme de résolution approchée est proposé, il utilise les principes de recherche à voisinage large et variables ainsi que de la recherche à arborescence tronquée. Les différents algorithmes et améliorations sont validés sur des instances réelles provenant du nœud ferroviaire de Pierrefite-Gonesse ainsi que sur un ensemble d'instance aléatoires. Les résultats obtenus sont les meilleurs connus à ce jour.
Origine : Fichiers produits par l'(les) auteur(s)