NCO4CVRP：容量制約付き車両経路問題に対するニューラル組合せ最適化

arXiv cs.LG / 2026/4/21

📰 ニュースDeveloper Stack & InfrastructureSignals & Early TrendsModels & Research

共有:

要点

この論文は、容量制約付き車両経路問題（CVRP）に対するニューラル組合せ最適化（NCO）の推論手法を改善し、解の質と汎化性能の向上を目指します。
LEHDモデルのRandom Re-Construct（RRC）を、確率的受理により局所最適から脱出して探索の多様性を高めるSimulated Annealing（SA）で改良します。
POMOにBeam Searchを組み込み、有望な複数解を体系的に探索しつつ、多様性を保つ形で拡張します。
Softmax Sampling、Greedy、Gumbel-Softmax、Epsilon-Greedyといった複数の推論戦略を比較し、反転や回転によるインスタンス拡張で汎化を高める効果も検証します。
CVRPベンチマークでの実験では、SAベースのRRCとBeam Searchが一貫して最適性ギャップを縮小し、NCOの実課題への適用可能性が高まることを示します。

Abstract

ニューラル組合せ最適化（Neural Combinatorial Optimization: NCO）は、深層学習ベースのモデルを統合することで組合せ最適化問題を解くための強力な枠組みとして注目を集めています。本研究は、既存の推論手法を改善し、解の品質と汎化性能を向上させることに焦点を当てます。具体的には、Light Encoder Heavy Decoder（LEHD）モデルの Random Re-Construct（RRC）手法を Simulated Annealing（SA）を組み込むことで改良します。従来のRRCが劣った部分を貪欲に置き換えるのに対し、提案するSAベースの改良では確率的な受容メカニズムを導入し、モデルが局所最適から脱出して、より多様な解空間を探索できるようにします。さらに、Policy Optimization with Multiple Optima（POMO）手法を改良し、Beam Search を統合することで、探索空間の多様性を維持しながら複数の有望な解を体系的に探索できるようにします。また、Softmax Sampling、Greedy、Gumbel-Softmax、Epsilon-Greedy を含むさまざまな推論戦略を調査し、それらが解の品質に与える影響を分析します。加えて、水平・垂直の反転や回転に基づく拡張などのインスタンス拡張手法を検討し、異なる CVRP（Capacitated Vehicle Routing Problem）インスタンス間でのモデル汎化性能を向上させます。広範な実験の結果、これらの改良は、さまざまな CVRP ベンチマークにおいて最適性ギャップを大幅に低減し、Beam Search と SA ベースの RRC が一貫して優れた性能を示すことが確認されました。推論手法を洗練し、強化された探索戦略を活用することで、本研究は実世界の組合せ最適化タスクにおける NCO モデルのより広範な適用可能性に貢献します。