Design and development of a general-purpose solver for a variety of problem of asking assignment and ordering

本年度の研究実績として，(1) 配置が2列になる長方形ストリップパッキング問題，(2) 最遅到着時刻を考慮するPrize-collecting バスルーティング問題を挙げる．(1)長方形ストリップパッキング問題は，与えられた長方形を幅が固定された長方形の容器(ストリップと呼ぶ)に重なりなく詰め込むとき，ストリップの高さをできるだけ小さくする問題である.本研究では，長方形ストリップパッキング問題 において，与えられた長方形集合の任意の3つの長方形の幅の合計がストリップの幅より大きいことを考える.この問題を配置が2列になる長方形ストリップパッキング問題と呼ぶ. この問題に対して，まず幅方向に3つ以上の長方形を配置することができない場合の配置の条件と最適性の条件を示し，この問題の複雑さを分析した.また，最適性の条件等を利用した整数計画問題としての定式化を提案した.計算実験では，ランダムに生成した問題例に対して，提案する定式化をMIPソルバgurobiで求解しその効果を示した．(2)通勤バスルーティング問題に対する反復局所探索法を提案した．バス停の候補とルートを同時に探索できる近傍操作set-del/1-insを提案した．また，set-del/1-ins近傍により得られた局所最適解をVRP-OPT*という近傍操作に基づく方法で解を改善した．解に多様性を持たせるため，重みを適応的に変化できるペナルティ付き評価関数も設計した．計算実験により近傍操作の有効性を確認した．また，1000人の社員を含む大規模な問題例に対して，3600秒で良質の解を求めた．

本年度の研究実績として，(1) 配置が2列になる長方形ストリップパッキング問題，(2) 最遅到着時刻を考慮するPrize-collecting バスルーティング問題を挙げる．(1)長方形ストリップパッキング問題は，与えられた長方形を幅が固定された長方形の容器(ストリップと呼ぶ)に重なりなく詰め込むとき，ストリップの高さをできるだけ小さくする問題である.本研究では，長方形ストリップパッキング問題 において，与えられた長方形集合の任意の3つの長方形の幅の合計がストリップの幅より大きいことを考える.この問題を配置が2列になる長方形ストリップパッキング問題と呼ぶ. この問題に対して，まず幅方向に3つ以上の長方形を配置することができない場合の配置の条件と最適性の条件を示し，この問題の複雑さを分析した.また，最適性の条件等を利用した整数計画問題としての定式化を提案した.計算実験では，ランダムに生成した問題例に対して，提案する定式化をMIPソルバgurobiで求解しその効果を示した．(2)通勤バスルーティング問題に対する反復局所探索法を提案した．バス停の候補とルートを同時に探索できる近傍操作set-del/1-insを提案した．また，set-del/1-ins近傍により得られた局所最適解をVRP-OPT*という近傍操作に基づく方法で解を改善した．解に多様性を持たせるため，重みを適応的に変化できるペナルティ付き評価関数も設計した．計算実験により近傍操作の有効性を確認した．また，1000人の社員を含む大規模な問題例に対して，3600秒で良質の解を求めた．