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

The optimal trajectory planning problem for multiple trains under fixed block signaling systems and moving block signaling systems is considered. Two approaches are proposed to solve this optimal control problem for multiple trains: the greedy approach and the simultaneous approach. In each solution approach, the trajectory planning problem is transformed into a mixed integer linear programming (MILP) problem. In particular, the objective function considered is the energy consumption of trains and the nonlinear train model is approximated by a piece-wise affine model. The varying line resistance, variable speed restrictions, and maximum traction force, etc. are also included in the problem definition. In addition, the constraints caused by the leading train in a fixed or moving block signaling system are first discretized and then transformed into linear constraints using piecewise affine approximations resulting in an MILP problem. Simulation results comparing the greedy MILP approach with the simultaneous MILP approach show that the simultaneous MILP approach yields a better control performance but requires a higher computation time. Moreover, the performance of the proposed greedy and the proposed simultaneous MILP approach is also compared with that of the greedy and the simultaneous pseudospectral method, where the pseudospectral method is a state-of-the-art method for solving optimal control problems. The results show that the energy consumption and the end time violations of the greedy MILP approach are slightly larger than those of the greedy pseudospectral method, but the computation time is one to two orders of magnitude smaller. The same trend holds for the simultaneous MILP approach and the simultaneous pseudospectral method.

Nowadays, the energy efficiency of transportation systems is becoming more and more important because of the rising energy prices and environmental concerns. Rail traffic plays a significant role for the sustainability for transportation systems, since it can provide safe, fast, punctual, and comfortable services (Peng, 2008). The reduction of energy consumption is one of the key objectives of railway systems because energy consumption is one of the major expenses in operational cost, which is about 13–16% of the annual operation and maintenance cost of railway systems in China (Ding, Bai, Liu, & Mao, 2009). Therefore, even a small improvement in energy saving is attractive to the railway operators since it can save a large amount of money. Some driver assistance systems have been developed to assist drivers to drive the train optimally, such as FreightMiser (Howlett & Pudney, 1995), Metromiser (Howlett & Pudney, 1995), and driving style manager (Franke, Meyer, & Terwiesch, 2002). With the development of modern railway systems, an automatic train operation system plays a key role in ensuring accurate stopping, operation punctuality, energy saving, and riding comfort (Peng, 2008). The railway control center or automatic train operation systems are responsible for solving the trajectory planning problems based on the information collected by train monitoring systems, such as line resistance, speed limits, maximum traction and braking forces. In the literature, the research on the optimal control of train operations began in the 1960s and is aimed at solving the trajectory planning problem for a train running from one station to another. Since it has significant effects for energy saving, punctuality, etc., various approaches were proposed for the trajectory planning problem. These approaches can be grouped into two main categories: analytical solutions and numerical optimization. For analytical solutions, the maximum principle is applied and it results in four optimal regimes (i.e., maximum traction, cruising, coasting, and maximum braking) (Howlett, 2000, Howlett et al., 1994, Khmelnitsky, 2000 and Liu and Golovicher, 2003). It is difficult to obtain the analytical solution if more realistic conditions are considered as these introduce more complex nonlinear terms into the model equations and the constraints (Ko, Koseki, & Miyatake, 2004). Numerical optimization approaches are applied more and more to the train optimal control problem due to the increasing computing power nowadays. A number of advanced techniques such as fuzzy and genetic algorithms have been proposed to calculate the optimal reference trajectory for trains, see, e.g., Chang and Xu (2000), Chang and Sim (1997), Han et al. (1999), and Ke, Lin, and Lai (2011). But in these approaches, the optimal solution is not always guaranteed to be found. On the other hand, multi-parametric quadratic programming is used in Vašak, Baotić, Perić, and Bago (2009) to calculate the optimal control law for train operations. In that approach, the nonlinear train model with quadratic resistance is approximated by a piecewise affine function. Inspired by Vašak et al. (2009), in Wang, De Schutter, Ning, Groot, and van den Boom (2011) and Wang, De Schutter, van den Boom, and Ning (2013) 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 (Atamtürk and Savelsbergh, 2005 and Linderoth and Ralphs, 2005) that guarantee finding the global optimum of the MILP problem. However, the approaches mentioned above ignore the impact caused by the signaling systems, e.g., a fixed block signaling (FBS) system or a moving block signaling (MBS) system. An FBS system is a block system using fixed block sections, which are protected by trackside traffic signals. A train cannot enter a block section until a signal indicates the train may proceed. In an MBS system, the blocks are defined as safe zones around each train in real time. Regular communication between trains and zone controllers is needed for knowing the exact locations and speeds of all trains in that zone at any given time. An MBS system allows trains to run closer together compared with an FBS system, thus increasing the line capacity. Lu and Feng (2011) consider the operation of two trains on a same line and optimize the trajectory of the following train with constraints caused by the leading train in an FBS system. More specifically, a parallel genetic algorithm is used to optimize the trajectories for the leading train and the following train, resulting in a lower energy consumption (Lu & Feng, 2011). Gu, Lu, and Tang (2011) apply nonlinear programming to optimize the trajectory for the following train. Two situations of the leading train, i.e. running and stopped, are studied and the corresponding strategies are proposed for the following train. In addition, Ding et al. (2009) take the constraints caused by the MBS system into account and develop an energy-efficient multi-train control algorithm to calculate the optimal trajectories. Three optimal control regimes, i.e. maximum traction, coasting, and maximum braking, are adopted in the algorithm and the sequences of these three regimes are determined by a predefined logic. In this paper, the constraints caused by the leading train in an FBS system and an MBS system are formulated. These constraints are discretized and then recast as linear constraints by piecewise affine approximations. Thus, they can be easily included into the MILP problem, which can be solved efficiently compared to the existing approaches. Furthermore, the greedy approach and the simultaneous approach are proposed to solve the trajectory planning problem for multiple trains. We also compare the MILP approach with the state-of-art optimization approach: pseudospectral methods. Over the last decade, pseudospectral methods have risen to prominence in the numerical optimal control area (Elnagar, Kazemi, & Razzaghi, 1995), which were applied to solving optimal control problems (Gong et al., 2007), such as orbit transfers, lunar guidance, magnetic control. Therefore, we have selected the pseudospectral method for the comparison of the case study. The remainder of this paper is structured as follows. In Section 2, the train model and the MILP approach for a single train are summarized based on Wang et al. (2013). Section 3 introduces the principle of railway signaling systems, i.e. the FBS system and the MBS system. Section 4 formulates the constraints for the following train caused by the leading train under an FBS system and shows how to include these constraints into the MILP formulation. The constraints caused by the MBS system are considered and included in the MILP problem in Section 5. Section 6 illustrates the calculation of the optimal trajectories using the data from Beijing Yizhuang subway line. We conclude with a short discussion of some topics for future work in Section 7.

In this paper, we have proposed two approaches, namely the greedy approach and simultaneous approach, to solve the optimal trajectory planning problem for multiple trains. In the greedy approach, the optimal trajectory planning problem of the leading train is solved first and then based on the optimal control inputs of the leading train, the trajectory planning problem for the following train is solved. For the simultaneous approach, the trajectories of the leading train and the following train are optimized at the same time. The constraints caused by the leading train in a fixed block signaling system and a moving block signaling system are included in the optimal trajectory planning problem for multiple trains. The nonlinear terms in the train model and constraints are approximated by piecewise affine functions. In this way, the optimal trajectory planning problem for multiple trains can then be recast as a mixed integer linear programming (MILP) problem. Furthermore, the performance of the greedy and the simultaneous MILP approach is compared with the greedy and the simultaneous pseudospectral method in a case study. The simulation results show that the MILP approaches have a similar control performance as the pseudospectral methods but they require a much less computation time. A topic for future work will be an extensive comparison and assessment between the MILP approach, the pseudospectral method (also using other nonlinear programming subsolvers, e.g., MINOS and KNITRO), a dynamic programming algorithm (Hellström, slund, & Nielsen, 2010), and other approaches and frameworks (such as AMPL, APMonitor, and ASCEND) described in the literature for various case studies and a wide range of scenarios.