普通列車を対象とした時間制約付き最長経路探索問題の探索法の考察

摘要

現在，乗換案内サービスの中には普通列車限定の探索機能を有するものが存在する.普通列車の場合，移動に時間がかかるため，一定の時間内に移動できる範囲が旅程を作成する際に重要である.しかし，既存の乗換案内サービスでは，出発駅の情報から，一定の時間内に移動できる範囲を知ることは難しい.本研究が対象とする問題は，普通列車のみを利用し、出発駅から乗り継ぎながら，制約時間内で移動できる最長経路を複数通り求める経路探索問題である.この問題を解くことにより，普通列車を利用した旅行の計画作りに有用な情報を得ることができる.筆者らは，現実的な時間で解くことができるヒユーリスティック探索法を考案した.本研究では，このヒューリスティック探索法と，経路探索問題を一般的に解くことができる他の探索法との計算時間• メモリ使用量についての比較を行った.