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; 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.

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. Specifically, we decompose the mixed-integer linear programming formulation at the basis of RECIFE-MILP (Pellegrini et al., 2015), a state-of-the-art algorithm for this problem. In our Benders' decomposition, we minimize total delays by making train routing and scheduling decisions 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, in France.

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.

Transportation Research Board 96th Annual Meeting - TRB, Washigton, D.C., Etats-Unis, 08-/01/2017 - 12/01/2017; Railway operations are sometimes perturbed by disruptions which impose a reorganization of the service plan. Such disruptions may be due to several causes, from external attacks to extreme weather conditions, but they all have the common characteristic of constraining the access to a part of the infrastructure. This requires the combined effort of infrastructure managers and railway undertakings for finding the most efficient alternative schedule to cope with the new constraints. In the Capacity4Rail FP7 European project, we study the disruption management process implemented in different European countries (UK, France, Spain and Sweden) and we define a formalization of the process capable of representing the current practice and its expected development. In particular, we formalize the common activities and, where possible, we advance generalizations, validating the result with the aid of the infrastructure managers. Through the analysis of this process, the needs of improvements in some specific activities can be pointed out, and different solutions can be envisioned. In this paper, we propose this formalization through the aid of SysML diagrams, with SysML being a standardised and open source modelling language for system engineering. The paper shows the applicability of the model in a large disruption handling process and provides some basic model properties validated using a model checking algorithm.

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.

National audience; Maintenance Activities (MA's) are necessary to sustain the state and functionality of the railway infrastructure. However, MA's directly or indirectly affect the circulations of trains in the network, either by banning or by restraining them in some locations. Therefore, an efficient coordination between MA's and train irculations is necessary to optimize the railway capacity utilization.In the first part of this work, we present a MILP formulation for rescheduling and rerouting trains that are directly or indirectly affected by MA's. This formulation can be used to validate or to optimize the train schedules and routes with great precision, since a microscopic perspective of the infrastructure and rolling stock is considered. In the second part, we discuss some experimental results obtained with our formulation in a real-world case study in the French railway network. Finally, we present our conclusions and perspectives.

RECIFE is a decision support platform developed at IFSTTAR. It includes several algorithms to deal with different problems which emerge in railway planning and operation. These algorithms use a common data structure to represent railway data. This report describes this data structure. Moreover, the report summarizes the main elements of RECIFE Class Manager, a C++ library used in the RECIFE algorithms implementation.

In railway, when a disruption occurs, the traffic may be perturbed, as a result, conflicts and delays may emerge. Modifying trains route and schedule to limit delay propagation in the network is the focus of the real-time Railway Traffic Management Problem (rtRTMP). In this work, we addressed the solution of the rtRTMP using a Benders decomposition approach. The decomposition algorithm is applyed to the mixed integer linear programming formulation of the problem. We test the algorithm to instances representing traffic in the junction of Gonesse, in France. The results are promising.

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.

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.

Railway operations management must cope with system failures and external disturbances that may cause delays. In heavy traffic areas, these delays can quickly propagate. This study details the results of a railway traffic optimization tool based on a MILP formulation. The case studies tackled represent different European locations. These experiments are part of a task the European FP7 project ON-TIME. The project aims to develop a prototype for a new generation of railway traffic management systems which will increase capacity and decrease delays for railway customers’ satisfaction.

We propose an optimal train dispatching module which computes in real-time the train routing and scheduling that minimize delay propagation. For solving this real-time railway traffic management problem, we exploit a fixed-speed mixed-integer linear programming (MILP) formulation (Pellegrini et al., 2014). To take into account the operational constraints, we impose here a maximum computation time to the MILP solver: the resulting algorithm is a heuristic which returns the optimal solution as soon as the search process is completed (the optimal solution is found and its optimality is proven) or returns the incumbent solution if the maximum computation time is reached (Pellegrini et al., 2013). The object of this work is to compare through simulation the solutions proposed by this formulation with the current dispatching rule. The scenarios tackled include both passenger and freight traffic at peack time. The experiments which we present have been produced in the context of the PREDIT project SIGIFret (Simulation d'une gestion innovante des circulations fret).

La gestion du trafic ferroviaire s’effectue par choix de routage et d'ordonnancement des trains qui minimisent la propagation de retards en cas de perturbation. Dans cet article, nous proposons des inégalités valides et des choix algorithmiques permettant d’améliorer les performances d'une formulation de programmation linéaire en nombres entiers pour la gestion du trafic ferroviaire. Dans l'analyse expérimentale, nous montrons que ces propositions améliorent effectivement les temps de calcul pour résoudre de manière exacte les instances représentatives du trafic dans une jonction française complexe: la gare Lille-Flandres.

TRB 2014 - Transportation Research Board 93rd Annual Meeting, WASHINGTON D.C, ETATS-UNIS, 12-/01/2014 - 16/01/2014; Transilien, the branch of SNCF in charge of operating the main urban railroad network in the area of Paris, faces a regular increase of passengers flows. The planning of railway operations is made carefully: simulation runs permit to assess the timetable stability. However, many disturbance 5 appears and cause trains delays. Due to the nature of the railroad network those delays are cumulative and an on-line update of the timetable is not always successful in maintaining the trains schedule. In this tensed context, operators are searching solutions to better use the infrastructure capacity and better service quality. A needed step towards this objective is a better understanding of the phenomena of disruptions. In particular because the expansion of congestion is not clearly 10 understood until now. This paper explores the possibility to transpose a traffic flow theory tool, the network fundamental diagram, in the field of dense railroad traffic. Railroad traffic is different of road traffic by many ways: railways are a planned system, traffic volume does not satisfy the continuum hypothesis, stations force stops and the signalization system brings a discrete behavior. Despite those big differences we show how to build a network fundamental diagram for a railroad 15 system and how to interpret some obtained shapes for those diagrams. These diagrams gives us some means to compare planned and reality. We also identify the limits that need to be overcome to take benefits of the road traffic tools in railroad traffic analysis.

International audience; Railway operations management must cope with failures of the railway system and with external disturbances that may cause initial delays, the so-called primary delays. In heavy traffic areas of railway networks, primary delays can quickly lead to many further delays, called secondary delays or knock-on delays. This paper describes the results of an experimental analysis which aims to evaluate the ability of railway traffic optimization tools to decrease secondary delays, by selecting appropriate route settings and sequences of train movements. We have previously proposed a mixed-integer linear programming (MILP) formulation to tackle this problem (Pellegrini, P., Marlière, G. and Rodriguez, J. 2013. Optimal train routing and scheduling for managing traffic perturbations in complex junctions, Transportation Research Part B: Methodological, to appear). This formulation considers a fine granularity of the infrastructure and it takes into account a large number of commercial and technical aspects characterizing real situations, e.g., passenger and rolling stock connections between trains, signal watching times, different numbers of signaling aspects, sectional route release of the interlocking systems. The experiments reported in this paper have been carried out in the context of the ON-TIME European project (http://www.ontime-project.eu/). This project aims to develop a prototype for a new generation of railway traffic management systems which will increase capacity and decrease delays, for augmenting customers' satisfaction. The results of the project will be validated through system simulation and real-life case studies proposed by different railway undertakings partners of the project.

Unexpected events often perturb railway traffic. The impact of these events may be very remarkable in terms of delay propagation. We analyze a mixed integer linear programming (MILP) formulation which aims at minimizing the delay propagation when traffic is perturbed. It does so by modifying train routing and scheduling at junctions. This formulation is able to solve to optimality many realistic instances in a computation time which is in line with real-time purposes. However, for the most difficult instances, finding the optimal solution is too time consuming. In this paper, we assess the performance of the MILP formulation when a short time limit is imposed. Moreover, we propose different methods for boosting this performance. We tackle instances representing traffic in the Lille-Flandres station (France), and we show that the boosted MILP formulation achieves very positive results, finding the optimal solution in more than 75% of the experimental runs.

Rail traffic management consists in optimizing perturbed traffic selecting train routing and scheduling. In this study, we propose different sets of valid inequalities for boosting the performance of a MILP formulation in terms of computation time. We apply an automatic algorithm configuration procedure for selecting both the appropriate sets of inequalities and the solver parameter settings to be applied for tackling traffic perturbations in different infrastructures. Our results show that the performance of the formulation improves significantly when the appropriate configuration is used.

In railway timetabling, the train running times are often known as the shortest durations between two stations increased of some percent of time. The running times are estimated by constructing the speed profiles that the trains must hold along the track. In this paper, an approach is proposed to compute several speed profiles for a same travel. The optimization approach involves two objectives optimized concurrently: the minimization of the journey duration and the minimization of the energy spent for the travel. Based on an evolutionary bi-objective algorithm, the optimization approach is applied to three instances and results are reported and analyzed.

In this paper, we propose a mixed-integer linear programming formulation for tackling a classic problem in railway traffic management. In particular, we deal with perturbed traffic in a complex junction. Here, multiple lines cross allowing train routing and scheduling modifications with respect to the planned timetable. Our formulation exploits alternative routing and scheduling to minimize delay propagation. This formulation allows modelling the infrastructure in terms of track-circuits, that is, with a higher granularity than what is typically done in the literature (where only block sections are modeled). In a thorough experimental analysis, we assess the impact of this granularity. The results indicate that, through the finer granularity, it is possible to achieve a much higher exploitation of the existing capacity.

L’une des problématiques actuelles du domaine ferroviaire est de minimiser la consommation énergétique sur le réseau sans impacter plus que nécessaire le temps de trajet des trains. Le modèle présenté a pour objectif d’une part, de proposer un ensemble de profils de vitesse étant des compromis entre temps de parcours et consommation énergétique. Et d’autre part de pouvoir intégrer facilement cette approche dans différents modèles multi-train.

At peak hours, railway timetables extensively exploit the infrastructure for accommodating traffic. Hence, the occurrence of unexpected events, even of apparently negligible entity, may cause a relevant deviation with respect to the scheduled timetable. If a train is delayed due to an unexpected event, conflicts may emerge, multiple trains may claim the same track section concurrently : in this case trains may have to stop or slow-down for ensuring safety and delay propagation may emerge. The selection of the train routing and scheduling for minimizing delay propagation has been formalized as the real-time Railway Traffic Management Problem (rtRTMP). In this study, we propose a fixed-speed mixed-integer linear programming formulation for optimally solving the rtRTMP. We model the infrastructure in terms of track-circuits, which are the basic components for train detection. In a thorough experimental analysis we quantify the improvement, in terms of reduction of delay propagation, that can be achieved by allowing the platform assignment to be different from the one defined in the timetable.

The real time railway traffic management seeks for the train routing and scheduling that minimize delays after an unexpected event perturbs the operations. In this paper, we propose a mixed-integer linear programming formulation for tackling this problem, modeling the infrastructure in terms of track-circuits, which are the basic components for train detection. This formulation considers all possible alternatives for train rerouting in the infrastructure and all rescheduling alternatives for trains along these routes. To the best of our knowledge, we present the first formulation that solves this problem to optimality. We tested the proposed formulation on real perturbation instances representing traffic in a control area including the Lille Flandres station (France), achieving very good performance in terms of computation time.

Scheduling theory (ST) is a formal framework which have been used many times over the last decade as starting point to model railway traffic management. Graph theory (GT), mathematical programming (MP) or constraint programming (CP) have also be used as additional steps to scheduling theory. This is illustrated in figure 1. The last step is a solution algorithm that is many times based a complete or partial enumeration procedure (EP) of feasible solutions where large subsets are discarded. This article will focus on the path ST → CP → EP to solve railway management problems. I will first briefly introduce each field, and after applications to the railway traffic management.

Scheduling is the process of allocating resources to activities over time. In a scheduling problem, resources are scarce and constrained in various ways (e.g. in the order of activities and the capacity of resources), and one is looking for a schedule of the activities that both satisfies the constraints and is optimal according to some criteria. This paper deals with an extension of a constraint-based scheduling model of real time management of train traffic through junctions and large stations. This extension allows the improvement of the model of conflicts between trains running in opposite directions with the use of state resources. To tackle large instances, a temporal decomposition has been used. We tested the model and algorithms by applying to problem instances of a real terminal station. Computational results show that with the temporal decomposition method we are able to obtain good solution in short computation time

Pour faire face à l'accroissement de la demande du trafic sans faire de nouveaux investissements, les gestionnaires d'infrastructure se penchent sur les possibilités d'améliorer l'exploitation de certains points critiques du réseau. Ces points critiques sont parcourus par des circulations mixtes (fret, grande ligne, TGV, . . .) avec de nombreux types de conflits. Les opérateurs qui gèrent les circulations doivent prendre des décisions difficiles afin d'arbitrer ces conflits. La difficulté provient principalement des nombreuses contraintes qu'il faut considérer. Le travail présenté dans ce chapitre porte sur la résolution du problème d'optimisation de la gestion opérationnelle des circulations. Le modèle qui est proposé pour traiter ce problème s'appuie sur la théorie de l'ordonnancement et la programmation par contraintes. La présentation du modèle se focalise sur la justification des hypothèses de modélisation. Ces hypothèses sont comparées avec celles d'autres travaux qui utilisent la même approche. Des expérimentations sur des instances de problèmes à partir de données réels montrent les bonnes performances de ce modèle

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.

This paper deals with the real-time problem of scheduling and routing trains in a railway network. In the related literature, this problem is usually solved starting from a subset of routing alternatives and computing the near-optimal solution of the simplified routing problem. We study how to select the best subset of routing alternatives for each train among all possible alternatives. The real-time train routing selection problem is formulated as an integer linear programming formulation and solved via an algorithm inspired by the ant colonies' behavior. The real-time railway traffic management problem takes as input the best subset of routing alternatives and is solved as a mixed-integer linear program. The proposed methodology is tested on two practical case studies of the French railway infrastructure: the Lille terminal station area and the Rouen line. The computational experiments are based on several practical disturbed scenarios. Our methodology allows the improvement of the state of the art in terms of the minimization of train consecutive delays. The improvement is around 22% for the Rouen instances and around 56% for the Lille instances. © 2016 Elsevier Ltd. This paper deals with the real-time problem of scheduling and routing trains in a railway network. In the related literature, this problem is usually solved starting from a subset of routing alternatives and computing the near-optimal solution of the simplified routing problem. We study how to select the best subset of routing alternatives for each train among all possible alternatives. The real-time train routing selection problem is formulated as an integer linear programming formulation and solved via an algorithm inspired by the ant colonies' behavior. The real-time railway traffic management problem takes as input the best subset of routing alternatives and is solved as a mixed-integer linear program. The proposed methodology is tested on two practical case studies of the French railway infrastructure: the Lille terminal station area and the Rouen line. The computational experiments are based on several practical disturbed scenarios. Our methodology allows the improvement of the state of the art in terms of the minimization of train consecutive delays. The improvement is around 22% for the Rouen instances and around 56% for the Lille instances.