環境変化に適応可能なネットワーク修正に基づくバス路線網最適化

摘要

2011年3月に発生した東日本大震災以降，大規模な災害が発生した場合における迅速な帰宅困難者の解消が重要視されている．そこで，一度に多数の人間を輸送可能であり，かつ道路の状況に応じて路線を柔軟に変更できるバスを用いた対策に注目が集まっている．災害時におけるバスの運行では，大規模な渋滞や瓦礫の崩落による道路の寸断が頻繁に発生するため，道路状況に応じて運行コストを最小化するだけではなく，平時に運行している路線からの修正量を抑える必要がある．これらの背景から，本研究では災害時の道路寸断に適用可能なバス路線修正手法として，(1) 路線網の輸送コスト（利用者の移動時間+ バス台数） と(2) 修正前後における利用者の移動経路の変化量との2 つの評価尺度を同時に考慮した手法を提案し，その有効性の検証を目的とする．本研究では，多数の評価尺度を同時に最適化可能な進化型多目的最適化を採用し，路線網を個体とみなした進化型多目的路線網最適化を提案する．さらに，効率的な路線網最適化を目指し，(i) 間島らによるマルチエージェントシステムに基づくバス路線網構築手法(以下，間島手法) を応用した効果的な初期母集団生成と，(ii) 類似した路線同士の交換に基づく交叉方法を組み合わせた手法を提案する．具体的に(i) 初期母集団生成では，個体毎に路線網の輸送コストのうちバス台数を考慮する重みを変化させることで，多様な路線とバス台数を持つ路線網集団を生成する． (ii) 類似した路線同士の交換では，路線同士の類似度をレーベンシュタイン距離に基づき定義し，類似度の高い路線同士を交換する．一般的なバス路線網最適化問題であるMandl の都市交通ベンチマーク問題を用いた実験において，平時の路線網を寸断後に提案手法と従来手法(GA に基づく路線網生成手法・間島手法) を適用し路線網を修正した結果，以下の知見が得られた．(1) 従来手法を用いて生成した修正解と比較して，提案手法は利用者の移動経路の変化量，路線網の輸送コストの2 つの目的ともに優れた解が生成可能である． (2)従来考慮されていなかった平時からの利用者の移動経路の変動量を最小化することで，結果的に路線網の変化量も削減可能である． (3) 類似路線の交換に基づく交叉と多様な初期母集団生成により，ランダムに路線を交換する交叉を実行した場合と比較して50% の計算量削減が可能であり，GA に基づく路線網生成手法と比較すると，25% 以上の計算量削減が可能である．特に，(3) の計算量削減は実世界の大都市において道路の寸断が発生してから短時間で修正解を導出し，早期の復旧が可能であることを示しており，実応用の観点から重要な知見である．