Research Article
BibTex RIS Cite

A Novel Heuristic For The Traveling Salesman Problem: maxS

Year 2022, , 665 - 677, 16.05.2022
https://doi.org/10.21205/deufmd.2022247129

Abstract

In this study, a new initial solution heuristic was proposed for the traveling salesman problem. The proposed maxS method is based on a new distance matrix obtained by normalizing the distance matrix of the problem being addressed according to the maximum row value. The proposed method was tested on 20 small and 11 large-scale problems, recommended by Hougardy and Zhong, which are difficult to solve optimally. The same problems were also solved by Greedy, Boruvka, Quick-Boruvka, Nearest-Neighborhood and Lin-Kernighan heuristics working on the Concorde software. Based on the comparisons, it is seen that the recommended maxS heuristic performance was better than that of Greedy and Nearest-Neighborhood heuristics and it showed a similar performance with Boruvka in small-scale problems. When the same comparisons were made for large-scale problems, maxS showed better performance than Quick Boruvka and Nearest-Neighborhood heuristics, on average. The maxS heuristic, which is very effective in terms of solution times, can be proposed as a promising initial solution method.

References

  • Matausek, J., Nesetril, J., 2008. An Invitation to Discrete Mathematics, (2nd edition). Oxford University Press, New York, USA.
  • Papadimitriou, C. H., Steiglitz, K., 1998. Combinatorial Optimization: Algorithms and Complexity, Dover Publications, New York, USA.
  • Cook, W.J., 2012. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, New Jersey, USA.
  • Gass, S.I., Assad, A.A., 2005. An Annotated Timeline of Operations Research: An Informal History, Kluwer Academic Publishers, New York, USA.
  • Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, USA.
  • Cook, W., “The Traveling Salesman Problem”, http://www.math.uwaterloo.ca/tsp/ history/milestone.html, Accessed:20/03/2019.
  • Kim, I.B., Shim, I.J., Zhang, M., 1998. Comparison of TSP algorithms, Project for Models in Facilities Planning and Materials Handling.
  • Helsgaun, K., 2000. “An effective implementation of the Lin–Kernighan traveling salesman heuristic”, European Journal of Operational Research, 126(1): 106–130.
  • Srour, A., Othman, Z.A., Hamdan, A.R., 2014. “A water flow-like algorithm for the travelling salesman problem”, Advances in Computer Engineering, Hindawi Publishing Corporation, 1-14.
  • Abid, M.M., Muhammad, I., 2015. “Heuristic approaches to solve traveling salesman problem”, TELKOMNIKA Indonesian Journal of Electrical Engineering, 15(2): 390-396.
  • Bostamam, J.M., Othman, Z., 2016. “Hybrid water flow-like algorithm with Tabu search for traveling salesman problem”, AIP Conference Proceedings 1761, 020058.
  • Kamarudin, A.A., Othman, Z.A., Sarim, H.M., 2016. “Improvement initial solution water flow like algorithm using simulated annealing for travelling salesman problem”, International Review of Management and Marketing, 6(8): 63-66.
  • Wu, G-H., Cheng, C-Y., Yang, H-I., Chena, C-T., 2018. “An improved water flow-like algorithm for order acceptance and scheduling with identical parallel machines”, Applied Soft Computing, 71, 1072-1084.
  • Demiriz, A., “Solving Traveling Salesman Problem by Ranking”, http://www.ayhandemiriz.com/SakaryaWebSite/papers/benelearn09.pdf, Accessed: 19/03/2019.
  • Lin, S., Kernighan, B.W., 1973. “An Effective Heuristic Algorithm for the Traveling-Salesman Problem”, Operations Research, 21(2): 498–516.
  • Karagül, K. (2019). A Novel Solution Approach for Travelling Salesman Problem: TPORT. DEUFMD, 21(63), 819-832
  • Karagül, K. (2019). A Novel Solution Approach for Travelling Salesman Problem Based on Hungarian Algorithm. Mühendislik Bilimleri ve Tasarım Dergisi , 7 (3) , 561-571 . DOI: 10.21923/jesd.523623
  • Karagül, K . (2019). Prüfer-Karagül Algorithm: A Novel Solution Approach for Travelling Salesman Problem. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi , 6 (2) , 452-470 . DOI: 10.30798/makuiibf.508842
  • Hougardy, S., Zhong, X., 2018. “Hard to Solve Instances of the Euclidean Traveling Salesman Problem”, arXiv:1808.02859 [cs.DM].
  • Helsgaun, K., “Lin-Kernighan-Helsgaun”, http://akira.ruc.dk/~keld/research/LKH/, Accessed:01/03/2019.
  • Hougardy, S., Zhong, X., “Hard to Solve Instances of the Euclidean Traveling Salesman Problem”, http://www.or.uni-bonn.de /~hougardy/HardTSPInstances.html, Accessed: 01/03/2019.
  • Karagul, K., Aydemir, E. and 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), pp.103-113.
  • Şahin, Y. and Karagül, K.,2019. Solving Travelling Salesman Problem Using Hybrid Fluid Genetic Algorithm (HFGA). Pamukkale University Journal of Engineering Sciences, 25(1), pp.106-114.
  • Sahin, Y., Aydemir, E., Karagul, K., Tokat, S. and Oran, B., 2021. Metaheuristics Approaches for the Travelling Salesman Problem on a Spherical Surface. In Interdisciplinary Perspectives on Operations Management and Service Evaluation (pp. 94-113). IGI Global.
  • Aydemir, E., Karagül, K. And Tokat, S., Kapasite Kisitli Araç Rotalama Problemlerinde Başlangiç Rotalarinin Kurulmasi İçin Yeni Bir Algoritma. Mühendislik Bilimleri Ve Tasarım Dergisi, 4(3), Pp.215-226.

Gezgin Satici Problemi Için Yeni Bir Sezgisel:maxS

Year 2022, , 665 - 677, 16.05.2022
https://doi.org/10.21205/deufmd.2022247129

Abstract

Bu çalışmada, gezgin satıcı problemi için yeni bir başlangıç çözüm sezgiseli önerilmiştir. Önerilen maxS metodu, üzerinde çalışılan problemin mesafe matrisinin maksimum satır değerine göre normalize edilmesiyle elde edilen yeni mesafe matrisi ile çalışır. Önerilen metot, Hougardy ve Zhong tarafından tavsiye edilen ve optimal çözümü zor olan 20 küçük ve 11 büyük ölçekte problem üzerinde test edilmiştir. Aynı problemler, Concorde yazılımı üzerinde çalışan Greedy, Boruvka, Quick-Boruvka, Nearest-Neighborhood and Lin-Kernighan sezgiselleri ile de çözülmüştür. Çözümler karşılaştırıldığında küçük ölçekli problemler için maxS sezgiselinin performansının Greedy ve Nearest-Neighborhood sezgisellerinden daha iyi olduğu ve Boruvka ile benzer performansta olduğu gözlenmiştir. Benzer karşılaştırmalar büyük ölçekli problemler için yapıldığında maxS, Quick Boruvka ve Nearest-Neighborhood sezgisellerinden ortalama olarak daha iyi performans göstermiştir. Çözüm zamanları açısından çok etkili olan maxS sezgiseli, gelecek vaadeden başlangıç çözüm yöntemi olarak önerilebilir.

References

  • Matausek, J., Nesetril, J., 2008. An Invitation to Discrete Mathematics, (2nd edition). Oxford University Press, New York, USA.
  • Papadimitriou, C. H., Steiglitz, K., 1998. Combinatorial Optimization: Algorithms and Complexity, Dover Publications, New York, USA.
  • Cook, W.J., 2012. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, New Jersey, USA.
  • Gass, S.I., Assad, A.A., 2005. An Annotated Timeline of Operations Research: An Informal History, Kluwer Academic Publishers, New York, USA.
  • Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, USA.
  • Cook, W., “The Traveling Salesman Problem”, http://www.math.uwaterloo.ca/tsp/ history/milestone.html, Accessed:20/03/2019.
  • Kim, I.B., Shim, I.J., Zhang, M., 1998. Comparison of TSP algorithms, Project for Models in Facilities Planning and Materials Handling.
  • Helsgaun, K., 2000. “An effective implementation of the Lin–Kernighan traveling salesman heuristic”, European Journal of Operational Research, 126(1): 106–130.
  • Srour, A., Othman, Z.A., Hamdan, A.R., 2014. “A water flow-like algorithm for the travelling salesman problem”, Advances in Computer Engineering, Hindawi Publishing Corporation, 1-14.
  • Abid, M.M., Muhammad, I., 2015. “Heuristic approaches to solve traveling salesman problem”, TELKOMNIKA Indonesian Journal of Electrical Engineering, 15(2): 390-396.
  • Bostamam, J.M., Othman, Z., 2016. “Hybrid water flow-like algorithm with Tabu search for traveling salesman problem”, AIP Conference Proceedings 1761, 020058.
  • Kamarudin, A.A., Othman, Z.A., Sarim, H.M., 2016. “Improvement initial solution water flow like algorithm using simulated annealing for travelling salesman problem”, International Review of Management and Marketing, 6(8): 63-66.
  • Wu, G-H., Cheng, C-Y., Yang, H-I., Chena, C-T., 2018. “An improved water flow-like algorithm for order acceptance and scheduling with identical parallel machines”, Applied Soft Computing, 71, 1072-1084.
  • Demiriz, A., “Solving Traveling Salesman Problem by Ranking”, http://www.ayhandemiriz.com/SakaryaWebSite/papers/benelearn09.pdf, Accessed: 19/03/2019.
  • Lin, S., Kernighan, B.W., 1973. “An Effective Heuristic Algorithm for the Traveling-Salesman Problem”, Operations Research, 21(2): 498–516.
  • Karagül, K. (2019). A Novel Solution Approach for Travelling Salesman Problem: TPORT. DEUFMD, 21(63), 819-832
  • Karagül, K. (2019). A Novel Solution Approach for Travelling Salesman Problem Based on Hungarian Algorithm. Mühendislik Bilimleri ve Tasarım Dergisi , 7 (3) , 561-571 . DOI: 10.21923/jesd.523623
  • Karagül, K . (2019). Prüfer-Karagül Algorithm: A Novel Solution Approach for Travelling Salesman Problem. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi , 6 (2) , 452-470 . DOI: 10.30798/makuiibf.508842
  • Hougardy, S., Zhong, X., 2018. “Hard to Solve Instances of the Euclidean Traveling Salesman Problem”, arXiv:1808.02859 [cs.DM].
  • Helsgaun, K., “Lin-Kernighan-Helsgaun”, http://akira.ruc.dk/~keld/research/LKH/, Accessed:01/03/2019.
  • Hougardy, S., Zhong, X., “Hard to Solve Instances of the Euclidean Traveling Salesman Problem”, http://www.or.uni-bonn.de /~hougardy/HardTSPInstances.html, Accessed: 01/03/2019.
  • Karagul, K., Aydemir, E. and 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), pp.103-113.
  • Şahin, Y. and Karagül, K.,2019. Solving Travelling Salesman Problem Using Hybrid Fluid Genetic Algorithm (HFGA). Pamukkale University Journal of Engineering Sciences, 25(1), pp.106-114.
  • Sahin, Y., Aydemir, E., Karagul, K., Tokat, S. and Oran, B., 2021. Metaheuristics Approaches for the Travelling Salesman Problem on a Spherical Surface. In Interdisciplinary Perspectives on Operations Management and Service Evaluation (pp. 94-113). IGI Global.
  • Aydemir, E., Karagül, K. And Tokat, S., Kapasite Kisitli Araç Rotalama Problemlerinde Başlangiç Rotalarinin Kurulmasi İçin Yeni Bir Algoritma. Mühendislik Bilimleri Ve Tasarım Dergisi, 4(3), Pp.215-226.
There are 25 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Research Article
Authors

Kenan Karagül 0000-0001-5397-4464

Gürhan Gündüz 0000-0002-0719-2688

Publication Date May 16, 2022
Published in Issue Year 2022

Cite

APA Karagül, K., & Gündüz, G. (2022). A Novel Heuristic For The Traveling Salesman Problem: maxS. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, 24(71), 665-677. https://doi.org/10.21205/deufmd.2022247129
AMA Karagül K, Gündüz G. A Novel Heuristic For The Traveling Salesman Problem: maxS. DEUFMD. May 2022;24(71):665-677. doi:10.21205/deufmd.2022247129
Chicago Karagül, Kenan, and Gürhan Gündüz. “A Novel Heuristic For The Traveling Salesman Problem: MaxS”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi 24, no. 71 (May 2022): 665-77. https://doi.org/10.21205/deufmd.2022247129.
EndNote Karagül K, Gündüz G (May 1, 2022) A Novel Heuristic For The Traveling Salesman Problem: maxS. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 24 71 665–677.
IEEE K. Karagül and G. Gündüz, “A Novel Heuristic For The Traveling Salesman Problem: maxS”, DEUFMD, vol. 24, no. 71, pp. 665–677, 2022, doi: 10.21205/deufmd.2022247129.
ISNAD Karagül, Kenan - Gündüz, Gürhan. “A Novel Heuristic For The Traveling Salesman Problem: MaxS”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 24/71 (May 2022), 665-677. https://doi.org/10.21205/deufmd.2022247129.
JAMA Karagül K, Gündüz G. A Novel Heuristic For The Traveling Salesman Problem: maxS. DEUFMD. 2022;24:665–677.
MLA Karagül, Kenan and Gürhan Gündüz. “A Novel Heuristic For The Traveling Salesman Problem: MaxS”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, vol. 24, no. 71, 2022, pp. 665-77, doi:10.21205/deufmd.2022247129.
Vancouver Karagül K, Gündüz G. A Novel Heuristic For The Traveling Salesman Problem: maxS. DEUFMD. 2022;24(71):665-77.

Dokuz Eylül Üniversitesi, Mühendislik Fakültesi Dekanlığı Tınaztepe Yerleşkesi, Adatepe Mah. Doğuş Cad. No: 207-I / 35390 Buca-İZMİR.