バス路線網構成のためのモデル化とアルゴリズム
川端 康之 (9551025)
本発表では, 数理計画問題の実際への応用例として,
乗客を1つの目的地に運ぶルート(バス路線)を構成する
問題について考察する.
ルート構成においては, さまざまな状況
が考えられ, それらすべてを考慮したモデル構築は非常に複雑
となる. そこで本論文では, ルートを構成する手順を3段階に分け,
全体として効率的な乗客の輸送を行なう
ルートを構成するためのモデルを提案する.
まず, 第1段階では, 適当な条件を満たす
ルートの候補を列挙する.
次に第2段階で,
列挙した候補の中から, 効率的な輸送を行なうルートの組合せを
求める.
最後に第3段階で, 得られたルートの組合せに対し必要な
バスの便数を求める.
とくに第2段階の問題はp-メディアン
問題に帰着できるので, よく知られている解法の
ひとつである入れ子双対法を適用する.
また, 本発表では, 学園前地域の実際のバス路線網のデータについて
計算機実験を行い, 提案したモデルの妥当性を検証する.