Науковий вісник НГУ

Алгоритм планування роботи водіїв на міжміських маршрутах: застосування вахтового методу роботи

• 
• 

Рейтинг користувача:  / 0

ГіршийКращий 

Деталі

Категорія: Зміст №4 2025

Останнє оновлення: 26 серпня 2025

Опубліковано: 30 листопада -0001

Перегляди: 1905

Authors:

Н. Хомин, orcid.org/0009-0008-1906-3024, Національний транспортний університет, м. Київ, Україна

М. Оліскевич, orcid.org/0000-0001-6237-0785, S. Львівський національний університет ветеринарної медицини та біотехнологій імені С. З. Гжицького, м. Львів, Україна

І. Таран*, orcid.org/0000-0002-3679-2519, Національний технічний університет «Дніпровська політехніка», м. Дніпро, Україна, e-mail: Ця електронна адреса захищена від спам-ботів. вам потрібно увімкнути JavaScript, щоб побачити її.

Г. Муратбекова, orcid.org/0000-0003-4733-2822, Академія цивільної авіації, м. Алмати, Республіка Казахстан

* Автор-кореспондент e-mail: Ця електронна адреса захищена від спам-ботів. вам потрібно увімкнути JavaScript, щоб побачити її.

повний текст / full article

Naukovyi Visnyk Natsionalnoho Hirnychoho Universytetu. 2025, (4): 185 - 194

https://doi.org/10.33271/nvngu/2025-4/185

Abstract:

Мета. Розробити методику побудови оптимального розкладу роботи групи вантажних автомобілів і водіїв, що забезпечує гарантоване розв‘язання проблеми недостатньої продуктивності вантажного автопарку, з одного боку, та зниження дефіциту водіїв у разі застосування змінного методу їх роботи. При цьому дотримуються обмеження тривалості роботи й відпочинку водіїв. Проблема низької продуктивності проявляється також у надмірній тривалості доставки вантажів і занадто довготривалому простої вантажних автомобілів.

Методика. Оптимальний розклад вантажних автомобілів і водіїв отримано внаслідок розв’язання задач синхронної маршрутизації декількох автомобілів за критерієм мінімального пробігу та встановлення моментів початку/завершення транспортно-технологічних операцій. Ці дві задачі розв’язані за допомогою вдосконаленого двоетапного алгоритму впорядкування змішаних орієнтованих графів, що містять цикли. Загальний алгоритм упорядкування містить у собі методи лінійного програмування на першому етапі, а також методи «розділяй і володарюй» і допоміжного розфарбовування графів на другому етапі.

Результати. Розроблена методика побудови оптимального розкладу роботи водіїв і вантажних автомобілів, що дає змогу скласти змінний розклад роботи бригад водіїв. Запропоновано відповідний практичний алгоритм. При цьому дотримані правила Європейського Союзу щодо режиму праці й відпочинку водіїв. Також скорочується загальна тривалість перевезення вантажів і мінімізується час простою автомобілів, необхідний для відпочинку водіїв, закріплених за ними. Ефективність алгоритму була перевірена на практичних даних з діяльності вантажоперевізників. Було зафіксовано, що тривалість руху автомобілів із вантажем на день може бути збільшена на 30,6 %. Загальна продуктивність вантажних автомобілів може бути збільшена на 23,4 % без порушення Європейської угоди про роботу екіпажів транспортних засобів.

Наукова новизна. Уперше задачі маршрутизації автомобільних вантажних перевезень та оптимізації розкладів автомобілів розв’язані синхронно. Отримані найбільш щільні графіки роботи водіїв декількох транспортних засобів відповідно до норм Європейської угоди про роботу екіпажів транспортних засобів на комплексних маршрутах.

Практична значимість. Розроблена методика дає змогу координувати експлуатацію вантажних транспортних засобів на мережі міжміських перевезень, зменшуючи їхні простої, холості пробіги, а також скорочуючи витрати часу бригад водіїв при застосуванні змінного методу.

Ключові слова: вантажні перевезення, маршрутизація вантажівок, оптимальний розклад, змішаний граф

References.

1. Beňuš, J., & Demirci, E. (2021). Regulation (EC) No 561/2006 - review of the adopted changes on 15 July 2020. The Archives of Automotive Engineering – Archiwum Motoryzacji, 90(4), 59-73. https://doi.org/10.14669/am.vol90.art5

2. Schiffer, M., Schneider, M., Walther, G., & Laporte, G. (2019). Vehicle Routing and Location Routing with Intermediate Stops: A Review. Transportation Science, 53(2), 319-343. https://doi.org/10.1287/trsc.2018.0836

3. Ammann, P., Kolisch, R., & Schiffer, M. (2023). Driver routing and scheduling with synchronization constraints. Transportation Research Part B: Methodological, 174, 102772. https://doi.org/10.1016/j.trb.2023.05.009

4. Ammar, A., Bennaceur, H., Châari, I., Koubâa, A., & Alajlan, M. (2015). Relaxed Dijkstra and A* with linear complexity for robot path planning problems in large-scale grid environments. Soft Computing, 20(10), 4149-4171. https://doi.org/10.1007/s00500-015-1750-1

5. Schiffer, M., & Walther, G. (2017). The electric location routing problem with time windows and partial recharging. European Journal of Operational Research, 260(3), 995-1013. https://doi.org/10.1016/j.ejor.2017.01.011

6. Tilk, C., & Goel, A. (2020). Bidirectional labeling for solving vehicle routing and truck driver scheduling problems. European Journal of Operational Research, 283(1), 108-124. https://doi.org/10.1016/j.ejor.2019.10.038

7. Domínguez-Martín, B., Rodríguez-Martín, I., & Salazar-González, J.-J. (2017). An exact algorithm for a Vehicle-and-Driver Scheduling Problem. Computers & Operations Research, 81, 247-256. https://doi.org/10.1016/j.cor.2016.12.022

8. Oliskevych, M., Taran, I., Volkova, T., & Klymenko, I. (2022). Simulation of cargo delivery by road carrier: case study of the transportation company. Naukovyi Visnyk Natsionalnoho Hirnychoho Universytetu, (2), 118-123. https://doi.org/10.33271/nvngu/2022-2/118

9. Pavlenko, O., Muzylyov, D., Ivanov, V., Bartoszuk, M., & Jozwik, J. (2023). Management of the grain supply chain during the conflict period: case study Ukraine. Acta Logistica, 10(3), 393-402. https://doi.org/10.22306/al.v10i3.406

10.      Taran, I., Bikhimova, G., Danchuk, V., Toktamyssova, A., Tursymbekova, Z., & Oliskevych, M. (2024). Improving the methodology for optimizing multimodal transportation delivery routes and cyclic schedules in a transnational direction. Transport Problems, 19(1), 157-170. https://doi.org/10.20858/tp.2024.19.1.13

11.      Koç, Ç., Jabali, O., & Laporte, G. (2017). Long-haul vehicle routing and scheduling with idling options. Journal of the Operational Research Society, 69(2), 235-246. https://doi.org/10.1057/s41274-017-0202-y

12.      Rodríguez-Martín, I., Salazar-González, J.-J., & Yaman, H. (2019). The periodic vehicle routing problem with driver consistency. European Journal of Operational Research, 273(2), 575-584. https://doi.org/10.1016/j.ejor.2018.08.032

13.      Bowden, Z. E., & Ragsdale, C. T. (2018). The truck driver scheduling problem with fatigue monitoring. Decision Support Systems, 110, 20-31. https://doi.org/10.1016/j.dss.2018.03.002

14.      Taran, I., Karsybayeva, A., Naumov, V., Murzabekova, K., & Chazhabayeva, M. (2023). Fuzzy-Logic Approach to Estimating the Fleet Efficiency of a Road Transport Company: A Case Study of Agricultural Products Deliveries in Kazakhstan. Sustainability, 15(5), 4179. https://doi.org/10.3390/su15054179

15.      Mayerle, S. F., De Genaro Chiroli, D. M., Neiva de Figueiredo, J., & Rodrigues, H. F. (2020). The long-haul full-load vehicle routing and truck driver scheduling problem with intermediate stops: An economic impact evaluation of Brazilian policy. Transportation Research Part A: Policy and Practice, 140, 36-51. https://doi.org/10.1016/j.tra.2020.07.021

16.      Pan, B., Zhang, Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1), 218-231. https://doi.org/10.1016/j.ejor.2020.09.022

17.      Muriyatmoko, D., Djunaidy, A., & Muklason, A. (2024). Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison. Procedia Computer Science, 234, 494-501. https://doi.org/10.1016/j.procs.2024.03.032

18.      Genova, K., & Williamson, D. P. (2015). An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem. Algorithms ‒ ESA 2015, 570-581. https://doi.org/10.1007/978-3-662-48350-3_48

19.      Cerrone, C., Cerulli, R., & Golden, B. (2017). Carousel greedy: A generalized greedy algorithm with applications in optimization. Computers & Operations Research, 85, 97-112. https://doi.org/10.1016/j.cor.2017.03.016

20.      Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61(3), 515-522. https://doi.org/10.1057/jors.2009.116

21.      Gmira, M., Gendreau, M., Lodi, A., & Potvin, J.-Y. (2021). Managing in real-time a vehicle routing plan with time-dependent travel times on a road network. Transportation Research Part C: Emerging Technologies, 132, 103379. https://doi.org/10.1016/j.trc.2021.103379

22.      Fischer, S., & Szürke, S. K. (2023). Detection process of energy loss in electric railway vehicles. Facta Universitatis, Series: Mechanical Engineering, 21(1), 81-99. https://doi.org/10.22190/FUME221104046F

23.      Fischer, S., Harangozó, D., Németh, D., Kocsis, B., Sysyn, M., Kurhan, D., & Brautigam, A. (2024). Investigation of heat-affected zones of thermite rail weldings. Facta Universitatis, Series: Mechanical Engineering, 22(4), 689-710. https://doi.org/10.22190/FUME221217008F

24.      Fischer, S. (2025). Investigation of the Settlement Behavior of Ballasted Railway Tracks Due to Dynamic Loading. Spectrum of Mechanical Engineering and Operational Research, 2(1), 24-46. https://doi.org/10.31181/smeor21202528

25.      Schepler, X., Rossi, A., Gurevsky, E., & Dolgui, A. (2022). Solving robust bin-packing problems with a branch-and-price approach. European Journal of Operational Research, 297(3), 831-843. https://doi.org/10.1016/j.ejor.2021.05.041

26.      Ahmed, A. A. A., Singhal, S., Prakaash, A. S., Dayupay, J., Rahadi, I., Marhoon, H. A., …, & Aravindhan, S. (2022). A Mathematical Model for the Vehicles Routing Problem with Multiple Depots, Considering the Possibility of Return Using the Tabu Search Algorithm. Foundations of Computing and Decision Sciences, 47(4), 359-370. https://doi.org/10.2478/fcds-2022-0019

27.      Elhüseyni, M., & Ünal, A. T. (2021). An integrated heuristic and mathematical modelling method to optimize vehicle maintenance schedule under single dead-end track parking and service level agreement. Computers & Operations Research, 132, 105261. https://doi.org/10.1016/j.cor.2021.105261

28.      Sotskov, Y. N., & Gholami, O. (2015). Mixed graph model and algorithms for parallel-machine job-shop scheduling problems. International Journal of Production Research, 55(6), 1549-1564. https://doi.org/10.1080/00207543.2015.1075666

29.      Oliskevych, M. (2018). Optimization of periodic unitary online schedule of transport tasks of highway road trains. Transport Problems, 13(1), 111-122. https://doi.org/10.21307/tp.2018.13.1.10

30.      Taran, I., Оlzhabayeva, R., Oliskevych, M., & Danchuk, V. (2023). Structural optimization of multimodal routes for cargo delivery. Archives of Transport, 67(3), 49-70. https://doi.org/10.5604/01.3001.0053.7076

• < Попередня
• Наступна >