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

Algorithm for scheduling drivers on intercity road routes: case study of the shift method

• 
• 

User Rating:  / 0

PoorBest 

Details

Category: Content №4 2025

Last Updated on 26 August 2025

Published on 30 November -0001

Hits: 3566

Authors:

N. Khomyn, orcid.org/0009-0008-1906-3024, National Transport University, Kyiv, Ukraine

M. Oliskevych, orcid.org/0000-0001-6237-0785, S. Z. Gzhytsky Lviv National University of Veterinary Medicine and Biotechnology, Lviv, Ukraine

I. Taran*, orcid.org/0000-0002-3679-2519, Dnipro University of Technology, Dnipro, Ukraine, e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

G. Muratbekova, orcid.org/0000-0003-4733-2822, Academy of Civil Aviation, Almaty, Republic of Kazakhstan

* Corresponding author e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

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

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

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

Abstract:

Purpose. To develop a methodology for constructing an optimal work schedule for a group of trucks and drivers, which provides a guaranteed solution to the problem of insufficient productivity of the truck fleet, on the one hand, and a reduction in the shortage of drivers in the case of using a variable method of their work. At the same time, restrictions on the duration of work and rest of drivers are observed. The problem of low productivity is also manifested in the excessive duration of cargo delivery and too long downtime of trucks.

Methodology. The optimal schedule of trucks and drivers was obtained as a result of solving the problems of synchronous routing of several vehicles according to the criterion of minimum mileage and establishing the moments of start/completion of transport and technological operations. These two problems were solved using an improved two-stage algorithm for ordering mixed directed graphs containing cycles. The general ordering algorithm includes linear programming methods at the first stage, as well as “divide and conquer” methods and auxiliary graph colouring at the second stage.

Findings. A methodology for constructing an optimal work schedule for drivers and trucks has been developed, which allows for a variable work schedule for driver teams. A corresponding practical algorithm has been proposed. At the same time, the rules of the European Union regarding the work and rest regime of drivers have been observed. The total duration of cargo transportation is also reduced and the downtime of vehicles necessary for the rest of the drivers assigned to them is minimized. The effectiveness of the algorithm was tested on practical data from the activities of freight carriers. It was recorded that the duration of movement of trucks with cargo per day can be increased by 30.6 %. The overall productivity of trucks can be increased by 23.4 % without violating the European Agreement on the Work of Vehicle Crews.

Originality. For the first time, the problems of routing road freight transportation and optimizing truck and car schedules have been solved synchronously. The tightest schedules of drivers of several vehicles were obtained in accordance with the norms of the European Agreement on the Work of Vehicle Crews on Complex Routes.

Practical value. The developed methodology allows coordinating the operation of freight vehicles on the intercity transportation network, reducing their downtime, idling runs, and also reducing the time spent by driver teams when using the variable method.

Keywords: freight transportation, truck routing, optimal schedule, mixed graph

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

• < Prev
• Next >