氏名 : 小島 義弘 (280967144)
所属 : 張研
題目 : ある在庫管理問題に対する近似解法の改良
概要 :
本研究が対象とするのは企業の現場に現れたある在庫管理問題である．
この問題はN日の間，
K箇所の倉庫に蓄えられている原料が無くならないように
運ばれてくる原料の搬入先を決定する組み合わせ最適化問題であり，
目的関数を最小化する最小化問題の形に帰着されている．
企業の現場では実用的な時間（汎用PCを用いて数分程度）
で解を得ることができる解法が強く求められている．
この問題に対して，
各種最適化問題の最適解を求める汎用アルゴリズムである分枝限定法を，
全期間ではなく短い部分期間に対して複数回適用する
という近似解法を用いることで計算時間に対する要請を満たすことに成功している．
しかし，計算時間が問題やパラメータに大きく依存するなど安定性に欠ける
という問題点があった．
そこで本研究では，この解法に改良を加えることにより，更なる高速化を目指す．
具体的には，
部分期間に対する分枝限定法において，数ステップ程度の先読みを行い，
その際の部分目的関数の値が小さい枝を優先的に探索する．
これにより，よい解が早く見つかることが期待される．
本発表ではこのアイデアに基づく数値実験の結果について報告し，
改良の効果および数値実験の結果明らかになった問題点と
その改良についても考察を行う．
目次に戻る