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

Autonomous robots frequently encounter routing problems that involve non-Euclidean cost considerations due to obstacles, traffic, or a cost function that is not simply the straight-line distance between locations to be visited. Often, the resulting Non-Euclidean Traveling Salesperson Problem (NETSP) must be solved onboard with limited computational resources, posing a significant challenge due to its NP-hard combinatorial nature. To address this, the Adapted Convex Hull Cheapest Insertion (ACHCI) algorithm is proposed. ACHCI is a lightweight heuristic designed for resource-constrained onboard tour computation, with small form factor robots as its target application. ACHCI combines a multidimensional scaling approach with a convex hull initialized tour construction procedure to generalize the well-known Euclidean CHCI heuristic to non-Euclidean problems. Computational experiments on diverse modified TSPLIB scenarios demonstrate that ACHCI outperforms other lightweight heuristics like Nearest Neighbor and Nearest Insertion in 88% and 99% of the cases, as well as population-based metaheuristics such as Genetic Algorithms and Ant Colony Optimization in 87% and 95% of test cases respectively. The adoption of ACHCI for resource-limited onboard routing is expected to enhance the operational efficiency of autonomous agents by reducing travel distance, energy consumption, charging-related downtime, task completion duration and operating costs.