無人搬送車システムの最適化における計算複雑さの解析

点击翻译按钮获取中文摘要

無人搬送車の運行計画問題を組合せ最適化問題として定式化するとき,これらは,どのような走行ネットワーク上での移動を考えるのか,仕事の時間的制約として何を考慮しなければならないのか,などによっていくつかのクラスに分類される.ここでは,現実によくみられる木状経路と直線状経路を対象として,いくつかのクラスを計算複雑さの立場から検討した.なお,直線状経路は木状経路の特殊な場合である.まず,準備時間制約のある木状経路の場合において,周回時間最小化問題は一般にNP困難であるが,深さ優先ルーティング近似解法に対して,過去に得ていた2倍というものよりもさらに精密な最悪性能比を示すことが出来た.また,納期制約のある木状経路の場合において,最大納期ずれ最小化問題はNP困難であり,これより納期遅れ仕事数最小化問題や納期遅れ和最小化問題もNP困難であると言える.より単純な走行ネットワークである直線上経路においては,正の処理時間が要求される場合,周回時間最小化問題がNP困難であることは知られていたが,最大納期ずれ最小化問題もNP困難であることが分かった.木状経路における平均完了時間最小化問題に対しては,計算機を利用して,遺伝的アルゴリズムにより近似解法の構築と分枝限定法で用いる下界値計算法を検討した.その結果,このような巡回修理人型の問題の難しさは,時間的制約よりもむしろ目的関数の累積性に起因していると推測され,より一層の解析が必要である.なお,遺伝的アルゴリズムは,より汎用性の高い配送経路問題に対してもその適用を検討した.