Route optimization은 정류장 순서와 차량 배정을 통해 플릿이 최소 시간, 거리, 비용으로 작업을 끝내도록 하는 작업입니다. 같은 밴과 같은 정류장으로 4시에 끝나는 배달 기사와 7시에 끝나는 기사의 차이를 만들어내는 게 바로 이것입니다. 물류 앱의 모든 "최적화된 경로" 버튼 뒤에는 수백만 가지 가능한 순서를 방금 씹어 삼키고 그중 하나를 골라낸 솔버가 자리하고 있습니다.
이 가이드는 route optimization이 실제로 무엇인지, 솔버가 어떻게 접근하는지, 현실에서 어디에 등장하는지, 그리고 어떤 제약과 함정이 데모와 프로덕션을 갈라놓는지 설명합니다.
Route Optimization의 본질
컴퓨터 과학에서 route optimization은 두 가지 고전 문제 안에 자리잡고 있습니다. Travelling Salesman Problem(TSP)은 묻습니다. 도시 리스트와 그들 사이의 거리가 주어졌을 때, 모든 도시를 정확히 한 번씩 방문하고 출발지로 돌아오는 가장 짧은 경로는 무엇인가? 단일 차량 문제죠. Vehicle Routing Problem(VRP)은 이를 플릿으로 일반화합니다. 데포, 고객 집합, 여러 차량이 주어졌을 때, 고객을 어떻게 차량에 나누고, 각 차량은 어떤 순서로 방문해야 하는가?
두 문제 모두 NP-hard입니다. 가능한 순서의 수가 정류장 수에 따라 팩토리얼로 늘어납니다. 정류장 20개만 되어도 가능한 경로가 10의 18제곱 개를 넘습니다. 어떤 정확한 알고리즘도 그 공간을 실시간으로 탐색할 수 없습니다. 따라서 프로덕션에서의 optimization은 완벽한 답을 찾는 게 아닙니다. 행동에 옮길 만큼 빠르게, 매우 좋은 답을 찾는 것입니다.
솔버의 접근 방식
탐색 공간이 거대하기 때문에 실제 솔버는 여러 기법을 섞어 씁니다.
작은 문제(대략 15개 정류장 미만)에서는 branch-and-bound나 정수 계획법 같은 정확한 방법으로 몇 초 안에 증명 가능한 최적해를 반환할 수 있습니다. 그 규모를 넘어서면 정확한 방법은 실용성을 잃고, 분야는 휴리스틱으로 넘어갑니다.
전형적인 파이프라인은 nearest-neighbour나 Clarke-Wright savings 알고리즘 같은 구성적 휴리스틱으로 초기 경로를 만드는 것에서 시작합니다. 그 경로는 메타휴리스틱에 넘겨져, 정류장을 swap하거나, sub-tour를 reverse하거나, 정류장을 차량 사이에서 이동시키며 목적 함수를 반복적으로 개선합니다. Simulated annealing, tabu search, large neighbourhood search, genetic algorithm이 가장 흔한 선택지입니다. 모두 같은 형태입니다. 변경을 시도하고, 받아들일지 결정하고, 고정된 시간 예산 동안 반복하는 것이죠.
또 하나의 핵심 입력은 distance matrix입니다. 모든 정류장 쌍 사이의 이동 시간과 거리를 미리 계산한 표죠. 옵티마이저는 탐색 중에 matrix를 수백만 번 조회하므로, matrix는 라우팅 엔진으로 사전에 한 번 빌드해서 솔버 실행 동안 메모리에 보관됩니다.
Route Optimization이 등장하는 곳
Route optimization은 운영 비즈니스의 긴 목록을 조용히 떠받치고 있습니다.
- 라스트마일 배송: 택배사, 식료품 배달, 이커머스 풀필먼트가 모두 밴 한 대당 하루 수십에서 수백 개의 정류장을 시퀀싱합니다
- 현장 서비스: HVAC 기술자, 통신 설치 기사, 방문 간호사가 약속 시간 윈도우와 스킬 요구사항을 가진 고객들을 지역에 걸쳐 방문합니다
- 모바일 인력: 유틸리티 작업자, 미터기 검침원, 검사관이 다양한 작업 유형이 섞인 영역을 커버합니다
- 음식 배달: 레스토랑 어그리게이터가 지리가 맞을 때 여러 주문을 단일 라이더 트립으로 묶습니다
- 폐기물 수거: 시청 트럭이 정해진 주간 라운드를 도는데, 작은 재정렬도 실제 연료를 절약합니다
- 영업 담당자: 영역 계획에서 담당자가 하루에 8~12개 거래처를 방문하고, 운전 시간과 미팅 밀도를 위해 순서가 중요해집니다
모든 경우에 사용자는 올바른 순서로 정렬된 정류장 리스트를 봅니다. 작업은 그 뒤의 옵티마이저에서 일어나죠.
중요한 제약 조건들
거리만 최소화하는 솔버는 장난감입니다. 프로덕션 라우팅은 제약 조건으로 정의됩니다.
- 차량 용량: 각 밴은 무게, 부피, 또는 팔레트 한도가 있고 배정된 정류장이 이를 초과하면 안 됩니다
- 시간 윈도우: 고객은 가령 오전 9~11시 사이의 배달을 기대하며, 11시 5분 도착은 실패입니다
- 기사 시프트: 최대 근무 시간, 의무 휴식, 특정 데포에서의 시작과 종료
- 스킬 또는 차량 매칭: 냉장고 설치는 2인 팀이 필요하고, 콜드체인 배송은 냉장 밴이 필요합니다
- 다중 데포: 대형 플릿은 여러 창고에서 디스패치하며, 솔버가 어느 데포가 어느 정류장을 처리할지 결정합니다
- 베이스 복귀: 어떤 경로는 오픈(기사가 집에서 종료)이고, 어떤 경로는 클로즈(기사가 데포로 복귀)입니다
각 제약은 가능한 경로 집합을 좁히고, 솔버를 종이 위에서는 약간 나빠 보이지만 실제로 실행 가능한 솔루션 쪽으로 밀어붙입니다.
프로덕션의 함정
Route optimization은 데모는 항상 잘 되지만 롤아웃이 자주 안 되는 카테고리입니다.
잘못된 목적 함수 최적화. 거리 최소화가 기본값이지만, 많은 플릿에게는 절약된 킬로미터보다 매출이나 SLA 준수가 더 중요합니다. 2km를 더 가는 대가로 택배 한 개를 더 떨어뜨리는 경로는 보통 이득입니다.
자유흐름 vs 트래픽 인식 시간. 원시 도로 속도로 만든 matrix는 4시간 걸린다고 알려주는데, 러시아워 트래픽에서는 6시간 걸립니다. 경로가 실행될 시간대의 트래픽 인식 이동 시간을 노출하는 라우팅 엔진을 사용하세요.
실시간 재계획 부재. 기사가 예상치 못한 트래픽을 만나거나, 고객이 취소하거나, 새 정류장이 들어오는 순간 계획은 흐트러집니다. 운영팀은 아침에 만든 작업을 버리지 않고도 남은 정류장을 한낮에 재최적화할 방법이 필요합니다.
고정된 계획의 노후화. 1월에는 최적이었던 주간 고정 경로가 지금은 20% 더 나쁩니다. 고객이 이사했고, 물량이 바뀌었고, 일방통행이 새로 생겼기 때문이죠. 주기적으로 optimization을 다시 돌리고, 기사들에게 변경을 강요하기 전에 새 계획과 현재 계획을 비교하세요.
MapAtlas의 Route Optimization
MapAtlas Optimize Route API는 운영팀이 실제로 필요로 하는 제약(용량, 시간 윈도우, 시프트, 스킬, 다중 데포)으로 단일 차량과 플릿 라우팅 문제를 해결합니다. 차량별로 시퀀싱된 계획과 모든 정류장에 대한 예상 도착 및 출발 시간을 반환합니다.
MapAtlas 스택의 다른 두 엔드포인트와 자연스럽게 짝을 이룹니다. Distance Matrix API는 솔버가 소비할 이동 시간 표를 트래픽 인식 시간으로 만들어 러시아워에도 계획이 유지되도록 합니다. Directions API는 순서가 정해진 후에 연속된 정류장 사이의 실제 턴바이턴 도로 경로를 그려, 기사 앱이 직선이 아니라 진짜 폴리라인을 보여줄 수 있게 해줍니다.
Route optimization은 슬라이드 덱에서는 화려해 보이지 않을 겁니다. 솔버, matrix, 제약 조건 리스트일 뿐이죠. 하지만 플릿이 시간 안에, 예산 안에 하루를 끝낼지 결정하는 레이어이고, 이걸 제대로 해내는 것이 출시되는 라우팅 기능과 조용히 꺼지는 라우팅 기능을 가르는 차이입니다.
자주 묻는 질문
Route optimization이란 무엇인가요?
Route optimization은 정류장 집합을 방문할 최적 순서를 결정하고, 차량이 둘 이상이라면 어느 차량이 어느 정류장을 처리할지 결정하는 과정입니다. 목표는 차량 용량, 기사 시프트, 고객 시간 윈도우 같은 실제 제약을 지키면서 총 운전 시간, 거리, 연료, 비용 같은 목적 함수를 최소화하는 것입니다. 컴퓨터 과학에서는 두 가지 고전 문제 안에 자리합니다. 단일 차량의 Travelling Salesman Problem(TSP)과 플릿의 Vehicle Routing Problem(VRP)입니다.
Route planning과 route optimization의 차이는 무엇인가요?
Route planning은 'A에서 B까지 어떻게 가는가'에 답합니다. 두 점 사이의 단일 경로를 반환하며, 보통 턴바이턴 안내가 포함됩니다. Route optimization은 '6대의 밴으로 80개 정류장을 어떤 순서로 방문해야 하고, 어느 밴이 어느 정류장을 맡을지'에 답합니다. Optimization은 planning보다 한 층 위에서 동작합니다. 시퀀스와 배정을 결정한 다음, 각 정류장 쌍 사이의 실제 도로 경로를 그리기 위해 라우팅 엔진을 호출하죠.
Route optimization에는 어떤 알고리즘이 사용되나요?
작은 문제(대략 15개 정류장 미만)에서는 branch-and-bound나 정수 계획법 같은 정확한 방법으로 증명 가능한 최적해를 찾을 수 있습니다. 그 이상이 되면 탐색 공간이 폭발하고, 프로덕션 시스템은 휴리스틱과 메타휴리스틱을 사용합니다. 초기 해를 위한 nearest-neighbour와 savings 알고리즘, 그리고 이를 개선하기 위한 local search, simulated annealing, tabu search, 또는 genetic algorithm입니다. 대부분의 상용 솔버는 이런 기법들을 결합하고, 증명된 최적해까지가 아니라 고정된 시간 예산 동안 실행됩니다.
Route optimization API는 어떤 입력을 필요로 하나요?
최소한 좌표가 있는 정류장 리스트, 시작과 종료 위치가 있는 차량들, 그리고 모든 정류장 쌍 사이의 거리 또는 시간 matrix가 필요합니다. 실제로는 차량 용량, 고객 시간 윈도우, 각 정류장의 서비스 소요 시간, 기사 시프트 시간, 정류장별 필수 스킬이나 차량 타입, 데포 위치도 함께 입력합니다. Matrix는 가장 무거운 입력이며, 보통 옵티마이저 실행 전에 별도의 distance matrix API로 생성됩니다.
