전이 가능한 지역 정책과 앙상블을 통해 차량 경로 문제를 위한 일반화 가능한 신경 해법으로 나아가기

기계 학습은 NP-하드 조합 최적화 문제를 해결하는 데 적응되었습니다. 널리 알려진 방법 중 하나는 깊은 신경망을 통해 솔루션을 구성하는 방법으로, 높은 효율성과 전문가 지식에 대한 요구가 적기 때문에 점점 더 많은 주목을 받고 있습니다. 그러나 차량 경로 문제(VRP)를 위한 많은 신경 구축 방법은 지정된 노드 분포와 제한된 스케일을 가진 합성 문제 인스턴스에 초점을 맞추고 있어, 복잡하고 알려지지 않은 노드 분포와 큰 스케일이 수반되는 실제 문제에서는 성능이 저조합니다. 신경 VRP 해법을 더 실용적으로 만들기 위해, 지역 전이 가능한 위상적 특성에서 학습하는 보조 정책, 즉 지역 정책을 설계하고, 이를 VRP 인스턴스의 글로벌 정보에서 학습하는 전형적인 구축 정책과 결합하여 앙상블 정책을 형성합니다. 공동 훈련을 통해 집계된 정책은 협력적이고 보완적으로 작동하여 일반화를 개선합니다. 여행 판매원 문제와 용량 제한 VRP에 대한 두 개의 잘 알려진 벤치마크인 TSPLIB와 CVRPLIB에서의 실험 결과는 앙상블 정책이 교차 분포 및 교차 스케일 일반화 성능을 크게 개선하며, 수천 개의 노드가 포함된 실제 문제에서도 잘 수행됨을 보여줍니다.