مسیر بهینه برنامه ریزی برای قطار - روش طیفی کاذب و یک روش برنامه ریزی خطی عدد صحیح مختلط

The optimal trajectory planning problem for train operations under constraints and fixed arrival time is considered. The varying line resistance, variable speed restrictions, and varying maximum traction force are included in the problem definition. The objective function is a trade-off between the energy consumption and the riding comfort. Two approaches are proposed to solve this optimal control problem. First, we propose to use the pseudospectral method, a state-of-the-art method for optimal control problems, which has not used for train optimal control before. In the pseudospectral method, the optimal trajectory planning problem is recast into a multiple-phase optimal control problem, which is then transformed into a nonlinear programming problem. However, the calculation time for the pseudospectral method is too long for the real-time application in an automatic train operation system. To shorten the computation time, the optimal trajectory planning problem is reformulated as a mixed-integer linear programming (MILP) problem by approximating the nonlinear terms in the problem by piecewise affine functions. The MILP problem can be solved efficiently by existing solvers that guarantee to return the global optimum for the proposed MILP problem. Simulation results comparing the pseudospectral method, the new MILP approach, and a discrete dynamic programming approach show that the pseudospectral method has the best control performance, but that if the required computation time is also take into consideration, the MILP approach yields the best overall performance. More specifically, for the given case study the control performance of the pseudospectral approach is about 10% better than that of the MILP approach, and the computation time of the MILP approach is two to three orders of magnitude smaller than that of the pseudospectral method and the discrete dynamic programming approach.

Nowadays, a number of high-speed lines and dedicated urban rapid transit railway systems with short headways are operated with a high degree of automation (Hansen and Pachl, 2008). This requires an advanced train control system to fulfill safety and operational requirements, such as the European Train Control System, which includes the equipment on board of the trains as well as in the control center (Midya and Thottappillil, 2008). An advanced train control system enables the energy-efficient driving of trains, which becomes more and more important because of the rising energy prices and environmental concerns (Liu and Golovicher, 2003). The automatic train operation (ATO) subsystem of the advanced train control system drives the train according to an optimal trajectory and recalculates it when the operational conditions change (Peng, 2008). Therefore, it is important to design an efficient algorithm to find the optimal speed-position reference trajectory. The present paper proposes two approaches to determine the optimal trajectory, viz. the pseudospectral method and the mixed-integer linear programming approach. In fact, the optimal control problem of train operations was solved firstly by applying the maximum principle by Ichikawa (1968). From the point view of optimal control, there are three basic numerical approaches for solving the optimal control problem: dynamic programming, indirect methods, and direct methods (Dielh et al., 2006). In the following, we will briefly present the research about the optimal control of trains in the literature for each of these three categories. Dynamic programming simplifies a complicated problem by breaking it down into simpler subproblems in a recursive manner. The result obtained by the calculation is in the form of a feedback control law in tabular form. Franke et al. (2002) solved the optimal control problem by discrete dynamic programming and compared the results with those of sequential quadratic programming. They concluded that discrete dynamic programming deals better with the nonlinear optimal problem. Ko et al. (2004) also applied dynamic programming to optimize the optimal reference trajectory. The original problem is then transformed into a multi-stage decision process and can be solved in an acceptable time with their improvements. It is known that approximations need to be made, usually by discretization, when dynamic programming is applied to discrete-time systems with continuous state spaces (Dielh et al., 2006). This discretization leads to the “curse of dimensionality”, which means exponential growth of the computation cost with respect to the dimension of the state space. In an indirect method, the calculus of variations is used to obtain the first-order necessary conditions for optimality (Bryson and Ho, 1975 and Pontryagin, 1962). A Hamiltonian boundary-value problem results from these necessary conditions. For a train with discrete control inputs, i.e. the traction/braking force can only take some discrete values, Howlett (2000) used the Karush–Kuhn–Tucker condition to determine the optimal switching times, for a given fixed discrete-valued control sequence. For a train with continuous control inputs, Howlett (1990) simplified the analysis by using Pontryagin’s principle to reformulate the problem as a finite-dimensional constrained optimization problem where the unknown switching times are the variables. Later on, Khmelnitsky (2000) gave a comprehensive analysis of the optimal trajectory planning problem with a continually varying gradient and speed restrictions. The maximum principle was applied to obtain optimal operation regimes (i.e. maximum traction, cruising, coasting, and maximum braking) and their sequences. The drawback of indirect methods is that the boundary-value problem is often difficult to solve due to strong nonlinearity and instability. In a direct method, the continuous-time optimal control problem is transformed into a nonlinear programming problem (Bettes, 2001). The resulting nonlinear programming problem is then solved by variants of well-developed algorithms, such as SNOPT (Gill et al., 2002) and IPOPT (Wächter and Biegler, 2006). Direct methods can easily handle inequality constraints on states and inputs (Dielh et al., 2006). Over the last decade, a particular class of direct methods, called pseudospectral methods, have risen to prominence in the numerical optimal control area (Elnagar et al., 1995). Pseudospectral methods were researched widely in the 1970s for solving partial differential equations (PDEs) in fluid dynamics (Canuto et al., 1988). Later on, they became an important methodology for the numerical solution of PDEs. From the 1990s on, pseudospectral methods were applied to solving optimal control problems (Gong et al., 2007), such as orbit transfers, lunar guidance, magnetic control. Recently, the scope of application has been broadened as a result of significant progress in large-scale computation. However, to the authors’ best knowledge, pseudospectral methods have not been applied to trajectory planning of trains. Therefore, the pseudospectral method is used for the first time to solve the train trajectory planning problem in this paper. On the other hand, multi-parametric quadratic programming is used in (Vašak et al., 2009) to calculate the optimal control law for train operations. The nonlinear train model with quadratic resistance is approximated by a piecewise affine function. Inspired by (Vašak et al., 2009), in Wang et al. (2011) we proposed to solve the optimal trajectory problem as a mixed integer linear programming (MILP) problem, which can be solved efficiently using existing commercial and free solvers (Linderoth and Ralphs, 2005 and Atamtürk and Savelsbergh, 2005). In the current paper, the MILP approach is extended in the following three aspects: we now allow different coefficients for the piecewise function for each space interval, we also approximate the nonlinear maximum traction force by piecewise affine functions, and we consider a more realistic model for the line resistance. The performance of the pseudospectral method and the MILP approach is compared with the discrete dynamic programming approach proposed in (Franke et al., 2002). Franke et al. (2002) concluded that the performance of the discrete dynamic programming approach is better than the sequential quadratic programming approach and the coasting strategy obtained by the maximum principle. Therefore, we have selected the discrete dynamic programming approach as the third approach for the comparison of the case study. The remainder of this paper is structured as follows. In Section 2 the nonlinear model of train operations is presented and the optimal trajectory planning problem is formulated. In Section 3 the optimal trajectory planning problem is recast as an multi-phase optimal control problem, which can be solved by the pseudospectral method. In Section 4 the nonlinear train model is formulated as a mixed logical dynamic model by approximating the nonlinear terms by piecewise functions and the optimal control problem is recast as an MILP problem. Section 5 illustrates with a case study how to calculate the optimal reference trajectory by the pseudospectral method and the MILP approach and it also compares these two approaches with the discrete dynamic programming approach. We conclude with a short discussion of some topics for future work in Section 6.

In the current paper, the optimal trajectory planning problem for trains is considered. We have proposed two approaches to solve this problem: the pseudospectral method and the mixed integer linear programming (MILP) approach. In the pseudospectral method, the optimal trajectory planning problem is formulated as a multiple-phase optimal control problem based on piecewise line resistance and speed limits. The constraints caused by the varying maximum traction force are defined as nonlinear path constraints. In the MILP approach, the nonlinear train operation model is formulated as a mixed logical dynamical model by using piece-wise affine (PWA) approximations. The variable line resistance (including variable grade profile, tunnels, curves) and speed restrictions are considered, which are included in the constraints of the mixed logical dynamic model. Furthermore, the optimal control problem is recast as an MILP problem, which can be solved efficiently by existing solvers. The case study shows that the pseudospectral method has the best control performance and the MILP has the best overall performance if the computation time is included. In addition, the computation time of the MILP approach is much shorter compared with the pseudospectral method and the discrete dynamic programming approach. The relative difference between the performance of the MILP approach and that of the pseudospectral approach is about 10%. When the timetable is known, the two approaches proposed in this paper (i.e. the MILP and the pseudospectral approach) can be applied to calculate the optimal trajectory for trains between stations to save energy and to ensure passenger comfort. If there are some disturbances in the network, then one could use a rescheduling approach to reorder trains and determine new timetables (Hansen and Pachl, 2008 and D’Ariano et al., 2008). Next, the affected trains have to optimize their trajectories according to the new timetable. In this case, the trajectory planning problem needs to be solved quickly to satisfy the real-time requirements; so then the MILP approach could be applied since it gives the best trade-off between computational speed and accuracy. An extensive comparison and assessment of the pseudospectral method, the MILP approach, and other approaches in the literature for various case studies and a wide range of scenarios will be a topic for future work. In addition, in this paper we focus on the trajectory planning for a single train between two stations with the assumption that the constraints and disturbances caused by signaling systems and other trains are handled by the lower control level. However, in practice these constraints and disturbances are significant for the capacity of the railway network, and therefore some interesting conflict detection and resolution approaches have been proposed to manage these constraints and disturbances during the rescheduling phases (D’Ariano and Albrecht, 2006, D’Ariano et al., 2007 and Corman et al., 2009). In future work, we will combine these conflict detection and resolution approaches with the trajectory planning approaches proposed in this paper to solve the trajectory planning for multiple trains. There we will also use the MILP approach (including hierarchical and distributed optimization if the problem grows too large). Furthermore, the pseudospectral and MILP solvers used in this paper are general-purpose solvers. By making use of the specific structure and properties of the optimal trajectory planing problem, significant speed-ups can be expected. Therefore, in the future we will develop tailored pseudospectral and MILP solvers for the optimal trajectory planing problem for trains. Moreover, a typical automatic train operation system consists of two levels of control actions. The high-level control is calculating the optimal reference trajectory, as shown in this paper. In the future, we will also focus on the low-level control of the automatic train operation system, which is used to make the train track the pre-planned reference trajectory via certain control methods, such as model predictive control (Camacho and Bordons, 1995), robust control (Green and Limebeer, 1995), and adaptive control (Tao, 1995).