Modeling and solving the robust train timetabling problem in a Mass Transit context

La concentration de l'activité économique autour des grandes villes y entraîne une augmentation régulière de la demande en transport. Afin de répondre à cette demande, les entreprises de transports en commun tentent de proposer une offre adéquate, mais celles-ci sont contraintes par la saturation progressive des infrastructures. Dans le cas du transport ferroviaire, l'accroissement du nombre de voyageurs et de trains en circulation a pour conséquence une augmentation du nombre de perturbations au cours de l'exploitation, ainsi que de leur tendance à se propager et à s'amplifier. Il en résulte une qualité de service dégradée pour les usagers et des pénalités financières pour les opérateurs. Deux leviers peuvent être actionnés pour atténuer les conséquences de ces perturbations : l'application de mesures de régulation pendant la phase opérationnelle, et la construction en amont de plans de transport robustes face aux petits aléas. C'est principalement sur ce dernier point que porte le travail de la thèse. Après avoir présenté le fonctionnement de l'exploitation ferroviaire en zone dense et donné une définition d'un petit aléa, nous passons en revue les différents travaux ayant été menés sur le sujet. La grande majorité des cadres conceptuels proposés pour la conception d'horaires robustes ne sont pas adaptés au cas spécifique de la zone dense, c'est pourquoi nous proposons un nouveau modèle sous la forme d'un problème d'optimisation stochastique. Une approche de résolution est ensuite détaillée, en trois étapes. La première porte sur l'estimation des distributions de probabilité des aléas de l'exploitation, à partir de données de retour d'expérience. Dans un second temps, nous utilisons ces distributions dans un outil de simulation stochastique permettant d'évaluer la performance d'une grille horaire donnée. Enfin, cet outil est utilisé comme fonction d'évaluation au sein d'une heuristique de recuit simulé visant à générer automatiquement des grilles horaires robustes.Due to the greater concentration of economic activities around big cities, transportation facilities are facing an increasing demand. In order to answer it, transport companies seek to provide an adequate offer. However, they are constrained by the progressive saturation of transportation networks. Concerning railway transportation, the increasing numbers of passengers and trains result in a higher number of disturbances occuring during operations, as well as a higher tendency of those to amplify and spread over the network. The final consequence is a lower quality of service for passenger and financial penalties to operating companies. There are two levels of action to prevent these phenomena or limit their reach : taking control actions during operations, and anticipate by building robust transportation plans that will make easier to cope with small random disturbances. The work presented in this thesis focuses mainly on this last point. After presenting railway operations and its specificities in a Mass Transit context and defining what we call ``small disturbances'', we provide a review of existing work on similar topics. Most of conceptual frames designed for robust train timetabling are inadequate when it comes to applying them to the specific case of dense traffic areas. That is why we propose a new model given under the form of a stochastic program. We present then a three-step approach for solving it. In the first step, we use data about operations to estimate the probability distributions of disturbances. In the second one, we use these distributions in a stochastic simulation tool that allows us to compute the performance of a given timetable. Finally, this tool is used as a fitness function in a simheuristic, based on simulated annealing algorithm, that aims at computing automatically some robust train timetables