COMPARING THE SOLUTION PERFORMANCES OF THE HEURISTIC AND METAHEURISTIC ALGORITHMS IN TRAVELLING SALESMAN PROBLEM

Year 2019, Volume: 19 Issue: 4, 911 - 932, 31.12.2019

Yusuf Şahin

https://doi.org/10.11616/basbed.v19i51339.558208

Cited By: 6

Abstract

The Traveling Salesman Problem is the problem
of identifying a route that will enable a salesman to visit all the cities only
once in the list where the cities are located, to start and to return the city
where he lives by traveling the shortest distance. In this study, the solution
performances of a series of heuristic and metaheuristic methods in Travelling Salesman
Problem is compared. Within the scope of the study, the nearest neighbor and
2-Opt methods were used as heuristic methods, and the Ant Colony Optimization,
Tabu Search, Simulated Annealing and Genetic Algorithm methods were used as
metaheuristic methods. As a result of the experiments conducted with 16 data
sets, it was determined that the integrated method consisting of the Nearest
Neighbor and 2-Opt heuristics provide the best solutions in terms of average
solution values and times.

Keywords

Traveling Salesman Problem, Heuristic, Metaheuristic

SEZGİSEL VE METASEZGİSEL YÖNTEMLERİN GEZGİN SATICI PROBLEMİ ÇÖZÜM PERFORMANSLARININ KIYASLANMASI

Abstract

Bu çalışmanın amacı, sezgisel ve metasezgisel yöntemlerin Gezgin Satıcı
Problemi çözüm performanslarının çözüm değeri ve süresi bakımından değerlendirilmesidir.
Çalışma kapsamında, sezgisel yöntem olarak bütünleşik En Yakın Komşu (EYK) ve
2-Opt sezgiseli, metasezgisel yöntem olarak ise karınca kolonisi optimizasyon,
tabu arama, benzetilmiş tavlama ve genetik algoritma yöntemleri kullanılmıştır.
16 adet veri seti ile yapılan deneyler, ortalama çözüm değerleri ve süreleri
bakımından EYK+2-Opt bütünleşik yönteminin en iyi çözümleri sağladığını
göstermiştir. Sonuç olarak, EYK+2-Opt yönteminin Gezgin Satıcı Probleminin
çözümünde hızlı ve etkin çözümler üretebilen kullanışlı bir yöntem olduğu ortaya
konmuştur.  

Keywords

Gezgin Satıcı Problemi, Sezgisel, Metasezgisel

References

• Ahmadi, A., El Bouanani, F. ve Ben-Azza, H. (2014), Four Parallel Decoding Schemas of Product BlockCodes,Transactions on Networks and Communications, 2(3), s.49-69.
• Alshamsi, A. ve Diabat, A. (2017), A Genetic Algorithm for Reverse Logistics Network Design: A Case Study From the GCC, Journal of Cleaner Production, 151, s.652-669.
• Antosiewicz, M., Koloch, G. ve Kamiński, B. (2013), Choice of best possible Metaheuristic Algorithm for the Travelling Salesman Problem with Limited Computational Time: Quality, Uncertainty and Speed, Journal of Theoretical and Applied Computer Science, 7(1), s.46-55.
• Archetti, C., Speranza, M. G. ve Hertz, A. (2006), A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem, Transportation Science, 40(1), s.64-73.
• Aycan, E. ve Ayav, T. (2009), Solving the Course Scheduling Problem Using Simulated Annealing, 2009 IEEE International Advance Computing Conference, Patiala, India.
• Barbarosoglu, G. ve Özgur, D. (1999), A Tabu Search Algorithm for the Vehicle Routing Problem, Computers&Operations Research, 26(3), s.255-270.
• Bilge, Ü., Kıraç, F., Kurtulan, M. ve Pekgün, P. (2004), A Tabu Search Algorithm for Parallel Machine Total Tardiness Problem, Computers & Operations Research, 31(3), s.397-414.
• Bouzidi, S., Riffi, M. E. ve Bouzidi, A. (2017), Comparative analysis of Three Metaheuristics for Solving the Travelling Salesman Problem, Transactions on Machine Learning and Artificial Intelligence, 5(4), s.395-402.
• Burke E.K., Cowling P.I. ve Keuthen R. (1999), New Models and Heuristics for Component Placement in Printed Circuit Board Assembly, 1999 International Conference on Information Intelligence and Systems, Bethesda, Maryland.
• Chowdhury, A., Ghosh, A., Sinha, S., Das, S. ve Ghosh, A. (2013), A Novel Genetic Algorithm to Solve Travelling Salesman Problem and Blocking Flow Shop Scheduling Problem, International Journal of Bio-Inspired Computation, 5(5), s.303-314.
• Correia, M. H., Oliveira, J. F. ve Ferreira, J. S. (2000), Cylinder Packing by Simulated Annealing, Pesquisa Operacional, 20(2): 269-286.
• Cunha, M. D. C. ve Sousa, J. (1999), Water Distribution Network Design Optimization: Simulated Annealing Approach, Journal of Water Resources Planning and Management, 125(4), s.15-221.
• Dantzig, G., Fulkerson, R. ve Johnson, S. (1954), Solution of a Large-Scale Traveling-Salesman Problem, Journal of the Operations Research Society of America, 2(4), s.393-410.
• Deng, Y., Liu, Y. ve Zhou, D. (2015), An Improved Genetic Algorithm -with Initial Population Strategy for Symmetric TSP, Mathematical Problems in Engineering, 2015, s.1-6.
• Dikmen, H., Dikmen, H., Elbir, A., Eksi, Z. ve Çelik, F. (2014), Gezgin Satıcı Probleminin Karınca Kolonisi ve Genetik Algoritmalarla Eniyilemesi ve Karşılaştırılması, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 18(1), s.8-13.
• Ding, Y. ve Fu, X. (2016), Kernel-Based Fuzzy C-Means Clustering Algorithm Based on Genetic Algorithm, Neurocomputing, 188, s.33-238.
• Dorigo, M., Maniezzo, V. ve Colorni, A. (1991), Ant System: An Autocatalytic Optimizing Process, Politecnico di Milano: https://pdfs.semanticscholar.org/9649/211474dcfc3a9fd75e5208ffd21d9dcb9794.pdf, ErişimTarihi: (18.12.2018)
• Dorigo, M. ve Gambardella, L.M. (1997), Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on evolutionary computation, 1(1), s.53-66.
• Dorigo, M. ve Stützle, T. (2019), Ant Colony Optimization: Overview and Recent Advances (Eds: M. Gendreau, J.-Y. Potvin), Handbook of Metaheuristics, s.311-351, Springer, Cham.
• Fiechter, C. N. (1994), A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems, Discrete Applied Mathematics, 51(3), s.243-267.
• Freisleben, B. ve Merz, P. (1996), A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems, IEEE International Conference on Evolutionary Computation, Nagoya.
• Fuellerer, G., Doerner, K.F., Hartl, R.F. ve Iori, M. (2009), Ant Colony Optimization for the Two-Dimensional Loading Vehicle Routing Problem, Computers & Operations Research, 36(3), s.655-673.
• Gambardella, L. M. ve Dorigo, M. (2000), An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem, INFORMS Journal on Computing, 12(3), s.237-255.
• Gendreau M., Laporte G. ve Semet F. (1998), A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem, European Journal of Operational Research, 106 (2-3), s.539-545.
• Gendreau, M., Iori, M., Laporte, G. ve Martello, S. (2006), A Tabu Search Algorithm for a Routing And Container Loading Problem”, Transportation Science, 40(3), s.342-350.
• Gilli, M., Maringer, D. ve Schumann, E. (2011), Numerical Methods and Optimization in Finance. San Diago: Academic Press.
• Glover, F. ve Laguna, M. (1989), Tabu Search-Part I, ORSA Journal on Computing, 1 (3), s.190-206.
• Glover, F. ve Laguna, M. (1997),Tabu Search (First Edition). Massachusetts: Kluwer Academic Publishers.
• Grabowski, J. ve Wodecki, M. (2004), A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion, Computers & Operations Research, 31(11), s.1891-1909.
• Gupta, D. (2013), Solving tsp using various meta-heuristic algorithms, International Journal of Recent Contributions from Engineering, Science & IT (iJES), 1(2), s.22-26.
• Gupta, S. ve Panwar, P. (2013), Solving Travelling Salesman Problem Using Genetic Algorithm, International Journal of Advanced Research in Computer Science and Software Engineering, 3(6), s.376-380.
• Halim, A. H. ve Ismail, I. (2019), Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem, Archives of Computational Methods in Engineering, 26(2), s.367-380.
• Hiassat, A., Diabat, A. ve Rahwan, I. (2017), A Genetic Algorithm Approach for Location-Inventory-Routing Problem with Perishable Products, Journal of manufacturing systems, 42, s.93-103.
• Hoffman K.L. ve Padberg M. (1993), Solving Airline Crew Scheduling Problems by Branch-and-Cut, Management Science, 39(6), s.657-682.
• İnak, N., Tokat, S. ve Karagül, K. (2018),Alt Sınır Temeline Dayalı Ağırlıklı Tavlama Yöntemi ile Kutulama Probleminin Çözümü, Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 5(3), s.549-567.
• Johnson, D. S., Aragon, C. R., McGeoch, L. A. ve Schevon, C. (1989), Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, Operations research, 37(6), s.865-892.
• Joines, J.A., Kay, M.G., Karabacak, M.F., Karagül, K. ve Tokat, S., (2017), Performance Analysis of Genetic Algorithm Optimization Toolbox via Traveling Salesperson Problem, (Ed.: W. Sayers), Contemporary Issues in Social Sciences and Humanities, Landon: AGP Academic Research.
• Kadri, R.L. ve Boctor, F.F. (2018), An Efficient Genetic Algorithm to Solve the Resource-Constrained Project Scheduling Problem with Transfer Times: The Single Mode Case, European Journal of Operational Research, 265(2), s.454-462.
• Karaboğa, D. (2011), Yapay Zeka Optimizasyon Algoritmaları, 2. Baskı, İstanbul: Nobel Yayın Dağıtım.
• Karagul K., Aydemir E. ve Tokat S. (2016),Using 2-Opt Based Evolution Strategy for Travelling Salesman Problem, An International Journal of Optimization and Control: Theories&Applications (IJOCTA), 6(2), s.103-113.
• Kirk, J. (2014), Traveling Salesman Problem -GeneticAlgorithm, https://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm, (Erişim Tarihi: 25.02.2019)
• Kirkpatrick, S., Gelatt, C.D. ve Vecchi, M.P. (1983), Optimization by Simulated Annealing. Science, 220(4598), s.671-680.
• Kulak, O., Sahin, Y. ve Taner, M. E. (2012), Joint Order Batching And Picker Routing in Single and Multiple-Cross-Aisle Warehouses Using Cluster-Based Tabu Search Algorithms, Flexible Services And Manufacturing Journal, 24(1), s.52-80.
• Leung, S. C., Zheng, J., Zhang, D. ve Zhou, X. (2010), Simulated Annealing for the Vehicle Routing Problem with Two-Dimensional Loading Constraints, Flexible Services and Manufacturing Journal, 22(1-2), s.61-82.
• Li, X. ve Gao, L. (2016), An Effective Hybrid Genetic Algorithm and Tabu Search for Flexible Job Shop Scheduling Problem, International Journal of Production Economics, 174, s.93-110.
• Lim, Y.F., Hong, P.Y., Ramli, R., Khalid, R. ve Baten, M.A. (2016), Performance Evaluation of Heuristic Methods in Solving Symmetric Travelling Salesman Problems, Journal of Artificial Intelligence, 9(1-3), s.12-22.
• Malek M., Guruswamy M., Pandya M. ve Owens, H. (1989), Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem, Annals of Operations Research, 21(1), s.59-84.
• Maniezzo, V. ve Colorni, A. (1999), The Ant System Applied to the Quadratic Assignment Problem, IEEE Transactions on Knowledge and Data Engineering, 11(5), s.69-778.
• Mavrovouniotis, M. ve Yang, S. (2013), Ant Colony Optimization with Immigrants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors, Applied Soft Computing, 13(10), s.4023-4037.
• Mazzeo S. ve Irene L. (2004), An Ant Colony Algorithm for the Capacitated Vehicle Routing, Electronic Notes in Discrete Mathematics, 18, s.181-186.
• Merkle, D., Middendorf, M. ve Schmeck, H. (2002), Ant Colony Optimization for Resource-Constrained Project Scheduling, IEEE transactions on evolutionary computation, 6(4), s.333-346.
• Metropolis, N., Bivins, R., Storm, M., Turkevich, A., Miller, J. M. ve Friedlander, G. (1958), Monte Carlo Calculations on Intranuclear Cascades, I. Low-energy studies. Physical Review, 110(1), s.185-203.
• Míča, O. (2015), Comparison Metaheuristic Methods by Solving Travelling Salesman Problem, The International Scientific Conference INPROFORUM, University of South Bohemia in ČeskéBudějovice.
• Misevicius, A. (2005), A Tabu Search Algorithm for the Quadratic Assignment Problem, Computational Optimization and Applications, 30(1), s.95-111.
• Mohammed, M.A., Ghani, M.K.A., Hamed, R.I., Mostafa, S.A., Ahmad, M.S. ve Ibrahim, D.A. (2017), Solving Vehicle Routing Problem by Using Improved Genetic Algorithm for Optimal Solution, Journal of Computational Science, 21, s.255-262.
• Nowicki, E. ve Smutnicki, C. (1996), A Fast Taboo Search Algorithm for the Job Shop Problem, Management Science, 42(6), s.797-813.
• Odili, J.B., Kahar, M.N.M., Noraziah, A., Zarina, M. ve Haq, R. U. (2017), Performance Analysis of Nature-inspired Algorithms on the Traveling Salesman’s Problems for Strategic Management, Intelligent Automation&Soft Computing, 1-11.doi:10.1080/10798587.2017.1334370
• Otero, F. E., Freitas, A. A. ve Johnson, C. G. (2008), cAnt-Miner: An Ant Colony Classification Algorithm to Cope with Continuous Attributes, International Conference on Ant Colony Optimization and Swarm Intelligence, Brussels.
• Özcan, U. ve Toklu, B. (2009), Balancing of Mixed-Model Two-Sided Assembly Lines, Computers&Industrial Engineering, 57(1), s.217-227.
• Park, J. ve Kim, B.I. (2010),The School Bus Routing Problem: A Review, European Journal of Operational Research, 202(2), s.311-319.
• Parpinelli, R. S., Lopes, H. S. ve Freitas, A. A. (2002), Data Mining with an Ant Colony Optimization Algorithm, IEEE Transactions on Evolutionary Computation, 6(4), s.321-332.
• Peng, J., Sun, Y. ve Wang, H. F. (2006), Optimal PMU Placement for Full Network Observability Using Tabu Search Algorithm, International Journal of Electrical Power&Energy Systems, 28(4), s.223-231.
• Potvin, J.Y. (1996), Genetic Algorithms for the Traveling Salesman Problem, Annals of Operations Research, 63(3), s.337-370.
• Ramírez-Rosado, I.J. ve Domínguez-Navarro, J.A. (2006), New Multiobjective Tabu Search Algorithm for Fuzzy Optimal Planning of Power Distribution Systems, IEEE Transactions on Powersystems, 21(1), s.224-233.
• Randall M. ve Montgomery J. (2003),The Accumulated Experience Ant Colony for the Traveling Salesman Problem, International Journal of Computational Intelligence and Applications, 3(2), s.189–198.
• Ratliff H.D. ve Rosenthal A.S. (1983), Order Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem, Operations Research, 31(3), s.507-521.
• Reimann, M., Doerner, K. ve Hartl, R.F., (2004), D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem, Computers& Operations Research, 31(4), s.563–59.
• Romero, R., Gallego, R. A. ve Monticelli, A. (1995), Transmission System Expansion Planning by Simulated Annealing, Power Industry Computer Applications Conference, Salt Lake City, UT.
• Selim, S. Z. ve Alsultan, K. (1991), A Simulated Annealing Algorithm for the Clustering Problem, Pattern Recognition, 24(10), s.1003-1008.
• Shi, Y., Boudouh, T. ve Grunder, O. (2017), A Hybrid Genetic Algorithm for a Home Healthcare Routing Problem with Time Window and Fuzzy Demand, Expert Systems with Applications, 72, s.60-176.
• Shukla, A. P. ve Tiwari, R. (2017), Discrete Problems in Nature Inspired Algorithms. Florida: CRC Press.
• Socha, K., Knowles, J. ve Sampels, M. (2002), A Max-Min Ant System for the University Course Timetabling Problem, Third International Workshop, ANTS 2002, Brussels, Belgium.
• Socha, K., Sampels, M. ve Manfrin, M. (2003), Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art, Workshops on Applications of Evolutionary Computation, Essex.
• Socha, K. ve Dorigo, M. (2008), Ant Colony Optimization for Continuous Domains, European Journal of Operational Research, 185(3), s.1155-1173.
• Stüzle T. ve Hoos H. (1997), MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, Reference Future Generations Computer Systems, 16(8), s.889–914.
• Şahin Y. (2014), Depo Operasyonları ve Sipariş Dağıtım Faaliyetlerinin Sezgisel Yöntemler Kullanarak Eş ZamanlıOptimizasyonu, Yayınlanmamış Doktora Tezi, Süleyman Demirel Üniversitesi, Isparta, Türkiye.
• Şahin, Y. ve Karagül, K. (2019), Gezgin Satıcı Probleminin Melez Akışkan Genetik Algoritma (MAGA) Kullanarak Çözümü, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1): s.106-114.
• Tavakkoli-Moghaddam, R., Safaei, N., Kah, M. M. O. ve Rabbani, M. (2007), A New Capacitated Vehicle Routing Problem with Split Service for Minimizing Fleet Cost by Simulated Annealing, Journal of the Franklin Institute, 344(5), s.406-425.
• Thamilselvan, R. ve Balasubramanie, P. (2009), A Genetic Algorithm with a Tabu Search (GTA) for Traveling Salesman Problem, International Journal of Recent Trends in Engineering, 1(1), s.607.
• Türkay, B., Küçüktezcan, F. ve Bulut, A. (2011), Elektrik Enerjisinin Bölgeler Arası Alışverişinin Optimizasyonu, EMO Bilimsel Dergi, 1(1), s.31-38.
• Van Laarhoven, P.J. ve Aarts, E. H. (1987), Simulated annealing. In Simulated annealing: Theory and Applications, Dordrecht: Springer,
• Wang K.P., Huang L., Zhou C.G. ve Pang W. (2003), Particle Swarm Optimization for Traveling Salesman Problem, International Conference on Machine Learning and Cybernetics, Xi'an.
• Wang, Y., Tian, D. ve Li, Y. (2013), An Improved Simulated Annealing Algorithm for Traveling Salesman Problem, International Conference on Information Technologyand Software Engineering, Beijing.
• Xiao, Y. ve Konak, A. (2017), A Genetic Algorithm with Exact Dynamic Programming for the Green Vehicle Routing & Scheduling Problem, Journal of Cleaner Production, 167, s.1450-1463.
• Yu Z., Jinhai L., Guochang G., Rubo Z. ve Haiyan Y. (2002), An Implementation of Evolutionary Computation for Path Planning of Cooperative Mobile Robots, 4th World Congress on Intelligent Control and Automation, Shanghai.
• Yuan, X., Elhoseny, M., El-Minir, H. K. ve Riad, A. M. (2017), A Genetic Algorithm-Based, Dynamic Clustering Method Towards Improved WSN Longevity, Journal of Network and Systems Management, 25(1), s.21-46.
• Zhao F., Li S, Sun J. ve Mei D. (2009), Genetic Algorithm for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem, Computers & Industrial Engineering, 56(4), s.1642-1648