改善：ルートを削減 ～ 引き返しルートを検索しない

今回はルールを追加して、余分な検索を行わないようにしてみた。

• 同じ駅間(セグメント)を通るのは2回まで
• 所要時間がそれまでの最短時間を上回ったら、それ以降のルートは検索しない
• 《追加》 引き返しルートを検索しないようにする(終点を除く)

東山線、名城線、名港線、上飯田線の4路線で確認。

まずは改善前。

続いて改善後。

改善前が55.2(秒)(あれ?、前回よりも早くなってる)で、改善後は何と2.5(秒)。
なんと、22倍に高速化。

検索された最短完乗ルートはまったく同じ。
検索ルート数は、75669から3174に激減。
約24分の1になっている。
ルールを追加してルート数を減らした効果が出ている。

東山線、名城線、名港線の3路線の最短完乗ルートは、所要時間155分、乗車時間125分だった。
上飯田線は1区間で移動時間は1分なので、移動時間が2分、折り返し1回で10分、乗換え2回で20分。
合計、32分追加になるはず。

上記の計算結果、東山線、名城線、名港線、上飯田線の4路線は、
所要時間187分、乗車時間127分なので、きちんと32分、2分増えてる。
結果は合ってそう。


今度は4路線を、東山線、名城線、名港線、鶴舞線で計算。
改善前は計算が終わらなくて諦めたけど、改善後は計算結果が出た。

 

計算時間は575.4(秒)、10分弱。
検索ルート数は 529845 で、東山線、名城線、名港線、上飯田線の4路線から167倍に増えている。
このプログラムでは5路線以上は無理そう。

つづく。