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

前回の改善、「最短所要時間予測により検索ルート削減」により検索ルート数を削減することができ、計算時間を短縮できたが、それでもまだ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ルートでこれも僅かに増えている。

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


つづく。