The key principles of optimal train control—Part 2: Existence of an optimal strategy,the local energy minimization principle,uniqueness, computational techniques

We discuss the problem of finding an energy-efficient driving strategy for a train journey on an undulating track with steep grades subject to a maximum prescribed journey time. In Part 1 of this paper we reviewed the state-of-the-art and established the key principles of optimal train control for a general model with continuous control. We assumed only that the tractive and braking control forces were bounded by non-increasing speed-dependent magnitude constraints and that the rate of energy dissipation from frictional resistance was given by a non-negative strictly convex function of speed. Partial cost recovery from regenerative braking was allowed. Our aim was to minimize the mechanical energy required to drive the train. We examined the characteristic optimal control modes, studied allowable control transitions and established the existence of optimal switching points. We found algebraic formulae for the adjoint variables in terms of speed on track with piecewise-constant gradient and drew phase plots of the associated optimal evolutionary lines for the state and adjoint variables. In Part 2 we will establish integral forms of the necessary conditions for optimal switching, find general bounds on the positions of the optimal switching points, justify an extended local energy minimization principle and show how these ideas can be used to calculate the optimal strategy. We prove that an optimal strategy always exists and use a perturbation analysis to show that the optimal strategy is unique. Finally we discuss computation of optimal switching points in two realistic examples with steep grades and describe the optimal control strategies and corresponding speed profiles for a complete journey with several different allowed journey times. In practice the strategies described here have been shown to reduce the costs of energy used by as much as 20%.     

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.     

The key principles of optimal train control—Part 1: Formulation of the model,strategies of optimal type,evolutionary lines,location of optimal switching points

We discuss the problem of finding an energy-efficient driving strategy for a train journey on an undulating track with steep grades subject to a maximum prescribed journey time. We review the state-of-the-art and establish the key principles of optimal train control for a general model with continuous control. The model with discrete control is not considered. We assume only that the tractive and braking control forces are bounded by non-increasing speed-dependent magnitude constraints and that the rate of energy dissipation from frictional resistance is given by a non-negative strictly convex function of speed. Partial cost recovery from regenerative braking is allowed. The cost of the strategy is the mechanical energy required to drive the train. Minimising the mechanical energy is an effective way of reducing the fuel or electrical energy used by the traction system. The paper is presented in two parts. In Part 1 we discuss formulation of the model, determine the characteristic optimal control modes, study allowable control transitions, establish the existence of optimal switching points and consider optimal strategies with speed limits. We find algebraic formulae for the adjoint variables in terms of speed on track with piecewise-constant gradient and draw phase plots of the associated optimal evolutionary lines for the state and adjoint variables. In Part 2 we will establish important integral forms of the necessary conditions for optimal switching, find general bounds on the positions of the optimal switching points, justify the local energy minimization principle and show how these ideas are used to calculate optimal switching points. We will prove that an optimal strategy always exists and use a perturbation analysis to show the strategy is unique. Finally we will discuss computational techniques in realistic examples with steep gradients and describe typical optimal strategies for a complete journey.     

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.     

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.     

Coordinated cruise control for high-speed train movements based on a multi-agent model

This paper investigates the coordinated cruise control strategy for multiple high-speed trains’ movement. The motion of an ordered set of high-speed trains running on a railway line is modeled by a multi-agent system, in which each train communicates with its neighboring trains to adjust its speed. By using the potential fields and LaSalles invariance principle, we design a new coordinated cruise control strategy for each train based on the neighboring trains’ information, under which each train can track the desired speed, and the headway distances between any two neighboring trains are stabilized in a safety range. Numerical examples are given to illustrate the effectiveness of the proposed methods.     

A simulation model of train travel on a rail transit line

A simplified simulation model for the operational analysis of a rail rapid transit train is presented. The model simulates the movement of a train along a route, and develops the relationships of time—distance, time—speed and distance—speed. The inputs to the model are the profile of speed limits and the dynamic characteristics of the train. Without the information on the track geometry and tractive effort, the model determines the speed of the train at a location based on the previous and future speed limits relative to the location. It was found that the model can fairly accurately simulate the relationship between travel time and distance. A comparison of the train travel times between the actual and simulated runs is presented. Because of the simplicity of input and calculation method, the model can be a useful tool for the “desk-top” analysis of frequently occurring planning problems of a commuter rail or rail rapid transit line, such as the impacts of changes in speed limits, station locations, station stopping policy, addition/elimination of stations, and types of rail cars.     

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

Reasonable scheduling for arrival–departure track operations in railway stations

We analyze the train types handled at a section station and the factors affecting the scheduling of the arrival–departure track operation, using the following conditions as our optimization goals: operating the arrival–departure tracks in accordance with a fixed operation scheme, and reducing the influence which the departing–receiving operations impose on shunting operations. We establish a 0–1 integer programming model for formulating a track operation plan. By applying modern sequencing theory, this is transformed into a fixed sequencing model of special parallel machines. We then design a heuristic algorithm to solve the model. Finally, the example of Yiyang railway station is used to verify the advantages of the model and the algorithm. A better operation plan is obtained using MATLAB 7.0 by applying the model and the algorithm provided in the paper, indicating the superiority of our study’s approach.     

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.     

Optimization of nonlinear control strategy for anti-lock braking system with improvement of vehicle directional stability on split-μ roads

In a hard braking on a split-μ road, the achievement of shorter stopping distance while maintaining the vehicle in the straight line are of great importance. In this paper, to achieve these conflicting aims, an optimal nonlinear algorithm based on the prediction of vehicle responses is presented to distribute the wheel braking forces properly. The base of this algorithm is reducing the maximum achievable braking forces of one side wheels, as low as possible, so that the minimum stabilizing yaw moment is produced. The optimal property of the proposed control method makes it possible to get a trade-off between the shorter stopping distance and the less deviation of the vehicle heading from the straight line. The special case of this algorithm leads to the conventional anti-lock braking system (ABS) which generates the maximum braking forces for all wheels to attain the minimum stopping distance. However, the ABS cannot control the vehicle directional stability directly. The simulation results carried out using a nonlinear 8-DOF vehicle model demonstrate that the designed control system has a suitable performance to attain the desired purposes compared with the convectional ABS.     

Scheduling and platforming trains at busy complex stations

We consider the problem of train planning or scheduling for large, busy, complex train stations, which are common in Europe and elsewhere, though not in North America. We develop the constraints and objectives for this problem, but these are too computationally complex to solve by standard combinatorial search or integer programming methods. Also, the problem is somewhat political in nature, that is, it does not have a clear objective function because it involves multiple train operators with conflicting interests. We therefore develop scheduling heuristics analogous to those successfully adopted by train planners using “manual” methods. We tested the model and algorithms by applying to a typical large station that exhibits most of the complexities found in practice. The results compare well with those found by traditional methods, and take account of cost and preference trade-offs not handled by those methods. With successive refinements, the algorithm eventually took only a few seconds to run, the time depending on the version of the algorithm and the scheduling problem. The scheduling models and algorithms developed and tested here can be used on their own, or as key components for a more general system for train scheduling for a rail line or network.Train scheduling for a busy station includes ensuring that there are no conflicts between several hundred trains per day going in and out of the station on intersecting paths from multiple in-lines and out-lines to multiple platforms, while ensuring that each train is allowed at least its minimum required headways, dwell time, turnaround time and trip time. This has to be done while minimizing (costs of) deviations from desired times, platforms or lines, allowing for conflicts due to through-platforms, dead-end platforms, multiple sub-platforms, and possible constraints due to infrastructure, safety or business policy.     

A new look at the rate of change of energy consumption with respect to journey time on an optimal train journey

We present a new derivation of a key formula for the rate of change of energy consumption with respect to journey time on an optimal train journey. We use a standard mathematical model (Albrecht et al., 2015b; Howlett, 2000; Howlett et al., 2009; Khmelnitsky, 2000; Liu and Golovitcher, 2003) to define the problem and show by explicit calculation of switching points that the formula also applies for all basic control subsequences within the optimal strategy on appropriately chosen fixed track segments. The rate of change was initially derived as a known strictly decreasing function of the optimal driving speed in a text edited by  Isayev (1987, Section 14.2, pp 259–260) using an empirical resistance function. An elegant derivation by Liu and Golovitcher (2003, Section 3) with a general resistance function required an underlying assumption that the optimal strategy is unique and that the associated optimal driving speed is a strictly decreasing and continuous function of journey time. An earlier proof of uniqueness (Khmelnitsky, 2000) showed that the optimal driving speed decreases when journey time increases. A subsequent constructive proof (Albrecht et al., 2013a, 2015c) used a local energy minimization principle to find optimal switching points and show explicitly that the optimal driving speed is a strictly decreasing and continuous function of journey time. Our new derivation of the key formula also uses the local energy minimization principle and depends on the following observations. If no speed limits are imposed the optimal strategy consists of a finite sequence of phases with only five permissible control modes. By considering all basic control subsequences and subdividing the track into suitably chosen fixed segments we show that the key formula is valid on each individual segment. The formula is extended to the entire journey by summation. The veracity of the formula is demonstrated with an elementary but realistic example.     

Surface prediction and control algorithms for anti-lock brake system

Anti-lock brake system (ABS) has been designed to achieve maximum deceleration by preventing the wheels from locking. The friction coefficient between tyre and road is a nonlinear function of slip ratio and varies for different road surfaces. In this paper, methods have been developed to predict these different surfaces and accordingly control the wheel slip to achieve maximum friction coefficient for different road surfaces. The surface prediction and control methods are based on a half car model to simulate high speed braking performance. The prediction methods have been compared with the results available in the literature. The results show the advantage of ABS with surface prediction as compared to ABS without proper surface identification. Finally, the performance of the controller developed in this paper has been compared with four different ABS control algorithms reported in the literature. The accuracy of prediction by the proposed methods is very high with error in prediction in a range of 0.17-2.4%. The stopping distance is reduced by more than 3% as a result of prediction for all surfaces.     

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.     

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.     

Characterising Green Light Optimal Speed Advisory trajectories for platoon-based optimisation

Conceptually, a Green Light Optimal Speed Advisory (GLOSA) system suggests speeds to vehicles, allowing them to pass through an intersection during the green interval. In previous papers, a single speed is computed for each vehicle in a range between acceptable minimum and maximum values (for example between standstill and the speed limit). This speed is assumed to be constant until the beginning of the green interval, and sent as advice to the vehicle. The goal is to optimise for a particular objective, whether it be minimisation of emissions (for environmental reasons), fuel usage or delay. This paper generalises the advice given to a vehicle, by optimising for delay over the entire trajectory instead of suggesting an individual speed, regardless of initial conditions – time until green, distance to intersection and initial speed. This may require multiple acceleration manoeuvres, so the advice is sent as a suggested acceleration at each time step. Such advice also takes into account a suitable safety constraint, ensuring that vehicles are always able to stop before the intersection during a red interval, thus safeguarding against last-minute signal control schedule changes. While the algorithms developed primarily minimise delay, they also help to reduce fuel usage and emissions by conserving kinetic energy. Since vehicles travel in platoons, the effectiveness of a GLOSA system is heavily reliant on correctly identifying the leading vehicle that is the first to be given trajectory advice for each cycle. Vehicles naturally form a platoon behind this leading vehicle. A time loop technique is proposed which allows accurate identification of the leader even when there are complex interactions between preceding vehicles. The developed algorithms are ideal for connected autonomous vehicle environments, because computer control allows vehicles’ trajectories to be managed with greater accuracy and ease. However, the advice algorithms can also be used in conjunction with manual control provided Vehicle-to-Infrastructure (V2I) communication is available.     

Scheduling freight trains traveling on complex networks

In the US, freight railways are one of the major means to transport goods from ports to inland destinations. According to the Association of American Railroad’s study, rail companies move more than 40% of the nation’s total freight. Given the fact that the freight railway industry is already running without much excess capacity, better planning and scheduling tools are needed to effectively manage the scarce resources, in order to cope with the rapidly increasing demand for railway transportation. This research develops optimization-based approaches for scheduling of freight trains. Two mathematical formulations of the scheduling problem are first introduced. One assumes the path of each train, which is the track segments each train uses, is given and the other one relaxes this assumption. Several heuristics based on mixtures of the two formulations are proposed. The proposed algorithms are able to outperform two existing heuristics, namely a simple look-ahead greedy heuristic and a global neighborhood search algorithm, in terms of railway total train delay. For large networks, two algorithms based on the idea of decomposition are developed and are shown to significantly outperform two existing algorithms.