[1Yin-A] Poster 1

[1Yin-A-41] Exact Approaches for the Profit-Maximizing Pickup and Delivery Selection Problem: Boolean Encodings and Lazy Clause Generation

〇Aolong Zha¹, Qiong Chang², Miyuki Koshimura³, Naoto Imura⁴ (1. Wakayama University, 2. Institute of Science Tokyo, 3. Kyushu University, 4. The University of Tokyo)

Keywords:

Combinatorial Optimization,Pickup and Delivery Problem,Maximum Satisfiability,Lazy Clause Generation,Boolean Encoding

利益最大化集配選択問題（PPDSP）は，複雑な順序制約を含むため，従来の混合整数計画法（MIP）では線形緩和が機能しにくく，探索空間の削減が困難であった．そこで本研究では，最大充足可能性問題（MaxSAT）に基づく厳密解法を提案する．順序制約には順序符号化を適用してSATの単位伝播を活用し，容量制約には遅延節生成を導入して静的符号化による変数の爆発を回避するハイブリッド手法である．実道路網を用いた評価実験の結果，提案手法は特に制約が厳しいシナリオにおいて，商用MIPソルバーよりも高速に最適解を導出できることを確認した．本手法は，論理制約が支配的な配送計画問題に対する新たな解決策となる．