A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
This work addresses a specific algorithmic gap in operations research for non-Euclidean TSP applications, but it is incremental as it adapts an existing heuristic to new metric spaces.
The paper tackles the problem of extending the convex hull cheapest insertion heuristic to non-Euclidean Traveling Salesperson Problems by using multidimensional scaling to project points into Euclidean space, achieving competitive solutions with up to 5% improvement over baseline methods in experiments.
The convex hull cheapest insertion heuristic produces good solutions to the Euclidean Traveling Salesperson Problem, but it has never been extended to the non-Euclidean problem. This paper uses multidimensional scaling to first project the points from a non-Euclidean space into a Euclidean space, enabling the generation of a convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding separators to the TSPLIB data-set, or by using the L1 norm as a metric.