Train Speed Profile Optimization Based on Lagrangian Relaxation Algorithm

Reasonable planning of the speed curve between the starting and ending points can effectively reduce the energy consumption of train operation. With regard to this issue, there is a contradiction between time optimization and energy optimization. The paper uses a modified Lagrange Relaxation algorithm with Dijkstra algorithm to build the optimal speed profile for trains between two stations. Firstly, the problem is converted to a graph theory problem. A node-edge network based on speed-distance profile is constructed to simulate the motion of the train between two stations, in which kinematic principles and physical characteristics are indicated in a graphic form. Secondly, a loop algorithm for Lagrange multiplier is designed. In each iteration, Lagrange Relaxation algorithm is adopted to combine the two matrices into one and it is solved by Dijkstra. The optimal Lagrange multiplier is identified by maximizing the combined cost. Thirdly, the optimal Lagrange multiplier is used to get the optimal velocity profile and energy consumed. To verify the effectiveness of the method, different velocity profiles under different scenarios are verified and compared. The experiment results show that the outcomes could satisfy all the speed constrictions in the path and the time consumed for the optimal path is nearest to maximum permissible time. It has been demonstrated that the proposed method could effectively solve for the most energy-efficient speed profile for the train while meeting the requirement of punctuality.