효율적인 배차 전략

(참고) 물류 서비스 향상을 위한 배차계획 시스템의 설계 및 구현
https://koreascience.kr/article/JAKO200634741432791.pdf

선분할-후경로 법(Cluster First - Route Second)
선경로-후분할 법(Route First - Cluster Second)
절약/삽입법 (Saving/Insertion)
개선/교환법 (Improvement/Exchange)
수리계획법 (Mathematical Programming-based)
대화식 최적화법 (Interactive Optimization)
정확한 해법
---

3단계 해법

첫번째 단계는 선택 기준 설정 단계로 제약조건이 있는 배차를 선 배차
미리 배차 가능한 물량을 선 배차한 후 미배차 물량을 처리
선택 기준(주문량, 배송요구시간, 하역난이도, 지정차량, 고객중요도)
seed point

두번째 선택된 seed point 중심으로 그룹핑 조건 처리(기준과의 거리, 배송차량의 적재 용량, 권역에 따른 물량 분포)에 따라 주변 거래처의 주문물량을 배송차량의 적재용량까지 더해 가면서 선정된 배송차량의 거래처를 확정
세번째 배송 차량의 거래처 확정되면 ,
거리, 시간 및 비용조건에 따라 발견적 외판원문제 알고리즘을 통하여 최적 배송경로를 구하거나,
거래처의 인접성 개념의 우편번호 중심좌표를 도입하여 배차리스트를 만든다.