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

arXiv: https://arxiv.org/abs/2302.06582 · HTML: https://mlsanity.com/paper/2302.06582/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 104 references that are in the map.
- First posted on arXiv 5 Feb 2023.

## Builds on (most cited first, 5 of 5)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [A Survey on UAV-enabled Edge Computing: Resource Management Perspective](https://mlsanity.com/paper/2210.06679/) (2022)
- [Efficient Mobility-on-Demand System with Ride-Sharing](https://mlsanity.com/paper/1804.02260/) (2018)
- [Planning for Aerial Robot Teams for Wide-Area Biometric and Phenotypic Data Collection](https://mlsanity.com/paper/2011.01492/) (2020)

## Abstract (arXiv)

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.