- 著者
- 森田 隼史 池上 敦子 菊地 丞 山口 拓真 中山 利宏 大倉 元宏
- 出版者
- 公益社団法人 日本オペレーションズ・リサーチ学会
- 雑誌
- 日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)
- 巻号頁・発行日
- vol.54, pp.1-22, 2011 (Released:2017-06-27)
- 参考文献数
- 13
鉄道運賃は,基本的に乗車距離が長くなればなるほど高くなるように設定されているが,同じ距離でも,会社によって,さらには同じ会社内でも地域や路線によって異なる料金が設定されている.さらに,乗車区間によっては割引ルールや特定の運賃が設定されていることなどから,最短経路の運賃が最安になるわけではない.運賃計算では,利用者の乗車経路が明確でない場合,乗車可能経路の中から最も安い運賃となる経路を利用したとみなし,その運賃を採用するルールが設定されている.そのため,与えられた2駅間の正しい運賃を計算するためには,その2駅間の乗車可能経路の運賃を全て,もしくはその1部を列挙して判断する必要があると考えられてきた.これに対し,我々は2008年,複数の鉄道会社を含む鉄道ネットワークにおける最安運賃経路探索用ネットワークFarenetと探索アルゴリズムを提案し,これを利用した自動改札機用運賃計算エンジンの実用にいたった.本論文では,Farenet構築の基盤となった1会社内の運賃計算,具体的には,首都圏エリアで利用可能であるICカード乗車券Suica/PASMOの適用範囲に含まれるJR東日本510駅の全2駅間(129,795組)に対して行った運賃計算について報告する.4つの対キロ運賃表と複数の運賃計算ルールが存在するこの運賃計算において,異なる地域・路線を考慮した部分ネットワークとダイクストラ法を利用することにより,多くの経路を列挙する従来の運賃計算方法において数時間要していた計算を,約1秒で処理することに成功した.論文の最後では,アルゴリズムの効率を示すとともに,対象ネットワークが持つ運賃計算上の特徴についても報告する.
2 0 0 0 OA 鉄道運賃計算のための最安運賃経路探索 : 複数の鉄道会社を含む場合
- 著者
- 池上 敦子 森田 隼史 山口 拓真 菊地 丞 中山 利宏 大倉 元宏
- 出版者
- 公益社団法人 日本オペレーションズ・リサーチ学会
- 雑誌
- 日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)
- 巻号頁・発行日
- vol.51, pp.1-24, 2008 (Released:2017-06-27)
- 参考文献数
- 41
- 被引用文献数
- 1 1
本研究では,運賃設定の異なる複数の鉄道会社を含む鉄道ネットワーク上の運賃計算を正確かつ高速に行えるネットワーク表現とアルゴリズムについて報告する.鉄道運賃は,利用者の乗車経路が明らかであるとき,多くの場合,その経路に含まれる各鉄道会社が定めた運賃を足し合わせることによって得られる.一方,利用者の乗車経路が明確でない場合,利用可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することが一般的である.しかし,鉄道運賃は,基本的には「距離が長くなればなるほど高く」なるように設定されているものの,同じ距離でも,会社によって異なる料金が設定されていることや,乗車区間によって割引ルールや特別運賃が設定されていることなどから,物理的距離に基づくショーテストパスが最も安い経路になるわけではない.よって,与えられた2駅間の正しい運賃を計算するためには,その2駅間の可能経路の運賃をすべて,もしくは,その1部を列挙して比較判断する必要があることがこれまでにも報告されてきた.本研究では,物理的構造に基づくネットワーク上での経路探索を行う代わりに,ダイクストラ法が利用可能な運賃計算用ネットワークを構築し,ダイクストラ法と,少ないケースではあるがK-shortest paths問題用のアルゴリズムを利用することにより,複数社を含む鉄道ネットワーク運賃計算の大幅な高速化に成功した.
- 著者
- 池上 敦子 森田 隼史 山口 拓真 菊地 丞 中山 利宏 大倉 元宏
- 出版者
- 公益社団法人 日本オペレーションズ・リサーチ学会
- 雑誌
- 日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:04534514)
- 巻号頁・発行日
- vol.51, pp.1-24, 2008
- 参考文献数
- 41
- 被引用文献数
- 4 1
本研究では,運賃設定の異なる複数の鉄道会社を含む鉄道ネットワーク上の運賃計算を正確かつ高速に行えるネットワーク表現とアルゴリズムについて報告する.鉄道運賃は,利用者の乗車経路が明らかであるとき,多くの場合,その経路に含まれる各鉄道会社が定めた運賃を足し合わせることによって得られる.一方,利用者の乗車経路が明確でない場合,利用可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することが一般的である.しかし,鉄道運賃は,基本的には「距離が長くなればなるほど高く」なるように設定されているものの,同じ距離でも,会社によって異なる料金が設定されていることや,乗車区間によって割引ルールや特別運賃が設定されていることなどから,物理的距離に基づくショーテストパスが最も安い経路になるわけではない.よって,与えられた2駅間の正しい運賃を計算するためには,その2駅間の可能経路の運賃をすべて,もしくは,その1部を列挙して比較判断する必要があることがこれまでにも報告されてきた.本研究では,物理的構造に基づくネットワーク上での経路探索を行う代わりに,ダイクストラ法が利用可能な運賃計算用ネットワークを構築し,ダイクストラ法と,少ないケースではあるがK-shortest paths問題用のアルゴリズムを利用することにより,複数社を含む鉄道ネットワーク運賃計算の大幅な高速化に成功した.
- 著者
- 森田 隼史 池上 敦子 菊地 丞 山口 拓真 中山 利宏 大倉 元宏
- 出版者
- 公益社団法人日本オペレーションズ・リサーチ学会
- 雑誌
- 日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:04534514)
- 巻号頁・発行日
- vol.54, pp.1-22, 2011-12
鉄道運賃は,基本的に乗車距離が長くなればなるほど高くなるように設定されているが,同じ距離でも,会社によって,さらには同じ会社内でも地域や路線によって異なる料金が設定されている.さらに,乗車区間によっては割引ルールや特定の運賃が設定されていることなどから,最短経路の運賃が最安になるわけではない.運賃計算では,利用者の乗車経路が明確でない場合,乗車可能経路の中から最も安い運賃となる経路を利用したとみなし,その運賃を採用するルールが設定されている.そのため,与えられた2駅間の正しい運賃を計算するためには,その2駅間の乗車可能経路の運賃を全て,もしくはその1部を列挙して判断する必要があると考えられてきた.これに対し,我々は2008年,複数の鉄道会社を含む鉄道ネットワークにおける最安運賃経路探索用ネットワークFarenetと探索アルゴリズムを提案し,これを利用した自動改札機用運賃計算エンジンの実用にいたった.本論文では,Farenet構築の基盤となった1会社内の運賃計算,具体的には,首都圏エリアで利用可能であるICカード乗車券Suica/PASMOの適用範囲に含まれるJR東日本510駅の全2駅間(129,795組)に対して行った運賃計算について報告する.4つの対キロ運賃表と複数の運賃計算ルールが存在するこの運賃計算において,異なる地域・路線を考慮した部分ネットワークとダイクストラ法を利用することにより,多くの経路を列挙する従来の運賃計算方法において数時間要していた計算を,約1秒で処理することに成功した.論文の最後では,アルゴリズムの効率を示すとともに,対象ネットワークが持つ運賃計算上の特徴についても報告する.