İki Amaçlı Çoklu Gezgin Satıcı Problemi için Üç Aşamalı Çözüm Yaklaşımı

Year 2021, Issue: 26 - Ejosat Special Issue 2021 (HORA), 325 - 331, 31.07.2021

Beyza Gunesen , Muzaffer Kapanoğlu

https://doi.org/10.31590/ejosat.952103

Cited By: 1

Abstract

Çoklu gezgin satıcı problemlerinin (ÇGSP) çözümünde karşılaşılan güçlükler literatürde oldukça uzun bir geçmişe sahiptir. Çoklu gezgin satıcı problemi çalışmalarında etkin ve başarılı sonuçların tespiti ve tartışılabilirliği için iki tür ölçüt kullanılmaktadır. Bunlar tüm satıcıların kat ettiği toplam uzaklık veya herhangi bir satıcının kat ettiği en uzun mesafe olabilmektedir. Toplam uzaklık temel alındığında satıcılar arasındaki iş yüklerinde önemli dengesizlikler meydana gelmektedir ki bu istenmeyen bir durumdur. En uzun mesafeyi kat eden satıcının kat ettiği mesafe azaltılmak istendiğinde dengesizlik ortadan kalkmakta fakat toplam mesafe (maliyet) dengeyi sağlamak amacıyla artmaktadır. Problem üstel artan bir çözüm uzayına sahip olup NP – zor sınıfında yer almaktadır. Problemin eniyi çözüme ulaştırılmasında önerilen mevcut matematiksel modeller, günlük hayatta çok kısıtlı bir kullanıma sahiptir. Bu durum, pratikte ele alınan probleme özel çözüm yöntemlerini ön plana çıkarmaktadır. Bu bağlamda, üç servis aracı ile insan-topla-dağıt hizmeti yürüten bir işletmenin problemi üzerinde çalışılmıştır. Üçlü gezgin satıcı problemi, ÇGSP’nin satıcı sayısının üç olduğu hali olan bir alt kümesidir. Bu çalışmada, iki enküçükleme amacını da gözeten ve etkin çözümlerin kısa sürelerde elde edilebileceği üç aşamalı çözüm yaklaşımı önerilmiş olup, kümeleme ve rotalama olmak üzere iki ana adımdan oluşmaktadır. Kümeleme adımı, uğrak noktalarını yakınlıklarına göre k – ortalamalar yöntemi ile önce üç gruba ayırmaktadır. Elde edilen kümeler için rotalar başlangıçta En Yakın Komşu Sezgiseli (EYK) ile oluşturulmakta ve daha sonra 2–opt algoritması ile iyileştirilmektedir. Bu çalışmada önerilen yaklaşım çoklu gezgin satıcı problemi için kullanılan test problemlerinde ve rassal türetilen problemlerde uygulanmış ve sonuçlar matematiksel model sonuçları ile karşılaştırılarak ortaya konulmuştur. Herhangi bir satıcının kat edeceği en uzun mesafe, toplam mesafe ve algoritma çözüm süresi, performans ölçütleri olarak belirlenmiştir. Sonuç olarak önerilen ardışık yaklaşım, ilk ölçütte %70–80 oranında en iyi çözümlere yakınsamış, diğer ölçütler de ise daha iyi performans sergilemiştir. Satıcılar arasındaki sapmaların ve toplam mesafenin paralel ödünleşerek enküçüklenmesi noktasında, elde edilen çözümler yüksek seviyeli olup, yaklaşımın koşma süresi polinom zamanlıdır.

Keywords

Çoklu Gezgin Satıcı Problemi, K–ortalamalar, En Yakın Komşu Sezgiseli, 2 – opt algoritması

Three-Step Solution Approach for the Two-Objective Multiple Traveling Salesman Problem

Abstract

The difficulties encountered in solving multi-traveling salesman problems (MTSP) have a long history in the literature. Two types of criteria are used to determine effective and successful outcomes and their arguability in multi-traveling salesman problem studies. These can be the sum of distances traveled by all salesman or the maximum distance traveled by any salesman. Significant imbalances occur in workloads between salesmen based on total distance, which is undesirable. When the distance traveled by the salesman who travels the maximum distance is desired to be reduced, the imbalance disappears, but the total distance (cost) increases to maintain the balance. The problem has an exponentially increasing solution space and is in the NP-hard class. The current mathematical models proposed for solving the problem at its optimum have very limited use in daily life. This brings to the fore the solution methods specific to the problem dealt with in practice. In this context, the problem of business management that runs people pick up and collect service with three vehicles has been studied. The triple traveling salesman problem is a subset of the MTSP where the number of salesmen is three. In this study, a three-phase solution approach, which considers both minimization objectives and which provides effective solutions in a short time, has been proposed. Clustering first divides the pick-up points into three groups according to their proximity with the k-means method. For the clusters obtained, the routes are initially created with the Nearest Neighbor Heuristic (NN) and then improved with the 2 – opt algorithm. The approach proposed in this study was applied to test problems used for the multiple traveling salesman problem and randomly generated problems, and the results were presented by comparing them with the results of the mathematical model. The maximum distance that any salesman will travel, total distance, and algorithm solution time are determined as performance criteria. As a result, the proposed sequential approach converged to the best solutions by 70–80% in the first criterion, outperforming other criteria. At the point where the deviations between salesmen and the total distance are minimized by parallel trade-off, the solutions obtained are of high level and the running time of the approach is polynomial time.

Keywords

Multiple Traveling Salesman Problem, K – means, Nearest Neighbor, 2 – opt algorithm.

References

• Al-Furhud, M. A., & Ahmed, Z. H. (2020). Genetic algorithms for the multiple travelling salesman problem. International Journal of Advanced Computer Science and Applications (IJACSA), 11(7), 553-560.
• Angel, R. D., Caudle, W. L., Noonan, R., & Whinston, A. N. D. A. (1972). Computer-assisted school bus scheduling. Management Science, 18(6), B-279.
• Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
• Carter, A. E. (2003). Design and application of genetic algorithms for the multiple traveling salesperson assignment problem (Doctoral dissertation, Virginia Tech).
• Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations research, 6(6), 791-812.
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
• Gavish, B. (1976). Note—a note on “the formulation of the m-salesman traveling salesman problem”. Management Science, 22(6), 704-705.
• Gilbert, K.C. & Hofstra, R.B. (1992). A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem. Decision Sciences, Vol. 23, pp.250–9.
• Gorenstein, S. (1970). Printing press scheduling for multi-edition periodicals. Management Science, 16(6), B-373.
• Gunesen, Beyza (2021), “Data For: Euclidean Matrix”, Mendeley Data, V1, doi: 10.17632/rvv4ymck92.1
• Huang, Z. (1998). Extensions to the k-means algorithm for clustering large data sets with categorical values. Data mining and knowledge discovery, 2(3), 283-304.
• K. Helsgaun. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic,Department of Computer Science, Roskilde University.
• 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.
• Laporte, G. & Nobert, Y. (1980). A cutting planes algorithm for the m-salesmen problem. Journal of the Operational Research Society, Vol. 31, pp.1017–23.
• Latah, M. (2016). Solving multiple TSP problem by K-means and crossover based modified ACO algorithm. International Journal of Engineering Research and Technology, 5(02).
• Liu, W., Li, S., Zhao, F., & Zheng, A. (2009, May). An ant colony optimization algorithm for the multiple traveling salesmen problem. In 2009 4th IEEE conference on industrial electronics and applications (pp. 1533-1537). IEEE.
• Matai, R., Singh, S. P., & Mittal, M. L. (2010). Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1.
• Matsuura, T., & Numata, K. (2014, September). Solving min-max multiple traveling salesman problems by chaotic neural network. In International Symposium on Nonlinear Theory and its Applications.
• Miller, C.E.; Tucker, A.W. & Zemlin, R.A.(1960). Integer programming formulation of traveling salesman problems. Journal of Association for Computing Machinery, Vol. 7, pp. 326–9.
• Na, S., Xumin, L., & Yong, G. (2010, April). Research on k-means clustering algorithm: An improved k-means clustering algorithm. In 2010 Third International Symposium on intelligent information technology and security informatics (pp. 63-67). Ieee.
• Nallusamy, R., Duraiswamy, K., Dhanalaksmi, R., & Parthiban, P. (2010). Optimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics. International Journal of Nonlinear Science, 9(2), 171-177.
• Necula, R., Breaban, M., & Raschip, M. (2015, November). Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems. In 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 873-880). IEEE.
• Necula, R., Raschip, M., & Breaban, M. (2018). Balancing the subtours for multiple TSP approached with ACS: Clustering-based approaches vs. MinMax formulation. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation VI (pp. 210-223). Springer, Cham.
• Singh, A. (2016). A review on algorithms used to solve multiple travelling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3(4), 598-603.
• Soylu, B. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering, 90, 390-401.
• Svestka, J.A. & Huckfeldt, V.E. (1973). Computational experience with an m-salesman traveling salesman algorithm. Management Science, Vol. 19, No. 7, pp. 790–9.
• Tiong, W. K. (2007). A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem. International Journal of Mathematical and Computational Sciences, 1(1), 13-16.