Please use this identifier to cite or link to this item: https://hdl.handle.net/11499/50663
Title: A Novel Heuristic For The Traveling Salesman Problem: maxS
Authors: Gündüz, Gürhan
Karagül, Kenan
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. Keywords: Traveling Salesman Problem, maxS, Boruvka, Nearest-Neighborhood, Lin-Kernighan, Initial Solutions
URI: https://doi.org/10.21205/deufmd.2022247129
https://search.trdizin.gov.tr/yayin/detay/1111905
https://hdl.handle.net/11499/50663
ISSN: 1302-9304
2547-958X
Appears in Collections:TR Dizin İndeksli Yayınlar Koleksiyonu / TR Dizin Indexed Publications Collection
Uygulamalı Bilimler Fakültesi Koleksiyonu

Files in This Item:
File SizeFormat 
document - 2024-03-18T143816.230.pdf1.25 MBAdobe PDFView/Open
Show full item record



CORE Recommender

Page view(s)

66
checked on Aug 24, 2024

Download(s)

26
checked on Aug 24, 2024

Google ScholarTM

Check




Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.