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 |
