그래프 포인터 네트워크와 분산 기법을 결합한 다양한 TSP 경로 생성

Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion

본 연구에서는 다양한 여행하는 판매원 문제(D-TSP)를 다룹니다. D-TSP는 $k$개의 서로 다른 TSP 경로를 찾는 이중 기준 최적화 문제입니다. 목표는 선택된 모든 경로의 길이가 최적 경로 길이 ($|T^*|$)의 $c$배 이내에 있어야 하며, 모든 경로 쌍 간의 평균 자카드 유사도를 최소화하는 것입니다. 이러한 제약 조건은 물류 계획, 로봇 경로 탐색 또는 전략적 순찰과 같이 높은 솔루션 품질과 내결함성을 요구하는 응용 분야에 매우 중요합니다. 기존 방법은 한계가 있습니다. 전통적인 휴리스틱 방법(예: Niching Memetic Algorithm, NMA) 또는 이중 기준 최적화 방법은 높은 계산 복잡도 $O(n^3)$를 갖는 반면, 최신 신경망 접근 방식(예: RF-MA3S)은 제한된 다양성 품질을 제공하며 복잡한 외부 메커니즘에 의존합니다. 이러한 한계를 극복하기 위해, D-TSP를 두 가지 효율적인 단계로 분해하는 새로운 하이브리드 프레임워크를 제안합니다. 첫 번째 단계에서는 단순한 그래프 포인터 네트워크(GPN)를 사용하며, 근사 시퀀스 엔트로피 손실을 추가하여 고품질의 다양한 경로 풀을 효율적으로 생성합니다. 이 간단한 수정은 복잡한 외부 메커니즘 없이 품질-다양성 균형을 효과적으로 제어합니다. 두 번째 단계에서는 분산 문제를 위한 2-근사 알고리즘을 사용하여 생성된 풀에서 최종 $k$개의 가장 다양한 경로를 선택합니다. 실험 결과는 제안된 방법이 최첨단 성능을 달성함을 보여줍니다. 베를린 데이터셋에서, 제안된 모델은 평균 자카드 지수가 0.015로, NMA (0.081) 및 RF-MA3S보다 훨씬 뛰어난 성능을 보입니다. GPU 가속을 활용하여, GPN 구조는 거의 선형적인 경험적 실행 시간 증가 $O(n)$을 달성합니다. 복잡한 이중 기준 알고리즘과 유사한 수준의 솔루션 다양성을 유지하면서, 제안된 방법은 대규모 인스턴스(783개 도시)에서 360배 이상 빠른 속도를 제공하여, 높은 품질의 TSP 솔루션을 전례 없는 효율성과 단순성으로 제공합니다.

We address the Diverse Traveling Salesman Problem (D-TSP), a bi-criteria optimization challenge that seeks a set of $k$ distinct TSP tours. The objective requires every selected tour to have a length at most $c|T^*|$ (where $|T^*|$ is the optimal tour length) while minimizing the average Jaccard similarity across all tour pairs. This formulation is crucial for applications requiring both high solution quality and fault tolerance, such as logistics planning, robotics pathfinding or strategic patrolling. Current methods are limited: traditional heuristics, such as the Niching Memetic Algorithm (NMA) or bi-criteria optimization, incur high computational complexity $O(n^3)$, while modern neural approaches (e.g., RF-MA3S) achieve limited diversity quality and rely on complex, external mechanisms. To overcome these limitations, we propose a novel hybrid framework that decomposes D-TSP into two efficient steps. First, we utilize a simple Graph Pointer Network (GPN), augmented with an approximated sequence entropy loss, to efficiently sample a large, diverse pool of high-quality tours. This simple modification effectively controls the quality-diversity trade-off without complex external mechanisms. Second, we apply a greedy algorithm that yields a 2-approximation for the dispersion problem to select the final $k$ maximally diverse tours from the generated pool. Our results demonstrate state-of-the-art performance. On the Berlin instance, our model achieves an average Jaccard index of $0.015$, significantly outperforming NMA ($0.081$) and RF-MA3S. By leveraging GPU acceleration, our GPN structure achieves a near-linear empirical runtime growth of $O(n)$. While maintaining solution diversity comparable to complex bi-criteria algorithms, our approach is over 360 times faster on large-scale instances (783 cities), delivering high-quality TSP solutions with unprecedented efficiency and simplicity.