時間指定のあるビークル・ルーティング問題

概要

論文の詳細を見る
この論文では、中央デポをベースとするキャパシティ付きビークル(車輌)を、できるだけ少ない台数で、時間指定のある需要群に対応させようというルーティング問題を考える。まず、この時間拘束付きビークル・ルーティング問題の定式化をおこない、これを解くヒューリスティック・アルゴリズムについて考察する。この問題にキャパシティ拘束が無かったなら、輸送計画問題となり、シンプレックス法を利用して解くことができる。しかし、キャパシティ拘束がつけられた場合、ビークルは何度もデポに戻り複数のツアーを扱うことになる。つまり、問題には、ツアーの作成とビークルに対するツアー割付けの2つの要素が存在し、輸送計画問題を二重に含む構造となる。この構造を利用したヒューリスティック・アルゴリズムを提案し、数値実験においてセービング法等を応用した6つのアルゴリズムと比較する。その結果、提案したアルゴリズムが有効であることがわかった。また、デポの位置とビークルのキャパシティの大小が、このヒューリスティック・アルゴリズムの有効性に大きく影響することがわかった。
社団法人日本オペレーションズ・リサーチ学会の論文