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

The paper addresses the Non-Euclidean Traveling Salesperson Problem (NETSP), a challenge encountered when "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. Because the NETSP is NP-hard and must often be solved onboard with limited computational resources, posing a significant challenge due to its NP-hard combinatorial nature, the authors propose the Adapted Convex Hull Cheapest Insertion (ACHCI) algorithm."

The ACHCI is described as a lightweight heuristic designed for resource-constrained onboard tour computation, with small form factor robots as its target application. The algorithm 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. The methodology is summarized as follows:

1. Use MDS to obtain 2D Euclidean approximate coordinates that define matrix.

2. Initiate sub-tour as the convex hull nodes of.

3. Find consecutive nodes v i, v j in V in the sub-tour and v k in V not in the sub-tour, that minimizes non-Euclidean insertion cost ratio (C ik + C kj) / C ij.

4. Insert v k between v i and v j, updating the sub-tour.

5. Repeat Steps 3 and 4, until all nodes are in the tour, thus obtaining the NETSP solution.

The authors justify the selection of Multidimensional Scaling (MDS) because it explicitly minimizes global distance distortion, making it more appropriate for identifying boundary-like points compared to other dimensionality reduction techniques like UMAP or t-SNE, which do not guarantee preservation of global pairwise distances. Additionally, the algorithm utilizes an insertion cost ratio (C ik + C kj) / C ij, which penalizes insertions that cause large relative detours with respect to the insertion edge.

To evaluate the algorithm, "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. These experiments utilized 57 modified TSPLIB instances, where costs were modified by either using the L 1 norm as the cost function... or by inserting impassable separators. The study also included a case study using two warehouse scenarios from the MAPF benchmark."

Key performance findings include:

• On average, [the ACHCI] tour cost was 11% and 9% lower than the NN and NI heuristics, respectively.

• ACHCI also achieves lower tour costs than GA and ACO in 87% and 94% of instances within a 60-second computation time budget, and on average, produces tours that were 8.28 times lower than GA and 27% lower than ACO tours.

• The ACHCI heuristic exhibits a worst-case time complexity of O(n 3).

The paper concludes that "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."

1. Onboard Real-Time Path Re-Planning for Micro-Robotics

• What the improved AI system can do: Enables small-scale, resource-constrained drones or swarm robots to solve complex, obstacle-heavy routing tasks locally on edge hardware (e.g., microcontrollers) without relying on cloud computation. This allows the robot to immediately recalculate optimal paths when encountering dynamic obstacles or impassable separators in real-time, minimizing latency and preventing energy-intensive detours.

2. Energy-Optimized Mission Sequencing for Edge IoT Agents

• What the improved AI system can do: An autonomous agent can treat battery consumption, signal strength, or terrain difficulty as non-Euclidean costs. By applying the ACHCI insertion cost ratio, the system can sequence a series of sensor-data collection tasks or patrol routes to maximize operational uptime, reduce charging-related downtime, and extend the total mission duration of battery-limited IoT devices.

3. MDS-Seeded Hybrid Optimization for Large-Scale Logistics

• What the improved AI system can do: A high-level logistics AI can use the Multidimensional Scaling (MDS) approach as a warm-start mechanism for global metaheuristics (like Genetic Algorithms or Ant Colony Optimization). By projecting high-dimensional, non-Euclidean constraints (such as one-way streets or traffic-heavy zones) into a 2D Euclidean approximation, the system can provide an optimized initial tour that drastically reduces the time-to-convergence for complex, large-scale delivery routing.

4. Obstacle-Aware Autonomous Warehouse Management Systems (WMS)

• What the improved AI system can do: An AI-driven fleet controller can manage mobile warehouse robots in highly congested environments. By utilizing the ACHCI algorithm, the system can calculate optimal task-visiting sequences that account for impassable shelving and high-traffic human zones, ensuring minimal task completion duration and reducing congestion by penalizing paths that require large relative detours.

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.