名古屋駅スタートで全6路線の最短完乗ルートを検索

前回、全6路線の最短完乗ルートの検索が10分以内で終わって 目標達成 としたが、名古屋駅スタートでの検索を忘れてた。

ということで、名古屋駅スタートで検索。
今までの経緯、札幌市営地下鉄、福岡市地下鉄での結果から、藤が丘駅のような終端駅からスタートする場合に比べて、途中駅からスタートの場合は完乗の所要時間も計算時間も長くなると思われる。

いきなり全6路線はやめて、名古屋駅駅スタートも4路線から始めることにする。


4路線(東山線、名城線、名港線、鶴舞線)

名古屋 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 八事 八事 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 本山 本山 ～( 東山線 )～ 藤が丘 藤が丘 ～( 東山線 )～ 高畑 名古屋-(東山線)-伏見-(鶴舞線)-丸の内-(鶴舞線)-上小田井-(鶴舞線)-丸の内 -(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞線)-御器所-(鶴舞線)-八事-(鶴舞線)- 赤池-(鶴舞線)-八事-(名城線)-本山-(名城線)-平安通-(名城線)-久屋大通-(名 城線)-栄-(名城線)-上前津-(名城線)-金山-(名港線)-名古屋港-(名港線)-金山 -(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山-(東山線)-藤が丘-(東山線)- 本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)-名古屋-(東山線)- 高畑 所要時間: 276(分) 乗車時間: 186(分) 乗換回数: 5(回)×10(分) 折返回数: 4(回)×10(分) intMakeRouteNum = 224088 intRouteNumMax = 40 -- 処理時間: 2(秒) intMakeRouteNum = 237274 intRouteNumMax = 40

藤が丘駅スタートの場合と比べると、検索時間は 0秒→2秒、検索ルート数は、28,245ルート→237,274ルートで約8.4倍になっている。


5路線(東山線、名城線、名港線、鶴舞線、桜通線)

名古屋 ～( 桜通線 )～ 丸の内 丸の内 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 八事 八事 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 本山 本山 ～( 東山線 )～ 藤が丘 藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 名古屋 名古屋 ～( 桜通線 )～ 中村区役所 中村区役所 ～( 桜通線 )～ 徳重 名古屋-(桜通線)-丸の内-(鶴舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見 -(鶴舞線)-上前津-(鶴舞線)-御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)- 八事-(名城線)-本山-(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城 線)-上前津-(名城線)-金山-(名港線)-名古屋港-(名港線)-金山-(名城線)-新瑞 橋-(名城線)-八事-(名城線)-本山-(東山線)-藤が丘-(東山線)-本山-(東山線)- 今池-(東山線)-栄-(東山線)-伏見-(東山線)-名古屋-(東山線)-高畑-(東山線)- 名古屋-(桜通線)-中村区役所-(桜通線)-名古屋-(桜通線)-丸の内-(桜通線)-久 屋大通-(桜通線)-今池-(桜通線)-御器所-(桜通線)-新瑞橋-(桜通線)-徳重 所要時間: 357(分) 乗車時間: 237(分) 乗換回数: 6(回)×10(分) 折返回数: 6(回)×10(分) intMakeRouteNum = 157891743 intRouteNumMax = 54 -- 処理時間: 1202(秒) intMakeRouteNum = 186919531 intRouteNumMax = 54

藤が丘駅スタートの場合と比べると、検索時間は 116秒→1202秒で約10倍、検索ルート数は、16,531,193ルート→186,919,531ルートで約11倍になっている。


6路線(東山線、名城線、名港線、鶴舞線、桜通線、上飯田線)

名古屋 ～( 桜通線 )～ 丸の内 丸の内 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 八事 八事 ～( 名城線 )～ 平安通 平安通 ～( 上飯田線 )～ 上飯田 上飯田 ～( 上飯田線 )～ 平安通 平安通 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 本山 本山 ～( 東山線 )～ 藤が丘 藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 名古屋 名古屋 ～( 桜通線 )～ 中村区役所 中村区役所 ～( 桜通線 )～ 徳重 名古屋-(桜通線)-丸の内-(鶴舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見 -(鶴舞線)-上前津-(鶴舞線)-御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)- 八事-(名城線)-本山-(名城線)-平安通-(上飯田線)-上飯田-(上飯田線)-平安通 -(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-(名城線)-金山-(名港線)- 名古屋港-(名港線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山-(東 山線)-藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東 山線)-名古屋-(東山線)-高畑-(東山線)-名古屋-(桜通線)-中村区役所-(桜通線 )-名古屋-(桜通線)-丸の内-(桜通線)-久屋大通-(桜通線)-今池-(桜通線)-御器 所-(桜通線)-新瑞橋-(桜通線)-徳重 所要時間: 389(分) 乗車時間: 239(分) 乗換回数: 8(回)×10(分) 折返回数: 7(回)×10(分) intMakeRouteNum = 603554163 intRouteNumMax = 56 -- 処理時間: 5199(秒) intMakeRouteNum = 717584587 intRouteNumMax = 56

藤が丘駅スタートの場合と比べると、検索時間は 454秒→5199秒で約11倍、検索ルート数は、67,328,414ルート→717,584,587ルートで約11倍になっている。

藤が丘駅スタートの場合は 454秒(7分半)で計算できたので目標達成としたが、名古屋駅スタートだと1時間半弱。

もう少し改善が必要かな。


つづく

全6路線の最短完乗ルート計算達成

前回の改善 所要時間予測の精度を向上 でプログラムを改修した。

まずは藤が丘駅スタートで4路線。

4路線(東山線、名城線、名港線、鶴舞線)

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-(鶴 舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞線)- 御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞 線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山-( 名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-(名城線)- 金山-(名港線)-名古屋港 所要時間: 245(分) 乗車時間: 185(分) 乗換回数: 3(回)×10(分) 折返回数: 3(回)×10(分) intMakeRouteNum = 3987 intRouteNumMax = 36 -- 処理時間: 0(秒) intMakeRouteNum = 28245 intRouteNumMax = 36

検索結果は改修前と同じ。

処理時間(計算時間)は改修前も0秒だったので変わらず。
検索ルート数は、97,105ルートが28,245ルートになり、3分の1以下。


続いて5路線をこれも藤が丘駅スタートで。
5路線(東山線、名城線、名港線、鶴舞線、桜通線)

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 名古屋 名古屋 ～( 桜通線 )～ 中村区役所 中村区役所 ～( 桜通線 )～ 徳重 徳重 ～( 桜通線 )～ 新瑞橋 新瑞橋 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 八事 八事 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上小田井 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(桜通線)-中村区役所-(桜通線)-名古 屋-(桜通線)-丸の内-(桜通線)-久屋大通-(桜通線)-今池-(桜通線)-御器所-(桜 通線)-新瑞橋-(桜通線)-徳重-(桜通線)-新瑞橋-(名城線)-八事-(名城線)-本山 -(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-(名城線 )-金山-(名港線)-名古屋港-(名港線)-金山-(名城線)-新瑞橋-(名城線)-八事-( 鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞線)-上前津-(鶴舞線)-伏 見-(鶴舞線)-丸の内-(鶴舞線)-上小田井 所要時間: 328(分) 乗車時間: 228(分) 乗換回数: 5(回)×10(分) 折返回数: 5(回)×10(分) intMakeRouteNum = 2415419 intRouteNumMax = 50 -- 処理時間: 116(秒) intMakeRouteNum = 16531193 intRouteNumMax = 50

処理時間(計算時間)は改修前の2,927秒(約49分)から116秒(約2分)に25分の1に激減。
検索ルート数は、698,771,279ルート(約7億)が16,531,193ルート(約1700万)になり、42分の1に激減。
検索結果は改修前と同じ。


いよいよ全6路線の計算。
6路線(東山線、名城線、名港線、鶴舞線、桜通線、上飯田線)

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 名古屋 名古屋 ～( 桜通線 )～ 中村区役所 中村区役所 ～( 桜通線 )～ 徳重 徳重 ～( 桜通線 )～ 新瑞橋 新瑞橋 ～( 名城線 )～ 平安通 平安通 ～( 上飯田線 )～ 上飯田 上飯田 ～( 上飯田線 )～ 平安通 平安通 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 八事 八事 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上小田井 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(桜通線)-中村区役所-(桜通線)-名古 屋-(桜通線)-丸の内-(桜通線)-久屋大通-(桜通線)-今池-(桜通線)-御器所-(桜 通線)-新瑞橋-(桜通線)-徳重-(桜通線)-新瑞橋-(名城線)-八事-(名城線)-本山 -(名城線)-平安通-(上飯田線)-上飯田-(上飯田線)-平安通-(名城線)-久屋大通 -(名城線)-栄-(名城線)-上前津-(名城線)-金山-(名港線)-名古屋港-(名港線)- 金山-(名城線)-新瑞橋-(名城線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線 )-御器所-(鶴舞線)-上前津-(鶴舞線)-伏見-(鶴舞線)-丸の内-(鶴舞線)-上小田 井 所要時間: 360(分) 乗車時間: 230(分) 乗換回数: 7(回)×10(分) 折返回数: 6(回)×10(分) intMakeRouteNum = 9567093 intRouteNumMax = 56 -- 処理時間: 454(秒) intMakeRouteNum = 67328414 intRouteNumMax = 56

454(秒)、7分半で計算した。
検索ルート数は67,328,414ルート(約6700万)。

10分以内で計算できているので、目標は達成。
2月始めからプログラムを作り始めているので、ｌここまで2ヵ月近く掛かった。


つづく。

改善：所要時間予測の精度を向上

実用的な時間(目標は10分以内)で、名古屋市営地下鉄の全6路線の最短完乗ルートの検索を行えるようんするため、更にプログラムを改善。

少し前、改善：最短所要時間予測により検索ルート削減 ということで、ルートが完成する前に所要時間を予想し、それまでの最短所要時間よりも長い場合はそれ以上のルート検索を行わないようにし、評価するルート数を減らした。

最短所要時間は、

• 作成したルートの所要時間
• 未乗車区間の所要時間の合計

の総合計時間として計算した。

未乗車の区間が複数路線あれば乗り換え時間も掛かるし、折り返し時間が必要なルートも考えられるので、もう少しルールを追加。

1. (ルートの最後のセグメントの路線と未乗車の路線の種類-1)×乗換え時間(10分)
2. (未乗車のセグメントのうち、終端駅を含むセグメントの数-1)×折り返し時間(10分)

1の方はこの後の乗換え時間が最低でもどれだけ掛かるかを数えて加算。
マイナス1しているのは、乗換え回数なので。
実際にはもっと多いこともあるが 最低でもこれだけ掛かる ということで。

2の方は同じくこの後の折り返し時間が最低でもどれだけ掛かるかを数えて加算。
マイナス1しているのは、最後は終端駅になるケースを考慮してその分を除外。

これで、所要時間の予測精度が上がり無駄な検索を打ち切ることで検索ルート数を減らし検索時間を減らせるはず。

プログラムを改修して実行。
結果は次回。


つづく。

改善：検索の経過を表示し、時間をかけて計算

前回、改善：分岐の順序を最適化での5路線の計算は、

• 東山線、名城線、名港線、鶴舞線、桜通線 → 計算できず
• 東山線、名城線、名港線、鶴舞線、上飯田線 → 2秒で計算

だった。

10分経っても終わらない場合は「計算できず」とすることにしてるけど、もしかしたらもう少し待てば計算できるのではないかと思い、検索中のルートを表示するようにしてみた。

10分経過した時点で思ったよりも計算が進んでいたため、そのまま計算を続行。

2,927秒(約49分)で終わった。

計算ルート数は4路線の97,514ルート(約10万)から698,771,279ルート(約7億)で7千倍以上に増えている。

5路線(東山線、名城線、名港線、鶴舞線、桜通線）

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 名古屋 名古屋 ～( 桜通線 )～ 中村区役所 中村区役所 ～( 桜通線 )～ 徳重 徳重 ～( 桜通線 )～ 新瑞橋 新瑞橋 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 八事 八事 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上小田井 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(桜通線)-中村区役所-(桜通線)-名古 屋-(桜通線)-丸の内-(桜通線)-久屋大通-(桜通線)-今池-(桜通線)-御器所-(桜 通線)-新瑞橋-(桜通線)-徳重-(桜通線)-新瑞橋-(名城線)-八事-(名城線)-本山 -(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-(名城線 )-金山-(名港線)-名古屋港-(名港線)-金山-(名城線)-新瑞橋-(名城線)-八事-( 鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞線)-上前津-(鶴舞線)-伏 見-(鶴舞線)-丸の内-(鶴舞線)-上小田井 所要時間: 328(分) 乗車時間: 228(分) 乗換回数: 5(回)×10(分) 折返回数: 5(回)×10(分) intMakeRouteNum = 31370501 intRouteNumMax = 50 -- 処理時間: 2927(秒) intMakeRouteNum = 698771279 intRouteNumMax = 50

残りは上飯田線の1路線だけ。
上飯田線は平安通駅から1区間だけ(続きは名鉄小牧線)だけど、3分岐で分岐して戻るり(1分岐)、また3分岐になるので、5路線の場合の数倍の計算量になると思われる。

5路線で約49分なので、5倍で4時間ちょっと、10倍だと8時間以上の計算時間か。
待てない時間じゃないけど、ここはもう少し改善を進めた方が良さそう。


つづく。

改善：分岐の順序を最適化

前回の改善、「最短所要時間予測により検索ルート削減」により検索ルート数を削減することができ、計算時間を短縮できたが、それでもまだ4路線までしか計算できない。

今回の改善は「分岐の順序を最適化」。

例えば藤が丘駅スタートの場合、最初の分岐は本山駅。

本山駅での選択肢は4つ。

1. そのまま東山線を進み、今池方面へ
2. 名城線に乗換え、左回り
3. 名城線の乗換え、右回り
4. 東山線を引き返す(折り返し)

最短完乗ルートの検索は、すべての組み合わの中から所要時間が一番短いルートを探す」ので、どんな順番でルートの評価を行なっても最終的に得られる最短完乗ルートは同じはず。

しかし、「すべての組合せを試すためには膨大な組合せの作成と評価をする必要があ現実的な時間で計算を終えられないため、これまでに無駄なルートを省くなどの方法で改善してきた。

よって、組合せの作り方によって、検索ルート数が変わってくるのではないかと考えられる。
分岐駅でのルート作成順を最適化すれば改善されるのではないか。

例えば上記の本山駅での分岐の場合、4の「引き返す」は明らかに無駄なルート。
1の東山線を進むルートと、2と3の名城線に乗り換えるルートだと、乗換え時間(設定で10分としている)があるので、1の方が効率が良さそう。

問題はどんな順序が最適かということ。
とりあえずは、以下のルールを考えてみた。

• 1分岐の場合 → そのまま進む
• 2分岐の場合 → 直進、戻る の順
• 3分岐の場合 → 乗り換え、直進、戻る の順
• 4分岐以上の場合 → 直進、乗り換え、、、乗り換え、戻る の順

このプログラム改善は今までの中で一番難しかった。
元々、分岐の順序を考えない設計だったので、今までに無い情報(優先順)を作り、それに従って処理をするようにしないといけない。


さっそく実行。
まずは、藤が丘駅スタート。

4路線(東山線、名城線、名港線、鶴舞線)

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線) -名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-( 鶴舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞 線)-御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所- (鶴舞線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)- 本山-(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-( 名城線)-金山-(名港線)-名古屋港 所要時間: 245(分) 乗車時間: 185(分) 乗換回数: 3(回)×10(分) 折返回数: 3(回)×10(分) intMakeRouteNum = 8045 intRouteNumMax = 37 -- 処理時間: 0(秒) intMakeRouteNum = 97514 intRouteNumMax = 37

最短完乗ルートは改善前のとまったく同じ。
プログラムは問題無さそう。

問題は検索ルート数。
検索ルート数を減らせるのではないかと思って改善を行なったが、期待に反して評価ルート数（intMakeRouteNum）は減らず、わずかだけど増えている。
97,105ルートが97,514ルートに。


5路線で計算。
5路線(東山線、名城線、名港線、鶴舞線、桜通線）

改善前と同じで、10分経っても終わらない。


5路線目を上飯田線で計算。
5路線(東山線、名城線、名港線、鶴舞線、上飯田線）

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 平安通 平安通 ～( 上飯田線 )～ 上飯田 上飯田 ～( 上飯田線 )～ 平安通 平安通 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-(鶴 舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞線)- 御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞 線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山-( 名城線)-平安通-(上飯田線)-上飯田-(上飯田線)-平安通-(名城線)-久屋大通-( 名城線)-栄-(名城線)-上前津-(名城線)-金山-(名港線)-名古屋港 所要時間: 277(分) 乗車時間: 187(分) 乗換回数: 5(回)×10(分) 折返回数: 4(回)×10(分) intMakeRouteNum = 42929 intRouteNumMax = 39 -- 処理時間: 2(秒) intMakeRouteNum = 596342 intRouteNumMax = 39

計算時間は2秒で改善前と同じ。
検索ルート数は、594,340ルート → 596,342ルートでこれも僅かに増えている。

今回のプログラム改善はかなり大変だったけど効果は無し。


つづく。

改善：最短所要時間予測により検索ルート削減 ～ 5路線、6路線

改善版のプログラムでは、4路線の最短完乗ルートの検索を、藤が丘駅スタートで0秒、名古屋駅スタートで1秒で計算できた。

路線を増やして計算。

まずは藤が丘駅スタート。


続いて名古屋駅スタート。
5路線、東山線、名城線、名港線、鶴舞線、桜通線

10分以上掛かってるので「時間切れ」で計算できず。
1億5千万ルート以上を計算して終わらない。

4路線(東山線、名城線、名港線、鶴舞線)は 97,105ルート を0秒で計算。
桜通線は、名古屋、丸の内、久屋大通、今池、御器所、新瑞橋の6駅で他路線と交差しているので、それぞれの駅で乗り換えの可能性があることになる。

交差なので4分岐。

単純計算で、4の6乗 = 4096倍 のルート数。

4路線で 97,105ルートなので、97,106×4,096 = 397,742,080 で約40億ルート計算すれば終わる?

そんな単純な計算じゃないかな。

路線の順序を決めたばかりだけど、5路線目を上飯田線にして計算してみることにした。

上飯田線は、1区間だけで平安通駅から分岐している路線。

分岐が1つ増えるだけなので計算できそう。

5路線、東山線、名城線、名港線、鶴舞線、上飯田線

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 平安通 平安通 ～( 上飯田線 )～ 上飯田 上飯田 ～( 上飯田線 )～ 平安通 平安通 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線)- 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-(鶴 舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞線)- 御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞 線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山-( 名城線)-平安通-(上飯田線)-上飯田-(上飯田線)-平安通-(名城線)-久屋大通-( 名城線)-栄-(名城線)-上前津-(名城線)-金山-(名港線)-名古屋港 所要時間: 277(分) 乗車時間: 187(分) 乗換回数: 5(回)×10(分) 折返回数: 4(回)×10(分) intMakeRouteNum = 28236 intRouteNumMax = 42 -- 処理時間: 2(秒) intMakeRouteNum = 594340 intRouteNumMax = 42

今度は2秒で計算。
ルート数は 594,340ルート なので、 97,105ルート の約6倍。
こんなもんかな。


つづく。

改善：最短所要時間予測により検索ルート削減

名古屋市営地下鉄の全6路線の完乗ルート検索。
4路線(東山線、名城線、名港線、鶴舞線)までは計算できたけど、5路線、6路線はまだ計算できていない。

完乗ルートの検索は、

1. ルートを作る
2. ルートが「完乗」かどうか判断する
3. ルートが「完乗」なら、「所要時間」を計算する

を繰り返すことになる。
最短のルートを求めるためには可能性があるすべてのルートを作って評価。
ルートを作るのは上記のの1、評価は上記の2と3に当たる。

実用的な時間で計算するためには、評価時間を短くする(処理を速くする)か、評価するルート数を減らす必要がある。

藤が丘駅スタートの場合、前回のプログラムで4路線の場合、最終的には 529,845 ものルートを作って評価している。
名古屋駅スタートの場合は更に増えて、1,705,788 のルートを評価している。

これまでも、ルート数を減らすための改善をしてきたが、今回は、最短所要時間予測により検索ルート削減すること。

ルートが未完成の状態で「最短所要時間」を予測。

最短所要時間は、

• 作成したルートの所要時間
• 未乗車区間の所要時間の合計

の総合計時間とする。

未乗車の区間が複数路線あれば、乗り換え時間も掛かるし、折り返し時間が必要なルートも考えられるが今回はそこまでは考えないことにする。


さっそくプログラムを改善。

まずは藤が丘駅スタートで確認。
4路線、東山線、名城線、名港線、鶴舞線

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線) -名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-( 鶴舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞 線)-御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所- (鶴舞線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)- 本山-(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-( 名城線)-金山-(名港線)-名古屋港 所要時間: 245(分) 乗車時間: 185(分) 乗換回数: 3(回)×10(分) 折返回数: 3(回)×10(分) intMakeRouteNum = 5458 intRouteNumMax = 40 -- 処理時間: 0(秒) intMakeRouteNum = 97105 intRouteNumMax = 40

結果は前回と同じ。
ルート数は、529,845 から 97,105 に大幅に削減。
5分の1以下。

続いて名古屋駅スタートで検証。
4路線、東山線、名城線、名港線、鶴舞線

名古屋 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 藤が丘 藤が丘 ～( 東山線 )～ 本山 本山 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 八事 八事 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上小田井 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(東山線)-栄-(東山 線)-今池-(東山線)-本山-(東山線)-藤が丘-(東山線)-本山-(名城線)-八事-( 名城線)-新瑞橋-(名城線)-金山-(名港線)-名古屋港-(名港線)-金山-(名城線) -上前津-(名城線)-栄-(名城線)-久屋大通-(名城線)-平安通-(名城線)-本山-( 名城線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞線)-上 前津-(鶴舞線)-伏見-(鶴舞線)-丸の内-(鶴舞線)-上小田井 所要時間: 264(分) 乗車時間: 184(分) 乗換回数: 4(回)×10(分) 折返回数: 4(回)×10(分) intMakeRouteNum = 6354 intRouteNumMax = 40 -- 処理時間: 1(秒) intMakeRouteNum = 354185 intRouteNumMax = 40

これも結果は前回と同じ。
ルート数は、1,705,788 から 354,185 で、同じく大幅に削減。
こちらも、ほぼ5分の1になった。


つづく。

C言語版プログラムでどこまで計算できるのか

前回、

• 3路線 ： 東山線、桜通線、名城線
• 4路線 ： 東山線、桜通線、名城線、名港線
• 5路線 ： 東山線、桜通線、名城線、名港線、上飯田線

まで計算した。

同じ1路線でも、1区間だけの名港線や上飯田線と鶴舞線では検索ルート数が大きく異なるはず。
今後改善を進めていくにあたり、路線の順序を決めることにした。

路線は開通順に、

1. 東山線(1957年)
2. 名城線(1965年)
3. 名港線(1971年)
4. 鶴舞線(1977年)
5. 桜通線(1989年)
6. 上飯田線(2003年)

に追加していく。

開通順とは言っても、ほとんどの路線は部分開通から徐々に延伸して全線開通しているので実際にはもっと複雑になるが、今回はそこまでは考えずに路線として最初に最初の区間が開通した順ということで上記の順とした。

スタート駅は藤が丘駅で始めているので藤が丘駅(東山線)。
それと、JR、名鉄、近鉄のターミナル駅でもある名古屋駅(東山線、桜通線)の2駅。

計算時間は10分で打ち切り。
10分経っても計算が終わらなければ、「計算できず」とする。

まずは藤が丘駅スタート。

3路線、東山線、名城線、名港線

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 栄 栄 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線) -名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(東山線)-栄-(名城 線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)-本山- (名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-(名城線 )-金山-(名港線)-名古屋港 所要時間: 155(分) 乗車時間: 125(分) 乗換回数: 2(回)×10(分) 折返回数: 1(回)×10(分) intMakeRouteNum = 159 intRouteNumMax = 28 -- 処理時間: 0(秒) intMakeRouteNum = 862 intRouteNumMax = 28

4路線、東山線、名城線、名港線、鶴舞線

藤が丘 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 伏見 伏見 ～( 鶴舞線 )～ 上小田井 上小田井 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上前津 上前津 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 藤が丘-(東山線)-本山-(東山線)-今池-(東山線)-栄-(東山線)-伏見-(東山線) -名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(鶴舞線)-丸の内-( 鶴舞線)-上小田井-(鶴舞線)-丸の内-(鶴舞線)-伏見-(鶴舞線)-上前津-(鶴舞 線)-御器所-(鶴舞線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所- (鶴舞線)-上前津-(名城線)-金山-(名城線)-新瑞橋-(名城線)-八事-(名城線)- 本山-(名城線)-平安通-(名城線)-久屋大通-(名城線)-栄-(名城線)-上前津-( 名城線)-金山-(名港線)-名古屋港 所要時間: 245(分) 乗車時間: 185(分) 乗換回数: 3(回)×10(分) 折返回数: 3(回)×10(分) intMakeRouteNum = 15693 intRouteNumMax = 40 -- 処理時間: 1(秒) intMakeRouteNum = 529845 intRouteNumMax = 40

5路線、東山線、名城線、名港線、鶴舞線、桜通線

計算できず。

6路線、東山線、名城線、名港線、鶴舞線、桜通線、上飯田線

計算できず。

続いて名古屋駅スタート。


3路線、東山線、名城線、名港線

名古屋 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 栄 栄 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 栄 栄 ～( 東山線 )～ 藤が丘 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(東山線)-栄-(名城 線)-上前津-(名城線)-金山-(名港線)-名古屋港-(名港線)-金山-(名城線)-新 瑞橋-(名城線)-八事-(名城線)-本山-(名城線)-平安通-(名城線)-久屋大通-( 名城線)-栄-(東山線)-今池-(東山線)-本山-(東山線)-藤が丘 所要時間: 183(分) 乗車時間: 123(分) 乗換回数: 4(回)×10(分) 折返回数: 2(回)×10(分) intMakeRouteNum = 825 intRouteNumMax = 28 -- 処理時間: 0(秒) intMakeRouteNum = 2985 intRouteNumMax = 28

4路線、東山線、名城線、名港線、鶴舞線

名古屋 ～( 東山線 )～ 高畑 高畑 ～( 東山線 )～ 藤が丘 藤が丘 ～( 東山線 )～ 本山 本山 ～( 名城線 )～ 金山 金山 ～( 名港線 )～ 名古屋港 名古屋港 ～( 名港線 )～ 金山 金山 ～( 名城線 )～ 八事 八事 ～( 鶴舞線 )～ 赤池 赤池 ～( 鶴舞線 )～ 上小田井 名古屋-(東山線)-高畑-(東山線)-名古屋-(東山線)-伏見-(東山線)-栄-(東山 線)-今池-(東山線)-本山-(東山線)-藤が丘-(東山線)-本山-(名城線)-八事-( 名城線)-新瑞橋-(名城線)-金山-(名港線)-名古屋港-(名港線)-金山-(名城線) -上前津-(名城線)-栄-(名城線)-久屋大通-(名城線)-平安通-(名城線)-本山-( 名城線)-八事-(鶴舞線)-赤池-(鶴舞線)-八事-(鶴舞線)-御器所-(鶴舞線)-上 前津-(鶴舞線)-伏見-(鶴舞線)-丸の内-(鶴舞線)-上小田井 所要時間: 264(分) 乗車時間: 184(分) 乗換回数: 4(回)×10(分) 折返回数: 4(回)×10(分) intMakeRouteNum = 16695 intRouteNumMax = 40 -- 処理時間: 4(秒) intMakeRouteNum = 1705788 intRouteNumMax = 40

5路線、東山線、名城線、名港線、鶴舞線、桜通線

計算できず。

6路線、東山線、名城線、名港線、鶴舞線、桜通線、上飯田線

計算できず。

これを基準に名古屋市営地下鉄の全6路線の最短完乗ルートの検索ができるように改善を進める。


つづく。

改善：高速化(C言語移植)、でも全6路線は検索できず

ちょっと寄り道して、名古屋市営地下鉄以外で最短完乗ルートの計算をしたけど、再び当初の目標の名古屋市営地下鉄の最短完乗ルートの検索を目指してプログラムの改善。

プログラムを作るためには、

• プログラムの構造
• データ構造

を決める(設計する)必要があるが、今回は試行錯誤で進めているため、途中、何度も見直しをしてきた。

試行錯誤が行いやすいようにということで、プログラムはVBScriptで作ってきたが、だいたい形になってきたのでこの週末で、VBScriptのプログラムをC言語に書き換えた。

• プログラムの構造
• データ構造

はほぼそのままに、プログラムの記述をVBScriptからC言語に変更。
こういうのをプログラムの移植といいますが、今回はその移植作業。


さっそく、東山線、桜通線、名城線の3路線で、藤が丘駅スタートで計算。

VBScript版の計算結果は次の通り。

このプログラムをC言語に移植。

C言語版の計算結果は次の通り。

結果の出力方法を変えましたが、計算結果はまったく同じ。
計算時間は341.1秒から1秒に高速化。
単純計算で341倍。

同じアルゴリズムのプログラムでこれだけスピードアップ。
VBScriptのプログラムをC/C++に書き換え(移植する)ことで1桁～2桁以上の高速化ができるだろうと思っていたが、2桁以上の高速化ができた。


もう少し路線数を増やして計算。

4路線、東山線、桜通線、名城線、名港線

6秒で計算。

5路線、東山線、桜通線、名城線、名港線、上飯田線

ちょっと時間が掛かって、28秒で計算。

6路線、東山線、桜通線、名城線、名港線、上飯田線、鶴舞線

10分程計算を続けたが終わらない。
さすがにいきなり全6路線は無理だった。


今回は単純に言語の変更だけで100倍以上の高速化を実現。
でも、全6路線の最短完乗ルートを検索するためには、まだまだ改善が必要。


つづく。

名古屋市営地下鉄以外で最短完乗ルート

名古屋市営地下鉄以外の事業者の最短完乗ルートの計算をしてみた。

• 札幌市営地下鉄
• 札幌市営地下鉄＋札幌市電
• 福岡市地下鉄

それぞれ、3路線、4路線、4路線(徒歩移動を1路線とする)の最短完乗ルートの検索。

今のプログラムではまだ、名古屋市営地下鉄の全6路線の最短完乗ルートの検索はできないけど、そんなプログラムでも福岡市地下鉄の4路線を0.1秒とか0秒(測定限度以下)で計算が終わったのはびっくり。

同じ4路線でも、札幌市営地下鉄＋札幌市電はそんなに速くない。

福岡市地下鉄は分岐が3分岐(枝分かれ)だけで、交差(4分岐)が無い。
そのため、ルートの組み合わせが少ないことが計算が速い理由と思われる。

名古屋市営地下鉄では交差(4分岐)が11駅、分岐(3分岐)が2駅もある。

そのため、ルートの組み合わせが膨大な数になり、結果、計算に時間が掛かっている。

名古屋市営地下鉄は6路線で特に路線数が多いとも思えないけど、交差が多いことが最短完乗ルートの計算を困難にしているんだと思う。
ハードルは高い。

次回からはまた名古屋市営地下鉄の最短完乗ルートの計算に戻ることする。
目標はある程度高い方がいいけど、でも、これからどうやって進めようか...


つづく。

福岡市地下鉄～最短完乗ルート計算

福岡市地下鉄の計算用のデータ（路線データ、時間データ）を準備したので実際に、最短完乗ルートを計算。

3路線+1路線(徒歩)の4路線で乗換駅は3駅。
札幌市営地下鉄＋札幌市電と同程度の計算量と思われる。

天神駅スタート

計算時間は0.1秒。
あまりにも速く、一瞬で結果が表示されたので間違いかと思って検算したら合ってた。

4路線あるが交差(4分岐)が無く分岐(3分岐)だけなのでルート数が少ないと思われる。
所要時間は160分。
最短完乗ルートは上記画面の結果以外に3ルート、全部で4ルートあった。
乗車の順番が違うだけで、所要時間160分は同じ。

続いて橋本駅スタート

計算時間は更に短くて表示は0秒。
測定限度以下で0秒。

ルートの所要時間は129分だった。
こちらは最短完乗ルートは上記の1ルートだけ。
ゴール駅は箱崎線の貝塚駅。
区間乗車時間が長い空港線の姪浜駅がゴールのルートが最短完乗ルートになるような気がしてたけど、乗換時間の差だろうか。


7駅をスタート駅にした結果結果は次の通り。
最短は橋本駅スタートのルートと、逆の貝塚駅スタートのルート。

つづく。

福岡市地下鉄（路線データ、時間データ）

福岡市地下鉄の最短完乗ルートの検索。
路線図、乗車時間のデータを用意。


■ 路線図 ■
Wikipedia - 福岡市地下鉄 路線図
福岡市交通局 - 路線図

3路線で構成され、空港線と箱崎線は中州川端駅で接続。
空港線はJR筑肥線に乗り入れているが、今回は地下鉄線だけを対象とする。

七隈線は空港線と隣接しているが同じ駅での接続は無い。
「空港線や箱崎線へは一旦改札を出て、天神地下街を介して天神駅で乗り換えとなる。」とあり、また、「改札内を出場してから120分以内に天神駅の改札内に入場する場合に限り、天神駅と当駅を同一駅扱いとし、営業キロを通算した運賃で乗車することができる。」とのこなので乗換駅として扱うことにする。

空港線と七隈線で駅名が異なることと乗換え時間が掛かることから、天神駅～天神南駅の間は徒歩の路線扱いでデータを用意することにする。

移動時間はYahoo!の路線検索では7分、Google Mapsの路線検索では12分となっている。
大雑把だが10分と想定。
別路線扱いとすることで、天神駅と天神南駅の両方で乗り換えが発生することになるので、乗換え×2回+移動時間ということになる。

今回も乗換え時間は10分とするので、空港線から七隈線への乗換えは30分も掛かることになる。
徒歩10分の距離で30分は多過ぎると思われるし、同一駅での乗り換え時間を10分と設定していることを考えると、10分+移動時間(10分)で20分程度が適当と思われる。
今のプログラムを使うために、移動時間を0分と設定し、トータルで乗換え時間20分となるようにする。


■ 路線 ■
(1) 空港線
(2) 箱崎線
(3) 七隈線
(4) 天神地下街

■ 駅 ■
(1) 姪浜、天神、中洲川端、福岡空港
(2) 中洲川端、貝塚
(3) 橋本、天神南
(4) 天神、天神南
駅は終端と乗換え駅のみ。
途中の駅は今回は省略。

■ 乗車時間 ■
(1-1) 空港線：姪浜～天神、13分
(1-2) 空港線：天神～中洲川端、1分
(1-3) 空港線：中洲川端～福岡空港、9分
(2-1) 箱崎線：中洲川端～貝塚、10分
(3-1) 七隈線：橋本～天神南、24分
(4-1) 天神地下街：天神～天神南、0分

■ 乗換時間 ■
電車を降りて別の路線に乗り換える時間。
今回はすべて10(分)とする。
駅別、路線別の違いは考えない。
実際に乗り換えるために歩く時間と、次の電車の待ち時間を含めている。

前述の通り、天神駅と天神南駅の乗り換えはトータルで20分になるように移動時間を0分として調整する。

■ 折返時間 ■
終点に到着した後、同じ路線を戻るときの時間。
今回はすべて10(分)とする

■ スタート駅 ■
博多駅と、おそらく所要時間が最短になると思われる橋本駅をスタート駅とする。
札幌市営地下鉄と同様に、すべての駅をスタート駅にした結果も試すことにする。


つづく。

横浜市営地下鉄、神戸市営地下鉄

名古屋市営地下鉄以外で最短完乗ルートの検索では、3～5路線の地下鉄事業者、

• 札幌市営地下鉄、3路線
• 都営地下鉄、4路線
• 横浜市営地下鉄、3路線
• 神戸市営地下鉄、4路線
• 福岡市地下鉄、3路線

の5事業者について、「次回から順次試していくことにする。」とした。

ところが、実際にデータ作成のために調べてみると、横浜市営地下鉄には「ブルーライン」と「グリーンライン」の2路線しかない。

もう一度、Wikipediaの一覧を見てみると、1・3号線（ブルーライン）は一体的に運行しているので実質は路線数2と書かれている。

同様に4路線の神戸市営地下鉄も、「西神・山手線」と「海岸線」の2路線しかない。
西神延伸・西神・山手線は一体的に運行しているので実質は路線数2と書かれている。

2路線の最短完乗ルート検索はもちろん可能だけれど、あまり面白味が無い。

福岡市地下鉄は3路線あるので、次は福岡市地下鉄の検索。


つづく。

都営地下鉄

札幌市営地下鉄の次は都営地下鉄。

• 浅草線
• 三田線
• 新宿線
• 大江戸線

の4路線。

路線図はこの辺りから。

http://ja.wikipedia.org/wiki/%E9%83%BD%E5%96%B6%E5%9C%B0%E4%B8%8B%E9%89%84

http://www.kotsu.metro.tokyo.jp/subway/line.pdf

http://www.kotsu.metro.tokyo.jp/subway/timetable/

4路線なので比較的簡単と考えて始めたけど...

• 浅草線
• 三田線
• 新宿線 

の3路線は特に問題ないけど問題は大江戸線。

大江戸線は光が丘～新宿の放射部と、新宿から左回りに都庁前までの環状部で構成されている。

環状部と言っても山手線、大阪環状線や名古屋の地下鉄名城線のような環状運転ではなく、数字の「６」を横にしたような感じで折返し運転をしている。

これだけなら問題ないが、問題は放射部の途中に都庁前駅があること。

環状部の終点の都庁前と同じ駅なのでここで乗り換えができてしまう。

これをどう表現するのか。

今のプログラムではこれが表現できない。

放射部、環状部と言っても同じ大江戸線で直通運転なので路線は1つ。

今まで通に区間データを作ると、

(4-1) 光が丘～都庁前

(4-2) 都庁前～新宿(新宿線)

(4-3) 新宿～

(4-n) ～都庁前

と言った感じになるが、放射部の都庁前駅と環状部の終点の都庁前駅は繋がってないので、光が丘から都庁前を経由して環状部を右回りするルートはあり得ない。

これが表現できない。

(案１) 放射部の都庁前駅と環状部の都庁前駅を別の駅として扱う

都庁前A駅と都庁前B駅といった感じ。

これなら上記のような問題は無い。

ただし、乗換はできるので、それを表現する必要がある。

例えば、乗車時間0分の仮想路線を作って、都庁前A駅と都庁前B駅を繋ぐ。

今は乗換時間は一律10分にしているのでこの方法だと、都庁前駅での乗換時間が20分になってしまう。

(案2) 上記(案1)+乗換時間を駅毎に設定でいるようにする

一律10分の乗換時間を、駅毎に別々に設定できるようにプログラムに機能追加する。

都庁前A駅と都庁前B駅は乗換時間は5分、その他は10分とすれば解決する。

他の路線でも、実際には駅によって乗換時間も折返し時間も異なるはずなので、いずれは対応したいと思っている機能ではあるが、まだ、当面の目標の名古屋市営地下鉄全6線の最短完乗ルートの検索ができていないので、今の段階では優先度が低い。

(案3) 光が丘～都庁前と、都庁前～都庁前を別の路線とする

単純に別路線とすると、直通運転でも乗換時間が発生してしまう。

複数路線を跨る直通運転に対応するようにプログラムに機能追加する。

もう1つ、他の路線に乗換ができるが、駅名が異なるケースの対応も問題。

都営地下鉄では新宿線の馬喰横山駅と浅草線の東日本橋駅。

これもプログラムの機能追加が必要で、更に、データの持ち方の見直しも必要になってくる。

今のところ1事業者だけの完乗ルートの検索をしているが、いずれは地域内の複数事業者で最短完乗ルートの検索ができるようにしたいと思っているので、大江戸線の(案3)での複数路線の直通運転に対応する機能、路線で駅名が異なる乗換に対応する機能は必要になってくるし、(案2)の駅毎、路線毎の乗換時間の設定、折返し時間の設定機能も必要になってくると思う。

いずれは対応したいが、今の段階では優先度を下げておきたい。

ということで、都営地下鉄は路線データの作成で行き詰ってしまった。

何かいいアイデア、解決策を思い付くまで、機能強化するまで保留。

つづく。

札幌市営地下鉄＋札幌市電～最短完乗ルート計算

さっそく、札幌市営地下鉄＋札幌市電の4路線で最短完乗ルートの計算をしてみた。

さっぽろ駅スタート

最短完乗ルート(所要時間266分)は上記のルートを含めて6ルートあった。

地下鉄×3路線の最短完乗ルートの所要時間は217分だったのでプラス49分で市電も含めて完乗できる。

新さっぽろ駅スタート

最短完乗ルート(所要時間243分)は上記のルートを含めて3ルートあった。

地下鉄×3路線の最短完乗ルートの所要時間は190分だったので、市電の乗車分はプラス53分。

地下鉄×3路線のときは、2.9～17.5秒で計算できてたけど、今回はずいぶんと掛かった。

さっぽろ駅スタートで171.5(秒)、新さっぽろ駅スタートで39.9(秒)掛かっている。

つづく。

札幌市営地下鉄＋札幌市電

札幌には地下鉄のほかに札幌市電もある。
http://www.city.sapporo.jp/st/index.html

札幌市電は3路線。

• 一条線（西4丁目停留場～西15丁目停留場）
• 山鼻西線（西15丁目停留場～中央図書館前停留場）
• 山鼻線（中央図書館前停留場～すすきの停留場）

3路線あるが、1本で繋がっていて直通運転されているので実質1路線と考えて良さそう。

札幌市電を加えた4路線でも最短完乗ルートを計算してみることにする。

地下鉄とは6駅/停留所で乗換えができるが、始点/終点の大通駅/西4丁目とすすきの駅でのみ乗り換えるものとする。

追加したの路線データ、時間データは次の通り。（青字が追加・変更分）

■ 路線 ■

(1) 南北線

(2) 東西線

(3) 東豊線

(4) 市電

■ 駅 ■

(1) 麻生、さっぽろ、大通、すすきの、真駒内

(2) 宮の沢、大通、新さっぽろ

(3) 栄町、さっぽろ、大通、福住

(4) 大通、すすきの

■ 乗車時間 ■

(1-1) 南北線：麻生～さっぽろ、8分

(1-2) 南北線：さっぽろ～大通、1分

(1-3) 南北線：大通～すすきの、1分

(1-4) 南北線：すすきの～真駒内、15分

(2-1) 東西線：宮の沢～大通、15分

(2-2) 東西線：大通～新さっぽろ、20分

(3-1) 東豊線：栄町～さっぽろ、11分

(3-2) 東豊線：さっぽろ～大通、1分

(3-3) 東豊線：大通～福住、12分

(4-1) 市電：大通～すすきの、40分

つづく。

札幌市営地下鉄～最短完乗ルート計算２

前回はさっぽろ駅スタートの場合と新さっぽろ駅スタートの場合で最短完乗ルートの検索を行なった。
結果は、さっぽろ駅スタートの所要時間が217分、新さっぽろ駅スタートで190分だった。
予想通り、新さっぽろ駅スタートの場合の方が所要時間が短い最短完乗ルートになったけど、果たして本当にこのルートが最短なんだろうか。

札幌市営地下鉄の場合、スタート駅の候補は8駅。
せっかくなので8駅すべてをスタート駅にして計算しみた。

前回計算した新さっぽろ駅スタートは札幌市営地下鉄の最短完乗ルートだったが、もう1つ、同じ所要時間のルートがあった。
真駒内駅スタートでゴール駅が新さっぽろ駅の逆ルート。

ほとんどの区間を2回乗っているけど、スタートとゴールの区間だけが1回乗車。
この区間が長いルートが最も効率がいい最短完乗ルート。

つづく。

札幌市営地下鉄～最短完乗ルート計算

札幌市営地下鉄の計算用のデータ（路線データ、時間データ）を準備したので実際に、最短完乗ルートを計算してみた。

3路線、乗換駅は2駅なので比較的簡単に結果が出ると思われる。

まずはスタート駅をさっぽろ駅

計算時間は13.8秒。
ルートの所要時間は217分で、単純な乗車時間の合計84分2.6倍。
放射状に延びる路線を中心駅からスタートしているので、ほぼ全線について行って戻るために2倍。
これに、折り返しが5回で50分と乗換え時間が掛かるため。


最短完乗ルートは上記画面の結果以外に7ルートあった。
乗車の順番が違うだけで、所要時間217分は同じ。


続いて新さっぽろ駅スタート

計算時間は僅か3.2秒。
ルートの所要時間は190分だった。
さっぽろ駅スタートの場合と異なり、こちらは最短完乗ルートは上記の1ルートだけ。




札幌市営地下鉄では名古屋市営地下鉄と違う、興味深い結果になった。


計算時間は13.8秒と3.2 秒で今まで改善してきた効果が現れているが、逆にこれだけ短時間で結果が出るならここまでプログラムの改善をする必要は無いのかもしれない。
数分程度で計算できれば実用性という面(このプログラムに実用性があるかどかという本質は別として)では充分なので。


最初に、名古屋市営地下鉄の全6路線の最短完乗ルートを検索するために作り始めたプログラム。
まだ完成していないけど、ある程度の高めの目標があったから改善に取り組むモチベーションを維持できてきた。
最初から簡単に結果が出ていたら、ここまで改善しなかったと思う。




つづく。

札幌市営地下鉄（路線データ、時間データ）

名古屋の時と同じように、路線図、乗車時間のデータを用意。


■ 路線図 ■
Wikipedia - 札幌市営地下鉄、路線図
札幌市 地下鉄路線図

　
大通駅で全3路線、さっぽろ駅で2路線の乗換ができる。

■ 路線 ■
(1) 南北線
(2) 東西線
(3) 東豊線

■ 駅 ■
(1) 麻生、さっぽろ、大通、真駒内
(2) 宮の沢、大通、新さっぽろ
(3) 栄町、さっぽろ、大通、福住
駅は終端と乗換え駅のみ。
途中の駅は今回は省略。

■ 乗車時間 ■
(1-1) 南北線：麻生～さっぽろ、8分
(1-2) 南北線：さっぽろ～大通、1分
(1-3) 南北線：大通～真駒内、16分
(2-1) 東西線：宮の沢～大通、15分
(2-2) 東西線：大通～新さっぽろ、20分
(3-1) 東豊線：栄町～さっぽろ、11分
(3-2) 東豊線：さっぽろ～大通、1分
(3-3) 東豊線：大通～福住、12分

■ 乗換時間 ■
電車を降りて別の路線に乗り換える時間。
名古屋と同じく、今回はすべて10(分)とする。
駅別、路線別の違いは今回は考えない。
実際に乗り換えるために歩く時間と、次の電車の待ち時間を含めている。

南北線と東豊線はさっぽろ駅からすすきの辺りまで並行していて、さっぽろ駅と大通駅では路線の乗換ができるが、地図を見ると南北線と東豊線は2街区離れている。
乗換時間10分というのが妥当なのか、良く判らない。

■ 折返時間 ■
終点に到着した後、同じ路線を戻るときの時間。
名古屋と同じく、今回はすべて10(分)とする

■ スタート駅 ■
JR札幌駅(函館本線)があるさっぽろ駅をスタート駅とする。
もう1つ、おそらく所要時間が最短になると思われる新さっぽろ駅もスタート駅とする。

札幌市営地下鉄特有の条件もあると思いますが、今回は上記の条件で。


つづく。

名古屋市営地下鉄以外で最短完乗ルートの検索

今のプログラムでは、4～5路線程度まで最短完乗ルートの検索ができる。
名古屋市営地下鉄の全6路線の最短完乗ルートの検索のために作り始めたプログラムだけど、なかなか6路線の検索に辿り着けない。(全6路線の最短完乗ルートの検索に向けて を参照）

ここでプログラムの開発/改善を一休みして、名古屋以外の地下鉄で最短完乗ルートの検索をしてみようと思う。
特に地下鉄に拘る訳じゃないけど、もともと地下鉄で始めたので。

Wikipediaで調べてみると、日本には公営で10事業者、民間で6事業者が地下鉄を運行している。
Wikipedia - 日本の地下鉄

1路線、2路線ではプログラムを作って検索する必要もないので3路線以上。
現時点では5路線が限界なので、3～5路線で絞ると次の5事業者。

• 札幌市営地下鉄、3路線
• 都営地下鉄、4路線
• 横浜市営地下鉄、3路線
• 神戸市営地下鉄、4路線
• 福岡市地下鉄、3路線

次回から順次試していくことにする。

名古屋市営地下鉄の6路線の最短完乗ルートの検索ができたら、 

• 大阪市営地下鉄、8路線
• 東京メトロ、9路線

も試してみたい。
更に、東京の地下鉄、都営地下鉄と東京メトロを合わせた合わせた13路線も試してみたい。


つづく。




追記 - 2012年3月5日
横浜市営地下鉄の3路線は「ブルーライン」と「グリーンライン」の実質2路線。
神戸市営地下鉄の4路線も、「西神・山手線」と「海岸線」の実質2路線。
であることに気が付いた。
ちゃんとWikipediaの一覧に書いてあるのに見落としてた。
ということで、最短完乗ルートの検索対象からは除外することにた。

改善：最短区間数に満たないルートを評価対象外にする

今のプログラムでは、5路線で45分とか200分掛かる。
前回の検証で、名古屋市営地下鉄の全6路線の最短完乗ルートの検索には150日もの時間が掛かるという予測。
抜本的な改善が必要ではあるけど、まずは今のプログラムを少しでも速くするためにプログラムコードを見直してみた。


ルートの評価、時間の計算に掛かるコストを削減
例えば、東山線と桜通線に限定すると路線は次のようになる。

この2路線は2ヵ所で交差していて乗換えができる。

それぞれに終端駅が2駅、合計4駅の終端駅がある

2路線で6区間あるので(上図参照)、最低でも6区間のルートでないと完全乗車ルートにはならない。
更に、終端駅では折り返しをするので、4駅の折り返して4区間余分に乗車する必要があるので6+4で10区間。
でも、スタート駅を終端駅にすれば、その駅での折り返しは不要。
更に、ゴール駅も終端駅のルートなら、その駅での折り返しも不要。
そう考えると、2区間少ないルートも成立する。
6+4-2 = 8区間

8区間がこの路線図での完乗ルートの最短区間数ということになる。
つまり、作成したルートが8区間未満なら、その路線を評価(所要時間の計算や比較)をする必要が無い。

他のケースでも同様。
東山線と名城線(環状線)だと路線は次のようになる。

この2路線は5区間で構成されていて、2ヵ所で交差していて乗換えができる。

終端駅は東山線に2駅だけで、名城線には無い。

よって、5+2-2=5で、最低5区間でルートが成立。

この路線図での完乗ルートの最短区間数は5区間。


プログラムを改善
最短区間数に満たないルートを評価の対象外にするようにプログラムを改善。

改善前、3路線(東山線、桜通線、名城線)

改善後、3路線(東山線、桜通線、名城線)

計算結果は同じ。
計算時間は、改善前が218.1秒、改善後が217.9秒。
改善効果はわずか0.1%弱。

最短区間数に満たないルートを評価の対象外にしたことによるコストの減少と、評価の対象にするかどうかの判断を行うコストがほとんど変わらないということなんだろうか。
それとも、プログラムの改善方法に問題があるのだろうか。


残念ながら、この改善の効果はほとんど無かった。

つづく。