Two-Stage Routing of Transport Using Geospatial Clustering

One of the urgent and key problems of the transport industry is considered. This is the problem of planning the routes of vehicles. The given problem can be described and formalized as the Traveling Salesman Problem (TSP) for many applications.

This problem consists in finding of the optimal route for a traveling salesman passing through the indicated cities at least once and with returning to the source city. In general, when planning such routes, it is necessary to solve the multiple traveling salesman problem (MTSP), which allows for more than one traveling salesman and more than one depot, their base point, where routes begin and end. As a combinatorial optimization problem, MTSP belongs to the class of NP-hard problems. This article presents a heuristic method for its solving on the basis of geospatial clusterization of the initial set of cities. First, an MTSP with a single depot is considered. A two-index mathematical formalization of this problem is given and the Miller-Tucker-Zemlin method is described. It reduced to the problem of integer linear programming. Metaheuristic methods for solving MTSP are discussed. A more complex problem an MTSP with several depots is being considered. A comprehensive two-stage method for solving this problem is described — the CFRS ("Cluster First — Route Second") method, which allows reducing it to the MTSP family with a single depot. Here, at the first stage, geospatial clustering of cities is carried out, for which it is possible to use various clustering methods, including the K-means method. At the second stage, for each built cluster, a depot is selected for its maintenance and routes are built to bypass all cities in this cluster. The clustering methodology is discussed as an effective tool for solving MTSP.

A numerical example of aviation logistics is given — the routing of flights of UAV group.

1. Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juan A. A. Rich Vehicle Routing Problem: Survey, ACM Computing Surveys, 2015, vol. 47, iss. 2, pp. 1—28, doi: 10.1145/2666003.

2. Valeeva A. F., Goncharova Yu. A., Valeev R. S. Routing Tasks During Transportation: an Overview of Models, Methods and Algorithms. Part 1, Logistics and Supply chain Management, 2019, no. 4 (93), pp. 74—89 (in Russian).

3. Titov B. A. Transport logistics, Samara, Samara University, 2012, 198 p. (in Russian).

4. Toth P., Vigo D. (eds.). Vehicle Routing: Problems, Methods, and Applications, Philadelphia, Society for Industrial and Applied Mathematics, 2014, 481 p., doi: 10.1137/1.9781611973594

5. Melamed I. I., Sergeev S. I., Sigal I. K. The Traveling Salesman Problem. Issues in Theory, Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147—1173 (in Russian).

6. Dantzig G. B., Ramser J. H. The Truck Dispatching Problem, Management Science, 1959, vol. 6, no. 1, pp. 80—91, doi: 10.1287/mnsc.6.1.80.

7. Clarke G., Wright J. W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations research, 1964, vol. 12, no. 4, pp. 568—581.

8. Gutin G., Punnen A. P. ed. The Traveling Salesman Problem and its Variations, NY, Springer, 2007, 850 p.

9. Kubil V. N. A review of the vehicle routing problem generalizations and extensions, Vestnik RGUPS, 2018, vol. 70, no. 2, pp. 97—109 (in Russian).

10. Filimonov A. B., Filimonov N. B. Optimal Routing by UAV Flights in Group Patrolling of the Territory, Journal of Advanced Research in Technical Science, 2023, issue 34, pp. 49—55 (in Russian), doi: 10.26160/2474-5901-2023-34-49-55.

11. Filimonov A. B., Filimonov N. B., Pham Q. P. Planning of Drones Flight of Routes when Group Patrolling of Large Extended Territories, V International Conference on Control in Technical Systems (CTS), Saint Petersburg, 2023, pp. 228—231 (in Russian).

12. Filimonov A. B., Filimonov N. B., Nguyen T. K., Pham Q. P. Planning of UAV Flight Routes in the Problems of Group Patrolling of Extended Territories, Mekhatronika, Avtomatizatsiya,Upravlenie, 2023, vol. 24, no. 7, pp. 374—381 (in Russian), doi: 10.17587/mau.24.374-381.

13. Filimonov A. B., Filimonov N. B. The problem of group patrolling of extended territories with multiple depots, Journal of Advanced Research in Technical Science, 2023, iss. 37, pp. 42—51 (in Russian), doi: 10.26160/2474-5901-2023-37-42-51.

14. Filimonov A. B., Filimonov N. B. Planning of UAV flight routes during group patrolling of extended territories, XIV AllRussian Meeting on Control Problems (VSPU-2024), Collection of works, Moscow, IPU RAS, 2024, pp. 1138—1142 (in Russian).

15. Filimonov A. B., Filimonov N. B., Nguyen T. K., Pham Q. P. Optimization of UAV Flight Routes During Group Patrolling of Extended Territories as a Multiple Task of a Traveling Salesman with Several Depots, Mekhatronika, Avtomatizatsiya, Upravlenie, 2024, vol. 25, no. 5, pp. 259—265 (in Russian), doi: 10.17587/mau.25.259-265

16. Bektas T. The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures, OMEGA: The International Journal of Management Science, 2006, vol. 34, iss. 3, pp. 209—219.

17. Cheikhrouhou O., Khoufi I. A Comprehensive Survey on the Multiple Traveling Salesman Problem: Applications, Approaches and Taxonomy, Comput. Sci. Rev., 2021, vol. 40, no. 100369, pp. 76, doi: 10.1016/j.cosrev.2021.100369.

18. Filimonov A. B., Nguyen T. K. A Cluster Method for Solving a Multiple Traveling Sales-man Problem with Several Depots, Journal of Advanced Research in Natural Science, 2024, iss. 19, pp. 4—10 (in Russian), doi: 10.26160/2572-4347-2024-19-4-10.

19. Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a Large-Scale Traveling Salesman Problem, Operation Research, 1954, vol. 2, pp. 393—410, doi: 10.1287/opre.2.4.393.

20. Miller C. E., Tucker A. W., Zemlin R. A. Integer Programming Formulation of Traveling Salesman Problems, Journal of the ACM, 1960, vol. 7, no. 4, pp. 326—329, doi: 10.1145/321043.321046.

21. Gendreau M., Gilbert L., Jean-Yves P. Vehicle Routing: Modern Heuristics, Local Search in Combinatorial Optimization, Princeton, Princeton University Press, 2003, pp. 311—336, doi: 10.1515/9780691187563-012.

22. Şahin Y., Eroğlu A. Metaheuristic Methods for Capacitated Vehicle Routing Problem: Literature Review, Suleyman Demirel University: The Journal of Faculty of Economics and Administrative Sciences, 2014, vol. 19, no. 4, pp. 337—355.

23. Labadie N., Prins C., Prodhon C. Metaheuristics for Vehicle Routing Problems, Computer engineering series Computer engineering series. Metaheuristics set (vol. 3), John Wiley & Sons, 2016, 194 p., doi: 10.1002/9781119136767.

24. Singh D. R., Singh M. K., Singh T., Prasad R. Genetic Algorithm for Solving MTSP using a New Crossover and Population Generation, Computación y Sistemas, 2018, vol. 22, no. 2, pp. 491—503, doi: 10.13053/cys-22-2-2956.

25. Kureichik V. M., Logunova J. A. The Genetic Algorithm Application Prospects Analysis for the Traveling Salesman Problem Solution, Information technologies, 2018, vol. 24, no. 11, pp. 691—697 (in Russian), doi: 10.17587/it.24.691-697.

26. Ghoseiri K., Ghannadpour S. A Hybrid Genetic Algorithm for Multi-Depot Homogenous Locomotive Assignment with Time Windows, Appl. Soft Comput., 2010, vol. 10, pp. 53—65, doi: 10.1016/j.asoc.2009.06.004.

27. Karakatič S., Podgorelec V. A Survey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem, Applied Soft Computing, 2015, vol. 27, pp. 519—532, doi: 10.1016/j.asoc.2014.11.005.

28. Savelyev M. V., Engibaryan I. A. Solving Problems of Integer Programming Based on Genetic Algorithms, Izvestiya vuzov. North Caucasian region natural sciences. Application, 2005, no. 9, pp. 18—21 (in Russian).

29. Liu Y., Li H., Chen H. A Genetic Algorithm for Solving Linear Integer Bilevel Programming Problems, 2018 14th International Conference on Computational Intelligence and Security (CIS), Hangzhou, China, 2018, pp. 40—44, doi: 10.1109/CIS2018.2018.00017.

30. Laporte G., Nobert Y., Arpin D. Optimal Solutions to Capacitated Multi Depot Vehicle Routing Problems, Congressus Numerantium, 1984, vol. 44, pp. 283—292.

31. Dutta S., Bhattacharya S. A Short Review of Clustering Techniques, International Journal of Advanced Research in Management and Social Sciences, 2015, vol. 4, no. 5, pp. 132—139.

32. Berkhin P. A Survey of Clustering Data Mining Techniques, Grouping Multidimensional Data, Springer, 2006, pp. 25—71, doi: 10.1007/3-540-28349-8.

33. Jain A. K. Data Clustering: 50 years Beyond K-means, Pattern Recognition Letters. 2010, vol. 31, no. 8, pp. 651—666, doi: 10.1016/j.patrec.2009.09.011.

34. Ikotun A. M., Ezugwu A. E., Abualigah L., Abuhaija B., Heming J. K-means Clustering Algorithms: A Comprehensive Review, Variants Analysis, and Advances in the Era of Big Data, Information Sciences, 2023, vol. 622, pp. 178—210, doi: 10.1016/j.ins.2022.11.139.

35. Xu X., Yuan H., Liptrott M. et al. Two Phase Heuristic Algorithm for the Multiple-Travelling Salesman Problem, Soft Comput., 2018, vol. 22, pp. 6567—6581, doi: 10.1007/s00500-017-2705-5.

36. Hasanov I. M., Goltsov I. S. Development of a Two-Phase Cluster Algorithm for Solving the Problem of Transport Routing, Innovation. Science. Education, 2022, no. 50, pp. 2366—2382.

37. Gillett B. E., Miller L. R. A Heuristic Algorithm for the Vehicle-Dispatch Problem, Operations Research, 1974, vol. 22, no. 2, pp. 340—349, doi: 10.1287/opre.22.2.340.

38. Bodin L. D. A Taxonomic Structure for Vehicle Routing and Scheduling Problems, Computers &Urban Society, 1975, vol. 1, no. 1, pp. 11—29, doi: 10.1016/0305-7097(75)90003-4.

39. Garside A. K., Laili N. R. A Cluster-First Route-Second Heuristic Approach to Solve the Multi-Trip Periodic Vehicle Routing Problem, Jurnal Teknik Industri, 2019, vol. 20, no. 2, pp.171—181, doi: 10.22219/JTIUMM.Vol20.No2.172-181.

40. Comert S. E., Yazgan H. R. Effective Cluster-First RouteSecond Approaches Using Metaheuristic Algorithms for the Capacitated Vehicle Routing Problem, International Journal of Industrial Engineering: Theory, Applications and Practice, 2021, vol. 28, no. 1, pp. 14—38.

41. Beasley J. E. Route First — Cluster Second Methods for Vehicle Routing, Omega, 1983, vol. 11, iss. 4, pp. 403—408, doi: 10.1016/0305-0483(83)90033-6.

42. Ekiz M. K., Bozdemir M., Türkkan B. Ö. Route First — Cluster Second Method for Personal Service Routing Problem, Journal of Engineering Studies and Research, 2019, vol. 25, no. 2, pp. 18—24, doi: 10.29081/jesr.v25i2.31.

43. Chisman J. A. The Clustered Traveling Salesman Problem, Computers & Operations Research, 1975, no. 2, pp. 115—119, doi: 10.1016/0305-0548(75)90015-5.

44. Lu Y., Hao J.-K., Wu Q. Solving the Clustered Travel ing Salesman Problem via Traveling Salesman Problem Methods, PeerJ Computer Science, 2022, vol. 8, 24 p.

45. Zhang T., Ramakrishnan R., Livny M. BIRCH: a New Data Clustering Algorithm and its Applications, Data Mining and Knowledge Discovery, 1997, vol. 1, iss. 2, pp. 141—182, doi: 10.1023/A:1009783824328.

46. Murray C. C., Raj R. The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones, Transportation Research Part C: Emerging Technologies, 2020, vol. 110, pp. 368—398, doi: 10.1016/j.trc.2019.11.003.

47. Mashnenkov D. V. Prospects for the Use of UAV in Lgistics, Innovation and investment, 2023, no. 6, pp. 168—171 (in Russian).