文献

J-GLOBAL ID：200902219128323116   整理番号：09A0022196

鉄道運賃計算のための最安運賃経路探索-複数の鉄道会社を含む場合-

FINDING THE MINIMUM COST PATH FOR A RAILWAY FARE CALCULATION-A CASE STUDY INVOLVING MORE THAN ONE RAILWAY COMPANY-

著者 (6件)： 池上敦子 (成けい大) ,  森田隼史 (成けい大) ,  山口拓真 (日本信号) ,  菊地丞 (日本信号) ,  中山利宏 (日本信号) ,  大倉元宏 (成けい大)
資料名： 日本オペレーションズ・リサーチ学会和文論文誌  (Transactions of the Operations Research Society of Japan)
巻： 51  ページ： 1-24  発行年： 2008年12月 
JST資料番号： L5172A  ISSN： 1349-8940  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,運賃設定の異なる複数の鉄道会社を含む鉄道ネットワーク上の運賃計算を正確かつ高速に行えるネットワーク表現とアルゴリズムについて報告する。鉄道運賃は,利用者の乗車経路が明らかであるとき,多くの場合,その経路に含まれる各鉄道会社が定めた運賃を足し合わせることによって得られる。一方,利用者の乗車経路が明確でない場合,利用可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することが一般的である。しかし,鉄道運賃は,基本的には「距離が長くなればなるほど高く」なるように設定されているものの,同じ距離でも,会社によって異なる料金が設定されていることや,乗車区間によって割引ルールや特別運賃が設定されていることなどから,物理的距離に基づくショーテストパスが最も安い経路になるわけではない。よって,与えられた2駅間の正しい運賃を計算するためには,その2駅間の可能経路の運賃をすべて,もしくは,その1部を列挙して比較判断する必要があることがこれまでにも報告されてきた。本研究では,物理的構造に基づくネットワーク上での経路探索を行う代わりに,ダイクストラ法が利用可能な運賃計算用ネットワークを構築し,ダイクストラ法と,少ないケースではあるがK-shortest paths問題用のアルゴリズムを利用することにより,複数社を含む鉄道ネットワーク運賃計算の大幅な高速化に成功した。(著者抄録)

シソーラス用語： *運賃 ,  *経路探索 ,  *計算機アルゴリズム ,  ネットワーク ,  流れ図 ,  鉄道輸送 ,  利用者 ,  最短路問題 ,  数値計算 ,  高速化 ,  ループ ,  節点 ,  経路
準シソーラス用語： ダイクストラ法 ,  併算割引

分類 (3件)： 輸送と業務  (TC01030N) ,  数値計算  (JE02000J) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (42件)：

• D. Eppstein: Finding the k shortest paths. SIAM Journal on Computing, 28(1998), 652-673.
• E. W. Dijkstra: A note on two problems in connection with graphs. Numeriche Mathematics, 1(1959), 269-271.
• 半田恵一, 田中俊明: 乗換え案内サービスにおける経路探索手法電子情報通信学会論文誌, J88-D1(2005), 1525-1533.
• N. Katoh, T. Ibaraki, and H. Mine: An efficient algorithm for K shortest simple paths. Networks, 12(1982), 411-427.
• E. Q. V. Martins, M. M. B. Pascoal, and J. L. E. Santos: The K shortest paths problem. Research Report, CISUC (1998).

タイトルに関連する用語 (5件)： 鉄道 ,  運賃計算 ,  運賃 ,  経路探索 ,  会社