ルート計算プログラムをどうやって作ろう～プログラム言語

必要なデータを揃えたので、次はプログラム作り。
さて、どうやって作ろうか。

• C/C++
• Visual Basic
• C#
• Java

などが定番か。

• VBScript
• Perl
• Ruby

などのスクリプト言語は手軽でいい。

• Excel/VBA

なら、Excelのシートで入力データの定義をして、結果もExcelのシートに書き出せる。
Excelって、表計算や資料作りでは広く使われてるし、個人でも(自宅で)使っている人も多いと思うけど、セルに計算式、関数などを使っている人は多くても、VBAでプログラムを作ってる人って意外と少ないみたい。
手軽だし、エディタ、デバッガなどが一通り揃った統合開発環境としてもお勧め。
ボタンや入力ボックスを自由に配置してフォームを作ることもできる。
Excelの表計算機能を使わなくても、開発環境、プログラム環境としてもお勧め。
今回は本題から外れるので、これはまたの機会に。

などを踏まえつつ...
次のような観点で検討。

• 最短完乗ルートの検索プログラムでは、試行錯誤を繰り返すと思われるので、アルゴリズムを手軽に試すことができる方がいい
• 最短完乗ルートは、おそらくは膨大な(数百万?、数千万?、数億?)のルートを作り、評価して最短のものを探すことになるので実行速度も重要

次の2段階でプログラム作りをすることにする。

Step1 最短完乗ルート検索アルゴリズムの確立
Step2 処理の高速化

ということで、Step1はVBScript、Step2はC/C++を使うことにする。

Step1でVBScriptを使うメリット
何と言ってもお手軽。
言語仕様で厳密な変数型の定義を必要とせず、アルゴリズムの検証など、ロジック部分に集中できる。

他のスクリプト言語でもいいが、エディタ(メモ帳でも)さえあれば動かせる手軽さは大きい。
デメリットは、遅いことか。

Step2でC/C++を使うことのメリット
アルゴリズムがある程度固まったら、C/C++に書き換えて高速化。
どのくらいの効果があるかは試してみる必要があるが、おそらく、同じロジックで1桁～2桁以上の高速化ができると思われる。

つづく。

ルート計算の元データ（路線データ、時間データ）を作ってみた

実際に名古屋の地下鉄で、ルート計算の元データを作ってみた。

■ 路線 ■
(1) 東山線
(2) 名城線
(3) 名港線
(4) 鶴舞線
(5) 桜通線
(6) 上飯田線

■ 駅 ■
(1) 高畑、伏見、名古屋、栄、今池、本山、藤が丘
(2) 金山、新瑞橋、八事、本山、平安通、久屋大通、栄、上前津
(3) 金山、名古屋港
(4) 上小田井、丸の内、伏見、上前津、御器所、八事、赤池
(5) 中村区役所、名古屋、丸の内、久屋大通、今池、御器所、新瑞橋、徳重
(6) 平安通、上飯田
駅は終端と乗換え駅のみ。
途中の駅は今回は省略。

■ 乗車時間 ■
(1-1) 東山線：高畑～名古屋、12分
(1-2) 東山線：名古屋～伏見、3分
(1-3) 東山線：伏見～栄、2分
(1-4) 東山線：栄～今池、6分(1-5) 東山線：今池～本山、5分
(1-6) 東山線：本山～藤が丘、12分
(2-1) 名城線：金山～新瑞橋、11分
(2-2) 名城線：新瑞橋～八事、7分 (2-3) 名城線：八事～本山、6分(2-4) 名城線：本山～平安通、11分
(2-5) 名城線：平安通～久屋大通、8分
(2-6) 名城線：久屋大通～栄、1分
(2-7) 名城線：栄～上前津、3分(2-8) 名城線：上前津～金山、4分
(3-1) 名港線：金山～名古屋港、10分
(4-1) 鶴舞線：上小田井～丸の内、10分(4-2) 鶴舞線：丸の内～伏見、1分 (4-3) 鶴舞線：伏見～上前津、3分
(4-4) 鶴舞線：上前津～御器所、6分 (4-5) 鶴舞線：御器所～八事、5分
(4-6) 鶴舞線：八事～赤池、9分 (5-1) 桜通線：中村区役所～名古屋、2分 (5-2) 桜通線：名古屋～丸の内、3分
(5-3) 桜通線：丸の内～久屋大通、2分 (5-4) 桜通線：久屋大通～今池、6分 (5-5) 桜通線：今池～御器所、4分 (5-6) 桜通線：御器所～新瑞橋、6分 (5-7) 桜通線：新瑞橋～徳重、15分 (6-1) 上飯田線：平安通～上飯田、1分

■ 乗換時間 ■
電車を降りて別の路線に乗り換える時間。
今回はすべて10(分)とする。
駅別、路線別の違いは今回は考えない。

名古屋の地下鉄では、名城線(環状運転)で途中で別の列車に乗り換える必要があるケースがあるが、今回は考慮しない。(右回りの大曽根行きなど)
複数路線を直通運転するケースも考慮しない。(名港線～名城線)
同じ路線ではどこまで乗っても乗換え時間は0(分)とする。

■ 折返時間 ■
終点に到着した後、同じ路線を戻るときの時間。
今回はすべて10(分)とする。


これだけのデータがあれば計算できるはず。
次はいよいよプログラム作り。

つづく。

ルート計算の元データ（路線データ、時間データ）

最短完乗ルートを求めるプログラムを作るとして、プログラムに与えるデータが必要。
(1) 路線図
(2) 乗車時間(移動時間)のデータ
(3) 乗換え時間、折り返し時間のデータ

まずは路線図。

どんな路線があって、他の路線とどんな関係になっているのか。
これは事業者のサイトなどで簡単に入手できる。
http://www.kotsu.city.nagoya.jp/subway/sub_route.html
駅にもあるし、電車の車内にもある。

次に乗車時間のデータ。
どこからどこまで何分掛かるか。
時刻表とか、乗換え案内とかの経路検索のサイトで調べることができる。
YAHOO! 路線情報 ( http://transit.loco.yahoo.co.jp/ )
ジョルダン 乗換案内 ( http://www.jorudan.co.jp/ )
Googleマップ ルート・乗換案内 ( http://maps.google.co.jp/maps?hl=ja&tab=wl )
なごや乗換ナビ/名古屋市交通局 ( http://kotsuk.city.nagoya.jp/route/web/exp.cgi )

列車によって同じ駅間でも乗車時間が異なったり、普通列車と優等列車(特急とか)でも違う。
幸い、今回対象にしている名古屋の地下鉄はすべて普通電車(各駅停車)なのでこの点はクリア。
乗る列車による差異はそれほど大きくないと考えて今は考えないことにする。

最後に乗換え時間、折り返し時間のデータ。
別の路線に乗り換えるのに何分掛かるか?
ホームからホームまでの移動時間は実測するしかないのかもしれない。
経路検索のサイトで調べると、乗換え時間が表示されるので目安にはなるかも。
問題は、列車を降りて別の路線のホームに移動したらすぐに次の列車に乗れるという訳ではないこと。
時間帯(朝晩の通勤時間と日中、平日と休日)による違いもある。
今回はあまり厳密には考えず、大雑把に例えば 平均10分 とかでいいかも。
終点駅まで行って折り返す場合も同じ。

これで必要なデータは揃えられる。


つづく。

ルート検索はプログラムを作って

名古屋市営地下鉄の全6路線の完乗。
最短ルートはどうしたら調べられるか。

1. 路線図と時刻表を見て考える
2. 路線検索サイトで調べる
3. ルート検索プログラムを作って調べる

2路線、3路線なら路線図と時刻表を見て最短ルートを見つけることができるかもしれない。
でも、6路線もあると組合せが複雑過ぎて無理。

路線検索サイトで調べるためには、経路を決めないといけない。
その経路が知りたいのだから無理。
経路を決めても、通常、経由地は1ヵ所なので複雑な経路は検索はできない。

やはり、ルート検索用にプログラムを作らないと調べられない。
ちょっと調べてみたけど、こういったことをしている人は見つけられなかった。

プログラムを作って最短完乗ルートを調べるのに必要なものは2つ。
(1) 路線データ、時間データ
(2) 検索プログラム(アルゴリズム)

つづく。

ドニチエコきっぷ

ドニチエコきっぷは名古屋市交通局の地下鉄と市バスで使える1日乗車券。

使える日が、

• 土曜日
• 日曜日
• 休日
• 毎月8日

に限られるが、600円で1日乗り放題はお得。

地下鉄は200円の1区から320円の5区までの運賃なので、320円区間の往復で640円。
http://www.kotsu.city.nagoya.jp/subway/sub_price/sub_ticketprice.html
320円区間に乗るなら迷わず購入。
230円の2区から290円の4区でも、途中下車が1回でもあればドニチエコきっぷがお徳。
市バスは市内均一料金で1乗車200円だから、3回乗れば元が取れる。

こども用は半額の300円。
こども料金は大人の半額で端数切上げなので290円区間は150円、往復300円。
290円の4区、320円の5区なら、こどもは迷わずドニチエコきっぷ。

地下鉄も市バスもICカードのmanacaだとマイレージポイントが付くけど、1ヵ月間に一定金額以上の利用が無いと割引されないので、休みの日に乗るだけなら断然、ドニチエコきっぷがお得。

地下鉄6路線全線乗車でも大活躍。

名古屋市交通局の1日乗車券は他に、

• バス・地下鉄全線一日乗車券(大人850円、こども430円)
• バス全線一日乗車券(大人600円、こども300円)
• 地下鉄全線一日乗車券(大人740円、こども370円)

もあるので平日以外もたくさん乗るときはお得。
http://www.kotsu.city.nagoya.jp/ticket/oneday.html

ドニチエコきっぷはmanaca対応の黄色い券売機でも買える。
でも、その場合は汎用のカードに印字しただけの味気ないカードに。

冒頭のデザインのカードは、専用券売機か窓口、駅長室で購入。

地下鉄全線乗車

名古屋市営地下鉄の6路線をすべて乗るのにどのくらいの時間が掛かるのか。

1路線の端から端まで1時間掛かるとすると、単純計算で6時間。
一筆書きはできないので乗換え時間や重複乗車の時間で2割り増し(根拠なし)と想定するとプラス1.2時間で合計7.2時間。

どんなルートが一番効率がいいのか判らないけど、まずは実際にやってみた。

地下鉄と市バスが1日乗り放題のドニチエコきっぷを買って、まずは東山線の東の終端駅、藤が丘駅へ。

ドニチエコきっぷは土曜日と日曜日、休日、まるはちの日(毎月8日)限定で乗り放題600円の切符。

朝10時に藤が丘駅に到着。

• 本山駅で名城線左回りに乗換え
• 平安通駅で上飯田線に乗り換え、1区間だけで上飯田駅で折り返し再び平安通駅
• 名古屋港行きが来たので一気に名古屋港まで
• 名古屋港駅で乗ってきた電車でそのまま名港線を引き返し、上前津駅で鶴舞線に乗換え
• 上小田井駅まで行き、引き返して豊田市行きに乗車
• 地下鉄の終点の赤池駅(ここから先は名鉄豊田線)で降りて、駅前でお昼ご飯
• 八事駅で名城線左回りにのり新瑞橋駅へ
• 桜通線を引き返し、終点の中村区役所駅まで
• 中村区役所駅からは市バスで本陣駅へ
• 本陣駅から東山線で高畑駅まで
• 高畑駅から東山線で本山駅まで
• 本山駅で名城線右回りに乗り八事駅、新瑞橋駅を通過して金山を通過

これで全線乗車。

金山駅を通過したのが18時半前なので、10時から約8時間半。
出発前の見込み時間より1時間ちょっと多く掛かっているけど、お昼ご飯を食べたり外に出て休憩したりしているので、実際の乗車時間は7時間くらいかな。

今回は市バスも使ったけど、地下鉄だけだともう少し時間が掛かったかもしれない。

最も効率がいいルートだとどのくらいで全線乗車できるんだろう?
ということで、全線乗車最短ルートを考えることにした。

• 名古屋市営地下鉄全線(6路線)に乗車
• スタート駅、ゴール駅はどこでもよい
• 同じ路線に何度乗ってもよい(一筆書きは不可能なので)
• 乗車時間が最短のルートを最短ルートとする

というルールで。

最短ルートが分かったら、実際に乗って確かめる。
でも、最短ルートってどうやって調べればいいんだろう?

ブログ説明

名古屋の地下鉄は全部で6路線あります。 
すべての路線を乗るとどのくらいの時間が掛かるのか。 

「ある交通機関が営業する路線にすべて乗車・搭乗すること」を「完全乗車」、略して「完乗(かんじょう)」と言うらしい。

• もっとも効率よく完乗する経路(完乗ルート)は?
• その経路でどのくらいの時間が掛かるのか?

そんな疑問を解決するために試行錯誤を始めた。
地下鉄最短完乗～試行錯誤。
名古屋市営地下鉄全6路線の最短完乗ルートは見付かるのか。