Neural Embedded Mixed-Integer Optimization for Location-Routing Problems

연구 초점

용량 제약이 있는 입지-경로 문제는 세 가지를 한꺼번에 묻습니다. 어느 거점을 열지, 각 거점이 어느 고객을 맡을지, 어떤 차량 경로로 배송할지입니다. 엄밀해법은 해의 품질을 보장하지만 고객 수백 명이나 후보 시설 열 곳 정도를 넘어서는 규모로는 확장되지 않습니다. 휴리스틱은 그런 보장 없이 더 큰 문제를 다루지만 휴리스틱이 입지와 배정 결정을 맡는 구조에서는 그 수준에 새로운 응용별 제약이 생길 때마다 탐색 연산자를 다시 설계해야 합니다.

접근 방법

NEO-LRP는 문제를 두 수준으로 나눕니다. 신경망은 단일 거점 차량 경로 문제의 비용을 예측하도록 한 번만 학습합니다. 학습에는 입지-경로 평가 문제와 겹치지 않도록 따로 생성한 경로 문제를 씁니다. 예측값은 한 거점에 배정된 고객의 순서에 따라 달라지지 않으며 신경망 구조가 이 성질을 그대로 따릅니다.

학습된 모델을 이진 변수와 선형 제약으로 혼합정수계획에 넣습니다. 표준 솔버가 경로를 직접 만드는 대신 신경망의 추정값을 써서 어느 거점을 열고 고객을 어떻게 배정할지 정하므로, 맞춤 제약을 일반 제약으로 추가할 수 있습니다. 이 계획 자체는 차량 경로를 만들지 않습니다. 경로는 그 뒤에 경로 솔버가 열린 거점마다 만듭니다.

결과

저자들은 네 가지 벤치마크 세트에서 해의 품질이 알려진 최선의 해와 견줄 만하고 계산 속도는 최신 휴리스틱보다 2배에서 120배 빠르다고 보고합니다. 약 여섯 시간의 일회성 학습을 마친 뒤에는 문제 하나를 푸는 데 1초 미만에서 5분 미만이 걸립니다. 고객 600명, 거점 30곳인 가장 큰 문제에서는 중앙값 격차 1%를 보고합니다. 대표적인 휴리스틱은 같은 문제에 네 시간 넘게 걸립니다.

일부 세트에서는 전용 휴리스틱이 알려진 최선의 해에 더 가깝습니다. 예를 들어 Prins 벤치마크에서 보고된 중앙값 격차는 NEO-LRP가 1.62%, 가장 강한 비교 대상이 0.11%이고, 풀이 시간 중앙값은 각각 2.2초와 11.3초입니다.

게재 정보

NeurIPS 2025 DiffCoALG 워크숍

Kaleem, W., Lee, D., Kwon, C., and Subramanyam, A.