Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

A partir de la définition d'un paradigme espaces - processus énonçant que tout système peut se définir comme une combinaison espaces - processus, les espaces contenant toutes les conditions et moyens nécessaires à l'achèvement du processus, le travail proposé définit une approche modélisatrice permettant de conserver une démarche purement systémique depuis l'identification des concepts du système jusqu'au modèle de représentation. Ce paradigme exprimant simplement qu'un système peut être vu à travers le comportement des différentes propriétés des entités intervenantes, le mémoire va proposer une représentation unifiée de la propriété permettant la manipulation conceptuelle et sémantique. Une forme de représentation des comportements des propriétés sera ensuite proposée. Cette représentation sera définie à partir de l'expression d'un comportement sous forme d'expressions rationnelles; ces expressions étant elles-mêmes des suites de symboles représentatives des propriétés du système observé. Le mémoire montrera comment la forme de représentation proposée permet de retranscrire et d'exploiter simplement les comportements observés ou observables. Le mémoire montrera comment manipuler ces éléments et quelles propriétés s'en dégagent. En particulier, le premier objectif de ce travail est une application à la maîtrise des risques systèmes, on exploitera donc le modèle dans la recherche et l'identification de situations dangereuses mais aussi pour la capacité d'évaluation des critères d'occurrence par un transfert de l'espace de propriétés vers un espace de probabilités.

La mesure de l'apport de l'intermodalité aéro-ferroviaire à grande vitesse au rayonnement métropolitain est au cœur de la problématique sur les relations entre les réseaux et les territoires. Dans le contexte de la construction des espaces de coopérations métropolitaines basées sur des réseaux de villes et une organisation polycentrique, le raisonnement n'est-il pas modifié vers l'inscription de l'espace métropolitain dans sa globalité au cœur d'un système de transport intégré ? L'hypothèse générale s'inscrit dans l'aphorisme suivante les grandes vitesses créent la métropole mais également les espaces métropolitains. La thèse introduit l'idée que pour rendre compte de l'ouverture des espaces métropolitains, un raisonnement multi-échelles et multimodal est nécessaire pour interroger le système de transport intégré des grandes vitesses et insérer une logique intermodale. L'intermodalité aéro-ferroviaire à grande vitesse analysée dans une gamme de configurations à travers la mobilisation d'indicateurs d'accessibilité horaire montre une diffusion des possibilités d'ouverture métropolitaine. Elle propose une nouvelle représentation des liens entre grandes vitesses et territoires remettant en cause les mesures du rayonnement des villes basé sur la possession d'une infrastructure aéroportuaire et le potentiel d'échanges des villes à partir de cette seule infrastructure.

En 2002, la régionalisation de l'action publique a franchi une étape importante avec le transfert aux Régions, à l'issue d'une expérimentation de cinq ans, d'une nouvelle compétence en matière de transports collectifs. Ce travail de doctorat tente de comprendre de quoi dépendent les usages régionaux de cette compétence et ce que ces usages traduisent en termes de recompositions de l'action publique. Reposant sur une analyse comparée de quatre régions (Alsace, Centre, Languedoc-Roussillon et Midi-Pyrénées), il s'attache à saisir l'action publique " au concret " à partir d'une combinaison d'approches empiriques et théoriques. Alors que l'étude des politiques de transport a été abandonnée depuis longtemps à d'autres disciplines (géographie et économie, notamment), la mobilisation d'une approche de science politique permet d'éclairer cet objet sous un jour nouveau. Le transport ferroviaire représente l'archétype même du secteur avec ses élites, son expertise et ses normes. Il constitue également un domaine où les réalisations ont une forte dimension spatiale, matérielle et technique. Ces spécificités impriment leur marque aux politiques régionales et soulèvent des questions concernant les rapports entre secteur et territoires, ainsi qu'entre technique et politique. En même temps, l'étude de la régionalisation des transports collectifs apporte des éléments substantiels à l'analyse de la Région et du pouvoir à cette échelle. Elle permet de dégager des pistes pour une approche renouvelée des politiques régionales.

L'intégration récente des systèmes de communication numériques embarqués à bord des trains pour la gestion du trafic introduit de nouveaux problèmes de compatibilité électromagnétique dans le milieu ferroviaire, notamment, pour le système GSM-R « Global System for Mobile Communications - Railway» sur lequel se focalisent les travaux de la thèse. Ce système est un système numérique élaboré employant des protocoles de communication qui lui permettent de résister à certaines perturbations électromagnétiques. Ainsi, son immunité électromagnétique ne peut pas être étudiée selon les méthodes traditionnelles standardisées, puisqu'elles sont adaptées principalement à des systèmes analogiques. La thèse consiste à caractériser l'environnement EM ferroviaire d'une manière adaptée au contexte du système GSM-R. En effet, il faut préalablement connaitre les perturbations EM qu'il peut rencontrer à bord d'un train. Ainsi, nous avons exploité les méthodes fréquentielle et temporelle pour caractériser les perturbations EM que peut subir son signal utile sous des conditions normales d'opération. Les résultats obtenus ont montré que les perturbations EM transitoires qui apparaissent lors d'un mauvais contact entre la caténaire et le pantographe sont la source principale de perturbations EM pour le système GSM-R. Ainsi, nous avons étudié minutieusement leurs caractéristiques temporelles et d'amplitude à travers une étude statistique de chaque paramètre. Suite aux résultats obtenus, nous avons pu générer des signaux de test représentatifs de ce que peut voir le système GSM-R à bord d'un train avant d'exploiter ces signaux pour l'étude de l'immunité EM de ce système en laboratoire. Thèse encadrée à l'INRETS par DENIAU,V

En raison de problèmes opérationnels et d'autres événements inattendus, un grand nombre d'incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d'entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d'incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d'Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d'envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d'analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d'algorithmes itératifs avec l'objectif d'améliorer progressivement la solution quand le temps d'exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d'un incident font qu'il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d'évaluer la probabilité qu'un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l'optimum pour les instances de petite taille et moyenne alors qu'une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d'autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge

En raison de problèmes opérationnels et d’autres événements inattendus, un grand nombre d’incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d’incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d’envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d’analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d’algorithmes itératifs avec l’objectif d’améliorer progressivement la solution quand le temps d’exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d’un incident font qu’il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d’évaluer la probabilité qu’un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l’optimum pour les instances de petite taille et moyenne alors qu’une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d’autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge / For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact; but, in some cases, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect, e.g., the total delay. This Thesis has been developed in the context of the MAGES project that builds mathematical models and algorithms for optimizing railway operations. Two complementary formulations are proposed to model this problem: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Because of the impossibility of solving real-world instances by using standard solvers, we propose several solutions methods: right-shift rescheduling; a MIP-based local search method; Statistical Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some methods are presented in different versions by extending them to iterative approaches. Among them; SAPI is one of the major contributions of this Thesis. It integrates the concepts of right-shift rescheduling and the MIP-based local search method by fixing integer variables and adding linear inequalities (cuts). SAPI assumes that the effects of disruptions can be propagated to other upcoming events. Nevertheless, this propagation is not uniform to all events and could be forecasted by a statistical analysis. Different versions of the methods are compared in two different networks located in France and Chile. From the results, it is possible to conclude that SAPI finds good solutions faster than the other methods, while a cooperative CP/MIP approach that takes advantage of both formulations seems to be appropriate for large instances. Because of the difficulty to compare SAPI to other methods presented in the literature due to lack of public benchmarks, we applied it to another problem where public instances are available. Hence, the methodology was adapted and applied to the problem of rescheduling passengers, flights, and aircraft under disrupted operations in the context of the ROADEF challenge 2009. SAPI took the third position on this competition, showing that the method seems to be effective solving such type of problems efficiently

Cette thèse est consacrée à la planification robuste du matériel roulant ferroviaire dans un contexte de transport de voyageurs régional. Il s'agit de déterminer pour chaque engin une suite de trajets à réaliser sur une période donnée de façon à résister au mieux aux aléas pouvant apparaître en opérationnel. Dans ce but, nous proposons une définition et une caractérisation de la robustesse par des indicateurs propres au contexte d'étude. Nous abordons le problème par une approche structurelle différente des approches robustes classiques qui permet d'agir sur la structure d'une solution en fonction des indicateurs définis. Trois méthodes sont alors mises en œuvre dans le cadre de ce travail. Une résolution approchée par une heuristique gloutonne et une recherche locale permet d'obtenir des solutions rapidement. Une méthode de résolution approchée par génération de colonnes a été développée afin de prendre en compte plus de contraintes de façon intégrée. Une méthode basée sur un programme linéaire en nombres entiers résolu exactement traite un problème plus général. Afin de limiter le coût de la robustesse, ces méthodes sont basées sur un existant à SNCF répondant au problème de planification des ressources matérielles à coûts de production minimaux. Un outil de simulation du comportement des solutions en situation perturbée permet de comparer les solutions entre elles par évaluation des indicateurs de robustesse. Des expérimentations sur des instances réelles ont prouvé la pertinence des approches et ont mené à l'industrialisation d'un prototype. / This thesis deals with robust rolling-stock planning problems for passenger regional trains. It consists in building robust rolling-stock schedules to operate trains under technical constraints while anticipating operational disturbances that can occur. First of all, we define indicators to characterize robustness in context. We use these indicators to have an effect on solutions that we build. This structural approach is unusual compared to classical robust optimization approaches. We have implemented three methods to solve the problem. A sequential heuristic method enhanced by a local search gives solutions quickly. A column-generation method calculates approximate solutions.An integer linear program is solved exactly to obtain solutions to a global problem. These methods are based on an existing tool at SNCF that optimizes the rolling-stock planning problem to assure optimal production costs. A simulation tool evaluates robustness indicators to compare solutions. Tests on real instances have proved the relevance of the approaches and have lead to the use of a prototype in production

Cette 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 algorithmes / 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 operational problem 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 algorithms