A GPU-Accelerated Two-Level Hybrid Approach for the Traveling Salesperson Problem with Non-Convex Neighborhoods

Vol 57, 2025 - 341091
Complete Articles (CA)
Favorite this paper
How to cite this paper?
Abstract

The Traveling Salesperson Problem with Neighborhoods (TSPN) in non-convex polygonal domains is a highly complex routing challenge that couples combinatorial sequencing with continuous path optimization. As exact geometric evaluations dominate the search cost, traditional approaches struggle to scale. To address this bottleneck, we propose a GPU-accelerated bi-level architecture that strictly decouples macroscopic topological exploration from continuous trajectory refinement. A Max-Min Ant System (MMAS) drives the combinatorial search, guided by a dynamic heuristic derived from a massive, GPU-computed intersection oracle. The exact continuous micro-routes are then recovered via a Dynamic Programming (DP) decoder and refined by a computationally lightweight topological local search. Furthermore, we present a large-scale public benchmark, with instances of up to 2,000 irregular polygons. Computational experiments demonstrate that the proposed framework balances exact geometric feasibility and scalability, reducing average route costs by 20.8% compared to constructive baselines.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Minas Gerais
  • 2 Universidade Federal de Viçosa
Track
  • MH – Metaheurístics
Keywords
Traveling Salesperson Problem with Neighborhood
Ant Colony Optimization
GPU Computing