아침마다 물류센터 앞에서는 트럭 여러 대가 짐을 싣고 출발을 기다립니다. 오늘 배송할 곳은 수십 곳인데, 어느 트럭이 어느 집을 맡고 어떤 순서로 돌아야 할지 정해야 합니다. 같은 짐을 같은 집에 나르더라도 길을 어떻게 짜느냐에 따라 하루 동안 달리는 거리와 기름값, 기사의 퇴근 시간이 크게 달라집니다.

차량 경로 문제(Vehicle Routing Problem)란 쉽게 말해 ‘여러 대의 차량이 창고에서 출발해 여러 고객을 나누어 방문하고 돌아올 때, 전체 비용이 가장 적게 드는 경로의 묶음을 찾는 문제’를 의미합니다. 1959년 조지 댄치그(George Dantzig)와 존 램저(John Ramser)가 주유소에 휘발유를 나르는 트럭 배차 문제로 처음 소개했고, 오늘날 택배와 유통 물류의 기본 계산이 되었습니다.

본 자료에서는 차량 경로 문제의 기본 구조부터, 경우의 수가 폭발하는 이유, 현실이 더하는 여러 조건, 그리고 답을 찾는 방법까지 차례로 살펴보겠습니다.

---

트럭 여러 대의 길을 한 번에 짜는 계산

차량 경로 문제의 기본 구조

차량 경로 문제는 몇 가지 요소만 정하면 그 모습이 분명해집니다.

(1) 창고와 차량
모든 차량은 한 곳의 창고, 곧 출발 기지에서 떠나 일을 마친 뒤 다시 그곳으로 돌아옵니다. 차량이 몇 대인지, 각 차량이 얼마나 실을 수 있는지가 처음부터 정해져 있습니다.

(2) 고객과 수요
배송할 곳마다 위치와 받아야 할 물건의 양이 있습니다. 모든 고객은 반드시 한 번씩, 그리고 한 대의 차량에게서만 물건을 받아야 합니다.

(3) 이동 비용
두 지점 사이를 오가는 데 드는 거리나 시간, 돈을 미리 계산해 둡니다. 실제 도로망에서 가장 짧은 길을 구해 두면, 지점 사이의 비용을 한 장의 표처럼 다룰 수 있습니다.

(4) 목표
가장 흔한 목표는 전체 이동 비용을 줄이는 것입니다. 경우에 따라 차량 대수를 최소로 하거나, 차량마다 일의 양을 고르게 나누는 것을 목표로 삼기도 합니다.

---

경우의 수가 폭발하는 이유

트럭 한 대가 모든 집을 한 바퀴 도는 가장 짧은 순서를 찾는 문제를 외판원 문제(Traveling Salesman Problem)라고 합니다. 차량 경로 문제는 이 외판원 문제를 여러 대의 차량으로 넓힌 것이라, 적어도 그만큼 어렵습니다.

방문할 곳이 10곳이면 도는 순서만 해도 약 362만 가지가 나옵니다. 20곳이 되면 그 수는 약 243경 가지로 불어납니다. 여기에 어느 차량이 어느 고객을 맡을지까지 정해야 하니, 모든 경우를 하나하나 따져 보는 방법은 금세 한계에 부딪힙니다.

수학에서는 이런 문제를 NP-난해(NP-hard) 문제로 분류합니다. 고객 수가 늘어날 때 정확한 답을 구하는 데 걸리는 시간이 감당하기 어려울 만큼 빠르게 늘어날 수 있다는 뜻입니다. 그래서 현장에서는 완벽한 답보다 충분히 좋은 답을 빠르게 찾는 쪽을 택하는 경우가 많습니다.

---

현실이 더하는 조건들

실제 배송 현장은 교과서 속 문제보다 훨씬 복잡해서, 조건이 붙을 때마다 새로운 변형 문제가 생깁니다.

• 적재 용량 제약(Capacitated Vehicle Routing Problem): 차량마다 실을 수 있는 무게나 부피에 한계가 있어, 이를 넘지 않게 고객을 나누어야 합니다.
• 시간 창 제약(Vehicle Routing Problem with Time Windows): 고객마다 물건을 받을 수 있는 시간대가 정해져 있어, 그 안에 도착해야 합니다.
• 수거와 배송(Vehicle Routing Problem with Pickup and Delivery): 한 곳에서 물건을 싣고 다른 곳에 내려 주는 일을 함께 처리합니다.
• 다중 창고(Multi-Depot Vehicle Routing Problem): 차량이 출발하고 돌아오는 창고가 여러 곳입니다.
• 전기차 경로 문제(Electric Vehicle Routing Problem): 배터리로 갈 수 있는 거리와 충전할 곳까지 함께 고려합니다.

이 밖에도 차량이 창고로 돌아오지 않아도 되는 경우, 하루에 여러 번 창고를 오가는 경우 등 현장의 사정만큼 다양한 변형이 연구되고 있습니다.

---

답을 찾는 방법들

차량 경로 문제를 푸는 방법은 크게 정확한 답을 구하는 쪽과 좋은 답을 빠르게 구하는 쪽으로 나뉩니다.

정확한 해법

정수계획법이라는 수학적 모형으로 문제를 세우고, 가능한 경우를 영리하게 걸러 내며 가장 좋은 답을 찾습니다. 답의 품질은 확실하지만, 고객이 많아지면 계산 시간이 크게 늘어나 주로 규모가 작은 문제에 쓰입니다.

절약 알고리즘

1964년 클라크(G. Clarke)와 라이트(J. W. Wright)가 제안한 방법입니다. 처음에는 고객마다 트럭을 한 대씩 따로 보낸다고 가정한 뒤, 두 고객을 한 경로로 이었을 때 줄어드는 거리, 곧 절약량이 큰 쌍부터 차례로 합쳐 나갑니다. 계산이 간단하고 결과도 쓸 만해서 지금도 널리 쓰입니다.

메타휴리스틱

유전 알고리즘, 타부 탐색, 담금질 기법처럼 처음 만든 경로를 조금씩 고쳐 가며 더 나은 답을 찾아가는 방법입니다. 최근의 뛰어난 방법들은 수백에서 수천 곳에 이르는 문제에서도 최적의 답과 1퍼센트 안팎까지 차이를 좁힌다고 알려져 있습니다.

---

차량 경로 문제는 지도 위에 선을 긋는 일처럼 보이지만, 그 뒤에는 비용과 시간, 사람의 노동을 함께 줄이려는 계산이 담겨 있습니다. 경로 계획 소프트웨어를 만드는 업체들이 5~30퍼센트의 비용 절감을 내세우는 것도 이 계산의 힘을 보여 줍니다.

같은 짐을 더 짧은 길로 나르기 위해 경로를 끊임없이 다시 따져 보는 것, 그것이 효율적인 배송의 첫걸음입니다.