利用鉄道会社数の制約を考慮した最安運賃経路探索(情報・システム基礎)

概要

論文の詳細を見る
本論文では,改札を通らずして複数の鉄道会社をまたいで乗車した場合の鉄道運賃計算を扱う.一般的に,鉄道運賃は多数存在する到着可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することになっている.また,鉄道会社ごとの運賃体系の違いや乗継割引等によって,距離最短の経路と運賃最安の経路が一致するとは限らない.筆者らの先行研究では,従来の「可能経路列挙とその運賃比較」による最安運賃経路探索に対して,ダイクストラ法を利用できるネットワークと探索アルゴリズムを提案し,正確かつ高速な計算を可能にした.この運賃計算方法は基本的な運賃計算制度及び乗継割引制度に基づく最安運賃経路を導くが,自動改札機における運賃計算のためには,更に利用する鉄道会社の数に関する制約を考慮する必要がある.本論文では,ネットワークを階層的に扱うことで,この問題を解決する自動改札機のための運賃計算方法を提案する.提案方法は,膨大な量の運賃計算を高速に行うことを可能にしたため,実際の自動改札機や自動精算機などの運賃計算にかかわるシステムに適用された.
2010-04-01