Search

RailBeijing 2021, 9th International Conference on Railway Operations Modelling and Analysis (ICROMA), Pékin, CHINE, 03-/11/2021 - 07/11/2021; The real-time Railway Traffic Management Problem (rtRTMP) is the problem of detecting and solving time-overlapping conflicting requests done by multiple trains on the same track resources. This problem consists in retiming, reordering and rerouting trains in such a way that the propagation of disturbances in the railway network is minimized. The rtRTMP is an NP-complete problem and finding good strategies to simplify its solution process is paramount to obtain good quality results in a short computation time. Solving the Train Routing Selection Problem (TRSP) aims to reduce the size of rtRTMP instances by limiting the number of routing variables: during a pre-processing the most promising routing alternatives among the available ones are selected for each train. These alternatives are the only ones to be then used in the rtRTMP solution. A first version of the TRSP has been recently proposed in the literature. This paper presents an improved TRSP model for stations where rolling stock re-utilization timing constraints and estimation of train delay propagation are taken into account. Additionally, a parallel Ant Colony Optimization (ACO) algorithm is proposed. We analyze the impact of the TRSP model and algorithm on the rtRTMP through a thorough computational campaign performed on a French case study with timetable disturbances and infrastructure disruptions. The model presented leads to a better correlation between TRSP and rtRTMP solutions, and the proposed ACO algorithm outperforms the former state-of-the-art.

RailBeijing 2021, 9th International Conference on Railway Operations Modelling and Analysis (ICROMA), Pékin, CHINE, 03-/11/2021 - 07/11/2021; On-demand shared transport systems have become an efficient means of transport that addresses the challenges of urban transport in large cities, and provides a flexible transport service to users according to their needs. In this paper, a public transport system based on a fleet of autonomous electric vehicles, from the point of view of the SNCF company, the largest public transport operator in France. The service operates on a dedicated infrastructure, based on a fixed timetable at peak hours and an on-demand service the rest of the time. The problem amounts to scheduling autonomous heterogeneous electric vehicles ondemand during off-peak hours. To model the problem, we propose to split the infrastructure into sections and segments. By doing so, we can model the scheduling of vehicles and manage their maneuvers including overtaking, turnarounds, and the access to single-lane sections, by using railway-inspired techniques. In this paper, we propose a mathematical model of this problem.

RailBeijing 2021, 9th International Conference on Railway Operations Modelling and Analysis (ICROMA), Pékin, CHINE, 03-/11/2021 - 07/11/2021; This professional paper presents the algorithmic framework for automatic timetable generation which is actually under development within the research project « Tools for mathematical optimization of strategic railway timetable models » funded by the Norwegian Railway Directorate. This framework is composed by two main components, which tackle the Train Timetabling Problem in a macroscopic model of infrastructure and operations. The first stage is a Multi-Objective Ant Colony Optimization (MOACO) algorithm which produces a Pareto Optimal Set of solutions. These are timetables optimized with respect to four main objectives, namely: the total travel time, the total energy consumption, the timetable robustness and the total number of scheduled trains. The MOACO treats conflict constraints as soft ones and produces strictly periodic traffic patterns. The second stage is a MILP formulation tackled with a commercial solver. It refines timetables produced by MOACO, looking for improvements in the neighbourhood of the solutions provided by the latter. MILP solutions are conflict-free timetables and can profit of given tolerances on trains periodicity. The MILP stage is used as a final refinement of the results as well as an intermediate local search during MOACO iterations.

RailBeijing 2021, 9th International Conference on Railway Operations Modelling and Analysis (ICROMA), Pékin, CHINE, 03-/11/2021 - 07/11/2021; Traffic perturbations in railway systems may give rise to conflicts, which cause delays w.r.t. the timetable. Dealing with them requires solving the real-time Rail Traffic Management Problem (rtRTMP). A subproblem of the rtRTMP is the real-time Energy Consumption Minimization Problem (rtECMP). It defines the speed profiles along with the timing of multiple trains in a given network and time horizon. It takes as input the train routing and precedences computed by a rtRTMP solver and its objective is to minimize train energy consumption and total delay. In this paper, we propose an Ant Colony Optimization algorithm for the rtECMP and we test it on the French Pierrefitte-Gonesse control area with dense mixed traffic. The results show that in 30 seconds a remarkable exploration of the search space is performed before convergence.

Les temps de stationnement en gare en Île-de-France peuvent avoir un impact significatif sur la régularité des trains transilien. L'optimisation des durées de stationnement est essentielle pour une exploitation efficace, en n'étant ni trop courtes, ni trop longues. Le déploiement d'un système de comptage automatique des voyageurs embarqué permet de comprendre les déterminants d'une telle durée optimale. Il en résulte une modélisation du temps de stationnement minimal, effectuée par gare et par sens, qui permet d'évaluer la probabilité que les temps de stationnement prévus dans la grille horaire soient respectés ou soient source de retards.

Rail Norrköping 2019, 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), Norrköping, SUEDE, 17-/06/2019 - 20/06/2019; This paper tackles the real-time Railway Traffic Management Problem (rtRTMP). It is the problem of finding an optimal choice for the train schedules and routes to reduce the delays of trains due to conflicts. We present a new formulation of the rtRTMP. This new formulation is based on a previously proposed one that models railway traffic at a microscopic level with optional activities using a Constraint Based Scheduling (CBS) approach. To ease the modelling of optional activities, a new concept based on a tree data structure and a specific filtering algorithm was extended through the introduction of conditional time-interval variables in Ilog CP-optimizer library. The new formulation of the rtRTMP presented in this paper exploits the conditional time-interval variables. The formulation has been validated with experiments on a large set of instances. The experimental results demonstrate the effectiveness of this new CBS model and show its good performance compared with the state-of-the art RECIFE-MILP algorithm.

RailNorrköping 2019, 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), Norrköping, SUEDE, 17-/06/2019 - 20/06/2019; In railway traffic management problems, a frequent approximation is the one of fixed-speed, i.e. the trains either run at their cruise speed or are stopped immediately without considering the acceleration and deceleration phases due to arising conflicts on the infrastructure. We assess the validity of the fixed-speed approximation for train speed dynamics in the real time Railway Traffic Management Problem. This is done through a statistical analysis on a number of perturbed scenarios on different railway infrastructures, for different objective functions commonly used in the literature. For each scenario, we analyze the ranking of the generated solutions both in the fixed-speed approximation, obtained by solving the optimization model, and with the variable-speed dynamics, obtained through micro simulation with the OpenTrack software. Our results indicate that some objective functions can be considered reliable when used in conjunction with the fixed-speed approximation, while others require more detailed studies. We also propose a modi?ed fixed-speed approximation to better reflect the behaviour of trains speed dynamics and study its efficiency.

ROADEF 2018, 19ème conférence de la Société française de Recherche Opérationnelle et d'Aide à la Décision, Lorient, FRANCE, 21-/02/2018 - 23/02/2018; Dans le cadre du projet européen OptiYard, nous voulons concevoir un outil d'optimisation qui a vocation à être adapté aux gares de triage en Europe pour le transport de marchandises. Provenant du réseau ferroviaire dit "classique", les trains arrivent et sortent respectivement par le faisceau de réception (ang. receiving tracks) et par le faisceau de départ (ang. departure tracks). Les wagons des trains réceptionnés sont recombinés de façon à former les trains attendus en sortie. Contrairement aux trains de passagers, l'ordre des wagons a ici de l'importance et c'est grâce aux allers-retours des wagons entre la butte de triage (ang. hump) et les voies de classification que les bonnes combinaisons sont obtenues. La butte sert à limiter l'énergie utilisée "à l'aller" pour envoyer un à un les wagons dans le faisceau de réception grâce à la force de gravitation, alors qu'"au retour", c'est un moteur qui sera utilisé pour remonter tout un ensemble de wagons d'une voie de classification vers la butte.

EURO 2018, 29th European Conference On Operational Research, Valence, ESPAGNE, 08-/07/2018 - 11/07/2018; The efficiency of rail good transportation is dependent on the processes implemented in shunting yards. Specifically, from the network, trains arrive and depart through the receiving and the departure bowl, respectively. The railcars of the inbound trains are recombined to form the desired outbound trains with the use of a hump from where they slide downhill to the classification bowl. If necessary, railcars may have to be pulled back and made slide again to achieve specific sortings. It is this going back and forth between the hump and the classification bowl that the optimization is most critical. Today, the recombination of the freight trains in yards can represent up to 50% of total transportation time. This large value can be explained by the weak automation and the lack of optimization. As part of the European project, OptiYard we will present an optimization tool designed to fit shunting yards in Europe. For assessing this tool, we will exploit microscopic simulation in a closed-loop framework. In this work, we realize a state of the art on the optimization of yard processes. We study different types of train sorting: simultaneous sorting, triangular sorting or geometric sorting. Recently quite complex methods have been published, many of them being based on integer programming. However, rather few papers exist on the real-time optimization of shunting yards, which could explain why, today, problems are solved "by hand" with empirically designed methods.

In this document we propose formulations of additional constraints or alternative objective functions which can be added to RECIFE-MILP. The aim of these refinements is acquiring the possibility of representing additional features of the railway traffic system and alternative traffic management strategies.

7th International Conference on Railway Operations Modelling and Analysis - Rail Lille, Lille, France, 04-/04/2017 - 07/04/2017; The real-time railway traffic management problem (rtRTMP) is the problem of solving time-overlapping conflicting track requests generated by disturbances during the normal course of daily operations. The size of an instance of the problem and the time required to solve it are particularly affected by the number of routing alternatives available to each train. The real-time train routing selection problem (rtTRSP) chooses a feasible routing subset for each train to use as input for the real-time railway traffic management problem. In particular, the validity of the problem and the impact of its solution have been analyzed in the literature. The analysis has been performed by using a specific mixed-integer linear programming model and the RECIFE-MILP solution approach for the rtRTMP. This paper generalizes such analysis by considering also a different model, objective function and solution approach for the rtRTMP. We consider the decision support system AGLIBRARY which solves an alternative graph model of the problem to minimize the maximum consecutive delay. The aim is to assess whether the selection of a subset of routings brings advantages for different solvers. We analyze how changes in the rtRTMP model have to be reflected in the rtTRSP and, if so, which modifications are required. The computational analysis is performed on two French infrastructures: the line around the city of Rouen and the Lille terminal station area. The analysis shows that solving the rtTRSP helps both solvers significantly, even if they are based on different models and algorithms.

7th International Conference on Railway Operations Modelling and Analysis - Rail Lille, Lille, France, 04-/04/2017 - 07/04/2017; Maintenance activities are necessary to maintain the functionality of the railway infrastructure. Commonly, timetables are elaborated by considering the infrastructure unavailability periods caused by the performance of maintenance activities. However, sometimes unplanned maintenance activities have to be introduced at short notice, and the timetable must be rearranged to respect the new unavailabilities. Moreover, most of these activities require the presence of special maintenance trains which are typically not scheduled in the timetable and may have an impact on other train circulations. In this paper, we propose a mixed-integer linear programming formulation that rearranges a timetable to cope with the performance of maintenance activities. It includes the consideration of maintenance trains and other specific constraints, such as temporary speed restrictions. In this formulation, the rearrangement of the timetable is optimized based on a microscopic representation of both the infrastructure and the rolling stock. We assess two algorithms founded on this formulation on a real case study in the French railway network and we show their practical applicability.

7th International Conference on Railway Operations Modelling and Analysis - Rail Lille, Lille , France, 04-/04/2017 - 07/07/2017; In railway, the saturation problem consists in scheduling extra train paths within an existing timetable, intended to be a fixed reference. Inserting extra train paths reduces the global timetable stability, if compared to that of the not-saturated timetable. A compromise should therefore be sought, introducing constraints on the number and characteristics of the saturating paths in order to keep the stability of saturated timetables within a desired range. In this study, this task is performed by imposing that saturating paths are separated by a given buffer time. The study aims to provide some figures about the way in which buffer time affects the number of saturating paths and the stability of the resulting timetable. We saturate a real timetable (concerning a 70 km long French railway) using a mixed integer linear programming algorithm, imposing seven increasing values of buffer time. We perform the saturation considering two different time windows (during peak and off-peak hours) and two sets of saturating path types. The stability of the saturated timetables is evaluated through OpenTrack simulations with perturbed traffic conditions. The simulations are carried out with two perturbation scenarios. In this way the influence on stability of the parameters combination used in saturation is assessed. Results are presented and discussed, highlighting the role of the buffer time and of the type of saturating paths in providing stable saturated timetables.

In this paper, we propose a Benders' decomposition algorithm to tackle the real time railway traffic management problem. We decompose the mixed-integer linear programming formulation at the basis of RECIFE-MILP, a state-of-the art algorithm for the real time railway traffic management problem. In our Benders' decomposition algorithm, train routing and scheduling decisions are made in the master problem. Given these decisions, we compute the trains arrival and passing times in the slave problem to deduce the total delay. By applying our Benders' decomposition algorithm to RECIFE-MILP, we tackle large instances representing traffic in the Rouen-Rive-Droite control area.

ROADEF 2017, 18ème conférence de la Société française de Recherche Opérationnelle et d'Aide à la Décision, Metz, France, 22-/02/2017 - 24/02/2017; Maintenance activities are necessary to maintain the functionality of the railway infrastructure. Commonly, the maintenance activities are planned first. Then, the timetable is elaborated respecting the unavailability periods caused by the former. However, unplanned maintenance activities may have to be introduced at short notice, and the timetable must be rearranged. In addition, specific trains may be necessary to perform maintenance activities, and they are typically not scheduled in the timetable. In this case, the timetable may need to be further modified to integrate the maintenance trains. In this paper, we propose a mixed integer linear programming formulation that modifies a timetable to cope with maintenance activities. It includes the consideration of maintenance trains and other specific constraints, such as temporary speed limitations.In this formulation, the modified timetable is optimized based on a microscopic representation of both the infrastructure and the rolling stock. We test the proposed formulation on a real case study in the French railway network and we show its practical applicability.

7th International Conference on Railway Operations Modelling and Analysis - Rail Lille, Lille, France, 04-/04/2017 - 07/04/2017; In this paper we propose a reformulation of RECIFE-MILP aimed at boosting the algorithm performance. RECIFE-MILP is a mixed integer linear programming based heuristic for the real-time railway traffic management problem, that is, the problem of re-routing and rescheduling trains in case of perturbation in order to minimize the delay propagation. The reformulation which we propose exploits the topology of the railway infrastructure. Specifically, it capitalizes on the implicit relations between routing and scheduling decisions to reduce the number of binary variables of the formulation. In an experimental analysis based on realistic instances representing traffic in the French Pierrefitte-Gonesse junction, we show the performance improvement achievable through the reformulation.

Measuring capacity of railway infrastructures is an open problem even in its definition. In this paper, we propose RECIFE-SAT, a MILP-based algorithm to quantify capacity by solving the saturation problem. This problem consists in saturating an infrastructure by adding as many trains as possible to an existing (possibly empty) timetable. In an experimental analysis performed in collaboration with the French infrastructure manager, we show the promising performance of RECIFE-SAT. To the best of our knowledge, RECIFE-SAT is the first algorithm which is shown to be capable of saturating rather large railway networks considering a microscopic infrastructure representation. This representation allows RECIFE-SAT to really quantify the actual capacity of the infrastructure considered.

Ce livrable Phare du COP 12-16 synthétise les travaux effectués au cours de ces quatre dernières années par les laboratoires ESTAS et LEOST dans le domaine de la régulation de trafic ferroviaire. Ces travaux ont été marqué par l'implication dans deux projets majeurs ; Le projet Predit SIGIFret réalisé entre 2012 et 2015 ainsi que leprojet Européen FP7 ON-TIME effectué entre 2011 et 2015.

The real-time Railway Traffic Management problem consists in funding suitable train routes and schedules to minimize delay propagation due to traffic perturbations. RECIFE-MILP is a mixed integer linear programming based heuristic for this problem which has proven to be effective in various contexts. However, when instances are very large or difficult, the performance of the algorithm may worsen. In this paper, we propose valid inequalities to boost the performance of RECIFE-MILP. These valid inequalities link the routing and scheduling binary variables and, at least in some cases, they are able to represent all the facets of the projection of the convex hull of the problem in the subspace of the binary variables. Moreover, they allow the definition of a model reformulation based on a reduced number of scheduling binary variables. In an experimental analysis based on realistic instances representing traffic in four French infrastructures, we observe that the addition of valid inequalities must be done thoroughly not to add too much computational burden to the solution process, and that the reduction of the number of binary variables in general boosts the performance of RECIFE-MILP significantly.

WCRR 2016, 11th World Congress of Railway Research, Milan, Italie, 29-/05/2016 - 02/06/2016; RECIFE-MILP is a well performing heuristic to tackle the real-time railway traffic management problem. This is the problem of routing and scheduling trains in case of perturbation, aiming at the minimization of delay propagation. In this paper, we show how RECIFE-MILP has been successfully applied to different case-studies, in collaboration with European railway undertakings and infrastructure managers. Indeed, despite the positive results achieved in these applications, several open questions remain on how to actually deploy a tool as RECIFE-MILP in the practice. In the final part of this work, we focus on some of these questions and we describe our experience with respect to them.

RailTokyo2015, 6th International Conference on Railway Operations Modelling and Analysis, Tokyo, JAPON, 23-/03/2015 - 26/03/2015; When railway traffic is perturbed by unexpected events, an appropriate train routing and scheduling may be applied to minimize delay propagation. In the literature, several algorithms have been proposed and tested in various traffic situations. However, their performance have almost always been studied neglecting the imperfect knowledge of precise traffic conditions which is almost impossible to avoid in reality. In this paper, we propose an empirical analysis assessing the applicability of these algorithms in case of imperfect information. In particular, we consider RECIFE-MILP as a traffic management algorithm and advanced or delayed train entrance times in the infrastructure as a source of imperfect information. The results show that the application of traffic management optimization allows outperforming the first-come-first-served management strategy even if the actual traffic conditions are not perfectly known by the optimization algorithm.

International audience; The construction of a timetable represents a critical part on the development of the yearly service plan for railway operations. The Train Timetabling Problem (TTP) aims to find a timetable that must respond both to commercial needs and certain capacity and security related constraints. The combination of the latter, makes the TTP a complex and time consuming process. While most approaches on the literature offers exact solving models, once they are applied on real-size instances, they fail to solve the problem within a reasonable amount of time. Reason for which, heuristic or relaxation techniques are extensively used. In this paper, we first propose an alternative mathematical model to tackle the TTP. Next, we present a Genetic Algorithm implementing our model in order to rapidly obtain near-optimal train timetables. Finally, we test the implementation of our model on a case study based on the German railway network.

La volonté politique de développer le fret ferroviaire se heurte à plusieurs problèmes qui le confinent au déclin par son manque de compétitivité. L'initiative MaxiPerfo, lancée en 2010 à la suite de l'Engagement National pour Fret Ferroviaire, a pour objectif de réaliser un saut de performance au fret ferroviaire par le biais du déploiement d'innovations techniques. Les innovations couvrent plusieurs composants du système ferroviaire comme la modernisation du matériel roulant, permettre la circulation de trains longs sur le réseau et l'introduction d'outils d'aide à la décision qui améliorent l'intégration des circulations de trains fret avec celles des trains de voyageurs. Le projet SIGIFret s'inscrit dans ce contexte et vise à étudier l'apport de ces outils d'aide à la décision dans les phases de gestion opérationnelle du trafic comme dans les phases amont de planification. SIGIFret est un projet du programme de recherche PREDIT avec pour partenaires SNCF Réseau et l'IFSTTAR. Le projet est structuré en deux parties. Dans la première partie du projet, l'objectif était d'évaluer l'apport d'un outil d'aide à la gestion opérationnelle du trafic. Pour cela, la ligne Paris-Le Havre a été choisie comme cas d'étude en raison de la mixité des circulations qui la traversent et de la présence de deux noeuds ferroviaires critiques : les gares de Mantes-La-Jolie de Rouen-Rive-Droite. Toute l'étendue de la ligne contrôlée par les postes de régulation de ces gares a été modélisée dans l'outil de simulation OpenTrack. Cet outil est capable de reproduire a un niveau microscopique le comportement des circulations à partir de la description de la topologie de la voie, du système de signalisation et de la dynamique des trains. Avec cet outil, on est donc en mesure d'évaluer l'impact de différentes décisions de régulation. La modélisation couvre 7 kilomètres de ligne autour de la gare de Mantes-la-Jolie et 27 kilomètres de ligne autour de Rouen-Rive-Droite. Pour chaque zone de régulation, nous avons considéré plusieurs scénarios de perturbations sur lesquels nous avons comparé quatre stratégies de régulation selon plusieurs indicateurs de performances lies à la régularité et à la consommation d'énergie. Toutes les stratégies de régulation sont appliquées à chaque scenario puis les décisions sont simulées dans l'outil OpenTrack afin d'évaluer les différents indicateurs. Les résultats montrent clairement l'apport d'un outil d'optimisation pour une meilleure intégration des trains fret et des trains de passagers au niveau de la gestion opérationnelle des circulations. L'objectif de la seconde partie du projet était de traiter le problème de l'intégration des trains de fret aussi au niveau de la phase de planification. Dans ce but, une méthode de calcul de la capacité a été conçue, elle a pour principe d'intégrer le maximum de trains supplémentaires à une grille horaire existante. Parmi ces trains supplémentaires, une attention particulière est portée aux trains de fret. Comme dans la première partie du projet, les zones autour des gares de Mantes-la-Jolie et de Rouen-Rive-Droite ont été considérées comme cas d'application, mais cette fois-ci en y incluant toute la section de ligne qui relie ces deux gares. Un algorithme d'optimisation bi-objectif a été développé pour l'évaluation de la capacité. Les deux objectifs considérés sont d'une part la maximisation du nombre de trains supplémentaires et d'autre part le nombre de trains de fret supplémentaires. Les contraintes de l'infrastructure de niveau microscopique ont été prises en compte pour être en cohérence avec le modèle utilisé dans la première partie. La méthode développée a permis de saturer la grille horaire actuelle sur différents horizons temporels. Pour la période couvrant l'heure de pointe et le flanc de pointe, la méthode a réussi à intégrer 332 trains supplémentaires avec plus de 100 trains de fret (plus du double du nombre actuellement présent dans la grille horaire). Cette grille horaire très dense peut ainsi fournir un indicateur de la capacité résiduelle de l'infrastructure considérée. De la même façon, cette méthode peut être utilisée pour l'évaluation de l'analyse de la capacité de différentes options de modification d'infrastructures ou lors des phases d'adaptation du service annuel pour satisfaire a des demandes de sillons de dernières minutes.

In the real-time railway traffic management problem, the number of alternative routings available to each train strongly affects the size of the problem and the time required to optimally solve it. The train routing selection problem identifies a suitable subset of alternative routings to be used for each train in the real-time railway traffic management. This paper analyzes the impact of solving the train routing selection problem at different levels. The problem can be solved at tactical level right after the timetabling process, using historical traffic data and with abundant computation time. In this case the problem constitutes an integration step between the timetabling and the real-time traffic management. Alternatively, the problem can be solved at operational level right before the real-time railway traffic management problem solution, using up to date traffic perturbation and a real-time time limit of computation. Experiments are performed on two French test cases, the line around Rouen and the Lille station area, for several disturbed and disrupted scenarios. The results show that the best approach depends on the type of traffic disturbance tackled.

ITSC 2018, 21st International Conference on Intelligent Transportation Systems, Maui - Hawaï, ETATS-UNIS, 04-/11/2018 - 07/11/2018; The real-time railway traffic management problem (rtRTMP) aims to solve time-overlapping conflicting track requests due to traffic disturbances. The size of the problem and the time required to solve it are affected by the number of routing alternatives available to each train. The real-time train routing selection problem (rtTRSP) chooses a feasible routing subset for each train to use as input for the rtRTMP. Recently, a computational analysis has been performed via Ant Colony Optimization and the RECIFE-MILP solver. This paper generalizes such analysis by considering a different rtRTMP model, objective function and solution approach. We adopt the AGLIBRARY solver, which is based an alternative graph model of the problem and minimizes the maximum consecutive delay. The aim is to develop real-time disturbance response strategies and to quantify the advantages of the selection of a subset of routings when using different solvers. We analyze how changes in the rtRTMP model are reflected in the rtTRSP and which modifications are required. The computational analysis is performed on two French infrastructures: the line around the city of Rouen and the Lille terminal station area. The analysis shows that solving the rtTRSP helps both solvers significantly, even if they are based on different models, objectives and algorithms.