Quelques algorithmes de planification ferroviaire sur voie unique

This thesis develops algorithms for rail transportation problems, conducted in relationship with the company Eurotunnel which operates the tunnel under the Channel. This partnership is a scientific chair with the École des Ponts et Chaussées, where this thesis was realized. We study three topics throughout the thesis: the first one is an operationalproblem faced by Eurotunnel, whereas the two other ones are prospective and theoretical problems inspired by their process.The planning process for rail transportation can be divided into several phases (demand estimation, line planning, scheduling of the departure times, rolling stock and crew planning). In a first part, we focus on the scheduling phase on a time interval, applied to the specific case of Eurotunnel. The objective is to compute the departure times of the trains for each of the two stations (Calais in France and Folkestone in England), satisfying operation constraints (security, loading, ...) and commercial agreements with their partners (Eurostar, ...). Moreover, taking into account the delays in the scheduling phase is essential to limit the propagation of the disturbances from train to train in the network. We develop scheduling algorithms for Eurotunnel taking into account the operation and commercial constraints, and the random distributions of the delays for each train. These algorithms use standard tools of Operations Research to model and solve these optimization problems.Pricing is a main issue for transportation companies. Many algorithms have been proposed to help airline companies to define optimized prices of the plane tickets for different classes of passengers. In a second part, we apply some standard pricing frameworks (discrete choice models) in order to optimize in a global way the prices and the departure times of the trains for rail transportation companies. Standard tools of stochastic optimization, discrete choice models, and some heuristics are used in our algorithms to compute the best possible solutions in a limited computation time.We focus in a last part on a class of transportation problems, inspired form Eurotunnel. We give efficient algorithms to solve exactly or to approximate the optimal solutions of these problems. These algorithms give an upper bound of the time complexity of this class of problems. The problems studied consist in scheduling the departure times of shuttles on a fixed trip, to transport passengers, arriving continuously at an initial station, to a given destination. The shuttles are potentially allowed to perform several rotations to transport several groups of passengers. The objective is to minimize the waiting time of the passengers before the depart of their shuttle. Original combinations of convex optimization and graph theory (shortest path problems) are used in our algorithmsCette thèse développe des algorithmes pour des problèmes de transport ferroviaire et est réalisée en partenariat avec l'entreprise Eurotunnel qui exploite le tunnel sous la Manche. Ce partenariat s'est établi sous la forme d'une chaire avec l'École des Ponts où cette thèse a été menée. Nous développons trois sujets dans cette thèse: le premier est un problème opérationnel rencontré par Eurotunnel, les deux autres sont plus prospectifs et théoriques, et sont inspirés des problèmes de transport ferroviaire d'Eurotunnel.Le processus de création de grilles horaires pour le transport ferroviaire se découpe en plusieurs phases (estimation de la demande, détermination du réseau, planification des départs, affectation des trains et du personnel). Nous nous intéressons dans une première partie à la phase de planification des départs des trains sur un intervalle temporel, appliquée au cas spécifique d'Eurotunnel. L'objectif est de calculer les horaires des départs des trains depuis chacune des deux stations (Coquelles en France et Folkestone en Angleterre) en respectant des contraintes d'exploitation (sécurité, chargement, ...) et des accords commerciaux signés avec leurs partenaires (Eurostar, ...). De plus, la prise en compte des retards dès la planification des départs est primordiale pour limiter la propagation des perturbations de train en train sur le réseau. Nous avons développé des algorithmes de planification pour Eurotunnel tenant compte des contraintes du réseau et de la probabilité de retard pour chaque train. Ces algorithmes utilisent des outils standard de la Recherche Opérationnelle pour modéliser et résoudre ces problèmes d'optimisation.La tarification des billets est un enjeu majeur pour les entreprises de transport. Pour les compagnies aériennes, de nombreux algorithmes ont été étudiés pour définir le prix optimal des billets pour différentes classes de passagers. Nous appliquons dans une deuxième partie des méthodes standard de tarification (modèles de choix discrets) afin d'optimiser de manière globale les prix et les horaires des départs pour des entreprises de transport ferroviaire. Des outils classiques de l'optimisation stochastique, des modèles de choix discrets et des heuristiques sont utilisés dans nos algorithmes pour donner les meilleures solutions possibles en un temps de calcul limité.Nous nous intéressons dans une dernière partie à une classe de problèmes de transport, inspirés de ceux rencontrés par Eurotunnel, en donnant des algorithmes efficaces de résolution exacte ou approchée. Ces algorithmes permettent de donner une borne supérieure de la complexité temporelle de ces problèmes. La classe de problèmes étudiés consiste en la planification des départs de navettes sur une ligne fixe, pour transporter d'une station A vers une station B des usagers arrivant de manière continue. Les navettes sont éventuellement autorisées à faire de multiples rotations pour transporter plusieurs vagues d'usagers. L'objectif est de limiter le temps d'attente des passagers avant le départ de leur navette. Des combinaisons originales de l'optimisation convexe et de la théorie des graphes (problèmes de plus court chemin) sont utilisées dans nos algorithme