Periodic train timetabling with mesoscopic tracks assignment
Ordonnancement de sillons ferroviaires périodiques avec affectation de voies à l’échelle mésoscopique
Résumé
The Infrastructure Manager SNCF Réseau produces train timetables on a yearly basis, to allow trains circulation fulfilling a mobility demand from the Transport Organisation Authority : this is a periodic slot scheduling task. This PhD project aims at providing a decision-aid tool to the timetable planners. We focus on a capacity structuration phase: we look for a periodic scheduling fulfilling a slots demand and satisfying the safety constraints arising from rail operations. We propose two methods to solve this problem. The first method is based on an Integer Linear Programming model inspired from the literature and that we decomposed to ease the solution search. The timetable determination is then made before the tracks assignment. A conflict evaluation function that does not require explicit tracks assignment knowledge is used to obtain conflict-free timetables for which a tracks assignment is reachable. We solve the conflicts of challenging instances with a constructive heuristic and a tabu search. The second method relies on a Constraint Programming model that we use to optimize the turnover time of rolling stock at terminus stations. We conceive filtering algorithms to improve algorithms that maintain the arc-consistency of precedence and disjunctive constraints of the problem, all having a periodic aspect. We propose lower bounds based on the cost contribution of slots subsets to the objective function in order to improve the optimality proof. Finally, we present branching strategies and a Branch-and-Check procedure to improve the resolution performance. We test these approaches on fictive instances of the problem and on the Savoie area around Chambéry.
Le Gestionnaire d’Infrastructure SNCF Réseau produit annuellement un ordonnancement de sillons pour permettre la circulation de trains répondant à une demande des Autorités Organisatrices de Transports. Cette thèse s’inscrit dans une démarche d’aide à la décision pour les chargés d’études horaires produisant ces sillons. Nous traitons une phase de structuration : il s’agit de trouver, s’il existe, un ordonnancement périodique répondant à une demande de sillons et respectant les contraintes de circulation. Nous proposons deux méthodes pour résoudre ce problème. La première méthode se base sur un modèle en Programmation Linéaire en Nombres Entiers inspiré de la littérature et décomposé pour faciliter sa résolution. La grille horaire est décidée, suivie de l’affectation de voies. Une fonction d’évaluation de conflits entre sillons sans connaître l’affectation de voies permet de construire une grille horaire garantissant une affectation de voies compatibles. Nous résolvons les conflits des instances difficiles avec une heuristique constructive et une recherche tabou. La deuxième méthode s’appuie sur un modèle en Programmation Par Contraintes optimisant le temps de retournement des rames en gares terminus. Nous concevons des algorithmes de filtrage améliorant la propagation des contraintes périodiques de précédence et disjonctives. Nous proposons des bornes inférieures basées sur la contribution de sous-ensembles de sillons à la fonction objectif pour améliorer la preuve d’optimalité. Nous présentons une procédure de Branch-and-Check accélérant la résolution. Nous testons ces approches sur des instances fictives du problème et sur l’Étoile de Savoie autour de Chambéry.
Mots clés
Scheduling
Timetabling
Tracks assignement
Exact methods
Tabu search heuristic
Periodic train timetabling
Mesoscopic tracks assignment
Integer linear programming
Constraint programming
Branch-and-Check procedure
Mathematical optimization
Combinatorial optimization
Metaheuristics
Planning
Rail safety
Operations research
Decision making
| Origine | Version validée par le jury (STAR) |
|---|