외판원문제 (Traveling Salesman Problem)
한 줄 정의: 여러 도시를 한 번씩만 방문하고 출발지로 돌아오는 경로 중에서 총 이동거리 또는 비용이 최소가 되는 순서를 찾는 조합최적화 문제를 의미합니다.
쉽게 풀면
택배기사가 하루 동안 배송해야 할 여러 집을 한 번씩만 들르고 다시 회사로 돌아와야 한다고 생각해봅시다. 방문 순서를 어떻게 정하느냐에 따라 총 이동거리가 크게 달라지는데, 외판원문제는 이 순서 중에서 이동거리가 가장 짧은 경로를 찾는 문제입니다. 이름은 "외판원"이지만 실제로는 배송, 회로 설계, 관광 경로 등 순서를 정해야 하는 다양한 상황에 적용됩니다.
왜 중요한가
외판원문제는 물류·수송 분야의 배송 경로 계획, 차량 라우팅 문제의 기초가 되는 대표적인 조합최적화 문제이며, 방문할 지점의 수가 늘어나면 가능한 경로의 수가 기하급수적으로 늘어나는 대표적인 계산 난제(NP-hard)이기도 해서 알고리즘 연구에서도 자주 다뤄집니다.
논문에서는 이렇게 쓰입니다
"택배 배송 경로 최적화를 위해 외판원문제를 기반으로 한 유전 알고리즘 기법을 적용하여 총 배송거리를 단축하였다."
배송 경로 최적화 문제를 외판원문제로 모형화한 사례입니다.
"차량 용량 제약을 포함한 차량라우팅문제는 외판원문제를 여러 차량으로 확장한 형태로 볼 수 있다."
외판원문제가 더 복잡한 물류 문제의 기초 모형으로 언급된 예시입니다.
조금 더 깊게 보면
외판원문제는 방문 지점 수가 조금만 늘어나도 모든 경로를 다 따져보는 완전탐색으로는 현실적인 시간 안에 풀기 어려워, 실제로는 근사해를 빠르게 구하는 휴리스틱이나 유전 알고리즘, 개미집단 최적화 같은 메타휴리스틱 기법이 자주 활용됩니다. 여러 대의 차량이 함께 방문지를 나누어 방문하는 경우로 확장한 것이 차량라우팅문제입니다.
주의할 점
외판원문제는 이론적으로 최적해를 구하기 어려운 문제이므로, 실무에서 사용하는 해법 대부분은 최적해에 가까운 근사해를 빠르게 찾는 데 초점을 두며 완전한 최적성을 보장하지는 않는 경우가 많습니다.