apps‎ > ‎Ekillion‎ > ‎

Ekillion実験結果

Ekillionを用いた実験の内容、および結果を紹介します。
表1は、4つの大都市近郊区間路線図をグラフとして表現したときの、節点数(駅数)・辺数(駅間数)および総距離です。
なお「全駅路線図」は実際の路線図をそのままグラフ化したもの、「乗換駅路線図」は次数2の節点(乗り換えの発生しない中間駅)を省略したグラフを表しています。
表2は節点(駅)の次数分布を表しています。次数1は終端駅です(大都市近郊区間の終端を表しているので、いわゆる終着駅とは必ずしも一致しない)。

表1 路線データ
地域 全駅路線図 乗換駅路線図
節点数 辺数 総距離 節点数 辺数 総距離
大阪 355 364 941.0 km 26 34 924.3 km
東京 623 653 2,055.6 km 72 101 2,037.9 km
福岡 128 131 323.0 km 19 22 323.0 km
新潟 58 59 174.2 km 7 7 159.0 km

表2 節点(駅)の次数分布
地域 次数nの駅数 次数1の駅名 最大次数の駅名
1 2 3 4 5
大阪 7 329 13 6 0 JR難波,和田岬,園部,桜島,東羽衣,関西空港,播州赤穂 京都,大阪,尼崎,木津,天王寺,京橋(4次)
東京 18 551 34 16 4 いわき,黒磯,海芝浦,大川,扇町,久里浜,韮崎,銚子,成田空港など 西船橋,拝島,赤羽,大宮(5次)
福岡 8 109 8 3 0 博多南,門司港,鳥栖,行橋,若松,今山,西戸崎,宇美 折尾,香椎,長者原(4次)
新潟 3 51 3 1 0 五泉,長岡,弥彦 新津(4次)

最多ルート駅ペア(隣接駅探索)

ある駅から隣の駅までの大回りルートを考えたとき、もっともルート数が多くなる駅のペアを探索しました。
表3は「乗換駅路線図」を用いた結果、表4は「全駅路線図」を用いた結果です。
乗換駅路線図は中間駅を省略していますので、たとえば大阪駅と京都駅は隣の駅として扱われています。

表3 最多ルート駅ペア探索(隣接駅+乗換駅路線図)
s-t駅名 ルート数 最長距離(km) 駅数 探索s-t総件数 処理時間(秒) 処理時間/件
大阪 京都 - 大阪 103 514.8 16 34 1.49 0.043
東京 我孫子 - 成田 9,427,117 976.4 52 101 15.07 0.149
福岡 桂川 - 新飯塚 9 157.5 11 22 0.94 0.043
新潟 東三条 - 吉田 3 108.5 5 7 0.37 0.053

表4 最多ルート駅ペア探索(隣接駅+全駅路線図)
s-t駅名 ルート数 最長距離(km) 駅数 探索s-t総件数 処理時間(秒) 処理時間/件
大阪 東淀川 - 新大阪 103 556.9 208 364 23.55 0.065
東京 布佐 - 木下 9,427,117 1,007.4 331 653 2715 4.16
福岡 福工大前 - 九産大前 9 163.4 66 131 6.45 0.049
新潟 田上 - 矢代田 3 121.0 41 59 2.57 0.043
* ルート数が等しい場合、最長距離がもっとも長い駅のペアを表示している。
* 実行環境: amazon AWS m3.2xlarge (8 cores, 26 ECUs, 30 GB memory)

最多ルート駅ペア(全対探索)

ある駅からある駅までの大回りルートを考えたとき、もっともルート数が多くなる駅のペアを探索しました。
先述の「隣接駅探索」は隣り合う駅同士という制約がありましたが、この「全対探索」ではその制約を取り払い、
大都市近郊区間内のすべての駅同士でルート数が最多となるペアを探索しています。
表5は「乗換駅路線図」を用いた結果、表6は「全駅路線図」を用いた結果です。

表5 最多ルート駅ペア探索(乗換駅路線図)
s-t駅名 ルート数 最長距離(km) 駅数 探索s-t総件数 処理時間(秒) 処理時間/件
大阪 播州赤穂 - 近江塩津 392 653.4 20 325 5.73 0.018
東京 磯子 - 上総亀山 26,440,720 1,121.1 52 2,556 143.8 0.0056
福岡 今山 - 博多南 14 200.0 11 171 2.82 0.016
新潟 東三条 - 新発田 4 87.7 5 21 0.32 0.015

表6 最多ルート駅ペア探索(全駅路線図)
s-t駅名 ルート数 最長距離(km) 駅数 探索s-t総件数 処理時間 処理時間(秒)/件
大阪 栗東 - 塚口 392 743.1 283 62,790 29.6 分 0.028
東京 本郷台 - 東十条 28,328,716 1,078.0 360 339,076 - -
福岡 原町 - 東水巻 16 200.3 81 8,125 2.5 分 0.019
新潟 越後石山 - 長岡 4 134.1 46 1,653 0.5 分 0.018
* ルート数が等しい場合、最長距離がもっとも長い駅のペアを表示している。
* 実行環境: amazon AWS m3.2xlarge (8 cores, 26 ECUs, 30 GB memory)
* 表6の東京のみ別の環境で実行したため、処理時間は省略する。

最長ルート駅ペア探索

ある駅からある駅までの大回りルートを考えたとき、距離がもっとも長くなる駅のペアを探索しました。
表7は隣り合う駅同士という制約をつけた場合、表8はすべての駅同士で探索した場合です。

表7 最長ルート駅ペア探索(隣接駅探索)
s-t 駅名 ルート数 最長距離(km) 駅数
大阪 JR河内永和 - JR俊徳道 71 557.0 208
東京 西日暮里 - 日暮里 4,789,007 1,016.8 340
福岡 博多 - 吉塚 7 163.4 66
新潟 田上 - 矢代田 3 121.0 41

表8 最長ルート駅ペア探索(全対探索)
s-t 駅名 ルート数 最長距離(km) 駅数
大阪 JR難波 - 塚口 210 743.5 286
東京 いわき - 韮崎 6,632,867 1,201.3 379
福岡 今山 - 水巻 10 210.2 85
新潟 北三条 - 長岡 3 142.2 48


実験に使用したコード

Graphillion の使用例として、Ekillion 本体(Python)および駅ペア探索(Ruby)のコードを公開します。
データファイルは配布しないため、そのままでは実行できないことにご留意ください。
ċ
allPairs.rb
(5k)
nysol info,
2013/11/14 0:33
ċ
ekillion.py
(10k)
nysol info,
2013/11/14 1:22