외판원 문제

최적설계 수치해석 마지막 수정: 2026-07-30 04:07:41

1. 개요[편집]

외판원 문제(Traveling Salesman Problem, TSP)는 $n$ 개의 도시와 도시 쌍마다 주어진 이동 비용 $c_{ij}$ 가 있을 때, 모든 도시를 정확히 한 번씩 방문하고 출발지로 돌아오는 최소 비용 순회(해밀턴 순환)를 찾는 문제다. 문장 하나로 설명이 끝나는데 아직도 안 풀린다는 점에서, 조합 최적화의 마스코트이자 영원한 벤치마크 노릇을 하고 있다.

대칭 TSP( $c_{ij}=c_{ji}$ )의 서로 다른 순회 수는 $(n-1)!/2$ 개다. 도시 20개면 $6\times10^{16}$ , 30개면 $4.4\times10^{30}$ . “유한하니까 다 세면 되죠”가 왜 안 되는지 보여주는 표준 반례로 이만한 게 없다.¹

2. 문제의 변종[편집]

대칭 TSP(STSP): 거리 행렬이 대칭. 무향 그래프 위의 순회.
비대칭 TSP(ATSP): $c_{ij}\neq c_{ji}$ . 일방통행, 오르막/내리막, 공구 교체 시간처럼 방향에 따라 비용이 다른 실제 상황이 여기 들어간다. 이론적으로 훨씬 다루기 까다롭다.
거리 TSP(metric TSP): 삼각부등식 $c_{ik}\le c_{ij}+c_{jk}$ 를 만족. 근사 알고리즘 이론의 대부분이 이 가정 위에서 굴러간다.
유클리드 TSP: 도시가 평면 위 점이고 비용이 유클리드 거리. 여전히 NP-난해지만, 기하 구조 덕에 훨씬 착한 성질을 갖는다.
경로형(path TSP), 다중 외판원(mTSP), 차량 경로 문제(VRP): 시작·끝을 풀거나, 순회를 여러 개로 쪼개거나, 용량·시간창 제약을 얹은 산업용 확장판들.

3. 복잡도와 근사 한계[편집]

TSP의 판정판은 카프의 1972년 21개 NP-완전 문제 목록에 들어 있다. 여기서 중요한 것은 근사 난이도의 층위가 변종마다 완전히 다르다는 점이다.

일반 TSP(삼각부등식 없음): 어떤 상수 $\rho$ 에 대해서도 $\rho$ -근사가 NP-난해다. 해밀턴 순환 존재성에서 환원하면서 없는 간선의 비용을 임의로 크게 잡으면 되기 때문. 즉 “적당히 잘하는 것”조차 불가능하다.²
거리 TSP: 상수배 근사가 가능하지만 무한정 좋아질 수는 없다. $123/122$ 보다 잘 근사하는 것이 NP-난해임이 알려져 있다.
유클리드 TSP: 아로라와 미첼이 독립적으로 PTAS를 제시했다(1996~98). 임의의 $\varepsilon>0$ 에 대해 $(1+\varepsilon)$ -근사를 다항시간에 얻는다. 근사 난이도 스펙트럼에서 가장 착한 등급에 속한다.
ATSP: 상수배 근사가 존재하는지조차 오래 미해결이었고, 2017년 스벤손·타르나프스키·베그가 처음으로 상수배 근사를 증명했다.

4. 정확해 — 증명된 최적을 원할 때[편집]

4.1. 정수계획 정식화[편집]

$x_{ij}\in\{0,1\}$ 을 간선 사용 여부로 두고 각 도시의 진입·진출 차수를 1로 묶으면 배정 문제가 되는데, 이것만으로는 여러 개의 작은 순환(부분순회, subtour)으로 쪼개진 해가 나온다. 이를 막는 제약이 두 갈래다.

DFJ(단치히-풀커슨-존슨) 부분순회 제거:

\sum_{i\in S}\sum_{j\in S} x_{ij} \le |S|-1,\qquad \forall\, S\subset V,\ 2\le|S|\le n-1

제약이 지수 개라 전부 쓸 수 없다. 대신 LP를 푼 뒤 위반된 제약만 찾아 넣는 분리(separation) 절차를 돌리는데, 이 분리 문제가 최소 절단 계산이라 네트워크 흐름 알고리즘으로 다항시간에 정확히 풀린다.

MTZ(밀러-터커-젬린): 보조 변수 $u_i$ 를 두고 $u_i-u_j+n\,x_{ij}\le n-1$ 을 건다. 제약이 $O(n^2)$ 개뿐이라 그냥 솔버에 던질 수 있지만, LP 완화가 훨씬 헐겁다. 교과서에서는 MTZ로 배우고 실전에서는 DFJ를 쓰는 이유가 이것.

4.2. 알고리즘[편집]

헬드-카프 동적계획법: $O(n^2 2^n)$ 시간, $O(n2^n)$ 공간. $O(n!)$ 보다 비교할 수 없이 낫지만 $n\approx25$ 가 한계다. 동적 계획법 참고.
분지한정법: 하계로 가지를 쳐낸다. 헬드-카프 하계(1-트리 라그랑주 완화 + 열경사 갱신)는 최적값의 99% 이상에 육박하는 하계를 주는 것으로 유명하다.
분지절단: 정수계획법의 LP 완화에 부분순회 제거 부등식, 빗(comb) 부등식, 클리크 트리 부등식 같은 유효 부등식을 계속 얹어 정수 껍질 쪽으로 조인다. Concorde가 바로 이 노선의 결정판으로, 2006년 VLSI 인스턴스 pla85900(85,900개 도시)의 최적성을 증명했다. 최악 복잡도가 지수적이라는 사실과, 구조가 있는 실제 인스턴스가 잘 풀린다는 사실은 얼마든지 공존한다.³

5. 구성 휴리스틱[편집]

해를 처음부터 하나 만들어 내는 방법들. 전부 빠르지만 품질은 제각각이다.

최근접 이웃(nearest neighbor): 가까운 미방문 도시로 계속 간다. 구현 10분, 무작위 유클리드 인스턴스에서 최적 대비 대략 +25% 수준. 다만 마지막에 남겨진 외딴 도시를 회수하느라 긴 간선을 한두 개 물게 되고, 최악 근사비는 $\Theta(\log n)$ 으로 발산한다.
탐욕 간선(greedy edge): 짧은 간선부터 차수 2와 조기 순환을 어기지 않는 한 계속 채택. 최근접 이웃보다 보통 낫다.
크리스토피데스 알고리즘: 거리 TSP에서 $3/2$ -근사. ① 최소 신장트리를 만들고 ② 홀수 차수 정점들만 모아 최소 가중 완전 매칭을 붙여 모든 차수를 짝수로 만든 뒤 ③ 오일러 회로를 따라가며 이미 방문한 도시를 건너뛴다(지름길, 삼각부등식이 여기서 필요하다). 1976년 결과가 40여 년간 최고 기록이었고, 2021년에야 $3/2-\varepsilon$ 이 깨졌는데 그 $\varepsilon$ 이 $10^{-36}$ 규모라 실용적 의미는 없다.

6. 지역 탐색과 린-커니건[편집]

TSP 실무의 진짜 주력은 간선 교환 지역 탐색이다.⁴

2-opt: 순회에서 간선 두 개를 끊고 사이 구간을 뒤집어 다시 잇는다. 유클리드 평면에서는 “교차하는 간선 쌍을 푸는” 연산과 같아서, 눈으로 봐도 개선이 보인다.
3-opt: 간선 세 개를 끊는다. 구간 반전 조합이 늘어 2-opt가 못 빠져나오는 지역 최적해를 넘는다.
Or-opt: 연속한 1~3개 도시 덩어리를 다른 위치로 옮긴다. 반전이 없어 ATSP에서도 안전하다.
린-커니건(LK): $k$ 를 고정하지 않고 가변 깊이로 교환 사슬을 뻗는다. 이득 누적합이 양수인 동안 사슬을 연장하고, 아니면 되돌린다. 헬스가운의 LKH는 여기에 5-opt 기본 이동과 1-트리에서 유도한 $\alpha$ -근접도 후보 간선을 얹은 구현으로, 대형 인스턴스에서 최적 대비 1% 이내 해를 사실상 실시간에 낸다.

이웃 후보를 도시마다 가장 가까운 5~10개로 제한하고, 순회를 이중연결리스트가 아니라 2-레벨 리스트나 스플레이 트리로 들고 있어야 반전 비용이 $O(n)$ 에서 $O(\sqrt n)$ 수준으로 떨어진다. 자료구조가 절반이다.

평면에 뿌린 도시 N개에 최근접 이웃으로 초기 순회를 만든 뒤 2-opt 간선 교환을 실제로 돌린다. 이득이 있는 (i,j) 쌍을 찾으면 사이 구간을 뒤집고, 2-opt가 소진되면 Or-opt로 넘어가며, 둘 다 막히면 국소 최적에서 멈춘다(정지 화면이 정상). 아래 곡선은 순회 길이 L의 감소이고 주황 점선이 최근접 이웃 초기값 L0 — 개선률이 15~25% 근처에서 멎는 것이 2-opt의 현실이다.

7. 메타휴리스틱[편집]

담금질 모사: 2-opt 이웃 위에서 나빠지는 이동도 $\exp(-\Delta/T)$ 로 받는다. 구현이 가장 쉬워 첫 시도로 자주 쓰인다.
타부 서치: 최근 되돌린 간선을 금지 목록에 넣어 같은 자리를 맴도는 것을 막는다.
개미 군집 최적화(ACO): 좋은 순회에 쓰인 간선에 페로몬을 쌓아 확률적 구성 편향을 학습한다. 애초에 TSP를 대상으로 태어난 계열이다.
유전 알고리즘: 순열 표현에서 교차 연산자 설계가 성능의 전부다. 실전 강자는 부모 두 순회의 공통 간선을 유지하고 차이 부분만 재조합하는 EAX 계열.

메타휴리스틱은 하계를 주지 않는다. 나온 해가 최적 대비 2% 떨어졌는지 20% 떨어졌는지 알 수 없으므로, 헬드-카프 하계를 따로 뽑아 간극을 함께 보고하는 것이 성실한 태도다.

8. 시뮬레이션·CAE에서의 TSP[편집]

TSP는 OR 교과서 안에만 사는 문제가 아니다.

공구 경로 최적화: PCB 드릴링은 문자 그대로 TSP다. 구멍이 곧 도시고 이송 시간이 곧 거리. CNC 가공의 공구 이동, 레이저 커팅의 절단 순서도 같은 틀.
적층 제조 시뮬레이션의 스캔 경로: 레이저가 층 내부를 어떤 순서로 훑느냐가 국소 열이력을 바꾸고, 그게 잔류응력과 변형으로 직결된다. 여기서는 경로 길이만이 아니라 열 축적까지 목적함수에 들어가 TSP 변종이 된다.
경로 계획: 로봇 용접 순서, 검사 좌표측정기(CMM)의 측점 순회, 게임에서 내비게이션 메시 위를 도는 NPC의 순찰 경로.
메시 재정렬: 캐시 지역성을 위해 요소를 공간 채움 곡선이나 TSP 근사 순서로 늘어놓으면 희소행렬 연산의 메모리 접근이 개선된다.

9. 관련 문서[편집]

이 문제에 “외판원”이라는 이름이 붙은 건 1930년대 독일·오스트리아의 순회 판매원 안내서에서 유래했다고 전해진다. 정작 21세기의 실제 활용처는 판매원이 아니라 드릴 헤드, 레이저 스캐너, 창고 로봇이다. 이름만 남고 직업은 사라진 셈. ↩
근사 불가능성 결과를 처음 보면 김이 새는데, 실무 관점에서는 오히려 반가운 소식이다. 일반 TSP가 근사 불가능하다는 말은 뒤집으면 삼각부등식이 성립하는 문제를 풀고 있는지 확인하라는 지침이 된다. 현실의 거리·시간 행렬은 대개 삼각부등식을 만족하므로, 우리는 어려운 쪽이 아니라 착한 쪽에 서 있다. ↩
전 세계 1,904,711개 도시를 도는 World TSP 인스턴스는 아직 최적성이 증명되지 않았다. 다만 알려진 최선 순회가 증명된 하계 대비 0.05% 이내라는 것까지는 밝혀져 있어서, 사실상 답을 알면서도 “증명”만 못 하고 있는 상태다. 공학자는 여기서 만족하고 퇴근하고, 수학자는 남는다. ↩
2-opt를 구현해 보면 유클리드 인스턴스에서 순회의 교차가 하나씩 풀리는 게 화면에 그대로 보인다. 이 즉각적인 시각 피드백 때문에 TSP는 최적화 강의 첫 실습 과제의 부동의 1위다. 그리고 학생들은 여기서 “그럼 다 풀린 거 아닌가요”라는 착각을 시작한다. ↩