REINDEERS CORE ENGINE DEEP DIVE

REINDEERS CORE ENGINE DEEP DIVE — PART 6

이번 파트에서는 REINDEERS 플랫폼의 DVRP 코어 엔진, 즉 DO 생성 → 배차 → 경로 최적화 → ETA 보정 → 재배차(Re-dispatch)까지 이어지는 전체 기술 구조를 정리한다.

여기서 다루는 내용은 이론적인 DVRP 설명이 아니라, 실제로 운영 가능한 수준으로 구현한 제약 기반 최적화 + AI 보정 + MQ/캐시 구조에 대한 기록이다.

37. DO 시스템의 기본 구조 재정리

REINDEERS는 모든 운송 지시를 DO(Delivery Order)로 통일했다.

Pickup DO — 고객사 → 창고 (입고용)
Delivery DO — 창고 → 고객사 (출고용)
Direct DO — 고객사 → 목적지 (직배송, 창고 미경유)

ASN/OSN은 어디까지나 입·출고 계획(Notice)이고, 실제 트럭이 움직이는 단위는 DO이다. DVRP 엔진이 다루는 모든 대상은 결국 “DO 집합”이다.


ASN / OSN (계획)
   ↓ (DO 생성기)
DO 집합 (Pickup / Delivery / Direct)
   ↓ (DVRP 엔진)
트럭·기사·경로·ETA

38. DVRP 엔진의 목표와 제약 조건

REINDEERS DVRP 엔진은 전형적인 VRP를 그대로 구현하지 않는다. 실제 현장의 제약을 우선해서 알고리즘을 구성했다.

38.1 최적화 목표

총 운행 거리 최소화
지각(ETA 초과) 최소화
트럭 당 적재율(CBM/중량) 최대화
AI 배차 실패율 최소화

38.2 강제 제약 조건

트럭 최대 CBM·중량 초과 금지
근로 시간·휴게 시간 준수
냉장/위험물/특수 화물 전용 트럭 사용
각 DO의 배송 가능 시간 윈도우(time window) 준수
Direct DO는 지정된 구간 수 이상 경유 금지(복잡도 제한)

엔진은 항상 “제약을 절대 어기지 않는 계획”을 먼저 만든 후, 그 안에서 비용·시간을 최적화한다.

39. 기본 Route Planning 파이프라인

DVRP 엔진의 1차 목표는 “수 초 내에 운영 가능한 계획”을 만드는 것이다.


1. Input 수집  →  2. 클러스터링  →  3. 초기 경로 생성
          ↓                     ↓
      5. 제약 검사   ←   4. 경로 개선(Local Search)
          ↓
      6. ETA 계산 + 캐시 반영

39.1 Step 1 — Input 수집

오늘 생성된 모든 DO
이미 운행 중인 트럭의 현재 위치/적재량(디지털 트윈)
트럭별 허용 근무 시간 잔여량
도로 거리/예상 소요 시간(캐시된 거리 메트릭)

39.2 Step 2 — 지리적 클러스터링

K-means 계열의 클러스터링 대신, 물류에서 더 단순한 “그리드 기반 혹은 고정 셀 기반” 클러스터링을 사용한다.


- 위도/경도를 일정 셀 크기로 나누고
- 셀 단위로 DO를 그룹핑
- 각 셀 그룹을 트럭 후보 그룹으로 매칭

복잡한 최적화 이전에, “같은 방향·같은 지역”끼리 묶는 구조다.

39.3 Step 3 — 초기 경로 생성 (Greedy Insertion)

각 클러스터 내에서 다음과 같은 순서로 초기 경로를 만든다.


1) 출발 허브(창고 또는 지정 기점) 설정
2) 가장 가까운 DO를 하나씩 경로에 삽입
3) CBM/중량이 한계에 가까워질 때까지 반복
4) 한계에 도달하면 새 루트 생성

이 단계까지는 “빠르게 큰 그림을 만드는 단계”이다.

39.4 Step 4 — Local Search 기반 경로 개선

초기 경로 위에서 2-Opt / 3-Opt와 유사한 로컬 서치(탐욕적 교환)를 수행한다.


- 두 구간의 순서를 바꿔본다
- 특정 DO를 다른 루트로 옮겨본다
- Direct DO를 다른 트럭에 재할당해본다
- 각 시나리오별 비용·시간을 비교하여
  더 나은 안으로 교체

여기서는 “전역 최적”이 아니라 제약 내부에서의 로컬 최적(Local Optimum)을 목표로 한다.

39.5 Step 5 — 제약 검사

모든 후보 경로는 다음 제약을 통과해야 한다.

근로 시간 초과 금지
트럭 허용 하중/CBM 초과 금지
시간 윈도우 준수
Direct DO의 경유 제한

제약 위반 경로는 즉시 폐기하거나, 강제 분할(루트 분리)로 회피한다.

39.6 Step 6 — ETA 계산 및 캐시 반영

최종 경로가 정해지면 각 DO에 대해 ETA를 계산하고 Redis / Firestore / Local 캐시에 동시에 반영한다.


eta = Σ(세그먼트별 주행시간 + 예상 상차/하차 시간)

이 ETA는 이후 AI 보정 모델에 의해 수정될 수 있다(38~40절 참조).

40. Direct DO 고급 처리 — 다구간 & 시간 제약 & 우선순위

Direct DO는 창고를 거치지 않기 때문에, 일반적인 “허브 경유형” 라우팅과 다르게 취급해야 한다.

40.1 Direct DO의 특징

출발지와 도착지가 모두 고객사(또는 협력사)
중간에 1~2개 노드를 경유하는 다구간(Multi-leg) 패턴 가능
시간 윈도우가 더 좁은 경우가 많음(납품 시간 지정)
타 DO보다 우선순위가 높은 경우가 많음

40.2 Direct DO 경로 구성

Direct DO는 일반 DO와 다른 경로 생성 규칙을 사용한다.


1) Direct DO만 별도의 큐로 분리
2) 납품 시간제약이 가장 강한 DO부터 처리
3) 기존 루트에 삽입 가능한지 시도
4) 불가능하면 Direct 전용 루트 생성

이때, 기존 루트에 삽입 시 “우선순위 승급”이 일어나면 그 루트 내 다른 DO의 ETA를 재계산하고, 특정 DO는 다른 트럭으로 이동시킬 수 있다.

40.3 Direct DO 우선순위 스코어


priority_score =
  w1 * (납품시간까지 남은 시간 역수) +
  w2 * (고객 중요도) +
  w3 * (운임 단가) +
  w4 * (계약 SLA 중요도)

priority_score가 높은 DO는 먼저 할당되고, 필요시 기존 루트 전체를 재구성하는 트리거가 된다.

41. AI 기반 ETA 보정 모델

기본 ETA는 거리 + 개략적인 속도 기반으로 계산된다. 그러나 실제 현장에서는 다음과 같은 변수들이 의미 있게 작용한다.

지역별 평균 실제 속도(도심/공단/항만)
시간대별 정체 패턴(출근/퇴근/점심)
날씨/우천/공사 등 외부 요인
운전기사 개인 운전 패턴(평균 속도, 정차 빈도)
상·하차 지연 패턴(고객사별)

41.1 ETA 보정 파이프라인


기본 ETA 계산
   ↓
디지털 트윈 데이터 + 이력 데이터 수집
   ↓
AI 보정 모델 (LLM + 회귀/트리 모델)
   ↓
조정된 ETA → 캐시 반영

여기서 LLM은 “지역적 특성과 패턴 설명”을 이해하는 역할만 하고, 최종 수치는 회귀·트리 모델(CatBoost, LightGBM 등)이 계산한다.

41.2 ETA 보정 예시


- 기본 ETA: 45분
- 지역 패턴: 퇴근시간대 평균 +18분
- 운전기사 패턴: 평균 -3분
- 고객사 상차 지연 평균: +6분
→ 최종 ETA ≈ 45 + 18 - 3 + 6 = 66분

이 최종 ETA는 Firestore에 푸시되어 관리·고객 뷰 모두에서 동일하게 사용된다.

42. 재배차(Re-dispatch) 및 실패 처리 로직

DVRP 엔진은 다음과 같은 경우 재배차를 수행해야 한다.

트럭 고장 또는 사고
운전기사 급작스러운 업무 중단
특정 DO 강제 취소·변경
ETA가 계약 SLA를 명백히 초과할 것으로 예상될 때

42.1 재배차 처리 순서


1) 문제 트럭/기사의 DO 목록 추출
2) 배송 완료된 DO 제외
3) 남은 DO를 "긴급 DO 큐"로 이동
4) 사용 가능한 다른 트럭 후보 검색
5) DVRP 엔진을 "제약 최소 세트" 모드로 다시 실행
6) 새로운 배차 결과 확정
7) 모바일 앱/웹에 재배차 정보 푸시

“제약 최소 세트 모드”는 비용 최적화보다 SLA 위반 방지에 더 높은 가중치를 둔 모드다.

42.2 재배차 실패 시 처리

어떠한 경우에도 트럭이 부족하거나 제약 상 물리적으로 불가능한 경우가 발생할 수 있다.

외주 트럭 배차 제안
납품 시간 재조정(고객사와 재협상 필요 경고)
DO 분할 제안(분할 배송)

이 정보는 MQ → Notification Service → 관리자 알림으로 전달된다.

43. 비용 모델과 DVRP 통합

DVRP 엔진은 단순히 “빠르고 가까운 경로”만 찾는 것이 아니라, 비용 모델과 완전히 통합되어 있다.

43.1 비용 요소

거리 기반 비용 (km 단가)
시간 기반 비용 (운전기사 인건비)
차종별 비용 (냉장/위험물 전용)
도로/통행료 등 추가 비용
외주 트럭 운임

43.2 DVRP에서 사용하는 비용 함수


cost(route) =
  distance_cost(route) +
  time_cost(route) +
  special_truck_premium +
  toll_road_cost +
  external_carrier_cost

엔진은 각 후보 루트마다 cost(route)를 계산하고, 제약을 만족하는 루트 중 비용 최저를 선택한다.

44. MQ · 캐시 · 모바일까지 이어지는 전체 플로우

지금까지 설명한 DVRP 관련 로직은 아래와 같은 흐름으로 하나의 체인을 이룬다.


1) ASN/OSN/DO 생성  →  DB/CDC 이벤트
2) LavinMQ로 DO 이벤트 발행
3) DVRP 엔진 소비 → 경로/배차/ETA 계산
4) 결과 Redis/Firestore/IndexedDB에 반영
5) 관리자 웹/운전기사 앱에 실시간 반영
6) 트럭/DO 상태 변화 시 다시 MQ로 이벤트 발행
7) 필요시 재배차/경로 재계산

이 구조 덕분에, DVRP 엔진은 고립된 배차 모듈이 아니라 플랫폼 전체와 긴밀히 연결된 “실시간 최적화 레이어”로 동작한다.

45. 정리 — REINDEERS DVRP 엔진이 제공하는 것

Pickup/Delivery/Direct DO를 하나의 모델로 통일해 처리
지리적 클러스터링 + Greedy + Local Search 기반 실시간 경로 생성
근로·적재·시간 윈도우·화물 제약을 항상 만족하는 안전한 계획
Direct DO에 대한 별도의 고급 처리(우선순위 / 다구간)
AI 기반 ETA 보정 및 재배차 로직
비용 모델과 통합된 DVRP 최적화
MQ·캐시·모바일까지 연결되는 실시간 동작 구조

REINDEERS의 DVRP 엔진은 “이론적으로 이상적인 해답”보다, 지금 당장 물류 현장에서 실제로 사용할 수 있는 실용적인 해답을 안정적으로 제공하는 것을 목표로 설계·구현되고 있다.

Blog of Reindeers

Search This Blog