×

Multi-train trajectory optimization for energy-efficient timetabling. (English) Zbl 1403.90374

Summary: This paper proposes a novel approach for energy-efficient timetabling by adjusting the running time allocation of given timetables using train trajectory optimization. The approach first converts the arrival and departure times to time window constraints in order to relax the given timetable. Then a train trajectory optimization method is developed to find optimal arrival/departure times and optimal energy-efficient speed profiles within the relaxed time windows. The proposed train trajectory optimization method includes two types, a single-train trajectory optimization (STTO), which focuses on optimizing individual train movements within the relaxed arrival and departure time windows, and a multi-train trajectory optimization (MTTO), which computes multi-train trajectories simultaneously with a shared objective of minimizing multi-train energy consumption and an additional target of eliminating conflicts between trains. The STTO and MTTO are re-formulated as a multiple-phase optimal control problem, which has the advantage of accurately incorporating varying gradients, curves and speed limits and different train routes. The multiple-phase optimal control problem is then solved by a pseudospectral method. The proposed approach is applied in case studies to fine-tune two timetables, for a single-track railway corridor and a double-track corridor of the Dutch railway. The results suggest that the proposed approach is able to improve the energy efficiency of a timetable.

MSC:

90B35 Deterministic scheduling theory in operations research
49N90 Applications of optimal control and differential games

Software:

GPOPS; PESPLib
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albrecht, A.; Howlett, P.; Pudney, P.; Vu, X.; Zhou, P., The key principles of optimal train control part 1: formulation of the model, strategies of optimal type, evolutionary lines, location of optimal switching points, Transportation Research Part B: Methodological, 94, 482-508, (2016)
[2] Albrecht, T.; Binder, A.; Gassel, C., Applications of real-time speed control in rail-bound public transportation systems, IET Intelligent Transport Systems, 7, 3, 305-314, (2013)
[3] Bešinović, N.; Goverde, R. M.P.; Quaglietta, E.; Roberti, R., An integrated micro-macro approach to robust railway timetabling, Transportation Research Part B: Methodological, 87, 14-32, (2016)
[4] Brännlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J.-E., Railway timetabling using Lagrangian relaxation, Transportation science, 32, 4, 358-369, (1998) · Zbl 1004.90035
[5] Cacchiani, V.; Caprara, A.; Toth, P., A column generation approach to train timetabling on a corridor, 4OR: A Quarterly Journal of Operations Research, 6, 2, 125-142, (2008) · Zbl 1151.90323
[6] Cacchiani, V.; Toth, P., Nominal and robust train timetabling problems, European Journal of Operational Research, 219, 3, 727-737, (2012) · Zbl 1253.90108
[7] Caimi, G.; Fuchsberger, M.; Laumanns, M.; Schüpbach, K., A multi-level framework for generating train schedules in highly utilised networks, Public Transport, 3, 1, 3-24, (2011)
[8] Canca, D.; Zarzo, A., Design of energy-efficient timetables in two-way railway rapid transit lines, Transportation Research Part B: Methodological, 102, 142-161, (2017)
[9] Garg, D., Advances in global pseudospectral methods for optimal control, (2011), University of Florida, (Ph.D. thesis).
[10] Gill, P. E.; Murray, W.; Saunders, M. A., {\scsnopt}: an {\scsqp} algorithm for large-scale constrained optimization, SIAM Review, 47, 1, 99-131, (2005)
[11] Goverde, R. M.P.; Bešinović, N.; Binder, A.; Cacchiani, V.; Quaglietta, E.; Roberti, R.; Toth, P., A three-level framework for performance-based railway timetabling, Transportation Research Part C: Emerging Technologies, 67, 62-83, (2016)
[12] Goverde, R. M.P.; Corman, F.; DAriano, A., Railway line capacity consumption of different railway signalling systems under scheduled and disturbed conditions, Journal of Rail Transport Planning & Management, 3, 3, 78-94, (2013)
[13] Gupta, S. D.; Tobin, J. K.; Pavel, L., A two-step linear programming model for energy-efficient timetables in metro railway networks, Transportation Research Part B: Methodological, 93, 57-74, (2016)
[14] Hansen, I. A.; Pachl, J., Railway timetabling and operations, (2014), Eurailpress
[15] Howlett, P., The optimal control of a train, Annals of Operations Research, 98, 1, 65-87, (2000) · Zbl 0977.49026
[16] Howlett, P.; Pudney, P., Energy-efficient train control, (1995), Springer London, UK · Zbl 0848.93042
[17] Huang, Y.; Yang, L.; Tang, T.; Cao, F.; Gao, Z., Saving energy and improving service quality: bicriteria train scheduling in urban rail transit systems, IEEE Transactions on Intelligent Transportation Systems, 17, 12, 3364-3379, (2016)
[18] Huang, Y.; Yang, L.; Tang, T.; Gao, Z.; Cao, F., Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks, Energy, 138, 1124-1147, (2017)
[19] Khmelnitsky, E., On an optimal control problem of train operation, IEEE Transactions on Automatic Control, 45, 7, 1257-1266, (2000) · Zbl 0972.49026
[20] Kraay, D.; Harker, P. T.; Chen, B., Optimal pacing of trains in freight railroads: model formulation and solution, Operations Research, 39, 1, 82-99, (1991)
[21] Li, X.; Lo, H. K., An energy-efficient scheduling and speed control approach for metro rail operations, Transportation Research Part B: Methodological, 64, 73-89, (2014)
[22] Li, X.; Lo, H. K., Energy minimization in dynamic train scheduling and control for metro rail operations, Transportation Research Part B: Methodological, 70, 269-284, (2014)
[23] Liu, R.; Golovitcher, I. M., Energy-efficient operation of rail vehicles, Transportation Research Part A: Policy and Practice, 37, 10, 917-932, (2003)
[24] Lusby, R. M.; Larsen, J.; Bull, S., A survey on robustness in railway planning, European Journal of Operational Research, 266, 1, 1-15, (2017) · Zbl 1403.90146
[25] Peeters, L., Cyclic railway timetable optimization, (2003), Erasmus Universiteit Rotterdam Rotterdam, The Netherlands, (Ph.D. thesis).
[26] ProRail (2017). Network statement. https://www.prorail.nl/sites/default/files; ProRail (2017). Network statement. https://www.prorail.nl/sites/default/files
[27] Rao, A.; Benson, D.; Darby, C.; Mahon, B.; Francolin, C.; Patterson, M., User’s manual for gpops version 4. x: a Matlab software for solving multiple-phase optimal control problems using hp-adaptive pseudospectral methods, (2011), University of Florida Gainesville
[28] Rao, A. V., Extension of a pseudospectral Legendre method to non-sequential multiple-phase optimal control problems, Proceedings of the AIAA guidance, navigation, and control conference and exhibit, Austin, USA, 11-14, (2003)
[29] Rao, A. V.; Benson, D. A.; Darby, C.; Patterson, M. A.; Francolin, C.; Sanders, I.; Huntington, G. T., Algorithm 902: {\scgpops}, a Matlab software for solving multiple-phase optimal control problems using the Gauss pseudospectral method, ACM Transactions on Mathematical Software, 37, 2, 22, (2010) · Zbl 1364.65131
[30] Scheepmaker, G. M.; Goverde, R. M.P., The interplay between energy-efficient train control and scheduled running time supplements, Journal of Rail Transport Planning & Management, 5, 4, 225-239, (2015)
[31] Scheepmaker, G. M.; Goverde, R. M.P.; Kroon, L. G., Review of energy-efficient train control and timetabling, European Journal of Operational Research, 257, 2, 355-376, (2017) · Zbl 1394.90005
[32] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM Journal on Discrete Mathematics, 2, 4, 550-581, (1989) · Zbl 0676.90030
[33] Su, S.; Li, X.; Tang, T.; Gao, Z., A subway train timetable optimization approach based on energy-efficient operation strategy, IEEE Transactions on Intelligent Transportation Systems, 14, 2, 883-893, (2013)
[34] Su, S.; Tang, T.; Li, X.; Gao, Z., Optimization of multitrain operations in a subway system, IEEE Transactions on Intelligent Transportation Systems, 15, 2, 673-684, (2014)
[35] Wang, P.; Goverde, R. M.P., Multiple-phase train trajectory optimization with signalling and operational constraints, Transportation Research Part C: Emerging Technologies, 69, 255-275, (2016)
[36] Wang, P.; Goverde, R. M.P., Train trajectory optimization of opposite trains on single-track railway lines, Proceedings of the IEEE international conference on intelligent rail transportation (ICIRT), Birmingham, UK, 23-31, (2016)
[37] Wang, P.; Goverde, R. M.P., Two-train trajectory optimization with a Green-wave policy, Transportation Research Record: Journal of the Transportation Research Board, 2546, 112-120, (2016)
[38] Wang, P.; Goverde, R. M.P., Multi-train trajectory optimization for energy efficiency and delay recovery on single-track railway lines, Transportation Research Part B: Methodological, 105, 340-361, (2017)
[39] Wang, Y.; Ning, B.; Cao, F.; De Schutter, B.; van den Boom, T. J., A survey on optimal trajectory planning for train operations, Proceedings of the IEEE international conference on service operations, logistics, and informatics (SOLI), Beijing, China, 589-594, (2011)
[40] Yang, L.; Li, K.; Gao, Z., Train timetable problem on a single-line railway with fuzzy passenger demand, IEEE Transactions on Fuzzy Systems, 17, 3, 617-629, (2009)
[41] Yang, L.; Li, K.; Gao, Z.; Li, X., Optimizing trains movement on a railway network, Omega, 40, 5, 619-633, (2012)
[42] Yang, X.; Li, X.; Ning, B.; Tang, T., A survey on energy-efficient train operation for urban rail transit, IEEE Transactions on Intelligent Transportation Systems, 17, 1, 2-13, (2016)
[43] Ye, H.; Liu, R., A multiphase optimal control method for multi-train control and scheduling on railway lines, Transportation Research Part B: Methodological, 93, 377-393, (2016)
[44] Yin, J.; Tang, T.; Yang, L.; Gao, Z.; Ran, B., Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach, Transportation Research Part B: Methodological, 91, 178-210, (2016)
[45] Zhou, L.; Tong, L. C.; Chen, J.; Tang, J.; Zhou, X., Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks, Transportation Research Part B: Methodological, 97, 157-181, (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.