講演情報
[1Yin-A-41]利益最大化集配選択問題に対する厳密解法：ブール符号化と遅延節生成の統合
〇査 澳龍1、常 穹2、越村 三幸3、井村 直人4 (1. 和歌山大学、2. 東京科学大学、3. 九州大学、4. 東京大学)
キーワード：
組合せ最適化、集荷配送問題、最大充足可能性問題、遅延節生成、ブール符号化
利益最大化集配選択問題（PPDSP）は，複雑な順序制約を含むため，従来の混合整数計画法（MIP）では線形緩和が機能しにくく，探索空間の削減が困難であった．そこで本研究では，最大充足可能性問題（MaxSAT）に基づく厳密解法を提案する．順序制約には順序符号化を適用してSATの単位伝播を活用し，容量制約には遅延節生成を導入して静的符号化による変数の爆発を回避するハイブリッド手法である．実道路網を用いた評価実験の結果，提案手法は特に制約が厳しいシナリオにおいて，商用MIPソルバーよりも高速に最適解を導出できることを確認した．本手法は，論理制約が支配的な配送計画問題に対する新たな解決策となる．