Novel Concave Hull-Based Heuristic Algorithm For TSP

Kemal Ihsan Kilic () and Leonardo Mostarda ()
Additional contact information
Kemal Ihsan Kilic: Univ. of Camerino
Leonardo Mostarda: Univ. of Camerino

SN Operations Research Forum, 2022, vol. 3, issue 2, 1-45

Abstract: Abstract We presented a novel deterministic concave hull-based heuristic algorithm for Euclidean symmetric TSP (Traveling Salesman Problem). The algorithm iteratively creates concentric concave hulls and in a heuristic way merges them into a single tour. We introduced a new metric called the Average Waiting Distance (AWD) of a tour which is an important optimization objective concerning the “cities.” Related to AWD, we also introduced another new metric called “min AWD” of a tour which is the minimum AWD when all the “rotations” and “directions” of a tour are considered. In experiments, we saw that the cost-optimum tour known so far does not guarantee optimum AWD or optimum min AWD. Benchmarks are carried out including various standard approximation algorithms by using standard TSPLIB and custom datasets. We performed preliminary statistical analysis on the datasets for classification purposes. The proposed algorithm offered a balanced compromise in performance metrics considered in the benchmarks compared to other algorithms. Especially for the lattice-based (hex) configuration of the cities, the proposed algorithm performed better in finding the shortest TSP tour with minimum AWD and with shorter running time. We investigated the percentages of the edges in the optimum and in the approximate TSP tours that are coming from the Delaunay Triangulation. Quantitative analysis is carried out, and the savings from the proposed heuristics are tabulated.

Keywords: Combinatorial optimization heuristics; Computational geometry; Concave hull; Delaunay triangulation; TSP heuristic algorithms; TSP approximation algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-022-00137-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:3:y:2022:i:2:d:10.1007_s43069-022-00137-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-022-00137-9

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().