UDC 625.8
This article examines the problem of optimizing delivery routes in urban logistics. The goal of the study is to develop an efficient routing algorithm that minimizes total delivery costs while meeting customer time windows. The paper analyzes classical methods for solving the vehicle routing problem and identifies their limitations in modern conditions. A combined algorithm is proposed, combining the Clark-Wright heuristic for generating initial solutions with a local search procedure and a permutation operator for improving them. The algorithm takes into account key practical constraints: vehicle carrying capacity, delivery time windows, and driver workday hours. Results of computational experiments on test data demonstrate the advantage of the proposed algorithm over the classical "nearest neighbor" heuristic: a 17.3% reduction in total mileage and a 12.5% reduction in the number of vehicles deployed. The developed algorithm can be integrated into delivery management systems to improve the operational efficiency of logistics companies.
route optimization, algorithm development, logistics, Clark-Wright algorithm, local search, delivery time windows
1. Afanas'ev M.Yu., Boyko A.A. Modeli i metody resheniya zadach marshrutizacii transportnyh sredstv // Logistika i upravlenie cepyami postavok. – 2020. – № 4(93). – S. 34-48.
2. Grigor'ev I.V., Sokolov R.V. Algoritmy optimizacii marshrutov dostavki v gorodskoy logistike // Transportnye sistemy. – 2021. – № 2(45). – S. 56-67.
3. Ivanov S.P., Petrova E.V. Sovremennye podhody k resheniyu zadachi VRP s vremennymi oknami // Avtomatika i telemehanika. – 2019. – № 8. – S. 112-125.
4. Kozlov V.V., Sidorov A.N. Intellektual'nye sistemy upravleniya dostavkoy tovarov. – M.: Izdatel'stvo MGTU, 2018. – 256 s.
5. Orlov A.I. Teoriya prinyatiya resheniy v transportnyh sistemah. – SPb.: Piter, 2017. – 320 s.
6. Petrov K.A. Metody kombinatornoy optimizacii v logistike. – M.: INFRA-M, 2020. – 184 s.
7. Semenov V.V., Fedorova M.A. Evristicheskie algoritmy dlya zadach marshrutizacii // Informacionnye tehnologii. – 2022. – № 3. – S. 45-58.
8. Laporte G. Fifty Years of Vehicle Routing // Transportation Science. – 2009. – Vol. 43. – P. 408-416.
9. Potvin J.-Y. State-of-the-Art Review—Evolutionary Algorithms for Vehicle Routing // INFORMS Journal on Computing. – 2009. – Vol. 21. – P. 518-548.
10. Solomon M.M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints // Operations Research. – 1987. – Vol. 35. – P. 254-265.
11. Toth P., Vigo D. (eds.) The Vehicle Routing Problem. – Philadelphia: SIAM, 2002. – 355 p.
12. Vidal T., Crainic T.G., Gendreau M., Prins C. Heuristics for multi-attribute vehicle routing problems: A survey and synthesis // European Journal of Operational Research. – 2013. – Vol. 231(1). – P. 1-21.
