エレベータ運行計画問題に対する動的計画法の一構成と状態遷移モデルの縮約による効率化

摘要

本論文では，中規模なESに対して現実的な状況下で最適なかご運行計画を立てるための枠組みの構築を目標とした研究が示される．その目標に向けた一歩として，計画期間における客の移動パターンが既知かつ一定であるという前提下で定式化されたESの状態遷移確率，およびエレベータ運行計画問題に対する動的計画法（以降，DP）の一構成，ならびに小規模なESに対する計算例が示される．状態遷移確率の定式化は，ESの挙動を確率的とする要因の想定およびその生起確率の定式化に基づいている．DPの計算式から，DPの計算時間がそのような要因の数に強く依存することが明示される．続いて，それらの要因のうち生起確率の低いものを考慮しない（“状態遷移モデルの縮約”と呼ぶ）ことで，計算時間を短くしつつ，最適なかご運行計画ルールにあまり劣らないルールを計算可能であることが示される．本論文の構成は次のとおりである．まず2章でエレベータ運行計画問題を概観し，本論文における目的関数および決定変数を示す．3章でESの離散モデルを構築し，これに基づいて4章で状態遷移確率を定式化する．5章では対象とするエレベータ運行計画問題に対するDPの一構成を述べる．つぎに，縮約された状態遷移モデル上でのDPを，これにより求められるコスト関数がもつ特徴の1つと併せて述べる．6章で，これら2種類のDPの小規模な2つの問題に対する適用結果を報告する．最後に7章で，結論と今後の課題を述べる．