[이론] TSP Traveling Salesman Problem - 기초 개념 정리

TSP 기초 개념 정리

---

TSP Traveling Salesman Problem - 기초 개념 정리

---

TSP란?

---

TSP는 Traveling Salesman Problem의 약자로, 흔히 외판원 문제로 잘 알려져 있습니다. 여러 도시를 각각 한 번씩만 방문하고, 출발했던 도시로 돌아올 때 총 이동 거리가 가장 짧은 경로를 찾는 문제입니다.

TSP는 물류, 배송 경로 최적화, 반도체 회로 설계 등 실생활의 다양한 분야에서 활용됩니다. 예를 들어, 택배 기사가 여러 집을 모두 방문하고 다시 출발지로 돌아올 때 가장 짧은 경로로 배달하는 상황을 생각해 볼 수 있습니다.

단순해 보이지만, 도시 수가 늘어날수록 가능한 경로의 수가 폭발적으로 증가하기 때문에 최적해를 찾는 것이 매우 어려운 문제로 알려져 있습니다. 이러한 특성 때문에 TSP는 컴퓨터 과학에서 중요하게 다뤄지는 대표적인 최적화 문제 중 하나입니다.

이 글에서는 TSP의 기초 개념과 수식 표현, 그리고 TSP를 해결하는 다양한 접근법에 대해 소개합니다.

---

• TSP 기초 예제 풀이
• TSP 수식 표현
• TSP 풀이 알고리즘 종류

---

TSP 기초 예제 풀이

---

개념을 더 쉽게 이해하기 위해 간단한 예제를 살펴보겠습니다. 도시 A, B, C, D 총 4개가 있고, 각 도시 사이의 거리가 아래 표와 같을 때 모든 도시를 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 찾아보겠습니다.

구분	A	B	C	D
A	0	10	15	20
B	10	0	35	25
C	15	35	0	30
D	20	25	30	0

 

위의 표를 그림으로 표현하면 다음과 같습니다. A에서 B까지의 거리는 10, A에서 C까지의 거리는 15입니다.

도시와 거리

---

1. 가능한 경로 탐색

A에서 출발한다고 가정하고, 가능한 경로와 해당 경로의 거리를 계산해보겠습니다.

TSP는 순환 경로를 찾는 문제이기 때문에, 어느 도시에서 출발하든 결국 같은 경로를 순환하게 됩니다.
예를 들어, "A→B→C→D→A" , "B→C→D→A→B", "C→D→A→B→C"는 모두 순환하면 동일하기에 사실상 같은 경로입니다.

따라서 출발 도시를 A로 고정하고, 가능한 모든 경로와 해당 거리를 나열하면 다음과 같습니다.

• 경로 1: A → B → C → D → A = 10 + 35 + 30 + 20 = 95
• 경로 2: A → B → D → C → A = 10 + 25 + 30 + 15 = 80
• 경로 3: A → C → B → D → A = 15 + 35 + 25 + 20 = 95
• 경로 4: A → C → D → B → A = 15 + 30 + 25 + 10 = 80
• 경로 5: A → D → B → C → A = 20 + 25 + 35 + 15 = 95
• 경로 6: A → D → C → B → A = 20 + 30 + 35 + 10 = 95

---

2. 최적 경로 도출

위의 가능한 경로 중 최소 거리는 80입니다. 
따라서, 도시가 4개인 TSP 문제의 최적 경로는 “A → B → D → C → A” 또는 “A → C → D → B → A”입니다.

---

TSP 수식 표현

---

4개의 도시에 대한 TSP 문제를 수식으로 표현하면 다음과 같습니다.

---

도시 집합

도시 집합은 A, B, C, D 총 4개이므로 다음과 같습니다.

$$ V={ A, B, C, D } $$

 

거리

$i$에서 $j$까지의 거리는 $d_{ij}$로 표현합니다. $d_{AB}$는 A에서 B까지의 거리, $d_{AC}$는 A에서 C까지의 거리입니다.

 

의사결정 변수

경로 선택의 유무에 관한 변수는 $x_{ij}$로 표현합니다. 특정 경로에 대해 이동할지, 이동하지 않을지 다음과 같이 구분합니다. 예를 들어, A에서 B 경로를 선택할 경우, $x_{AB}$=1입니다.

• $x_{ij} = 1$ : $i$→$j$ 이동
• $x_{ij} = 0$ : 이동하지 않음

 

목적 함수

TSP 문제의 목표는 총 이동 거리가 가장 짧은 경로를 선택하는 것이므로 목적 함수 수식은 다음과 같습니다. (거리 × 이동 여부)를 모두 더한 값의 최솟값입니다.

$$ \min \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ij} $$

 

제약 조건

제약 조건은 다음과 같이 표현할 수 있습니다. 첫째, 각 도시에서는 한 번만 출발해야 합니다.

$$ \sum_{j=1}^{n} x_{ij} = 1 $$

둘째, 각 도시에는 한 번만 도착해야 합니다.

$$ \sum_{i=1}^{n} x_{ij} = 1 $$

반응형

---

TSP 풀이 알고리즘 종류

---

위 예제에서는 도시가 4개뿐이어서 가능한 경로를 직접 모두 나열할 수 있었습니다. 그러나 도시 수가 늘어날수록 탐색해야 하는 경로의 수는 $(n-1)!$ 로 폭발적으로 증가합니다.

도시 개수(n)	경우의 수 $(n-1)!$
4개	6가지
10개	362,880가지
20개	약 $1.2×10^{17}$가지

---

도시가 20개만 되어도 경우의 수가 천문학적으로 커지기 때문에, 모든 경로를 직접 탐색하는 방식은 현실적으로 사용하기 어렵습니다. 따라서 TSP를 효율적으로 해결하는 다양한 알고리즘이 연구되고 있으며, 대표적으로 다음과 같은 방법들이 있습니다.

• 다이내믹 프로그래밍 (Held-Karp): 이미 계산한 경로를 재활용해 완전 탐색보다 효율적으로 최적해를 구하는 방법
• 휴리스틱 (Nearest Neighbor): 최적해를 보장하지는 않지만, 가장 가까운 도시를 우선 방문하는 방식으로 빠르게 근사해를 구하는 방법
• 메타휴리스틱 (유전 알고리즘, 시뮬레이티드 어닐링): 자연 현상에서 아이디어를 얻어 대규모 문제에서도 현실적인 시간 안에 좋은 해를 찾는 방법

---

마무리하며

TSP는 단순한 개념에서 출발하지만, 도시 수가 늘어날수록 완전 탐색만으로는 현실적인 해결이 어려운 복잡한 최적화 문제입니다. 이러한 이유로 다이나믹 프로그래밍, 휴리스틱 등 다양한 알고리즘이 연구되어 왔으며, 각각의 방법은 문제의 규모와 목적에 따라 다르게 활용되고 있습니다.