名古屋駅スタートで全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になった。


つづく。