経路検索サーバおよび経路検索プログラム
【課題】出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する。
【解決手段】条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段３１と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段３２と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段３３とを備える。
【解決手段】条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段３１と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段３２と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段３３とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバおよび経路検索プログラムに関する。
【背景技術】
【０００２】
近年の情報通信の技術に伴い、インターネット等の通信ネットワークを介して、様々な情報が提供されている。その一つに、交通機関の乗換情報がある。乗換情報とは、ユーザが出発地と、目的地と、目的地の到着を希望する時刻等を入力することにより、どの交通機関の何時の電車に乗り、どの駅で乗り換えるか、等の電車の乗換情報を提供するものである。経路検索サービスにおいては、ユーザに最適な乗換情報を提供できる方法が提案されており、その一つに、所定の区間の終電を案内するサービスがある。終電案内サービスは、例えば、仕事や所用で遅くなる場合に予め終電を検索する際に用いられる。
【０００３】
終電案内サービスはユーザが入力した出発地および目的地間の終電を案内するものであるが、終電に間に合わない場合の案内サービスもある（例えば、特許文献１参照。）特許文献１等に記載の方法においては、終電時間内に利用することができる目的地に最も近い駅の情報をユーザに提供する。この際、特許文献１に記載の方法では、ユーザの現在位置の位置情報に基づいて、ユーザの位置情報に対して最寄りかつ終電時間内に利用可能な出発駅と、ユーザの住所に対して最寄りかつ終電時間内に利用可能な位置を検索する（特許文献１の段落番号［００２０］等参照）。ここで、特許文献１に記載の方法では、ユーザの位置情報を元に、駅の緯度経度情報に基づいて最寄り駅を検索する（特許文献１の段落番号［００３２］および［００３３］等参照）。
【特許文献１】特開２００６−１１５４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の特許文献１に記載の方法では、位置情報を取得する装置を有しないパーソナルコンピュータ等を用いて検索する際には適切ではない。また、位置情報に基づいて出発地および目的地を検索するため、通常の使いなれていないルートが検索される場合があり、一刻を争う終電後の乗換案内には不向きな場合がある。
【０００５】
このように、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することが期待されている。
【０００６】
従って本発明の目的は、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の第１の特徴は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバに関する。即ち本発明の第１の特徴に係る経路検索サーバは、交通機関の経路と、経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、乗換の条件を取得する条件取得手段と、記憶装置から経路データを読み出し、条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段と、移動データを出力する結果提示手段とを備える。
【０００８】
ここで、交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、記憶装置に記憶するタクシー料金データ記憶手段と、記憶装置からタクシー料金データを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出するタクシー料金算出手段をさらに備え、移動データは、タクシー料金算出手段によって算出されたタクシー料金を含んでも良い。
【０００９】
また、平均経路検索手段はさらに、経路上の駅間の距離を記憶し、平均経路検索手段が複数の平均経路データを算出した場合、終電後列車割当手段は、平均経路検索手段が算出したすべての平均経路データについて乗換データおよび日越え駅を算出し、目的地との距離が最も小さい日越え駅を終電後列車到着駅としても良い。
【００１０】
また、終電後列車割当手段は、さらに、第２の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、出発地から新たな終電後列車到着駅までの交通機関の終電となる第３の終電データを算出し、第３の終電データを含む新たな移動データを算出しても良い。
【００１１】
また、終電後列車割当手段は、新たな終電後列車到着駅が出発地になるまで、新たな移動データを算出する処理を繰り返しても良い。
【００１２】
また、タクシー料金算出手段はさらに、新たな終電後列車到着駅と目的地との新たなタクシー料金を算出し、新たな移動データは、タクシー料金算出手段によって算出された新たなタクシー料金を含んでも良い。
【００１３】
本発明の第２の特徴は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索プログラムに関する。即ち本発明の第２の特徴に係る経路検索プログラムは、交通機関の経路と、経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、乗換の条件を取得する条件取得手段と、記憶装置から経路データを読み出し、条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段と、移動データを出力する結果提示手段とを、コンピュータに機能させる。
【００１４】
ここで、交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、記憶装置に記憶するタクシー料金データ記憶手段と、記憶装置からタクシー料金データを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出するタクシー料金算出手段をさらにコンピュータに機能させ、移動データは、タクシー料金算出手段によって算出されたタクシー料金を含んでも良い。
【００１５】
また、平均経路検索手段はさらに、経路上の駅間の距離を記憶し、平均経路検索手段が複数の平均経路データを算出した場合、終電後列車割当手段は、平均経路検索手段が算出したすべての平均経路データについて乗換データおよび日越え駅を算出し、目的地との距離が最も小さい日越え駅を終電後列車到着駅としてもよい。
【００１６】
また、終電後列車割当手段は、さらに、第２の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、出発地から新たな終電後列車到着駅までの交通機関の終電となる第３の終電データを算出し、第３の終電データを含む新たな移動データを算出しても良い。
【００１７】
また、終電後列車割当手段は、新たな終電後列車到着駅が出発地になるまで、新たな移動データを算出する処理を繰り返しても良い。
【００１８】
また、タクシー料金算出手段はさらに、新たな終電後列車到着駅と目的地との新たなタクシー料金を算出し、新たな移動データは、タクシー料金算出手段によって算出された新たなタクシー料金を含んでも良い。
【発明の効果】
【００１９】
本発明によれば、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することができる。
【発明を実施するための最良の形態】
【００２０】
つぎに、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一または類似の部分には同一または類似の符号を付している。
【００２１】
本発明の最良の実施の形態において「終電」とは、出発地から目的地までの所定区間の交通機関の乗換データのうち、各交通機関で当日扱いとなる最終の乗換データのことを指す。具体的には、ある交通機関の駅で９月５日午前２時に到着する列車が最終の列車であっても、その列車に９月４日発売の切符で乗車できる場合、９月４日の終電として検索される。
【００２２】
「終電後列車」とは、所定区間の終電データに基づいて、終電データにおける出発地の出発時刻の単位時間後に出発する列車であって、目的地までの途中駅まで到着する列車のことを指す。
【００２３】
「単位時間」とは、経路検索サーバ１に記憶された時刻表データ２３ａの最小時間単位である。例えば、時刻表データ２３ａが１分単位で作成されている場合、単位時間は１分となる。同様に、時刻表データ２３が１０秒単位で作成されている場合、単位時間は１０秒となる。本発明の最良の実施の形態においては、時刻表データ２３ａが１分単位で作成されており、単位時間が１分の場合について説明する。
【００２４】
（最良の実施の形態）
本発明の最良の実施の形態に係る経路検索システムは、経路検索サーバ１、クライアント端末２ａ等を備えている。経路検索サーバ１とクライアント端末２ａ等は、インターネット等の通信ネットワーク３によって、相互に接続されている。
【００２５】
経路検索サーバ１は、所定の条件で、出発地から目的地までの交通機関の乗換を検索した結果である乗換データを出力する。経路検索サーバ１は、クライアント端末２ａ等から条件を受信し、その条件に従って出発地から目的地までの交通機関の乗換を検索し、その結果である乗換データを、条件を入力したクライアント端末２ａ等の表示画面に表示する。
【００２６】
ここで所定の条件とは、クライアント端末２ａ等から、ユーザの操作によって入力される。所定の条件は具体的には、出発地、目的地、出発地を出発する時刻を指定した出発希望時刻、目的地に到着する時刻を指定した到着希望時刻が挙げられる。出発地および目的地は、電車の駅やバスの停留所など交通機関の乗車下車できる地点である。さらに所定の条件は、複数の乗換データからユーザのニーズにあった条件を優先するために、所要時間優先、乗換回数優先、運賃優先、今来る列車に乗ることを優先する今来る列車優先、等が挙げられる。
【００２７】
本発明の最良の実施の形態に係る経路検索サーバ１は特に、終電後の移動データを適切に出力する。従って、所定の条件として、出発地および目的地の他に、終電や終電後列車を検索する旨の指示が含まれる。
【００２８】
クライアント端末２ａは、一般的にＣＰＵ、記憶装置、入力装置および表示装置等を備える電子機器である。クライアント端末２ａにはブラウザなどの所定のソフトウェアなどがインストールされている。このソフトウェアは、経路検索サーバ１に送信する所定条件の入力や、経路検索サーバ１から送信された検索結果の出力等を支援する。クライアント端末２ｂおよびクライアント端末２ｃも、クライアント端末２ａと同様の構成を備える。
【００２９】
図２に示すように、本発明の最良の実施の形態に係る経路検索サーバ１は、中央処理制御装置１０１、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３および入出力インタフェース１０９が、バス１１０を介して接続されている。入出力インタフェース１０９には、入力装置１０４、表示装置１０５、通信制御装置１０６、記憶装置１０７およびリムーバブルディスク１０８が接続されている。
【００３０】
中央処理制御装置１０１は、入力装置１０４からの入力信号に基づいてＲＯＭ１０２から経路検索サーバ１を起動するためのブートプログラムを読み出して実行し、さらに記憶装置１０７に記憶されたオペレーティングシステムを読み出す。さらに中央処理制御装置１０１は、入力装置１０４や通信制御装置１０６などの入力信号に基づいて、各種装置の制御を行ったり、ＲＡＭ１０３や記憶装置１０７などに記憶されたプログラムおよびデータを読み出してＲＡＭ１０３にロードするとともに、ＲＡＭ１０３から読み出されたプログラムのコマンドに基づいて、データの計算または加工など、後述する一連の処理を実現する処理装置である。
【００３１】
入力装置１０４は、操作者が各種の操作を入力するキーボード、マウスなどの入力デバイスにより構成されており、操作者の操作に基づいて入力信号を作成し、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送信される。表示装置１０５は、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどであり、中央処理制御装置１０１からバス１１０および入出力インタフェース１０９を介して表示装置１０５において表示させる出力信号を受信し、例えば中央処理制御装置１０１の処理結果などを表示する装置である。通信制御装置１０６は、ＬＡＮカードやモデムなどの装置であり、経路検索サーバ１をインターネットやＬＡＮなどの通信ネットワークに接続する装置である。通信制御装置１０６を介して通信ネットワークと送受信したデータは入力信号または出力信号として、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送受信される。
【００３２】
記憶装置１０７は半導体記憶装置や磁気ディスク装置であって、中央処理制御装置１０１で実行されるプログラムやデータが記憶されている。リムーバブルディスク１０８は、光ディスクやフレキシブルディスクのことであり、ディスクドライブによって読み書きされた信号は、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送受信される。
【００３３】
本発明の最良の実施の形態に係る経路検索サーバ１の記憶装置１０７には、経路検索プログラムが記憶されるとともに、検索条件データ記憶部２１、経路データ記憶部２２、時刻表データ記憶部２３、運賃データ記憶部２４、タクシー料金データ記憶部２５および結果データ記憶部２６を備えている。また、経路検索プログラムが経路検索サーバ１の中央処理制御装置１０１に読み込まれ実行されることによって、条件取得手段１１、経路検索手段１２および結果提示手段１３が経路検索サーバ１に実装される。
【００３４】
検索条件データ記憶部２１は、クライアント端末２ａ等から受信した交通機関の乗換の検索条件データ２１ａが記憶された記憶部である。条件取得手段１１が、記憶装置１０７の検索条件データ記憶部２１に、検索条件データ２１ａを記憶する。検索条件データ２１ａは、出発地および目的地の識別子を含み、一般的に、出発地の出発希望時刻または到着地の到着希望時刻を含むデータである。特に本発明の最良の実施の形態において検索条件は、出発地および目的地間の交通機関の終電や、終電後列車を案内する旨が含まれる。さらに、検索条件データ２１ａに、検索結果を「所要時間」の短い順に出力するか等のソート条件も含まれる場合がある。
【００３５】
経路データ記憶部２２は、経路データ２２ａが記憶された記憶部である。経路データ記憶手段（図示せず）が、記憶装置１０７の経路データ記憶部２２に、経路データ２２ａを記憶する。経路データ２２ａは、交通機関の路線と、路線上に位置する駅と、経路上の駅間の距離と、を関連づけたデータである。経路上の駅間の距離は営業距離でも良いが、駅位置から算出される直線距離でも良い。直線距離の場合、後述する終電後列車の下車駅から目的地までタクシー等で移動する場合の基準とすることができる。
【００３６】
時刻表データ記憶部２３は、時刻表データ２３ａが記憶された記憶部である。時刻表データ記憶手段（図示せず）が、記憶装置１０７の時刻表データ記憶部２３に、時刻表データ２３ａを記憶する。時刻表データ２３ａは、交通機関の経路の列車の時刻表を関連づけたデータである。時刻表データ２３ａは、交通機関、経路の駅および電車種別毎に記憶されていることが好ましい。
【００３７】
運賃データ記憶部２４は、運賃データ２４ａが記憶された記憶部である。運賃データ記憶手段（図示せず）が、記憶装置１０７の運賃データ記憶部２２に、運賃データ２４ａを記憶する。運賃データ２４ａは、交通機関の経路と運賃を関連づけたデータである。運賃データ２４ａは、交通機関の距離毎に記憶されていることが好ましい。
【００３８】
タクシー料金データ記憶部２５は、タクシー料金データ２５ａが記憶された記憶部である。タクシー料金データ記憶手段（図示せず）が、記憶装置１０７のタクシー料金データ記憶部２５に、タクシー料金データ２５ａを記憶する。タクシー料金データ２５ａは、交通機関の各駅間についてタクシー料金が関連づけられている。また、別の実施例としては、タクシー料金を計算するために必要となる、初乗り運賃と初乗り運賃が適用される距離、さらに従量制の距離と料金の情報を記憶しても良い。この場合、後述するタクシー料金算出手段３５が、タクシーで移動となる距離を取得して、タクシー料金を算出しても良い。
【００３９】
経路データ２２ａ、時刻表データ２３ａ、運賃データ２４ａおよびタクシー料金データ２５ａは、一般的な経路検索サーバが有している情報で、経路検索が可能であれば、どのような構成を備えていても良い。
【００４０】
結果データ記憶部２６は、結果データ２６ａが記憶された記憶部である。経路検索手段１２が、記憶装置１０７の結果データ記憶部２６に、結果データ２６ａを記憶する。結果データ２５ａは、出発地から目的地までの終電後の列車であって、終電における出発地の出発時刻より単位時間後に出発地を出発し、終電後列車の到着駅までの乗換データを含む。さらに結果データ２５ａには、終電後列車到着駅から目的地までタクシーで移動する場合の所要時間、料金等が含まれても良い。
【００４１】
検索条件データ記憶部２１に記憶された検索条件データ２１ａおよび結果データ記憶部２５に記憶された結果データ２５ａは、本発明の最良の実施の形態に係る経路検索サーバ１の処理における一時データであるので、記憶装置１０７ではなく、ＲＡＭ１０３に記憶され、必要に応じて消去されても良い。
【００４２】
つぎに図３を参照して、本発明の最良の実施の形態に係る経路検索サーバ１の処理の概略を説明する。
【００４３】
まずクライアント端末２ａ等から検索条件が入力されると、ステップＳ１において、経路検索処理に先立って初期化する。具体的には、経路検索処理で使用される変数の初期化などが行われる。ここで検索条件とは、出発地、目的地、経由地等の経路を決定するための条件と、出発希望時刻、到着希望時刻、所用時間優先、乗換回数優先、運賃優先、今くる列車優先、ユーザに最適な経路を出力するための条件が含まれる。ここでは、出発地を「Ａ駅」、目的地を「Ｂ駅」として、出発地から目的地までの終電または終電後列車を求めるとの条件が入力されたとする。
【００４４】
つぎにステップＳ２ないしステップＳ６において、乗換データを算出する処理が行われる。具体的には、ステップＳ２において、Ａ駅からＢ駅までの平均経路データが検索される。ここで平均経路データとは、ユーザが入力した条件に適合する可能性のある経路データである。この平均経路データでは、出力する経路数以上の経路が出力される。つぎに、ステップＳ２で検索された平均経路のそれぞれについて、ステップＳ３において、列車の時刻表データ等を参照して、Ａ駅からＢ駅までの終電の列車を割り当てる。
【００４５】
つぎにステップＳ４において、ステップＳ３で検索した終電列車の出発地Ａ駅における出発時刻に単位時間を足した時間を算出し、時刻Ｔとする。さらにステップＳ５において、終電後の列車を割り当てる。具体的には、出発地Ａ駅をステップＳ４で算出した時刻Ｔに出発する列車を検索する。ステップＳ５で割り当てられる列車は、Ａ駅からＢ駅までの終電よりも後の列車になるので、Ａ駅から、Ａ駅とＢ駅の間のＣ駅までの終電の列車となる。ステップＳ６において、列車の運賃データ等を参照して、運賃を算出する。さらにステップＳ７において、タクシー料金が算出される。ここで算出されるタクシー料金は、Ｃ駅からＢ駅までのタクシー料金である。
【００４６】
ステップＳ２で算出された平均経路のすべて或いは一部について、ステップＳ３ないしステップＳ７の処理を繰り返す。ステップＳ２ないしステップＳ７で算出された結果は、結果データ２５ａとして記憶装置１０７に記憶される。
【００４７】
さらに、ステップＳ８において、結果データ２５ａのうち、ユーザが入力した検索条件に適合する乗換データを出力する。ここでは、ユーザが、「所要時間優先」で経路検索しているので、ステップＳ８において、所要時間が短いものから優先した乗換データが、クライアント端末２ａ等に出力される。ステップＳ８で出力される経路データは、一つでも良いし複数でも良い。
【００４８】
つぎに、図１を参照して、本発明の最良の実施の形態に係る経路探索サーバ１の各処理手段について詳述する。
【００４９】
条件取得手段１１は、乗換のための検索条件を取得する。条件取得手段１１は、クライアント端末２ａ等から通信ネットワーク４、通信制御装置１０６等を介して入力された検索条件データ２１ａを、検索条件データ記憶部２１に記憶する。この検索条件データ２１ａには、出発地、目的地、経由地等の経路を決定するための条件と、出発希望時刻、到着希望時刻、時間優先、乗換回数優先、運賃優先、今くる列車優先、ユーザに最適な経路を出力するための条件が含まれる。本発明の最良の実施の形態においては特に、検索条件データ２１ａとして終電または終電後列車を検索する旨が含まれる。また条件取得手段１１は、条件を取得すると、経路検索のための初期化処理をする。
【００５０】
経路検索手段１２は、記憶装置１０７から経路データ２２ａを読み出し、条件取得手段１１によって取得された検索条件データ２１ａに従って、乗換データを検索して出力する。ここで出力される乗換データは、ユーザが入力した出発地から目的地までの交通機関の終電後の列車に関する乗換のデータである。経路検索手段１２は、さらに、記憶装置１０７から時刻表データ２３ａを読み出し、出力された乗換データに交通機関の列車の時刻を割り当てて、交通機関の時刻と、当該乗換データにおける所要時間を出力する。経路検索手段１２は、さらに、出力された乗換データにおける乗換回数を出力する。経路検索手段１２は、さらに、記憶装置１０７から運賃データを読み出し、出力された乗換データの運賃を算出して出力する。乗換検索手段１２は、さらに、記憶装置１０７からタクシー料金データ２５ａを読み出し、終電後列車到着駅から目的地までのタクシーの料金や所要時間等も出力する。
【００５１】
図１に示すように経路検索手段１２はさらに、平均経路検索手段３１、終電列車割当手段３２、終電後列車割当手段３３、列車料金算出手段３４、タクシー料金算出手段３５および出力順序算出手段３６を備える。
【００５２】
平均経路探索手段３１は、記憶装置１０７から経路データ２２ａを読み出し、条件取得手段１１によって取得された条件に従って、平均経路データを検索して出力する。
【００５３】
本発明の実施の形態に係る経路検索手段１２の平均経路検索手段３１の経路検索方法について、まず、複数の「ノード」とノード間を接続する「アーク」からなるネットワークについて説明する。経路探索で用いるネットワークは、基本的には、駅を「ノード」とみなし、線路上で隣り合う駅間に「アーク」を設けて作成する。「アーク」には駅間の移動時間が付されており、これを「重み」という。この例として、Ｘ駅とＹ駅のネットワークを図４に示す。ここでは、Ｘ駅、Ｙ駅がノードとなり、記号Ａ、Ｂ、Ｃ、Ｄ、Ｅを付した実線で示す両端矢印がアークを表す（上り／下りの２本のアークを１本にまとめて表している）。アークに付された記号Ａ、Ｂ、Ｃ、Ｄ、Ｅは路線名を表す。この他に、路線の各アークには、上り／下りのフラグ、平均所要時間等が付されている。また、図５では、Ｘ駅とＹ駅の間を破線のアークで示し、徒歩１３分の位置にあるとしている。
【００５４】
路線間の乗換には、同じ駅で乗り換える場合と、異なる駅間を移動して乗り換える場合とがある。同じ駅での乗換については、駅をクリーク化する。「クリーク」とは、与えられたグラフに含まれる複数の点（ノード）からなる完全部分グラフのことである。「クリーク化」とは、一つの駅を、その駅に接続する路線数に相当するノードで表し、ノード間に乗換のためのアークを設けることである。クリーク化された複数のノード間にはアークを張って乗換時間を付す。図５は、Ｘ駅、Ｙ駅をクリーク化した例である。
【００５５】
Ｘ駅は、Ａ路線のＸ駅（Ａ）、Ｂ路線のＸ駅（Ｂ）、Ｃ路線のＸ駅（Ｃ）からなる３点完全グラフ（三角形）にクリーク化されており、ノード間の乗換時間はすべて３分となっている。また、Ｙ駅は、Ｄ路線のＹ駅（Ｄ）、Ｅ路線のＹ駅（Ｅ）からなる２点完全グラフにクリーク化されており、ノード間の乗換時間は２分となっている。クリーク内のノードを「クリーク駅」と呼び、クリーク駅間のアークを「路線変更アーク」と呼ぶ。
【００５６】
列車の場合の路線変更とは、路線を乗り換えることを指す。異なる駅間での徒歩による乗換については、新たに「徒歩アーク」を設ける。路線変更アークも徒歩アークも徒歩による移動であるが、便宜上、区別して用いる。図５において、太線は路線変更アークを、破線は徒歩アークを表す。徒歩アークは、Ｘ駅とＹ駅のクリーク駅のすべてのペアに対して張られる。徒歩アークまたは路線変更アークには、それを識別するためのフラグや、移動または乗換時間等が付されている。
【００５７】
また、本来の駅とクリーク駅を区別するために、本来の駅を本来駅と呼ぶことにする。例えば、Ｘ駅やＹ駅は本来駅であり、Ｘ駅（Ａ）、Ｘ駅（Ｂ）、Ｘ駅（Ｃ）はクリーク駅である。Ｘ駅は複数のクリーク駅としてネットワークに残る。
【００５８】
つぎに、本発明の最良の実施の形態に係る経路検索手段１２の経路検索方法について、図６を用いて説明する。
【００５９】
まず、経路検索を行う前提として、ステップＳ１０１において、駅をノードに持ち、駅間の路線および徒歩乗換をアークで表現するネットワークの作成を行う。このとき、作成されるネットワークは、例えばネットワークＡであり、Ａ、Ａ２、Ａ１、Ａ０等の間のグループ番号が切り替わる箇所を記憶する。作成されたネットワークは経路データとして経路データ記憶部２１に記憶される。なお、これら複数のネットワークは、別の装置で予め作成されて、経路データ記憶部２１に記憶されても良い。
【００６０】
つぎに、ステップＳ１０２において、ユーザによってクライアント端末２ａ等から入力された乗車駅、下車駅、出発時刻、到着時刻等の検索条件を読み込む。ステップＳ１０３において、記憶装置１０７から、経路データ、時刻表データ、運賃データ等の必要なデータを読み込む。
【００６１】
つぎに、ステップＳ１０４において、ダイクストラ法等を用いて、最短パス木の作成を行う。ここで作成された最短パス木は、最短パス木データとして保存される。そして、ステップＳ１０５において、マーチンのアルゴリズム等を用いて、最短パス木データをもとに、乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜Ｋ最短パスの検索を行う。このとき、ネットワークＡ、Ａ２、Ａ１、Ａ０を用いて、飛行機、新幹線、有料特急、普通列車等を利用したパス群をバランス良く求める。これらのパス群の中にはたまたま同一のパスが含まれることもあるので、それらを除去し、最終的に第１〜Ｋ最短パスを得る。得られた第１〜Ｋ最短パスは、複数パスデータに保存される。
【００６２】
つぎに、ステップＳ１０６において、第１〜Ｋ最短パスを短縮して第１〜Ｋ経路を得る。具体的には、第１〜Ｋ最短パスそれぞれに対して、路線変更アークをすべて除去し、さらに連続する同一路線名のアークをすべて短縮する。求められた複数経路は、複数経路データに保存される。本発明の最良の実施の形態において、ここで求められる経路を平均経路データと称す。本発明の最良の実施の形態においては、ステップＳ１０１ないしステップＳ１０６で算出された平均経路データに基づいて、終電や終電後列車を検索する。
【００６３】
このような本発明の最良の実施の形態に係る経路検索手段１２による経路検索方法によると、地点をノードに持ち、地点間の路線および徒歩乗換をアークで表現するネットワークにおいて、飛行機、新幹線、有料特急、普通列車等を利用した経路をバランス良く求めることができる。
【００６４】
終電列車割当手段３２は、平均経路探索手段３１で出力された平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する。終電列車割当手段３２は、従来通り、出発地Ａ駅から目的地Ｂ駅までの交通機関における終電の乗換データを出力する。終電列車割当手段３２が出力する乗換データは、出発地Ａ駅から目的地Ｂ駅まですべて交通機関で移動する場合の乗換データである。図１１に示す例によると、終電列車割当手段３２は、Ａ駅を２３：２５に出発し、Ｂ駅に００：０７に到着する乗換データを終電データとして出力する。
【００６５】
終電列車割当手段３２は、例えば午前３時などの当日扱いとなる時間の最後の時間までに到着する列車であって、最も遅く出発地を出発する列車を割り当てることにより、終電の乗換データを算出することができる。また終電列車割当手段３２は、終電と考えられる時間帯の各時間を発時間に設定して、最も遅くに出発地を出発し、当日扱いとなる時間までに到着する列車を検索しても良い。
【００６６】
終電後列車割当手段３３は、平均経路検索手段３１によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出する。さらに終電後列車割当手段３３は、この乗換データについて、日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出する。終電後列車割当手段３３は、第２の終電データを含む移動データを算出する。ここで、日越え駅とは、翌日の列車の乗車駅となる。
【００６７】
終電列車割当手段３２は、Ａ駅を２３：３６に出発する列車を終電データとして検索している。本発明の最良の実施の形態において単位時間は１分であるので、終電後列車割当手段３３は、Ａ駅を２３：３７分以降に出発するＢ駅までの乗換データを検索する。Ａ駅を２３：３７分以降に出発する列車に乗車しても、Ａ駅を２３：３６分発が終電であるので、Ａ駅からＢ駅の乗換データを検索すると、翌日の始発以降の列車を利用する区間が発生する。例えば、Ａ駅からＣ駅までは当日扱いの列車で移動できるが、Ｃ駅からＢ駅までは翌日の始発以降の列車を利用する検索結果が出力される。
【００６８】
そこで、本発明の最良の実施の形態においては、翌日の列車の乗車駅となるＣ駅を、終電後列車到着駅として定義づける。Ａ駅からＣ駅までを交通機関の乗換で案内し、Ｃ駅からＢ駅までは交通機関によらない移動手段として、例えばタクシーや徒歩等で案内する。このように、終電後列車到着駅は、ユーザによって入力された終電について出発地の出発時刻よりも単位時間以降に出発する列車に乗車した場合に、当日扱いで移動できる駅であって、目的地Ｂ駅に最も近い駅である。
【００６９】
終電後列車割当手段３３の処理は、後に詳述する。
【００７０】
列車料金算出手段３４は、記憶装置１０７から運賃データ２４ａを読み出して、終電後列車割当手段３３によって算出された第２の終電データについて、出発地から終電後列車到着駅までの交通機関の運賃を算出する。経路検索サーバ１が終電列車割当手段３２によって算出された第１の終電データを算出する場合、第１の終電データについて、出発地から目的地までの交通機関の運賃を算出する。複数の平均経路について第１の終電データを算出する場合や、複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、列車料金算出手段３４は、各第１の終電データまたは第２の終電データについて、交通機関の運賃を算出する。
【００７１】
タクシー料金算出手段３５は、記憶装置１０７からタクシー料金データ２５ａを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出する。タクシー料金算出手段３５は、終電後列車割当手段３３によって算出された第２の終電データについて、タクシー料金データ２５ａから、終電後列車到着駅と目的地間の料金を抽出する。タクシー料金算出手段３５は、記憶装置１０７から経路データ２２ａを読み出して終電後列車到着駅と目的地間の距離を算出し、算出された距離に基づいてタクシー料金を算出しても良い。複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、タクシー料金算出手段３５は、各第２の終電データについて、タクシー料金を算出する。
【００７２】
出力順序算出手段３６は、複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、所要時間優先、乗換回数優先、運賃優先等の条件取得手段１１によって取得された条件に従って、複数の第２の終電データをソートして、ソート番号を付与する。
【００７３】
経路検索手段１２の各手段による出力結果は、結果データ２６ａとして、記憶装置１０７の結果データ記憶部２６に記憶される。
【００７４】
結果提示手段１３は、記憶装置１０７から結果データ２６ａを読み出して、クライアント端末２ａの表示装置に表示可能な形式にデータを成形して、クライアント端末２ａに送信する。
【００７５】
（終電後列車検索方法）
図７および図８を参照して、本発明の最良の実施の形態に係る終電列車検索手段３２および終電後列車割当手段３３による終電後列車割当処理を説明する。
【００７６】
まず図７を参照して、本発明の最良の実施の形態に係る終電後列車割当処理の概要を説明する。図７（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【００７７】
つぎに、図７（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図７（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで日越え駅とは、図７（ｂ）に示すように、出発地Ａ駅を時刻Ｔに出発する出発地Ａ駅から目的地Ｂ駅までの列車時刻を割り当てた際に、翌日の列車の乗車駅となる駅である。換言すると、日越え駅は、出発駅Ａ駅から、当日扱いの切符で移動できる駅であって、その平均経路上で最もＢ駅に近い駅である。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、終電後列車到着駅とする。図７（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。特に環状線等の路線においては、目的地までの駅の数や所要時間よりも、距離に基づいて終電後列車到着駅を決定するほうが、ユーザに便利な経路を検索することができる。
【００７８】
図７（ｂ）に示すように、終電後列車到着駅を決定すると、図７（ｃ）に示すように、出発駅Ａ駅から終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【００７９】
図８を参照して、本発明の最良の実施の形態に係る終電後列車割当処理を説明する。
【００８０】
まずステップＳ２０１において、変数「終電後列車到着駅」として出発地を設定する。ここで設定される駅は、後述するステップＳ２０７の判定に用いられる駅なので、どの駅にも該当しないダミーの駅や、nullでも良い。さらに、変数「Ｄ＿ｍｉｎ」として、出発地と目的地の距離を代入する。この変数Ｄ＿ｍｉｎには、日越え駅と目的地との距離の最大値より大きい値であれば、どのような数値が代入されても良い。
【００８１】
つぎに、ステップＳ２０２において、平均経路検索手段３１において検索された平均経路データのそれぞれについて、ステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８２】
ステップＳ２０２において、出発地から目的地までの列車であって、出発地を時刻Ｔに出発する列車を割り当てる。ステップＳ２０３において、ステップＳ２０２において割り当てられた列車について、日越え駅を特定する。具体的には、当日扱いの切符で行ける最も目的地に経路上で近い駅を日越え駅とする。例えば、ある交通機関が、夜の３時に下車するまで当日扱いの切符で行ける場合、夜の３時に最も近い時間に下車できる駅を日越え駅とする。
【００８３】
つぎに、ステップＳ２０４において、変数「Ｄ」に、日越え駅と目的地との距離を代入する。このとき終電後列車割当手段３３は、記憶装置１０７から経路データ２２ａを読み出して、日越え駅と目的地との距離を抽出する。さらにステップＳ２０５において、変数Ｄより変数Ｄ＿ｍｉｎが大きいか否かを判定する。大きくない場合、他の平均経路についてステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８４】
一方、変数Ｄより変数「Ｄ＿ｍｉｎ」が大きい場合、ステップＳ２０６において、変数「終電後列車到着駅」にステップＳ２０３で特定した日越え駅を代入するとともに、変数「Ｄ＿ｍｉｎ」に、当該終電後列車到着駅と目的地との距離を代入する。さらに、他の平均経路についてステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８５】
すべての平均経路についてステップＳ２０２ないしステップＳ２０６の処理が終了すると、ステップＳ２０７において、変数「終電後列車到着駅」が出発地であるか否か、具体的には、ステップＳ２０１で設定した初期値のままであるか否かを判定する。初期値の場合、終電後列車で当日扱いの切符で移動できる乗換データは案内できないとして、処理を終了する。一方、変数「終電後列車到着駅」が出発地でない場合、ステップＳ２０８において出発地から終電後列車到着駅までの区間について、終電を検索し、第２の終電データとして出力する。
【００８６】
このように本発明の最良の実施の形態に係る経路検索サーバ１によれば、所定の区間について終電を検索した後、その終電の出発駅の出発時刻より単位時間後にその出発駅を出発し、目的地までの列車を検索して日越え駅となる終電後列車到着駅を特定する。従って、通常の検索エンジンの入力データを工夫することで終電後の乗換データを容易に案内することができるので、開発を容易に行うことができる。
【００８７】
さらに、出発地から終電後列車到着駅までの終電を改めて検索することにより、出発地をさらに遅く出発する列車を案内することができる。
【００８８】
（第１の変形例）
つぎに図９ないし図１２を参照して本発明の第１の変形例を説明する。
【００８９】
まず図９を参照して、本発明の第１の変形例に係る終電後列車割当処理の概要を説明する。図９（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【００９０】
つぎに、図９（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第１の終電後列車到着駅とする。図９（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９１】
図９（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図９（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ１とする。
【００９２】
さらに、図９（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ１の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｄ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ４駅、Ｃ５駅およびＣ６駅とする。ここで、各日越え駅Ｃ４駅、Ｃ５駅およびＣ６駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第２の終電後列車到着駅（新たな終電後列車到着駅）とする。図９（ｄ）に示す例では、駅Ｃ４を第２の終電後列車到着駅とする。第２の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第２の終電後列車到着駅を選択することで、第２の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９３】
図９（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図９（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｃ４駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｃ４駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ２とする。
【００９４】
さらに、図１０（ａ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ２の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図１０（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ７駅およびＣ８駅とする。ここで、各日越え駅Ｃ７駅およびＣ８駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第３の終電後列車到着駅とする。図１０（ｂ）に示す例では、駅Ｃ７を第３の終電後列車到着駅とする。第３の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第３の終電後列車到着駅を選択することで、第３の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９５】
なお、図１０（ａ）に示す例では、上から２番目の経路において、出発時刻Ｔ２以降に出発し、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がない場合を示す。この場合、出発地Ａ駅が日越え駅となるので、当該経路の駅が終電後列車到着駅になることはない。
【００９６】
図１０（ｂ）に示すように、第３の終電後列車到着駅を決定すると、図１０（ｃ）に示すように、出発駅Ａ駅から第３の終電後列車到着駅Ｃ７駅の区間について、終電列車割当手段３２により終電を検索し、第４の終電データとする。さらに、第３の終電後列車到着駅Ｃ７駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ３とする。
【００９７】
ここで、出発地Ａ駅を時刻Ｔ３（時刻ＴＤ３の１分後）に出発するＡ駅からＢ駅までの列車割当を繰り返す。この列車割当は、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなるまで繰り返される。
【００９８】
図１０（ｃ）に示すように、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１０（ｄ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【００９９】
このような本発明の第１の変形例においては、図１１に示すように、終電後列車を複数提示することができる。図１１に示す画面例では、出発地Ａ駅から到着地Ｂ駅までの終電を表示した終電経路表示部６０１と、この終電後の列車でタクシーを利用した経路を表示する複数のタクシー利用経路表示部６０２ａ、６０２ｂ、６０２ｃおよび６０２ｄを有する。
【０１００】
図１２を参照して、本発明の第１の変形例に係る終電後列車割当処理を説明する。
【０１０１】
図１２に示すステップＳ３０１ないしステップＳ３０８は、図８を参照して説明した本発明の最良の実施の形態に係る終電後列車割当処理のステップＳ２０１ないしステップＳ２０８と同様である。
【０１０２】
具体的には、まずステップＳ３０１において、変数「終電後列車到着駅」（第１の終電後列車到着駅）として出発地を設定する。さらに、変数「Ｄ＿ｍｉｎ」として、出発地と目的地の距離を代入する。
【０１０３】
つぎに、平均経路検索手段３１において検索された平均経路データのそれぞれについて、ステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０４】
ステップＳ３０２において、出発地から目的地までの列車であって、出発地を時刻Ｔに出発する列車を割り当てる。ステップＳ３０３において、ステップＳ２０２において割り当てられた列車について、日越え駅を特定する。具体的には、当日扱いの切符で行ける最も目的地に経路上で近い駅を日越え駅とする。
【０１０５】
つぎに、ステップＳ３０４において、変数「Ｄ」に、日越え駅と目的地との距離を代入する。このとき終電後列車割当手段３３は、記憶装置１０７から経路データ２２ａを読み出して、日越え駅と目的地との距離を抽出する。さらにステップＳ３０５において、変数Ｄより変数Ｄ＿ｍｉｎが大きいか否かを判定する。大きくない場合、他の平均経路についてステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０６】
一方、変数Ｄより変数「Ｄ＿ｍｉｎ」が大きい場合、ステップＳ３０６において、変数「終電後列車到着駅」にステップＳ２０３で特定した日越え駅を代入するとともに、変数「Ｄ＿ｍｉｎ」に、当該終電後列車到着駅と目的地との距離を代入する。さらに、他の平均経路についてステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０７】
すべての平均経路についてステップＳ３０２ないしステップＳ３０６の処理が終了すると、ステップＳ３０７において、変数「終電後列車到着駅」が出発地であるか否か、具体的には、ステップＳ２０１で設定した初期値のままであるか否かを判定する。初期値の場合、終電後列車で当日扱いの切符で移動できる乗換データは案内できないとして、処理を終了する。一方、変数「終電後列車到着駅」が出発地でない場合、ステップＳ３０８において出発地から終電後列車到着駅までの区間について、終電を検索し、第２の終電データとして出力する。
【０１０８】
さらにステップＳ３０９において、第２の終電データにおける出発地Ａ駅の出発時刻に単位時間１分を加算して、時刻Ｔ１を算出する。つぎに、ステップＳ３１０において、さらに、時刻Ｔ１以降に出発し出発地Ａ駅から目的地Ｂ駅に到着する列車を検索するために、終電後列車割当手段３３による終電後列車割当処理を実行する。この処理においても、出発地Ｓ３０７において出発地が終電後列車到着駅になると、処理を終了する。
【０１０９】
このように本発明の第１の変形例に係る終電後列車割当処理によれば、終電後列車到着駅が出発地に一致するまで、終電データの検索を継続するので、出発地から目的地までの終電後について、複数の経路を出力することができる。さらに、タクシー利用の距離が増えるとともに、出発地の出発時刻を遅くすることができるので、ユーザは自己の状況に応じて、適切な経路を選択することができる。
【０１１０】
（第２の変形例）
第２の変形例では、第１の変形例と同様に複数の終電後の経路データを出力することができるが、その算出方法が異なる。
【０１１１】
まず図１３を参照して、本発明の第２の変形例に係る終電後列車割当処理の概要を説明する。図１３（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【０１１２】
つぎに、図１３（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図１３（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第１の終電後列車到着駅とする。図１３（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１３】
図１３（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図１３（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ１とする。
【０１１４】
さらに、図１３（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ＿Ｃ１の１分後）に出発するＡ駅から第１の終電後列車到着駅Ｃ１駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｄ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ４駅およびＣ５駅とする。ここで、各日越え駅Ｃ４駅およびＣ５駅と、図１３（ｂ）で算出したＣ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第２の終電後列車到着駅とする。図１３（ｄ）に示す例では、駅Ｃ２を第２の終電後列車到着駅とする。第２の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第２の終電後列車到着駅を選択することで、第２の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１５】
図１３（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図１３（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｃ２駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｃ２駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ２とする。
【０１１６】
さらに、図１４（ａ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ＿Ｃ２の１分後）に出発するＡ駅から第２の終電後列車到着駅Ｃ２駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定する。ここで、日越え駅Ｃ６駅と、既に算出された日越え駅Ｃ３、Ｃ４およびＣ５のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第３の終電後列車到着駅とする。図１４（ｂ）に示す例では、駅Ｃ４を第３の終電後列車到着駅とする。第３の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第３の終電後列車到着駅を選択することで、第３の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１７】
図１４（ｂ）に示すように、第３の終電後列車到着駅を決定すると、図１４（ｃ）に示すように、出発駅Ａ駅から第３の終電後列車到着駅Ｃ４駅の区間について、終電列車割当手段３２により終電を検索し、第４の終電データとする。さらに、第３の終電後列車到着駅Ｃ４駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ４とする。
【０１１８】
ここで、図１４（ａ）に示されている４つの経路のうち、上の二つは、図１３（ｄ）で算出された経路で、一番下は、図１３（ｂ）で算出された経路である。このように各処理ステップで算出された日越え駅のデータを引き継ぎ、最終的に、出発地Ａ駅と目的地Ｂ駅間のすべての終電列車を割り当てるまで繰り返される。
【０１１９】
図１４（ｃ）に示すように、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１４（ｄ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【０１２０】
このような本発明の第２の変形例においては、出発地Ａ駅と目的地Ｂ駅間のすべての終電列車を検索するので、より多くの経路をユーザに提示することができる。
【０１２１】
つぎに図１５および図１６を参照して、本発明の第２の変形例に係る終電後列車割当処理を説明する。
【０１２２】
まず図１５に示すステップＳ３０１において、変数「終電後列車到着駅」（第１の終電後列車到着駅）として目的地を設定する。さらに、変数「到着候補駅リスト」を初期化する。この到着候補駅リストには、出発地から目的地までの各経路上に位置する日越え駅が挿入される。この到着候補駅リストが空になるまで、ステップＳ４０２ないしステップＳ４０７の処理を繰り返す。
【０１２３】
つぎに、ステップＳ４０２において、日越え駅検索処理を実行する。これにより、日越え駅がある場合は、到着候補駅リストに日越え駅が挿入される。この処理は後に詳述する。
【０１２４】
ステップＳ４０３において、到着候補駅リストが空であるか否かを検索する。到着候補駅リストが空の場合、そのまま処理を終了する。到着候補駅リストに、到着候補駅が挿入されている場合、ステップＳ４０４において、到着候補駅リストの駅から、目的地との距離が最短の駅を抽出するとともに削除する。さらに、ステップＳ４０５において、終電後列車到着駅に、ステップＳ４０４において抽出された駅を挿入する。
【０１２５】
ステップＳ４０６において、出発地から終電後列車到着駅の間の区間について終電検索する。ステップＳ４０７において、ステップＳ４０６で算出した終電の出発地における出発時刻に単位時間を足して、時刻Ｔを算出する。
【０１２６】
到着候補駅リストが空になるまで、ステップＳ４０２ないしステップＳ４０７の処理を繰り返すと、終電後列車割当処理を終了する。
【０１２７】
つぎに図１６を参照して、図１５のステップＳ４０２に相当する日越え駅検索処理を説明する。日越え駅検索処理は、平均経路検索手段３１によって算出されたすべての平均経路についてステップＳ４５１ないしステップＳ４５４の処理を繰り返す。
【０１２８】
まずステップＳ４５１において、出発地を時刻Ｔに出発する出発地から終電後列車到着駅の列車を割り当てる。ステップＳ４５２において、ステップＳ４５１で割り当てた列車について日越え駅を特定する。
【０１２９】
ステップＳ４５３において日越え駅と出発地が同じか否かを判定する。同じ場合、他の平均経路についてステップＳ４５１の処理を実行する。一方日越え駅と出発地が異なる場合、ステップＳ４５４において、到着候補駅リストにステップＳ４５２で特定した日越え駅を追加して、他の平均経路についてステップＳ４５１の処理を実行する。
【０１３０】
このように本発明の第２の変形例に係る終電後列車割当処理によれば、出発地から目的地までの終電後の時間帯について、すべての日越え駅を抽出することができるので、より多くの終電後列車を割り当てることができる。
【０１３１】
（第３の変形例）
つぎに図１７および図１８を参照して本発明の第３の変形例を説明する。
【０１３２】
まず図１７を参照して、本発明の第１の変形例に係る終電後列車割当処理の概要を説明する。図１７（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【０１３３】
つぎに、図１７（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。このとき、列車割当に対して、日越え駅を決定し、Ｃ駅とする。複数の経路についてそれぞれ日越え駅が決定された場合、そのうち目的地のＢ駅に最も近い日越え駅を、第１の終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１３４】
図１７（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図１７（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ１とする。
【０１３５】
さらに、図１７（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ１の１分後）に出発するＡ駅からＣ駅までの列車時刻を割り当てる。このとき、列車割当に対して、日越え駅を決定し、Ｄ駅とする。ここで、複数の経路についてそれぞれ日越え駅が決定された場合、そのうち第１の終電後列車到着駅のＣ駅に最も近い日越え駅を、第２の終電後列車到着駅とする。
【０１３６】
図１７（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図１７（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｄ駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｄ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ２とする。
【０１３７】
さらに、図１７（ｆ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ２の１分後）に出発するＡ駅からＤ駅までの列車時刻を割り当て、図１７（ｄ）および図１７（ｅ）と同様の処理を、終電後列車到着駅と出発地とが一致するまで繰り返す。
【０１３８】
出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１７（ｇ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【０１３９】
このような本発明の第３の変形例においては、終電後列車到着駅を目的地として処理を繰り返す。
【０１４０】
図１８を参照して、本発明の第３の変形例に係る終電後列車割当処理を説明する。
【０１４１】
図１８に示すステップＳ５０１ないしステップＳ５０９は、図１２を参照して説明した本発明の第１の変形例に係る終電後列車割当処理のステップＳ３０１ないしステップＳ３０９と同様である。
【０１４２】
ステップＳ５１０においてさらに、時刻Ｔ１以降に出発し出発地Ａ駅から終電後列車到着駅に到着する列車を検索するために、終電後列車割当手段３３による終電後列車割当処理を実行する。この処理においても、出発地Ｓ５０７において出発地が終電後列車到着駅になると、処理を終了する。
【０１４３】
なお、本発明の第２の変形例においては、図１２のステップＳ３１０において、出発地から目的地間の終電を検索している。一方、本発明の第３の変形例においては、図１８のステップＳ５１０において、出発地から終電後列車到着駅間の終電を検索している。
【０１４４】
（その他の実施の形態）
上記のように、本発明の最良の実施の形態および第１ないし第３の変形例によって記載したが、この開示の一部をなす論述および図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例および運用技術が明らかとなる。
【０１４５】
例えば、本発明の最良の実施の形態に記載した経路検索サーバ１は、図１に示すように一つのハードウェア上に構成されても良いし、その機能や処理数に応じて複数のハードウェア上に構成されても良い。
【０１４６】
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１４７】
【図１】本発明の最良の実施の形態に係る経路検索システムのシステム構成と、経路検索サーバの機能ブロックを説明する図である。
【図２】本発明の最良の実施の形態に係る経路検索サーバのハードウェア構成図である。
【図３】本発明の最良の実施の形態に係る経路検索サーバによる経路検索処理の概要を説明するフローチャートである。
【図４】本発明の最良の実施の形態に係る経路検索処理におけるネットワークの一例を説明する図である。
【図５】本発明の最良の実施の形態に係る経路検索処理におけるクリーク化されたネットワークの一例を説明する図である。
【図６】本発明の最良の実施の形態に係る経路検索手段の平均経路検索手段による平均経路検索処理を説明するフローチャートである。
【図７】本発明の最良の実施の形態に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。
【図８】本発明の最良の実施の形態に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図９】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その１）
【図１０】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その２）
【図１１】本発明の最良の実施の形態に係る経路検索サーバが、検索結果を表示する画面の一例である。
【図１２】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図１３】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その１）
【図１４】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その２）
【図１５】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図１６】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による日越え駅検索処理を説明するフローチャートである。
【図１７】本発明の第３の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。
【図１８】本発明の第３の変形例に係る経路検索手段の終電後列車割当手段による日越え駅検索処理を説明するフローチャートである。
【図１９】一般的な経路検索サーバが、検索結果を表示する画面の一例である。
【符号の説明】
【０１４８】
１ 経路検索サーバ
２ クライアント端末
３ 通信ネットワーク
１１ 条件取得手段
１２ 経路検索手段
１３ 結果提示手段
２１ 検索条件データ記憶部
２２ 経路データ記憶部
２３ 時刻表データ記憶部
２４ 運賃データ記憶部
２５ タクシー料金データ記憶部
２６ 結果データ記憶部
３１ 平均経路探索手段
３２ 終電列車割当手段
３３ 終電後列車割当手段
３４ 列車料金算出手段
３５ タクシー料金算出手段
３６ 出力順序算出手段
１０１ 中央処理制御装置
１０２ ＲＯＭ
１０３ ＲＡＭ
１０４ 入力装置
１０５ 表示装置
１０６ 通信制御装置
１０７、３０ 記憶装置
１０８ リムーバブルディスク
１０９ 入出力インタフェース
１１０ バス
【技術分野】
【０００１】
本発明は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバおよび経路検索プログラムに関する。
【背景技術】
【０００２】
近年の情報通信の技術に伴い、インターネット等の通信ネットワークを介して、様々な情報が提供されている。その一つに、交通機関の乗換情報がある。乗換情報とは、ユーザが出発地と、目的地と、目的地の到着を希望する時刻等を入力することにより、どの交通機関の何時の電車に乗り、どの駅で乗り換えるか、等の電車の乗換情報を提供するものである。経路検索サービスにおいては、ユーザに最適な乗換情報を提供できる方法が提案されており、その一つに、所定の区間の終電を案内するサービスがある。終電案内サービスは、例えば、仕事や所用で遅くなる場合に予め終電を検索する際に用いられる。
【０００３】
終電案内サービスはユーザが入力した出発地および目的地間の終電を案内するものであるが、終電に間に合わない場合の案内サービスもある（例えば、特許文献１参照。）特許文献１等に記載の方法においては、終電時間内に利用することができる目的地に最も近い駅の情報をユーザに提供する。この際、特許文献１に記載の方法では、ユーザの現在位置の位置情報に基づいて、ユーザの位置情報に対して最寄りかつ終電時間内に利用可能な出発駅と、ユーザの住所に対して最寄りかつ終電時間内に利用可能な位置を検索する（特許文献１の段落番号［００２０］等参照）。ここで、特許文献１に記載の方法では、ユーザの位置情報を元に、駅の緯度経度情報に基づいて最寄り駅を検索する（特許文献１の段落番号［００３２］および［００３３］等参照）。
【特許文献１】特開２００６−１１５４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の特許文献１に記載の方法では、位置情報を取得する装置を有しないパーソナルコンピュータ等を用いて検索する際には適切ではない。また、位置情報に基づいて出発地および目的地を検索するため、通常の使いなれていないルートが検索される場合があり、一刻を争う終電後の乗換案内には不向きな場合がある。
【０００５】
このように、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することが期待されている。
【０００６】
従って本発明の目的は、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の第１の特徴は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバに関する。即ち本発明の第１の特徴に係る経路検索サーバは、交通機関の経路と、経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、乗換の条件を取得する条件取得手段と、記憶装置から経路データを読み出し、条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段と、移動データを出力する結果提示手段とを備える。
【０００８】
ここで、交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、記憶装置に記憶するタクシー料金データ記憶手段と、記憶装置からタクシー料金データを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出するタクシー料金算出手段をさらに備え、移動データは、タクシー料金算出手段によって算出されたタクシー料金を含んでも良い。
【０００９】
また、平均経路検索手段はさらに、経路上の駅間の距離を記憶し、平均経路検索手段が複数の平均経路データを算出した場合、終電後列車割当手段は、平均経路検索手段が算出したすべての平均経路データについて乗換データおよび日越え駅を算出し、目的地との距離が最も小さい日越え駅を終電後列車到着駅としても良い。
【００１０】
また、終電後列車割当手段は、さらに、第２の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、出発地から新たな終電後列車到着駅までの交通機関の終電となる第３の終電データを算出し、第３の終電データを含む新たな移動データを算出しても良い。
【００１１】
また、終電後列車割当手段は、新たな終電後列車到着駅が出発地になるまで、新たな移動データを算出する処理を繰り返しても良い。
【００１２】
また、タクシー料金算出手段はさらに、新たな終電後列車到着駅と目的地との新たなタクシー料金を算出し、新たな移動データは、タクシー料金算出手段によって算出された新たなタクシー料金を含んでも良い。
【００１３】
本発明の第２の特徴は、出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索プログラムに関する。即ち本発明の第２の特徴に係る経路検索プログラムは、交通機関の経路と、経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、乗換の条件を取得する条件取得手段と、記憶装置から経路データを読み出し、条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する終電列車割当手段と、平均経路検索手段によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出し、第２の終電データを含む移動データを算出する終電後列車割当手段と、移動データを出力する結果提示手段とを、コンピュータに機能させる。
【００１４】
ここで、交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、記憶装置に記憶するタクシー料金データ記憶手段と、記憶装置からタクシー料金データを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出するタクシー料金算出手段をさらにコンピュータに機能させ、移動データは、タクシー料金算出手段によって算出されたタクシー料金を含んでも良い。
【００１５】
また、平均経路検索手段はさらに、経路上の駅間の距離を記憶し、平均経路検索手段が複数の平均経路データを算出した場合、終電後列車割当手段は、平均経路検索手段が算出したすべての平均経路データについて乗換データおよび日越え駅を算出し、目的地との距離が最も小さい日越え駅を終電後列車到着駅としてもよい。
【００１６】
また、終電後列車割当手段は、さらに、第２の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、出発地から新たな終電後列車到着駅までの交通機関の終電となる第３の終電データを算出し、第３の終電データを含む新たな移動データを算出しても良い。
【００１７】
また、終電後列車割当手段は、新たな終電後列車到着駅が出発地になるまで、新たな移動データを算出する処理を繰り返しても良い。
【００１８】
また、タクシー料金算出手段はさらに、新たな終電後列車到着駅と目的地との新たなタクシー料金を算出し、新たな移動データは、タクシー料金算出手段によって算出された新たなタクシー料金を含んでも良い。
【発明の効果】
【００１９】
本発明によれば、終電後の移動データを適切に出力する経路検索サーバおよび経路検索プログラムを提供することができる。
【発明を実施するための最良の形態】
【００２０】
つぎに、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一または類似の部分には同一または類似の符号を付している。
【００２１】
本発明の最良の実施の形態において「終電」とは、出発地から目的地までの所定区間の交通機関の乗換データのうち、各交通機関で当日扱いとなる最終の乗換データのことを指す。具体的には、ある交通機関の駅で９月５日午前２時に到着する列車が最終の列車であっても、その列車に９月４日発売の切符で乗車できる場合、９月４日の終電として検索される。
【００２２】
「終電後列車」とは、所定区間の終電データに基づいて、終電データにおける出発地の出発時刻の単位時間後に出発する列車であって、目的地までの途中駅まで到着する列車のことを指す。
【００２３】
「単位時間」とは、経路検索サーバ１に記憶された時刻表データ２３ａの最小時間単位である。例えば、時刻表データ２３ａが１分単位で作成されている場合、単位時間は１分となる。同様に、時刻表データ２３が１０秒単位で作成されている場合、単位時間は１０秒となる。本発明の最良の実施の形態においては、時刻表データ２３ａが１分単位で作成されており、単位時間が１分の場合について説明する。
【００２４】
（最良の実施の形態）
本発明の最良の実施の形態に係る経路検索システムは、経路検索サーバ１、クライアント端末２ａ等を備えている。経路検索サーバ１とクライアント端末２ａ等は、インターネット等の通信ネットワーク３によって、相互に接続されている。
【００２５】
経路検索サーバ１は、所定の条件で、出発地から目的地までの交通機関の乗換を検索した結果である乗換データを出力する。経路検索サーバ１は、クライアント端末２ａ等から条件を受信し、その条件に従って出発地から目的地までの交通機関の乗換を検索し、その結果である乗換データを、条件を入力したクライアント端末２ａ等の表示画面に表示する。
【００２６】
ここで所定の条件とは、クライアント端末２ａ等から、ユーザの操作によって入力される。所定の条件は具体的には、出発地、目的地、出発地を出発する時刻を指定した出発希望時刻、目的地に到着する時刻を指定した到着希望時刻が挙げられる。出発地および目的地は、電車の駅やバスの停留所など交通機関の乗車下車できる地点である。さらに所定の条件は、複数の乗換データからユーザのニーズにあった条件を優先するために、所要時間優先、乗換回数優先、運賃優先、今来る列車に乗ることを優先する今来る列車優先、等が挙げられる。
【００２７】
本発明の最良の実施の形態に係る経路検索サーバ１は特に、終電後の移動データを適切に出力する。従って、所定の条件として、出発地および目的地の他に、終電や終電後列車を検索する旨の指示が含まれる。
【００２８】
クライアント端末２ａは、一般的にＣＰＵ、記憶装置、入力装置および表示装置等を備える電子機器である。クライアント端末２ａにはブラウザなどの所定のソフトウェアなどがインストールされている。このソフトウェアは、経路検索サーバ１に送信する所定条件の入力や、経路検索サーバ１から送信された検索結果の出力等を支援する。クライアント端末２ｂおよびクライアント端末２ｃも、クライアント端末２ａと同様の構成を備える。
【００２９】
図２に示すように、本発明の最良の実施の形態に係る経路検索サーバ１は、中央処理制御装置１０１、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３および入出力インタフェース１０９が、バス１１０を介して接続されている。入出力インタフェース１０９には、入力装置１０４、表示装置１０５、通信制御装置１０６、記憶装置１０７およびリムーバブルディスク１０８が接続されている。
【００３０】
中央処理制御装置１０１は、入力装置１０４からの入力信号に基づいてＲＯＭ１０２から経路検索サーバ１を起動するためのブートプログラムを読み出して実行し、さらに記憶装置１０７に記憶されたオペレーティングシステムを読み出す。さらに中央処理制御装置１０１は、入力装置１０４や通信制御装置１０６などの入力信号に基づいて、各種装置の制御を行ったり、ＲＡＭ１０３や記憶装置１０７などに記憶されたプログラムおよびデータを読み出してＲＡＭ１０３にロードするとともに、ＲＡＭ１０３から読み出されたプログラムのコマンドに基づいて、データの計算または加工など、後述する一連の処理を実現する処理装置である。
【００３１】
入力装置１０４は、操作者が各種の操作を入力するキーボード、マウスなどの入力デバイスにより構成されており、操作者の操作に基づいて入力信号を作成し、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送信される。表示装置１０５は、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどであり、中央処理制御装置１０１からバス１１０および入出力インタフェース１０９を介して表示装置１０５において表示させる出力信号を受信し、例えば中央処理制御装置１０１の処理結果などを表示する装置である。通信制御装置１０６は、ＬＡＮカードやモデムなどの装置であり、経路検索サーバ１をインターネットやＬＡＮなどの通信ネットワークに接続する装置である。通信制御装置１０６を介して通信ネットワークと送受信したデータは入力信号または出力信号として、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送受信される。
【００３２】
記憶装置１０７は半導体記憶装置や磁気ディスク装置であって、中央処理制御装置１０１で実行されるプログラムやデータが記憶されている。リムーバブルディスク１０８は、光ディスクやフレキシブルディスクのことであり、ディスクドライブによって読み書きされた信号は、入出力インタフェース１０９およびバス１１０を介して中央処理制御装置１０１に送受信される。
【００３３】
本発明の最良の実施の形態に係る経路検索サーバ１の記憶装置１０７には、経路検索プログラムが記憶されるとともに、検索条件データ記憶部２１、経路データ記憶部２２、時刻表データ記憶部２３、運賃データ記憶部２４、タクシー料金データ記憶部２５および結果データ記憶部２６を備えている。また、経路検索プログラムが経路検索サーバ１の中央処理制御装置１０１に読み込まれ実行されることによって、条件取得手段１１、経路検索手段１２および結果提示手段１３が経路検索サーバ１に実装される。
【００３４】
検索条件データ記憶部２１は、クライアント端末２ａ等から受信した交通機関の乗換の検索条件データ２１ａが記憶された記憶部である。条件取得手段１１が、記憶装置１０７の検索条件データ記憶部２１に、検索条件データ２１ａを記憶する。検索条件データ２１ａは、出発地および目的地の識別子を含み、一般的に、出発地の出発希望時刻または到着地の到着希望時刻を含むデータである。特に本発明の最良の実施の形態において検索条件は、出発地および目的地間の交通機関の終電や、終電後列車を案内する旨が含まれる。さらに、検索条件データ２１ａに、検索結果を「所要時間」の短い順に出力するか等のソート条件も含まれる場合がある。
【００３５】
経路データ記憶部２２は、経路データ２２ａが記憶された記憶部である。経路データ記憶手段（図示せず）が、記憶装置１０７の経路データ記憶部２２に、経路データ２２ａを記憶する。経路データ２２ａは、交通機関の路線と、路線上に位置する駅と、経路上の駅間の距離と、を関連づけたデータである。経路上の駅間の距離は営業距離でも良いが、駅位置から算出される直線距離でも良い。直線距離の場合、後述する終電後列車の下車駅から目的地までタクシー等で移動する場合の基準とすることができる。
【００３６】
時刻表データ記憶部２３は、時刻表データ２３ａが記憶された記憶部である。時刻表データ記憶手段（図示せず）が、記憶装置１０７の時刻表データ記憶部２３に、時刻表データ２３ａを記憶する。時刻表データ２３ａは、交通機関の経路の列車の時刻表を関連づけたデータである。時刻表データ２３ａは、交通機関、経路の駅および電車種別毎に記憶されていることが好ましい。
【００３７】
運賃データ記憶部２４は、運賃データ２４ａが記憶された記憶部である。運賃データ記憶手段（図示せず）が、記憶装置１０７の運賃データ記憶部２２に、運賃データ２４ａを記憶する。運賃データ２４ａは、交通機関の経路と運賃を関連づけたデータである。運賃データ２４ａは、交通機関の距離毎に記憶されていることが好ましい。
【００３８】
タクシー料金データ記憶部２５は、タクシー料金データ２５ａが記憶された記憶部である。タクシー料金データ記憶手段（図示せず）が、記憶装置１０７のタクシー料金データ記憶部２５に、タクシー料金データ２５ａを記憶する。タクシー料金データ２５ａは、交通機関の各駅間についてタクシー料金が関連づけられている。また、別の実施例としては、タクシー料金を計算するために必要となる、初乗り運賃と初乗り運賃が適用される距離、さらに従量制の距離と料金の情報を記憶しても良い。この場合、後述するタクシー料金算出手段３５が、タクシーで移動となる距離を取得して、タクシー料金を算出しても良い。
【００３９】
経路データ２２ａ、時刻表データ２３ａ、運賃データ２４ａおよびタクシー料金データ２５ａは、一般的な経路検索サーバが有している情報で、経路検索が可能であれば、どのような構成を備えていても良い。
【００４０】
結果データ記憶部２６は、結果データ２６ａが記憶された記憶部である。経路検索手段１２が、記憶装置１０７の結果データ記憶部２６に、結果データ２６ａを記憶する。結果データ２５ａは、出発地から目的地までの終電後の列車であって、終電における出発地の出発時刻より単位時間後に出発地を出発し、終電後列車の到着駅までの乗換データを含む。さらに結果データ２５ａには、終電後列車到着駅から目的地までタクシーで移動する場合の所要時間、料金等が含まれても良い。
【００４１】
検索条件データ記憶部２１に記憶された検索条件データ２１ａおよび結果データ記憶部２５に記憶された結果データ２５ａは、本発明の最良の実施の形態に係る経路検索サーバ１の処理における一時データであるので、記憶装置１０７ではなく、ＲＡＭ１０３に記憶され、必要に応じて消去されても良い。
【００４２】
つぎに図３を参照して、本発明の最良の実施の形態に係る経路検索サーバ１の処理の概略を説明する。
【００４３】
まずクライアント端末２ａ等から検索条件が入力されると、ステップＳ１において、経路検索処理に先立って初期化する。具体的には、経路検索処理で使用される変数の初期化などが行われる。ここで検索条件とは、出発地、目的地、経由地等の経路を決定するための条件と、出発希望時刻、到着希望時刻、所用時間優先、乗換回数優先、運賃優先、今くる列車優先、ユーザに最適な経路を出力するための条件が含まれる。ここでは、出発地を「Ａ駅」、目的地を「Ｂ駅」として、出発地から目的地までの終電または終電後列車を求めるとの条件が入力されたとする。
【００４４】
つぎにステップＳ２ないしステップＳ６において、乗換データを算出する処理が行われる。具体的には、ステップＳ２において、Ａ駅からＢ駅までの平均経路データが検索される。ここで平均経路データとは、ユーザが入力した条件に適合する可能性のある経路データである。この平均経路データでは、出力する経路数以上の経路が出力される。つぎに、ステップＳ２で検索された平均経路のそれぞれについて、ステップＳ３において、列車の時刻表データ等を参照して、Ａ駅からＢ駅までの終電の列車を割り当てる。
【００４５】
つぎにステップＳ４において、ステップＳ３で検索した終電列車の出発地Ａ駅における出発時刻に単位時間を足した時間を算出し、時刻Ｔとする。さらにステップＳ５において、終電後の列車を割り当てる。具体的には、出発地Ａ駅をステップＳ４で算出した時刻Ｔに出発する列車を検索する。ステップＳ５で割り当てられる列車は、Ａ駅からＢ駅までの終電よりも後の列車になるので、Ａ駅から、Ａ駅とＢ駅の間のＣ駅までの終電の列車となる。ステップＳ６において、列車の運賃データ等を参照して、運賃を算出する。さらにステップＳ７において、タクシー料金が算出される。ここで算出されるタクシー料金は、Ｃ駅からＢ駅までのタクシー料金である。
【００４６】
ステップＳ２で算出された平均経路のすべて或いは一部について、ステップＳ３ないしステップＳ７の処理を繰り返す。ステップＳ２ないしステップＳ７で算出された結果は、結果データ２５ａとして記憶装置１０７に記憶される。
【００４７】
さらに、ステップＳ８において、結果データ２５ａのうち、ユーザが入力した検索条件に適合する乗換データを出力する。ここでは、ユーザが、「所要時間優先」で経路検索しているので、ステップＳ８において、所要時間が短いものから優先した乗換データが、クライアント端末２ａ等に出力される。ステップＳ８で出力される経路データは、一つでも良いし複数でも良い。
【００４８】
つぎに、図１を参照して、本発明の最良の実施の形態に係る経路探索サーバ１の各処理手段について詳述する。
【００４９】
条件取得手段１１は、乗換のための検索条件を取得する。条件取得手段１１は、クライアント端末２ａ等から通信ネットワーク４、通信制御装置１０６等を介して入力された検索条件データ２１ａを、検索条件データ記憶部２１に記憶する。この検索条件データ２１ａには、出発地、目的地、経由地等の経路を決定するための条件と、出発希望時刻、到着希望時刻、時間優先、乗換回数優先、運賃優先、今くる列車優先、ユーザに最適な経路を出力するための条件が含まれる。本発明の最良の実施の形態においては特に、検索条件データ２１ａとして終電または終電後列車を検索する旨が含まれる。また条件取得手段１１は、条件を取得すると、経路検索のための初期化処理をする。
【００５０】
経路検索手段１２は、記憶装置１０７から経路データ２２ａを読み出し、条件取得手段１１によって取得された検索条件データ２１ａに従って、乗換データを検索して出力する。ここで出力される乗換データは、ユーザが入力した出発地から目的地までの交通機関の終電後の列車に関する乗換のデータである。経路検索手段１２は、さらに、記憶装置１０７から時刻表データ２３ａを読み出し、出力された乗換データに交通機関の列車の時刻を割り当てて、交通機関の時刻と、当該乗換データにおける所要時間を出力する。経路検索手段１２は、さらに、出力された乗換データにおける乗換回数を出力する。経路検索手段１２は、さらに、記憶装置１０７から運賃データを読み出し、出力された乗換データの運賃を算出して出力する。乗換検索手段１２は、さらに、記憶装置１０７からタクシー料金データ２５ａを読み出し、終電後列車到着駅から目的地までのタクシーの料金や所要時間等も出力する。
【００５１】
図１に示すように経路検索手段１２はさらに、平均経路検索手段３１、終電列車割当手段３２、終電後列車割当手段３３、列車料金算出手段３４、タクシー料金算出手段３５および出力順序算出手段３６を備える。
【００５２】
平均経路探索手段３１は、記憶装置１０７から経路データ２２ａを読み出し、条件取得手段１１によって取得された条件に従って、平均経路データを検索して出力する。
【００５３】
本発明の実施の形態に係る経路検索手段１２の平均経路検索手段３１の経路検索方法について、まず、複数の「ノード」とノード間を接続する「アーク」からなるネットワークについて説明する。経路探索で用いるネットワークは、基本的には、駅を「ノード」とみなし、線路上で隣り合う駅間に「アーク」を設けて作成する。「アーク」には駅間の移動時間が付されており、これを「重み」という。この例として、Ｘ駅とＹ駅のネットワークを図４に示す。ここでは、Ｘ駅、Ｙ駅がノードとなり、記号Ａ、Ｂ、Ｃ、Ｄ、Ｅを付した実線で示す両端矢印がアークを表す（上り／下りの２本のアークを１本にまとめて表している）。アークに付された記号Ａ、Ｂ、Ｃ、Ｄ、Ｅは路線名を表す。この他に、路線の各アークには、上り／下りのフラグ、平均所要時間等が付されている。また、図５では、Ｘ駅とＹ駅の間を破線のアークで示し、徒歩１３分の位置にあるとしている。
【００５４】
路線間の乗換には、同じ駅で乗り換える場合と、異なる駅間を移動して乗り換える場合とがある。同じ駅での乗換については、駅をクリーク化する。「クリーク」とは、与えられたグラフに含まれる複数の点（ノード）からなる完全部分グラフのことである。「クリーク化」とは、一つの駅を、その駅に接続する路線数に相当するノードで表し、ノード間に乗換のためのアークを設けることである。クリーク化された複数のノード間にはアークを張って乗換時間を付す。図５は、Ｘ駅、Ｙ駅をクリーク化した例である。
【００５５】
Ｘ駅は、Ａ路線のＸ駅（Ａ）、Ｂ路線のＸ駅（Ｂ）、Ｃ路線のＸ駅（Ｃ）からなる３点完全グラフ（三角形）にクリーク化されており、ノード間の乗換時間はすべて３分となっている。また、Ｙ駅は、Ｄ路線のＹ駅（Ｄ）、Ｅ路線のＹ駅（Ｅ）からなる２点完全グラフにクリーク化されており、ノード間の乗換時間は２分となっている。クリーク内のノードを「クリーク駅」と呼び、クリーク駅間のアークを「路線変更アーク」と呼ぶ。
【００５６】
列車の場合の路線変更とは、路線を乗り換えることを指す。異なる駅間での徒歩による乗換については、新たに「徒歩アーク」を設ける。路線変更アークも徒歩アークも徒歩による移動であるが、便宜上、区別して用いる。図５において、太線は路線変更アークを、破線は徒歩アークを表す。徒歩アークは、Ｘ駅とＹ駅のクリーク駅のすべてのペアに対して張られる。徒歩アークまたは路線変更アークには、それを識別するためのフラグや、移動または乗換時間等が付されている。
【００５７】
また、本来の駅とクリーク駅を区別するために、本来の駅を本来駅と呼ぶことにする。例えば、Ｘ駅やＹ駅は本来駅であり、Ｘ駅（Ａ）、Ｘ駅（Ｂ）、Ｘ駅（Ｃ）はクリーク駅である。Ｘ駅は複数のクリーク駅としてネットワークに残る。
【００５８】
つぎに、本発明の最良の実施の形態に係る経路検索手段１２の経路検索方法について、図６を用いて説明する。
【００５９】
まず、経路検索を行う前提として、ステップＳ１０１において、駅をノードに持ち、駅間の路線および徒歩乗換をアークで表現するネットワークの作成を行う。このとき、作成されるネットワークは、例えばネットワークＡであり、Ａ、Ａ２、Ａ１、Ａ０等の間のグループ番号が切り替わる箇所を記憶する。作成されたネットワークは経路データとして経路データ記憶部２１に記憶される。なお、これら複数のネットワークは、別の装置で予め作成されて、経路データ記憶部２１に記憶されても良い。
【００６０】
つぎに、ステップＳ１０２において、ユーザによってクライアント端末２ａ等から入力された乗車駅、下車駅、出発時刻、到着時刻等の検索条件を読み込む。ステップＳ１０３において、記憶装置１０７から、経路データ、時刻表データ、運賃データ等の必要なデータを読み込む。
【００６１】
つぎに、ステップＳ１０４において、ダイクストラ法等を用いて、最短パス木の作成を行う。ここで作成された最短パス木は、最短パス木データとして保存される。そして、ステップＳ１０５において、マーチンのアルゴリズム等を用いて、最短パス木データをもとに、乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜Ｋ最短パスの検索を行う。このとき、ネットワークＡ、Ａ２、Ａ１、Ａ０を用いて、飛行機、新幹線、有料特急、普通列車等を利用したパス群をバランス良く求める。これらのパス群の中にはたまたま同一のパスが含まれることもあるので、それらを除去し、最終的に第１〜Ｋ最短パスを得る。得られた第１〜Ｋ最短パスは、複数パスデータに保存される。
【００６２】
つぎに、ステップＳ１０６において、第１〜Ｋ最短パスを短縮して第１〜Ｋ経路を得る。具体的には、第１〜Ｋ最短パスそれぞれに対して、路線変更アークをすべて除去し、さらに連続する同一路線名のアークをすべて短縮する。求められた複数経路は、複数経路データに保存される。本発明の最良の実施の形態において、ここで求められる経路を平均経路データと称す。本発明の最良の実施の形態においては、ステップＳ１０１ないしステップＳ１０６で算出された平均経路データに基づいて、終電や終電後列車を検索する。
【００６３】
このような本発明の最良の実施の形態に係る経路検索手段１２による経路検索方法によると、地点をノードに持ち、地点間の路線および徒歩乗換をアークで表現するネットワークにおいて、飛行機、新幹線、有料特急、普通列車等を利用した経路をバランス良く求めることができる。
【００６４】
終電列車割当手段３２は、平均経路探索手段３１で出力された平均経路データに基づいて、出発地から目的地までの交通機関の終電となる第１の終電データを算出する。終電列車割当手段３２は、従来通り、出発地Ａ駅から目的地Ｂ駅までの交通機関における終電の乗換データを出力する。終電列車割当手段３２が出力する乗換データは、出発地Ａ駅から目的地Ｂ駅まですべて交通機関で移動する場合の乗換データである。図１１に示す例によると、終電列車割当手段３２は、Ａ駅を２３：２５に出発し、Ｂ駅に００：０７に到着する乗換データを終電データとして出力する。
【００６５】
終電列車割当手段３２は、例えば午前３時などの当日扱いとなる時間の最後の時間までに到着する列車であって、最も遅く出発地を出発する列車を割り当てることにより、終電の乗換データを算出することができる。また終電列車割当手段３２は、終電と考えられる時間帯の各時間を発時間に設定して、最も遅くに出発地を出発し、当日扱いとなる時間までに到着する列車を検索しても良い。
【００６６】
終電後列車割当手段３３は、平均経路検索手段３１によって検索された平均経路データについて、第１の終電データにおける出発地の出発時刻の単位時間以上後に出発し、出発地から目的地まで移動する列車を割り当てて乗換データを算出する。さらに終電後列車割当手段３３は、この乗換データについて、日越え駅を算出して終電後列車到着駅を決定し、出発地から終電後列車到着駅までの交通機関の終電となる第２の終電データを算出する。終電後列車割当手段３３は、第２の終電データを含む移動データを算出する。ここで、日越え駅とは、翌日の列車の乗車駅となる。
【００６７】
終電列車割当手段３２は、Ａ駅を２３：３６に出発する列車を終電データとして検索している。本発明の最良の実施の形態において単位時間は１分であるので、終電後列車割当手段３３は、Ａ駅を２３：３７分以降に出発するＢ駅までの乗換データを検索する。Ａ駅を２３：３７分以降に出発する列車に乗車しても、Ａ駅を２３：３６分発が終電であるので、Ａ駅からＢ駅の乗換データを検索すると、翌日の始発以降の列車を利用する区間が発生する。例えば、Ａ駅からＣ駅までは当日扱いの列車で移動できるが、Ｃ駅からＢ駅までは翌日の始発以降の列車を利用する検索結果が出力される。
【００６８】
そこで、本発明の最良の実施の形態においては、翌日の列車の乗車駅となるＣ駅を、終電後列車到着駅として定義づける。Ａ駅からＣ駅までを交通機関の乗換で案内し、Ｃ駅からＢ駅までは交通機関によらない移動手段として、例えばタクシーや徒歩等で案内する。このように、終電後列車到着駅は、ユーザによって入力された終電について出発地の出発時刻よりも単位時間以降に出発する列車に乗車した場合に、当日扱いで移動できる駅であって、目的地Ｂ駅に最も近い駅である。
【００６９】
終電後列車割当手段３３の処理は、後に詳述する。
【００７０】
列車料金算出手段３４は、記憶装置１０７から運賃データ２４ａを読み出して、終電後列車割当手段３３によって算出された第２の終電データについて、出発地から終電後列車到着駅までの交通機関の運賃を算出する。経路検索サーバ１が終電列車割当手段３２によって算出された第１の終電データを算出する場合、第１の終電データについて、出発地から目的地までの交通機関の運賃を算出する。複数の平均経路について第１の終電データを算出する場合や、複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、列車料金算出手段３４は、各第１の終電データまたは第２の終電データについて、交通機関の運賃を算出する。
【００７１】
タクシー料金算出手段３５は、記憶装置１０７からタクシー料金データ２５ａを読み出して、終電後列車到着駅と目的地とのタクシー料金を算出する。タクシー料金算出手段３５は、終電後列車割当手段３３によって算出された第２の終電データについて、タクシー料金データ２５ａから、終電後列車到着駅と目的地間の料金を抽出する。タクシー料金算出手段３５は、記憶装置１０７から経路データ２２ａを読み出して終電後列車到着駅と目的地間の距離を算出し、算出された距離に基づいてタクシー料金を算出しても良い。複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、タクシー料金算出手段３５は、各第２の終電データについて、タクシー料金を算出する。
【００７２】
出力順序算出手段３６は、複数の終電後列車を割り当てて複数の第２の終電データを算出する場合、所要時間優先、乗換回数優先、運賃優先等の条件取得手段１１によって取得された条件に従って、複数の第２の終電データをソートして、ソート番号を付与する。
【００７３】
経路検索手段１２の各手段による出力結果は、結果データ２６ａとして、記憶装置１０７の結果データ記憶部２６に記憶される。
【００７４】
結果提示手段１３は、記憶装置１０７から結果データ２６ａを読み出して、クライアント端末２ａの表示装置に表示可能な形式にデータを成形して、クライアント端末２ａに送信する。
【００７５】
（終電後列車検索方法）
図７および図８を参照して、本発明の最良の実施の形態に係る終電列車検索手段３２および終電後列車割当手段３３による終電後列車割当処理を説明する。
【００７６】
まず図７を参照して、本発明の最良の実施の形態に係る終電後列車割当処理の概要を説明する。図７（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【００７７】
つぎに、図７（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図７（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで日越え駅とは、図７（ｂ）に示すように、出発地Ａ駅を時刻Ｔに出発する出発地Ａ駅から目的地Ｂ駅までの列車時刻を割り当てた際に、翌日の列車の乗車駅となる駅である。換言すると、日越え駅は、出発駅Ａ駅から、当日扱いの切符で移動できる駅であって、その平均経路上で最もＢ駅に近い駅である。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、終電後列車到着駅とする。図７（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。特に環状線等の路線においては、目的地までの駅の数や所要時間よりも、距離に基づいて終電後列車到着駅を決定するほうが、ユーザに便利な経路を検索することができる。
【００７８】
図７（ｂ）に示すように、終電後列車到着駅を決定すると、図７（ｃ）に示すように、出発駅Ａ駅から終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【００７９】
図８を参照して、本発明の最良の実施の形態に係る終電後列車割当処理を説明する。
【００８０】
まずステップＳ２０１において、変数「終電後列車到着駅」として出発地を設定する。ここで設定される駅は、後述するステップＳ２０７の判定に用いられる駅なので、どの駅にも該当しないダミーの駅や、nullでも良い。さらに、変数「Ｄ＿ｍｉｎ」として、出発地と目的地の距離を代入する。この変数Ｄ＿ｍｉｎには、日越え駅と目的地との距離の最大値より大きい値であれば、どのような数値が代入されても良い。
【００８１】
つぎに、ステップＳ２０２において、平均経路検索手段３１において検索された平均経路データのそれぞれについて、ステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８２】
ステップＳ２０２において、出発地から目的地までの列車であって、出発地を時刻Ｔに出発する列車を割り当てる。ステップＳ２０３において、ステップＳ２０２において割り当てられた列車について、日越え駅を特定する。具体的には、当日扱いの切符で行ける最も目的地に経路上で近い駅を日越え駅とする。例えば、ある交通機関が、夜の３時に下車するまで当日扱いの切符で行ける場合、夜の３時に最も近い時間に下車できる駅を日越え駅とする。
【００８３】
つぎに、ステップＳ２０４において、変数「Ｄ」に、日越え駅と目的地との距離を代入する。このとき終電後列車割当手段３３は、記憶装置１０７から経路データ２２ａを読み出して、日越え駅と目的地との距離を抽出する。さらにステップＳ２０５において、変数Ｄより変数Ｄ＿ｍｉｎが大きいか否かを判定する。大きくない場合、他の平均経路についてステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８４】
一方、変数Ｄより変数「Ｄ＿ｍｉｎ」が大きい場合、ステップＳ２０６において、変数「終電後列車到着駅」にステップＳ２０３で特定した日越え駅を代入するとともに、変数「Ｄ＿ｍｉｎ」に、当該終電後列車到着駅と目的地との距離を代入する。さらに、他の平均経路についてステップＳ２０２ないしステップＳ２０６の処理を繰り返す。
【００８５】
すべての平均経路についてステップＳ２０２ないしステップＳ２０６の処理が終了すると、ステップＳ２０７において、変数「終電後列車到着駅」が出発地であるか否か、具体的には、ステップＳ２０１で設定した初期値のままであるか否かを判定する。初期値の場合、終電後列車で当日扱いの切符で移動できる乗換データは案内できないとして、処理を終了する。一方、変数「終電後列車到着駅」が出発地でない場合、ステップＳ２０８において出発地から終電後列車到着駅までの区間について、終電を検索し、第２の終電データとして出力する。
【００８６】
このように本発明の最良の実施の形態に係る経路検索サーバ１によれば、所定の区間について終電を検索した後、その終電の出発駅の出発時刻より単位時間後にその出発駅を出発し、目的地までの列車を検索して日越え駅となる終電後列車到着駅を特定する。従って、通常の検索エンジンの入力データを工夫することで終電後の乗換データを容易に案内することができるので、開発を容易に行うことができる。
【００８７】
さらに、出発地から終電後列車到着駅までの終電を改めて検索することにより、出発地をさらに遅く出発する列車を案内することができる。
【００８８】
（第１の変形例）
つぎに図９ないし図１２を参照して本発明の第１の変形例を説明する。
【００８９】
まず図９を参照して、本発明の第１の変形例に係る終電後列車割当処理の概要を説明する。図９（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【００９０】
つぎに、図９（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第１の終電後列車到着駅とする。図９（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９１】
図９（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図９（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ１とする。
【００９２】
さらに、図９（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ１の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｄ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ４駅、Ｃ５駅およびＣ６駅とする。ここで、各日越え駅Ｃ４駅、Ｃ５駅およびＣ６駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第２の終電後列車到着駅（新たな終電後列車到着駅）とする。図９（ｄ）に示す例では、駅Ｃ４を第２の終電後列車到着駅とする。第２の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第２の終電後列車到着駅を選択することで、第２の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９３】
図９（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図９（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｃ４駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｃ４駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ２とする。
【００９４】
さらに、図１０（ａ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ２の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図１０（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ７駅およびＣ８駅とする。ここで、各日越え駅Ｃ７駅およびＣ８駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第３の終電後列車到着駅とする。図１０（ｂ）に示す例では、駅Ｃ７を第３の終電後列車到着駅とする。第３の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第３の終電後列車到着駅を選択することで、第３の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【００９５】
なお、図１０（ａ）に示す例では、上から２番目の経路において、出発時刻Ｔ２以降に出発し、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がない場合を示す。この場合、出発地Ａ駅が日越え駅となるので、当該経路の駅が終電後列車到着駅になることはない。
【００９６】
図１０（ｂ）に示すように、第３の終電後列車到着駅を決定すると、図１０（ｃ）に示すように、出発駅Ａ駅から第３の終電後列車到着駅Ｃ７駅の区間について、終電列車割当手段３２により終電を検索し、第４の終電データとする。さらに、第３の終電後列車到着駅Ｃ７駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ３とする。
【００９７】
ここで、出発地Ａ駅を時刻Ｔ３（時刻ＴＤ３の１分後）に出発するＡ駅からＢ駅までの列車割当を繰り返す。この列車割当は、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなるまで繰り返される。
【００９８】
図１０（ｃ）に示すように、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１０（ｄ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【００９９】
このような本発明の第１の変形例においては、図１１に示すように、終電後列車を複数提示することができる。図１１に示す画面例では、出発地Ａ駅から到着地Ｂ駅までの終電を表示した終電経路表示部６０１と、この終電後の列車でタクシーを利用した経路を表示する複数のタクシー利用経路表示部６０２ａ、６０２ｂ、６０２ｃおよび６０２ｄを有する。
【０１００】
図１２を参照して、本発明の第１の変形例に係る終電後列車割当処理を説明する。
【０１０１】
図１２に示すステップＳ３０１ないしステップＳ３０８は、図８を参照して説明した本発明の最良の実施の形態に係る終電後列車割当処理のステップＳ２０１ないしステップＳ２０８と同様である。
【０１０２】
具体的には、まずステップＳ３０１において、変数「終電後列車到着駅」（第１の終電後列車到着駅）として出発地を設定する。さらに、変数「Ｄ＿ｍｉｎ」として、出発地と目的地の距離を代入する。
【０１０３】
つぎに、平均経路検索手段３１において検索された平均経路データのそれぞれについて、ステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０４】
ステップＳ３０２において、出発地から目的地までの列車であって、出発地を時刻Ｔに出発する列車を割り当てる。ステップＳ３０３において、ステップＳ２０２において割り当てられた列車について、日越え駅を特定する。具体的には、当日扱いの切符で行ける最も目的地に経路上で近い駅を日越え駅とする。
【０１０５】
つぎに、ステップＳ３０４において、変数「Ｄ」に、日越え駅と目的地との距離を代入する。このとき終電後列車割当手段３３は、記憶装置１０７から経路データ２２ａを読み出して、日越え駅と目的地との距離を抽出する。さらにステップＳ３０５において、変数Ｄより変数Ｄ＿ｍｉｎが大きいか否かを判定する。大きくない場合、他の平均経路についてステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０６】
一方、変数Ｄより変数「Ｄ＿ｍｉｎ」が大きい場合、ステップＳ３０６において、変数「終電後列車到着駅」にステップＳ２０３で特定した日越え駅を代入するとともに、変数「Ｄ＿ｍｉｎ」に、当該終電後列車到着駅と目的地との距離を代入する。さらに、他の平均経路についてステップＳ３０２ないしステップＳ３０６の処理を繰り返す。
【０１０７】
すべての平均経路についてステップＳ３０２ないしステップＳ３０６の処理が終了すると、ステップＳ３０７において、変数「終電後列車到着駅」が出発地であるか否か、具体的には、ステップＳ２０１で設定した初期値のままであるか否かを判定する。初期値の場合、終電後列車で当日扱いの切符で移動できる乗換データは案内できないとして、処理を終了する。一方、変数「終電後列車到着駅」が出発地でない場合、ステップＳ３０８において出発地から終電後列車到着駅までの区間について、終電を検索し、第２の終電データとして出力する。
【０１０８】
さらにステップＳ３０９において、第２の終電データにおける出発地Ａ駅の出発時刻に単位時間１分を加算して、時刻Ｔ１を算出する。つぎに、ステップＳ３１０において、さらに、時刻Ｔ１以降に出発し出発地Ａ駅から目的地Ｂ駅に到着する列車を検索するために、終電後列車割当手段３３による終電後列車割当処理を実行する。この処理においても、出発地Ｓ３０７において出発地が終電後列車到着駅になると、処理を終了する。
【０１０９】
このように本発明の第１の変形例に係る終電後列車割当処理によれば、終電後列車到着駅が出発地に一致するまで、終電データの検索を継続するので、出発地から目的地までの終電後について、複数の経路を出力することができる。さらに、タクシー利用の距離が増えるとともに、出発地の出発時刻を遅くすることができるので、ユーザは自己の状況に応じて、適切な経路を選択することができる。
【０１１０】
（第２の変形例）
第２の変形例では、第１の変形例と同様に複数の終電後の経路データを出力することができるが、その算出方法が異なる。
【０１１１】
まず図１３を参照して、本発明の第２の変形例に係る終電後列車割当処理の概要を説明する。図１３（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【０１１２】
つぎに、図１３（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図１３（ｂ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ１駅、Ｃ２駅およびＣ３駅とする。ここで、各日越え駅Ｃ１駅、Ｃ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第１の終電後列車到着駅とする。図１３（ｂ）に示す例では、駅Ｃ１を終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１３】
図１３（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図１３（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ１駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ１駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ１とする。
【０１１４】
さらに、図１３（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ＿Ｃ１の１分後）に出発するＡ駅から第１の終電後列車到着駅Ｃ１駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、図９（ｄ）に示すように複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定し、それぞれＣ４駅およびＣ５駅とする。ここで、各日越え駅Ｃ４駅およびＣ５駅と、図１３（ｂ）で算出したＣ２駅およびＣ３駅のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第２の終電後列車到着駅とする。図１３（ｄ）に示す例では、駅Ｃ２を第２の終電後列車到着駅とする。第２の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第２の終電後列車到着駅を選択することで、第２の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１５】
図１３（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図１３（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｃ２駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｃ２駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ２とする。
【０１１６】
さらに、図１４（ａ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ＿Ｃ２の１分後）に出発するＡ駅から第２の終電後列車到着駅Ｃ２駅までの列車時刻を割り当てる。ここで、平均経路検索手段３１により複数の平均経路が求められた場合、複数の列車割当がなされる。このとき、各列車割当に対して、日越え駅を決定する。ここで、日越え駅Ｃ６駅と、既に算出された日越え駅Ｃ３、Ｃ４およびＣ５のうち、目的地Ｂ駅との距離が最短となる駅を検索し、第３の終電後列車到着駅とする。図１４（ｂ）に示す例では、駅Ｃ４を第３の終電後列車到着駅とする。第３の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように第３の終電後列車到着駅を選択することで、第３の終電後到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１１７】
図１４（ｂ）に示すように、第３の終電後列車到着駅を決定すると、図１４（ｃ）に示すように、出発駅Ａ駅から第３の終電後列車到着駅Ｃ４駅の区間について、終電列車割当手段３２により終電を検索し、第４の終電データとする。さらに、第３の終電後列車到着駅Ｃ４駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ＿Ｃ４とする。
【０１１８】
ここで、図１４（ａ）に示されている４つの経路のうち、上の二つは、図１３（ｄ）で算出された経路で、一番下は、図１３（ｂ）で算出された経路である。このように各処理ステップで算出された日越え駅のデータを引き継ぎ、最終的に、出発地Ａ駅と目的地Ｂ駅間のすべての終電列車を割り当てるまで繰り返される。
【０１１９】
図１４（ｃ）に示すように、出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１４（ｄ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【０１２０】
このような本発明の第２の変形例においては、出発地Ａ駅と目的地Ｂ駅間のすべての終電列車を検索するので、より多くの経路をユーザに提示することができる。
【０１２１】
つぎに図１５および図１６を参照して、本発明の第２の変形例に係る終電後列車割当処理を説明する。
【０１２２】
まず図１５に示すステップＳ３０１において、変数「終電後列車到着駅」（第１の終電後列車到着駅）として目的地を設定する。さらに、変数「到着候補駅リスト」を初期化する。この到着候補駅リストには、出発地から目的地までの各経路上に位置する日越え駅が挿入される。この到着候補駅リストが空になるまで、ステップＳ４０２ないしステップＳ４０７の処理を繰り返す。
【０１２３】
つぎに、ステップＳ４０２において、日越え駅検索処理を実行する。これにより、日越え駅がある場合は、到着候補駅リストに日越え駅が挿入される。この処理は後に詳述する。
【０１２４】
ステップＳ４０３において、到着候補駅リストが空であるか否かを検索する。到着候補駅リストが空の場合、そのまま処理を終了する。到着候補駅リストに、到着候補駅が挿入されている場合、ステップＳ４０４において、到着候補駅リストの駅から、目的地との距離が最短の駅を抽出するとともに削除する。さらに、ステップＳ４０５において、終電後列車到着駅に、ステップＳ４０４において抽出された駅を挿入する。
【０１２５】
ステップＳ４０６において、出発地から終電後列車到着駅の間の区間について終電検索する。ステップＳ４０７において、ステップＳ４０６で算出した終電の出発地における出発時刻に単位時間を足して、時刻Ｔを算出する。
【０１２６】
到着候補駅リストが空になるまで、ステップＳ４０２ないしステップＳ４０７の処理を繰り返すと、終電後列車割当処理を終了する。
【０１２７】
つぎに図１６を参照して、図１５のステップＳ４０２に相当する日越え駅検索処理を説明する。日越え駅検索処理は、平均経路検索手段３１によって算出されたすべての平均経路についてステップＳ４５１ないしステップＳ４５４の処理を繰り返す。
【０１２８】
まずステップＳ４５１において、出発地を時刻Ｔに出発する出発地から終電後列車到着駅の列車を割り当てる。ステップＳ４５２において、ステップＳ４５１で割り当てた列車について日越え駅を特定する。
【０１２９】
ステップＳ４５３において日越え駅と出発地が同じか否かを判定する。同じ場合、他の平均経路についてステップＳ４５１の処理を実行する。一方日越え駅と出発地が異なる場合、ステップＳ４５４において、到着候補駅リストにステップＳ４５２で特定した日越え駅を追加して、他の平均経路についてステップＳ４５１の処理を実行する。
【０１３０】
このように本発明の第２の変形例に係る終電後列車割当処理によれば、出発地から目的地までの終電後の時間帯について、すべての日越え駅を抽出することができるので、より多くの終電後列車を割り当てることができる。
【０１３１】
（第３の変形例）
つぎに図１７および図１８を参照して本発明の第３の変形例を説明する。
【０１３２】
まず図１７を参照して、本発明の第１の変形例に係る終電後列車割当処理の概要を説明する。図１７（ａ）に示すように、終電列車検索手段３２が、出発地Ａ駅から目的地Ｂ駅までの終電を検索し、第１の終電データとする。ここで、出発地Ａ駅の出発時刻を、ＴＤ０とする。
【０１３３】
つぎに、図１７（ｂ）に示すように、出発地Ａ駅を時刻Ｔ（時刻ＴＤ０の１分後）に出発するＡ駅からＢ駅までの列車時刻を割り当てる。このとき、列車割当に対して、日越え駅を決定し、Ｃ駅とする。複数の経路についてそれぞれ日越え駅が決定された場合、そのうち目的地のＢ駅に最も近い日越え駅を、第１の終電後列車到着駅とする。第１の終電後列車到着駅から目的地Ｂ駅の距離が最短になるように終電後列車到着駅を選択することで、第１の終電後列車到着駅から目的地Ｂ駅の移動が最も楽になる経路を検索することができる。
【０１３４】
図１７（ｂ）に示すように、第１の終電後列車到着駅を決定すると、図１７（ｃ）に示すように、出発駅Ａ駅から第１の終電後列車到着駅Ｃ駅の区間について、終電列車割当手段３２により終電を検索し、第２の終電データとする。さらに、第１の終電後列車到着駅Ｃ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ１とする。
【０１３５】
さらに、図１７（ｄ）に示すように、出発地Ａ駅を時刻Ｔ１（時刻ＴＤ１の１分後）に出発するＡ駅からＣ駅までの列車時刻を割り当てる。このとき、列車割当に対して、日越え駅を決定し、Ｄ駅とする。ここで、複数の経路についてそれぞれ日越え駅が決定された場合、そのうち第１の終電後列車到着駅のＣ駅に最も近い日越え駅を、第２の終電後列車到着駅とする。
【０１３６】
図１７（ｄ）に示すように、第２の終電後列車到着駅を決定すると、図１７（ｅ）に示すように、出発駅Ａ駅から第２の終電後列車到着駅Ｄ駅の区間について、終電列車割当手段３２により終電を検索し、第３の終電データとする。さらに、第２の終電後列車到着駅Ｄ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。ここで、出発地Ａ駅の出発時刻を、ＴＤ２とする。
【０１３７】
さらに、図１７（ｆ）に示すように、出発地Ａ駅を時刻Ｔ２（時刻ＴＤ２の１分後）に出発するＡ駅からＤ駅までの列車時刻を割り当て、図１７（ｄ）および図１７（ｅ）と同様の処理を、終電後列車到着駅と出発地とが一致するまで繰り返す。
【０１３８】
出発地Ａ駅から到着地Ｂ駅まで、当日扱いの切符で移動できる経路がなくなると、図１７（ｇ）に示すように、出発地Ａ駅から目的地Ｂ駅までの区間についてタクシーで移動する場合の料金や所要時間を検索する。
【０１３９】
このような本発明の第３の変形例においては、終電後列車到着駅を目的地として処理を繰り返す。
【０１４０】
図１８を参照して、本発明の第３の変形例に係る終電後列車割当処理を説明する。
【０１４１】
図１８に示すステップＳ５０１ないしステップＳ５０９は、図１２を参照して説明した本発明の第１の変形例に係る終電後列車割当処理のステップＳ３０１ないしステップＳ３０９と同様である。
【０１４２】
ステップＳ５１０においてさらに、時刻Ｔ１以降に出発し出発地Ａ駅から終電後列車到着駅に到着する列車を検索するために、終電後列車割当手段３３による終電後列車割当処理を実行する。この処理においても、出発地Ｓ５０７において出発地が終電後列車到着駅になると、処理を終了する。
【０１４３】
なお、本発明の第２の変形例においては、図１２のステップＳ３１０において、出発地から目的地間の終電を検索している。一方、本発明の第３の変形例においては、図１８のステップＳ５１０において、出発地から終電後列車到着駅間の終電を検索している。
【０１４４】
（その他の実施の形態）
上記のように、本発明の最良の実施の形態および第１ないし第３の変形例によって記載したが、この開示の一部をなす論述および図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例および運用技術が明らかとなる。
【０１４５】
例えば、本発明の最良の実施の形態に記載した経路検索サーバ１は、図１に示すように一つのハードウェア上に構成されても良いし、その機能や処理数に応じて複数のハードウェア上に構成されても良い。
【０１４６】
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１４７】
【図１】本発明の最良の実施の形態に係る経路検索システムのシステム構成と、経路検索サーバの機能ブロックを説明する図である。
【図２】本発明の最良の実施の形態に係る経路検索サーバのハードウェア構成図である。
【図３】本発明の最良の実施の形態に係る経路検索サーバによる経路検索処理の概要を説明するフローチャートである。
【図４】本発明の最良の実施の形態に係る経路検索処理におけるネットワークの一例を説明する図である。
【図５】本発明の最良の実施の形態に係る経路検索処理におけるクリーク化されたネットワークの一例を説明する図である。
【図６】本発明の最良の実施の形態に係る経路検索手段の平均経路検索手段による平均経路検索処理を説明するフローチャートである。
【図７】本発明の最良の実施の形態に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。
【図８】本発明の最良の実施の形態に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図９】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その１）
【図１０】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その２）
【図１１】本発明の最良の実施の形態に係る経路検索サーバが、検索結果を表示する画面の一例である。
【図１２】本発明の第１の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図１３】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その１）
【図１４】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。（その２）
【図１５】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理を説明するフローチャートである。
【図１６】本発明の第２の変形例に係る経路検索手段の終電後列車割当手段による日越え駅検索処理を説明するフローチャートである。
【図１７】本発明の第３の変形例に係る経路検索手段の終電後列車割当手段による終電後列車割当処理の概要を説明する図である。
【図１８】本発明の第３の変形例に係る経路検索手段の終電後列車割当手段による日越え駅検索処理を説明するフローチャートである。
【図１９】一般的な経路検索サーバが、検索結果を表示する画面の一例である。
【符号の説明】
【０１４８】
１ 経路検索サーバ
２ クライアント端末
３ 通信ネットワーク
１１ 条件取得手段
１２ 経路検索手段
１３ 結果提示手段
２１ 検索条件データ記憶部
２２ 経路データ記憶部
２３ 時刻表データ記憶部
２４ 運賃データ記憶部
２５ タクシー料金データ記憶部
２６ 結果データ記憶部
３１ 平均経路探索手段
３２ 終電列車割当手段
３３ 終電後列車割当手段
３４ 列車料金算出手段
３５ タクシー料金算出手段
３６ 出力順序算出手段
１０１ 中央処理制御装置
１０２ ＲＯＭ
１０３ ＲＡＭ
１０４ 入力装置
１０５ 表示装置
１０６ 通信制御装置
１０７、３０ 記憶装置
１０８ リムーバブルディスク
１０９ 入出力インタフェース
１１０ バス
【特許請求の範囲】
【請求項１】
出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバであって、
交通機関の経路と、前記経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、
前記乗換の条件を取得する条件取得手段と、
前記記憶装置から前記経路データを読み出し、前記条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、
前記平均経路データに基づいて、前記出発地から前記目的地までの前記交通機関の終電となる第１の終電データを算出する終電列車割当手段と、
前記平均経路検索手段によって検索された平均経路データについて、前記第１の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、前記出発地から前記終電後列車到着駅までの前記交通機関の終電となる第２の終電データを算出し、前記第２の終電データを含む移動データを算出する終電後列車割当手段と、
前記移動データを出力する結果提示手段
とを備えることを特徴とする経路検索サーバ。
【請求項２】
前記交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、前記記憶装置に記憶するタクシー料金データ記憶手段と、
前記記憶装置から前記タクシー料金データを読み出して、前記終電後列車到着駅と前記目的地とのタクシー料金を算出するタクシー料金算出手段をさらに備え、
前記移動データは、前記タクシー料金算出手段によって算出された前記タクシー料金を含む
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項３】
前記平均経路検索手段はさらに、前記経路上の駅間の距離を記憶し、
前記平均経路検索手段が複数の平均経路データを算出した場合、
前記終電後列車割当手段は、前記平均経路検索手段が算出したすべての平均経路データについて前記乗換データおよび前記日越え駅を算出し、前記目的地との距離が最も小さい日越え駅を前記終電後列車到着駅とする
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項４】
前記終電後列車割当手段は、さらに、
前記第２の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、前記出発地から前記新たな終電後列車到着駅までの前記交通機関の終電となる第３の終電データを算出し、前記第３の終電データを含む新たな移動データを算出する
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項５】
前記終電後列車割当手段は、前記新たな終電後列車到着駅が前記出発地になるまで、前記新たな移動データを算出する処理を繰り返す
ことを特徴とする請求項４に記載の経路検索サーバ。
【請求項６】
前記タクシー料金算出手段はさらに、前記新たな終電後列車到着駅と前記目的地との新たなタクシー料金を算出し、
前記新たな移動データは、前記タクシー料金算出手段によって算出された前記新たなタクシー料金を含む
ことを特徴とする請求項４または５に記載の経路検索サーバ。
【請求項７】
出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索プログラムであって、
交通機関の経路と、前記経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、
前記乗換の条件を取得する条件取得手段と、
前記記憶装置から前記経路データを読み出し、前記条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、
前記平均経路データに基づいて、前記出発地から前記目的地までの前記交通機関の終電となる第１の終電データを算出する終電列車割当手段と、
前記平均経路検索手段によって検索された平均経路データについて、前記第１の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、前記出発地から前記終電後列車到着駅までの前記交通機関の終電となる第２の終電データを算出し、前記第２の終電データを含む移動データを算出する終電後列車割当手段と、
前記移動データを出力する結果提示手段
とを、コンピュータに機能させることを特徴とする経路検索プログラム。
【請求項８】
前記交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、前記記憶装置に記憶するタクシー料金データ記憶手段と、
前記記憶装置から前記タクシー料金データを読み出して、前記終電後列車到着駅と前記目的地とのタクシー料金を算出するタクシー料金算出手段をさらに前記コンピュータに機能させ、
前記移動データは、前記タクシー料金算出手段によって算出された前記タクシー料金を含む
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項９】
前記平均経路検索手段はさらに、前記経路上の駅間の距離を記憶し、
前記平均経路検索手段が複数の平均経路データを算出した場合、
前記終電後列車割当手段は、前記平均経路検索手段が算出したすべての平均経路データについて前記乗換データおよび前記日越え駅を算出し、前記目的地との距離が最も小さい日越え駅を前記終電後列車到着駅とする
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項１０】
前記終電後列車割当手段は、さらに、
前記第２の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、前記出発地から前記新たな終電後列車到着駅までの前記交通機関の終電となる第３の終電データを算出し、前記第３の終電データを含む新たな移動データを算出する
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項１１】
前記終電後列車割当手段は、前記新たな終電後列車到着駅が前記出発地になるまで、前記新たな移動データを算出する処理を繰り返す
ことを特徴とする請求項１０に記載の経路検索プログラム。
【請求項１２】
前記タクシー料金算出手段はさらに、前記新たな終電後列車到着駅と前記目的地との新たなタクシー料金を算出し、
前記新たな移動データは、前記タクシー料金算出手段によって算出された前記新たなタクシー料金を含む
ことを特徴とする請求項１０または１１に記載の経路検索プログラム。
【請求項１】
出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索サーバであって、
交通機関の経路と、前記経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、
前記乗換の条件を取得する条件取得手段と、
前記記憶装置から前記経路データを読み出し、前記条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、
前記平均経路データに基づいて、前記出発地から前記目的地までの前記交通機関の終電となる第１の終電データを算出する終電列車割当手段と、
前記平均経路検索手段によって検索された平均経路データについて、前記第１の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、前記出発地から前記終電後列車到着駅までの前記交通機関の終電となる第２の終電データを算出し、前記第２の終電データを含む移動データを算出する終電後列車割当手段と、
前記移動データを出力する結果提示手段
とを備えることを特徴とする経路検索サーバ。
【請求項２】
前記交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、前記記憶装置に記憶するタクシー料金データ記憶手段と、
前記記憶装置から前記タクシー料金データを読み出して、前記終電後列車到着駅と前記目的地とのタクシー料金を算出するタクシー料金算出手段をさらに備え、
前記移動データは、前記タクシー料金算出手段によって算出された前記タクシー料金を含む
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項３】
前記平均経路検索手段はさらに、前記経路上の駅間の距離を記憶し、
前記平均経路検索手段が複数の平均経路データを算出した場合、
前記終電後列車割当手段は、前記平均経路検索手段が算出したすべての平均経路データについて前記乗換データおよび前記日越え駅を算出し、前記目的地との距離が最も小さい日越え駅を前記終電後列車到着駅とする
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項４】
前記終電後列車割当手段は、さらに、
前記第２の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、前記出発地から前記新たな終電後列車到着駅までの前記交通機関の終電となる第３の終電データを算出し、前記第３の終電データを含む新たな移動データを算出する
ことを特徴とする請求項１に記載の経路検索サーバ。
【請求項５】
前記終電後列車割当手段は、前記新たな終電後列車到着駅が前記出発地になるまで、前記新たな移動データを算出する処理を繰り返す
ことを特徴とする請求項４に記載の経路検索サーバ。
【請求項６】
前記タクシー料金算出手段はさらに、前記新たな終電後列車到着駅と前記目的地との新たなタクシー料金を算出し、
前記新たな移動データは、前記タクシー料金算出手段によって算出された前記新たなタクシー料金を含む
ことを特徴とする請求項４または５に記載の経路検索サーバ。
【請求項７】
出発地から目的地までの移動データであって、時刻表に従って運行する交通機関を利用した終電後の移動データを検索する経路検索プログラムであって、
交通機関の経路と、前記経路の駅とが関連づけられた経路データを、記憶装置に記憶する経路データ記憶手段と、
前記乗換の条件を取得する条件取得手段と、
前記記憶装置から前記経路データを読み出し、前記条件取得手段によって取得された条件に従って、平均経路データを検索して出力する平均経路検索手段と、
前記平均経路データに基づいて、前記出発地から前記目的地までの前記交通機関の終電となる第１の終電データを算出する終電列車割当手段と、
前記平均経路検索手段によって検索された平均経路データについて、前記第１の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する列車を割り当てて乗換データを算出するとともに、該乗換データについて、翌日の列車の乗車駅となる日越え駅を算出して終電後列車到着駅を決定し、前記出発地から前記終電後列車到着駅までの前記交通機関の終電となる第２の終電データを算出し、前記第２の終電データを含む移動データを算出する終電後列車割当手段と、
前記移動データを出力する結果提示手段
とを、コンピュータに機能させることを特徴とする経路検索プログラム。
【請求項８】
前記交通機関の各駅間のタクシー料金が関連づけられたタクシー料金データを、前記記憶装置に記憶するタクシー料金データ記憶手段と、
前記記憶装置から前記タクシー料金データを読み出して、前記終電後列車到着駅と前記目的地とのタクシー料金を算出するタクシー料金算出手段をさらに前記コンピュータに機能させ、
前記移動データは、前記タクシー料金算出手段によって算出された前記タクシー料金を含む
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項９】
前記平均経路検索手段はさらに、前記経路上の駅間の距離を記憶し、
前記平均経路検索手段が複数の平均経路データを算出した場合、
前記終電後列車割当手段は、前記平均経路検索手段が算出したすべての平均経路データについて前記乗換データおよび前記日越え駅を算出し、前記目的地との距離が最も小さい日越え駅を前記終電後列車到着駅とする
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項１０】
前記終電後列車割当手段は、さらに、
前記第２の終電データにおける前記出発地の出発時刻の単位時間以上後に出発し、前記出発地から前記目的地まで移動する新たな乗換データを算出するとともに、該新たな乗換データについての新たな日越え駅を算出して新たな終電後列車到着駅を決定し、前記出発地から前記新たな終電後列車到着駅までの前記交通機関の終電となる第３の終電データを算出し、前記第３の終電データを含む新たな移動データを算出する
ことを特徴とする請求項７に記載の経路検索プログラム。
【請求項１１】
前記終電後列車割当手段は、前記新たな終電後列車到着駅が前記出発地になるまで、前記新たな移動データを算出する処理を繰り返す
ことを特徴とする請求項１０に記載の経路検索プログラム。
【請求項１２】
前記タクシー料金算出手段はさらに、前記新たな終電後列車到着駅と前記目的地との新たなタクシー料金を算出し、
前記新たな移動データは、前記タクシー料金算出手段によって算出された前記新たなタクシー料金を含む
ことを特徴とする請求項１０または１１に記載の経路検索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２０１０−５２５７６（Ｐ２０１０−５２５７６Ａ）
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願番号】特願２００８−２１９４６５（Ｐ２００８−２１９４６５）
【出願日】平成２０年８月２８日（２００８．８．２８）
【出願人】（３０３０２６１３２）株式会社駅探 (5)
【Ｆターム（参考）】
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願日】平成２０年８月２８日（２００８．８．２８）
【出願人】（３０３０２６１３２）株式会社駅探 (5)
【Ｆターム（参考）】
[ Back to top ]