배차 최적화란? 내비게이션과 다른 점, VRP·TSP 뜻까지 쉽게 정리

아침마다 배송지 목록을 펼쳐 놓고 '오늘은 어느 차를 어디로 보내지?' 고민하는 배차 담당자라면, 한 번쯤 이런 생각을 해 보셨을 거예요. 내비게이션은 길을 저렇게 척척 찾아 주는데, 배차도 그냥 맡기면 안 될까 하고요.

결론부터 말하면, 두 가지는 비슷해 보여도 풀고 있는 문제가 전혀 다릅니다. 내비게이션이 차 한 대가 목적지까지 가는 가장 빠른 길을 알려 준다면, 배차 최적화는 여러 대의 차량에 수백, 수천 곳의 배송지를 나눠 맡기고 차량마다 들를 순서까지 정해서, 전체 비용이 가장 적게 드는 계획을 세우는 일이죠.

간혹 현장에서도 "길 찾기는 내비게이션도 하는데, 배차 프로그램은 뭐가 다른 거예요?"라는 질문이 나오기도 합니다. 지도 위에 경로를 그려 준다는 겉모습은 같지만, 그 뒤에서 풀고 있는 문제의 크기는 비교하기 어려울 만큼 차이가 나거든요.

이 글에서는 내비게이션이 푸는 최단 경로 문제에서 시작해, 한 사람의 방문 순서를 정하는 TSP, 여러 차량의 배차를 정하는 VRP까지 하나씩 짚어 보면서 배차 최적화가 왜 그렇게 어려운 문제인지 쉽게 풀어 볼게요.

최단 경로, TSP, VRP는 어떻게 다를까?

세 문제의 차이는 결국 ‘몇 대의 차가, 몇 곳을, 어떤 조건으로’ 가느냐에서 갈립니다. 조건이 하나씩 붙을 때마다 난이도가 어떻게 달라지는지 표로 먼저 볼게요.

최단 경로 문제: 내비게이션이 푸는 문제

출발지와 목적지가 하나씩 정해져 있을 때, 그 사이의 가장 빠른 길을 찾는 문제입니다. 도로가 아무리 복잡하게 얽혀 있어도 컴퓨터가 빠르게 답을 낼 수 있는 방법이 이미 잘 알려져 있죠. 내비게이션 앱이 목적지를 입력하자마자 길 안내를 시작할 수 있는 것도 그래서예요.

TSP: 한 사람이 여러 곳을 도는 순서 문제

TSP(Traveling Salesman Problem, 외판원 문제)는 영업사원 한 명이 여러 고객사를 한 번씩만 들르고 돌아온다고 할 때, 어떤 순서로 돌아야 가장 짧을지 찾는 문제예요. 들를 곳이 5곳이라면 가능한 순서는 120가지 정도지만, 10곳만 돼도 약 360만 가지로 불어납니다. 방문지가 하나 늘 때마다 경우의 수가 곱셈으로 커지기 때문이에요.

VRP: 여러 차량이 일을 나눠 맡는 문제

VRP(Vehicle Routing Problem, 차량 경로 문제)는 여기에 ‘차가 여러 대’라는 조건이 더해진 문제입니다. 순서만 정하면 끝나는 게 아니라, 어느 배송지를 어떤 차에 맡길지부터 정해야 하거든요. 물류센터의 배차 담당자가 매일 아침 씨름하는 문제가 바로 이 VRP예요. 업계에서는 일정까지 함께 짠다는 뜻에서 VRS(Vehicle Routing and Scheduling)라고도 부르는데, 같은 의미로 보시면 좋아요.

배차 최적화는 왜 이렇게 어려울까?

내비게이션처럼 뚝딱 답이 나오지 않는 이유는, 실제 배차에는 ‘차 여러 대’에 더해 수많은 제약 조건이 따라붙기 때문입니다. 제약 조건이란 배차 계획이 반드시 지켜야 하는 규칙을 말해요.

현장에서 자주 만나는 제약 조건

• 배송 시간대(Time Window): “이 매장은 오전 7시에서 9시 사이에만 받을 수 있어요” 같은 약속이에요.

• 차량 적재량: 한 차에 실을 수 있는 무게와 부피에는 한계가 있습니다.

• 진입 제한: 도심이나 일부 건물은 큰 차나 높은 차가 들어갈 수 없죠.

• 기사 근무 시간과 휴게 시간: 하루에 일할 수 있는 시간과 쉬는 시간도 지켜야 하고요.

• 하역 시간: 배송지마다 짐을 내리는 데 걸리는 시간도 제각각이에요.

이 가운데 가장 까다로운 건 단연 배송 시간대입니다. 배송 시간대가 붙은 VRP는 VRPTW(VRP with Time Windows)라고 따로 부를 정도죠. 시간대 제약이 왜 그렇게 어려운지는 “몇 시에 오나요?”의 이면 글에서 더 자세히 다뤘으니 함께 읽어 보셔도 좋아요.

경우의 수가 우주의 원자 수보다 많아져요

들를 곳이 20곳만 돼도 가능한 순서는 약 243경 가지로, 빠른 컴퓨터로 하나씩 따져 봐도 수십 년이 걸립니다. 실제 배차는 여기에 차량 여러 대와 제약 조건까지 붙으니, 모든 경우를 다 확인하는 방식으로는 답을 낼 수 없어요.

그래서 컴퓨터 과학에서는 VRP 같은 문제를 NP-hard 문제라고 부릅니다. 문제가 조금만 커져도 정답을 구하는 데 필요한 시간이 폭발적으로 늘어난다는 뜻이에요. 따라서 실제로는 모든 경우를 확인하는 대신, 좋은 답이 있을 만한 방향을 빠르게 좁혀 가는 알고리즘으로 풀어냅니다.

그래서 사람은 ‘권역’으로 나눠왔어요

사람이 머리로 풀 수 있는 문제가 아니다 보니, 현장에서는 오랫동안 기사마다 담당 권역을 정해 두는 방식을 써 왔습니다. “이 기사님은 강남, 저 기사님은 강서”처럼요. 배차는 간단해지지만 아쉬운 점도 있어요. 주문이 한 지역에 몰리는 날이면 그 권역 기사님은 정신없이 바쁜데 옆 권역 기사님은 오히려 한가한, 그런 불균형이 생기거든요. 모자란 차는 용차(외부 차량)를 불러 채우게 되고, 그만큼 비용도 늘어나죠.

배차 최적화로 무엇을 줄일 수 있을까?

글 첫머리의 배차 담당자 이야기로 다시 돌아가 볼게요. 배송지 목록을 펼쳐 놓고, 지도를 보며 권역을 나누고, 기사님마다 사정을 떠올리며 순서를 맞춰 가는 일. 겨우 다 짰다 싶을 때 주문 몇 건이 추가되면 처음부터 다시 손봐야 하죠. 이 과정을 매일 아침 반복하고 있다면, 이제는 사람이 아니라 엔진에게 맡길 때입니다.

루티(ROOUTY)에 주문과 차량 정보를 넣으면, AI 배차 엔진이 배송 시간대, 적재량, 진입 제한 같은 제약 조건을 반영해 어떤 차가 어느 곳을 어떤 순서로 갈지 자동으로 계획합니다. 앞에서 사람의 머리로는 따져 볼 수 없다고 했던 그 많은 경우의 수를, 엔진이 대신 좁혀 가며 좋은 답을 찾아 주는 거예요.

전체 물량을 한눈에 보고 나누기 때문에, 주문이 한쪽에 몰리는 날에도 차량별 업무량을 고르게 맞출 수 있죠. 한 권역은 바쁘고 옆 권역은 한가한 불균형이 줄어들면, 급하게 용차를 부르는 일도 그만큼 줄어들고요.

계획이 확정된 뒤의 흐름도 이어집니다. 기사님은 앱으로 경로를 받고, 관리자는 지도에서 계획한 경로와 실제 운행 현황을 함께 확인할 수 있어요. 결국 배차 담당자의 아침이 '계획을 짜는 시간'에서 '계획을 확인하고 예외 상황에 대응하는 시간'으로 바뀌는 셈입니다. 참고로 루티의 AI 배차 엔진은 국토교통부 '우수 물류신기술'로 지정되기도 했습니다.

물론 차량을 몇 대 줄이고 이동 거리를 얼마나 아낄 수 있을지는 회사마다 달라요. 물량도, 배송지도, 지켜야 할 조건도 모두 다르니까요. 그래서 가장 정확한 방법은 우리 회사의 실제 배차 데이터로 직접 확인해 보는 거예요.

우리 회사 물량이라면 차를 몇 대까지 줄일 수 있을까요? 감으로 짐작하기보다 실제 데이터로 확인해 보는 게 가장 빠릅니다. 루티로 지금의 배차를 진단해 보세요.