バス路線網構成のためのモデル化とアルゴリズム

川端 康之 (9551025)


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