A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP

The convex hull cheapest insertion heuristic is known to produce good solutions to the Traveling Salesperson Problem in Euclidean spaces, but it has not been extended to the non-Euclidean case. The proposed adaptation uses multidimensional scaling to first project the points into a Euclidean space, thereby enabling the generation of the convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding impassable separators to the TSPLIB benchmark data-set, or by using the L1 norm as a metric. This adapted heuristic is demonstrated to outperform the commonly used Nearest Neighbor heuristic and Nearest Insertion heuristic in 89% and 99% of the cases studied, respectively. When the genetic algorithm and ant colony optimization algorithms are provided 1 minute of computation time, the proposed heuristic tour costs are lower than the mean metaheuristic solutions found in 87% and 95% of the instances, respectively.