DOI: https://doi.org/10.15802/stp2019/171774

OPTIMIZATIONAL TRACTION TASKS ON THE RAILWAY NETWORK

M. G. Prytula, О. А. Pasechnyk

Abstract


Purpose. The paper involves the development of information and algorithmic support for conducting the optimization traction and energy calculations on the railway network for their further use in decision-making systems – systems for efficient management of the transport process. Methodology. The system is based on the graph-analytic system, the model of the train with different types of traction, the methods of optimal control of the train and the fundamental algorithms on the weighted graphs with possible parallel ribs (arcs). In the complex, these components of the system provide finding the tracks on the chart-diagram according to the given criteria, conducting the optimization traction-energy calculations according to different criteria, as well as conducting a comparative analysis of the obtained results. The reliability of the results has been repeatedly checked by available methods for varying complexity of race according to the plan and profile of the course. For this purpose, data obtained as a result of control visits using dynamometric cars were used. Also a comparative analysis of the modes in operation of trains, calculated and received by qualified drivers on different races was conducted. Findings. The problem of efficient operation of various types and modifications of locomotives, involved in the implementation of trains schedules for different purposes and loads is considered. Presentations of direct and inverse optimization, according to various criteria, of the regime tasks on the railway network and variants of their effective solution are given. The analysis of the results of the developed mathematical support and the ideas of implemented algorithms is given. Originality. The paper proposes the establishment of the network optimization problems that arise at the stages of the developing the plan for the formation, construction of traffic schedules, transmission capacity assessment and the calculation of optimal parameters for the composite graphs of motion, etc. The system approach is important to ensure the combination of the developed network structure in the universal terms of the graph theory with the system of actualization of their parameters. Pull and energy efficiency calculations are carried out by combinatorial optimization methods, which ensured the maximum level of automation of the process in solving a large set of direct and inverse regime problems with different optimality criteria. Practical value. The information and algorithmic support for the automation of the process in solving the direct and reverse regime traction-energy problems on the railway network was developed. It was tested in the process of calculating the main components for the formation of traffic schedules, analysis of train driving modes, assessment in choosing the optimal parameters of the track reconstruction for high-speed and new types of trains (locomotives).


Keywords


traction calculations; railway network; fundamental algorithms; mode of movement; optimal mode; schedule; traffic safety; mathematical support

References


Kormen, T. K., Leyzerson, C. I., Rivest, R. L., & Shtayn, K. (2011). Algoritmy: Postroenie i analiz. Moskow: Williams. (in Russian)

Kristofides, N. (1978). Teoriya grafov. Algoritmicheskiy podkhod. Moskow: Mir. (in Russian)

Muginsheyn, L. A., Ilyutovich, A. U., & Yabko, I. A. (2012). Energooptimalnye metody upravleniya dvizheniem poezdov. Moskow: Intext. (in Russian)

Prytula, M. H., & Shpakovych, R. R. (2008). Alhorytm pobudovy hrafika rukhu poizdiv. Bulletin of the National University «Lviv Polytechnic». Series: Computer Science and Information Technologies, 629, 146-152. (in Ukrainian)

Prytula, M. H., & Shpakovych, R. R. (2007). Modeliuvannia ta rozrakhunok optymalnykh parametriv rukhu poizdiv. Physical-mathematical modeling and information technologies, 5, 139-145. (in Ukrainian)

Prytula, M. H., & Shpakovych, R. R. (2008). Identyfikatsiia parametriv modeli rukhu poizda. Bulletin of the National University «Lviv Polytechnic». Series: Computer Science and Information Technologies, 629, 105-110. (in Ukrainian)

Prytula, M. G., & Pasechnyk, O. A. (2019). Development of the algorithms formation of energy-optimized trains traffic modes. Science and Transport Progress, 6(78), 82-100. doi: https://doi.org/10.15802/stp2018/154641 (in Ukrainian)

Kapіtsa, M. І., Kalіvoda, J., Neduzha, L. O., Ochkasov, O. B., & Chernyayev, D. V. (2018). Komp’yuterne modelyuvannya zalіznichnikh transportnikh zasobіv: metodychni vkazivky do vykonannia praktychnykh robit, kursovoho ta dyplomnoho proektuvannia. Dnipro. (in Ukranian)

Sedzhvik, R. (2002). Fundamentalnye algoritmy na S++: Algoritmy na grafakh. St. Petersburg: Diasoft. (in Russian)

Troelsen, E. (2008). S# i platforma. NET 3.0. St. Petersburg: Piter. (in Russian)

Cacchiani, V., Huisman, D., Kidd, M., Kroon, L., Toth, P., Veelenturf, L., & Wagenaar, J. (2014). An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research. Part B: Methodological, 63, 15-37. doi: https://doi.org/10.1016/j.trb.2014.01.009 (in English)

Dollevoet, T., Huisman, D., Kroon, L. G., Veelenturf, L. P., & Wagenaar, J. C. (2017). Application of an iterative framework for real-time railway rescheduling. Computers & Operations Research, 78, 203-217. doi: doi.org/10.1016/j.cor.2016.08.011 (in English)

Corman, F., & Meng, L. (2015). Review of Online Dynamic Models and Algorithms for Railway Traffic Management. IEEE Transactions on Intelligent Transportation Systems, 16(3), 1274-1284. doi: https://doi.org/10.1109/tits.2014.2358392 (in English)

Gholamian, S. A. (2017). A discrete-event optimization framework for mixed-speed train timetabling problem. Journal of Industrial Engineering and Management Studies, 4(2), 64-84. (in English)

Haahr, J., Pisinger, D., & Sabbaghian, M. (2017). A dynamic programming approach for optimizing train speed profiles with speed restrictions and passage points. Transportation Research Part B: Methodological, 99, 167-182. doi: https://doi.org/10.1016/j.trb.2016.12.016 (in English)

Zhou, L., Tong, Lu (Carol), Chen, J., Tang, J., & Zhou, X. (2017). 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. doi: https://doi.org/10.1016/j.trb.2017.01.002 (in English)

Klimenko, І, Kalivoda, J., & Neduzha, L. (2018). Parameter Optimization of the Locomotive Running Gear, Transport Means 2018: Proceedings of 22nd International Scientific Conference. Trakai, Klaipėda. (in English)

Scheepmaker, G. M., Goverde, R. M. P., & Kroon, L. G. (2017). Review of energy-efficient train control and timetabling. European Journal of Operational Research, 257(2), 355-376. doi: https://doi.org/10.1016/j.ejor.2016.09.044 (in English)

Skiena, S. S. (2008). The Algorithm Design Manual. London: Springer. doi: https://doi.org/10.1007/978-1-84800-070-4 (in English)

Albrecht, A., Howlett, P., Pudney, P., Vu, X., & Zhou, P. (2016). 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. doi: https://doi.org/10.1016/j.trb.2015.07.023 (in English)

Albrecht, A., Howlett, P., Pudney, P., Vu, X. & Zhou P. (2016). The key principles of optimal train control. Part 2: Existence of an optimal strategy, the local energy minimization principle, uniqueness, computational techniques. Transportation Research. Part B: Methodological, 94, 509-538. doi: https://doi.org/10.1016/j.trb.2015.07.024 (in English)

Wang, P. (2017). Train Trajectory Optimization Methods for Energy-Efficient Railway Operations. (Doctoral thesis). Delft University of Technology, Delft. Retrieved from https://repository.tudelft.nl/islandora/object/uuid%3Ace04a07d-89fc-470a-9d1a-b6fae9182dae (in English)

Warg, J., & Bohlin, M. (2016). The use of railway simulation as an input to economic assessment of timetables. Journal of Rail Transport Planning & Management, 6(3), 255-270. doi: https://doi.org/10.1016/j.jrtpm.2016.08.001 (in English)

Ye, H., & Liu, R. (2017). Nonlinear programming methods based on closed-form expressions for optimal train control. Transportation Research. Part C: Emerging Technologies, 82, 102-123. doi: https://doi.org/10.1016/j.trc.2017.06.011 (in English)


GOST Style Citations


  1. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн ; пер. с англ. – 2-е изд. – Москва : Вильямс, 2005. – 1296 с.
  2. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – Москва : Мир, 1978. – 432 с.
  3. Мугиншейн, Л. А. Энергооптимальные методы управления движением поездов / Л. А. Мугиншейн, А. У. Илютович, И. А. Ябко. – Москва : Интекст, 2012. – 80 с.
  4. Притула, М. Г. Алгоритм побудови графіка руху поїздів / М. Г. Притула, Р. Р. Шпакович // Вісн. Нац. ун-ту «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології : зб. наук. пр. – Львів, 2008. – № 629. – С. 146–152.
  5. Притула, М. Г. Моделювання та розрахунок оптимальних параметрів руху поїздів / М. Г. Притула, Р. Р. Шпакович // Фізико-математичне моделювання та інформаційні технології. – 2007. – Вип. 5. – С. 139–145.
  6. Притула, М. Г. Ідентифікація параметрів моделі руху поїзда / М. Г. Притула, Р. Р. Шпакович // Вісн. Нац. ун-ту «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології : зб. наук. пр. – Львів, 2008. – № 629. – С. 105–110.
  7. Притула, М. Г. Розроблення алгоритмів формування енергооптимальних режимів руху поїздів / М. Г. Притула, О. А. Пасечник // Наука та прогрес транспорту. – 2018. – № 6 (78). – С. 82–100. doi: https://doi.org/10.15802/stp2018/154641
  8. Комп’ютерне моделювання залізничних транспортних засобів : метод. вказівки до виконання практичних робіт, курсового та дипломного проектування / М. Капіца, Я. Калівода, Л. Недужа, О. Очкасов, Д. Черняєв. – Дніпро : Дніпропетр. нац. ун-т залізн. трансп. ім. акад. В. Лазаряна, 2018. – 59 с.
  9. Седжвик, Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах / Р. Седжвик ; пер. с англ. – Санкт-Петербург : Диасофт, 2002. – 496 с.
  10. Троелсен, Э. С# и платформа. NET 3.0 / Э. Троелсен. – Санкт-Петербург : Питер, 2008. – 1456 с.
  11. An overview of recovery models and algorithms for real-time railway rescheduling / V. Cacchiani, D. Huisman, M. Kidd [at al.] // Transportation Research. Part B: Methodological. – 2014. – Vol. 63. – P. 15–37. doi: https://doi.org/10.1016/j.trb.2014.01.009
  12. Application of an iterative framework for real-time railway rescheduling / T. Dollevoet, D. Huisman, L. Kroon, L. Veelenturf, J.Wagenaar // Computers & Operations Research. – 2017. – Vol. 78. – P. 203–217. doi: doi.org/10.1016/j.cor.2016.08.011
  13. Corman, F. A Review of Online Dynamic Models and Algorithms for Railway Traffic Management / F. Corman, L. Meng // IEEE Transactions on Intelligent Transportation Systems. – 2015. – Vol. 16. – Iss. 3. – P. 1274–1284. doi: https://doi.org/10.1109/tits.2014.2358392 
  14. Gholamian, S. A. A discrete-event optimization framework for mixed-speed train timetabling problem / S. A. Gholamian // Journal of Industrial Engineering and Management Studies. – 2017. – Vol. 4, No. 2. – P. 64–84.
  15. Haahr, J. T. A dynamic programming approach for optimizing train speed profiles with speed restrictions and passage points / J. T. Haahr, D. Pisinger, M. Sabbaghian // Transportation Research. Part B: Methodological. – 2017. – Vol. 99. – P. 167–182. doi: https://doi.org/10.1016/j.trb.2016.12.016
  16. Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks / L. Zhou, Lu (Carol) Tong, J. Chen, J. Tang, X. Zhou // Transportation Research. Part B: Methodological. – 2017.Vol. 97. – P. 157–181. doi: https://doi.org/10.1016/j.trb.2017.01.002
  17. Klimenko, I. Parameter optimization of the locomotive running gear / I. Klimenko, J. Kalivoda, L. Neduzha // Transport Means 2018 : Proceedings of 22nd International Scientific Conference (October 3–5, 2018) / Kaunas University of Technology. – Trakai, Klaipėda, 2018. – Р. 1095–1098.
  18. Review of energy efficient train control and timetabling / G. Scheepmaker, M. Gerben, R. Goverde, L. Kroon // European Journal of Operational Research. – 2017. – Vol. 257. – Iss. 2. – P. 355–376. doi: https://doi.org/10.1016/j.ejor.2016.09.044
  19. Skiena, S. S. The Algorithm Design Manual / S. S. Skiena. – London : Springer,2008. – 730 p. doi: https://doi.org/10.1007/978-1-84800-070-4
  20. The key principles of optimal train control. Part 1: Formulation of the model, strategies of optimal type, evolutionary lines, location of optimal switching points / A. Albrecht, P. Howlett, P. Pudney, X. Vu, P. Zhou // Transportation Research. Part B: Methodological. – 2016. – Vol. 94. – P. 482–508. doi: https://doi.org/10.1016/j.trb.2015.07.023
  21. The key principles of optimal train control. Part 2: Existence of an optimal strategy, the local energy minimization principle, uniqueness, computational techniques / A. Albrecht, P. Howlett, P. Pudney, X. Vu, P. Zhou // Transportation Research. Part B: Methodological. – 2016. – Vol. 94. – P. 509–538. doi: https://doi.org/10.1016/j.trb.2015.07.024
  22. Wang, P. Train Trajectory Optimization Methods for Energy-Efficient Railway Operations : doctoral thesis [Електронний ресурс] / P. Wang ; Delft University of Technology. – Delft, 2017. – Режим доступу: https://repository.tudelft.nl/islandora/object/uuid%3Ace04a07d-89fc-470a-9d1a-b6fae9182dae. – Назва з екрана. – Перевірено : 18.06.2019.
  23. Warg, J. The use of railway simulation as an input to economic assessment of timetables / J. Warg, M. Bohlin // Journal of Rail Transport Planning & Management. – 2016. – Vol. 6. – Iss. 3. – P. 255–270. doi: https://doi.org/10.1016/j.jrtpm.2016.08.001
  24. Ye, H. Nonlinear programming methods based on closed-form expressions for optimal train control / H. Ye, R. Liu // Transportation Research. Part C: Emerging Technologies. – 2017. – Vol. 82. – P. 102–123. doi: https://doi.org/10.1016/j.trc.2017.06.011




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)