Integrated optimization on train scheduling and preventive maintenance time slots planning

We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method.     

An improved car‐following model for railway traffic

In this paper, we propose an improved traffic model for simulating train movement in railway traffic. The proposed model is based on optimal velocity car‐following model. In order to test the proposed model, we use it to simulate the train movement with fixed‐block system. In simulations, we analyze and discuss the space–time diagram of railway traffic flow and the trajectories of train movement. Simulation results demonstrate that the proposed model can be successfully used for simulating the train movement in railway traffic. From the space–time diagram, we find some complex phenomena of train flow, which are observed in real railway traffic, such as train delays. By analyzing the trajectories of train movement, some dynamic characteristics of trains can be reproduced. Copyright © 2011 John Wiley & Sons, Ltd.     

Closing the loop in real-time railway control: Framework design and impacts on operations

Railway traffic is heavily affected by disturbances and/or disruptions, which are often cause of delays and low performance of train services. The impact and the propagation of such delays can be mitigated by relying on automatic tools for rescheduling traffic in real-time. These tools predict future track conflict based on current train information and provide suitable control measures (e.g. reordering, retiming and/or rerouting) by using advanced mathematical models. A growing literature is available on these tools, but their effects on real operations are blurry and not yet well known, due to the very scarce implementation of such systems in practice.In this paper we widen the knowledge on how automatic real-time rescheduling tools can influence train performance when interfaced with railway operations. To this purpose we build up a novel traffic control framework that couples the state-of-the art automatic rescheduling tool ROMA, with the realistic railway traffic simulation environment EGTRAIN, used as a surrogate of the real field. At regular times ROMA is fed with current traffic information measured from the field (i.e. EGTRAIN) in order to predict possible conflicts and compute (sub) optimal control measures that minimize the max consecutive delay on the network. We test the impact of the traffic control framework based on different types of interaction (i.e. open loop, multiple open loop, closed loop) between the rescheduling tool and the simulation environment as well as different combinations of parameter values (such as the rescheduling interval and prediction horizon). The influence of different traffic prediction models (assuming e.g. aggressive versus conservative driving behaviour) is also investigated together with the effects on traffic due to control delays of the dispatcher in implementing the control measures computed by the rescheduling tool.Results obtained for the Dutch railway corridor Utrecht–Den Bosch show that a closed loop interaction outperforms both the multiple open loop and the open loop approaches, especially with large control delays and limited information on train entrance delays and dwell times. A slow rescheduling frequency and a large prediction horizon improve the quality of the control measure. A limited control delay and a conservative prediction of train speed help filtering out uncertain traffic dynamics thereby increasing the effectiveness of the implemented measures.     

A delay propagation algorithm for large-scale railway traffic networks

In scheduled railway traffic networks a single delayed train may cause a domino effect of secondary delays over the entire network, which is a main concern to planners and dispatchers. This paper presents a model and an algorithm to compute the propagation of initial delays over a periodic railway timetable. The railway system is modelled as a linear system in max-plus algebra including zero-order dynamics corresponding to delay propagation within a timetable period. A timed event graph representation is exploited in an effective graph algorithm that computes the propagation of train delays using a bucket implementation to store the propagated delays. The behaviour of the delay propagation and the convergence of the algorithm is analysed depending on timetable properties such as realisability and stability. Different types of delays and delay behaviour are discussed, including primary and secondary delays, structural delays, periodic delay regimes, and delay explosion. A decomposition method based on linearity is introduced to deal with structural and initial delays separately. The algorithm can be applied to large-scale scheduled railway traffic networks in real-time applications such as interactive timetable stability analysis and decision support systems to assist train dispatchers.     

Railway traffic disturbance management—An experimental analysis of disturbance complexity,management objectives and limitations in planning horizon

With the increasing traffic volumes in European railway networks and reports on capacity deficiencies that cause reliability problems, the need for efficient disturbance management becomes evident. This paper presents a heuristic approach for railway traffic re-scheduling during disturbances and a performance evaluation for various disturbance settings using data for a large part of the Swedish railway network that currently experiences capacity deficiencies. The significance of applying certain re-scheduling objectives and their correlation with performance measures are also investigated. The analysis shows e.g. that a minimisation of accumulated delays has a tendency to delay more trains than a minimisation of total final delay or total delay costs. An experimental study of how the choice of planning horizon in the re-scheduling process affects the network on longer-term is finally presented. The results indicate that solutions which are good on longer-term can be achieved despite the use of a limited planning horizon. A 60 min long planning horizon was sufficient for the scenarios in the experiments.     

Multi-level condition-based maintenance planning for railway infrastructures – A scenario-based chance-constrained approach

This paper develops a multi-level decision making approach for the optimal planning of maintenance operations of railway infrastructures, which are composed of multiple components divided into basic units for maintenance. Scenario-based chance-constrained Model Predictive Control (MPC) is used at the high level to determine an optimal long-term component-wise intervention plan for a railway infrastructure, and the Time Instant Optimization (TIO) approach is applied to transform the MPC optimization problem with both continuous and integer decision variables into a nonlinear continuous optimization problem. The middle-level problem determines the allocation of time slots for the maintenance interventions suggested at the high level to optimize the trade-off between traffic disruption and the setup cost of maintenance slots. Based on the high-level intervention plan, the low-level problem determines the optimal clustering of the basic units to be treated by a maintenance agent, subject to the time limit imposed by the maintenance slots. The proposed approach is applied to the optimal treatment of squats, with real data from the Eindhoven-Weert line in the Dutch railway network.     

Techniques for inserting additional trains into existing timetables

In this paper techniques for scheduling additional train services (SATS) are considered as is train scheduling involving general time window constraints, fixed operations, maintenance activities and periods of section unavailability. The SATS problem is important because additional services must often be given access to the railway and subsequently integrated into current timetables. The SATS problem therefore considers the competition for railway infrastructure between new services and existing services belonging to the same or different operators. The SATS problem is characterised as a hybrid job shop scheduling problem with time window constraints. To solve this problem constructive algorithm and meta-heuristic scheduling techniques that operate upon a disjunctive graph model of train operations are utilised. From numerical investigations the proposed framework and associated techniques are tested and shown to be effective.     

京张高铁自动驾驶列车技术规章适应分析与制修订建议研究

自动驾驶列车是京张高铁智能化的一个重要体现,该项智能技术设备的运用对既有行车组织、设备维修、旅客服务等方面产生了较大的影响。为充分发挥智能设备的先进功能,需要与之相配套的技术规章体系。本文研究智能驾驶技术对行车组织、设备维修、旅客服务等方面的影响,分析既有相关技术规章的适应性,并从自动驾驶技术设备运用、管理、维修的角度出发,提出技术规章制修订的建议。论文的研究为京张高铁自动驾驶智能设备的运用提供保障,也为智能京张的技术规章体系构建提供技术支撑。     

Passenger Perspectives in Railway Timetabling: A Literature Review

When looking at railway planning, a discrepancy exists between planners who focus on the train operations and publish fixed railway schedules, and passengers who look not only at the schedules but also at the entirety of their trip, from access to waiting to on-board travel and egress. Looking into this discrepancy is essential, as assessing railway performances by merely measuring train punctuality would provide an unfair picture of the level of service experienced by passengers. Firstly, passengers’ delays are often significantly larger than the train delays responsible for the passengers to be late. Secondly, trains’ punctuality is often strictly related to too tight schedules that in turn might translate into knock-on delays for longer dwelling times at stations, trip delays for increased risk of missing transfer connections, and uncertain assessment of the level of service experienced, especially with fluctuating passenger demand. A key aspect is the robustness of railway timetables. Empirical evidence indicates that passengers give more importance to travel time certainty than travel time reductions, as passengers associate an inherent disutility with travel time uncertainty. This disutility may be broadly interpreted as an anxiety cost for the need for having contingency plans in case of disruptions, and may be looked at as the motivator for the need for delay-robust railway timetables. Interestingly, passenger-oriented optimisation studies considering robustness in railway planning typically limit their emphasis on passengers to the consideration of transfer maintenance. Clearly, passengers’ travel behaviour is far more complex and multi-faceted and thus several other aspects should be considered, as becoming more and more evident from passenger surveys. The current literature review starts by looking at the parameters that railway optimisation/planning studies are focused on and the key performance indicators that impact railway planning. The attention then turns to the parameters influencing passengers’ perceptions and travel experiences. Finally, the review proposes guidelines on how to reduce the gap between the operators’ railway planning and performance measurement on the one hand and the passengers’ perception of the railway performance on the other hand. Thereby, the conclusions create a foundation for a more passenger-oriented railway timetabling ensuring that passengers are provided with the best service possible with the resources available.     

Macroscopic multiple-station short-turning model in case of complete railway blockages

In case of railway disruptions, traffic controllers are responsible for dealing with disrupted traffic and reduce the negative impact for the rest of the network. In case of a complete blockage when no train can use an entire track, a common practice is to short-turn trains. Trains approaching the blockage cannot proceed according to their original plans and have to short-turn at a station close to the disruption on both sides. This paper presents a Mixed Integer Linear Program that computes the optimal station and times for short-turning the affected train services during the three phases of a disruption. The proposed solution approach takes into account the interaction of the traffic between both sides of the blockage before and after the disruption. The model is applied to a busy corridor of the Dutch railway network. The computation time meets the real-time solution requirement. The case study gives insight into the importance of the disruption period in computing the optimal solution. It is concluded that different optimal short-turning solutions may exist depending on the start time of the disruption and the disruption length. For periodic timetables, the optimal short-turning choices repeat due to the periodicity of the timetable. In addition, it is observed that a minor extension of the disruption length may result in less delay propagation at the cost of more cancellations.     

Single track line capacity model

The objective of the research described in this paper was to develop a model for computation of an ultimate capacity of a single track line and to provide a sensitivity analysis of this capacity to the parameters which influence it. The model is based in a concept of mathematical expectation of capacity and can be applied under saturation conditions i.e. a constant demand for service. It can serve for planning purposes, computation of single track line capacity on the base of which estimations are possible concerning a single track line performance under given conditions, as well as commercial time‐tables planning, decisions about a partial or complete construction of the second parallel track along the line in service, intermediate stations locations planning and the necessary facilities along the line under construction.

In the sensitivity analysis, the model allows a change of parameters upon which the capacity depends. These are: the length of the line segment which is considered to be bottleneck for calculation of capacity, traffic distributions per directions, train mix, train velocities and train spacing rules applied by the dispatching service when regulating the traffic on a line.     

A proposal for cost-related and market-oriented train running charges

This paper examines some key aspects of a charging system for promoting railway transport, including charges reflecting a clear relationship with costs (transparency) and charges reflecting the quality of the infrastructure manager's service. Train running charges recover track-related costs and can help to develop a charging system that meets these requirements. To orient train running charges to the market, a method for processing track maintenance and renewal costs is proposed whereby the quality of the service provided by an infrastructure is measured according to its utility to the railway undertaking. To achieve transparency, a single indicator is used for cost planning and the subsequent levying of costs on railway undertakings. The paper includes an example of how proposed train running charges would be calculated according to data from 14 European countries. The example shows that short-distance trains generate the lowest maintenance and renewal costs, followed by long-distance trains and freight trains.     

ARTEMIS: French-German project for railway movements command and control

The development of railway transportation, especially through the gradual implementation of high-speed European network, is inciting railway companies to design railway movements command and control systems to enhance technical performance in terms of throughput and control of disturbances while simultaneously minimizing operational costs. The new command-control systems must be modular, adaptable and evolutive structures from both functional and geographical viewpoints if they are to satisfy all operational needs. Concurrent research into performance enhancement and cost reduction prescribes a system in which the majority of the “real time” components are aboards the locomotives. This is particularly true for those components used by the train to indicate its own position on the network as well as those enabling it to converse with operational control centers. The initial task is to design a global architecture of the command-control system that satisfies modularity and availability criteria followed by the development of numerous technical components including radar self-location systems and cellular radio transmission networks. The French (SNCF) and German (DB) national railways have implemented a vast program of co-operation aimed at providing valid, proven answers to these problems so as to allow their trains to travel freely on either network.     

Robust stop-skipping patterns in urban railway operations under traffic alteration situation

In this paper an operation mode which is based on the stop-skipping approach is studied in urban railway lines under uncertainty. In this mode, each train follows a specific stop schedule. Trains are allowed to skip any intermediate stations to increase the commercial speed and to save energy consumption. As the commercial speed increases, the number of required trains in operation reduces and results eliminating unnecessary costs. To that end, a new mathematical model is proposed to reach the optimum stop schedule patterns. In the planning step, based on the traffic studies, the headway distributions are computed for different weekdays, and holidays. However, in practice, because of many unexpected events, the traffic may alter from what is planned. Therefore, in this condition, a robust plan is required that is optimized and immunized from uncertainty. In this paper, a new robust mathematical model, as well as two heuristic algorithms including (1) a decomposition-based algorithm and (2) a Simulated Annealing (SA) based algorithm is proposed. Finally, an Iranian metro line is studied and the optimum patterns are presented and analyzed.     

站城融合理念下高铁客运枢纽区域步行交通布置研究

本文对高铁客运枢纽区域内步行交通的影响范围和功能定位进行分析,提出在站城融合理念下,步行交通是高铁客运枢纽最重要的交通方式。利用开源数据,对比我国京沪高铁沿线与日本东海道新干线,以及北京南站、上海虹桥站、东京站、名古屋站,分析枢纽步行交通的影响因素,并提出站城融合背景下枢纽步行交通系统的规划建设重点和指标体系,为高铁客运枢纽实现站城融合、建立完善的步行交通系统提供参考。     

A comparison of modelled and real-life driving profiles for the simulation of railway vehicle operation

A key factor in determining the performance of a railway system is the speed profile of the trains within the network. There can be significant variation in this speed profile for identical trains on identical routes, depending on how the train is driven. A better understanding and control of speed profiles can therefore offer significant potential for improvements in the performance of railway systems. This paper develops a model to allow the variability of real-life driving profiles of railway vehicles to be quantitatively described and predicted, in order to better account for the effects on the speed profile of the train and hence the performance of the railway network as a whole. The model is validated against data from the Tyne and Wear Metro, and replicates the measured data to a good degree of accuracy.     

Reinforcement learning approach for train rescheduling on a single-track railway

Optimal rail network infrastructure and rolling stock utilization can be achieved with use of different scheduling tools by extensive planning a long time before actual operations. The initial train timetable takes into account possible smaller disturbances, which can be compensated within the schedule. Bigger disruptions, such as accidents, rolling stock breakdown, prolonged passenger boarding, and changed speed limit cause delays that require train rescheduling. In this paper, we introduce a train rescheduling method based on reinforcement learning, and more specifically, Q-learning. We present here the Q-learning principles for train rescheduling, which consist of a learning agent and its actions, environment and its states, as well as rewards. The use of the proposed approach is first illustrated on a simple rescheduling problem comprising a single-lane track with three trains. The evaluation of the approach is performed on extensive set of experiments carried out on a real-world railway network in Slovenia. The empirical results show that Q-learning lead to rescheduling solutions that are at least equivalent and often superior to those of several basic rescheduling methods that do not rely on learning agents. The solutions are learned within reasonable computational time, a crucial factor for real-time applications.     

Ant colony optimization for the real-time train routing selection problem

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.     

Assessing the usage and level-of-service of pedestrian facilities in train stations: A Swiss case study

A framework for assessing the usage and level-of-service of rail access facilities is presented. It consists of two parts. A dynamic demand estimator allows to obtain time-dependent pedestrian origin–destination demand within walking facilities. Using that demand, a traffic assignment model describes the propagation of pedestrians through the station, providing an estimate of prevalent traffic conditions in terms of flow, walking times, speed and density. The corresponding level-of-service of the facilities can be directly obtained. The framework is discussed at the example of Lausanne railway station. For this train station, a rich set of data sources including travel surveys, pedestrian counts and trajectories has been collected in collaboration with the Swiss Federal Railways. Results show a good performance of the framework. To underline its practical applicability, a six-step planning guideline is presented that can be used to design and optimize rail access facilities for new or existing train stations. In the long term, the framework may also be used for crowd management, involving real-time monitoring and control of pedestrian flows.     

Recent success stories on integrated optimization of railway systems

Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.