OPEN MULTIPLE TRAVELLING SALESMAN PROBLEM AND A SOLUTION PROPOSAL

Abstract

The multiple traveling salesman problem aims to minimize the total cost of m tours while visiting each city only once form sellers who start a tour from a single depot and finish the tour at the same depot. In the open multiple traveling salesman problem, m sellers complete the tour in the city they last visited without returning to the depot. The aim of the problem is to minimize the total travelled distance formed by m sellers. This problem is encountered in the logistics sector, especially in cargo transportation. In this study, a solution is proposed to solve by using open source softwares. First, the cities to be visited by m sellers are determined by the K-Medoids Clustering Algorithm which is an unsupervised machine learning algorithm, and then the routes are formed with the Nearest Neighborhood Algorithm. The performance of the proposed method was tested on datasets with different clustering characteristics such as clustered, random and a hydrid random-clustered dataset from the literature. Its performance was compared with the optimal solutions taken from the Gurobi commercial solver. The results indicate that the proposed method is reasonably successful; however, it exhibits different behaviors on datasets with distinct characteristics.

Keywords

• Open Multiple Travelling Salesman Problem
• Machine Learning
• K-Medoids Algorithm
• Nearest Neighborhood Algorithm.

AÇIK UÇLU ÇOKLU GEZGİN SATICI PROBLEMİ VE BİR ÇÖZÜM ÖNERİSİ

Abstract

Çoklu gezgin satıcı problemi, bir tura tek bir depodan başlayan ve turu depoda bitiren m adet satıcı için her bir şehrin yalnızca bir kez ziyaret edilmesi kısıtı altında, oluşan m adet turun toplam maliyetini minimize etmeyi amaçlar. Açık uçlu çoklu gezgin satıcı probleminde ise, m adet satıcı depoya geri dönme zorunluluğu olmadan, turu en son ziyaret ettikleri şehirde tamamlarlar. Problemin amacı, m adet satıcının oluşturduğu rotaların toplam mesafesinin en küçüklenmesini sağlamaktır. Bu probleme lojistik sektöründe özellikle kargo taşımacılığında rastlanmaktadır. Bu çalışma ile, açık uçlu çoklu gezgin satıcı problemine açık kaynak kodlu yazılımlar kullanılarak bir çözüm önerisinde bulunulmuştur. İlk olarak m adet satıcının gezeceği şehirler denetimsiz makine öğrenmesi algoritmalarından K-Medoids Kümeleme Algoritmasıyla belirlenmiş, ardından En Yakın Komşuluk Algoritması ile rotalar oluşturulmuştur. Önerilen yöntemin başarısı literatürden kümelenmiş, rassal ve hibrid rassal-kümelenmiş olarak sunulmuş özellikler gösteren veri setleri üzerindeki denenerek, performansı Gurobi ticari çözücüsünden alınan optimal çözümlerle karşılaştırılmıştır. Sonuç olarak, önerilen yöntemin kabul edilebilir seviyede başarılı olduğunu ancak, farklı özellikler taşıyan veri setlerinde farklı davranışlar sergilediğini göstermektedir.

Keywords

• Açık Uçlu Gezgin Satıcı Problemi
• Makine Öğrenmesi
• K-Medoids Algoritması
• En Yakın Komşuluk Araması Algoritması.

References

1. Alesiani F., Ermiş G., Konstantinos G., 2022. Constrained Clustering for the Capacitated Vehicle Routing Problem. Applied Artificial Intelligence 36(1).
2. Archetti, C., Speranza, M.G. 2014. A Survey on Matheuristics for Routing Problems. EURO Journal on Computational Optimization, 2, 223–246.
3. Asis L.S., Eduardo C., Grossmann E.I., 2021. A MILP-based Clustering Strategy for Integrating The Operational Management of Crude Oil Supply. Computers & Chemical Engineering, 145.
4. Atefi, R., Salari, M., C. Coelho, L., Renaud, J., 2018. The Open Vehicle Routing Problem with Decoupling Points. European Journal of Operational Research, 265(1), 316–327.
5. Azadeh, A., Farrokhi-Asl, H., 2019. The Close–Open Mixed Multi Depot Vehicle Routing Problem Considering Internal and External Fleet Of Vehicles. Transportation Letters, 11(2), 78–92.
6. Beasley, J.E., 1983. Route First-Cluster Second Methods For Vehicle Routing. Omega, 11(4), 403-408.
7. Bektas, T., 2006. The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures. Omega, 34(3), 209-219.
8. Brandão, J., 2004 . A Tabu Search Algorithm for The Open Vehicle Routing Problem. European Journal of Operational Research, 157(3), 552–564.

9. Cai, Z., Zhang, Z., He, H., 2018. Solving the Last Mile Delivery Problem Using Iterated Local Search Approach. ICNSC 2018 - 15th IEEE International Conference on Networking, Sensing and Control, 1–6.
10. Cheikhrouhou, O., Khoufi, I., 2021. A Comprehensive Survey on the Multiple Traveling Salesman Problem: Applications, Approaches and Taxonomy. Computer Science Review, 40, 100369.
11. Dantzig, G.B., Ramser, J.H. 1959. The Truck Dispatching Problem. Management Science, 6 (1), 80–91.
12. Dondo, R., Cerdá, J., 2007. A Cluster-Based Optimization Approach for the Multidepot Heterogeneous Fleet Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 176, 1478-1507.
13. Effendy, S., Ngo, B. C., Yap, R. H. C., 2021. An Efficient Heuristic for Passenger Bus VRP with Preferences and Tradeoffs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12931 LNCS, 121–127.
14. Effendy, S., Yap, R. H. C., 2022. Real-Time Passenger Bus Routing Problems with Preferences and Tradeoffs. Annals of Mathematics and Artificial Intelligence, 10472.
15. Fan, H., Zhang, X., Ren, X., Liu, P., 2021. Optimization of Multi-Depot Open Split Delivery Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice, 41(6), 1521–1534.
16. Fernando, M., Thibbotuwawa, A., Perera, H.N., Ratnayake, R.M.C., 2022. Close-Open Mixed Vehicle Routing Optimization Model with Multiple Collecting Centers to Collect Farmers' Perishable Produce. International Conference for Advancement in Technology (ICONAT), Goa, India, 1-8.
17. Geetha, S., Poonthalir, G., Vanathi, P.T., 2009. Improved K-Means Algorithm for Capacitated Clustering Problem. INFOCOMP Journal of Computer Science, 8(4), 52-59.
18. Gendreau, M., Laporte, G., Musaraganyi, C., Taillard, E.D., 1999. A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem. Computers& Operations Research, 26, 1153-1173.
19. Guo, X., Samaranayake, S., 2022. Shareability Network Based Decomposition Approach for Solving Large-Scale Single School Routing Problems. Transportation Research Part C: Emerging Technologies, 140, 103691.
20. Günesen, B., Kapanoğlu, M., 2021. İki Amaçlı Çoklu Gezgin Satıcı Problemi için Üç Aşamalı Çözüm Yaklaşımı. Avrupa Bilim ve Teknoloji Dergisi, Ejosat Özel Sayı 2021 (HORA), 325-331.
21. Hopfield, J. J., Tank, D.W., 1985. Neural Computation of Decisions in Optimization Problems. Biological Cybernetics 52(3), 141–152.
22. Hosseinabadi, A. A. R., Vahidi, J., Balas, V. E., Mirkamali, S. S., 2018. OVRP_GELS: Solving Open Vehicle Routing Problem Using the Gravitational Emulation Local Search Algorithm. Neural Computing and Applications, 29(10), 955–968.
23. Hussain Ahmed, Z., Yousefikhoshbakht, M., 2022. An Improved Tabu Search Algorithm for Solving Heterogeneous Fixed Fleet Open Vehicle Routing Problem with Time Windows. Alexandria Engineering Journal, 64, 349-363.
24. Jin, X., Han, J., 2011. K-Medoids Clustering. Editörler: Sammut, C., Webb, G.I., Encyclopedia of Machine Learning, içinde (564-565). Springer, Boston, MA, USA.
25. Kara, I., Bektas, T., 2006. Integer Linear Programming Formulations of Multiple Salesman Problems and Its Variations. European Journal of Operational Research, 174(3), 1449-1458.
26. Kaufman, L., Rousseeuw, P., J., 1990. Partitioning Around Medoids (Program PAM). Wiley Series in Probability and Statistics, Hoboken, NJ, USA: John Wiley & Sons, Inc., 68–125.
27. Lysgaard, J., López-Sánchez, A. D., Hernández-Díaz, A. G., 2020. A Matheuristic for the Min-Max Capacitated Open Vehicle Routing Problem. International Transactions in Operational Research, 27(1), 394–417.
28. Miller, C.E., Tucker, E.W., Zemlin, R.A. 1960. Integer Programming Formulations and Travelling Salesman Problems. Journal of the ACM, 7, 326–329.
29. Montoya, J.A., Guéret, C., Mendoza, J.E., Villegas, J.G., 2014. A Route First Cluster-Second Heuristic for the Green Vehicle Routing Problem. ROADEF 2014, Bordeaux, France.
30. Mor, A., Speranza, M.G., 2020. Vehicle Routing Problems Over Time: A Survey. 4OR-Quarter Journal of Operations Research, 18, 129–149.
31. Mostafa, N., Eltawir, A., 2017. Solving the Heterogeneous Capacitated Vehicle Routing Problem Using K-Means Clustering and Valid Inequalities. Proceedings of the International Conference on Industrial Engineering and Operations Management Rabat, Morocco, April 11-13.
32. Nazari, M., Afshin, O., Snyder, L.V., Takac, M., 2018. Reinforcement Learning for Solving the Vehicle Routing Problem. 2018. Erişim adresi: https://arxiv.org/ abs/1802.04240
33. Oropeza, A., Cruz-Chávez, M., Cruz-Rosal Martín, H., Bernal, P., Abarca J.C., 2012. Unsupervised Clustering Method for the Capacited Vehicle Routing Problem. Ninth Electronics, Robotics and Automotive Mechanics Conference, Mexico. DOI:10.1109/CERMA.2012.41
34. Purusotham, S., Thenepalle, J.K., 2021. An Efficient Genetic Algorithm for Solving Open Multiple Travelling Salesman Problem with Load Balancing Constraint. Decision Science Letters, 10, 525-534.
35. Rautela, A., Sharma, S.K., Bhardwaj, P., 2018. Distribution Planning Using Capacitated Clustering And Vehicle Routing Problem. Journal of Advances in Management Research, 16(5), 781-795.
36. Ropke, S., Pisinger, D., 2006. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40,455-472, 2006.
37. Ruiz, E., Soto-Mendoza, V., Ruiz Barbosa, A. E., Reyes, R., 2019. Solving the Open Vehicle Routing Problem with Capacity and Distance Constraints with a Biased Random Key Genetic Algorithm. Computers and Industrial Engineering, 133, 207–219.
38. Sanlı, O. ve Kartal, Z., 2024.Kapasiteli Araç Rotalama Problemi için Makine Öğrenmesi ve Matematiksel Programlama Temelli Hibrid Bir Çözüm Önerisi. Gazi Üniversitesi Mühendislik Mimarlık Dergisi, 39(2), 741-755.
39. Sariklis, D., Powell, S., 2000. A Heuristic Method for the Open Vehicle Routing Problem. The Journal of the Operational Research Society, 51(5), 564-573.
40. Shao, S., Xu, G., Li, M., 2019. The Design of an Iot-Based Route Optimization System: A Smart Product-Service System (Spss) Approach. Advanced Engineering Informatics, 42, 101006.
41. Solomon, M., 1987. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operation Research, 35, 254-265.
42. Sun, Y., Ernst, A., Li, X., Jake, W., 2021. Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems. OR Spectrum 43, 607–633.
43. Tavakkoli-Moghaddam, R., Meskini, M., Nasseri, H., Tavakkoli-Moghaddam, H., 2019. A Multi-Depot Close and Open Vehicle Routing Problem with Heterogeneous Vehicles. Proceedings of the 2019 International Conference on Industrial Engineering and Systems Management, IESM 2019, 1–6.
44. Thenepalle, J.K., Purusotham, S., 2019. An Open Close Multiple Travelling Salesman Problem with Single Depot. Decision Science Letters, 8, 121-136.
45. Toth, P., Vigo, D. 2014. Vehicle Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization, SIAM, Philedelphia, USA.
46. Wang, Y., Ran, L., Guan, X., Fan, J., Sun, Y., Wang, H., 2022. Collaborative Multicenter Vehicle Routing Problem with Time Windows and Mixed Deliveries and Pickups. Expert Systems with Applications, 197, 116690.
47. Xie, Y., Guo, Y., Zhou, T., Mi, Z., Yang, Y., Sadoun, B., Obaidat, M. S., 2021. A Strategy to Alleviate Rush Hour Traffics in Urban Areas Based on School-Trip Commute Information. IEEE Systems Journal, 15(2), 2630–2641.
48. Google OR-Tools (2023).
49. Erişim Adresi: https://developers.google.com/optimization/routing/routing_options?hl=tr