[이론] CVRP, Capacitated Vehicle Routing Problem - 기초 개념 정리

CVRP 기초 개념 정리

---

CVRP, Capacitated Vehicle Routing Problem - 기초 개념 정리

---

CVRP란?

---

CVRP는 Capacitated Vehicle Routing Problem의 약자로, 여러 대의 차량이 하나의 창고(Depot)에서 출발해 모든 고객을 방문하고, 다시 창고로 돌아올 때 총 이동 거리(또는 비용)를 최소화하는 문제입니다.

TSP와의 가장 큰 차이는 두 가지입니다.

• 차량이 여러 대입니다. TSP는 한 사람(차량)이 모든 도시를 방문하지만, CVRP는 여러 차량이 고객을 나눠서 방문합니다.
• 차량마다 적재 용량(Capacity) 제한이 있습니다. 각 차량이 한 번에 운반할 수 있는 화물의 양이 정해져 있으며, 이 한도를 넘길 수 없습니다.

예를 들어, 택배 회사에서 여러 대의 배송 차량이 물류 창고에서 출발해 각자 담당 고객들에게 배달하고 창고로 돌아오는 상황을 생각해 볼 수 있습니다. 이때 각 차량의 최대 적재량이 정해져 있기 때문에, 어떤 차량이 어떤 고객을 맡을지, 어떤 순서로 방문할지를 최적으로 결정해야 합니다.

** TSP에 대한 이론은 다음 링크를 참고해주세요

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

---

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

---

CVRP 기초 예제 풀이

---

개념을 더 쉽게 이해하기 위해 간단한 예제를 살펴보겠습니다.

창고(Depot, D)와 고객 A, B, C, E 총 4명이 있습니다. 각 고객의 화물 수요(demand)와 창고-고객, 고객-고객 간 이동 거리는 아래와 같습니다.

[ 차량 조건 ]

차량은 총 2대, 각 차량의 최대 적재량(Q)은 5입니다.

[ 고객별 수요 ]

고객	수요
A	2
B	3
C	2
E	3

[ 이동 거리 행렬 ]

구분	D	A	B	C	E
D	0	10	20	15	25
A	10	0	12	8	18
B	20	12	0	10	7
C	15	8	10	0	14
E	25	18	7	14	0

---

1. 배차 가능 조합 탐색

총 수요는 2 + 3 + 2 + 3 = 10이고 차량이 2대, 적재량이 5이므로 전체를 알맞게 나눠 담아야 합니다. 각 차량이 담을 수 있는 수요 합 ≤ 5인 조합을 찾는 것이 이 단계의 목적입니다.

가능한 분할 방법은 다음과 같습니다.

조합 구분	차량 1	차량 2	결론
조합 1번	A(2) + C(2) = 4	B(3) + E(3) = 6	초과! 불가능
조합 2번	A(2) + B(3) = 5	C(2) + E(3) = 5	가능
조합 3번	A(2) + E(3) = 5	B(3) + C(2) = 5	가능
조합 4번	C(2) + B(3) = 5	A(2) + E(3) = 5	조합 3번과 동일한 경우

 

2. 각 조합의 이동 비용 계산

위에서 탐색한 경우 중 가능한 조합(2번, 3번)에 대해 이동 비용을 계산하면 다음과 같습니다.

조합 구분	방문 순서 후보	총 비용
조합 2번	차량 1의 방문 순서 후보: - D→A→B→D = 10+12+20 = 42 - D→B→A→D = 20+12+10 = 42 차량 2의 방문 순서 후보: - D→C→E→D = 15+14+25 = 54 - D→E→C→D = 25+14+15 = 54	조합 1의 총 비용 = 42+54 = 96
조합 3번	차량 1의 방문 순서 후보: - D→A→E→D = 10+18+25 = 53 - D→E→A→D = 25+18+10 = 53 차량 2의 방문 수서 후보: - D→B→C→D = 20+10+15 = 45 - D→C→B→D = 15+10+20 = 45	조합 2의 총 비용 = 53+45 = 98

 

3. 최적 경로 도출

조합 2,3번에 대한 경로와 비용은 다음과 같습니다. 따라서 최적 배차는 조합 2번으로, 총 이동 비용 96이 최솟값입니다.

조합 구분	차량 1 경로	차량 2 경로	총 비용
조합 2번	D→A→B→D (42)	D→C→E→D (54)	96
조합 3번	D→A→E→D (53)	D→B→C→D (45)	98

 

반응형

---

CVRP 수식 표현

---

위 예제를 수식으로 표현하면 다음과 같습니다.

[ 노드 집합 ]

창고를 0번, 고객을 1~n번으로 표현합니다. 0은 창고(Depot), 1~n은 고객 노드입니다.

$$ V = \{0, 1, 2, ..., n\} $$

[ 이동 비용 ]

$i$에서 $j$까지의 이동 비용은 $c_{ij}$로 표현합니다.

[ 수요 ]

각 고객 $i$의 화물 수요는 $d_i$로 표현합니다. 창고의 수요는 $d_0 = 0$입니다.

[ 의사결정 변수 ]

차량 $k$가 $i$에서 $j$로 이동하는지 여부를 나타내는 변수는 $x_{ijk}$로 표현합니다.

- $x_{ijk} = 1$: 차량 $k$가 $i$ → $j$ 이동
- $x_{ijk} = 0$: 이동하지 않음

 [ 목적 함수 ]

CVRP 문제의 목표는 모든 차량의 총 이동 비용을 최소화하는 것이므로 목적 함수 수식은 다음과 같습니다.

$$\min \sum_{k} \sum_{i} \sum_{j} c_{ij} \cdot x_{ijk}$$

[ 제약 조건 ]

첫째, 각 고객은 정확히 한 번만 방문해야 합니다.

$$\sum_{k} \sum_{j} x_{ijk} = 1 \quad \forall i \in \{1,...,n\}$$

둘째, 각 차량의 총 적재량은 용량 Q를 초과할 수 없습니다.

$$\sum_{i} d_i \cdot y_{ik} \leq Q \quad \forall k$$

여기서 $y_{ik} = 1$이면 고객 $i$를 차량 $k$가 방문한다는 의미입니다.

셋째, 각 차량은 창고에서 출발하고 창고로 돌아와야 합니다.

$$\sum_{j} x_{0jk} = \sum_{i} x_{i0k} = 1 \quad \forall k$$

넷째, 흐름 보존 조건으로, 어떤 노드에 들어온 차량은 반드시 나가야 합니다.

$$\sum_{i} x_{ihk} = \sum_{j} x_{hjk} \quad \forall h \in \{1,...,n\}, \forall k$$

다섯째, 부분 순환(subtour)을 허용하지 않습니다. 창고를 포함하지 않는 루프가 생기면 안 됩니다.

---

CVRP 풀이 알고리즘 종류

---

위 예제에서는 고객이 4명이어서 가능한 조합을 직접 나열할 수 있었습니다. 그러나 고객 수가 늘어날수록 탐색해야 하는 경우의 수는 폭발적으로 증가합니다.

CVRP는 TSP에 차량 배정 문제까지 더해지므로 TSP보다 더 어려운 문제입니다. 따라서 CVRP를 효율적으로 해결하는 다양한 알고리즘이 연구되고 있으며, 대표적으로 다음과 같은 방법들이 있습니다.

• 완전 탐색 (Brute Force)
  : 모든 가능한 경로와 배차 조합을 탐색합니다. 소규모 문제(고객 수 ~10명)에서만 현실적으로 사용 가능합니다.
• Clarke-Wright Savings Algorithm
  : 두 고객을 하나의 경로로 합칠 때 절약되는 비용(saving)을 계산하고, 절약량이 큰 쌍부터 탐욕적으로 경로를 합쳐 나가는 방법입니다. 1964년에 제안된 방법이지만 지금도 실무에서 많이 사용됩니다.
• Nearest Neighbor Heuristic
  : 각 차량이 현재 위치에서 가장 가까운 미방문 고객으로 이동하는 탐욕적 방법입니다. 빠르지만 최적해와의 거리가 큽니다.
• 메타휴리스틱 (Tabu Search, 유전 알고리즘)
  : 휴리스틱으로 구한 해를 반복적으로 개선하는 방법으로, 대규모 문제에서도 최적해에 가까운 해를 찾을 수 있습니다.

---

마무리하며

---

CVRP는 TSP에 "차량이 여러 대"이고 "각 차량에 적재 한도가 있다"는 현실적인 제약을 추가한 문제입니다. 단순해 보이지만 고객 수가 늘어날수록 완전 탐색만으로는 현실적인 해결이 어렵습니다.

물류 플랫폼에서의 배차 문제는 결국 CVRP의 변형으로 볼 수 있습니다. 여기에 시간 제약(VRPTW), 실시간 주문(DVRP), 픽업-배송 쌍(PDVRP) 등을 추가할수록 현실에 가까운 문제가 됩니다.

다음 글에서는 파이썬으로 CVRP 문제를 직접 풀어보겠습니다.

---