시간창 차량경로문제 (VRP with Time Windows)
한 줄 정의: 고객마다 정해진 방문 허용 시간대 안에 도착해야 하는 조건이 붙은 차량경로문제입니다.
쉽게 풀면
택배 차량이 여러 고객을 도는 경로를 짤 때, 어떤 가게는 오전 9~11시에만 물건을 받을 수 있다고 해봅시다. 이런 '시간창'을 모두 지키면서 차량 수와 총 이동거리를 최소로 하는 문제가 시간창 차량경로문제입니다.
왜 중요한가
실제 배송·수거 업무에는 거의 항상 시간 약속이 있기 때문에 기본 VRP보다 현실에 가까운 표준 모형으로 널리 연구됩니다. 새 휴리스틱의 성능을 비교하는 대표 시험대이기도 합니다.
논문에서는 이렇게 쓰입니다
"제안한 대규모 이웃탐색 알고리즘은 Solomon 벤치마크에서 기존 최고해 일부를 갱신하였다."
표준 문제 세트로 알고리즘 성능을 비교한 문장입니다.
"연성 시간창을 적용해 지연 도착에 벌점을 부과하였다."
시간창 위반을 허용하되 비용으로 반영했다는 뜻입니다.
조금 더 깊게 보면
경성(hard) 시간창은 늦게 도착하는 것을 허용하지 않고, 일찍 도착하면 기다려야 합니다. 연성(soft) 시간창은 위반을 허용하되 벌점 비용을 매깁니다. 문제는 NP-난해하여 대규모 문제에는 Solomon(1987)의 삽입 휴리스틱이나 타부탐색 같은 메타휴리스틱이 쓰이고, 정확해법으로는 열생성과 자원제약 최단경로 라벨링 알고리즘을 결합한 분지-가격 방법이 대표적입니다. Solomon이 만든 100고객 벤치마크 세트가 표준 비교 기준으로 쓰입니다.
주의할 점
차량경로문제(VRP)에 방문 허용 시간창 제약이 추가된 변형이므로 기본 개념은 VRP 항목을 먼저 보세요. 논문마다 목적함수(차량 수 우선인지 거리 우선인지)가 달라 결과 수치를 직접 비교할 때 주의해야 합니다.