경로 최적화를 넘어서: 배송 권역을 검증하고 발굴하는 최적화 엔진 만들기

전용차량 한 대를 더 붙이는 게 이득일까요, 손해일까요? 그리고 어디를 묶어야 그 한 대가 흑자가 될까요? 경로를 최단으로 만드는 최적화는 이 질문에 답해주지 않았습니다. 저희가 만든 건 “가장 짧은 경로”가 아니라 “현장에서 방어 가능한 권역”을 찾는 엔진이었습니다.

안녕하세요, UMOSONE TMS(Transportation Management System) 개발팀의 Backend Engineer 백효현입니다.

이 글은 전용차량 배송 권역(zone) 을 비용 최소화 관점에서 추천·최적화하는 엔진을 만들면서, 흔히 말하는 “경로 최적화”를 어떻게 실제 물류 도메인을 검증하고 발굴하는 상용화 기술로 끌어왔는지에 대한 기록입니다. 결정의 근거, 실패한 접근, 운영에서 배운 제약을 함께 남깁니다.

이 글의 수치(손익분기 박스 수, 용량 상한, 절감 비율 등)는 방법론을 설명하기 위한 값이며, 실제 계약 단가·거점 위치·거래처 정보는 포함하지 않습니다.

경로 최적화가 답하지 않는 질문

배송 최적화라고 하면 보통 VRP(Vehicle Routing Problem), 즉 “주어진 배송지들을 가장 짧게 순회하라”를 떠올립니다. 많은 회사가 이 문제에 도전하고, 좋은 솔버도 많습니다. 그런데 저희가 실제로 답해야 했던 질문은 조금 달랐습니다.

• 전용차량(고정 계약)으로 직접 배송할 권역과, 건당 단가로 공동배송에 위탁할 물량을 어떻게 나눌 것인가?
• 어떤 읍면동들을 하나로 묶어야 그 권역을 맡은 차량이 손익분기를 넘겨 흑자가 되는가?
• 지금 운영 중인 전용차량 외에, 위탁 물량 안에 숨어 있는 추가로 전용화하면 이득인 권역은 없는가?

경로 최적화는 “이 배송지들을 어떻게 도느냐”에 답하지만, 위 질문들은 “애초에 어떤 배송지를 한 묶음으로 볼 것이냐”를 묻습니다. 묶음이 정해지기 전에는 경로가 없고, 묶음의 좋고 나쁨은 경로 길이가 아니라 비용과 제약으로 판단해야 합니다. 여기서부터는 경로 문제가 아니라 권역 설계 문제입니다.

비용 구조부터 세우기

권역이 이득인지 판단하려면 먼저 비용 모델이 필요했습니다. 전용차량은 거리 기반 계약이라, 한 권역 z의 월 차량비는 고정비와 주행비의 합으로 둘 수 있습니다.

차량비(z)      = F + r × 월주행거리(z)
월주행거리(z)  = ( 거점↔권역 왕복 스템 + 권역 내 전 읍면동 2-opt 투어 ) × 월 운행일수
절감액(z)      = 월박스(z) × p  −  차량비(z)          # p = 박스당 공동배송 단가
손익분기(z)    = 차량비(z) / p                          # 이만큼은 배송해야 본전

여기서 두 가지가 중요합니다.

첫째, 손익분기는 전역 상수가 아니라 권역별로 다릅니다. 차량비에 주행거리가 들어가므로, 거점에서 가까운 권역은 손익분기 박스 수가 낮고(≈900박스대도 흑자 가능), 먼 권역은 높습니다(월 1,200박스를 넘겨도 적자일 수 있음). 그래서 “월 1,200박스”라는 하나의 기준선으로 모든 권역을 재단하면 가까운 흑자 권역을 놓치고 먼 적자 권역을 잘못 채택합니다.

둘째, 어떤 흑자 권역에도 들어가지 못한 물량은 자동으로 공동배송으로 낙착됩니다. 즉 “효율화가 안 되면 위탁”이 별도 규칙이 아니라 비용 모델의 자연스러운 결과가 되도록 설계했습니다.

핵심 재정식화 — 비용 최소화를 절감액 최대화로

초기 버전(임베디드 JS greedy)은 “최대 몇 대까지”, “반경 몇 km까지” 같은 상한을 입력으로 받았습니다. 그런데 이 상한들이야말로 문제의 본질을 가리고 있었습니다. 몇 대가 최적인지는 우리가 정할 게 아니라 절감액이 정해야 했으니까요.

그래서 목적함수를 뒤집었습니다.

min  총비용
 = min [ Σ 전용권역 차량비(z)  +  Σ 공동배송 박스 × p ]
 = ( 전체 박스 × p )  −  Σ 선택권역 절감액(z)      ← 앞항은 상수
 ⟺ max  Σ 선택권역 절감액(z)
        s.t. 선택된 권역끼리 셀이 겹치지 않음,  절감액(z) > 0

전체 물량에 단가를 곱한 값은 무엇을 선택하든 상수입니다. 따라서 총비용 최소화는 “겹치지 않는 흑자 권역들의 절감액 합을 최대화”하는 문제와 완전히 같습니다. 이는 전형적인 최대가중 집합 패킹(max-weight set packing) 이고, maxZones 같은 상한이 원천적으로 필요 없어집니다. 몇 대를 뽑을지는 최적화가 절감액을 보고 스스로 결정합니다.

이 재정식화 덕분에 구조가 세 개의 레이어로 깔끔하게 갈라졌습니다.

레이어	역할	핵심
A. Routing	실행 가능성·비용 추정	이동시간 행렬 + 대표운행일 경로시간 게이트
B. Candidates	후보 권역 생성	폴리곤 인접 그래프를 따라 성장 → 중첩 허용 후보 풀
C. Optimize	선택	CP-SAT로 절감액 합 최대인 서로소 조합 선택

레이어 A — 크기를 정하는 건 반경이 아니라 시간

권역을 얼마나 크게 잡을지는 고정 반경으로 정하지 않았습니다. 실제 운영에서 권역 크기는 밀도의 결과였습니다. 서울 도심은 4km, 경기 외곽은 12km, 지방은 20km까지도 한 권역이 됩니다. 이걸 손으로 정하는 순간 현실과 어긋납니다.

대신 유일한 크기 제약을 “시간”으로 뒀습니다. 한 권역의 대표적인 하루 운행이 근무시간 안에 끝나면 실행 가능, 넘으면 불가능입니다.

하루 경로시간 = 주행시간 + ( 상차·준비 + 배송지 수 × 하차서비스 )
feasible(z)  = 대표운행일 경로시간(z) ≤ 근무창(450분)

이동시간 행렬은 오픈소스 라우팅 엔진으로 좌표 간 실측 이동시간을 뽑고(고유 좌표만 dedup, 48블록 단위, .npz로 캐시), 경로는 최근접 이웃(NN)으로 초기해를 만든 뒤 2-opt 로컬서치로 개선합니다.

실패담 ① — NN만 쓰면 흑자 권역이 탈락한다

처음엔 최근접 이웃 경로만으로 시간을 추정했습니다. 그런데 NN 단독 경로는 최적 대비 5~10% 과대추정을 합니다. 그 결과 실제로는 근무시간 안에 도는 흑자 권역이 “경로 초과”로 판정돼 탈락했습니다. 검토해 보니 탈락한 권역들은 경제성이 문제가 아니라 경로 추정이 부풀려진 것이었습니다. 2-opt를 붙이자 초과로 잘못 걸린 권역의 상당수가 회수됐습니다.

실패담 ② — “최악일” 게이트는 현실을 과대평가한다

더 미묘한 함정이 있었습니다. 처음엔 “권역의 모든 배송지를 매일 다 돈다”는 가정(all-cells, 사실상 최번일)으로 시간을 쟀습니다. 그런데 실제 기사는 그날 주문이 있는 배송지만 돕니다. 최악일 기준으로 재면 멀쩡한 권역이 계속 불가능으로 찍혔습니다.

그래서 게이트를 대표운행일(p50) 로 바꿨습니다. “그날 실제 주문이 있는 셀만 라우팅한 일별 소요의 중앙값이 근무시간 이하인가”로 판정합니다.

feasible(z) = median_over_days( 그날 활성 셀만 라우팅한 소요 )  ≤ 근무창

여기엔 반직관적인 성능 함정이 하나 더 있었습니다. “최악일이 통과하면 중앙값도 당연히 통과할 테니 건너뛰자”고 최적화하려 했는데, 최악일은 중앙값의 상한이 아니었습니다. 희소한 권역에서는 평균 배송지 수가 0인 날에 희석돼 최악일 추정이 오히려 중앙값보다 작게 나오는 경우가 있었습니다(실제로 이 때문에 근무초과 권역이 통과된 버그가 있었습니다). 해결책은 진짜 상한이 보장되는 피크일 기반 상한값을 따로 만들어, 그게 근무시간 이하일 때만 중앙값 계산을 건너뛰게 한 것입니다. 이 “값싼 문턱” 덕분에 1,200개가 넘는 씨앗을 몇 분 만에 처리할 수 있었습니다.

레이어 A½ — 도메인 제약을 코드로 옮기기

여기가 이 프로젝트에서 가장 “도메인”스러운 부분입니다. 순수한 거리 문제라면 필요 없지만, 실제 배송을 검증하려면 반드시 있어야 하는 제약들입니다.

① 근무창 450분 (스템 제외). 근무 8시간에서 식사·버퍼 30분을 뺀 7시간 30분을 예산으로 둡니다. 중요한 건 무엇을 이 예산에 넣느냐였습니다. 기사는 새벽에 거점에서 상차하고 첫 배송지로 이동하므로, 거점↔권역 왕복(스템) 주행은 근무창에서 제외하고 첫 배송지 도착부터 마지막 배송 완료까지만 잽니다. 이 구분을 하지 않았을 때는 거점에서 먼 권역(도심·외곽)이 왕복 스템 때문에 과잉 페널티를 받아 부당하게 탈락했습니다. (단, 계약 거리는 기사의 실주행이므로 차량비 계산에는 스템 왕복을 포함합니다. 시간 모델과 비용 모델의 거리 정의가 다르다는 점이 처음엔 헷갈렸습니다.)

② 강 불가침. “한강을 건너 배송하지 않는다”는 현장 규칙입니다. 손으로 그린 근사 중심선(본류 + 지류) GeoJSON을 두고, 두 셀의 중심을 잇는 선분이 이 강과 교차하면 인접이 아닌 것으로 간주해 인접·다리 간선을 제거했습니다. 이것만으로 강을 넘는 인접 쌍 100여 개가 사라졌습니다. 지리 데이터 없이 인접 그래프만 믿었다면, 다리도 없는 곳을 “가깝다”고 묶었을 겁니다.

③ 한 권역이 걸치는 시군구 ≤ 2. 성장 과정에서 한 권역이 세 번째 시군구로 번지지 않도록 막았습니다. 관리·정산 단위가 깔끔해지는 운영상의 이유도 있지만, 흥미로운 건 이 제약이 비용도 개선했다는 점입니다. 권역이 컴팩트해지면 주행이 짧아지고, 같은 450분 안에 더 많은 박스를 소화할 수 있어 전용 물량이 늘고 비용이 내려갔습니다. 여기서 “구가 있는 모든 시는 시+구를 한 단위로” 같은 행정구역 처리가 필요했는데, 특례시(예: 천안·청주 등도 시+구 구조)를 특정 지역만 하드코딩하면 다른 지역의 동이 통째로 사라지는 버그가 있어, 주소 레벨을 일반 규칙으로 판정하도록 고쳤습니다.

④ 월 용량 상한과 셀 분할. 한 대가 월 1,750박스까지 담는다고 두고, 물량이 큰 읍면동은 50박스 단위 조각으로 쪼갰습니다(월 운행일 × 배송지당 평균 박스 ≈ 50). 이렇게 하면 한 동을 여러 기사와 공동배송이 나눠 담을 수 있고, 넘치는 물량은 자동으로 공동배송으로 낙착됩니다. “한 동에 물량이 몰리면 어떻게 나눌까”라는 질문이 별도 로직 없이, 조각 분할 + 중첩 후보 + 최적화 선택의 조합으로 자연스럽게 풀립니다.

이 네 제약이 함께 작동하면, 반경을 한 번도 지정하지 않았는데도 “수도권은 작게, 지방은 넓게”가 저절로 만들어집니다. 권역 크기는 입력이 아니라 제약의 결과입니다.

레이어 B·C — 후보를 넉넉히 만들고, 최적으로 고른다

레이어 B는 폴리곤 인접 그래프를 따라 모든 셀을 씨앗으로 성장시킵니다. 손익분기를 넘는 순간과 시간 한계에 닿는 순간 등 여러 크기에서 후보를 방출하므로, 셀이 서로 겹치는 후보 풀이 만들어집니다. 풀의 다양성이 클수록 최적 조합이 그 안에 존재할 확률이 높아집니다.

레이어 C는 OR-Tools CP-SAT로 집합 패킹을 풉니다.

변수:  x_z ∈ {0,1}                       # 후보 권역 z 채택 여부
제약:  각 셀 c 에 대해  Σ_{z ∋ c} x_z ≤ 1   # 셀 중첩 금지 (미커버 = 공동배송)
목적:  max  Σ_z  x_z · 절감액(z)            # 절감액>0 후보만 풀에 포함

maxZones도 반경도 없습니다. 겹치지 않게 고르면서 절감액 합이 최대가 되는 조합을 CP-SAT가 찾고, 어디에도 뽑히지 않은 셀은 공동배송으로 남습니다.

상용화의 갈림길 — “답을 주는 도구”가 아니라 “검증하는 도구”

여기까지가 최적화입니다. 그런데 저희가 정말 신경 쓴 부분은 그다음이었습니다. 모델은 낙관한다는 것을 알고 있었기 때문입니다.

후보 생성은 읍면동 중심점 기준으로 빠르게 경로를 추정합니다. 중심점은 셀 내부에 흩어진 실제 배송지들을 무시하기 때문에, 특히 배송지가 듬성듬성한 희소 권역에서 소요 시간을 과소평가합니다. 이 낙관을 그대로 “권장안”으로 내보내면, 현장에서 “계산은 되는데 실제로는 안 돌아가는” 안을 파는 셈이 됩니다.

그래서 검증 단계를 붙였습니다.

실측 재검증. 선택된 권역을 운행일별 실제 배송지 좌표로 다시 라우팅합니다. 방문 순서는 별도 솔버로 최적화하고, 주행거리·시간은 실측 도로망으로 계산합니다. 각 운행일의 원자료(배송지 수·박스·소요·거리)를 캐시해 두어, 나중에 임의의 백분위를 다시 라우팅 없이 재계산할 수 있게 했습니다. 이렇게 재보면 모델이 말하던 절감 폭은 줄어듭니다. 글로벌 재편성 모드 기준 모델은 약 −9%를 말했지만, 실측으로 되돌리면 약 −5%대가 정직한 숫자였습니다. 편향은 밀도에 따라 양방향입니다. 스캐터가 심한 권역은 과소추정, 밀집 권역은 과대추정이라, 실측이 항상 나쁜 쪽으로만 움직이지도 않았습니다.

처리량 테스트 — 판정 기준 자체를 바꾸다. 처음엔 “매일 근무시간 이하”를 기준으로 삼았습니다. 그런데 이건 현장 운영과 맞지 않았습니다. 고물량일에 초과분이 생기면 그날은 일부를 공동배송으로 넘기면 그만이고, 전용차량이 매일 근무시간 안에 끝나야 할 이유는 없습니다. 진짜 문제는 다른 데 있었습니다 — 저물량일에 배송지가 파편화돼 시간이 초과되면, 정작 손익분기를 채울 만큼의 물량을 소화하지 못하는 것입니다.

그래서 게이트를 “매일 ≤ 근무”에서 처리량으로 바꿨습니다.

월 배송가능(z) = Σ_운행일  일박스 × min(1, 근무 / 그날 소요)  ÷  개월수
유효(z)        = 월 배송가능(z) ≥ 손익분기(z)         # 시간비례 근사임을 명시

즉 “하루 450분까지 소화하고 초과분은 공동배송으로 넘긴다고 했을 때, 그래도 손익분기 이상 배송할 수 있는가”를 봅니다. 저물량일 시간초과 횟수는 파편화 위험 신호로 따로 진단합니다. 이 기준으로 보면 중앙 운행일에 조금 초과하는 권역도 대부분 유효로 판정되고, 정말 걸러야 할 것은 손익분기 근처에서 아슬아슬한 소수 권역이라는 게 드러납니다.

이 “시간비례 근사”는 정확한 시뮬레이션이 아니라 운영 모델을 반영한 근사이며, 리포트에도 근사임을 명시합니다. 검증 리포트는 가설성 보정(안정성 패널티 등)을 섞지 않고 “지금 실제로 이익을 내는가”만 판단한다는 원칙을 지켰습니다.

목적을 “재편성”에서 “발굴”로 바꾸다

초기엔 전용 + 공동배송 전체를 글로벌 재편성해 “현행 대비 몇 대 감축, 약 −9%” 같은 결론을 냈습니다. 숫자는 컸지만, 실제 운영 중인 계약과 노선을 통째로 흔드는 안이라 현장 적용이 부담스러웠습니다.

그래서 목적을 바꿨습니다. 기존 전용차량은 그대로 고정하고, 공동배송·택배로 위탁 중인 잔여 물량 안에서 추가로 전용화하면 이득인 권역만 발굴하는 방향입니다.

• 후보 성장과 집합 패킹의 대상은 위탁 물량(공동배송 + 택배)만으로 한정하고, 기존 전용은 셀 풀에서 빼되 지도에는 고정 표시합니다.
• 발굴된 권역은 순수 추가분이라 기존 계약비가 양쪽에 공통으로 상쇄되고, 실운영 노선을 건드리지 않아 훨씬 방어적입니다.

추가 절감 = ( 전환된 위탁 물량 × p )  −  Σ 신규 발굴권역 차량비(z)  =  Σ 절감액(z)

발굴 프레임에서는 위탁 물량 풀이 희소해(배송지당 물량이 적어) 후보 성장이 느리지만, 결과적으로 수도권·충청권에서 소수의 권역을 추가로 발굴할 수 있었고 위탁비의 약 10%를 절감하는 것으로 나왔습니다. 다만 이 역시 처리량 테스트로 되돌려 보면 일부 권역은 손익분기 마진이 근소해, 물량 변동 시 이탈 1순위로 관찰 대상에 두었습니다. “발굴했다”로 끝내지 않고 “얼마나 방어 가능한가”까지 붙이는 것이 이 엔진의 핵심입니다.

정직하게 남긴 한계

상용화를 목표로 했기에, 잘 되는 것만큼 안 되는 것도 명시적으로 남겼습니다.

• 실행가능성은 대표운행일 기준입니다. 최번일에는 근무시간을 넘을 수 있고, 이건 초과분 공동배송 이관을 전제로 합의한 모델입니다.
• 최적성은 생성된 후보 풀 기준이지 전역 최적이 아닙니다. 후보 생성이 인접-최근접 성장이라, 더 다양한 풀로 추가 개선 여지가 있지만 체감 이득은 줄어듭니다.
• 강 근사 중심선은 손으로 그린 근사입니다. 정밀 하천 데이터가 아니라, 정점 편집으로 정밀도를 올릴 수 있습니다.
• 실측 검증은 사후 축소이지, 실측 라우팅을 후보 생성 루프 안에 넣은 전역 재최적화는 아닙니다. 완전 정합하려면 실측을 실행가능성 판정에 통합해야 하고, 그만큼 느려집니다.

이 한계들을 숨기지 않은 이유는 분명합니다. 최적화 결과를 “정답”처럼 제시하면 현장은 한 번 어긋나는 순간 도구 전체를 불신합니다. 어디까지 믿을 수 있고 어디부터 다시 확인해야 하는지를 같이 내보내는 편이, 실제로 쓰이는 도구가 되는 길이었습니다.

마치며

경로 최적화는 이미 많은 회사가 잘 풀고 있는 문제입니다. 저희가 붙들었던 건 그 앞과 뒤였습니다. 앞에서는 순수한 거리 문제를 손익분기·근무창·강·행정경계·용량이라는 도메인 제약이 박힌 집합 패킹 문제로 재정식화했고, 뒤에서는 낙관적인 모델을 실제 배송지 좌표로 되돌려 처리량 기준으로 검증했습니다.

정리하면 이렇습니다.

• 재정식화가 상한을 지운다 — 비용 최소화를 절감액 최대화로 뒤집으니 “몇 대”가 입력에서 결과로 바뀌었습니다.
• 제약이 크기를 정한다 — 반경을 지정하는 대신 시간·지리·행정 제약을 넣으니 권역 크기가 밀도의 결과가 됐습니다.
• 검증이 신뢰를 만든다 — 모델의 낙관을 실측과 처리량 테스트로 되돌려야 현장에서 방어 가능한 안이 됐습니다.

단순 최적화를 서비스에 녹이는 일은 더 좋은 솔버를 붙이는 게 아니라, 우리 도메인의 제약과 검증 기준을 최적화 안으로 끌어들이는 일이었습니다. 그 과정에서 최적화 엔진은 “답을 주는 기계”가 아니라 “권역을 검증하고 발굴하는 도구”가 되었습니다.

비슷한 고민을 하는 팀이 있다면, 어떤 제약을 모델 안으로 넣었고 어디서 낙관을 걷어냈는지 이야기 나눠보고 싶습니다. 긴 글 읽어주셔서 감사합니다.