ナビゲーションシステム、経路探索サーバおよび経路探索方法
【課題】経路探索の負荷を軽減し効率的に出発地から目的地までの経路を探索することができ、また、最適経路を見落とす恐れなく、効率的に探索範囲を限定できるナビゲーションシステムを提供する。
【解決手段】ナビゲーションシステム１０はノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータ３０３と、交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータ３０２とを備え、経路探索手段３１４は、操作・入力手段２１７により設定された出発地と目的地の情報に従って平均コストネットワークデータ３０３に基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について時刻表ネットワークデータ３０２に基づいて各候補経路における最適経路を探索する。
【解決手段】ナビゲーションシステム１０はノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータ３０３と、交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータ３０２とを備え、経路探索手段３１４は、操作・入力手段２１７により設定された出発地と目的地の情報に従って平均コストネットワークデータ３０３に基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について時刻表ネットワークデータ３０２に基づいて各候補経路における最適経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望の出発地から目的地まで、交通機関を利用した経路を含む経路を探索して案内する経路探索システムに関するものであり、特に、交通機関を利用した経路を効率よく、かつ、最適な案内経路が経路探索から漏れることがないようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法に関するものである。本発明は、経路探索のためのネットワークデータを、平均コストをベースとした平均コストネットワークデータと、運行時刻表をベースとした時刻表ネットワークデータとの別個のデータで構成し、平均コストネットワークデータを用いて広域を対象とした経路探索を行い複数の候補経路を探索し、候補経路のみについて時刻表ネットワークデータを用いて案内経路を探索するようにしたナビゲーション、経路探索サーバおよび経路探索方法に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
このような経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのままあるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１０】
交通機関を利用した経路探索を行う経路探索方法は、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に交通ネットワーク経路探索方法として開示されている。この特許文献２に開示された交通ネットワーク経路探索方法は、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法である。
【００１１】
この方法においては、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するようにしている。
【００１２】
通常の経路探索に使用される道路網や交通機関の路線網のデータは以下のように構成されている。すなわち、例えば、道路が図５に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００１３】
すなわち、図５において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図５では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００１４】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図５において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００１５】
図５ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００１６】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図６に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図６において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図６では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００１７】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図６に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。この意味で交通ネットワークデータは運行時刻表をベースとしたネットワークデータであり、時刻表ネットワークデータということができる。
【００１８】
図６に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００１９】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００２０】
例えば、図６において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００２１】
このように交通機関のネットワークデータは、網の数が圧倒的に多い道路のネットワークデータに比べて路線数は格段に少ない（網の数が少ない）ものの網を運行する個々の電車や、列車（交通手段）の数が膨大であり全ての運行時刻が加味されたネットワークデータになり、かつ個々の交通手段の運行時刻に基づく組み合わせを経路探索する必要があり、経路探索における演算処理の付加が大きくなるという問題点がある。
【００２２】
このような問題点を解決するため、例えば、下記の特許文献３（特開平１０−３３４３８７号公報）には、経路を探索すべき出発地と目的地とから経路探索の範囲を限定することにより経路探索の処理負荷を軽減するようにした最適乗継系列探索方法の発明が開示されている。経路探索の範囲を限定する方法としては、出発地と目的地を結ぶ線を基線とし、その前後左右を含む長方形あるいは楕円等の図形（領域）で囲み、その領域外の地域については探索の範囲外とする方法、あるいは、出発地と目的地を結ぶ線を基線とし、その基線の外側の方向に対して、ある地域単位に探索禁止地域を設ける方法が提案されている。
【００２３】
「基線の外側方向」とは、出発地においては目的地と逆方向が探索禁止地域の対象となり、目的地においては出発地と逆方向が探索禁止地域となる。この方法においては、あらかじめ地域ごと（たとえば県単位）の探索禁止をテーブルで定めておき、出発地と目的地が定まった時点で、禁止の範囲が特定されるようにしている。
【００２４】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図４、図７）
【特許文献３】特開平１０−３３４３８７号公報（図５、段落［００４０］、［００４１］）
【発明の開示】
【発明が解決しようとする課題】
【００２５】
しかしながら、上記特許文献３に開示されたように、出発地と目的地とから予め経路探索の範囲を限定して経路探索する場合、どのように経路探索範囲を制限して経路探索したら最適な案内経路が漏れることなく得られるか、その制限方法を最適化する解を見出してはいない。このため、次のような問題点が生ずる。
【００２６】
例えば、図７に示すように「東京（TOKYO）」から岐阜県の「中津川（NAKATSUGAWA）」への経路を探索する場合、代表的な経路には「東京（TOKYO）」から「名古屋（NAGOYA）」まで新幹線を利用し、「名古屋（NAGOYA）」から特急に乗り換えて「中津川（NAKATSUGAWA）」に至る第１ルートＲＴ１（図７における実線の経路）があげられる。これに対して、距離的に最短の経路としては中央線を用いた第２ルートＲＴ２（図７における点線の経路）がある。
【００２７】
このような出発地と目的地の場合、第１ルートＲＴ１は新幹線を利用するために所要時間は圧倒的に短く実用的な経路である。これに対して第２ルートは距離的には最短経路ではあるが、在来線特急を利用しても第１ルートに比べ所要時間が長くなる。特に岐阜県に居住する人はこのことを経験的に知っている。
【００２８】
上記特許文献３に開示されたように経路探索の範囲を制限する場合、上記のような出発地と目的地を結ぶ経路探索においては、名古屋が探索範囲に含まれるようにしないと、第１ルートＲＴ１を探索できないことになる。上記のような例に限らず、航空機や船舶まで含めた各種の交通機関を含めたマルチモーダルな経路探索では、交通機関の移動速度に大きな差があり、一旦目的地から遠く離れた地点まで移動して、そこから目的地に移動するルートをとるほうが最適であるケースが多く含まれる。
【００２９】
このような出発地と目的地の事例は多々存在し、探索範囲の決定に苦慮する。最適経路が漏れないように経路探索しようとすると、経路探索の範囲をできるだけ広くとることが必要になる。経路探索範囲を広くとると、経路探索の処理負荷が大きくなり高速、効率的に最適経路を探索することができなくなる。逆に探索範囲を狭く制限すると、高速な探索処理はできるが、最適経路が漏れる可能性が大きくなる。交通機関を用いた経路の探索にはこのような相反する課題が生じる。
【００３０】
本願の発明者はこのような問題点を解消すべく種々検討を重ねた結果、通常の交通機関を利用した経路探索に用いられる時刻表データをベースとした時刻表ネットワークデータの他に、全ての交通機関の経路ネットワークを平均コストのみで表現した平均コストネットワークデータを別に用意し、先ず、平均コストネットワークデータを用いて出発地から目的地に至る候補経路を探索し、候補経路のみについて時刻表ネットワークデータを用いた経路探索をすれば上記問題点を解消しえることに想到して本発明を完成するに至ったものである。
【００３１】
すなわち、本発明は前記の問題点を解消することを課題とし、経路探索の負荷を軽減し効率的に出発地から目的地までの経路を探索することができ、また、最適経路を見落とす恐れなく、効率的に探索範囲を限定できるナビゲーションシステム、経路探索サーバおよび経路探索方法を提供することを目的とするものである。
【課題を解決するための手段】
【００３２】
前記課題を解決するために、本願の請求項１にかかる発明は、
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする。
【００３３】
本願の請求項２にかかる発明は、請求項１にかかる発明において、前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする。
【００３４】
本願の請求項３にかかる発明は、請求項１にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする。
【００３５】
本願の請求項４にかかる発明は、請求項３にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする。
【００３６】
本願の請求項５にかかる発明は、請求項１にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【００３７】
また、本願の請求項６にかかる発明は、
表示手段と、操作・入力手段と、を備え、操作・入力手段により設定した出発地と目的地とを含む経路探索要求を経路探索サーバに送信し、経路探索サーバから配信された案内経路データを前記表示手段に表示する端末装置にネットワークを介して接続される経路探索サーバにおいて、
前記経路探索サーバは、ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする。
【００３８】
本願の請求項７にかかる発明は、請求項６にかかる発明において、前記経路探索サーバは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする。
【００３９】
本願の請求項８にかかる発明は、請求項６にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする。
【００４０】
本願の請求項９にかかる発明は、請求項８にかかる発明において、前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする。
【００４１】
本願の請求項１０にかかる発明は、請求項６にかかる発明において、前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【００４２】
また、本願の請求項１１にかかる発明は、
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索手段が、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索する第１のステップと、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する第２のステップとを有することを特徴とする。
【００４３】
本願の請求項１２にかかる発明は、請求項１１にかかる発明において、前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段が前記所定数の候補経路の時刻表ネットワークデータのみを編集するステップを有し、前記第２のステップは、経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する処理であることを特徴とする。
【００４４】
本願の請求項１３にかかる発明は、請求項１１にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記第１のステップは、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する処理を含むことを特徴とする。
【００４５】
本願の請求項１４にかかる発明は、請求項１３にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集するステップを有し、前記第１のステップは前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する処理であることを特徴とする。
【００４６】
本願の請求項１５にかかる発明は、請求項１１にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集するステップを有し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【発明の効果】
【００４７】
請求項１にかかる発明においては、ナビゲーションシステムはノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータとを備え、経路探索手段は、操作・入力手段により設定された出発地と目的地の情報に従って平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について時刻表ネットワークデータに基づいて各候補経路における最適経路を探索する。
【００４８】
このような構成によれば、平均コストネットワークデータを用いて出発地と目的地との間の候補経路を探索するから、経路探索範囲を広くとることができ、経路探索負荷も増大することがない。また、候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【００４９】
請求項２にかかる発明は、請求項１にかかる発明において、ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力する。
【００５０】
このような構成によれば、平均コストネットワークデータを用いて探索した候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【００５１】
請求項３にかかる発明は、請求項１にかかる発明において、平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する。
【００５２】
請求項４にかかる発明は、請求項３にかかる発明において、ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する。
【００５３】
このような構成によれば、平均コストネットワークデータから、探索条件として設定された交通手段に関する平均コストネットワークのみを対象にした経路探索を行うから、経路探索負荷を更に軽減することができるようになる。
【００５４】
請求項５にかかる発明は、請求項１にかかる発明において、ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにする。
【００５５】
このような構成によれば、災害や事故により交通機関に一時運休する区間が生じた場合であっても、時刻表ネットワークデータを更新することなく、平均コストネットワークデータの更新のみで容易に対応することができるようになる。
【００５６】
また、請求項６ないし請求項１０にかかる発明においては、それぞれ請求項１ないし請求項５にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになり、請求項１１ないし請求項１５にかかる発明においては、それぞれ請求項１ないし請求項５にかかるナビゲーションシステムにおける経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００５７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００５８】
図１は、本発明の実施例１にかかるナビゲーションシステムの構成を示す図である。ナビゲーションシステム１０は、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。なお、本実施例１においては、経路探索、案内経路を提供するナビゲーションシステム１０を具体例として説明するが、本発明はこれに限ることなく、スタンドアロンタイプのナビゲーションシステムになどにも適用可能である。
【００５９】
経路探索サーバ３０は、経路探索のため道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを時刻表ネットワークデータとして蓄積したデータベース（ＤＢ２）、交通ネットワークの各リンクを平均のリンクコストで表現した平均コストネットワークデータを蓄積したデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。ここで、平均コストネットワークデータとは、交通ネットワークを構成する各リンクのリンクコストを平均的なリンクコストのみで表したものであり、例えば、鉄道であれば普通列車のコストを平均コストとして使用する。
【００６０】
経路探索サーバは、先ず、最初に交通機関を利用する経路部分について、平均コストネットワークデータを用いて経路探索し、所定数の候補経路を探索する。このとき、平均コストに影響を与えるパラメータとして、交通手段の選択条件を設定し、例えば、航空機や特急の利用を認めない設定の場合には、航空機利用の経路区間のリンクコストを編集し、候補経路として探索されないようにする。リンクコストの編集は、該当するリンクコストを無限大にし、または、利用禁止フラグを立て、あるいは該当リンクを平均コストネットワークから除外するなどの方法をとることができる。
【００６１】
平均コストネットワークデータに基づく経路探索は、ダイクストラ法による経路探索を適用するが、交通機関のネットワークは道路ネットワークに比べて格段にリンク数が少ない。カーナビが道路ネットワークデータを用いて経路探索を行う場合と比較しても、平均コストネットワークデータを用いた経路探索ならば探索範囲を限定しなくても、容易に経路探索が行える。従来は、いきなり時刻表ネットワークでの経路探索を行おうとしたので、リンクに相当する交通手段（電車やバス）の運行本数が多くて演算負荷が大きくなっていたものである。ダイクストラ法ではまず最小コスト経路が最初に求められ、例えば、マーチンのアルゴリズムを用いて第Ｋ最短経路まで複数の候補経路を求めることが出来る。ここでは、内部的に５〜２０経路ほど（多めに）の候補経路を求めておく。
【００６２】
次いで経路探索サーバは、上記のようにして探索した候補経路に限定して、時刻表をベースとした通常の時刻表ネットワークデータ（探索条件として設定した交通手段の時刻表ネットワークデータに限定することもできる）を参照して経路探索を行うので、経路探索の対象となる時刻表データを格段に減らすことが出来る。なお、詳細には、平均コストネットワークデータによる経路探索で求められた候補経路の１つ１つに応じて時刻表ネットワークデータを用いて経路探索し、乗車する交通手段（案内経路）を求める方法、平均コストネットワークデータを用いた経路探索で求められた候補経路の全経路の時刻表ネットワークデータを探索範囲として経路探索し、乗車する交通手段を求める方法のいずれでも良い。これにより、出発時間や到着時間の条件にあう交通手段（案内経路）が探索される。
【００６３】
平均コストネットワークデータを用いて探索された候補経路であっても、実際の時刻表ネットワークデータを用いて時刻表探索を行うと、平均コストとは異なる所要時間で経路が求められる。それをソートして、最適なものから結果表示する。乗り継ぎが良くない経路はソートで順位を下げるが、所要時間の短い経路はソートでも生き残ることになり、最適な案内経路から順に利用者に案内することができる。
このような経路探索を行えば、経路探索の演算負荷を増大することなく、効率的に最適経路を見落とすことなく探索、案内することができるようになる。
【００６４】
図２は、図１のナビゲーションシステム１０の概略構成を示すブロック図である。端末装置２０は、例えばＧＰＳ受信機などからなるＧＰＳ測位手段２１３を搭載した携帯電話機であり、制御手段２１１、通信手段２１２、配信要求手段２１４、データ記憶手段２１５、表示手段２１６、操作・入力手段２１７などを備えて構成されている。利用者は、徒歩あるいは交通機関を移動手段として選択し、徒歩や交通機関を利用した経路案内を受けることができ、また、自動車の助手席に同乗した時には移動手段として自動車を選択して経路案内を受けることができる。
【００６５】
制御手段２１１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２１７は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力のためのものであり、出力手段である表示手段２１６に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２１６は操作・入力手段２１７の一部としても機能する。通信手段２１２は、ネットワーク１２を介して経路探索サーバ３０と通信するためのインターフェースである。
【００６６】
利用者が経路探索サーバ３０に経路探索を依頼しようとする場合、端末装置２０において操作・入力手段２１７を操作し、表示手段２１６に表示されるサービスメニューから経路探索を選択し、現在位置、目的地、移動手段（自動車、徒歩、交通機関あるいは徒歩と交通機関併用など）などの経路探索条件を入力する。経路探索条件は配信要求手段２１４で経路探索サーバ３０への配信要求に編集され、通信手段２１２を介して経路探索サーバ３０に送信される。
【００６７】
経路探索サーバ３０から配信される案内経路などの配信データはデータ記憶手段２１５に一時記憶され、必要に応じてデータ記憶手段２１５から読み出され、表示手段２１６に表示される。経路探索サーバ３０からの配信データに交通機関を利用した経路が含まれる場合は、複数の候補経路が順に（トータルの所要時間順や所要運賃順など表示順は利用者が設定することができる）表示される。
【００６８】
ＧＰＳ測位手段２１３は、予め定められた一定の周期でＧＰＳ衛星信号を受信し、端末装置２０の現在位置を緯度・経度で測位する。ＧＰＳ測位手段２１３で測位された現在位置の情報は必要に応じて経路探索サーバ３０に送信され、経路探索サーバ３０は端末装置２０からの配信要求に応じて経路の再探索や現在位置情報に基づく各種データ、例えば、利用者が関心を持つＰＯＩ（興味対象場所）の検索、情報配信などに使用される。
【００６９】
一方、経路探索サーバ３０は、前述したように、経路探索のための道路ネットワークデータ３０１、時刻表データに基づく交通ネットワークのデータである時刻表ネットワークデータ３０２、リンクを平均のリンクコストで表現した平均コストネットワークデータ３０３、地図データ３０４を備えている。
【００７０】
また、経路探索サーバ３０は、制御手段３１１、通信手段３１２、配信手段３１３、経路探索手段３１４、平均コストデータ編集手段３１５、時刻表ネットワーク編集手段３１６などを備えて構成されている。制御手段３１１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１２は、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。
【００７１】
経路探索手段３１４は端末装置２０からの配信要求に基づいて出発地から目的地までの経路を探索する。移動手段が徒歩や自動車による経路探索の場合、経路探索手段３１４は道路ネットワークデータ３０１を参照して案内経路を探索する。移動手段に交通機関が含まれる場合、経路探索手段３１４は、先に説明したように、先ず、平均コストネットワークデータ３０３を参照して、所定数の候補経路を探索する。図３は、図７に例示されている出発地（東京（TOKYO））と目的地（中津川（NAKATSUGAWA））との間の経路を、平均コストネットワークデータ３０４を用いて探索して得られる候補経路を示す図である。探索する候補経路数に応じて複数の候補経路ＲＴ１〜ＲＴ５のようなルートが得られる。
【００７２】
次いで、経路探索手段３１４は、平均コストネットワークデータ３０３を用いて探索した候補経路（例えば、図３のＲＴ１〜ＲＴ５）について、その候補経路に限定して、時刻表をベースとした通常の時刻表ネットワークデータ３０２を参照して経路探索し、乗車する交通手段（案内経路）を求める。このような経路探索を行えば、経路探索の演算負荷を増大することなく、効率的に最適経路を見落とすことなく探索、案内することができるようになる。
【００７３】
このため、時刻表ネットワーク編集手段３１６は、時刻表ネットワークデータ３０２を編集し、候補経路（図３のＲＴ１〜ＲＴ５）の時刻表データのみに編集して経路探索手段３１４に編集された時刻表ネットワークデータを対象に経路探索させる。編集の方法は、時刻表ネットワークデータ３０２から候補経路（図３のＲＴ１〜ＲＴ５）の時刻表データを抽出する方法、または候補経路の属する路線の時刻表データを抽出する方法、候補経路（図３のＲＴ１〜ＲＴ５）以外の時刻表データのリンクコストを無限大にする方法、あるいは、利用禁止フラグを立てる方法などの方法によって実現することができる。
【００７４】
平均コストネットワークデータ３０３を用いた経路探索において、交通手段の制限条件が設定される場合、例えば、航空機や新幹線を利用しないという条件が設定された場合、平均コストデータ編集手段３１５は平均コストネットワークデータ３０３を編集し、該当する経路（リンク）の平均コストデータが参照されないようにする。編集の方法は先に説明したように、該当するリンクコストを無限大にし、または、利用禁止フラグを立て、あるいは該当リンクを平均コストネットワークから除外するなどの方法によって実現することができる。
【００７５】
次に、本発明の実施例１にかかるナビゲーションシステム１０の動作手順を図４に示すフローチャートを参照して説明する。先ず、ステップＳ１１の処理において、端末装置２０において経路探索条件を設定して経路探索要求を経路探索サーバ３０に送信する。経路探索条件は、操作・入力手段２１７によって設定するが、条件は通常のナビゲーションシステムと同様であり、出発地、目的地、出発／到着時刻条件、交通手段の選択条件（航空機、特急使用）などの設定入力を行う。
【００７６】
経路探索サーバ３０はステップＳ１２の処理において端末装置２０から経路探索要求を受信すると、ステップＳ１３の処理において経路探索条件を解析して、利用を制限する交通機関が設定されているか否か、すなわち、平均コストネットワークデータ３０３の編集が必要であるか否かを判別する。平均コストネットワークデータの編集が必要でなければステップＳ１５の処理に進む。平均コストネットワークデータの編集が必要であれば、ステップＳ１４の処理において先に説明した方法の何れかにより平均コストデータ編集手段３１５は平均コストネットワークデータの編集を行い、ステップＳ１５の処理に進む。
【００７７】
ステップＳ１５の処理において経路探索手段３１４は、平均コストネットワークデータ３０３、あるいは、ステップＳ１４の処理によって編集された平均コストネットワークデータ３０３を用いて所定数の候補経路を探索する。所定数の候補経路が探索されると、時刻表ネットワーク編集手段３１６は、時刻表ネットワークデータ３０２を候補経路のみのデータに編集する。
【００７８】
次いで、経路探索手段３１４はステップＳ１７の処理において候補経路のみに編集された時刻表ネットワークデータ３０２を用いて経路探索を行い、出発時間や到着時間の条件にあう交通手段（案内経路）が探索される。探索された案内経路はステップＳ１８の処理において出力され端末装置２０に配信される。探索された案内経路は、実際の時刻表で時刻表探索が行われるから、平均コストとは異なる所要時間で経路が求められるが、ソートして、最適なものから結果を出力する。
【００７９】
なお、上記の手順では、時刻表ネットワーク編集手段３１６が時刻表ネットワークデータ３０２を候補経路のみのデータに編集する方法を説明したが、他の方法をとることもできる。例えば、平均コストネットワークデータを用いて探索された候補経路の１つ１つに従って経路探索手段３１４が時刻表ネットワークデータ３０２を用いて探索する方法、あるいは、候補経路の全てを経路探索の範囲として時刻表ネットワークデータ３０２を用いて探索する方法であってもよい。
【実施例２】
【００８０】
以上説明したように、経路探索を、平均コストネットワークデータ３０３を使用した候補経路の探索と、候補経路に従って時刻表ネットワークデータ３０２を用いた経路の探索の２段階に分けることによって、探索用の時刻表ネットワークデータ３０２のメンテナンスを効果的に行うことができるようになる。例えば、天災や事故によって交通機関に運休区間が発生することがある。一時的な運転見合わせならともかく、何日も運休する場合はナビゲーションシステムも対応しなければならない。このためには、時刻表ネットワークデータ３０２を変更、メンテナンスしなければならない。
【００８１】
そこで、本実施例２においては、平均コストデータ編集手段３１５によって運休区間の平均コストデータを無限大とする編集を行えば、当該運休区間を含む候補経路が探索されることがなく、時刻表ネットワークデータ３０２の修正を行わずに、運休区間を避けた経路探索が行える。なお、実施例２のナビゲーションシステムの構成は図２に示すナビゲーションシステム１０と同一の構成である。
【００８２】
この場合、ナビゲーションシステムは、交通ネットワークの平均コストネットワークデータと時刻表ネットワークデータが経路探索サーバ側にあるクライアント−サーバ型のシステムであることが好ましい。交通機関から運休が発表されると、サーバ管理者はその区間の平均コストを無限大に設定できるような編集入力手段が経路探索サーバにあれば良い。もし、運休区間の影響で、それ以外の区間でも運休する列車があれば、それは時刻表を修正することになるが、修正の作業量は大幅に軽減される。勿論定期的なダイヤ改正がある場合には、時刻表ネットワークデータ３０２の更新が必要になる。
【００８３】
また運休区間が発生すると、影響のある列車の案内が実際と異なってしまい、サービスの信頼度を落としてしまう。本発明を適用して、迅速なデータベースの管理を行えば、クライアント−サーバ型のシステムで正しいデータの提供を維持できる。
【００８４】
以上、詳細に説明したように、本発明によれば、平均コストネットワークデータを用いて出発地と目的地との間の候補経路を探索するから、経路探索範囲を広くとることができ、経路探索負荷も増大することがない。また、候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【産業上の利用可能性】
【００８５】
最近では、携帯電話やインターネットに接続したＰＣあるいは携帯端末装置により交通機関を利用した経路案内を利用する頻度が高まってきている。このような経路案内において、クライアント−サーバ型のシステムでは、クライアントが多くなるとサーバにかかる負荷が問題となる。本発明はサーバの探索処理の負荷を軽減するために極めて有効であり、クライアント−サーバ型のシステムにおいて好適である。
【００８６】
またスタンドアロンタイプのナビゲーション装置でも、インターネット経由の配信で平均コストネットワークデータの提供を行うことは十分可能である。差分データのみであればデータ量も少なくて済むので本発明を適用することができる。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】図１のナビゲーションシステムの概略構成を示すブロック図である。
【図３】平均コストネットワークデータを用いて出発地から目的地までの候補経路を探索した結果を示す図である。
【図４】本発発明の実施例にかかるナビゲーションシステムの動作手順を示すフローチャートである。
【図５】経路探索のための道路ネットワークのデータを説明するための模式図である。
【図６】経路探索のための交通ネットワークのデータを説明するための模式図である。
【図７】交通機関を利用して所望の出発地から目的地までの経路を探索した結果の一例を示す図である。
【符号の説明】
【００８８】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１１・・・制御手段
２１２・・・通信手段
２１３・・・ＧＰＳ測位手段
２１４・・・配信要求手段
２１５・・・データ記憶手段
２１６・・・表示手段
２１７・・・操作・入力手段
３０・・・・経路探索サーバ
３１１・・・制御手段
３１２・・・通信手段
３１３・・・配信手段
３１４・・・経路探索手段
３１５・・・平均コストデータ編集手段
３１６・・・時刻表ネットワーク編集手段
３０１・・・道路ネットワークデータ
３０２・・・時刻表ネットワークデータ
３０３・・・平均コストネットワークデータ
３０４・・・地図データ
【技術分野】
【０００１】
本発明は、所望の出発地から目的地まで、交通機関を利用した経路を含む経路を探索して案内する経路探索システムに関するものであり、特に、交通機関を利用した経路を効率よく、かつ、最適な案内経路が経路探索から漏れることがないようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法に関するものである。本発明は、経路探索のためのネットワークデータを、平均コストをベースとした平均コストネットワークデータと、運行時刻表をベースとした時刻表ネットワークデータとの別個のデータで構成し、平均コストネットワークデータを用いて広域を対象とした経路探索を行い複数の候補経路を探索し、候補経路のみについて時刻表ネットワークデータを用いて案内経路を探索するようにしたナビゲーション、経路探索サーバおよび経路探索方法に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
このような経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける経路探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００９】
従って端末装置に配信される案内経路データには、利用者が指定した経路探索条件である出発地から目的地までの路線経路や乗車を案内するバス、電車、列車およびその時刻が含まれ、運行時刻表や駅に掲示されるいわゆる駅貼り時刻表などがそのままあるいは必要部分が画面表示できる表示データなどの形式に加工されて端末装置に配信される。端末装置では案内経路のデータや運行時刻表あるいは駅貼り時刻表を表示して経路や乗車すべき交通手段を確認することができる。
【００１０】
交通機関を利用した経路探索を行う経路探索方法は、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に交通ネットワーク経路探索方法として開示されている。この特許文献２に開示された交通ネットワーク経路探索方法は、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法である。
【００１１】
この方法においては、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するようにしている。
【００１２】
通常の経路探索に使用される道路網や交通機関の路線網のデータは以下のように構成されている。すなわち、例えば、道路が図５に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００１３】
すなわち、図５において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図５では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００１４】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図５において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００１５】
図５ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００１６】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図６に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図６において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図６では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００１７】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図６に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。この意味で交通ネットワークデータは運行時刻表をベースとしたネットワークデータであり、時刻表ネットワークデータということができる。
【００１８】
図６に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００１９】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００２０】
例えば、図６において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００２１】
このように交通機関のネットワークデータは、網の数が圧倒的に多い道路のネットワークデータに比べて路線数は格段に少ない（網の数が少ない）ものの網を運行する個々の電車や、列車（交通手段）の数が膨大であり全ての運行時刻が加味されたネットワークデータになり、かつ個々の交通手段の運行時刻に基づく組み合わせを経路探索する必要があり、経路探索における演算処理の付加が大きくなるという問題点がある。
【００２２】
このような問題点を解決するため、例えば、下記の特許文献３（特開平１０−３３４３８７号公報）には、経路を探索すべき出発地と目的地とから経路探索の範囲を限定することにより経路探索の処理負荷を軽減するようにした最適乗継系列探索方法の発明が開示されている。経路探索の範囲を限定する方法としては、出発地と目的地を結ぶ線を基線とし、その前後左右を含む長方形あるいは楕円等の図形（領域）で囲み、その領域外の地域については探索の範囲外とする方法、あるいは、出発地と目的地を結ぶ線を基線とし、その基線の外側の方向に対して、ある地域単位に探索禁止地域を設ける方法が提案されている。
【００２３】
「基線の外側方向」とは、出発地においては目的地と逆方向が探索禁止地域の対象となり、目的地においては出発地と逆方向が探索禁止地域となる。この方法においては、あらかじめ地域ごと（たとえば県単位）の探索禁止をテーブルで定めておき、出発地と目的地が定まった時点で、禁止の範囲が特定されるようにしている。
【００２４】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−２５８１８４号公報（図４、図７）
【特許文献３】特開平１０−３３４３８７号公報（図５、段落［００４０］、［００４１］）
【発明の開示】
【発明が解決しようとする課題】
【００２５】
しかしながら、上記特許文献３に開示されたように、出発地と目的地とから予め経路探索の範囲を限定して経路探索する場合、どのように経路探索範囲を制限して経路探索したら最適な案内経路が漏れることなく得られるか、その制限方法を最適化する解を見出してはいない。このため、次のような問題点が生ずる。
【００２６】
例えば、図７に示すように「東京（TOKYO）」から岐阜県の「中津川（NAKATSUGAWA）」への経路を探索する場合、代表的な経路には「東京（TOKYO）」から「名古屋（NAGOYA）」まで新幹線を利用し、「名古屋（NAGOYA）」から特急に乗り換えて「中津川（NAKATSUGAWA）」に至る第１ルートＲＴ１（図７における実線の経路）があげられる。これに対して、距離的に最短の経路としては中央線を用いた第２ルートＲＴ２（図７における点線の経路）がある。
【００２７】
このような出発地と目的地の場合、第１ルートＲＴ１は新幹線を利用するために所要時間は圧倒的に短く実用的な経路である。これに対して第２ルートは距離的には最短経路ではあるが、在来線特急を利用しても第１ルートに比べ所要時間が長くなる。特に岐阜県に居住する人はこのことを経験的に知っている。
【００２８】
上記特許文献３に開示されたように経路探索の範囲を制限する場合、上記のような出発地と目的地を結ぶ経路探索においては、名古屋が探索範囲に含まれるようにしないと、第１ルートＲＴ１を探索できないことになる。上記のような例に限らず、航空機や船舶まで含めた各種の交通機関を含めたマルチモーダルな経路探索では、交通機関の移動速度に大きな差があり、一旦目的地から遠く離れた地点まで移動して、そこから目的地に移動するルートをとるほうが最適であるケースが多く含まれる。
【００２９】
このような出発地と目的地の事例は多々存在し、探索範囲の決定に苦慮する。最適経路が漏れないように経路探索しようとすると、経路探索の範囲をできるだけ広くとることが必要になる。経路探索範囲を広くとると、経路探索の処理負荷が大きくなり高速、効率的に最適経路を探索することができなくなる。逆に探索範囲を狭く制限すると、高速な探索処理はできるが、最適経路が漏れる可能性が大きくなる。交通機関を用いた経路の探索にはこのような相反する課題が生じる。
【００３０】
本願の発明者はこのような問題点を解消すべく種々検討を重ねた結果、通常の交通機関を利用した経路探索に用いられる時刻表データをベースとした時刻表ネットワークデータの他に、全ての交通機関の経路ネットワークを平均コストのみで表現した平均コストネットワークデータを別に用意し、先ず、平均コストネットワークデータを用いて出発地から目的地に至る候補経路を探索し、候補経路のみについて時刻表ネットワークデータを用いた経路探索をすれば上記問題点を解消しえることに想到して本発明を完成するに至ったものである。
【００３１】
すなわち、本発明は前記の問題点を解消することを課題とし、経路探索の負荷を軽減し効率的に出発地から目的地までの経路を探索することができ、また、最適経路を見落とす恐れなく、効率的に探索範囲を限定できるナビゲーションシステム、経路探索サーバおよび経路探索方法を提供することを目的とするものである。
【課題を解決するための手段】
【００３２】
前記課題を解決するために、本願の請求項１にかかる発明は、
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする。
【００３３】
本願の請求項２にかかる発明は、請求項１にかかる発明において、前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする。
【００３４】
本願の請求項３にかかる発明は、請求項１にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする。
【００３５】
本願の請求項４にかかる発明は、請求項３にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする。
【００３６】
本願の請求項５にかかる発明は、請求項１にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【００３７】
また、本願の請求項６にかかる発明は、
表示手段と、操作・入力手段と、を備え、操作・入力手段により設定した出発地と目的地とを含む経路探索要求を経路探索サーバに送信し、経路探索サーバから配信された案内経路データを前記表示手段に表示する端末装置にネットワークを介して接続される経路探索サーバにおいて、
前記経路探索サーバは、ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする。
【００３８】
本願の請求項７にかかる発明は、請求項６にかかる発明において、前記経路探索サーバは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする。
【００３９】
本願の請求項８にかかる発明は、請求項６にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする。
【００４０】
本願の請求項９にかかる発明は、請求項８にかかる発明において、前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする。
【００４１】
本願の請求項１０にかかる発明は、請求項６にかかる発明において、前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【００４２】
また、本願の請求項１１にかかる発明は、
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索手段が、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索する第１のステップと、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する第２のステップとを有することを特徴とする。
【００４３】
本願の請求項１２にかかる発明は、請求項１１にかかる発明において、前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段が前記所定数の候補経路の時刻表ネットワークデータのみを編集するステップを有し、前記第２のステップは、経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する処理であることを特徴とする。
【００４４】
本願の請求項１３にかかる発明は、請求項１１にかかる発明において、前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記第１のステップは、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する処理を含むことを特徴とする。
【００４５】
本願の請求項１４にかかる発明は、請求項１３にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集するステップを有し、前記第１のステップは前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する処理であることを特徴とする。
【００４６】
本願の請求項１５にかかる発明は、請求項１１にかかる発明において、前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集するステップを有し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする。
【発明の効果】
【００４７】
請求項１にかかる発明においては、ナビゲーションシステムはノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータとを備え、経路探索手段は、操作・入力手段により設定された出発地と目的地の情報に従って平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について時刻表ネットワークデータに基づいて各候補経路における最適経路を探索する。
【００４８】
このような構成によれば、平均コストネットワークデータを用いて出発地と目的地との間の候補経路を探索するから、経路探索範囲を広くとることができ、経路探索負荷も増大することがない。また、候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【００４９】
請求項２にかかる発明は、請求項１にかかる発明において、ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力する。
【００５０】
このような構成によれば、平均コストネットワークデータを用いて探索した候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【００５１】
請求項３にかかる発明は、請求項１にかかる発明において、平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する。
【００５２】
請求項４にかかる発明は、請求項３にかかる発明において、ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する。
【００５３】
このような構成によれば、平均コストネットワークデータから、探索条件として設定された交通手段に関する平均コストネットワークのみを対象にした経路探索を行うから、経路探索負荷を更に軽減することができるようになる。
【００５４】
請求項５にかかる発明は、請求項１にかかる発明において、ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにする。
【００５５】
このような構成によれば、災害や事故により交通機関に一時運休する区間が生じた場合であっても、時刻表ネットワークデータを更新することなく、平均コストネットワークデータの更新のみで容易に対応することができるようになる。
【００５６】
また、請求項６ないし請求項１０にかかる発明においては、それぞれ請求項１ないし請求項５にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになり、請求項１１ないし請求項１５にかかる発明においては、それぞれ請求項１ないし請求項５にかかるナビゲーションシステムにおける経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００５７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００５８】
図１は、本発明の実施例１にかかるナビゲーションシステムの構成を示す図である。ナビゲーションシステム１０は、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。なお、本実施例１においては、経路探索、案内経路を提供するナビゲーションシステム１０を具体例として説明するが、本発明はこれに限ることなく、スタンドアロンタイプのナビゲーションシステムになどにも適用可能である。
【００５９】
経路探索サーバ３０は、経路探索のため道路ネットワークのデータを蓄積したデータベース（ＤＢ１）、時刻表データに基づく交通ネットワークのデータを時刻表ネットワークデータとして蓄積したデータベース（ＤＢ２）、交通ネットワークの各リンクを平均のリンクコストで表現した平均コストネットワークデータを蓄積したデータベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。ここで、平均コストネットワークデータとは、交通ネットワークを構成する各リンクのリンクコストを平均的なリンクコストのみで表したものであり、例えば、鉄道であれば普通列車のコストを平均コストとして使用する。
【００６０】
経路探索サーバは、先ず、最初に交通機関を利用する経路部分について、平均コストネットワークデータを用いて経路探索し、所定数の候補経路を探索する。このとき、平均コストに影響を与えるパラメータとして、交通手段の選択条件を設定し、例えば、航空機や特急の利用を認めない設定の場合には、航空機利用の経路区間のリンクコストを編集し、候補経路として探索されないようにする。リンクコストの編集は、該当するリンクコストを無限大にし、または、利用禁止フラグを立て、あるいは該当リンクを平均コストネットワークから除外するなどの方法をとることができる。
【００６１】
平均コストネットワークデータに基づく経路探索は、ダイクストラ法による経路探索を適用するが、交通機関のネットワークは道路ネットワークに比べて格段にリンク数が少ない。カーナビが道路ネットワークデータを用いて経路探索を行う場合と比較しても、平均コストネットワークデータを用いた経路探索ならば探索範囲を限定しなくても、容易に経路探索が行える。従来は、いきなり時刻表ネットワークでの経路探索を行おうとしたので、リンクに相当する交通手段（電車やバス）の運行本数が多くて演算負荷が大きくなっていたものである。ダイクストラ法ではまず最小コスト経路が最初に求められ、例えば、マーチンのアルゴリズムを用いて第Ｋ最短経路まで複数の候補経路を求めることが出来る。ここでは、内部的に５〜２０経路ほど（多めに）の候補経路を求めておく。
【００６２】
次いで経路探索サーバは、上記のようにして探索した候補経路に限定して、時刻表をベースとした通常の時刻表ネットワークデータ（探索条件として設定した交通手段の時刻表ネットワークデータに限定することもできる）を参照して経路探索を行うので、経路探索の対象となる時刻表データを格段に減らすことが出来る。なお、詳細には、平均コストネットワークデータによる経路探索で求められた候補経路の１つ１つに応じて時刻表ネットワークデータを用いて経路探索し、乗車する交通手段（案内経路）を求める方法、平均コストネットワークデータを用いた経路探索で求められた候補経路の全経路の時刻表ネットワークデータを探索範囲として経路探索し、乗車する交通手段を求める方法のいずれでも良い。これにより、出発時間や到着時間の条件にあう交通手段（案内経路）が探索される。
【００６３】
平均コストネットワークデータを用いて探索された候補経路であっても、実際の時刻表ネットワークデータを用いて時刻表探索を行うと、平均コストとは異なる所要時間で経路が求められる。それをソートして、最適なものから結果表示する。乗り継ぎが良くない経路はソートで順位を下げるが、所要時間の短い経路はソートでも生き残ることになり、最適な案内経路から順に利用者に案内することができる。
このような経路探索を行えば、経路探索の演算負荷を増大することなく、効率的に最適経路を見落とすことなく探索、案内することができるようになる。
【００６４】
図２は、図１のナビゲーションシステム１０の概略構成を示すブロック図である。端末装置２０は、例えばＧＰＳ受信機などからなるＧＰＳ測位手段２１３を搭載した携帯電話機であり、制御手段２１１、通信手段２１２、配信要求手段２１４、データ記憶手段２１５、表示手段２１６、操作・入力手段２１７などを備えて構成されている。利用者は、徒歩あるいは交通機関を移動手段として選択し、徒歩や交通機関を利用した経路案内を受けることができ、また、自動車の助手席に同乗した時には移動手段として自動車を選択して経路案内を受けることができる。
【００６５】
制御手段２１１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２１７は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力のためのものであり、出力手段である表示手段２１６に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２１６は操作・入力手段２１７の一部としても機能する。通信手段２１２は、ネットワーク１２を介して経路探索サーバ３０と通信するためのインターフェースである。
【００６６】
利用者が経路探索サーバ３０に経路探索を依頼しようとする場合、端末装置２０において操作・入力手段２１７を操作し、表示手段２１６に表示されるサービスメニューから経路探索を選択し、現在位置、目的地、移動手段（自動車、徒歩、交通機関あるいは徒歩と交通機関併用など）などの経路探索条件を入力する。経路探索条件は配信要求手段２１４で経路探索サーバ３０への配信要求に編集され、通信手段２１２を介して経路探索サーバ３０に送信される。
【００６７】
経路探索サーバ３０から配信される案内経路などの配信データはデータ記憶手段２１５に一時記憶され、必要に応じてデータ記憶手段２１５から読み出され、表示手段２１６に表示される。経路探索サーバ３０からの配信データに交通機関を利用した経路が含まれる場合は、複数の候補経路が順に（トータルの所要時間順や所要運賃順など表示順は利用者が設定することができる）表示される。
【００６８】
ＧＰＳ測位手段２１３は、予め定められた一定の周期でＧＰＳ衛星信号を受信し、端末装置２０の現在位置を緯度・経度で測位する。ＧＰＳ測位手段２１３で測位された現在位置の情報は必要に応じて経路探索サーバ３０に送信され、経路探索サーバ３０は端末装置２０からの配信要求に応じて経路の再探索や現在位置情報に基づく各種データ、例えば、利用者が関心を持つＰＯＩ（興味対象場所）の検索、情報配信などに使用される。
【００６９】
一方、経路探索サーバ３０は、前述したように、経路探索のための道路ネットワークデータ３０１、時刻表データに基づく交通ネットワークのデータである時刻表ネットワークデータ３０２、リンクを平均のリンクコストで表現した平均コストネットワークデータ３０３、地図データ３０４を備えている。
【００７０】
また、経路探索サーバ３０は、制御手段３１１、通信手段３１２、配信手段３１３、経路探索手段３１４、平均コストデータ編集手段３１５、時刻表ネットワーク編集手段３１６などを備えて構成されている。制御手段３１１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１２は、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。
【００７１】
経路探索手段３１４は端末装置２０からの配信要求に基づいて出発地から目的地までの経路を探索する。移動手段が徒歩や自動車による経路探索の場合、経路探索手段３１４は道路ネットワークデータ３０１を参照して案内経路を探索する。移動手段に交通機関が含まれる場合、経路探索手段３１４は、先に説明したように、先ず、平均コストネットワークデータ３０３を参照して、所定数の候補経路を探索する。図３は、図７に例示されている出発地（東京（TOKYO））と目的地（中津川（NAKATSUGAWA））との間の経路を、平均コストネットワークデータ３０４を用いて探索して得られる候補経路を示す図である。探索する候補経路数に応じて複数の候補経路ＲＴ１〜ＲＴ５のようなルートが得られる。
【００７２】
次いで、経路探索手段３１４は、平均コストネットワークデータ３０３を用いて探索した候補経路（例えば、図３のＲＴ１〜ＲＴ５）について、その候補経路に限定して、時刻表をベースとした通常の時刻表ネットワークデータ３０２を参照して経路探索し、乗車する交通手段（案内経路）を求める。このような経路探索を行えば、経路探索の演算負荷を増大することなく、効率的に最適経路を見落とすことなく探索、案内することができるようになる。
【００７３】
このため、時刻表ネットワーク編集手段３１６は、時刻表ネットワークデータ３０２を編集し、候補経路（図３のＲＴ１〜ＲＴ５）の時刻表データのみに編集して経路探索手段３１４に編集された時刻表ネットワークデータを対象に経路探索させる。編集の方法は、時刻表ネットワークデータ３０２から候補経路（図３のＲＴ１〜ＲＴ５）の時刻表データを抽出する方法、または候補経路の属する路線の時刻表データを抽出する方法、候補経路（図３のＲＴ１〜ＲＴ５）以外の時刻表データのリンクコストを無限大にする方法、あるいは、利用禁止フラグを立てる方法などの方法によって実現することができる。
【００７４】
平均コストネットワークデータ３０３を用いた経路探索において、交通手段の制限条件が設定される場合、例えば、航空機や新幹線を利用しないという条件が設定された場合、平均コストデータ編集手段３１５は平均コストネットワークデータ３０３を編集し、該当する経路（リンク）の平均コストデータが参照されないようにする。編集の方法は先に説明したように、該当するリンクコストを無限大にし、または、利用禁止フラグを立て、あるいは該当リンクを平均コストネットワークから除外するなどの方法によって実現することができる。
【００７５】
次に、本発明の実施例１にかかるナビゲーションシステム１０の動作手順を図４に示すフローチャートを参照して説明する。先ず、ステップＳ１１の処理において、端末装置２０において経路探索条件を設定して経路探索要求を経路探索サーバ３０に送信する。経路探索条件は、操作・入力手段２１７によって設定するが、条件は通常のナビゲーションシステムと同様であり、出発地、目的地、出発／到着時刻条件、交通手段の選択条件（航空機、特急使用）などの設定入力を行う。
【００７６】
経路探索サーバ３０はステップＳ１２の処理において端末装置２０から経路探索要求を受信すると、ステップＳ１３の処理において経路探索条件を解析して、利用を制限する交通機関が設定されているか否か、すなわち、平均コストネットワークデータ３０３の編集が必要であるか否かを判別する。平均コストネットワークデータの編集が必要でなければステップＳ１５の処理に進む。平均コストネットワークデータの編集が必要であれば、ステップＳ１４の処理において先に説明した方法の何れかにより平均コストデータ編集手段３１５は平均コストネットワークデータの編集を行い、ステップＳ１５の処理に進む。
【００７７】
ステップＳ１５の処理において経路探索手段３１４は、平均コストネットワークデータ３０３、あるいは、ステップＳ１４の処理によって編集された平均コストネットワークデータ３０３を用いて所定数の候補経路を探索する。所定数の候補経路が探索されると、時刻表ネットワーク編集手段３１６は、時刻表ネットワークデータ３０２を候補経路のみのデータに編集する。
【００７８】
次いで、経路探索手段３１４はステップＳ１７の処理において候補経路のみに編集された時刻表ネットワークデータ３０２を用いて経路探索を行い、出発時間や到着時間の条件にあう交通手段（案内経路）が探索される。探索された案内経路はステップＳ１８の処理において出力され端末装置２０に配信される。探索された案内経路は、実際の時刻表で時刻表探索が行われるから、平均コストとは異なる所要時間で経路が求められるが、ソートして、最適なものから結果を出力する。
【００７９】
なお、上記の手順では、時刻表ネットワーク編集手段３１６が時刻表ネットワークデータ３０２を候補経路のみのデータに編集する方法を説明したが、他の方法をとることもできる。例えば、平均コストネットワークデータを用いて探索された候補経路の１つ１つに従って経路探索手段３１４が時刻表ネットワークデータ３０２を用いて探索する方法、あるいは、候補経路の全てを経路探索の範囲として時刻表ネットワークデータ３０２を用いて探索する方法であってもよい。
【実施例２】
【００８０】
以上説明したように、経路探索を、平均コストネットワークデータ３０３を使用した候補経路の探索と、候補経路に従って時刻表ネットワークデータ３０２を用いた経路の探索の２段階に分けることによって、探索用の時刻表ネットワークデータ３０２のメンテナンスを効果的に行うことができるようになる。例えば、天災や事故によって交通機関に運休区間が発生することがある。一時的な運転見合わせならともかく、何日も運休する場合はナビゲーションシステムも対応しなければならない。このためには、時刻表ネットワークデータ３０２を変更、メンテナンスしなければならない。
【００８１】
そこで、本実施例２においては、平均コストデータ編集手段３１５によって運休区間の平均コストデータを無限大とする編集を行えば、当該運休区間を含む候補経路が探索されることがなく、時刻表ネットワークデータ３０２の修正を行わずに、運休区間を避けた経路探索が行える。なお、実施例２のナビゲーションシステムの構成は図２に示すナビゲーションシステム１０と同一の構成である。
【００８２】
この場合、ナビゲーションシステムは、交通ネットワークの平均コストネットワークデータと時刻表ネットワークデータが経路探索サーバ側にあるクライアント−サーバ型のシステムであることが好ましい。交通機関から運休が発表されると、サーバ管理者はその区間の平均コストを無限大に設定できるような編集入力手段が経路探索サーバにあれば良い。もし、運休区間の影響で、それ以外の区間でも運休する列車があれば、それは時刻表を修正することになるが、修正の作業量は大幅に軽減される。勿論定期的なダイヤ改正がある場合には、時刻表ネットワークデータ３０２の更新が必要になる。
【００８３】
また運休区間が発生すると、影響のある列車の案内が実際と異なってしまい、サービスの信頼度を落としてしまう。本発明を適用して、迅速なデータベースの管理を行えば、クライアント−サーバ型のシステムで正しいデータの提供を維持できる。
【００８４】
以上、詳細に説明したように、本発明によれば、平均コストネットワークデータを用いて出発地と目的地との間の候補経路を探索するから、経路探索範囲を広くとることができ、経路探索負荷も増大することがない。また、候補経路のみについて時刻表ネットワークデータを用いて実際に乗車可能な案内経路を探索するから、経路探索の負荷を増大することなく経路探索することができ、最適経路が漏れる恐れも小さくすることができるようになる。
【産業上の利用可能性】
【００８５】
最近では、携帯電話やインターネットに接続したＰＣあるいは携帯端末装置により交通機関を利用した経路案内を利用する頻度が高まってきている。このような経路案内において、クライアント−サーバ型のシステムでは、クライアントが多くなるとサーバにかかる負荷が問題となる。本発明はサーバの探索処理の負荷を軽減するために極めて有効であり、クライアント−サーバ型のシステムにおいて好適である。
【００８６】
またスタンドアロンタイプのナビゲーション装置でも、インターネット経由の配信で平均コストネットワークデータの提供を行うことは十分可能である。差分データのみであればデータ量も少なくて済むので本発明を適用することができる。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】図１のナビゲーションシステムの概略構成を示すブロック図である。
【図３】平均コストネットワークデータを用いて出発地から目的地までの候補経路を探索した結果を示す図である。
【図４】本発発明の実施例にかかるナビゲーションシステムの動作手順を示すフローチャートである。
【図５】経路探索のための道路ネットワークのデータを説明するための模式図である。
【図６】経路探索のための交通ネットワークのデータを説明するための模式図である。
【図７】交通機関を利用して所望の出発地から目的地までの経路を探索した結果の一例を示す図である。
【符号の説明】
【００８８】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１１・・・制御手段
２１２・・・通信手段
２１３・・・ＧＰＳ測位手段
２１４・・・配信要求手段
２１５・・・データ記憶手段
２１６・・・表示手段
２１７・・・操作・入力手段
３０・・・・経路探索サーバ
３１１・・・制御手段
３１２・・・通信手段
３１３・・・配信手段
３１４・・・経路探索手段
３１５・・・平均コストデータ編集手段
３１６・・・時刻表ネットワーク編集手段
３０１・・・道路ネットワークデータ
３０２・・・時刻表ネットワークデータ
３０３・・・平均コストネットワークデータ
３０４・・・地図データ
【特許請求の範囲】
【請求項１】
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする請求項３に記載のナビゲーションシステム。
【請求項５】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
表示手段と、操作・入力手段と、を備え、操作・入力手段により設定した出発地と目的地とを含む経路探索要求を経路探索サーバに送信し、経路探索サーバから配信された案内経路データを前記表示手段に表示する端末装置にネットワークを介して接続される経路探索サーバにおいて、
前記経路探索サーバは、ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする経路探索サーバ。
【請求項７】
前記経路探索サーバは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする請求項６に記載の経路探索サーバ。
【請求項９】
前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする請求項８に記載の経路探索サーバ。
【請求項１０】
前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項６に記載の経路探索サーバ。
【請求項１１】
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索手段が、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索する第１のステップと、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する第２のステップとを有することを特徴とする経路探索方法。
【請求項１２】
前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段が前記所定数の候補経路の時刻表ネットワークデータのみを編集するステップを有し、前記第２のステップは、経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する処理であることを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記第１のステップは、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する処理を含むことを特徴とする請求項１１に記載の経路探索方法。
【請求項１４】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集するステップを有し、前記第１のステップは前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する処理であることを特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集するステップを有し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項１１に記載の経路探索方法。
【請求項１】
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする請求項３に記載のナビゲーションシステム。
【請求項５】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
表示手段と、操作・入力手段と、を備え、操作・入力手段により設定した出発地と目的地とを含む経路探索要求を経路探索サーバに送信し、経路探索サーバから配信された案内経路データを前記表示手段に表示する端末装置にネットワークを介して接続される経路探索サーバにおいて、
前記経路探索サーバは、ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、を備え、
前記経路探索手段は、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索し、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して案内経路を出力することを特徴とする経路探索サーバ。
【請求項７】
前記経路探索サーバは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段は前記所定数の候補経路の時刻表ネットワークデータのみを編集し、前記経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索して出力することを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記経路探索手段は、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索することを特徴とする請求項６に記載の経路探索サーバ。
【請求項９】
前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集し、前記経路探索手段は前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索することを特徴とする請求項８に記載の経路探索サーバ。
【請求項１０】
前記経路探索サーバは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段は、交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項６に記載の経路探索サーバ。
【請求項１１】
ノードとリンクとリンクコストで表現される交通機関のネットワークを各リンクのリンクコストを平均リンクコストとした平均コストネットワークデータと、前記交通機関のネットワークを時刻表に基づいて表現した時刻表ネットワークデータと、経路探索手段と、経路探索条件を設定する操作・入力手段と、を備えたナビゲーションシステムにおける経路探索方法であって、
前記経路探索手段が、前記操作・入力手段により設定された出発地と目的地の情報に従って前記平均コストネットワークデータに基づいて、予め定めた所定数の候補経路を探索する第１のステップと、当該候補経路の各々について前記時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する第２のステップとを有することを特徴とする経路探索方法。
【請求項１２】
前記ナビゲーションシステムは更に時刻表ネットワークデータを編集する時刻表ネットワーク編集手段を備え、前記時刻表ネットワーク編集手段が前記所定数の候補経路の時刻表ネットワークデータのみを編集するステップを有し、前記第２のステップは、経路探索手段は前記編集された時刻表ネットワークデータに基づいて前記各候補経路における最適経路を探索する処理であることを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記平均コストネットワークデータは、交通手段ごとの平均リンクコストを含み、前記第１のステップは、経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストに基づいて前記候補経路を探索する処理を含むことを特徴とする請求項１１に記載の経路探索方法。
【請求項１４】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が経路探索条件に含まれる交通手段の設定に基づき、前記交通手段に該当する平均リンクコストのみを編集するステップを有し、前記第１のステップは前記編集された平均コストネットワークデータに基づいて前記各候補経路を探索する処理であることを特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記ナビゲーションシステムは更に平均コストネットワークデータを編集する平均コストデータ編集手段を備え、前記平均コストデータ編集手段が交通ネットワーク上の運休区間情報に基づいて、当該運休区間に該当する区間のリンクコストを編集するステップを有し、当該運休区間が実質的に経路探索対象から除外されるようにすることを特徴とする請求項１１に記載の経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００７−２７１４６６（Ｐ２００７−２７１４６６Ａ）
【公開日】平成１９年１０月１８日（２００７．１０．１８）
【国際特許分類】
【出願番号】特願２００６−９７７１２（Ｐ２００６−９７７１２）
【出願日】平成１８年３月３１日（２００６．３．３１）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成１９年１０月１８日（２００７．１０．１８）
【国際特許分類】
【出願日】平成１８年３月３１日（２００６．３．３１）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]