경로 문제 해결을 위한 신경망 솔버의 효율적인 제약 조건 처리 방안 연구

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

신경망 솔버는 간단한 경로 문제 해결에서 뛰어난 성능을 보여주며, 특히 계산 효율성 측면에서 강점을 나타냅니다. 그러나 복잡한 제약 조건 하에서의 성능은 아직 미흡하며, 기존의 제약 조건 처리 방식인 가능성 마스킹 또는 암묵적 가능성 인지 방식은 엄격한 제약 조건에 대해 비효율적이거나 적용 불가능할 수 있습니다. 본 논문에서는 명시적인 학습 기반 가능성 개선을 기반으로 하는 신경망 경로 솔버를 위한 첫 번째 일반적이고 효율적인 제약 조건 처리 프레임워크인 Construct-and-Refine (CaR)을 제시합니다. 기존의 구성-탐색 하이브리드 방식이 최적성 간극을 줄이기 위해 많은 노력을 기울이지만, 여전히 엄격한 제약 조건에 어려움을 겪는 것과 달리, CaR은 효율적인 제약 조건 처리를 위해, 가벼운 개선 과정을 위한 다양하고 고품질의 해를 생성하도록 구성 모듈을 안내하는 공동 학습 프레임워크를 설계합니다. 예를 들어, 기존 연구에서 5천 단계가 필요한 개선 과정을 10단계로 줄일 수 있습니다. 또한, CaR은 구성-개선-공유 표현 방식을 처음으로 도입하여, 특히 복잡한 제약 조건 시나리오에서 인코더를 통합함으로써 패러다임 간의 잠재적인 지식 공유를 가능하게 합니다. CaR의 광범위한 적용 가능성을 보여주기 위해, 일반적인 엄격한 경로 제약 조건에 대한 실험을 수행했습니다. 결과는 CaR이 기존의 고전적 및 신경망 기반 최첨단 솔버보다 우수한 가능성, 해의 품질 및 효율성을 달성함을 보여줍니다.

Neural solvers have achieved impressive progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint-handling schemes via feasibility masking or implicit feasibility awareness can be inefficient or inapplicable for hard constraints. In this paper, we present Construct-and-Refine (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning-based feasibility refinement. Unlike prior construction-search hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework that guides the construction module to generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction-improvement-shared representation, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints to showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers.