Tesi sul tema "Problèmes ferroviaires"

Cette thèse s'intéresse à la planification de l'exploitation d'infrastructures ferroviaires à l'échelle d'un nœud ou d'une gare. Pour déterminer une stratégie d'offre, il est important de disposer d'outils d'évaluation de la capacité des infrastructures. Cela permet de situer les limites d'un réseau, et d'étudier l'impact de modifications. Dans ce cadre, la faisabilité d'une grille horaire, son optimisation vis-à-vis de critères comme le nombre de trains (saturation), et l'évaluation de la stabilité sont considérées. Nous proposons une modélisation linéaire multiobjectif de ce problème. Le niveau de détail considéré est suffisamment fin pour obtenir des grilles horaires réalisables dans la pratique sur les infrastructures étudiées. En outre, elle présente deux structures correspondant à des problèmes d'optimisation classiques appelés plus court chemin et set packing. Si le premier est facile à résoudre, le second est connu comme NP-difficile. Nous proposons différents algorithmes de pré-traitements, et de résolution approchée (basée sur la métaheuristique GRASP), pour ce problème. Une première extension de cette heuristique au cas biobjectif est présentée. Les expérimentations numériques, menées sur des instances correspondant au nœud de Pierrefitte-Gonesse, ou générées aléatoirement, montrent l'efficacité de ces algorithmes. L'intégration de ces travaux dans un logiciel dédié aux études de capacité d'infrastructures ferroviaires (projet RECIFE, en collaboration avec la SNCF) est décrite
The subject of this thesis is the planning of railroad infrastructures operation at a node or station scale. In order to determine an offer strategy, it is important to have some evaluation tools of the infrastructures capacity. This allows to evaluate the network limits, and to study the impact of some modifications. The main questions considered are, the feasibility of a timetable, its optimization according to criteria like the number of trains (saturation), and the stability evaluation. We propose a multiobjective linear model of this problem. The precision considered is accurate enough to obtain realizable timetables in practice on the studied infrastructures. Moreover, it presents two structures corresponding to classic optimization problems named shortest path and set packing. If the resolution of the first one is easy, the second one is known as NP-hard. We propose several pre-processing algorithms, and an approximation method based on the GRASP metaheuristic, for this problem. A first extension of this method in biobjective case is presented. The numerical experimentations on several instances, corresponding to Pierrefitte-Gonesse node or randomly generated, show the efficiency of these algorithms. The integration of these works in a complete software dedicated to the evaluation of railroad infrastructures capacity (RECIFE project, in collaboration with the french national railroad society) is described

Cette thèse est dédiée à la conception et à l’application d’algorithmes quantiques pour la résolution de problèmes d’optimisation combinatoire ferroviaires. Aujourd’hui, les problèmes d’optimisation auxquels fait face la SNCF sont complexes, empêchant souvent une résolution à l’optimalité via des méthodes classiques en un temps raisonnable. L’informatique quantique est pressentie pour améliorer la qualité des solutions et diminuer le temps de calcul pour certains de ces problèmes. Actuellement, les algorithmes quantiques pour l’optimisation se divisent en deux classes : les algorithmes exacts et les heuristiques. Les premiers présentent un avantage théorique pour plusieurs problèmes, mais ne sont pas implémentables sur les machines actuelles car trop gourmands en ressources. Les seconds sont implémentables dès aujourd’hui, au moins sur de petites instances, ouvrant la porte aux premières applications, bien qu’ils ne présentent pas encore de garanties de performances ni d'avantage quantique. Dans cette thèse, nous analysons et proposons des algorithmes qui appartiennent à chacune de ces deux classes.D’une part, nous étudions une classe d’heuristiques appelée Algorithmes Variationnels Quantiques. Il s’agit d’algorithmes hybrides quantique-classique, qui alternent entre l’exécution d’un circuit quantique paramétré et l’optimisation classique des paramètres. Ils permettent de résoudre des problèmes non contraints à variables binaires, et nous proposons une méthode générale pour reformuler des problèmes contraints à variables entières sous cette forme. Nous présentons certaines propriétés des Algorithmes Variationnels Quantiques, nécessaires pour envisager des preuves théoriques de garanties de performances. En particulier, nous étudions QAOA (Quantum Approximate Optimization Algorithm) en l'analysant à la lumière des précédentes propriétés et en donnant une décomposition universelle de son circuit quantique pour des problèmes dont la fonction objectif est polynomiale. Avec cet algorithme, nous résolvons un problème de conception de plan de transport de la SNCF. Ce problème a pour but de trouver un plan de transport qui correspond au meilleur compromis économique entre les bénéfices générés par la vente de billets aux voyageurs et les coûts d'exploitation, tout en respectant la disponibilité du réseau ferroviaire. Pour résoudre ce problème avec QAOA, nous proposons deux simplifications correspondant à différentes adaptations du problème métier initial.D’autre part, nous élaborons des algorithmes quantiques-classiques exacts pour deux grandes familles de problèmes combinatoires. La première famille concerne les problèmes d’ordonnancement. L’algorithme proposé s’applique à une large classe de problèmes d’ordonnancement à une machine, NP-difficiles, qui satisfont une propriété de programmation dynamique particulière (Dynamic Programming Across the Subsets). L’algorithme, reprenant l’idée de Ambainis et al. (2019), allie la programmation dynamique classique et l’algorithme quantique de recherche du minimum dans une table (basé sur l’algorithme de Grover). Il permet de réduire la complexité en temps pire-cas, parfois au détriment de l’introduction d’un terme pseudo-polynomial. Nous étendons cet algorithme au problème du flowshop à trois machines, pour lequel une accélération est aussi obtenue. La deuxième famille relève des problèmes d’optimisation robuste où l’ensemble d’incertitude est un polytope. Nous proposons un algorithme qui, partant de l’algorithme classique traitant de ces problèmes, remplace certaines opérations par des routines quantiques afin d’obtenir une accélération. Précisément, nous étudions l'utilisation des deux routines quantiques suivantes : la recherche du minimum dans une table et la résolution d’un système linéaire
This thesis is dedicated to the conception and application of quantum algorithms for railway combinatorial optimization problems. Today, the optimization problems that SNCF faces are complex, often prohibiting finding the optimal solution for industrial instances with classical methods within a reasonable amount of time. Quantum computing is expected to improve the quality of solutions and reduce the computation time for some of these problems. Quantum algorithms for optimization are divided into two classes: exact algorithms and heuristics. The former demonstrate theoretical advantages for several problems but cannot be implemented on current quantum machines because they require too high-quality quantum resources. On the contrary, the latter can be implemented, at least for small instances, but there are no performance guarantees or proven quantum advantages yet. In this thesis, we analyze and propose algorithms that belong to each of these two classes.On the one hand, we study the Variational Quantum Algorithms, which belong to the class of heuristics. These are hybrid quantum-classical algorithms that alternate between a parametrized quantum circuit and a classical optimizer. They allow solving unconstrained problems with binary variables, and we propose a general method to reformulate constrained integer problems into such problems. We highlight some properties of Variational Quantum Algorithms necessary for potential theoretical guarantees. In particular, we study QAOA (Quantum Approximate Optimization Algorithm) in light of the previous properties, and we provide a universal decomposition of the quantum circuit for problems whose objective function is polynomial. We solve with this algorithm a railway timetabling problem of SNCF. It consists of finding the transportation plan maximizing the operating profit according to the customers' demand taking into account the availability and cost of both the network and the rolling stock. To solve it with QAOA, we propose two simplifications with different adaptations of the original problem.On the other hand, we design exact quantum-classical algorithms for two broad families of combinatorial problems. The first family relates to scheduling problems. We propose an algorithm that tackles a large class of NP-hard single-machine scheduling problems, which satisfy a specific dynamic programming property (Dynamic Programming Across the Subsets). Our algorithm, based on the seminal idea of Ambainis et al. (2019), combines classical dynamic programming and quantum search of the minimum in a table (generalization of Grover Search). It reduces the worst-case time complexity, sometimes at the cost of an additional pseudopolynomial factor. We extend this algorithm to the 3-machine flowshop problem, also leading to a reduction of the complexity. The second family concerns robust optimization problems where the uncertainty set is a polytope. We present an algorithm that, relying on the classical method that deals with these problems, replaces some computations with quantum subroutines to achieve a speedup. Specifically, we study the two following quantum subroutines: the search of the minimum in a table and the resolution of a linear system

Dans la réalisation technico-commericiale du transport de fret, la répartition des wagons vides participe fortement aux coûts de production, à la qualité et à la consistance du service offert. Dans un environnement aussi concurrentiel que celui du transport de marchandises, les enjeux pour la SNCF sont multiples. Les objectifs fondamentaux d'une nouvelle application informatique sont de satisfaire des demandes en matériel de la clientèle et d'optimiser la répartition par l'utilisation d'un algorithme de recherche opérationnelle. La principale difficulté de la répartition est d'appréhender un problème de grande taille (environ 85 000 wagons pour 6 000 demandes hebdomadaires) dans un système complexe et rigide, pour informatiser la prise des décisions optimales en temps réel (2 fois par jour) en tenant compte de l'état fictif du réseau sur l'horizon de travail. Il est donc nécessaire d'intégrer les aspects dynamiques, prévisionnels et multiniveaux dans la prise des décisions optimales. L'objectif de ce travail est d'adapter une méthode de décomposition au modèle global de transbordement dynamique. Nous proposons une décomposition temporelle du problème, puis une décomposition par catégorie de matériel et enfin une décomposition spatiale. Dans ce troisième axe de recherche, nous proposons une méthode encore très peu étudiée, de type primale-duale.

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions
In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features

La conception d’un plan de transport d’un service ferroviaire est un processus qui se réalise entre deux ans et six mois avant la mise en service de celui-ci. Les principales phases de la conception sont la définition des dessertes, le calcul de la grille horaire et enfin l’organisation des roulements de rames et des conducteurs. La manière dont le plan de transport est conçu peut avoir de nombreuses conséquences sur la qualité de service : fréquence en gare insuffisante qui peut entrainer une perte de clients, robustesse de la grille horaire face à de petits incidents... En zone dense, tous ces éléments sont à prendre en compte, dès la conception de la grille horaire.Aujourd’hui, SNCF Transilien conçoit ses plans de transport en prenant d’abord en compte l’optimisation des ressources de production (sillons, rames et agents de conduite). Toutefois, l’augmentation des ressources mises en œuvre n’améliore plus l’adéquation du plan de transport à la demande des voyageurs. Ce mode de conception ne permet donc plus de faire face à l’augmentation de la demande de mobilité. C’est pourquoi il faut repenser la conception du plan de transport en intégrant immédiatement la dimension voyageuse.Nos travaux se concentrent sur les problématiques de conception de dessertes et de grille horaire, en prenant en compte le point de vue des voyageurs. Nous présentons un modèle multiobjectif de conception de dessertes, puis nous présentons un modèle de conception de grille horaire intégrant le choix d’itinéraire des voyageurs. Ensuite, nous présentons une méthode cherchant à intégrer ces deux modèles. Enfin, nous présentons une évaluation de nos résultats grâce à des indicateurs de fiabilité
The design of a railway transportation plan is a process achieved between two years and six months before it is put into service. The main phases in the design of a transportation plan are the line planning, the timetabling, the rolling stock and the crew scheduling.The design of the transportation plan can have many consequences on the quality of service: an inadequate frequency in station can cause a loss of passengers, sufficient number of seated places, robustness of the timetable in the face of small incidents... In dense area, as in the Ile-de-France region, all these elements must be taken into account as the transportation plan is designed.Today, SNCF Transilien designs its transportation plans by first taking into account the optimization of production resources (train paths, rolling stock units and drivers). However, today, the increase in resources implemented no longer improves the adequacy of the transportation plan to passengers’ demand. This design method no longer makes it possible to cope with the increase in the demand for mobility (+3% each year since 2000). This is why we must rethink the design of the transport plan by immediately integrating the passenger dimension. Our work focuses on issues of line planning and timetabling in a passenger-oriented approach. First, we present a multi-objective model for line planning. Then, we present a model of timetabling incorporating passenger route choice. Then, we initiate a method to integrate these two models. Finally, we present an evaluation of our results thanks to reliability indicators from the literature and a macroscopic simulation of the timetables

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

La plupart des systèmes ferroviaires subissent une demande croissante de capacité. Pour y faire face, il faut construire de nouvelles infrastructures ou exploiter plus efficacement celles existantes, notamment en définissant des grilles horaires optimisées. Dans la littérature, la plupart des approches de construction des grilles sont basées sur des représentations macroscopiques de l'infrastructure, ce qui peut conduireà des solutions infaisables ou inefficaces. En revanche, les approches microscopiques reposent sur une modélisation réaliste du système ferroviaire, ce qui garantit la faisabilité et l'efficacité des résultats. Néanmoins, en raison de leur complexité, l'utilisation de ces approches est généralement limitée à une seule gare. Malgré l'optimisation de la grille horaire, les travaux de maintenance peuvent avoir un fort impact sur les circulations des trains. En présence de maintenances, il peut donc être nécessaire de redéfinir la grille horaire pour assurer une exploitation efficace de la capacité. Nous présentons deux contributions principales sous forme de deux approches microscopiques : une pour la conception de grilles horaires et l'autre pour leur redéfinition en cas de maintenance. La deuxième est la première approche microscopique qui apparaît dans la littérature pour aborder ce problème tout en considérant des aspects comme les limitations temporaires de vitesse. Nous démontrons la validité de nos approches et leur applicabilité dans des scénarios réels. De plus, nous montrons que les approches microscopiques peuvent être utilisées pour traiter des zones de l'infrastructure contenant plusieurs gares
Most railway systems experience a growing demand of railway capacity. To face this demand, either new infrastructure must be built or a more efficient exploitation of the existing one must be attained. Timetables play a determinant role in the efficient capacity exploitation. Most timetabling approaches in the literature are based on macroscopic representations of the infrastructure. This may lead to inefficient and in some cases, impractical solutions. Instead, microscopic approaches are based on more realistic modelling of the elements of the railway system. This guarantees the feasibility of the timetables while promoting an efficient capacity exploitation. However, due to their complexity, the scope of microscopic approaches is typically restricted to main stations. Despite the optimization of timetables, the performance of infrastructure maintenance may severely impact the trains' circulations in the network. Therefore, the timetable may have to be rearranged to ensure an efficient capacity exploitation. We present two main contributions in this thesis: first, a microscopic approach for timetable design. Second, a microscopic approach for timetable rearrangement to cope with maintenance. This is the first microscopic approach in the literature to tackle this problem while also considering specific aspects as temporary speed limitations. After a thorough experimental analysis, we demonstrate the validity of our approaches and their practical applicability in real life scenarios. In particular, we show that microscopic approaches can be used to tackle large areas of the infrastructure, including several stations

La propagation acoustique en milieu extérieur fait intervenir des phénomènes physiques complexes, liés essentiellement aux variations de température et de vent dans la couche limite atmosphérique et aux frontières du domaine (effet de l'impédance du sol, de la topographie, ...). De plus, dans le contexte des trains à grande vitesse (TGV), les sources de bruit sont étendues, en mouvement 'a une vitesse relativement élevée, et de nature diverse (bruit de roulement, bruit d'origine aérodynamique, ...). Ce travail de thèse a pour but de modéliser la propagation du bruit des TGV en milieu atmosphérique, et de comprendre les phénomènes physiques associés à ce type de propagation. La première partie de ce travail s'intéresse à l'effet de diffusion des fluctuations turbulentes de température et de vent sur les ondes acoustiques en présence d'une zone d'ombre acoustique. L'effet de diffusion d'une taille de structure turbulente donnée dépend de la fréquence acoustique et de la géométrie de propagation. Ce couplage entre échelles de turbulence, fréquence acoustique et géométrie est étudié à l'aide d'outils de la théorie de la propagation des ondes en milieu aléatoire et de simulations d'équation parabolique, afin d'estimer les plus petites et les plus grandes tailles de structure turbulente à prendre en compte dans une configuration donnée. Dans une deuxième partie, une méthode de résolution des équations d'Euler linéarisées par différences finies dans le domaine temporel est décrite. L'utilisation de schémas numériques optimisés permet d'appliquer ce modèle de propagation à des configurations de propagation acoustique longue distance. Une des principales difficultés rencontrées avec les modèles temporels de propagation est la prise en compte de la réflexion des acoustiques sur un sol d'impédance finie. Des conditions limites d'impédance performantes d'un point de vue numérique sont proposées pour des modèles d'impédance couramment employés dans les études de propagation en milieu extérieur. Ces conditions limites sont obtenues en approchant l'impédance par des fonctions-type particulières, ce qui permet d'utiliser la méthode de convolution récursive. Elles sont validées dans des configurations de propagation bi- et tridimensionnelle, en considérant une atmosphère homogène puis une atmosphère stratifiée. Enfin, les applications spécifiques au bruit des TGV sont présentées dans une troisième partie. Dans un premier temps, un modèle de propagation du bruit des TGV basé sur une décomposition du train en un ensemble de sources ponctuelles équivalentes est décrit. Les résultats de ce modèle sont comparés à des mesures réalisées à différentes distances de la voie de circulation en supposant les conditions de propagation homogènes. Le modèle de sources équivalentes est également couplé à un code d'équation parabolique afin de prendre en compte l'effet d'un profil vertical de température ou de vent. Dans un deuxième temps, les phases d'approche et d''éloignement de passages de TGV sont analysées afin de caractériser un phénomène de "grondement". Dans certaines circonstances, il est en effet possible d'entendre un bruit similaire à un passage d'avion une dizaine de secondes avant ou après un passage de TGV, bruit qualifié de "grondement". L'analyse s'appuie principalement sur des résultats expérimentaux, qui permettent de déterminer les caractéristiques du "grondement" et les circonstances dans lesquelles il se produit. Cette étude est complétée par des simulations d'équation parabolique qui montrent l'importance du vent dans l'apparition de ce phénomène.

La propagation acoustique en milieu extérieur fait intervenir des phénomènes physiques complexes, liés essentiellement aux variations de température et de vent dans la couche limite atmosphérique et aux frontières du domaine (effet de l’impédance du sol, de la topographie,. . . ). De plus, dans le contexte des trains `a grande vitesse (TGV), les sources de bruit sont étendues, en mouvement `a une vitesse relativement élevée, et de nature diverse (bruit de roulement, bruit d’origine aérodynamique,. . . ). Ce travail de thèse a pour but de modéliser la propagation du bruit des TGV en milieu atmosphérique, et de comprendre les phénomènes physiques associés `a ce type de propagation. La première partie de ce travail s’intéresse à l’effet de diffusion des fluctuations turbulentes de température et de vent sur les ondes acoustiques en présence d’une zone d’ombre acoustique. L’effet de diffusion d’une taille de structure turbulente donnée dépend de la fréquence acoustique et de la géométrie de propagation. Ce couplage entre échelles de turbulence, fréquence acoustique et géométrie est étudié `a l’aide d’outils de la théorie de la propagation des ondes en milieu aléatoire et de simulations d’´equation parabolique, afin d’estimer les plus petites et les plus grandes tailles de structure turbulente à prendre en compte dans une configuration donnée. Dans une deuxième partie, une méthode de résolution des équations d’Euler linéarisées par différences finies dans le domaine temporel est décrite. L’utilisation de schémas numériques optimisés permet d’appliquer ce modèle de propagation `a des configurations de propagation acoustique longue distance. Une des principales difficultés rencontrées avec les modèles temporels de propagation est la prise en compte de la réflexion des acoustiques sur un sol d’impédance finie. Des conditions limites d’impédance performantes d’un point de vue numérique sont proposées pour des modèles d’impédance couramment employés dans les études de propagation en milieu extérieur. Ces conditions limites sont obtenues en approchant l’impédance par des fonctions-type particulières, ce qui permet d’utiliser la méthode de convolution récursive. Elles sont validées dans des configurations de propagation bi- et tridimensionnelle, en considérant une atmosphère homogène puis une atmosphère stratifiée. Enfin, les applications spécifiques au bruit des TGV sont présentées dans une troisième partie. Dans un premier temps, un modèle de propagation du bruit des TGV basée sur une décomposition du train en un ensemble de sources ponctuelles équivalentes est d´écrit. Les résultats de ce modèle sont comparés à des mesures réalisées à différentes distances de la voie de circulation en supposant les conditions de propagation homogènes. Le modèle de sources équivalentes est également couplé à un code d’´equation parabolique afin de prendre en compte l’effet d’un profil vertical de température ou de vent. Dans un deuxième temps, les phases d’approche et d’´eloignement de passages de TGV sont analysées afin de caractériser un phénomène de “grondement”. Dans certaines circonstances, il est en effet possible d’entendre un bruit similaire à un passage d’avion une dizaine de secondes avant ou après un passage de TGV, bruit qualifié de “grondement”. L’analyse s’appuie principalement sur des résultats expérimentaux, qui permettent de déterminer les caractéristiques du “grondement” et les circonstances dans lesquelles il se produit. Cette étude est complétée par des simulations d’´equation parabolique qui montrent l’importance du vent dans l’apparition de ce phénomène
Outdoor sound propagation involves complex physical phenomena, mainly associated with temperature and wind variations in the atmospheric boundary layer and with boundary conditions (influence of the ground impedance, terrain effects,. . . ). Furthermore, in the context of high speed trains (TGV), noise sources are in motion at a relatively high speed, cannot be considered as compact, and are of different types (rolling noise, aerodynamic noise,. . . ). This work aims at modeling TGV noise propagation outdoors and at understanding the physical phenomena associated with this type of propagation. In a first part, acoustic scattering by turbulent fluctuations of temperature and wind is considered in the presence of a refractive shadow zone. The scattering effect of a given turbulence scale depends on acoustic frequency and propagation geometry. This coupling between turbulent structures, acoustic frequency and geometry is studied using tools from the theory of wave propagation in random media and parabolic equation simulations, in order to estimate the smallest and largest turbulence scales to be taken into account in a given configuration. In a second part, a solver of the linearized Euler equations is described which uses finite-difference time-domain methods. The use of optimized numerical schemes enables to apply this propagation model to long range sound propagation configurations. One of the main difficulties encountered with timedomain propagation models is to take into account the reflection of acoustic waves by an impedance ground. Time-domain impedance boundary conditions that are efficient from a numerical point of view are proposed for impedance models commonly used in outdoor sound propagation studies. To obtain these boundary conditions, the impedance is approximated by well chosen template functions, which enables the use of the recursive convolution method. They are validated in two- and three-dimensional propagation geometries, considering a homogeneous atmosphere and then a stratified atmosphere. Finally, specific applications to TGV noise are presented in a third part. First, a TGV noise propagation model is described where the train is represented by a set of equivalent point sources. Model results are compared to measurements performed at different distances from the track assuming homogeneous propagation conditions. The equivalent sources model is also coupled to a parabolic equation code in order to take into account the influence of a vertical profile of temperature or wind. Second, the characteristics of a “rumbling” noise that can be heard tens of second before or after some TGV pass-bys are analyzed. In some circumstances, it is indeed possible to hear a relatively low-frequency noise perceived as an aircraft pass-by, which is referred to as “rumbling” noise. The analysis is mainly based on experimental results and enables to determine the characteristics of this “rumbling” noise and the circumstances in which it occurs. Parabolic equation simulations are also performed to show the importance of the wind in the appearance of this phenomenon

La première partie de ce travail concerne la production cyclique pour l'optimisation du taux de production dans les flowshops robotisés, où un robot est chargé du transport des pièces. Les cellules robotisées peuvent être disposées de façon linéaire ou circulaire. Les principaux résultats théoriques concernant la disposition linéaire ne peuvent être étendus à la configuration circulaire. En particulier, trouver le meilleur cycle de production de une pièce (1-cycle) est un problème polynomial dans le cas des cellules linéaires additives, mais NP-difficile pour la configuration correspondante circulaire.Nous nous concentrons principalement sur le cas des cellules circulaires équilibrées, où le temps d'usinage est identique sur toutes les machines. Après avoir présentés des outils pour l'analyse cyclique dans les cellules circulaires, nous établissons des propriétés nécessaires des 1-cycles performants, ce qui permet de conclure sur le problème du meilleur 1-cycle jusqu'à 8 machines. Toutefois, nous fournissons un contre-exemple pour 6 machines à la conjecture classique des 1-cycles, toujours ouverte dans cette configuration.Ensuite, nous étudions la structure des 1-cycles performants pour des cellules circulaires équilibrées arbitrairement grandes. Nous définissons et étudions les propriétés d'une nouvelle famille de cycles basée sur cette structure et formulons une conjecture sur sa dominance sur les 1-cycles qui conduirait à un algorithme polynomial pour le problème du meilleur 1-cycle dans ce cas. Cette structure permet de déterminer le meilleur 1-cycle jusqu'à 11 machines.Dans la deuxième partie, nous présentons le travail réalisé sur un problème industriel proposé par la SNCF dans le cadre du challenge ROADEF/EURO. Nous proposons un algorithme glouton pour ce problème combinant divers aspects de la gestion des trains au sein d'une gare
The first part of this work deals with cyclic production for throughput optimization in robotic flow-shops, where a robot is in charge of the material handling of parts. Robotic cells may have a linear or a circular layout. Most theoretical results for the linear layout do not hold for the circular layout. In particular, the problem of finding the best one part production cycle (1-cycle), which is a polynomial problem for linear additive cells, has been proved NP-hard for the corresponding circular configuration.We mainly focus on a special case of circular balanced cells, where the processing times are identical for all machines. After presenting tools for cyclic analysis in circular cells, we study necessary properties of efficient 1-cycles. These results allow to conclude on the best one part production cycle for any parameters in circular balanced cells up to 8 machines. However, we provide a counter-example to the classical 1-cycle conjecture, still open for this configuration.Then, we study the structure of efficient one part production cycles in arbitrarily large circular balanced cells. We introduce and study a new family of cycles based on this structure, and formulate a conjecture on its dominance over one part-production cycles, which would lead to a polynomial algorithm for finding the best 1-cycle for circular balanced cells. This structure allows to settle the best one part production cycle for cells with up to 11 machines.In a second part, we present work on an industrial problem of railway stock scheduling proposed by the French railway company in the context of the ROADEF/EURO competition. We propose a greedy algorithm for this problem combining the various aspects of trains handling inside a station

Etude du fonctionnement d'un entrainement multimachine a convertisseur unique, a courant, flux ou couple constant. Etude de sensibilite des principales variables pour les 2 modes de montage des machines (serie ou parallele). Simulation numerique et elaboration d'une methode graphique d'analyse des regimes transitoires

Les programmes de couverture en nombres entiers (CIP) modélisent de nombreux problèmes industriels réels. Dans le cadre de cette thèse, nous nous intéressons aux CIP de grande taille, programmes qui apparaissent souvent comme problèmes maîtres issus d’une décomposition de type Dantzig-Wolfe. Les approches de résolution de problèmes de grande taille, et plus spécifiquement, la méthode de génération de colonnes, connaissent un intérêt grandissant depuis plusieurs années. Nous présentons dans un premier temps un tour d’horizon autour de la méthode de génération de colonnes, et des approches de résolution entière (exactes ou approchées) basées sur cette méthode. Nous étudions ensuite les heuristiques d’approximation dédiées aux CIP, puis nous proposons une adaptation de l’heuristique gloutonne de Dobson aux CIP de grande taille, engendrant la résolution d’un sous-problème fractionnaire. Nous revisitons à l’issue de cette étude la preuve du rapport d’approximation de l’heuristique de Dobson à l’aide d’une reformulation originale permettant d’étendre cette preuve à de nouvelles variantes. A l’issue des deux études précédentes, nous proposons de nouvelles approches de résolution approchée pour les CIP de grande taille qui font coopérer l’heuristique d’approximation gloutonne et la méthode de génération de colonnes. Des coopérations séquentielles et hybrides sont alors mises en oeuvre et évaluées sur des instances de problèmes réels. Les résultats obtenus montrent que l’heuristique gloutonne constitue un générateur efficace de colonnes et de solutions diversifiées permettant d’améliorer différents aspects du schéma de génération de colonnes : d’une part, en diminuant le nombre d’itérations ainsi que le temps de résolution, et d’autre part, en améliorant la valeur du majorant (les CIP étant des problèmes de minimisation) dans un schéma de résolution en nombres entiers. La validation expérimentale de l’ensemble des approches proposées est finalement réalisée sur deux applications types issues des domaines du transport ferroviaire et de la production agricole
Large-size Covering Integer Programs (CIP) model many real-case applications. They appear typically as master problems resulting from a Dantzig-Wolfe decomposition. The well-known column generation approach is widely used for solving such large-size problems. In this thesis, it is combined in a hybrid way with the best-known approximation heuristic for CIP : the greedy heuristic of Dobson that is extended, through the resolution of fractional subproblems, to large-size CIP. The propsed hybridization scheme takes advantage of the distinct criteria of columns selection used by the two methods. It is evaluated on two transportation and production planning applications. Numerical results on real-case instances show that the hybrid scheme improves the convergence of column generation both in terms of number of iterations and computational time. The integer solutions derived from the column generation scheme are also significantly improved, highlighting the diversification potential of the approximation heuristic. On an other hand, an original reformulation of CIP as Set Covering Problems is proposed as an alternative demonstration of the logarithmic approximation ratio allowing it’s extention to new variants of CIP as the Fixed Charge Covering Integer Programs

Le bruit de roulement est la principale source de bruit des transports ferroviaires, pour un large intervalle de vitesses. Pour prédire le bruit de roulement, la SNCF utilise un outil de simulation, basé une approche fréquentielle. Bien que très efficace dans les cas de voies ballastées standard, en ligne droite et à vitesse constante, cette approche est limitée aux roues et aux rails sans défaut important. Une approche temporelle a donc été envisagée pour étendre la modélisation du bruit de roulement à celle du bruit d'impact dû aux irrégularités discrètes sur l'une et/ou l'autre des deux structures, telles que des joints sur le rail ou des méplats sur la roue. L'objectif principal de la thèse est donc de construire un outil de simulation, dans le domaine temporel, de l'interaction verticale entre la roue et le rail, pour la prédiction du bruit de roulement. Les données d'entrée du modèle d'interaction, le modèle de contact roue/rail et le modèle vibratoire de la roue ont d'abord été formulés. Les données d'entrée du modèle consistent à définir un déplacement vertical relatif entre la roue et le rail, appelé rugosité relative, à partir de données spatiales de rugosité. Le modèle de contact, non linéaire et autorisant des pertes de contact, est basé sur la théorie de Hertz. Un modèle masse-ressort-amortisseur est suffisant pour représenter le déplacement vertical de la roue, dans le contexte de la simulation des vibrations engendrées dans le rail dans la même direction. La seconde étape de l'outil de simulation est d'élaborer un modèle de voie ferrée, permettant de simuler une structure infinie à partir d'une représentation numérique finie, indispensable pour l'approche temporelle. Le rail est modélisé par une poutre de longueur finie, supportée périodiquement par des systèmes masse-ressort-amortisseur (décrivant le système des supports semelle-traverseballast). Les conditions aux limites de la poutre permettent d'absorber les réflexions des ondes aux bords de celle-ci. Des conditions aux limites absorbantes numériques ont donc été formulées. Le second objectif de cette thèse est de caractériser expérimentalement le bruit de roulement et le bruit d'impact, dans les cas de défauts importants sur la roue et/ou le rail. Un essai en situation réelle a donc été réalisé. Deux sites de mesures ont été installés ; le premier sur une zone équipée de Longs Rails Soudés (LRS) et le second sur une zone avec un joint de rail (JR). De plus, certains essieux du train d'essai ont été spécialement sélectionnés pour les défauts de surface sur les roues. Des mesures de caractérisation telles que la rugosité de surface des roues et du rail mais aussi les accélérances de la voie ont été réalisées. Les niveaux vibratoires du rail et des traverses ainsi que le bruit au passage du train d'essai ont été mesurés. L'utilité de ces mesures est double. D'une part, elles permettent de réaliser une caractérisation expérimentale du comportement acoustique et vibratoire du système roue/rail, dans différentes situations. Ces conclusions aboutissent à un cahier des charges pour l'élaboration d'un outil expérimental de détection de défauts de roue, à partir de mesures acoustique et vibratoire en bord de voie. La seconde utilité de ces mesures est de pouvoir à la fois alimenter le modèle temporel d'interaction roue/rail, développé pendant la thèse, et de quantifier ses performances. Le problème d'interaction roue / rail complet est résolu par la méthode des différences finies. L'évaluation des performances de ce modèle a été menée grâce à différentes comparaisons. L'efficacité des conditions aux limites absorbantes a d'abord été estimée. Une comparaison entre les résultats de simulation et ceux des mesures a ensuite été effectuée. Dans un premier temps, la capacité du modèle temporel à reproduire les caractéristiques dynamiques de la voie a été évaluée. Dans un second temps, la simulation des différentes situations mesurées pendant la campagne de mesure est réalisée. La comparaison entre les niveaux vibratoires simulés et mesurés au passage des roues avec différents états de surface est discutée.

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

L’objectif de ce travail est l'étude de la commande découplée du flux et du couple pour des machines asynchrones de forte puissance. Celle-ci concerne l'ensemble alimentation-machine-charge. Des problèmes spécifiques apparaissent dus à la forte puissance et à la configuration de l'alimentation: découplage flux-couple, instabilité de la chaîne complète. Notre travail porte tout d'abord sur l'étude théorique de la commande découplée du flux et du couple: un découplage prenant en compte les constantes de temps naturelles du moteur a été obtenu. Puis, après avoir mis en évidence de manière théorique les problèmes d'instabilité constatés expérimentalement, nous montrons que l'on ne peut à la fois assurer le découplage couple/flux et la stabilisation. Une solution de compromis a été trouvée par une technique de stabilisation prenant en compte le filtre d'entrée. Diverses commandes lui ont été associées dont une commande de type H2, assurant des résultats satisfaisants sur toute la plage de vitesse ou cette commande peut être mise en œuvre. L’ensemble de la commande a été implanté sur une carte industrielle et testé expérimentalement sur un banc de 300 kW. Cette étude a été réalisée en collaboration avec la société GEC ALSTHOM TRANSPORT dans le cadre général de la conception de chaines de traction asynchrone pour le TGV de nouvelle génération

Ce travail de thèse traite du développement d'une méthode de télédiagnostique de l'état de santé des suspensions des trains à grande vitesse à partir de mesures de la réponse dynamique du train en circulation par des accéléromètres embarqués. Un train en circulation est un système dynamique dont l'excitation provient des irrégularités de la géométrie de la voie ferrée. Ses éléments de suspension jouent un rôle fondamental de sécurité et de confort. La réponse dynamique du train étant dépendante des caractéristiques mécaniques des éléments de suspension, il est possible d'obtenir en inverse des informations sur l'état de ces éléments à partir de mesures accélérométriques embarquées. Connaître l'état de santé réel des suspensions permettrait d'améliorer la maintenance des trains. D’un point de vue mathématique, la méthode de télédiagnostique proposée consiste à résoudre un problème statistique inverse. Elle s'appuie sur un modèle numérique de dynamique ferroviaire et prend en compte l'incertitude de modèle ainsi que les erreurs de mesures. Les paramètres mécaniques associés aux éléments de suspension sont identifiés par calibration Bayésienne à partir de mesures simultanées des entrées (les irrégularités de la géométrie de la voie) et sorties (la réponse dynamique du train) du système. La calibration Bayésienne classique implique le calcul de la fonction de vraisemblance à partir du modèle stochastique de réponse et des données expérimentales. Le modèle numérique étant numériquement coûteux d'une part, ses entrées et sorties étant fonctionnelles d'autre part, une méthode de calibration Bayésienne originale est proposée. Elle utilise un métamodèle par processus Gaussien de la fonction de vraisemblance. Cette thèse présente comment un métamodèle aléatoire peut être utilisé pour estimer la loi de probabilité des paramètres du modèle. La méthode proposée permet la prise en compte du nouveau type d'incertitude induit par l'utilisation d'un métamodèle. Cette prise en compte est nécessaire pour une estimation correcte de la précision de la calibration. La nouvelle méthode de calibration Bayésienne a été testée sur le cas applicatif ferroviaire, et a produit des résultats concluants. La validation a été faite par expériences numériques. Par ailleurs, l'évolution à long terme des paramètres mécaniques de suspensions a été étudiée à partir de mesures réelles de la réponse dynamique du train
The work presented here deals with the development of a health-state monitoring method for high-speed train suspensions using in-service measurements of the train dynamical response by embedded acceleration sensors. A rolling train is a dynamical system excited by the track-geometry irregularities. The suspension elements play a key role for the ride safety and comfort. The train dynamical response being dependent on the suspensions mechanical characteristics, information about the suspensions state can be inferred from acceleration measurements in the train by embedded sensors. This information about the actual suspensions state would allow for providing a more efficient train maintenance. Mathematically, the proposed monitoring solution consists in solving a statistical inverse problem. It is based on a train-dynamics computational model, and takes into account the model uncertainty and the measurement errors. A Bayesian calibration approach is adopted to identify the probability distribution of the mechanical parameters of the suspension elements from joint measurements of the system input (the track-geometry irregularities) and output (the train dynamical response).Classical Bayesian calibration implies the computation of the likelihood function using the stochastic model of the system output and experimental data. To cope with the fact that each run of the computational model is numerically expensive, and because of the functional nature of the system input and output, a novel Bayesian calibration method using a Gaussian-process surrogate model of the likelihood function is proposed. This thesis presents how such a random surrogate model can be used to estimate the probability distribution of the model parameters. The proposed method allows for taking into account the new type of uncertainty induced by the use of a surrogate model, which is necessary to correctly assess the calibration accuracy. The novel Bayesian calibration method has been tested on the railway application and has achieved conclusive results. Numerical experiments were used for validation. The long-term evolution of the suspension mechanical parameters has been studied using actual measurements of the train dynamical response

Cette thèse traite de l’incertitude et de la robustesse dans les problèmes de d´décision, avec le cas d’application des affectations de quais en gare en cas de retards. Une m´méthodologie en deux parties est proposée pour aborder ce problème. Dans un premier temps, les archives de données de retards sont utilisées pour construire des modèles de prédiction de distribution de probabilités conditionnellement aux valeurs d’un ensemble de variables explicatives. Une m´méthodologie de validation et d’évaluation de ces prédictions est mise en place afin d’assurer leur fiabilité pour de la prise de d´décision. Le problème d’affectations de quais pouvant être vu comme une recherche de clique de taille maximum, ces distributions prédites sont utilisées dans une seconde partie pour ajouter des pondérations pénalisant les risques de rupture des arêtes en cas de retard. Des algorithmes de recherche locale ont ´été utilisés et les expériences ont montré une importante baisse de conflits
This thesis deals with uncertainty and robustness in decision problems, with the case of the train platforming problem subject to delays. A two-part methodology is proposed to address this problem. First, delay records are used to build models predicting probability distributions conditionnaly to a set of explanatory variables. A methodology to validate and evaluate these predictions is proposed to ensure their reliability for decision-making. As the train platforming problem can be seen as a weighted clique problem, these predicted distributions are used in a second part to add weights on edges to penalize risk of conflict. Local search algorithms are used and experiments show a significant decrease in conflicts

Cette thèse, effectuée à la demande de la SNCF, apporte une contribution à la résolution du problème des grilles de service des agents roulants. Elle a donné lieu à AFGAR. Le problème posé est un problème complexe, combinatoire, pour lequel il n'existe pas d'algorithme efficace. Concrètement il s'agit, partant d'un ensemble de journées de travail, de trouver si possible la meilleure succession de journées de travail et de repos périodiques qui respectent les contraintes temporelles, règlementaires et humaines. Le principe méthodologique de la démarche de modélisation a été de faire une séparation nette entre un modèle du processus avec sa logique de fonctionnement et un modèle de la stratégie de résolution (du problème) avec sa logique de raisonnement. Ayant à représenter deux types de connaissances (structurelles et fonctionnelles d'une part, expertes et déductives d'autre part), le choix d'un formalisme hybride (objets et règles) s'imposait. Nous avons donc opté pour le générateur (hybride : règles et objets) de systèmes experts SMECI. La partie raisonnement est basée sur le modèle systémique Opérand, Information et Décision (OID). La partie fonctionnement est basée sur une méthodologie objet qui permet de structurer tant les classes que les instances. En synthèse, nous proposons une ébauche de méthodologie de développement des systèmes à base de connaissances