A dynamic programming approach for optimizing train speed profiles with speed restrictions and passage points. (May 2017) - Haahr, Jørgen Thorlund; Pisinger, David; Sabbaghian, Mohammad
Highlights: Novel solution method for generating optimal speed profiles for trains. Passage points and several other extensions can easily be handled Energy consumption is decreased by 3.3% compared to a state-of-the-art commercial system. The algorithm can solve the problem from scratch in a few seconds. The algorithm is suitable for a Train driver advice systems. Abstract: This paper considers a novel solution method for generating improved train speed profiles with reduced energy consumption. The solution method makes use of a time-space graph formulation which can be solved through Dynamic Programming. Instead of using uniform discretization of time and space as seen previously in the literature, we rely on an event-based decomposition that drastically reduces the search space. This approach is very flexible, making it easy to handle, e.g., speed limits, changes in altitude, and passage points that need to be crossed within a given time window. Based on solving an extensive number of real-life problem instances, our benchmarks show that the proposed solution method is able to satisfy all secondary constraints and still be able to decrease energy consumption by 3.3% on average compared to a commercial solver provided by our industrial collaborator, Cubris. The computational times are generally very low, making it possible to recompute the train speed profile in case of unexpected changes in speed restrictions or timings. This is a great advantage over static offline lookup tables. Also, the framework is very flexible, making it possible to handle a number of additional constraints on robustness, passenger comfort etc. Selected details of the method and benchmark are only described at a high level for confidentiality reasons.