본 논문은 NP-완전으로 다항시간 알고리즘이 존재하지 않는 대규모 외판원 문제의 최적 해를 O(n²)의 다항시간으로 구하는 알고리즘을 제안하였다. 대규모 외판원 문제에서 가장 큰 문제는 처리될 데이터가 n ×n으로?n 커질수록 기하급수적으로 증가한다. 본 논문에서는 먼저, 데이터의 양을 약 n/2기로 축소시킨다. 다음으로 임의의 정점에서 시작하여 양방향으로 경로를 탐색하는 방법을 적용하였다. 제안된 알고리즘을 26개의 유럽 도시들을방문하는 TSP-1과 46개 미국 도시들을 방문하는 TSP-2에 적용한 결과 모두 최적 해를 O(n²) 수행 복잡도로 빠르게 구하는데 성공하였다. 따라서 제안된 알고리즘은 TSP의 일반화된 알고리즘으로 적용할 수 있을 것이다.
본 연구는 NP-완전으로 다항시간 알고리즘이 존재하지 않는 대규모 외판원 문제의 최적 해를 O(n²)의 다항시간으로 구하는 알고리즘을 제안하고자 하였다.