외판원문제 (Traveling Salesman Problem)
쉽게 풀면
택배기사가 하루 동안 배송해야 할 여러 집을 한 번씩만 들르고 다시 회사로 돌아와야 한다고 생각해봅시다. 방문 순서를 어떻게 정하느냐에 따라 총 이동거리가 크게 달라지는데, 외판원문제는 이 순서 중에서 이동거리가 가장 짧은 경로를 찾는 문제입니다.
이름은 "외판원"이지만 실제로는 배송, 회로 설계, 관광 경로 등 순서를 정해야 하는 다양한 상황에 적용됩니다. 외판원문제는 여러 도시를 딱 한 번씩만 방문하고 출발지로 되돌아오는 최단 경로를 찾는 문제로, 조합최적화 분야에서 가장 널리 알려진 대표적인 문제입니다.
왜 중요한가
외판원문제는 물류·수송 분야의 배송 경로 계획, 차량 라우팅 문제의 기초가 되는 대표적인 조합최적화 문제이며, 방문할 지점의 수가 늘어나면 가능한 경로의 수가 기하급수적으로 늘어나는 대표적인 계산 난제(NP-hard)이기도 해서 알고리즘 연구에서도 자주 다뤄집니다. 외판원문제는 배송 경로 설계나 회로 기판의 배선 순서 결정 등 실무의 다양한 순서결정 문제로 변형되어 응용되며, 계산 이론에서 NP-난해 문제의 대표 사례로 다뤄져 왔습니다.
핵심 정리
- 외판원 문제(TSP): n개 도시와 도시 사이의 거리가 주어졌을 때, 모든 도시를 한 번씩 거쳐 출발지로 돌아오는 가장 짧은 순환 경로를 찾는 문제입니다.
- 가능한 경로의 수는 대칭(왕복 거리가 같은) 문제에서 (n − 1)!/2개입니다. 완전탐색은 도시 수가 늘면 현실적으로 불가능해집니다.
- TSP의 결정 버전은 NP-완전이고, 최적값을 구하는 문제는 NP-난해로 분류됩니다(Karp 1972의 환원 결과에서 나온 결론). 자세한 개념은 NP-완전성, P 대 NP 문제를 보세요.
- 정확한 알고리즘으로는 동적계획법(Held–Karp, 1962; 시간 O(n²2ⁿ))이 있고, 대규모는 분기한정법·절단평면법으로 풉니다(Dantzig 외 1954가 선구).
- 근사 알고리즘: 거리가 삼각부등식을 만족하는 경우 Christofides(1976) 알고리즘은 최적값의 1.5배 이내를 보장합니다. 유클리드 평면에서는 임의의 정밀도로 근사하는 다항시간 근사 체계가 알려져 있습니다(Arora 1998).
예시로 보기
경로 수가 얼마나 빨리 불어나는지 계산하면 다음과 같습니다.
| 도시 수 n | (n − 1)!/2 | Held–Karp 연산 수 n²2ⁿ |
|---|---|---|
| 5 | 12 | 800 |
| 10 | 181,440 | 102,400 |
| 15 | 약 4.4 × 10¹⁰ | 약 7.4 × 10⁶ |
| 20 | 약 6.1 × 10¹⁶ | 약 4.2 × 10⁸ |
| 25 | 약 3.1 × 10²³ | 약 2.1 × 10¹⁰ |
동적계획법이 완전탐색보다 훨씬 낫지만 여전히 n에 대해 지수적입니다.
5개 도시 예(가상의 좌표, 직선거리): A(0,0), B(4,0), C(4,3), D(0,3), E(2,5). 서로 다른 순환 경로는 12개이고, 모두 계산하면 최단은 A→B→C→E→D→A로 길이 ≈ 15.66, 최장은 A→E→B→D→C→A로 ≈ 24.77입니다. 가장 가까운 도시로 가는 탐욕 규칙(최근접 이웃)으로 A에서 출발하면 이 사례에서는 우연히 최단 경로를 찾지만, 일반적으로 최적을 보장하지 못합니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| NP-난해라서 큰 문제는 풀 수 없다. | 이론상 최악의 경우가 어렵다는 뜻입니다. 전문 소프트웨어(Concorde 등)는 수만 개 도시 사례의 최적해를 증명까지 한 사례가 보고되어 있습니다(Applegate 외 2006). |
| 가까운 도시부터 방문하면 최적이다. | 최근접 이웃 규칙은 빠르지만 최적이 아닌 경우가 많습니다. |
| 모든 TSP에 근사 보장이 있다. | Christofides의 1.5 보장은 삼각부등식을 만족하는 경우에 한정됩니다. 일반 TSP는 상수 배 근사도 어렵다는 것이 알려져 있습니다. |
| 차량경로문제와 같다. | TSP는 한 명이 모든 곳을 도는 문제이고, 차량경로문제는 여러 차량·용량·시간 제약을 함께 다루는 확장입니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
배송 경로 최적화 문제를 외판원문제로 모형화한 사례입니다.
외판원문제가 더 복잡한 물류 문제의 기초 모형으로 언급된 예시입니다.
조금 더 깊게 보면
외판원문제는 방문 지점 수가 조금만 늘어나도 모든 경로를 다 따져보는 완전탐색으로는 현실적인 시간 안에 풀기 어려워, 실제로는 근사해를 빠르게 구하는 휴리스틱이나 유전 알고리즘, 개미집단 최적화 같은 메타휴리스틱 기법이 자주 활용됩니다.
여러 대의 차량이 함께 방문지를 나누어 방문하는 경우로 확장한 것이 차량라우팅문제입니다. 도시 수가 늘어나면 가능한 경로의 수가 팩토리얼 규모로 폭증해 정확한 최적해를 구하는 데 엄청난 계산량이 필요하므로, 실무에서는 최근접이웃법 같은 근사 해법이나 메타휴리스틱을 이용해 충분히 좋은 해를 구하는 방식이 흔히 쓰입니다.
주의할 점
외판원문제는 이론적으로 최적해를 구하기 어려운 문제이므로, 실무에서 사용하는 해법 대부분은 최적해에 가까운 근사해를 빠르게 찾는 데 초점을 두며 완전한 최적성을 보장하지는 않는 경우가 많습니다.
헷갈리기 쉬운 용어
| 문제 | 핵심 | 특징 |
|---|---|---|
| 외판원 문제 | 모든 도시를 한 번씩 거쳐 돌아오는 최단 순환 | 경로 수가 (n − 1)!/2 |
| 차량경로문제 | 여러 차량이 여러 배송지를 나누어 방문 | TSP의 확장, 용량·시간 제약 |
| 최단경로 문제 | 두 지점 사이의 최단 경로 | 다항시간에 풀림(다익스트라 등) |
| NP-완전성 | 확인은 쉽지만 풀이는 어려운 문제군의 성질 | TSP 결정 버전이 해당 |
참고 문헌
- Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393–410.
- Held, M., & Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
- Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations. Plenum Press.
- Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
- Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem (Report 388). Graduate School of Industrial Administration, Carnegie Mellon University.
- Arora, S. (1998). Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5), 753–782.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.