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

名古屋市営地下鉄の全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になった。


つづく。