Novel Concave Hull-Based Heuristic Algorithm For TSP

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.