Abstract
Numerous remarkable advancements have been made in accuracy, speed, and parallelism for solving the Unmanned Aerial Vehicle Route Planing (UAVRP). However, existing UAVRP solvers face challenges when attempting to scale effectively and efficiently for larger instances. In this paper, we present a generalization framework that enables current UAVRP solvers to robustly extend their capabilities to larger instances, accommodating up to 10,000 points, using widely recognized test sets. The UAVRP under a large number of patrol points is a typical large-scale TSP problem. Our proposed framework comprises three distinct steps. Firstly, we employ Delaunay triangulation to extract subgraphs from large instances while preserving global features. Secondly, we utilize an embedded TSP solver to obtain sub-results, followed by graph fusion. Finally, we implement a decoding strategy customizable to the user's requirements, resulting in high-quality solutions, complemented by a warming-up process for the heatmap. To demonstrate the flexibility of our approach, we integrate two representative TSP solvers into our framework and conduct a comprehensive comparative analysis against existing algorithms using large TSP benchmark datasets. The results unequivocally demonstrate that our framework efficiently scales existing TSP solvers to handle large instances and consistently outperforms state-of-the-art (SOTA) methods. Furthermore, since our proposed framework does not necessitate additional training or fine-tuning, we believe that its generality can significantly advance research on end-to-end UAVRP solvers, enabling the application of a broader range of methods to real-world scenarios.
Introduction
Unmanned Aerial Vehicle Route Planning (UAVRP) is a critical component of modern logistics and surveillance, fundamentally modeled as a Large-Scale Traveling Salesman Problem (LSTSP). While small-scale TSP instances (under 100 nodes) are well-handled by modern solvers, scaling to thousands of points introduces significant hurdles. Exact solvers like Concorde become computationally prohibitive for massive instances, while heuristic methods like LKH-3 may suffer from instability or long runtimes.
Learning-based solvers, despite their inference speed, often fail to generalize beyond their training distributions. Existing "divide-and-conquer" approaches frequently lose global geometric features by isolating clusters into independent sub-problems. This paper introduces the Delaunay Triangulation-based TSP-solver Generalization Framework (DTTGF), designed to bridge these gaps by preserving global structure while leveraging the efficiency of local solvers.
Methodology
The DTTGF framework operates through a four-stage pipeline designed to maintain global connectivity while solving local sub-problems efficiently:
- Delaunay Triangulation (DT): Instead of standard k-nearest neighbor clustering, the framework uses DT to extract subgraphs. This geometric prior is based on the observation that optimal TSP edges are highly likely to be Delaunay edges, effectively preserving the "skeleton" of the global route.
- Sub-graph Solving: The large problem is partitioned into manageable sub-graphs, which are processed by an embedded TSP solver. The authors tested both "one-stage" solvers (like POMO) and "two-stage" solvers (like Att-GCN).
- Graph Fusion: Local solutions are merged into a global heatmap, where each edge is assigned a probability of being part of the optimal tour.
- Reinforcement Warm-up & Search: To correct errors introduced during partitioning, a pseudo-reinforcement learning "warm-up" phase iteratively refines the heatmap. A final search algorithm (such as MCTS) then decodes the refined heatmap into the definitive route.
Experimental Evaluation
The framework was evaluated using three benchmark datasets: TSP-500, TSP-1000, and TSP-10000. The results demonstrate that DTTGF allows solvers trained on small instances to generalize to 10,000 nodes without any additional training or fine-tuning.
Key findings from the comparative analysis include:
- Outperforming SOTA: DTTGF integrated with MCTS consistently outperformed state-of-the-art methods like DIMES and Att-GCN across all scales.
- Zero-Shot Scalability: The framework acts as a "plug-and-play" solution. For example, the standard Attention Model (AM) solver, which had an error "drop" of over 500% on TSP-10000, saw that error slashed to approximately 11-12% when integrated into the DTTGF framework.
- Efficiency: On 10,000-point instances, DTTGF produced high-quality solutions in reasonable timeframes (e.g., ~25 minutes for DTTGF+Att-GCN) where exact solvers were often impractical.
Discussion and Conclusion
DTTGF provides a robust framework for scaling TSP solvers to large-scale UAVRP tasks. By utilizing Delaunay Triangulation as a geometric prior and a reinforcement-based warm-up phase, it achieves state-of-the-art performance without the need for retraining neural networks. While the warm-up phase adds some computational overhead, the trade-off in accuracy is significant, particularly for instances with 1,000+ nodes. Future research will focus on adaptive hyperparameters for the warm-up phase and extending the framework to more complex combinatorial optimization problems, such as 3D path planning and vehicle routing with time windows.
Summary updated