[배송 권역 시스템 2편] 수도권 새벽 배송 자동 배차 시스템 – 구현을 하면서 깨달은 것들

1편에서는 “수도권 새벽 배송 3만 건을 어떻게 배정·경로화할 것인가”를 문제 정의와 전체 구조 중심으로 정리했다.
이번 2편에서는 구현을 진행하면서 실제로 무엇을 했고, 무엇을 배웠고, 앞으로 어떻게 개선할 생각인지를 가볍게 정리해 보려고 한다.

세부 구현(점수 함수 상수, 실제 코드, 쿼리 등)은 일부러 추상화해서 적었다.
아직 개선점이 많고 부족하기 때문에, 설계·아이디어 수준까지만 먼저 공유한다.

 

1. 이번에 실제로 무엇을 했나

큰 틀에서 이번 프로젝트에서 한 일은 세 가지로 정리할 수 있다.

1-1. CVRP를 현실적으로 풀기 위해 2단계로 분리했다

“기사 수백 명 + 배송 3만 건 + 시간/케파 제약”은 학술적으로 CVRP(Capacitated VRP)에 해당한다.
이걸 한 번에 풀려고 하면 다음 문제가 바로 걸린다.

• OSRM Table API의 거리 행렬 크기 한계
• 3,000건 이상에서 거리 매트릭스 생성 비용
• 1~2초 이내에 결과를 보고 싶어 하는 운영자 UX
• 배차가 매일 밤 돌아간다는 운영 현실

그래서 처음부터 “완벽한 CVRP 솔버”를 목표로 하기보다는, 문제를 다음 두 단계로 분리했다.

• 1단계: 누가 어떤 건을 담당할지 결정 (클러스터링/배정)
• 2단계: 각 기사별로 어떤 순서로 방문할지 결정 (경로/TSP)

이렇게 나누면, 1단계는 거리 기반 클러스터링 문제에 가깝게, 2단계는 기사별 TSP 문제로 축소된다.

1-2. 1단계 — H3 + Capacity-aware Greedy 배정

배정 단계에서 한 핵심 작업은 다음과 같다.

• 위경도 좌표만 들고 있는 배송 건들을 H3 셀로 묶어서,
  • 같은 건물·아파트에 있는 배송은 반드시 같이 움직이게 하고,
  • 3만 건을 약 2천 개 셀 정도 규모로 축소했다.
• 그 위에서 “거리 + load penalty”를 하나의 점수 함수로 통합해서,
  • 지리적으로는 최대한 가까운 기사에게,
  • 기사당 케파(약 80건)는 너무 벗어나지 않도록 Capacity-aware Greedy 방식으로 배정했다.
• 중간에 v1~v6까지 여러 버전을 거치면서:
  • 거리만 보면 물량이 망가지고,
  • 물량만 맞추면 기사 동선이 수도권 전체로 터지는 걸 직접 겪었다.

최종적으로는:

• 기사당 38~67건 정도의 범위,
• 평균 span 약 1.89km 정도의 클러스터를 만들어 내는 수준까지 조정했다.

1-3. 2단계 — OSRM Trip으로 실도로 기반 경로 최적화, ETA 계산

배정이 끝난 뒤, 기사별로 묶인 배송 건(대략 60~80개)을 가지고:

• OSRM Trip API를 호출해서,
  • 실도로 기준 최단에 가까운 방문 순서,
  • 총 이동 거리/시간을 얻고,
• 22:00 출발 기준으로 각 배송 건의 예상 도착 시각(ETA) 를 계산했다.

이 정도까지 구현했을 때, 강남권 2,870건/45명 기준으로 전체 배차 + 경로 계산이 약 1.6초에 끝나는 수준까지 만들어 냈다.

2. 구현하면서 가장 크게 배운 것들

2-1. 이론 100점보다, “제약 안에서 80점짜리 해”를 만드는 일이 더 어렵다

이론적으로만 보면, CVRP는 OR-Tools 같은 솔버로 “배정 + 경로 최적화”를 한 번에 풀 수 있다.
하지만 실제로는 다음 제약들이 걸려 있었다.

• 거리 매트릭스 API(OSRM Table)의 행렬 크기 제한
• 3,000건 이상에서 거리 매트릭스를 만들 때의 비용
• 운영자가 1~2초 안에 결과를 보고 싶어 한다는 UX 요구
• 이 작업이 “한 번”이 아니라 매일 밤 반복된다는 운영 현실

그래서 이 프로젝트의 목표는

“수학적으로 얼마나 최적인가” 보다 “3만 건/600명 규모에서, 1~2초 내에 운영자가 수용할 수 있는 배차안을 만들 수 있는가” 에 더 가까웠다.

그 기준으로 보면:

• CVRP를 통째로 풀기보다는 2단계 분리(배정+경로)가 맞았고,
• 배정 단계에서는 Greedy + 리밸런싱 조합이 “가장 단순하면서도 충분히 품질이 나오는 선택”이었다.

2-2. 알고리즘 복잡도 절반은 데이터 파이프라인이 만든다

이번 구현에서 배정 알고리즘이 필요 이상으로 복잡해진 이유 중 하나는, 배송 데이터에 h3_cell이 사전에 완전히 매핑되어 있지 않았다는 점이다.
 
그래서 런타임에:

• 좌표 기반 H3 계산,
• H3가 없는 경우 좌표 기반 가상 셀(~11m) 생성,
• 일부 리밸런싱 단계에서 이런 예외들을 다시 고려하는 작업을 알고리즘 안에서 모두 떠안아야 했다.

이 경험을 통해 자연스럽게 이런 생각이 들었다.

“알고리즘을 단순하게 만들고 싶다면, 먼저 데이터 파이프라인과 스키마를 단순하게 설계해야 한다.”

실제 상용 서비스에 이 시스템을 넣는다면:

• 이벤트 인입/ETL 단계에서 배송 건별로 h3_cell을 확정적으로 매핑해 두고,
• 배차 알고리즘은 “이미 정제된 H3 셀 집합”을 전제로 최대한 심플하게 설계하는 게 맞다고 느꼈다.

2-3. “보정 처리”도 결국 알고리즘의 일부다

처음에는 K-Means, K-Medoids, GA, OR-Tools 같은 “알고리즘 이름”에 꽂혀 있었는데, 실제로 구현을 진행하면서 더 많이 시간을 쓴 부분은 이런 것들이었다.

• H3 누락으로 인한 그룹핑 오류
• 기사 수를 물량 기준으로 잡았다가, 나중에 시간 제약을 고려해 전면 수정한 일
• OSRM와 Spring/Jackson 버전 충돌로 인한 JSON 파싱 문제
• 배차 API 멱등성(더블클릭/재시도 시 중복 run 생성) 설계

이런 것들을 하나씩 해결하고 나니, 내가 만든 건 “교과서적인 CVRP 해결 알고리즘”이라기보다는,

“현실 데이터와 제약을 보정하면서, 운영자가 실제로 쓸 수 있는 레벨까지 결과를 끌어올리는 파이프라인”에 더 가깝다는 걸 인정하게 되었다.

 
이걸 받아들이고 나니,

• “이건 이상적인 CVRP 솔루션이 아니야”라는 컴플렉스는 줄고,
• “그래도 이 정도면 실제 서비스에 꽂아서 돌려 볼 수 있는 수준”이라는 자신감이 조금 생겼다.

3. 이번 프로젝트에서의 AI 활용과 배운 점

이 프로젝트는 처음부터 끝까지 AI를 적극적으로 활용한 프로젝트이기도 했다. 단순히 코드 자동완성을 넘어서, “AI와 역할을 나누어 함께 일하는 경험”을 해 본 것이 가장 큰 수확이었다.

3-1. 모르는 지식을 빠르게 검색·비교할 수 있었다

Haversine, K-Medoids, CVRP, OSRM Trip 같은 개념들은 한 번에 다 이해하기 쉽지 않은 주제였다.
AI를 사용해서:

• 관련 개념을 요약해서 비교하고,
• 각 접근의 장단점과 적용 사례를 한 번에 훑어볼 수 있었다.

결과적으로 “내가 어떤 키워드로 더 깊이 공부해야 하는지”를 빠르게 파악할 수 있었다.

3-2. “혼자서도 팀처럼” 프론트와 백을 동시에 밀어붙일 수 있었다

이전까지는 혼자서 백엔드·프론트·인프라를 모두 책임지는 프로젝트를 하기 부담스러웠다.
이번에는:

• 백엔드 설계와 핵심 도메인 코드는 내가 직접 주도하고,
• 프론트엔드 컴포넌트 구조, Leaflet 예제, Zustand 스토어 구성 같은 반복적인 부분은 AI에게 초안을 생성하게 한 뒤,
• 리뷰·수정하는 방식으로 진행했다.

덕분에 실질적으로는 혼자 일하면서도 “2~3명의 팀으로 일하는 속도”를 낼 수 있었다.

3-3. 생산성이 체감될 정도로 올라갔다

스펙 작성 → 코드 초안 → 리팩터링 → 문서화의 전 과정을 AI와 같이 돌리다 보니,

• 반복적인 코드 작성 시간,
• 라이브러리 사용법을 찾는 시간,
• 문서 초안 만드는 시간이 크게 줄었다.

그만큼 나는:

• 비즈니스 제약 정의,
• 알고리즘 선택,
• 테이블/인덱스 설계,
• 성능 튜닝 같은

“사람이 할 수 있는 의사결정”에 더 많은 시간을 쓸 수 있었다.

3-4. Human-in-the-loop: 설계·품질에 대한 제어권은 끝까지 내가 가진다

이번 프로젝트에서 의식적으로 지켰던 원칙이 하나 있다.

“AI가 많은 것을 제안해도, 최종 설계와 품질에 대한 제어권은 항상 내가 가진다.”

AI가 제안한 설계/코드를 그대로 받아들이지 않고,

• 도메인 제약과 맞는지,
• 성능/복잡도 관점에서 합리적인지,
• 내 시스템의 방향성과 일치하는지를 검토하는 과정을 항상 끼워 넣었다.

덕분에:

• AI가 제시한 아이디어 중 “좋은 것만 골라 쓰는 필터 역할”을 할 수 있었고,
• 문제가 있는 부분은 바로 짚어서 수정하거나, 아예 다른 방향으로 다시 설계할 수 있었다.

3-5. “코드를 잘 치는 것”보다 “아키텍트로서의 역량”이 더 중요하다는 걸 다시 느꼈다

AI를 적극적으로 쓰다 보니, 오히려 “코드를 직접 치는 능력”의 상대적 비중이 줄어드는 느낌을 받았다.
대신 훨씬 중요해진 것은:

• 문제를 어떻게 모델링할지,
• 어떤 알고리즘/아키텍처를 선택할지,
• 어디까지를 자동화하고 어디부터를 운영자 판단에 맡길지,
• 시스템 전체를 어떻게 단계별로 발전시킬지

같은 아키텍처/설계 역량이었다.
 
특히 나는 원래 일반적인 백엔드 개발자였고, 프로젝트를 시작할 때는 VRP, CVRP, 배차·배정 알고리즘에 대한 배경 지식이 거의 없었다.

 
그럼에도 이 정도 규모의 시스템을 만들 수 있었던 이유는,

• AI를 통해 관련 개념과 논문·글들을 빠르게 찾아보고 비교·요약할 수 있었고,
• 그 위에서 내가 직접 “어떤 방식이 이 문제와 제약에 맞는지”를 선택해 나갔기 때문이다.

결국 중요한 것은,

“AI가 문제를 대신 풀어주는가?” 가 아니라
“AI가 던져주는 수많은 옵션 중에서,
어떤 것을 선택해서 어떤 구조로 엮을지 결정하는 사람의 역할”

 
이라는 걸 많이 느꼈다.
 
그래서 오히려:

• 알고리즘, 분산 시스템, 최적화, 도메인 지식 등에 대해 더 많이 공부해야겠다는 동기가 생겼다.
• AI가 제시하는 방향과 코드를 이해할 수 있는 지식이 있다면,
• AI에 끌려가는 것이 아니라,
• AI를 레버리지로 삼아 더 멀리, 더 빠르게 갈 수 있다고 느꼈다.

4. 다음 단계에서 개선하고 싶은 것들

이번 프로젝트는 “불완전한 데이터와 제약 속에서 쓸 만한 해법을 만드는 것”에 초점을 맞췄다.

 
다음 단계에서는 같은 문제를 더 깔끔한 구조와 더 강한 기능으로 풀어보고 싶다.

4-1. H3 사전 매핑으로 알고리즘 단순화

현재 배정 알고리즘은 배송 데이터에 h3_cell이 완전히 매핑되어 있지 않다는 전제를 두고 설계되어 있다.
그래서 런타임에 다음과 같은 보정 처리가 들어가 있다.

• 좌표 기반 H3 계산 및 fallback
• 일부 리밸런싱 단계에서 예외 케이스에 대한 추가 처리

다음 버전에서는:

• 데이터 인입/ETL 단계에서 배송 건별 h3_cell을 사전에 확정하고,
• 배차 알고리즘은 “정제된 H3 셀 집합”만을 입력으로 받는 구조로 바꾸고자 한다.

이렇게 하면:

• 현재 여러 단계에 흩어져 있는 보정 로직을 대폭 줄이고,
• 알고리즘을 더 단순한 형태(K-Medoids/Greedy 중심)로 재구성하면서도
• 성능과 품질은 지금과 같거나 더 나은 수준으로 끌어올릴 수 있을 것으로 기대한다.

4-2. 실시간 추적과 동적 리라우팅

현재 시스템은 “배차 시점 기준의 정적 시뮬레이션”에 가깝다.
다음 단계에서는 실시간성을 포함한 시나리오를 실험해 보고 싶다.

• 기사 앱 또는 위치 스트림을 통해 기사 실시간 위치를 수집하고,
• WebSocket/Server-Sent Events로 운영 화면에 현재 위치와 진행률을 표시하며,
• 지연·추가 주문·취소 등 이벤트가 발생했을 때,
  • 해당 기사의 잔여 경로를 부분 재계산하거나,
  • 인근 기사와의 재배정을 고려하는 동적 리라우팅을 시도해 보고자 한다.

이를 통해:

• “배차 시점의 최적화”를 넘어서
• “운영 중에도 계속해서 경로와 ETA를 갱신하는 시스템”으로 확장하는 것을 중·장기 목표로 삼고 있다.

실제 동작 화면

아래 영상은 실제로 동작하는 배차 시뮬레이션 화면을 녹화한 것이다. 권역을 선택하고 자동 배차를 실행하면, 기사별 클러스터(색상), OSRM 기반 경로, 기사별 물량/동선 요약 정보가 동시에 표시된다. 초기 로딩부터 배차 실행, 경로 시각화 확인까지의 흐름을 한 번에 볼 수 있다.