氏名 : 棚橋 優 (281267189)
所属 : 張研
題目 : 配送計画問題に対するデータベース付きメタ戦略
概要 :
本発表では，配送計画問題におけるアルゴリズムの工夫について述べる．
・取り扱う問題
配送計画問題とは，運搬車を用いてある出発点から複数の顧客へモノを配送する際，
どの運搬車がどの顧客をどういう順番で回れば，最もコストを抑えることができるか
を求める問題である．
・研究背景
従来，配送計画問題にはメタ戦略と呼ばれる考えに基づいた解法が用いられている．
メタ戦略とは，厳密な最適解を求めることが難しい最適化問題に対して，多少時間を
かけることでより精度の高い近似解を求めようとする取り組みのことである．一般的
にメタ戦略は，解の精度と計算時間は比例関係にあり，良い解を求めようとするほど
時間がかかる傾向にある．
・提案法
アルゴリズムに工夫を施す目的は，解の精度を保ちながら，近似解を求める計算にか
かる時間を削減することである． 特に本研究で扱うアルゴリズムは，随所に同様の
計算をしている箇所がある．そこで，それら局所における計算結果の情報をうまく活
用しながら，近似解を導き出す新たな手法を提案する．これにより計算効率を向上さ
せ，アルゴリズム全体における計算時間の削減を果たすことを期待した．
目次に戻る