column generation(CG)은 대규모 최적화에서 널리 쓰이지만, 이중해가 흔들리면 수렴이 크게 느려진다. 이번 arXiv 프리프린트는 차량경로 문제에서 그 불안정을 줄이기 위해 learned pairwise deep dual-optimal inequalities, 즉 L-PDDOIs를 제안한다. 핵심은 듀얼 변수 사이의 순서를 학습해 master problem에 반영하고, 상충·중복 관계는 그래프 기반 후처리로 걸러내는 방식이다. 기존 deep dual-optimal inequalities는 문제별 교환 논증에 기대는 경우가 많아, 용량 제한이나 시간창 같은 자원 제약이 붙은 라우팅 문제에 적용하기 까다로웠다. 이 프레임워크는 최적 듀얼 해를 여러 번 샘플링한 뒤, 충분히 큰 공통 부분집합에서 동시에 성립하는 쌍wise 순서관계를 라벨로 삼는다. 이어 분류기가 각 후보 관계에 점수를 매기고, 배포 전 그래프 후처리가 후보 집합을 압축한다.
연구진은 또 복구 절차를 넣어, 학습된 부등식을 선택적으로 완화하면서 baseline CG bound가 회복됐는지 인증할 수 있게 했다. 원문에 따르면 직접 배포한 L-PDDOIs는 capacitated vehicle routing problem(CVRP)과 vehicle routing problem with time windows(VRPTW)의 주요 테스트 세트에서 root CG time의 기하평균을 각각 89.7%, 93.9% 줄였고, 평균 bound 손실은 각각 1.3%, 0.5%였다. 복구 절차를 쓰면 시간 단축은 각각 54.8%, 83.1%로 남고, CG bound 손실은 없었다.
실험 구성도 비교적 분명하다. CVRP 쪽에는 XML500-Learn 500개 인스턴스로 학습·모델선택을 하고 XML500-Test 200개로 주 평가를 진행했으며, X100 100개는 전이 평가에 사용했다. VRPTW는 S-GH200-Learn 300개, S-GH200-Test 60개, 공식 Gehring–Homberger 200·400 고객 세트를 각각 30개씩 전이 및 크기 전이에 썼다. 주요 평가에서는 CVRP의 X100에서 default 40.7초가 L-PDDOI 5.9초로 줄어 85.6% 감소했고, 평균 bound 손실은 1.1%였다.
후처리와 복구의 역할도 분리해 확인했다. XML500-Test ablation에서는 Raw Prediction이 119,794개 후보에서 10.1초, bound 손실 9.5%를 보였고, Repair Only는 18.0초와 1.3% 손실로 개선했다. Full은 2,045개 후보로 줄여 12.3초, 1.3% 손실을 기록했다. VRPTW S-GH200-Test에서는 Full+Rec이 1,417개 후보를 바탕으로 16.1초, 평균 5.3회 복구 라운드를 보였다. GH400-Benchmark에선 직접 배포의 시간 감소가 97.7%였지만 평균 bound 손실이 6.0%로 커졌고, 30개 중 9개만 BKS gap 5.0% 미만이었다.
| 구분 | 수치 | 의미 | source_locator |
|---|---|---|---|
| CVRP main test | direct deployment: root CG time 89.7% 감소; mean bound loss 1.3%; recovery: 54.8% 감소; no loss in CG bound | 주요 테스트 세트 성능 | abstract; p.1; p.4 |
| VRPTW main test | direct deployment: root CG time 93.9% 감소; mean bound loss 0.5%; recovery: 83.1% 감소; no loss in CG bound | 주요 테스트 세트 성능 | abstract; p.1 |
| CVRP X100 transfer evaluation | Default 40.7 s -> L-PDDOI 5.9 s; 85.6% reduction; mean bound loss 1.1%; mean BKS gap 2.4% | 전이 평가 결과 | p.21 Table 6 |
| VRPTW GH400-Benchmark | direct deployment: 97.7% reduction; mean bound loss 6.0%; 9/30 instances below 5.0% BKS gap | 크기 전이 평가 결과 | p.23 |
자료: STORIUM 정리
이 논문은 INFORMS Journal on Computing 제출 상태의 arXiv v1 프리프린트로, 동료검토 전 결과다. 제시된 수치는 원문에 적힌 CVRP·VRPTW 테스트 및 전이 평가 범위에서만 해석해야 하며, 다른 차량경로 유형이나 더 넓은 분포에 대한 일반화는 추가 검증이 필요하다.
저작권자 © STORIUM 무단전재 및 재배포 금지
