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.     

A stochastic model for the integrated optimization on metro timetable and speed profile with uncertain train mass

The integrated timetable and speed profile optimization model has recently attracted more attention because of its good achievements on energy conservation in metro systems. However, most previous studies often ignore the spatial and temporal uncertainties of train mass, and the variabilities of tractive force, braking force and basic running resistance on energy consumption in order to simplify the model formulation and solution algorithm. In this paper, we develop an integrated metro timetable and speed profile optimization model to minimize the total tractive energy consumption, where these real-world operating conditions are explicitly considered in the model formulation and solution algorithm. Firstly, we formulate a two-phase stochastic programming model to determine the timetable and speed profile. Given the speed profile, the first phase determines the timetable by scheduling the arrival and departure times for each station, and the second phase determines the speed profile for each inter-station with the scheduled arrival and departure times. Secondly, we design a simulation-based genetic algorithm procedure incorporated with the optimal train control algorithm to find the optimal solution. Finally, we present a simple example and a real-world example based on the operation data from the Beijing Metro Yizhuang Line in Beijing, China. The results of the real-world example show that, during peak hours, off-peak hours and night hours, the total tractive energy consumptions can be reduced by: (1) 10.66%, 9.94% and 9.13% in comparison with the current timetable and speed profile; and (2) 3.35%, 3.12% and 3.04% in comparison with the deterministic model.     

Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach

In a heavily congested metro line, unexpected disturbances often occur to cause the delay of the traveling passengers, infeasibility of the current timetable and reduction of the operational efficiency. Due to the uncertain and dynamic characteristics of passenger demands, the commonly used method to recover from disturbances in practice is to change the timetable and rolling stock manually based on the experiences and professional judgements. In this paper, we develop a stochastic programming model for metro train rescheduling problem in order to jointly reduce the time delay of affected passengers, their total traveling time and operational costs of trains. To capture the complexity of passenger traveling characteristics, the arriving ratio of passengers at each station is modeled as a non-homogeneous poisson distribution, in which the intensity function is treated as time-varying origin-to-destination passenger demand matrices. By considering the number of on-board passengers, the total energy usage is modeled as the difference between the tractive energy consumption and the regenerative energy. Then, we design an approximate dynamic programming based algorithm to solve the proposed model, which can obtain a high-quality solution in a short time. Finally, numerical examples with real-world data sets are implemented to verify the effectiveness and robustness of the proposed approaches.     

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.     

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.     

Balancing energy consumption and risk of delay in high speed trains: A three-objective real-time eco-driving algorithm with fuzzy parameters

Eco-driving is an energy efficient traffic operation measure that may lead to important energy savings in high speed railway lines. When a delay arises in real time, it is necessary to recalculate an optimal driving that must be energy efficient and computationally efficient.In addition, it is important that the algorithm includes the existing uncertainty associated with the manual execution of the driving parameters and with the possible future traffic disturbances that could lead to new delays.This paper proposes a new algorithm to be executed in real time, which models the uncertainty in manual driving by means of fuzzy numbers. It is a multi-objective optimization algorithm that includes the classical objectives in literature, running time and energy consumption, and as well a newly defined objective, the risk of delay in arrival. The risk of delay in arrival measure is based on the evolution of the time margin of the train up to destination.The proposed approach is a dynamic algorithm designed to improve the computational time. The optimal Pareto front is continuously tracked during the train travel, and a new set of driving commands is selected and presented to the driver when a delay is detected.The algorithm evaluates the 3 objectives of each solution using a detailed simulator of high speed trains to ensure that solutions are realistic, accurate and applicable by the driver. The use of this algorithm provides energy savings and, in addition, it permits railway operators to balance energy consumption and risk of delays in arrival. This way, the energy performance of the system is improved without degrading the quality of the service.     

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.     

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

An energy-efficient scheduling approach to improve the utilization of regenerative energy for metro systems

Regenerative braking is an energy recovery mechanism that converts the kinetic energy during braking into electricity, also known as regenerative energy. In general, most of the regenerative energy is transmitted backward along the pantograph and fed back into the overhead contact line. To reduce the trains’ energy consumption, this paper develops a scheduling approach to coordinate the arrivals and departures of all trains located in the same electricity supply interval so that the energy regenerated from braking trains can be more effectively utilized to accelerate trains. Firstly, we formulate an integer programming model with real-world speed profiles to minimize the trains’ energy consumption with dwell time control. Secondly, we design a genetic algorithm and an allocation algorithm to find a good solution. Finally, we present numerical examples based on the real-life operation data from the Beijing Metro Yizhuang Line in Beijing, China. The results show that the proposed scheduling approach can reduce energy consumption by 6.97% and save about 1,054,388 CNY (or 169,223 USD) each year in comparison with the current timetable. Compared to the cooperative scheduling (CS) approach, the proposed scheduling approach can improve the utilization of regenerative energy by 36.16% and reduce the total energy consumption by 4.28%.     

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.     

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.     

Automated real-time railway traffic control: an experimental analysis of reliability,resilience and robustness

Railway transportation provides sustainable, fast and safe transport. Its attractiveness is linked to a broad concept of service reliability: the capability to adhere to a timetable in the presence of delays perturbing traffic. To counter these phenomena, real-time rescheduling can be used, changing train orders and times, according to rules of thumb, or mathematical optimization models, minimizing delays or maximizing punctuality. In the literature, different indices of robustness, reliability and resilience are defined for railway traffic. We review and evaluate these indices applied to railway traffic control, comparing optimal rescheduling approaches such as Open Loop and Closed Loop control, to a typical First-Come-First-Served dispatching rule, and following the timetable (no-action). This experimental analysis clarifies the benefits of automated traffic control for infrastructure managers, railway operators and passengers. The timetable order, normally used in assessing a-priori reliability, systematically overestimates unreliability of operations that can be reduced by real-time control.     

Multi-objective re-synchronizing of bus timetable: Model,complexity and solution

This work is originally motived by the re-planning of a bus network timetable. The existing timetable with even headways for the network is generated using line by line timetabling approach without considering the interactions between lines. Decision-makers (i.e., schedulers) intend to synchronize vehicle timetable of lines at transfer nodes to facilitate passenger transfers while being concerned with the impacts of re-designed timetable on the regularity of existing timetable and the accustomed trip plans of passengers. Regarding this situation, we investigate a multi-objective re-synchronizing of bus timetable (MSBT) problem, which is characterized by headway-sensitive passenger demand, uneven headways, service regularity, flexible synchronization and involvement of existing bus timetable. A multi-objective optimization model for the MSBT is proposed to make a trade-off between the total number of passengers benefited by smooth transfers and the maximal deviation from the departure times of the existing timetable. By clarifying the mathematical properties and solution space of the model, we prove that the MSBT problem is NP-hard, and its Pareto-optimal front is non-convex. Therefore, we design a non-dominated sorting genetic (NSGA-II) based algorithm to solve this problem. Numerical experiments show that the designed algorithm, compared with enumeration method, can generate high-quality Pareto solutions within reasonable times. We also find that the timetable allowing larger flexibility of headways can obtain more and better Pareto-optimal solutions, which can provide decision-makers more choice.     

Energy-efficient operation of rail vehicles

This paper describes an analytical process that computes the optimal operating successions of a rail vehicle to minimize energy consumption. Rising energy prices and environmental concerns have made energy conservation a high priority for transportation operations. The cost of energy consumption makes up a large portion of the Operation and Maintenance (O&M) costs of transit especially rail transit systems. Energy conservation or reduction in energy cost may be one of the effective ways to reduce transit operating cost, therefore improve the efficiency of transit operations.From a theoretical point of view, the problem of energy efficient train control can be formulated as one of the functions of Optimal Control Theory. However, the classic numerical optimization methods such as discrete method of optimum programming are too slow to be used in an on-board computer even with the much improved computation power, today. The contribution of this particular research is the analytical solution that gives the sequence of optimal controls and equations to find the control change points. As a result, a calculation algorithm and a computer program for energy efficient train control has been developed. This program is also capable of developing energy efficient operating schedules by optimizing distributions of running time for an entire route or any part of rail systems.We see the major application of the proposed algorithms in fully or partially automated Train Control Systems. The modern train control systems, often referred as “positive” train control (PTC), have collected a large amount of information to ensure safety of train operations. The same data can be utilized to compute the optimum controls on-board to minimize energy consumption based on the algorithms proposed in this paper. Most of the input data, such as track plan, track profile, traction and braking characteristics, speed limits and required trip time are located in an on-board database and/or they can be transmitted via radio link to be processed by the proposed algorithm and program.     

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.     

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 constraint generation algorithm for the construction of periodic railway timetables

This paper addresses the problem of constructing periodic timetables for train operations. We use a mathematical model consisting of periodic time window constraints by means of which arrival and departure times can be related pairwise on a clock, rather than on a linear time axis. Constructing a timetable, then, means solving a set of such constraints. This problem is known to be hard, i.e. it is NP-complete. We describe a new algorithm to solve the problem based on constraint generation and work out a real-life example. It appears that, for problem instances of modest, yet non-trivial, size, the algorithm performs very well, which opens a way to thorough performance analysis of railway systems by studying a large number of possible future timetables.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

Demand-driven timetable design for metro services

Timetable design is crucial to the metro service reliability. A straightforward and commonly adopted strategy in daily operation is a peak/off-peak-based schedule. However, such a strategy may fail to meet dynamic temporal passenger demand, resulting in long passenger waiting time at platforms and over-crowding in trains. Thanks to the emergence of smart card-based automated fare collection systems, we can now better quantify spatial–temporal demand on a microscopic level. In this paper, we formulate three optimization models to design demand-sensitive timetables by demonstrating train operation using equivalent time (interval). The first model aims at making the timetable more dynamic; the second model is an extension allowing for capacity constraints. The third model aims at designing a capacitated demand-sensitive peak/off-peak timetable. We assessed the performance of these three models and conducted sensitivity analyzes on different parameters on a metro line in Singapore, finding that dynamical timetable built with capacity constraints is most advantageous. Finally, we conclude our study and discuss the implications of the three models: the capacitated model provides a timetable which shows best performance under fixed capacity constraints, while the uncapacitated model may offer optimal temporal train configuration. Although we imposed capacity constraints when designing the optimal peak/off-peak timetable, its performance is not as good as models with dynamical headways. However, it shows advantages such as being easier to operate and more understandable to the passengers.     

Passenger oriented railway disruption management by adapting timetables and rolling stock schedules

In passenger railway operations, unforeseen events require railway operators to adjust their timetable and their resource schedules. The passengers will also adapt their routes to their destinations. When determining the new timetable and rolling stock schedule, the railway operator has to take passenger behavior into account. The operator should increase the capacity of trains for which the operator expects more demand than on a regular day. Furthermore, the operator could increase the frequency of the trains that serve stations with an additional demand.This paper describes a real-time disruption management approach which integrates the rescheduling of the rolling stock and the timetable by taking the changed passenger demand into account. The timetable decisions are limited to additional stops of trains at stations at which they normally would not call. Several variants of the approach are suggested, with the difference in how to determine which additional stops should be executed.Real-time rescheduling requires fast solutions. Therefore a heuristic approach is used. We demonstrate the performance of the several variants of our algorithm on realistic instances of Netherlands Railways, the major railway operator in the Netherlands.