成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.44 No.２ (2007) pp.75-77（特別研究費に係る論文）

鉄道運賃計算のための効率の良いアルゴリズム― Suica/Pasmo 利用可能エリア内の JR510 駅を対象にした場合 ―森田 隼史*1，池上敦子*2，菊地丞*3，山口拓真*3，中山利宏*3，大倉元宏*4

An efficient algorithm for a railway fare calculation― A case study involving 510 JR stations within the Suica/Pasmo system ―Shunji MORITA*1，Atsuko IKEGAMI*2，Jo KIKUCHI*3，Takuma
YAMAGUCHI*3，Toshihiro NAKAYAMA*3，Motohiro OHKURA*4（Received September 14, 2007）

１

はじめに最安運賃経路になる。しかし，会社によっては，エリアや路線の種類に対応する複数の対キロ運賃表を持ったり，鉄道サービスを運営する企業では，与えられた２駅間運賃計算の特例ルールが存在することなどから，最短経の運賃算出のため，利用可能な経路の中で，最も運賃が路を求めても，その経路の運賃が最安にならない場合が安い経路（最安運賃経路）とその運賃（最安運賃）を計ある。そのため，与えられた２駅間の正確な運賃を計算算することが求められる。本研究では，正確な最安運賃するためには，その２駅間に存在する多くの利用可能経を計算するためのモデルとアルゴリズムの構築を試みた。

路の運賃を全て，もしくは，その 1 部を計算して判断す

具体的には，2007 年３月から関東地域で相互利用が可能る必要があるとされてきた[1]。しかし，ネットワークがになった IC カード乗車券 Suica/Pasmo の適用範囲（関東

大きく，また，密になればなるほど，存在する利用可能IC 範囲）を対象に，大きく２つの研究，(1)1 社内の運賃経路の数は膨大になり，経路の列挙に多くの計算時間が計算，(2)複数社を含む運賃計算を行った。

費やされることが容易に想像できる。

本稿では，研究(1)の内の，「東日本旅客鉄道（JR 東日これに対し，本研究では，正確な運賃を得る保証を持本）510 駅全駅間」の運賃計算の成果を報告する。

ちつつ，経路の列挙数を出来る限り（可能なら 1 まで）減らすことを目指し，関東 IC 範囲に存在する全 27 鉄道

2．1

社内の運賃計算会社の運賃計算を行った。本稿では，その中でも，対キロ運賃表が 4 種類存在し，駅数も関東 IC 範囲の中で最も各鉄道会社では，運賃計算のために，鉄道を利用した距離に対して運賃を定めた対キロ運賃表を持つ｡

多い JR 東日本を対象にした運賃計算アルゴリズムについて述べる。

表1

対キロ運賃表距離（km）x
1471116～～～～～

３．JR 東日本の運賃計算

片道運賃（円）f(x)36101520

3．1 運賃計算のルール

140180190230320

JR 東日本における関東 IC 範囲（図 1 参照）には，山手線エリア，電車特定エリア，東京近郊エリアと呼ばれる３つのエリアが存在し，次のような包含関係がある。
山手線エリア⊂電車特定エリア⊂東京近郊エリア

表 1 が示すように，運賃は距離が長くなればなるほど高く設定されており，一般的には，２駅間の最短経路が*1

情報処理専攻・2006 年度修了生
情報科学科・准教授*3 日本信号株式会社*4 エレクトロメカ二クス学科・教授*2－75－黒磯

最安運賃経路
日立着

渋川発

最短経路

電車特定エリア
東京近郊エリア
奥多摩

成田空港

韮崎

図２

最短経路と最安運賃経路

電車特定エリアに存在する 2 駅間の最短経路を実線で示してあるが，この経路自体は東京近郊エリアにまたが君津
大原

久里浜っている。このような場合，電車特定エリア内の最短経伊東

図1路（破線で示した経路で，実線で示した経路より距離がJR 東日本における関東 IC 範囲長いもの）も存在するはずである。この２つの経路は，運賃を求めるために利用する対キロ運賃表が異なるため，また，JR 東日本の路線には，幹線と呼ばれるものと地得られた２つの経路のうち，どちらの経路が最安運賃に方交通線（地交線）と呼ばれるものの２種類があり，地なるかを比較しなければならず，本来の最短経路の運賃交線を利用したときの運賃の方が高く設定されている。

が最安であるという保証が得られない。

この３つのエリアと２種類の路線の関係から， JR 東日本の関東 IC 範囲では，異なる４つの対キロ運賃表が存在3．3し，それらを適切に利用しなければならない。表２に４運賃計算アルゴリズム

前節の問題点を考慮するために， これまでは，2 駅間つの対キロ運賃表の名称と適用範囲を示す。に存在する可能経路を全て，もしくはその多くを列挙して運賃の比較を行う方法が取られてきたが，非常に多く表２４つの対キロ運賃表の適用範囲と名称の処理時間を費やしてしまうという問題を抱えていた。
そこで，我々が考案したアルゴリズムでは，エリア毎

山手線エリア

電車特定エリア

東京近郊エリア

幹線

山手線エリア用

電車特定エリア用

幹線用の部分ネットワークを構築することによって，解の存在

地交線――

地交線用の可能性を考慮しつつ，エリアを狭めながら最短路問題を解くことで，できる限り列挙に依存せずに問題を解く

幹線だけを利用した場合，山手線エリア内だけの利用ことを可能にした。与えられた２駅間の最安運賃を求めであれば山手線エリア用の対キロ運賃表を，電車特定エるために，高々3 回の最短路問題を解くだけで，正確なリアだけの利用であれば電車特定エリア用の対キロ運賃解を得ることはもちろん，高速にこれらを処理できる。

表を適用して運賃を求める。そして，地交線だけを利用

なお，アルゴリズムで求める最短経路は，ダイクストラした場合には，地交線用の対キロ運賃表を適用して運賃法[2][3]を利用して求める。以下におおまかなアルゴリを求めるように決められている。また，幹線と地交線をズムの流れを示す。

混在して利用する混合経路の場合には，その距離によっアルゴリズムて利用する対キロ運賃表が変わったり，地交線部分の距東京近郊エリアの最短経路を求める。→ path0

離を割増して運賃を計算する。そして，これらの他にも，if（path0 が山手線エリア内だけを通る）いくつかの運賃計算の特例ルールが存在している。

■ path0 の運賃を採用。
3．2

else if（path0 の構成がすべて電車特定エリア内）

運賃計算の難しさ

if（発着ともに電車特定エリア内）

前節で挙げたルールより，発着 2 駅間に関して，最短経路が最安運賃経路にならないケースが発生する。その電車特定エリア内の最短経路を求める。→ path1

例の一つを図２に示す。

■ path0 と path1 の安い運賃を採用。
else－76－■ path0 の運賃を採用。

elseif（path0 が地交線だけの経路 or 10km 以下の混合経路）
if（幹線の対キロ運賃表を適用する経路に path0 より安い経路がある）
その経路を path0 にする。
else if（path0 が 10km を越す混合経路）
運賃計算キロの最短経路を求める。→ path0
地交線の最短経路を求める。→ path1
if（path0 より path1 の運賃の方が安い）
path1 を path0 にする。
if（発着とも山手線エリア内）
電車特定エリア内の最短経路を求める。→ path1
山手線エリア内の最短経路を求める。→ path2■ path0～2 の中で，一番安い運賃を採用。
else if（発着とも電車特定エリア内）
電車特定エリア内の最短経路を求める。→ path1■ path0 と path1 の安い運賃を採用。
else■path0 の運賃を採用

このアルゴリズムを利用し，JR 東日本の関東 IC 範囲における全２駅間の運賃計算を行った結果，正確な解を得るだけでなく，処理時間を大幅に（約 12 時間半から0.67 秒にまで）削減することに成功した。

４．おわりに今後の展開としては，新しい駅や新しい路線が導入された場合や，運賃計算のルールが変更された場合に生じる「運賃の変更」をシミュレートできるツールの開発などが考えられる。また，途中で一度だけ，駅の改札を通る経路の中での最安運賃経路を求めるといったような，目的に合わせた経路探索ができるモデルを構築することも考えられる。

参考文献[1] 野末尚次：道具箱としての OR。オペレーションズ・リサーチ，52（2007），135-140．
[2] R.K.Ahuja，T.L.Magnanti，J.B.Orlin：Network flows．
Prentice-hall，New Jersey，1993．
[3] E.W.Dijkstra：A note on two problems in connection
with graphs．Numeriche Mathematics，vol.1，pp.269-271，
1959．

－77－