본 논문은 그래프의 볼록 집합(GCS)을 기반으로 하는 새로운 외판원 문제(TSP) 변형인 GCS-TSP를 연구한다. 이 문제는 고정된 에지 비용 대신 각 볼록 영역을 통과하는 궤적에 따라 비용이 달라지므로 기존 TSP 방법을 적용할 수 없다. 저자들은 GHOST라는 계층적 프레임워크를 도입하여 조합 투어 검색과 볼록 궤적 최적화를 결합함으로써 GCS-TSP를 최적으로 해결한다. GHOST는 새로운 추상 경로 전개 알고리즘을 사용하여 투어와 실행 가능한 GCS 경로 모두에서 최선 우선 탐색을 안내하는 허용 가능한 하한을 계산하여 완전 그래프에서 투어를 체계적으로 탐색한다. 이 하한은 강력한 가지치기 능력을 제공하여 불필요한 볼록 최적화 호출을 피하면서 효율적인 검색을 가능하게 한다. 저자들은 GHOST가 최적성을 보장함을 증명하고, 시간 제약이 있는 시나리오를 위한 제한된 서브 옵티멀 변형을 제시한다.
