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

前回はさっぽろ駅スタートの場合と新さっぽろ駅スタートの場合で最短完乗ルートの検索を行なった。
結果は、さっぽろ駅スタートの所要時間が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%弱。

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


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

つづく。

全6路線の最短完乗ルートの検索に向けて

前回の計算で、5路線、東山線、名城線、名港線、鶴舞線、上飯田線の最短完乗ルートの計算に約45分掛かった。

目標は名古屋市営地下鉄の全6路線の最短完乗ルートの検索。

上記の5路線に桜通線を加えるだけだけど、プログラムを動かすといつまでたっても計算が終わらない。

どこのくら時間が掛かるのかを予想してみることにした。

今のプログラムで何とか5路線までは計算できる。

4路線、東山線、名城線、名港線、上飯田線と、これに桜通線を加えた5路線で計算時間とルート数を比較。

4路線、東山線、名城線、名港線、上飯田線

５路線、東山線、名城線、名港線、上飯田線

計算時間と検索ルート数は次の通り。

4路線に桜通線を加えることで、計算時間は約4800倍、検索ルート数は約3000倍以上になっている。

同じ5路線でも鶴舞線を桜通線に変えただけで計算時間が45分から200分、4.4倍になった。
区間数が、鶴舞線の6区間に対して、桜通線は7区間で1区間多いためと思われる。
1区間増えるとそこでの分岐が1回増えるので、他路線との交差の場合は単純計算で4倍。
4.4倍というのは妥当なところと言えそう。

前回の桜通線を除く5路線での計算時間は約45分(2707.3秒)、ルート数は230万(2,304,666)だった。
これに、桜通線を加えるには上記の比率、計算時間は4800倍、ルート数は3000倍する。

全6路線の計算時間は計算時間は21.6万分(=150日)、計算ルート数は69億と予想できる。
名古屋市営地下鉄の全6路線の最短完乗ルートの検索は、今のプログラムではまだまだ無理そう。


つづく。

改善：ルートを削減～引き換えしルートを検索しない～その2

先日の改善版プログラム。

東山線、名城線、名港線、鶴舞線の4路線を10分弱で計算したけど、ちょっと時間を掛けて5路線のルート計算をしてみることにした。

桜通線を加えるのは無理そうなので、東山線、名城線、名港線、 鶴舞線、上飯田線の5路線で計算。

計算時間は2707.3秒。
45分で最短完乗ルートが計算できた。

検索ルート数は、4路線(東山線、名城線、名港線、 鶴舞線)の時は 529,845(53万)だったけど、5路線だと 2,304,666(230万)にもなている。
上飯田線って1区間だけで、名城線の平安通駅から分岐してるので行って戻るだけなんだけど。
検索ルート数は実に約4.3倍。

最短完乗ルートの所要時間は、4路線が245分で5路線が277分だからその差は32分。
上飯田線は平安通駅から分岐して戻るので、乗車時間が往復で2分、折り返しが1回で10分、乗換が2回で20分で合計32分。
合ってる。

何とか5路線まで計算できたけど、桜通線を加えて全6路線の計算をするためには、もう一工夫必要かな。


つづく。

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

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

• 同じ駅間(セグメント)を通るのは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路線以上は無理そう。

つづく。

改善：繰り返し行なう処理の効率化～何度も同じことを行なわない

3路線(東山線、名城線、名港線)まで、最短完乗ルートの計算ができるようになったけど、4路線は1時間経っても終わらない。


前回の改善ではルート作成のルールを追加。
今回は処理の効率化。
何度も繰り返される処理を効率化することで、処理速度をアップさせようという改善。

改善点は完成チェックと重複チェックの高速化。
具体的には、前のバージョンではチェックの都度行っていたセグメント数のカウントをルート作成と同時に行なうようにする。
処理が複雑になるのでバグが入らないように慎重にプログラムを改善。


3路線(東山線、名城線、名港線)での計算結果は次の通り。
まずは改善前。

次に改善後。

計算結果は同じ。
計算ルート数(intMakeRrouteNum)は 17623 で同じだけど、処理時間が、18秒から11.3秒に改善されている。
改善効果は約1.6倍。

更に4路線(東山線、名城線、名港線、鶴舞線)で試してみた。
なかなか終わらない。
この程度の改善では無理なのかな。


4路線を、東山線、名城線、名港線、上飯田線にして試してみた。
まずは改善前。

続いて改善後。

計算結果は同じで、検索ルート数も 75669 で同じ。
計算時間は、改善前の130.8秒から84.5秒、約1.5倍に改善。


全6路線はまだまだ遠い。

つづく。

どうすれば速くなるのか

処理が遅くて、目標の名古屋市営地下鉄の全６路線の最短完乗ルート検索になかなかたどり着けない。

前にも書いたけど、処理(=計算)を早くするには、

• 速いPCを使う
• VBScriptのプログラムをC/C++などで作り直す
• アルゴリズムを改善する

などが考えられる。

速いPC、これは確実に効果があるはず。
今使ってるPCは少し前のネットブックで、CPUはAtom N270(1.6GHｚ）、メモリは1GBでかなり非力。

最新のPCを使えば確実に速くなるはず。
でも、せいぜい数倍なんじゃないかな。
1日かかってやっと終わるプログラムがあったとして、例えば5倍速くなっても5時間くらいかかる。

今回使っているのはVBScript。
コンピュータに詳しい方なら判っていると思うけど、。
これで速さを求めるのは無理というか目的が違う。
最初に決めたけど、まずはアルゴリズムを確立したいので、それまでは使いやすいVBScriptで行くことにする。
どこかで、C/C++などで書き換える予定。
これだけでおそらく、数十倍～数百倍に速度アップされるんじゃないかな。

ということで、暫くはアルゴリズムの改善に注力。
実際、余分なルートを作らないというアルゴリズムの改善で8倍以上に速度アップしている。
どこまで行けるか判らないけど、まだまだ改善の余地は充分にあるはず。


つづく

改善：ルートが判らない

名古屋市営地下鉄の名城線は環状で、右回りと左回りで運転されている。

ルート検索結果の表示。

名城線のルートがどちらなのか判らないことに気が付いた。

例えば、藤が丘駅スタートで東山線と名城線の2路線。

本山～本山って。
この場合は1周なので、どちらでもいいんだけど。

藤が丘駅スタートで、東山線、名城線、名港線の3路線の場合。

栄～金山は左回りなんだろうか、それとも右回りなんだろうか。
この結果で完乗しているということは、左回りで栄～金山～新瑞橋を回って栄を通り過ぎて金山ってことかな。
右回りだと栄～金山の間を通らないので。


表示を改善
もう少し詳しく表示するようにした。
藤が丘駅スタートで、東山線、名城線、名港線の3路線の場合。

検索結果はまったく同じ。
単純にすべてのセグメント(区間)を表示するようにしただけなのでちょっと見辛いけど、ルートは判るようになった。
名城線の栄～金山は、栄から名城線左回りに乗って1周して、更に栄を超えて金山まで行くルートだった。


つづく

改善：余分なルートを作らない

検索を早くするにはいくつかの方法が考えられる。

• 処理を効率化する
• 評価対象のルート数を減らす

もちろん、速いPCを使うとか、C/C++などで書き直すというのも高速化には有効だけど、C/C++はアルゴリズムが固まってからStep2で行うことにしているので今回はなし。
速いPCを使うのは当然効果があるけど、速いと言っても普通に手に入るPCであれば、せいぜい数倍。
アルゴリズムを見直すのが高速化の効果が高い。

ではどうするのか。
ルートを作るルールを1つ追加することにした。

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

作ったルートの所要時間がそれまで求めた完乗ルートの所要時間を上回ったら、ルートが完成していなくてもそれ以降のルートは作らないようにする。
未完成のルートの所要時間を求める(ルートを評価する)ので、そのコスト(処理時間)が余分に掛かるが、せっかく完乗ルートができても所要時間が最短でなければ意味がないので。
評価対象のルートを大幅に減らせるはず。

試してみた。
藤が丘駅スタートで、東山線、名城線、名港線の3路線でルート検索。

左が旧バージョン、右が新バージョン

評価回数(intRouteNumMax)は、228,983回から17,623回に大幅に削減された。(元の7.7%)
処理時間も152.4秒が18.5秒に短縮。(元の12.1%)
当然、結果は同じ。

旧バージョンではできなかった、東山線、名城線、名港線、鶴舞線の4路線を試してみた。
1時間経っても終わらない。
まだまだ先は長い。


つづく

できたけど遅い

実際にプログラムを作って動かしてみたけど遅い。
と言うより、ぜんぜん終わらない。

一気に全6路線ではなく、1路線から順に路線を増やして試してみた。
スタート駅は藤が丘駅(最寄の終端駅)と名古屋駅の2パターン。

藤が丘や高畑のような終端の駅からスタートすれば、折り返しが1回少なくなるので名古屋駅のような中間駅からスタートするよりも所要時間が短くなるはず。

プログラムを少し機能アップして、計算結果(検索したルート)をファイルに書き出すようにした。
処理時間も表示できるようにした。

1路線：東山線

あっという間に完了。

2路線：東山線、名城線

1分程度なら問題なし。

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

ちょっと時間が掛かったけど許容範囲。

4路線：東山線、名城線、名港線、鶴舞線
1時間くらい計算しても終わらない。
中断。


数分から1時間程度で計算するのが目標。
長くても一晩くらいが限界。
4路線なら一晩動かせば結果がでそうだけど、目標の全6路線は今のプログラムでは無理そう。
さて、どうやって進めよう。

つづく。

どうやって計算すればいいのか～ルート計算のアルゴリズム

最短完乗ルートの検索。
まずは力まかせ探索で完乗ルートを順番につくり、乗車時間を計算(評価)。
乗車時間が最短のルートを求める。

完乗ルートを作るためには、

1. スタート駅を決める
2. 行き先を1つ決める
3. 分岐駅にきたら、分岐先を順番に試す
4. 全線乗車(すべての駅間=セグメント)を1回以上通過するルートができたら1ルート完成
5. すべてのルートを試す

実際にプログラムを書いて動かしてみるとルートがまったくできない。
例えば藤が丘をスタートすると、

• 本山駅まで進む
• 藤が丘駅に進む
• 本山駅に進む
• ：
• ：

を繰り返してしまう。

そこで、以下のルールを追加。
同じ駅間(セグメント)は2回までしか通らない
つまり、

• 藤が丘から本山まで進む
• 本山から藤が丘まで進む
• 藤が丘から本山まで進む → 藤が丘～本山間を3回通ったので1つ戻って次
• 本山に戻る
• 今池まで進む .... 藤が丘へのルートの検索は終わったので本山から次の駅間に進む

やってみた。
ルートはできたけど、検索が終わらない。
例えば、名古屋市営地下鉄全6路線を藤が丘駅スタートの場合、こんなルートが検索された。

他にもたくさんあるけど、とても最短ルートとは思えない。
数時間動かしても終わらない。


つづく。