차량 경로 문제(VRP)를 위한 그래프 편집 거리(GED) 정식화: 이론 및 분석

본 연구에서는 차량 경로 문제 (Vehicle Routing Problem, VRP)를 그래프 편집 거리 (Graph Edit Distance, GED) 최대화 문제로 재정식화할 수 있음을 보여줍니다. 단순한 에지 삭제 비용 모델 (edge-deletion cost model) 하에서, 총 경로 비용을 최소화하는 것은 완전 인스턴스 그래프 (complete instance graph)에서 삭제된 에지들의 총 가중치를 최대화하는 것과 동일합니다. 이러한 정식화는 VRP를 에지 수준 (edge level)에서 모델링하며, 여기서 솔루션은 경로 순서가 아닌 선택된 에지들에 의해 정의됩니다. 이를 통해 기존의 정식화 방식으로는 어려웠던 구조적 분석, 즉 솔루션 품질의 에지별 귀속 (per-edge attribution), 최적성 격차 (optimality gap)의 분해, 솔루션 희소성 (solution sparsity)의 특성화, 그리고 탐욕적 구성 (greedy construction)으로 도달하기 어려운 에지의 식별 등이 가능해집니다. 이론적으로, 우리는 Clarke-Wright 세이빙 (savings)이 병합당 GED 증가량과 같음을 보여주는 병합-분해 정리 (merge-decomposition theorem)와, GED 근사 비율을 VRP 비용 경계로 변환하는 근사-전이 정리 (approximation-transfer theorem)를 확립합니다. 이 재정식화를 사용하여, 우리는 최적 솔루션이 알려진 90개의 CVRP 벤치마크 인스턴스를 분석합니다. 분석 결과, 최적 경로 그래프는 사용 가능한 에지의 5.5%만을 사용하며, 최적 에지의 약 3.0%는 반복적인 재시작(restarts) 하의 Clarke-Wright 휴리스틱에 의해 일관되게 발견되지 않는다는 것을 발견했습니다. 또한 비용 격차는 놓친 최적 에지들과 그에 상응하는 총 가중치를 가진 대체된 비최적 에지들로 분해됩니다. 에지 가산 목적 함수 (edge-additive objective)는 향후 에지 예측을 위한 그래프 신경망 (Graph Neural Network, GNN) 접근 방식에 자연스러운 에지별 감독 신호 (per-edge supervision signal)를 제공하며, 이는 우리가 후속 연구로 남겨둔 그래프 신경망 접근 방식과의 잠재적 연결성을 시사합니다.