Multiple-phase train trajectory optimization with signalling and operational constraints

The train trajectory optimization problem aims at finding the optimal speed profiles and control regimes for a safe, punctual, comfortable, and energy-efficient train operation. This paper studies the train trajectory optimization problem with consideration of general operational constraints as well as signalling constraints. Operational constraints refer to time and speed restrictions from the actual timetable, while signalling constraints refer to the influences of signal aspects and automatic train protection on train operation. A railway timetable provides each train with a train path envelope, which consists of a set of positions on the route with a specified target time and speed point or window. The train trajectory optimization problem is formulated as a multiple-phase optimal control model and solved by a pseudospectral method. This model is able to capture varying gradients and speed limits, as well as time and speed constraints from the train path envelope. Train trajectory calculation methods under delay and no-delay situations are discussed. When the train follows the planned timetable, the train trajectory calculation aims at minimizing energy consumption, whereas in the case of delays the train trajectory is re-calculated to track the possibly adjusted timetable with the aim of minimizing delays as well as energy consumption. Moreover, the train operation could be affected by yellow or red signals, which is taken into account in the train speed regulation. For this purpose, two optimization policies are developed with either limited or full information of the train ahead. A local signal response policy ensures that the train makes correct and quick responses to different signalling aspects, while a global green wave policy aims at avoiding yellow signals and thus proceed with all green signals. The method is applied in a case study of two successive trains running on a corridor with various delays showing the benefit of accurate predictive information of the leading train on energy consumption and train delay of the following train.     

An integrated metro operation optimization to minimize energy consumption

Energy efficient techniques are receiving increasing attention because of rising energy prices and environmental concerns. Railways, along with other transport modes, are facing increasing pressure to provide more intelligent and efficient power management strategies.This paper presents an integrated optimization method for metro operation to minimize whole day substation energy consumption by calculating the most appropriate train trajectory (driving speed profile) and timetable configuration. A train trajectory optimization algorithm and timetable optimization algorithm are developed specifically for the study. The train operation performance is affected by a number of different systems that are closely interlinked. Therefore, an integrated optimization process is introduced to obtain the optimal results accurately and efficiently.The results show that, by using the optimal train trajectory and timetable, the substation energy consumption and load can be significantly reduced, thereby improving the system performance and stability. This also has the effect of reducing substation investment costs for new metros.     

Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).     

Optimizing train operational plan in an urban rail corridor based on the maximum headway function

The train operational plan (TOP) plays a crucial role in the efficient and effective operation of an urban rail system. We optimize the train operational plan in a special network layout, an urban rail corridor with one terminal yard, by decomposing it into two sub-problems, i.e., the train departure profile optimization and the rolling stock circulation optimization. The first sub-problem synthetically optimizes frequency setting, timetabling and the rolling stock circulation at the terminal without a yard. The maximum headway function is generated to ensure the service of the train operational plan without considering travel demand, then we present a model to minimize the number of train trips, and design a heuristic algorithm to maximize the train headway. On the basis of a given timetable, the rolling stock circulation optimization only involves the terminal with a yard. We propose a model to minimize the number of trains and yard–station runs, and an algorithm to find the optimal assignment of train-trip pair connections is designed. The computational complexities of the two algorithms are both linear. Finally, a real case study shows that the train operational plan developed by our approach enables a better match of train headway and travel demand, and reduces the operational cost while satisfying the requirement of the level of service.     

Integrating capacity analysis with high-speed railway timetabling: A minimum cycle time calculation model with flexible overtaking constraints and intelligent enumeration

Compared with most optimization methods for capacity evaluation, integrating capacity analysis with timetabling can reveal the types of train line plans and operating rules that have a positive influence on improving capacity utilization as well as yielding more accurate analyses. For most capacity analyses and cyclic timetabling methods, the cycle time is a constant (e.g., one or two hours). In this paper, we propose a minimum cycle time calculation (MCTC) model based on the periodic event scheduling problem (PESP) for a given train line plan, which is promising for macroscopic train timetabling and capacity analysis. In accordance with train operating rules, a non-collision constraint and a series of flexible overtaking constraints (FOCs) are constructed based on variations of the original binary variables in the PESP. Because of the complexity of the PESP, an iterative approximation (IA) method for integration with the CPLEX solver is proposed. Finally, two hypothetical cases are considered to analyze railway capacity, and several influencing factors are studied, including train regularity, train speed, line plan specifications (train stops), overtaking and train heterogeneity. The MCTC model and IA method are used to test a real-world case involving the timetable of the Beijing–Shanghai high-speed railway in China.     

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.     

A three-level framework for performance-based railway timetabling

The performance of railway operations depends highly on the quality of the railway timetable. In particular for dense railway networks it can be challenging to obtain a stable robust conflict-free and energy-efficient timetable with acceptable infrastructure occupation and short journey times. This paper presents a performance-based railway timetabling framework integrating timetable construction and evaluation on three levels: microscopic, macroscopic, and a corridor fine-tuning level, where each performance indicator is optimized or evaluated at the appropriate level. A modular implementation of the three-level framework is presented and demonstrated on a case study on the Dutch railway network illustrating the feasibility of this approach to achieve the highest timetabling design level.     

A multiobjective planning model for intercity train seat allocation

This paper presents a multiobjective planning model for generating optimal train seat allocation plans on an intercity rail line serving passengers with many‐to‐many origin‐destination pairs. Two planning objectives of the model are to maximise the operator's total passenger revenue and to minimise the passenger's total discomfort level. For a given set of travel demand, train capacity, and train stop‐schedules, the model is solved by fuzzy mathematical programming to generate a best‐compromise train seat allocation plan. The plan determines how many reserved and non‐reserved seats are to be allocated at each origin station for all subsequent destination stations on each train run operated within a specified operating period. An empirical study on the to‐be‐built Taiwan's high‐speed rail system is conducted to demonstrate the effectiveness of the model. The model can be used for any setting of travel demand and stop‐schedules with various train seating capacities.     

Real-time automatic rescheduling strategy for an urban rail line by integrating the information of fault handling

In the operation of urban rails, faults are inevitable, which leads to deviation between the actual timetable and the planned timetable. In nowadays, timetable rescheduling strategies rarely integrate the information of fault handling. In this paper, we develop a real-time automatic rescheduling strategy, which integrates the dynamic information of fault handling. The rescheduled timetable is obtained by a mathematical optimization model, the constraints set of which is automatically generated and adjusted as more information of fault handling is feedback. Compared with the experience-based rescheduling methods, the automatic rescheduling strategy reacts more quickly, and uses the information of fault handling more efficiently. A simulation system for testing the automatic rescheduling strategy is built, which uses the data of the Beijing Yizhuang metro line. Via testing on the simulation system, the effectiveness and efficiency of the automatic rescheduling strategy are validated.     

A hierarchical line planning approach for a large-scale high speed rail network: The China case

Planning a set of train lines in a large-scale high speed rail (HSR) network is typically influenced by issues of longer travel distance, high transport demand, track capacity constraints, and a non-periodic timetable. In this paper, we describe an integrated hierarchical approach to determine line plans by defining the stations and trains according to two classes. Based on a bi-level programming model, heuristics are developed for two consecutive stages corresponding to each classification. The approach determines day-period based train line frequencies as well as a combination of various stopping patterns for a mix of fast trunk line services between major stations and a variety of slower body lines that offer service to intermediate stations, so as to satisfy the predicted passenger transport demand. Efficiencies of the line plans described herein concern passenger travel times, train capacity occupancy, and the number of transfers. Moreover, our heuristics allow for combining many additional conflicting demand–supply factors to design a line plan with predominantly cost-oriented and/or customer-oriented objectives. A range of scenarios are developed to generate three line plans for a real-world example of the HSR network in China using a decision support system. The performance of potential train schedules is evaluated to further examine the feasibility of the obtained line plans through graphical timetables.     

High-Speed Rail Operations on an Existing Network: An Assessment Model for China

High-speed rail operations have the potential to reduce the long-term decline in rail passenger travel demand for the medium to long distance inter-urban markets. Such decline has been evident through most of the industrialized countries where air and road transport tend to be the dominant modes. In China, the operations of long distance high-speed rail on fully dedicated track is not very easy to implement, due to the high proportion of passengers who travel between high-speed and conventional railways. An alternative approach would be to allow for mixed operations with trains of various speeds on the same track. This article puts forward a simulation model designed to allow an evaluation of the most efficient distance for high-speed rail operations under mixed train speed scenarios. The model takes into account the main operating parameters such as passenger volumes, train speeds, capital and maintenance costs, train operating costs and energy consumption. The distance of high-speed train running on conventional rail that will yield the most economic benefit can be estimated using the model. The article includes the results of using the model for a specific example. It is concluded that large-scale high-speed trains have the potential to be successfully operated on conventional rail networks.     

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.     

Train routing and timetabling problem for heterogeneous train traffic with switchable scheduling rules

This paper proposes a mathematical model for the train routing and timetabling problem that allows a train to occasionally switch to the opposite track when it is not occupied, which we define it as switchable scheduling rule. The layouts of stations are taken into account in the proposed mathematical model to avoid head-on and rear-end collisions in stations. In this paper, train timetable could be scheduled by three different scheduling rules, i.e., no switchable scheduling rule (No-SSR) which allows trains switching track neither at stations and segments, incomplete switchable scheduling rule (In-SSR) which allows trains switching track at stations but not at segments, and complete switchable scheduling rule (Co-SSR) which allows trains switching track both at stations and segments. Numerical experiments are carried out on a small-scale railway corridor and a large-scale railway corridor based on Beijing–Shanghai high-speed railway (HSR) corridor respectively. The results of case studies indicate that Co-SSR outperforms the other two scheduling rules. It is also found that the proposed model can improve train operational efficiency.     

Strategic assessment of capacity consumption in railway networks: Framework and model

In this paper, we develop a new framework for strategic planning purposes to calculate railway infrastructure occupation and capacity consumption in networks, independent of a timetable. Furthermore, a model implementing the framework is presented. In this model different train sequences are generated and assessed to obtain timetable independence. A stochastic simulation of delays is used to obtain the capacity consumption. The model is tested on a case network where four different infrastructure scenarios are considered. Both infrastructure occupation and capacity consumption results are obtained efficiently with little input. The case illustrates the model’s ability to quantify the capacity gain from infrastructure scenario to infrastructure scenario which can be used to increase the number of trains or improve the robustness of the system.     

An integrated micro–macro approach to robust railway timetabling

With the increasing demand for railway transportation infrastructure managers need improved automatic timetabling tools that provide feasible timetables with enhanced performance in short computation times. This paper proposes a hierarchical framework for timetable design which combines a microscopic and a macroscopic model of the network. The framework performs an iterative adjustment of train running and minimum headway times until a feasible and stable timetable has been generated at the microscopic level. The macroscopic model optimizes a trade-off between minimal travel times and maximal robustness using an Integer Linear Programming formulation which includes a measure for delay recovery computed by an integrated delay propagation model in a Monte Carlo setting. The application to an area of the Dutch railway network shows the ability of the approach to automatically compute a feasible, stable and robust timetable. Practitioners can use this approach both for effective timetabling and post-evaluation of existing timetables.     

Real-time energy consumption minimization in railway networks

A new timetable must be calculated in real-time when train operations are perturbed. Although energy consumption is becoming a central issue both from the environmental and economic perspective, it is usually neglected in the timetable recalculation. In this paper, we formalize the real-time Energy Consumption Minimization Problem (rtECMP). It finds in real-time the driving regime combination for each train that minimizes energy consumption, respecting given routing and precedences between trains. In the possible driving regime combinations, train routes are split in subsections for which one of the regimes resulting from the Pontryagin’s Maximum Principle is to be chosen. We model the trade-off between minimizing energy consumption and total delay by considering as objective function their weighted sum. We propose an algorithm to solve the rtECMP, based on the solution of a mixed-integer linear programming model. We test this algorithm on the Pierrefitte-Gonesse control area, which is a critical area in France with dense mixed traffic. The results show that the problem is tractable and an optimal solution of the model tackled can often be found in real-time for most instances.     

A bi-level model for single-line rail timetable design with consideration of demand and capacity

This paper proposes a bi-level model to solve the timetable design problem for an urban rail line. The upper level model aims at determining the headways between trains to minimize total passenger cost, which includes not only the usual perceived travel time cost, but also penalties during travel. With the headways given by the upper level model, passengers’ arrival times at their origin stops are determined by the lower level model, in which the cost-minimizing behavior of each passenger is taken into account. To make the model more realistic, explicit capacity constraints of individual trains are considered. With these constraints, passengers cannot board a full train, but wait in queues for the next coming train. A two-stage genetic algorithm incorporating the method of successive averages is introduced to solve the bi-level model. Two hypothetical examples and a real world case are employed to evaluate the effectiveness of the proposed bi-level model and algorithm. Results show that the bi-level model performs well in reducing total passenger cost, especially in reducing waiting time cost and penalties. And the section loading-rates of trains in the optimized timetable are more balanced than the even-headway timetable. The sensitivity analyses show that passenger’s desired arrival time interval at destination and crowding penalty factor have a high influence on the optimal solution. And with the dispersing of passengers' desired arrival time intervals or the increase of crowding penalty factor, the section loading-rates of trains become more balanced.     

A G/G(n)/C/C state‐dependent simulation model for metro station corridor width design

Metro station corridor and passengers are described as a G/G(n)/C/C state‐dependent queuing system with a general random arrival interval G and a general random and state‐dependent service time G(n) to offset the shortcomings in existing design methods. The corresponding G/G(n)/C/C state‐dependent discrete event simulation model is developed, and its high‐fidelity is tested. Then the optimization algorithm based on the simulation model is designed to determine corridor width. The proposed simulation optimization method and the existing analytical optimization methods, based on M/G(n)/C/C and D/D/1/C queuing models, are applied to design corridor width in a numerical example of 48 combinations of passenger flow rates and level of service (LOS). The designed corridor widths are tested in a micro‐simulation model, and the performance measure is compared. The result shows that the corridor widths obtained by the new method are 0.357 m (7.4%) larger than that of the other two methods on average; the area per passenger of the new method increases 10.53% and 11.63%, respectively, compared with that of the other two methods; the widths designed by the new method satisfy the requirement of LOS under various passenger flows, whereas 93% of the corridor widths obtained by the other two methods fail to meet the requirement of LOS, and the corridor widths designed by the new method have high elasticity coefficients of LOS‐width. Copyright © 2015 John Wiley & Sons, Ltd.     

Improving recovery-to-optimality robustness through efficiency-balanced design of timetable structure

To improve the service quality of the railway system (e.g., punctuality and travel times) and to enhance the robust timetabling methods further, this paper proposes an integrated two-stage approach to consider the recovery-to-optimality robustness into the optimized timetable design without predefined structure information (defined as flexible structure) such as initial departure times, overtaking stations, train order and buffer time. The first-stage timetabling model performs an iterative adjustment of all departure and arrival times to generate an optimal timetable with balanced efficiency and recovery-to-optimality robustness. The second-stage dispatching model evaluates the recovery-to-optimality robustness by simulating how each timetable generated from the first-stage could recover under a set of restricted scenarios of disturbances using the proposed dispatching algorithm. The concept of recovery-to-optimality is examined carefully for each timetable by selecting a set of optimally refined dispatching schedules with minimum recovery cost under each scenario of disturbance. The robustness evaluation process enables an updating of the timetable by using the generated dispatching schedules. Case studies were conducted in a railway corridor as a special case of a simple railway network to verify the effectiveness of the proposed approach. The results show that the proposed approach can effectively attain a good trade-off between the timetable efficiency and obtainable robustness for practical applications.