ナビゲーションシステム、経路探索サーバおよび経路探索方法ならびにナビゲーション装置
【課題】車両が他の交通手段に積載されて移動する経路についても通常の道路を移動する経路の探索とともに効率よく探索できるようにする。
【解決手段】道路をノードとリンクで表現した経路探索用ネットワークデータ３５を備えラベル確定法を用いて最適経路を探索するナビゲーションシステム１０において、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、経路探索手段３９は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続する。
【解決手段】道路をノードとリンクで表現した経路探索用ネットワークデータ３５を備えラベル確定法を用いて最適経路を探索するナビゲーションシステム１０において、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、経路探索手段３９は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、設定された出発地から目的地までの最適経路を探索して案内するナビゲーションシステムであって、経路探索用の道路ネットワークデータに、カーフェリーなどの航路データを擬似的な道路データとして付加し、車載用ナビゲーション装置がカーフェリーなど他の交通手段に積載されて移動する経路区間も経路探索の対象とするようにしたナビゲーションシステムの改良に関するものであり、特に、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、効率よく経路探索を行うようにしたナビゲーションシステムに関するものである。
【背景技術】
【０００２】
従来から自動車の運転者に出発地から目的地までの最適な経路を案内する車載用のナビゲーション装置が提供されている。従来のナビゲーション装置は、地図データを記録したＣＤ−ＲＯＭ又はＩＣカード等の地図データ記憶装置と、ディスプレイ装置と、ジャイロ、ＧＰＳ（Global Positioning System）及び車速センサ等の車両の現在位置及び現在方位を検出する車両移動検出装置等を有し、車両の現在位置を含む地図データを地図データ記憶装置から読み出し、該地図データに基づいて車両位置の周囲の地図画像をディスプレイ装置上に描画する。また、車両位置マーク（ロケーション）をディスプレイ画面の地図画像に重ね合わせて表示し、車両の移動に応じて地図画像をスクロール表示したり、地図画像を画面に固定し車両位置マークを移動させたりして、車両が現在どこを走行しているのかを一目で判るようにしている。
【０００３】
通常、このような車載用ナビゲーション装置には、運転者が所望の目的地に向けて道路を間違うことなく容易に走行できるようにした経路案内機能が搭載されている。この経路案内機能によれば、地図データを用いて出発地から目的地までを結ぶ最もコストが小さい経路を、ダイクストラ法等を用いたシミュレーション計算を行って経路探索し、その探索した経路を案内経路として記憶しておき、走行中、地図画像上に案内経路を他の道路とは色を変えて太く描画して画面表示したり、車両が案内経路上の進路を変更すべき交差点に一定距離内に近づいたときに、地図画像上の進路を変更すべき交差点に進路を示す矢印を描画して画面表示したりすることで目的地までの最適な経路を運転者が簡単に把握できるようにしている。
【０００４】
上記の車載用のナビゲーション装置は、経路探索機能や地図データを持つスタンドアロン型のナビゲーション装置であるが、このようなナビゲーション装置はナビゲーションに必要な全ての機能を備えている必要があり、装置が大型化し価格も高いものとなっていた。近年の通信、情報処理技術の発展により車載用のナビゲーション装置にネットワークを介した通信機能を付加し経路探索サーバとデータ通信して案内経路データや地図データを取得するいわゆる通信型のナビゲーションシステムも普及してきており、車載、携帯兼用のナビゲーション装置も提供されている。更には、歩行者用のナビゲーションシステムとして携帯電話をナビゲーション端末としたシステムも実用化されている。携帯電話をナビゲーション端末としたシステムであっても、助手席に乗車した操作者が経路探索して運転者を案内する、助手席ナビとして用いることができる。
【０００５】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００６】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００７】
経路探索して得た出発地から目的地までの経路のうち、経路の累計コスト（距離または時間）が最小となる経路が最適な案内経路として決定され、案内経路データが作成される。案内経路データには、最適経路のデータの他に地図データ、ガイダンスデータが含まれ、案内経路データは必要に応じて案内データ記憶手段から読み出され表示手段に表示される。一般的には、ナビゲーション装置が有するＧＰＳ受信機を用いて測位したナビゲーション装置の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、ナビゲーション装置の現在位置を示すマークを重ね合わせ、該現在位置マークが表示画面の中心になるように表示する。
【０００８】
ＧＰＳ受信機を用いて測位した位置情報には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理や地図上の最も近い道路上に補正するマップマッチング処理が行われる。また、案内経路データに交差点などのガイダンスポイントが設定され、そのガイダンスポイントにおけるガイダンスとして音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力して利用者をガイドする。
【０００９】
また、ナビゲーション装置が歩行用に用いられる場合、交通機関を用いた経路区間を含む経路探索ができるように、道路ネットワークデータに加えて、交通ネットワークデータベースを備えている。交通ネットワークのデータは、各交通路線を道路のように扱い、交通路線の各駅をノードとし、各駅間を結ぶ区間をリンクとするものであるが、道路ネットワークのデータとリンクデータが異なる。交通ネットワークのデータにおけるリンクは、交通機関の時刻表データによって定まる各電車やバスなどの移動手段の個々がリンクを構成する。従って、交通ネットワークのデータにおけるリンクのデータは、端点のノードである駅を出発する出発時刻と、他の端点のノードである駅に到着する時刻が定まっており、出発時刻と到着時刻との差である所要時間がリンクコストとなる。
【００１０】
ところで、ナビゲーション装置が移動し得る経路には、道路や交通機関を用いた経路の他に、カーフェリーやカートレインなどナビゲーション装置が搭載された車両が、船や鉄道車両に積載されて移動する経路も存在する。従って、経路探索の対象としてカーフェリーやカートレインなどナビゲーション装置が搭載された車両が、船や鉄道車両に積載されて移動する経路も一般の道路を移動する経路とともに探索されることが好ましい。一般に、カーフェリーやカートレインでは、乗降ターミナルである港湾や鉄道の駅などの端点（ノード）間を結ぶリンクの合計距離は、道路や交通路線のノードを繋ぐリンクよりも圧倒的に長い。また、各端点における船や電車の発着時刻が定まっており、道路ネットワークのデータよりは交通ネットワークのデータに近い性格を有する。
【００１１】
カーフェリーの航路を擬似的な道路データとして表現し、道路ネットワークのデータに結合して経路探索の対象に含めるようにした車載ナビゲーション装置は、例えば、下記の特許文献２（特許第２５５６６２２号公報）や特許文献３（特許第２６２３３９４号公報）に開示されている。
【００１２】
特許文献２に開示された車載ナビゲータの発明は、記憶手段に記憶された道路データを参照して、走行誘導経路計算手段で現在地から目的地までの走行誘導経路を求め、地図画像上に経路誘導表示を行うようにした車載ナビゲータにおいて、記憶手段の道路データに、予め、実際の道路以外で車両が移動可能な交通路も擬似的な道路として含めておき、走行誘導経路計算手段は、道路データの実際の道路と擬似的な道路の両者を対象にして走行誘導経路を求めるようにしたものである。
【００１３】
特許文献３に開示された車載ナビゲーション装置の発明は、実際の道路形状を線分によって折線近似したときの各線分の位置および相互の接続状態に関するデータからなるデジタル地図データにもとづいて、画面に写し出される道路地図上に設定された出発点から目的地に到るまでの経路の探索をなして車両の走行案内を行わせる車両走行案内装置において、道路地図上の既存の道路と連結した航路などの道路外の路のデータをデジタル地図データ内に組み込んで、出発点と目的地との間に航路などの道路外の路が介在するときの経路探索を行わせるようにしたものであり、航路など道路外の線分のコストをみかけ上大きくしたうえでコスト最小の経路を探索するようにしたものである。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特許第２５５６６２２号公報
【特許文献３】特許第２６２３３９４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
先ず、ダイクストラ法に代表されるラベル確定法を用いる一般的な経路探索の方法について説明する。図９は、本発明において経路探索の対象とする道路ネットワークの基本構成を説明するための概念図である。図９において、道路の交差点、屈曲点がノード１〜８（まるで囲んだ数字）で示され、各ノード１〜８の間を連結する矢印線がリンク［１］〜リンク［８］で示されている。このノード１〜８とリンク［１］〜［８］が道路のデータであり、地図データとともにあるいは経路探索用のネットワークデータとして蓄積される。本来、車両が走行する道路は上り、下りの双方向の車線があり、それぞれの方向に向きを持ったリンクが記載されるべきであるが、図面および説明が複雑になるため、図９においては、片方向の有向リンク（矢印線）のみを記載している。もちろんこの道路ネットワークは、道路に限らず、路線バス、鉄道などの公共交通機関の路線ネットワークであってもよい。
【００１６】
各リンク［１］〜リンク［８］の矢印線を挟んで記述されている数字はリンクのコストを示しており、リンクのコストとは、例えば、リンクの距離や所要時間を示すものであり、ラベル確定法（ダイクストラ法）における経路探索では、距離や所要時間が最短のリンクをたどり、コストの累積値が最小となる経路を最適な案内経路（距離や時間が最短の案内経路）として経路探索を行うものである。図９において、例えば、リンク［１］のコストは所要時間で４分であることを示し、リンク［２］のコストは１分であることを示している。交通機関を利用するネットワークデータには時刻条件が加味されるため、別途、時刻表の情報をリンクおよびリンクコストに反映させる必要がある。
【００１７】
このような経路ネットワークにおいて、例えば、ノード１からノード６に移動する最適な経路を探索する場合、先ず、ノード１を出発してリンク［１］をたどりノード２に到達する。このリンク［１］のコスト（所要時間）は「４」分である。ノード２からの出リンクは、リンク［２］とリンク［７］であり、そのコストは、「１」分と「４」分である。このようにして順次、ノード６に到達できるリンクをたどり、コストの累計を求めると、第１の経路は、ノード１、ノード２、ノード３、ノード４、ノード５を経てノード６に至る経路であり、そのコスト累積は、「１４」分となる。第２の経路は、ノード１、ノード２、ノード５を経てノード６に至る経路であり、そのコスト累積は「１３」分となる。従って、所要時間が最短となる経路は第２の経路であり、これを案内経路として出力するのが通常の経路探索である。
【００１８】
図１０は、ダイクストラ法（ラベル確定法）を用いて図９のような道路ネットワークにおける経路探索の手順を詳細に説明する概念図である。図１０（ａ）に示すように、出発地がノード１で、目的地がノード６であるものとする。ノード１は出発地であるので、まる印に斜線を引いて示している。以下の経路ネットワーク図においても同様に経路探索が進行しているノードをまる印に斜線を引いて表している。そしてこの出発ノード１のポテンシャルを「Ｐ＝０」と置いて経路探索を開始する。
【００１９】
ノード１から出るリンク（出リンク）はリンク［１］のみである。これを
Extract
［１］０＋４＝４
と表している。この式が表す意味は、リンク［１］はノード１のポテンシャル「Ｐ＝０」に、リンク［１］のリンクコスト「４」（以下単にコストという）を加えたポテンシャルをリンク１が到達するノード２にもたらすという意味である。
【００２０】
すなわち、あるノードのポテンシャルとは、そのノードまでたどってきたリンクのコストの累積値を示すことになる。演算手段は、道路ネットワークのデータを参照してこのポテンシャルの演算を行うものであり、演算結果のポテンシャルは、その結果をもたらすリンクのリンク番号とともに作業用メモリに記憶されていく。すなわち、作業用メモリにはリンク番号とそのリンクに到達するまでにたどってきた各リンクのリンクコストの累積値が記憶されていく。
【００２１】
この作業用メモリのうちソート部分は、いわゆる、「ヒープ（Ｈｅａｐ）」と称されるツリー形式でデータの記憶を行い、記憶したデータ（値）の大小関係に従ったソート処理を行うことができるメモリである。本明細書においては、探索したリンクのリンクコスト累積値とリンク番号を作業用メモリに記憶する処理を「ヒープ登録する」といい、登録されたデータをソートして最小値を求める処理を「ヒープソートする」ということとする。図１０（ａ）の状態では、ヒープ登録した要素が１つしかないので、リンク［１］は最小値「４」であって、図１０（ｂ）に示すようにノード２までの経路がリンク［１］に決定する。すなわち、ノード２のポテンシャルは「Ｐ＝４」に決まり、これが現在の最小ラベルである。
【００２２】
次に、図１０（ｃ）のように、ノード２からは、２本の矢印（出リンク：リンク［２］とリンク［７］）が存在している。この出リンクは、経路探索部がこれからたどろうとするリンクであり、これを探索の拡散といい、ある到達ノードからの出リンクを拡散するリンクと呼ぶこととする。この拡散するリンクの状態が、
Extract
［７］＝４＋４＝８
［２］＝４＋１＝５
で表される。リンク［６］は、ノード２に対する入りリンクであるので選択されない。以下、同様に目的地であるノード６に到達するまでノード、リンクをたどり新たなノードに到達するたびに、拡散するリンクのコストを累計してその拡散するリンクの到達ノードのポテンシャルを算出して行く。
【００２３】
図１０（ｃ）において到達ノード３およびノード５は目的地のノードではないので、探索は更にそれぞれのノード３、ノード５から拡散するリンク［３］、［５］、［８］に進む。このようにして拡散したリンクが目的地のノードに到達するまで探索が行われ、それぞれのリンクが目的地のノード（この例ではノード６）に到達すると、そのルートを経路とした時の目的地ノードのポテンシャル（累計コスト）が確定する。確定したポテンシャルが最も小さいルートが最適経路になる。ノードから拡散するリンク（出リンク）のことを別の用語を用い「発芽するリンク」とも称する。
【００２４】
ここで、作業用メモリにおけるヒープ登録、ヒープソートのためのメモリ構成とその作用について説明する。図１１は、作業用メモリに記憶されるデータの構造を示す概念図であり、（ａ）はツリー状に登録されるデータの概念を示し、（ｂ）は、ツリー状のデータが実際に作業用メモリに記憶される配列を示す図である。図１１（ａ）に示すように、ヒープ登録されるデータの構造はツリー状であるが、実際には、図１１（ｂ）のように作業用メモリ上の配列であって、リンク番号とコストのペアである。例えば、図１１において、Ａはツリーの根となるデータであって、このデータＡに関連するデータＢ、Ｃが連なり、更に、データＢにデータＤとデータＥが、データＣにデータＦとデータＧが連なる構造であるが、実際のデータＡ〜Ｇは、図１１（ｂ）のように作業用メモリ上に配列されて記憶される。
【００２５】
ここで記憶されるデータは、リンク番号とコストのペアであり、経路探索のコストは時間や距離なので非負の数である。このようにしてヒープ登録されたコストを比較してヒープソートを行い、最小のデータをツリーの根（ツリーの頂点）から取り出す。このようにして、コスト最小の経路が決定される。なお、このような探索法を用いて、最適経路だけでなく、コストが小さい順に第１最適経路〜第ｋ最適経路まで、複数の候補経路を探索してユーザに提示する方法を採ることもできる。
【００２６】
上記特許文献２や特許文献３に開示されたナビゲーション装置のように、カーフェリーなどの航路を道路に疑似化して、出発地の港湾、経由地のる港湾、到着地の港湾をノードとし、ノード間をリンクで繋ぎ、リンクコストをカーフェリーの航行所要時間として道路のネットワークデータに加えることで、カーフェリーを利用して移動する経路を経路探索の対象とすることができる。
【００２７】
しかしながら、上記特許文献２や特許文献３に開示された技術を適用した場合、経路探索の演算処理の負荷が大きいという問題がある。前述したようにダイクストラ法を用いた経路探索においては、ノードに到達する毎に探索が拡散していき拡散するリンクの到達ノードにおけるリンクコスト累計値を算出してノードのポテンシャルを決定していく。地図データやネットワークデータは所定の緯度範囲、経度範囲の大きさのメッシュに区分されており、メッシュの境界にもノードが設定され、リンクが区分される。
【００２８】
カーフェリーの航路を道路に疑似して出発港湾、経由港湾、到着港湾をノードとした場合、各ノード間のリンクは論理的には１本のリンクであるが、カーフェリーなどのように港湾間の距離が長い場合には、当然に航路を道路に疑似した時のリンクもメッシュ境界のノードで区分される。このため、出発地点のノードから経路探索が拡散していく過程で、カーフェリーの出発地である港湾のノードに到達した後も、ノード到達、拡散するリンクの選択、リンクの到達ノードのポテンシャル（累計コストの算出）を到着地である港湾のノードに到達するまで繰り返し演算処理しなければならない。すなわち、行く先がわかっている１本道を、区分されたノード、リンクに進む毎に丁寧に探索するという無駄が生じてしまい、経路探索の処理負荷が増大し、また、最適経路の確定に余分な時間がかかるという問題点がある。また、特許文献３の発明は、カーフェリー航路などのコストを大きめに設定するというだけで、カーフェリーを利用した場合の正確な到着時刻を求めるものではない。従って、陸路とどちらが早く到着するかもわからないという問題点がある。
【００２９】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、ワープノードの出リンクのリンクコストに航路の所要時間を加算するようになせば、経路探索の拡散がカーフェリーの出発地点であるノードに到達した時点で瞬時に到着地点であるノードの出リンクに及び、経路探索処理が効率化できることに想到して本発明を完成するに至ったものである。
【００３０】
すなわち、本発明は、上記の問題点を解消することを課題とし、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、効率よく経路探索を行うようにしたナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００３１】
前記課題を解決するために、本願の請求項１にかかる発明は、
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーションシステムにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００３２】
また、本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００３３】
また、本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００３４】
また、本願の請求項４にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項２に記載のナビゲーションシステム。
【００３５】
また、本願の請求項４にかかる発明は、請求項２ないし請求項４の何れかにかかるナビゲーションシステムにおいて、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００３６】
また、本願の請求項６にかかる発明は、
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００３７】
また、本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００３８】
また、本願の請求項８にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００３９】
また、本願の請求項９にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００４０】
また、本願の請求項１０にかかる発明は、請求項７ないし請求項９の何れかにかかる経路探索サーバにおいて、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００４１】
また、本願の請求項１１にかかる発明は、
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００４２】
また、本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００４３】
また、本願の請求項１３にかかる発明は、請求項１２にかかる経路探索方法において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００４４】
また、本願の請求項１４にかかる発明は、請求項１２にかかる経路探索方法において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００４５】
また、本願の請求項１５にかかる発明は、請求項１２ないし請求項１４の何れかにかかる経路探索方法において、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００４６】
また、本願の請求項１６にかかる発明は、
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーション装置において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００４７】
また、本願の請求項１７にかかる発明は、請求項１６にかかるナビゲーション装置において、前記ナビゲーション装置は、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００４８】
また、本願の請求項１８にかかる発明は、請求項１７にかかるナビゲーション装置において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００４９】
また、本願の請求項１９にかかる発明は、請求項１７にかかるナビゲーション装置において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００５０】
また、本願の請求項２０にかかる発明は、請求項１７ないし請求項１９の何れかにかかるナビゲーション装置において、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【発明の効果】
【００５１】
請求項１にかかる発明においては、道路をノードとリンクで表現した経路探索用ネットワークデータを備えラベル確定法を用いて最適経路を探索するナビゲーションシステムにおいて、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続する。
【００５２】
かかる構成によれば、例えば、仙台−苫小牧のカーフェリーの経路区間の両端に、絶対位置情報を持たず、仙台、苫小牧周辺の道路にリンクで接続される同一のワープノードを設定するものであるから、出発地側のカーフェリーの港湾ノード、例えば、仙台側のワープノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノード、例えば、苫小牧側のワープノードの出リンクに拡散が及ぶようにでき、効率よく経路探索を行うことができるようになる。
【００５３】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとする。
【００５４】
かかる構成によれば、探索がワープノードに到達した際にその出リンク（例えば、苫小牧側の道路リンク）の道路リンクのコストに、ワープノードが設定された経路区間の利用コスト、例えば、仙台−苫小牧間のカーフェリーの利用コストを加算した値をリンクコストとするので、出リンクの到達ノードのポテンシャル算出にあたって、ワープノードが設定された経路区間のコストを加味することができ、出発地側のカーフェリーの港湾ノード、例えば、仙台側のワープノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノード、例えば、苫小牧側のワープノードの出リンクに拡散が及ぶようにでき、効率よく経路探索を行うことができるようになる。
【００５５】
請求項３にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出する。
【００５６】
かかる構成によれば、車両が他の交通手段に積載されて移動する経路についても、一般的な電車、バスなどの公共交通機関を用いた経路区間の経路と同様の探索ができ、また、探索条件に時刻条件が設定されている場合にも対応できるようになる。
【００５７】
請求項４にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとする。
【００５８】
かかる構成によれば、車両が積載される他の交通手段が、運行時刻が定まっておらず随時運行される場合であっても、その交通手段を用いて移動する経路区間の利用コストを算出することができる。
【００５９】
請求項５にかかる発明においては、請求項２ないし請求項４の何れかにかかるナビゲーションシステムにおいて、利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むものであるから、より正確に、その交通手段を用いて移動する経路区間の利用コストを算出することができる。
【００６０】
請求項６〜請求項１０にかかる発明においては、請求項１〜請求項５にかかるナビゲーションシステムを構成する経路探索サーバを構成することができ、請求項１１〜１５にかかる発明においては、請求項６〜請求項１０にかかる経路探索サーバにおける経路探索方法を提供することができるようになる。また、請求項１６〜請求項２０にかかる発明においては、請求項１〜請求項５にかかるナビゲーションシステムを適用したスタンドアロンタイプのナビゲーション装置を提供することができるようになる。
【図面の簡単な説明】
【００６１】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】経路探索用ネットワークデータベースに蓄積される道路ネットワークのデータの概念を示す図である。
【図３】経路探索用ネットワークデータベースに蓄積される鉄道、バスなどの通常の公共交通機関の路線ネットワークのデータの概念を示す図である。
【図４】車両が他の交通手段に積載されて移動する経路ネットワークの、本発明にかかるデータの概念を示す図である。
【図５】図４に示すネットワークにおける経路探索の概念を説明するための模式図である。
【図６】図５に示す仙台−苫小牧間の経路探索の概念を説明するための模式図である。
【図７】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図８】ワープノードから発芽するリンクのリンクコスト算出の手順を示すフローチャートである。
【図９】本発明において経路探索の対象となる道路ネットワークの基本を示す概念図である。
【図１０】図１⇒９のネットワーク概念図において、出発地をノード１、目的地をノード６として経路を探索する場合の手順を示す模式図であり、図１０（ａ）ないし（ｃ）は探索の手順を順に示す概念図である。
【図１１】経路探索の過程で作業用メモリに記憶されるデータの構造を示す概念図であり、図１１（ａ）はツリー状に登録されるノードの概念を示し、図１１（ｂ）は、ツリー状のノード、リンクのデータが実際に作業用メモリに記憶される配列を示す図である。
【発明を実施するための形態】
【００６２】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００６３】
図１は、本発明の実施例にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、路線ネットワークや運行時刻表などの情報を提供する交通情報配信サーバ５１などを備えて構成されている。一般にこのような交通情報配信サーバはそれぞれの交通機関事業者によって設置される。
【００６４】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や交通情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や交通情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００６５】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。また、通信型のナビゲーションシステムに限らず、スタンドアロンで動作する車載用のナビゲーションシステム、車載、携帯兼用のナビゲーションシステムであってもよい。
【００６６】
図１に示す端末装置２０は、経路探索条件として出発地、目的地を設定して経路探索サーバ３０に経路探索要求する。経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５、時刻表データベース３７を備え、端末装置２０から経路探索要求があると、経路探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た案内経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。
【００６７】
経路探索要ネットワークデータベース３５には、道路ネットワークのデータ、交通ネットワークのデータが蓄積され、交通ネットワークのデータには、鉄道、バス、航空機、船舶などの公共交通機関の路線ネットワークデータの他に、車両が他の交通手段に積載されて移動する経路のデータも蓄積される。図２、図３は、経路探索用ネットワークデータベース３５に蓄積される道路ネットワークのデータの概念および鉄道、バスなどの通常の公共交通機関の路線ネットワークのデータの概念を示す図である。
【００６８】
道路ネットワークデータは以下のように構成されている。例えば、道路が図２に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
すなわち、図２において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図２では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００６９】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図２において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００７０】
図２ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、先に説明したダイクストラ法を代表とするラベル確定法と呼ばれる周知の手法によって行われる。
【００７１】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図３に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７２】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図３に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７３】
図３に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。
【００７４】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００７５】
例えば、図３において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００７６】
道路ネットワークのデータには、高速道路など車両専用の道路や、公園など車両進入禁止の道路がある、歩行者に対する経路探索、経路案内には後者のような道路は必要であるが、前者のような道路は必要ない。逆に、車両に対する経路探索、経路案内には、前者のような道路は必要であるが、後者のような道路は必要ない。また、出発地から目的地まで徒歩や車両による移動と公共交通機関による移動を併用する場合とそうでない場合とがある。これらのネットワークデータを全て結合して経路探索用ネットワークデータベースに蓄積することもできるが、不用なネットワークのデータが含まれている場合、ラベル確定法による経路探索の拡散が不用なリンクに及んでしまう。
【００７７】
そこで、歩行者用の道路ネットワークのデータ、車両用の道路ネットワークのデータ、交通機関のネットワークデータをそれぞれ別個に蓄積しておき、経路探索時に移動手段（徒歩、車両、公共交通機関）の選択条件によって必要なネットワークデータを結合して経路探索するように構成しておくとよい。ネットワークデータの結合はノードに接続されるリンクを特定しておけば容易に処理できる。例えば、交通ネットワークのデータは、駅や停留所のノードに至る道路ネットワークデータの道路リンクに接続される。従って、交通ネットワークデータの各ノードに道路ネットワークデータのどのリンクが接続されるかを特定しておけばよい。
【００７８】
本発明においては、上記のような通常の公共交通機関のネットワークデータの他に、車両が他の交通手段に積載されて移動する経路についてもネットワークデータを蓄積しておくものであるが、通常の交通ネットワークのデータとは異なる形態のデータで経路探索用ネットワークデータベース３５に記憶しておく。例えば、通常の交通ネットワークデータでは、カーフェリーの航路を道路、交通路線に疑似して出発港湾、経由港湾、到着港湾をノードとし、ノード間をリンクで接続することになる。しかしながら、このようにすると、各ノード間のリンクは論理的には１本のリンクであるが、港湾間の距離が長いため、リンクも地図メッシュ境界のノードで区分され、経路探索の処理負荷が増大する。
【００７９】
そこで、本発明においては、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端のノードを特別の概念のノードとして設定するものである。特別の概念のノードとは、例えば、出発地側のカーフェリーの港湾ノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノードに拡散が及ぶように設定するものであり、具体的には、この両端ノードは、同一ノードであって、絶対位置情報は持たず、前記経路探索用ネットワークデータにおける前記経路区間の両端の近傍の道路リンクに接続されるノードである。
【００８０】
図４は、苫小牧と名古屋間を結ぶカーフェリーにこのようなノードを設定した例を示している。このカーフェリーには途中の寄港地として仙台がある。そこで、苫小牧と仙台にノードＷＮ１を設定し、また、仙台と名古屋にノードＷＮ２を設定する。従って仙台にはノードＷＮ１、ＷＮ２が設定される。このノードＷＮ１、ＷＮ２は緯度、経度で表される地理上（実際）の位置情報は有していない。しかしながらノードＷＮ１、ＷＮ２は、カーフェリーの発着埠頭に至る道路リンクに接続されるように設定されている。
【００８１】
例えば、苫小牧のノードＷＮ１は、苫小牧のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ２００と結ばれる道路リンクＬ２００に接続されるデータ構成を持つ。また、名古屋のノードＷＮ２は、名古屋のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ３００と結ばれる道路リンクＬ３００に接続されるデータ構成を持つ。
【００８２】
仙台のノードＷＮ１、ＷＮ２も同様であり、仙台のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ１００と結ばれる道路リンクＬ１００、Ｌ１０１に接続されるデータ構成を持つ。このようなノードとしてカーフェリーの発着場所を表現すると、出発地側のカーフェリーの港湾ノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノードに拡散が及ぶようにできる。
【００８３】
ここで、仙台のノードをＷＮ１、ＷＮ２に分けた理由であるが、フェリーターミナルをすべて同じノードにしてしまうと、このノードにダイクストラ法を用いた経路探索の拡散が到着した瞬間に、すべての同じノードに拡散が飛び火したように探索されることになる。しかし、そのような探索の広がりは現実的でないので、別ノードとしたものである。ただし、この例の「苫小牧−仙台−名古屋」のカーフェリーは直行便であり、苫小牧（ＷＮ1）−仙台（ＷＮ1，ＷＮ２）−名古屋（ＷＮ２）と探索が拡散するのは差し支えない。従ってこの仙台のようにノードが分けられた場合は、フェリーターミナルの道路ノードＮ１００（リンクＬ１００、Ｌ１０１）に両方のワープノードＷＮ１、ＷＮ２が接続するデータ構造になっている。
【００８４】
図５は、仙台の近傍の出発地Ｓからある目的地への経路探索の概念を説明するための模式図であり、経路探索の進行（拡散）の過程で、探索が図４に示すカーフェリーの仙台のノードに到達する前後の様子を説明する図である。探索が仙台のカーフェリー発着ノード、であるノードＷＮ１、ＷＮ２に接続する道路リンクＬ１００、Ｌ１０１（図４参照）に到達すると、これらのノードＷＮ１、ＷＮ２は、苫小牧側、名古屋側のノードと同一であるから、当該ノードＷＮ１、ＷＮ２から拡散するリンクは、苫小牧側のノードＷＮ１と道路ネットワークのノードＮ２００とを接続するリンクＬ２００（図４参照）になる。また、名古屋側のノードＷＮ２と道路ネットワークのノードＮ３００とを接続するリンクＬ３００（図４参照）になり、瞬時にカーフェリーの到着地側である苫小牧側と名古屋側に探索が及ぶ。なお、仙台のワープノードＷＮ１、ＷＮ２が接続される道路リンクは上記の例ではリンクＬ１００とＬ１０１の別のリンクとしたが、同一の道路リンクであっても差し支えない。
【００８５】
すなわち、出発地Ｓからの拡散が、仙台のノードＷＮ１、ＷＮ２に達した時に（破線円のイメージ）、拡散は苫小牧のノードＷＮ１、名古屋のノードＷＮ２に達したのと等価である。さらに拡散が進むと、出発地Ｓからの拡散が実線円に達すると共に、苫小牧のノードＷＮ１、名古屋のノードＷＮ２からも拡散が成長する。これが本発明におけるノードを用いた探索の作用である。このまま目的地に到達すれば、カーフェリー航路を除く部分の経路がわかったことになる。このようなノードＷＮ１、ＷＮ２の性格から、通常の道路ネットワークのデータや交通ネットワークのデータにおけるノードと区別するため、本発明においては、ノードＷＮ１、ＷＮ２を「ワープノード」と称している。
【００８６】
次いで、到着地側のワープノードから拡散を拡大する際に、カーフェリーの航路（経路区間）のコストを調整、加味する。これにより、カーフェリーのリンクコストが反映され、経路探索が進むことになる。具体的には、ワープノードＷＮ１、ＷＮ２が接続される到着地側の道路リンクＬ２００、Ｌ３００）は道路リンクのコスト（例えば、コストＸ）を有しているが、探索ワープノードＷＮ１、ＷＮ２に到達し、拡散する際のリンクＬ２００、Ｌ３００のコストは道路リンクとしてのコストＸに、仙台・苫小牧間のカーフェリーの利用コスト（例えば、コストＹ）、仙台・名古屋間のカーフェリーの利用コスト（例えば、コストＺ）を加算する。
【００８７】
図６は、１つのワープノードに着目した図であり、図５において、仙台から苫小牧に向かうカーフェリーの経路区間が探索対象となる場合を示す図である。仙台のカーフェリーの端点（港湾または埠頭）に設定されたワープノードＷＮ１は、道路リンクＬ１００により近傍の道路ネットワークのノードＮ１００に接続されている。また、このワープノードＷＮ１は、道路リンクＬ２００により苫小牧のカーフェリーの端点（港湾または埠頭）近傍の道路ネットワークのノードＮ２００に接続されている。
【００８８】
出発地Ｓが仙台近傍である場合（図５参照）、探索が道路ネットワークのノードＮ１００に到達するとノードＮ１００から発芽するリンクＬ１００に拡散し、ワープノードＷＮ１に至る。リンクＬ１００はワープノードＷＮ１の入りリンクである。探索の拡散がワープノードＷＮ１に至ると、ワープノードＷＮ１から発芽するリンクは、出リンクであるリンクＬ２００になる。リンクＬ２００は苫小牧のカーフェリーの端点（港湾または埠頭）に接続される道路リンクであるから、探索がワープノードＷＮ１に到達した時点で瞬時に出発地側の仙台の港湾の近傍から目的地側の苫小牧の港湾の近傍に拡散する。
【００８９】
苫小牧側のリンクＬ２００は、道路リンクとしてのリンクコストＸを有しており、通常のコスト算出ではリンクコストＸが用いられる。しかしながらリンクＬ２００はワープノードＷＮ１から発芽するリンクであるので、仙台と苫小牧間のカーフェリーの経路区間の利用コストＹを加算する。このことにより、苫小牧側のノードＮ２００のポテンシャルは、道路リンクＬ２００のリンクコストＸだけでなく、仙台−苫小牧間のカーフェリーの経路区間の利用コストＹが加味された値になる。
【００９０】
このことは、カーフェリーの経路区間の端点に、近傍の道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードを設定することによって、例えば、図６で説明したように、仙台−苫小牧間のカーフェリーの経路区間を道路に擬似した場合のリンク用いて探索するのと同等の結果が、瞬時に得られるということを示している。すなわち、本発明によれば、カーフェリー経路のリンクを探索する無駄がない。また、探索がワープノードに達したことで、カーフェリーの時刻表を用いてコスト算出する手順に切り替える判定が出来て、実際の運行時刻表に基づいた探索が可能になる。
【００９１】
ここで、カーフェリーの利用コストとは、該当するカーフェリーの運行時刻表を参照して算出される所要時間であり、また、カーフェリーが運行時刻表を有さず随時運行される場合には、該カーフェリーを用いる経路区間の平均所要時間である。更に正確には、利用コストには、ワープノードに到着してから、カーフェリーが出発するまでの待ち時間を含むようにする。このようにすれば、道路を用いて移動する通常の経路の探索とともに、カーフェリーの利用区間を含む経路探索を無駄な処理なく実行できるようになる。
【００９２】
該当するカーフェリーの運行時刻表を参照して算出される所要時間を利用コストとすれば、車両が他の交通手段に積載されて移動する経路についても、一般的な電車、バスなどの公共交通機関を用いた経路区間の経路と同様の探索ができ、また、探索条件に時刻条件が設定されている場合にも対応できるようになる。運行時刻が定まっておらず随時運行される交通手段の場合もその平均所要時間を利用コストとすれば、カーフェリーを用いる経路区間の利用コストを算出することができる。
【００９３】
図７は、以上説明した経路探索処理を行う、本発明の実施例にかかる図１のナビゲーションシステムの詳細な構成を示すブロック図である。
【００９４】
端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、経路再探索要求手段２３、条件設定手段２４、案内経路データ記憶手段２５、表示手段２６、操作入力手段２７を備えて構成される。
【００９５】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００９６】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの入力機能としても用いられる。表示手段２６は液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２６はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。また、表示手段２６にはタッチパネル機能を設け、表示された画像上の所望の部分をタッチして入力する入力手段として機能させてもよい。
【００９７】
経路探索サーバ３０から端末装置２０に送信される案内経路、推奨経路などの案内データは地図データとともに案内経路データ記憶手段２５に記憶され、案内経路データ記憶手段２５に記憶された案内経路などの案内データや地図データは、必要に応じて読み出され、表示手段２６に表示される。
【００９８】
端末装置２０は、条件設定手段２４により経路探索の条件として、出発地、目的地、出発時刻あるいは到着希望時刻などを設定する。本発明においては、更に、カーフェリーなど、車両を積載して運行する公共交通機関を用いた経路を経路探索の対象とするか否かを設定する構成を採る。このようにすれば、ユーザにおいてカーフェリーを利用する頻度が高くないと予想されるので、通常の経路探索の妨げとなることがない。勿論、全ての経路探索において自動的にこのような経路を経路探索対象とすることもできる。
【００９９】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、案内経路データ編集手段３２、コスト算出手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、ワープノード設定手段３６、時刻表データベース３７などを備えて構成される。経路探索用ネットワークデータ３５には、先に説明したように道路ネットワークデータ、交通ネットワークデータ、ワープ設定手段３６が設定したワープノードデータが蓄積され、これらのネットワークデータは経路探索の条件によって適宜結合され、経路探索が行われる。
【０１００】
経路探索サーバ３０は、端末装置２０から経路探索要求があると、これを探索要求記憶手段３８に一時記憶する。そして経路探索手段３９は、探索要求記憶手段３８に記憶した経路探索要求に従って経路探索用ネットワークデータベース３５を参照して出発地から目的地までの複数の候補経路を探索する。経路探索要求が通常の経路探索の要求である場合、経路探索の結果得られた案内経路のデータを地図データベース３４から読み出した地図データとともに端末装置２０に送信する。この経路探索の方法は通常のナビゲーションシステムにおける経路探索サーバと同様、ダイクストラ法に代表されるラベル確定法を用いるものである。
【０１０１】
経路探索の結果得られた案内経路のデータは、地図データとともに端末装置２０に送信される。地図データは端末装置２０の現在位置を含む所定範囲の単位地図データ（緯度・経度で所定の大きさのエリアに区分された地図データ）が地図データベース３４から読み出される。案内経路データ編集手段３２は、地図データや案内経路のデータを端末装置２０に送信するための案内情報（データ）に編集する。
【０１０２】
時刻表データベース３７には、電車、バス、航空機、船舶などの公共交通機関の路線データ、時刻表データが蓄積される。また、人が乗車する公共交通機関の他、カーフェリーやカートレインのような車両を積載して移動する経路の路線（航路）および時刻表データも蓄積されている。
【０１０３】
ワープノード設定手段３６は、カーフェリーやカートレインのような車両を積載して移動する経路の路線（航路）のデータに基づいて、その経路区間の両端点、例えば、出発地と経由地、経由地と経由地、経由地と到着地にワープノードを設定する。このワープノードは、端点のそれぞれの近傍の道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したものである。ワープノードの具体例は、既に図４〜図６を参照して説明したとおりである。設定されたワープノードのネットワークデータは経路探索用ネットワークデータベース３５に蓄積される。
【０１０４】
端末装置２０からの経路探索要求に設定された経路探索条件が、カーフェリーなど、車両を積載して移動する経路区間を探索の対象に含む場合、経路探索手段３９が出発地から目的地までの経路を探索するにあたって、経路探索用ネットワークデータベース３５に蓄積された道路ネットワークデータに、ワープノードのデータを結合して経路探索をたん行う。ワープノードは、カーフェリーの経路区間の両端点に同一ノードとして設定され、端点のそれぞれの近傍の道路リンクに接続されるものであるから、道路ネットワークデータに容易に結合することができる（例えば、図４参照）。
【０１０５】
経路探索手段３９が経路探索を行う過程で、探索がワープノード、例えば、図６のリンクＬ１００（仙台側）からＷＮ１に到達すると、リンクコスト算出手段３３は、ワープノードから拡散するリンク（発芽するリンク、例えば、図６のリンクＬ２００（苫小牧側）のリンクコストを算出する。ここで算出するリンクコストは、リンクＬ２００のリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加えたものである。経路探索手段３９はワープノードＷＮ１から先に経路探索を進める際には、リンクＬ２００のリンクコストをリンクコスト算出手段３３が算出した前述の値（リンクＬ２００のリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加えたもの）を使用して到達ノード（例えば、図６のＮ２００）のポテンシャルを算出する。
【０１０６】
ここで、カーフェリーの利用コストとは、先に説明したように、該当するカーフェリーの運行時刻表を参照して算出される所要時間、または、該カーフェリーを用いる経路区間の平均所要時間であり、この利用コストには、ワープノードに到着してから、カーフェリーが出発するまでの待ち時間を含むようにしてもよい。従って、道路を用いて移動する通常の経路の探索とともに、カーフェリーの利用区間を含む経路探索を無駄な処理なく実行できるようになる。
【０１０７】
図８は、ワープノードから発芽するリンクのリンクコスト算出の手順を示すフローチャートである。経路探索手段３９が、探索が及んだリンクをダイクストラ法に従いメモリ（ヒープ：図１１参照）に記憶する際の処理を示している。経路探索手段３９は、経路探索の到達ノードがワープノード、例えば、ワープノードＷＮ１、ＷＮ２（図５参照）であるか否かをチッェクする。ワープノードであれば、探索がそのワープノードから拡散するか否かを判定する（ステップＤ１０１）。通常このステップではワープノードから拡散する判定が得られるが、そうでない場合（ステップＳ１０１のＮＯ）は何もせずにリターンする。ワープノードである場合（ステップＳ１０１のＹＥＳ）、ステップＳ１０２に進み、リンクコスト算出手段３３によりワープノードの出リンク（発芽するリンク）のリンクコストを算出させ、その値を出リンクのリンクコストとしてリターンする。
【０１０８】
ここで算出するリンクコストは、先に説明したように、例えば、図６に示すワープノードＷＮ１の場合、リンクＬ２００の道路リンクとしてのリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加算したものである。経路探索手段３９はこのようにして算出されたリンクコストを用いて到着側のワープノードから先の探索を継続する。
【０１０９】
例えば、カーフェリー航路の所要時間をコストに代入してもよいし、さらに正確には
そのワープノードへの到達時刻から、フェリーに乗船してワープノードの出リンクに至るまでの時間を、カーフェリー時刻表を参照して求める。具体的には、仙台のワープノードＷＮ１の到達時刻が１６：００。次に乗船できるカーフェリーの出港が１９：４０。苫小牧への到着が翌日の１１：００。もともとの、出リンクＬ２００コストが1分である場合は、出リンクＬ２００のコストを「１９時間1分」に変更してリターンする。なお、ワープノードからの出リンクが複数ある場合は、それぞれにリンクコストの算出（ステップＳ１０２）を実行する。また、時刻表がなく渡し船のように随時運行されるものについては、平均所要時間をコストに採用する。
【０１１０】
なお、上記実施例の説明において、ワープノード設定手段３６が予めカーフェリーなどの経路区間の端点にワープノードを設定し、経路探索用ネットワークデータベース３５に蓄積しておく例を説明したが、本発明はこれに限られるものではなく、経路探索条件としてカーフェリーなどの経路区間を経路探索の対象とする設定を含む経路探索要求があった場合に、ワープノード設定手段３６が時刻表データベースに蓄積されたデータに基づいてワープノードを設定し、経路探索用ネットワークデータベース３５の道路ネットワークデータに結合するようにしてもよい。
【０１１１】
また、実施例においては、ワープノードから発芽するリンクのリンクコスト算出をリンクコスト算出手段３３が行う例を示したが、これに限られるものではなく、経路探索手段３９が経路探索する過程で、このリンクコストの算出を行った上で該リンクによって到達するノードのポテンシャルを算出するようにしてもよい。また、装置の分散・統合の具体的形態は上記説明した実施形態のものに限られず、その全部または一部を、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１１２】
以上、詳細に説明したように、本発明によるナビゲーションシステムによれば、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードであって、絶対位置情報は持たず、該経路区間の両端の近傍の道路リンクに接続されるワープノードを設定することによって、通常の道路を移動する経路野探索とともに、車両が他の交通手段に積載されて移動する経路も、効率よく探索することができるようになる。すなわち、カーフェリーを使う場合も、陸路だけで行く場合も同じ探索で探索が進むため、最適経路が求められる。出リンクのコストは大きくなるので、しばらくはメモリ（ヒープ）に留まるが、離島などを探索した場合は陸路では到達できないため、いずれヒープから取り出され、探索経路となる。
【産業上の利用可能性】
【０１１３】
本発明は、車載用のナビゲーションシステムに限らず、通信型の携帯ナビゲーションシステム、車載、携帯兼用のナビゲーションシステムにも適用することができる。また、本発明の経路探索は、実際に車両を積載せずに、ユーザのみがカーフェリーなどの交通手段を用いて移動する場合にも適用することができる。
【符号の説明】
【０１１４】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・経路再探索要求手段
２４・・・・条件設定手段
２５・・・・案内経路データ記憶手段
２６・・・・表示手段
２７・・・・操作入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・案内データ編集手段
３３・・・・リンクコスト算出手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・ワープノード設定手段
３７・・・・時刻表データベース
３８・・・・探索要求記憶手段
３９・・・・経路探索手段
【技術分野】
【０００１】
本発明は、設定された出発地から目的地までの最適経路を探索して案内するナビゲーションシステムであって、経路探索用の道路ネットワークデータに、カーフェリーなどの航路データを擬似的な道路データとして付加し、車載用ナビゲーション装置がカーフェリーなど他の交通手段に積載されて移動する経路区間も経路探索の対象とするようにしたナビゲーションシステムの改良に関するものであり、特に、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、効率よく経路探索を行うようにしたナビゲーションシステムに関するものである。
【背景技術】
【０００２】
従来から自動車の運転者に出発地から目的地までの最適な経路を案内する車載用のナビゲーション装置が提供されている。従来のナビゲーション装置は、地図データを記録したＣＤ−ＲＯＭ又はＩＣカード等の地図データ記憶装置と、ディスプレイ装置と、ジャイロ、ＧＰＳ（Global Positioning System）及び車速センサ等の車両の現在位置及び現在方位を検出する車両移動検出装置等を有し、車両の現在位置を含む地図データを地図データ記憶装置から読み出し、該地図データに基づいて車両位置の周囲の地図画像をディスプレイ装置上に描画する。また、車両位置マーク（ロケーション）をディスプレイ画面の地図画像に重ね合わせて表示し、車両の移動に応じて地図画像をスクロール表示したり、地図画像を画面に固定し車両位置マークを移動させたりして、車両が現在どこを走行しているのかを一目で判るようにしている。
【０００３】
通常、このような車載用ナビゲーション装置には、運転者が所望の目的地に向けて道路を間違うことなく容易に走行できるようにした経路案内機能が搭載されている。この経路案内機能によれば、地図データを用いて出発地から目的地までを結ぶ最もコストが小さい経路を、ダイクストラ法等を用いたシミュレーション計算を行って経路探索し、その探索した経路を案内経路として記憶しておき、走行中、地図画像上に案内経路を他の道路とは色を変えて太く描画して画面表示したり、車両が案内経路上の進路を変更すべき交差点に一定距離内に近づいたときに、地図画像上の進路を変更すべき交差点に進路を示す矢印を描画して画面表示したりすることで目的地までの最適な経路を運転者が簡単に把握できるようにしている。
【０００４】
上記の車載用のナビゲーション装置は、経路探索機能や地図データを持つスタンドアロン型のナビゲーション装置であるが、このようなナビゲーション装置はナビゲーションに必要な全ての機能を備えている必要があり、装置が大型化し価格も高いものとなっていた。近年の通信、情報処理技術の発展により車載用のナビゲーション装置にネットワークを介した通信機能を付加し経路探索サーバとデータ通信して案内経路データや地図データを取得するいわゆる通信型のナビゲーションシステムも普及してきており、車載、携帯兼用のナビゲーション装置も提供されている。更には、歩行者用のナビゲーションシステムとして携帯電話をナビゲーション端末としたシステムも実用化されている。携帯電話をナビゲーション端末としたシステムであっても、助手席に乗車した操作者が経路探索して運転者を案内する、助手席ナビとして用いることができる。
【０００５】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００６】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００７】
経路探索して得た出発地から目的地までの経路のうち、経路の累計コスト（距離または時間）が最小となる経路が最適な案内経路として決定され、案内経路データが作成される。案内経路データには、最適経路のデータの他に地図データ、ガイダンスデータが含まれ、案内経路データは必要に応じて案内データ記憶手段から読み出され表示手段に表示される。一般的には、ナビゲーション装置が有するＧＰＳ受信機を用いて測位したナビゲーション装置の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、ナビゲーション装置の現在位置を示すマークを重ね合わせ、該現在位置マークが表示画面の中心になるように表示する。
【０００８】
ＧＰＳ受信機を用いて測位した位置情報には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理や地図上の最も近い道路上に補正するマップマッチング処理が行われる。また、案内経路データに交差点などのガイダンスポイントが設定され、そのガイダンスポイントにおけるガイダンスとして音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力して利用者をガイドする。
【０００９】
また、ナビゲーション装置が歩行用に用いられる場合、交通機関を用いた経路区間を含む経路探索ができるように、道路ネットワークデータに加えて、交通ネットワークデータベースを備えている。交通ネットワークのデータは、各交通路線を道路のように扱い、交通路線の各駅をノードとし、各駅間を結ぶ区間をリンクとするものであるが、道路ネットワークのデータとリンクデータが異なる。交通ネットワークのデータにおけるリンクは、交通機関の時刻表データによって定まる各電車やバスなどの移動手段の個々がリンクを構成する。従って、交通ネットワークのデータにおけるリンクのデータは、端点のノードである駅を出発する出発時刻と、他の端点のノードである駅に到着する時刻が定まっており、出発時刻と到着時刻との差である所要時間がリンクコストとなる。
【００１０】
ところで、ナビゲーション装置が移動し得る経路には、道路や交通機関を用いた経路の他に、カーフェリーやカートレインなどナビゲーション装置が搭載された車両が、船や鉄道車両に積載されて移動する経路も存在する。従って、経路探索の対象としてカーフェリーやカートレインなどナビゲーション装置が搭載された車両が、船や鉄道車両に積載されて移動する経路も一般の道路を移動する経路とともに探索されることが好ましい。一般に、カーフェリーやカートレインでは、乗降ターミナルである港湾や鉄道の駅などの端点（ノード）間を結ぶリンクの合計距離は、道路や交通路線のノードを繋ぐリンクよりも圧倒的に長い。また、各端点における船や電車の発着時刻が定まっており、道路ネットワークのデータよりは交通ネットワークのデータに近い性格を有する。
【００１１】
カーフェリーの航路を擬似的な道路データとして表現し、道路ネットワークのデータに結合して経路探索の対象に含めるようにした車載ナビゲーション装置は、例えば、下記の特許文献２（特許第２５５６６２２号公報）や特許文献３（特許第２６２３３９４号公報）に開示されている。
【００１２】
特許文献２に開示された車載ナビゲータの発明は、記憶手段に記憶された道路データを参照して、走行誘導経路計算手段で現在地から目的地までの走行誘導経路を求め、地図画像上に経路誘導表示を行うようにした車載ナビゲータにおいて、記憶手段の道路データに、予め、実際の道路以外で車両が移動可能な交通路も擬似的な道路として含めておき、走行誘導経路計算手段は、道路データの実際の道路と擬似的な道路の両者を対象にして走行誘導経路を求めるようにしたものである。
【００１３】
特許文献３に開示された車載ナビゲーション装置の発明は、実際の道路形状を線分によって折線近似したときの各線分の位置および相互の接続状態に関するデータからなるデジタル地図データにもとづいて、画面に写し出される道路地図上に設定された出発点から目的地に到るまでの経路の探索をなして車両の走行案内を行わせる車両走行案内装置において、道路地図上の既存の道路と連結した航路などの道路外の路のデータをデジタル地図データ内に組み込んで、出発点と目的地との間に航路などの道路外の路が介在するときの経路探索を行わせるようにしたものであり、航路など道路外の線分のコストをみかけ上大きくしたうえでコスト最小の経路を探索するようにしたものである。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特許第２５５６６２２号公報
【特許文献３】特許第２６２３３９４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
先ず、ダイクストラ法に代表されるラベル確定法を用いる一般的な経路探索の方法について説明する。図９は、本発明において経路探索の対象とする道路ネットワークの基本構成を説明するための概念図である。図９において、道路の交差点、屈曲点がノード１〜８（まるで囲んだ数字）で示され、各ノード１〜８の間を連結する矢印線がリンク［１］〜リンク［８］で示されている。このノード１〜８とリンク［１］〜［８］が道路のデータであり、地図データとともにあるいは経路探索用のネットワークデータとして蓄積される。本来、車両が走行する道路は上り、下りの双方向の車線があり、それぞれの方向に向きを持ったリンクが記載されるべきであるが、図面および説明が複雑になるため、図９においては、片方向の有向リンク（矢印線）のみを記載している。もちろんこの道路ネットワークは、道路に限らず、路線バス、鉄道などの公共交通機関の路線ネットワークであってもよい。
【００１６】
各リンク［１］〜リンク［８］の矢印線を挟んで記述されている数字はリンクのコストを示しており、リンクのコストとは、例えば、リンクの距離や所要時間を示すものであり、ラベル確定法（ダイクストラ法）における経路探索では、距離や所要時間が最短のリンクをたどり、コストの累積値が最小となる経路を最適な案内経路（距離や時間が最短の案内経路）として経路探索を行うものである。図９において、例えば、リンク［１］のコストは所要時間で４分であることを示し、リンク［２］のコストは１分であることを示している。交通機関を利用するネットワークデータには時刻条件が加味されるため、別途、時刻表の情報をリンクおよびリンクコストに反映させる必要がある。
【００１７】
このような経路ネットワークにおいて、例えば、ノード１からノード６に移動する最適な経路を探索する場合、先ず、ノード１を出発してリンク［１］をたどりノード２に到達する。このリンク［１］のコスト（所要時間）は「４」分である。ノード２からの出リンクは、リンク［２］とリンク［７］であり、そのコストは、「１」分と「４」分である。このようにして順次、ノード６に到達できるリンクをたどり、コストの累計を求めると、第１の経路は、ノード１、ノード２、ノード３、ノード４、ノード５を経てノード６に至る経路であり、そのコスト累積は、「１４」分となる。第２の経路は、ノード１、ノード２、ノード５を経てノード６に至る経路であり、そのコスト累積は「１３」分となる。従って、所要時間が最短となる経路は第２の経路であり、これを案内経路として出力するのが通常の経路探索である。
【００１８】
図１０は、ダイクストラ法（ラベル確定法）を用いて図９のような道路ネットワークにおける経路探索の手順を詳細に説明する概念図である。図１０（ａ）に示すように、出発地がノード１で、目的地がノード６であるものとする。ノード１は出発地であるので、まる印に斜線を引いて示している。以下の経路ネットワーク図においても同様に経路探索が進行しているノードをまる印に斜線を引いて表している。そしてこの出発ノード１のポテンシャルを「Ｐ＝０」と置いて経路探索を開始する。
【００１９】
ノード１から出るリンク（出リンク）はリンク［１］のみである。これを
Extract
［１］０＋４＝４
と表している。この式が表す意味は、リンク［１］はノード１のポテンシャル「Ｐ＝０」に、リンク［１］のリンクコスト「４」（以下単にコストという）を加えたポテンシャルをリンク１が到達するノード２にもたらすという意味である。
【００２０】
すなわち、あるノードのポテンシャルとは、そのノードまでたどってきたリンクのコストの累積値を示すことになる。演算手段は、道路ネットワークのデータを参照してこのポテンシャルの演算を行うものであり、演算結果のポテンシャルは、その結果をもたらすリンクのリンク番号とともに作業用メモリに記憶されていく。すなわち、作業用メモリにはリンク番号とそのリンクに到達するまでにたどってきた各リンクのリンクコストの累積値が記憶されていく。
【００２１】
この作業用メモリのうちソート部分は、いわゆる、「ヒープ（Ｈｅａｐ）」と称されるツリー形式でデータの記憶を行い、記憶したデータ（値）の大小関係に従ったソート処理を行うことができるメモリである。本明細書においては、探索したリンクのリンクコスト累積値とリンク番号を作業用メモリに記憶する処理を「ヒープ登録する」といい、登録されたデータをソートして最小値を求める処理を「ヒープソートする」ということとする。図１０（ａ）の状態では、ヒープ登録した要素が１つしかないので、リンク［１］は最小値「４」であって、図１０（ｂ）に示すようにノード２までの経路がリンク［１］に決定する。すなわち、ノード２のポテンシャルは「Ｐ＝４」に決まり、これが現在の最小ラベルである。
【００２２】
次に、図１０（ｃ）のように、ノード２からは、２本の矢印（出リンク：リンク［２］とリンク［７］）が存在している。この出リンクは、経路探索部がこれからたどろうとするリンクであり、これを探索の拡散といい、ある到達ノードからの出リンクを拡散するリンクと呼ぶこととする。この拡散するリンクの状態が、
Extract
［７］＝４＋４＝８
［２］＝４＋１＝５
で表される。リンク［６］は、ノード２に対する入りリンクであるので選択されない。以下、同様に目的地であるノード６に到達するまでノード、リンクをたどり新たなノードに到達するたびに、拡散するリンクのコストを累計してその拡散するリンクの到達ノードのポテンシャルを算出して行く。
【００２３】
図１０（ｃ）において到達ノード３およびノード５は目的地のノードではないので、探索は更にそれぞれのノード３、ノード５から拡散するリンク［３］、［５］、［８］に進む。このようにして拡散したリンクが目的地のノードに到達するまで探索が行われ、それぞれのリンクが目的地のノード（この例ではノード６）に到達すると、そのルートを経路とした時の目的地ノードのポテンシャル（累計コスト）が確定する。確定したポテンシャルが最も小さいルートが最適経路になる。ノードから拡散するリンク（出リンク）のことを別の用語を用い「発芽するリンク」とも称する。
【００２４】
ここで、作業用メモリにおけるヒープ登録、ヒープソートのためのメモリ構成とその作用について説明する。図１１は、作業用メモリに記憶されるデータの構造を示す概念図であり、（ａ）はツリー状に登録されるデータの概念を示し、（ｂ）は、ツリー状のデータが実際に作業用メモリに記憶される配列を示す図である。図１１（ａ）に示すように、ヒープ登録されるデータの構造はツリー状であるが、実際には、図１１（ｂ）のように作業用メモリ上の配列であって、リンク番号とコストのペアである。例えば、図１１において、Ａはツリーの根となるデータであって、このデータＡに関連するデータＢ、Ｃが連なり、更に、データＢにデータＤとデータＥが、データＣにデータＦとデータＧが連なる構造であるが、実際のデータＡ〜Ｇは、図１１（ｂ）のように作業用メモリ上に配列されて記憶される。
【００２５】
ここで記憶されるデータは、リンク番号とコストのペアであり、経路探索のコストは時間や距離なので非負の数である。このようにしてヒープ登録されたコストを比較してヒープソートを行い、最小のデータをツリーの根（ツリーの頂点）から取り出す。このようにして、コスト最小の経路が決定される。なお、このような探索法を用いて、最適経路だけでなく、コストが小さい順に第１最適経路〜第ｋ最適経路まで、複数の候補経路を探索してユーザに提示する方法を採ることもできる。
【００２６】
上記特許文献２や特許文献３に開示されたナビゲーション装置のように、カーフェリーなどの航路を道路に疑似化して、出発地の港湾、経由地のる港湾、到着地の港湾をノードとし、ノード間をリンクで繋ぎ、リンクコストをカーフェリーの航行所要時間として道路のネットワークデータに加えることで、カーフェリーを利用して移動する経路を経路探索の対象とすることができる。
【００２７】
しかしながら、上記特許文献２や特許文献３に開示された技術を適用した場合、経路探索の演算処理の負荷が大きいという問題がある。前述したようにダイクストラ法を用いた経路探索においては、ノードに到達する毎に探索が拡散していき拡散するリンクの到達ノードにおけるリンクコスト累計値を算出してノードのポテンシャルを決定していく。地図データやネットワークデータは所定の緯度範囲、経度範囲の大きさのメッシュに区分されており、メッシュの境界にもノードが設定され、リンクが区分される。
【００２８】
カーフェリーの航路を道路に疑似して出発港湾、経由港湾、到着港湾をノードとした場合、各ノード間のリンクは論理的には１本のリンクであるが、カーフェリーなどのように港湾間の距離が長い場合には、当然に航路を道路に疑似した時のリンクもメッシュ境界のノードで区分される。このため、出発地点のノードから経路探索が拡散していく過程で、カーフェリーの出発地である港湾のノードに到達した後も、ノード到達、拡散するリンクの選択、リンクの到達ノードのポテンシャル（累計コストの算出）を到着地である港湾のノードに到達するまで繰り返し演算処理しなければならない。すなわち、行く先がわかっている１本道を、区分されたノード、リンクに進む毎に丁寧に探索するという無駄が生じてしまい、経路探索の処理負荷が増大し、また、最適経路の確定に余分な時間がかかるという問題点がある。また、特許文献３の発明は、カーフェリー航路などのコストを大きめに設定するというだけで、カーフェリーを利用した場合の正確な到着時刻を求めるものではない。従って、陸路とどちらが早く到着するかもわからないという問題点がある。
【００２９】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、ワープノードの出リンクのリンクコストに航路の所要時間を加算するようになせば、経路探索の拡散がカーフェリーの出発地点であるノードに到達した時点で瞬時に到着地点であるノードの出リンクに及び、経路探索処理が効率化できることに想到して本発明を完成するに至ったものである。
【００３０】
すなわち、本発明は、上記の問題点を解消することを課題とし、カーフェリーなど、車両を積載して運行する公共交通機関であって、ターミナルである港湾などの区間を長距離に渡って運行される交通機関の出発地点と経由地点、経由地点同志、経由地点と到着地点のノードを、道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードとして道路ネットワークに加え、効率よく経路探索を行うようにしたナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００３１】
前記課題を解決するために、本願の請求項１にかかる発明は、
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーションシステムにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００３２】
また、本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００３３】
また、本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００３４】
また、本願の請求項４にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項２に記載のナビゲーションシステム。
【００３５】
また、本願の請求項４にかかる発明は、請求項２ないし請求項４の何れかにかかるナビゲーションシステムにおいて、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００３６】
また、本願の請求項６にかかる発明は、
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００３７】
また、本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００３８】
また、本願の請求項８にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００３９】
また、本願の請求項９にかかる発明は、請求項７にかかる経路探索サーバにおいて、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００４０】
また、本願の請求項１０にかかる発明は、請求項７ないし請求項９の何れかにかかる経路探索サーバにおいて、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００４１】
また、本願の請求項１１にかかる発明は、
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００４２】
また、本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００４３】
また、本願の請求項１３にかかる発明は、請求項１２にかかる経路探索方法において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００４４】
また、本願の請求項１４にかかる発明は、請求項１２にかかる経路探索方法において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００４５】
また、本願の請求項１５にかかる発明は、請求項１２ないし請求項１４の何れかにかかる経路探索方法において、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【００４６】
また、本願の請求項１６にかかる発明は、
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーション装置において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする。
【００４７】
また、本願の請求項１７にかかる発明は、請求項１６にかかるナビゲーション装置において、前記ナビゲーション装置は、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする。
【００４８】
また、本願の請求項１８にかかる発明は、請求項１７にかかるナビゲーション装置において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする。
【００４９】
また、本願の請求項１９にかかる発明は、請求項１７にかかるナビゲーション装置において、前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする。
【００５０】
また、本願の請求項２０にかかる発明は、請求項１７ないし請求項１９の何れかにかかるナビゲーション装置において、前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする。
【発明の効果】
【００５１】
請求項１にかかる発明においては、道路をノードとリンクで表現した経路探索用ネットワークデータを備えラベル確定法を用いて最適経路を探索するナビゲーションシステムにおいて、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続する。
【００５２】
かかる構成によれば、例えば、仙台−苫小牧のカーフェリーの経路区間の両端に、絶対位置情報を持たず、仙台、苫小牧周辺の道路にリンクで接続される同一のワープノードを設定するものであるから、出発地側のカーフェリーの港湾ノード、例えば、仙台側のワープノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノード、例えば、苫小牧側のワープノードの出リンクに拡散が及ぶようにでき、効率よく経路探索を行うことができるようになる。
【００５３】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとする。
【００５４】
かかる構成によれば、探索がワープノードに到達した際にその出リンク（例えば、苫小牧側の道路リンク）の道路リンクのコストに、ワープノードが設定された経路区間の利用コスト、例えば、仙台−苫小牧間のカーフェリーの利用コストを加算した値をリンクコストとするので、出リンクの到達ノードのポテンシャル算出にあたって、ワープノードが設定された経路区間のコストを加味することができ、出発地側のカーフェリーの港湾ノード、例えば、仙台側のワープノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノード、例えば、苫小牧側のワープノードの出リンクに拡散が及ぶようにでき、効率よく経路探索を行うことができるようになる。
【００５５】
請求項３にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出する。
【００５６】
かかる構成によれば、車両が他の交通手段に積載されて移動する経路についても、一般的な電車、バスなどの公共交通機関を用いた経路区間の経路と同様の探索ができ、また、探索条件に時刻条件が設定されている場合にも対応できるようになる。
【００５７】
請求項４にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとする。
【００５８】
かかる構成によれば、車両が積載される他の交通手段が、運行時刻が定まっておらず随時運行される場合であっても、その交通手段を用いて移動する経路区間の利用コストを算出することができる。
【００５９】
請求項５にかかる発明においては、請求項２ないし請求項４の何れかにかかるナビゲーションシステムにおいて、利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むものであるから、より正確に、その交通手段を用いて移動する経路区間の利用コストを算出することができる。
【００６０】
請求項６〜請求項１０にかかる発明においては、請求項１〜請求項５にかかるナビゲーションシステムを構成する経路探索サーバを構成することができ、請求項１１〜１５にかかる発明においては、請求項６〜請求項１０にかかる経路探索サーバにおける経路探索方法を提供することができるようになる。また、請求項１６〜請求項２０にかかる発明においては、請求項１〜請求項５にかかるナビゲーションシステムを適用したスタンドアロンタイプのナビゲーション装置を提供することができるようになる。
【図面の簡単な説明】
【００６１】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】経路探索用ネットワークデータベースに蓄積される道路ネットワークのデータの概念を示す図である。
【図３】経路探索用ネットワークデータベースに蓄積される鉄道、バスなどの通常の公共交通機関の路線ネットワークのデータの概念を示す図である。
【図４】車両が他の交通手段に積載されて移動する経路ネットワークの、本発明にかかるデータの概念を示す図である。
【図５】図４に示すネットワークにおける経路探索の概念を説明するための模式図である。
【図６】図５に示す仙台−苫小牧間の経路探索の概念を説明するための模式図である。
【図７】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図８】ワープノードから発芽するリンクのリンクコスト算出の手順を示すフローチャートである。
【図９】本発明において経路探索の対象となる道路ネットワークの基本を示す概念図である。
【図１０】図１⇒９のネットワーク概念図において、出発地をノード１、目的地をノード６として経路を探索する場合の手順を示す模式図であり、図１０（ａ）ないし（ｃ）は探索の手順を順に示す概念図である。
【図１１】経路探索の過程で作業用メモリに記憶されるデータの構造を示す概念図であり、図１１（ａ）はツリー状に登録されるノードの概念を示し、図１１（ｂ）は、ツリー状のノード、リンクのデータが実際に作業用メモリに記憶される配列を示す図である。
【発明を実施するための形態】
【００６２】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００６３】
図１は、本発明の実施例にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、路線ネットワークや運行時刻表などの情報を提供する交通情報配信サーバ５１などを備えて構成されている。一般にこのような交通情報配信サーバはそれぞれの交通機関事業者によって設置される。
【００６４】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や交通情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や交通情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００６５】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。また、通信型のナビゲーションシステムに限らず、スタンドアロンで動作する車載用のナビゲーションシステム、車載、携帯兼用のナビゲーションシステムであってもよい。
【００６６】
図１に示す端末装置２０は、経路探索条件として出発地、目的地を設定して経路探索サーバ３０に経路探索要求する。経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５、時刻表データベース３７を備え、端末装置２０から経路探索要求があると、経路探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た案内経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。
【００６７】
経路探索要ネットワークデータベース３５には、道路ネットワークのデータ、交通ネットワークのデータが蓄積され、交通ネットワークのデータには、鉄道、バス、航空機、船舶などの公共交通機関の路線ネットワークデータの他に、車両が他の交通手段に積載されて移動する経路のデータも蓄積される。図２、図３は、経路探索用ネットワークデータベース３５に蓄積される道路ネットワークのデータの概念および鉄道、バスなどの通常の公共交通機関の路線ネットワークのデータの概念を示す図である。
【００６８】
道路ネットワークデータは以下のように構成されている。例えば、道路が図２に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
すなわち、図２において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図２では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００６９】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図２において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００７０】
図２ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、先に説明したダイクストラ法を代表とするラベル確定法と呼ばれる周知の手法によって行われる。
【００７１】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図３に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７２】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図３に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７３】
図３に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。
【００７４】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【００７５】
例えば、図３において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００７６】
道路ネットワークのデータには、高速道路など車両専用の道路や、公園など車両進入禁止の道路がある、歩行者に対する経路探索、経路案内には後者のような道路は必要であるが、前者のような道路は必要ない。逆に、車両に対する経路探索、経路案内には、前者のような道路は必要であるが、後者のような道路は必要ない。また、出発地から目的地まで徒歩や車両による移動と公共交通機関による移動を併用する場合とそうでない場合とがある。これらのネットワークデータを全て結合して経路探索用ネットワークデータベースに蓄積することもできるが、不用なネットワークのデータが含まれている場合、ラベル確定法による経路探索の拡散が不用なリンクに及んでしまう。
【００７７】
そこで、歩行者用の道路ネットワークのデータ、車両用の道路ネットワークのデータ、交通機関のネットワークデータをそれぞれ別個に蓄積しておき、経路探索時に移動手段（徒歩、車両、公共交通機関）の選択条件によって必要なネットワークデータを結合して経路探索するように構成しておくとよい。ネットワークデータの結合はノードに接続されるリンクを特定しておけば容易に処理できる。例えば、交通ネットワークのデータは、駅や停留所のノードに至る道路ネットワークデータの道路リンクに接続される。従って、交通ネットワークデータの各ノードに道路ネットワークデータのどのリンクが接続されるかを特定しておけばよい。
【００７８】
本発明においては、上記のような通常の公共交通機関のネットワークデータの他に、車両が他の交通手段に積載されて移動する経路についてもネットワークデータを蓄積しておくものであるが、通常の交通ネットワークのデータとは異なる形態のデータで経路探索用ネットワークデータベース３５に記憶しておく。例えば、通常の交通ネットワークデータでは、カーフェリーの航路を道路、交通路線に疑似して出発港湾、経由港湾、到着港湾をノードとし、ノード間をリンクで接続することになる。しかしながら、このようにすると、各ノード間のリンクは論理的には１本のリンクであるが、港湾間の距離が長いため、リンクも地図メッシュ境界のノードで区分され、経路探索の処理負荷が増大する。
【００７９】
そこで、本発明においては、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端のノードを特別の概念のノードとして設定するものである。特別の概念のノードとは、例えば、出発地側のカーフェリーの港湾ノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノードに拡散が及ぶように設定するものであり、具体的には、この両端ノードは、同一ノードであって、絶対位置情報は持たず、前記経路探索用ネットワークデータにおける前記経路区間の両端の近傍の道路リンクに接続されるノードである。
【００８０】
図４は、苫小牧と名古屋間を結ぶカーフェリーにこのようなノードを設定した例を示している。このカーフェリーには途中の寄港地として仙台がある。そこで、苫小牧と仙台にノードＷＮ１を設定し、また、仙台と名古屋にノードＷＮ２を設定する。従って仙台にはノードＷＮ１、ＷＮ２が設定される。このノードＷＮ１、ＷＮ２は緯度、経度で表される地理上（実際）の位置情報は有していない。しかしながらノードＷＮ１、ＷＮ２は、カーフェリーの発着埠頭に至る道路リンクに接続されるように設定されている。
【００８１】
例えば、苫小牧のノードＷＮ１は、苫小牧のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ２００と結ばれる道路リンクＬ２００に接続されるデータ構成を持つ。また、名古屋のノードＷＮ２は、名古屋のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ３００と結ばれる道路リンクＬ３００に接続されるデータ構成を持つ。
【００８２】
仙台のノードＷＮ１、ＷＮ２も同様であり、仙台のカーフェリー発着埠頭の近傍の道路、すなわち、道路ネットワークのノードＮ１００と結ばれる道路リンクＬ１００、Ｌ１０１に接続されるデータ構成を持つ。このようなノードとしてカーフェリーの発着場所を表現すると、出発地側のカーフェリーの港湾ノードに探索が到達すると、瞬時に到着側のカーフェリーの港湾ノードに拡散が及ぶようにできる。
【００８３】
ここで、仙台のノードをＷＮ１、ＷＮ２に分けた理由であるが、フェリーターミナルをすべて同じノードにしてしまうと、このノードにダイクストラ法を用いた経路探索の拡散が到着した瞬間に、すべての同じノードに拡散が飛び火したように探索されることになる。しかし、そのような探索の広がりは現実的でないので、別ノードとしたものである。ただし、この例の「苫小牧−仙台−名古屋」のカーフェリーは直行便であり、苫小牧（ＷＮ1）−仙台（ＷＮ1，ＷＮ２）−名古屋（ＷＮ２）と探索が拡散するのは差し支えない。従ってこの仙台のようにノードが分けられた場合は、フェリーターミナルの道路ノードＮ１００（リンクＬ１００、Ｌ１０１）に両方のワープノードＷＮ１、ＷＮ２が接続するデータ構造になっている。
【００８４】
図５は、仙台の近傍の出発地Ｓからある目的地への経路探索の概念を説明するための模式図であり、経路探索の進行（拡散）の過程で、探索が図４に示すカーフェリーの仙台のノードに到達する前後の様子を説明する図である。探索が仙台のカーフェリー発着ノード、であるノードＷＮ１、ＷＮ２に接続する道路リンクＬ１００、Ｌ１０１（図４参照）に到達すると、これらのノードＷＮ１、ＷＮ２は、苫小牧側、名古屋側のノードと同一であるから、当該ノードＷＮ１、ＷＮ２から拡散するリンクは、苫小牧側のノードＷＮ１と道路ネットワークのノードＮ２００とを接続するリンクＬ２００（図４参照）になる。また、名古屋側のノードＷＮ２と道路ネットワークのノードＮ３００とを接続するリンクＬ３００（図４参照）になり、瞬時にカーフェリーの到着地側である苫小牧側と名古屋側に探索が及ぶ。なお、仙台のワープノードＷＮ１、ＷＮ２が接続される道路リンクは上記の例ではリンクＬ１００とＬ１０１の別のリンクとしたが、同一の道路リンクであっても差し支えない。
【００８５】
すなわち、出発地Ｓからの拡散が、仙台のノードＷＮ１、ＷＮ２に達した時に（破線円のイメージ）、拡散は苫小牧のノードＷＮ１、名古屋のノードＷＮ２に達したのと等価である。さらに拡散が進むと、出発地Ｓからの拡散が実線円に達すると共に、苫小牧のノードＷＮ１、名古屋のノードＷＮ２からも拡散が成長する。これが本発明におけるノードを用いた探索の作用である。このまま目的地に到達すれば、カーフェリー航路を除く部分の経路がわかったことになる。このようなノードＷＮ１、ＷＮ２の性格から、通常の道路ネットワークのデータや交通ネットワークのデータにおけるノードと区別するため、本発明においては、ノードＷＮ１、ＷＮ２を「ワープノード」と称している。
【００８６】
次いで、到着地側のワープノードから拡散を拡大する際に、カーフェリーの航路（経路区間）のコストを調整、加味する。これにより、カーフェリーのリンクコストが反映され、経路探索が進むことになる。具体的には、ワープノードＷＮ１、ＷＮ２が接続される到着地側の道路リンクＬ２００、Ｌ３００）は道路リンクのコスト（例えば、コストＸ）を有しているが、探索ワープノードＷＮ１、ＷＮ２に到達し、拡散する際のリンクＬ２００、Ｌ３００のコストは道路リンクとしてのコストＸに、仙台・苫小牧間のカーフェリーの利用コスト（例えば、コストＹ）、仙台・名古屋間のカーフェリーの利用コスト（例えば、コストＺ）を加算する。
【００８７】
図６は、１つのワープノードに着目した図であり、図５において、仙台から苫小牧に向かうカーフェリーの経路区間が探索対象となる場合を示す図である。仙台のカーフェリーの端点（港湾または埠頭）に設定されたワープノードＷＮ１は、道路リンクＬ１００により近傍の道路ネットワークのノードＮ１００に接続されている。また、このワープノードＷＮ１は、道路リンクＬ２００により苫小牧のカーフェリーの端点（港湾または埠頭）近傍の道路ネットワークのノードＮ２００に接続されている。
【００８８】
出発地Ｓが仙台近傍である場合（図５参照）、探索が道路ネットワークのノードＮ１００に到達するとノードＮ１００から発芽するリンクＬ１００に拡散し、ワープノードＷＮ１に至る。リンクＬ１００はワープノードＷＮ１の入りリンクである。探索の拡散がワープノードＷＮ１に至ると、ワープノードＷＮ１から発芽するリンクは、出リンクであるリンクＬ２００になる。リンクＬ２００は苫小牧のカーフェリーの端点（港湾または埠頭）に接続される道路リンクであるから、探索がワープノードＷＮ１に到達した時点で瞬時に出発地側の仙台の港湾の近傍から目的地側の苫小牧の港湾の近傍に拡散する。
【００８９】
苫小牧側のリンクＬ２００は、道路リンクとしてのリンクコストＸを有しており、通常のコスト算出ではリンクコストＸが用いられる。しかしながらリンクＬ２００はワープノードＷＮ１から発芽するリンクであるので、仙台と苫小牧間のカーフェリーの経路区間の利用コストＹを加算する。このことにより、苫小牧側のノードＮ２００のポテンシャルは、道路リンクＬ２００のリンクコストＸだけでなく、仙台−苫小牧間のカーフェリーの経路区間の利用コストＹが加味された値になる。
【００９０】
このことは、カーフェリーの経路区間の端点に、近傍の道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したワープノードを設定することによって、例えば、図６で説明したように、仙台−苫小牧間のカーフェリーの経路区間を道路に擬似した場合のリンク用いて探索するのと同等の結果が、瞬時に得られるということを示している。すなわち、本発明によれば、カーフェリー経路のリンクを探索する無駄がない。また、探索がワープノードに達したことで、カーフェリーの時刻表を用いてコスト算出する手順に切り替える判定が出来て、実際の運行時刻表に基づいた探索が可能になる。
【００９１】
ここで、カーフェリーの利用コストとは、該当するカーフェリーの運行時刻表を参照して算出される所要時間であり、また、カーフェリーが運行時刻表を有さず随時運行される場合には、該カーフェリーを用いる経路区間の平均所要時間である。更に正確には、利用コストには、ワープノードに到着してから、カーフェリーが出発するまでの待ち時間を含むようにする。このようにすれば、道路を用いて移動する通常の経路の探索とともに、カーフェリーの利用区間を含む経路探索を無駄な処理なく実行できるようになる。
【００９２】
該当するカーフェリーの運行時刻表を参照して算出される所要時間を利用コストとすれば、車両が他の交通手段に積載されて移動する経路についても、一般的な電車、バスなどの公共交通機関を用いた経路区間の経路と同様の探索ができ、また、探索条件に時刻条件が設定されている場合にも対応できるようになる。運行時刻が定まっておらず随時運行される交通手段の場合もその平均所要時間を利用コストとすれば、カーフェリーを用いる経路区間の利用コストを算出することができる。
【００９３】
図７は、以上説明した経路探索処理を行う、本発明の実施例にかかる図１のナビゲーションシステムの詳細な構成を示すブロック図である。
【００９４】
端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、経路再探索要求手段２３、条件設定手段２４、案内経路データ記憶手段２５、表示手段２６、操作入力手段２７を備えて構成される。
【００９５】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００９６】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの入力機能としても用いられる。表示手段２６は液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２６はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。また、表示手段２６にはタッチパネル機能を設け、表示された画像上の所望の部分をタッチして入力する入力手段として機能させてもよい。
【００９７】
経路探索サーバ３０から端末装置２０に送信される案内経路、推奨経路などの案内データは地図データとともに案内経路データ記憶手段２５に記憶され、案内経路データ記憶手段２５に記憶された案内経路などの案内データや地図データは、必要に応じて読み出され、表示手段２６に表示される。
【００９８】
端末装置２０は、条件設定手段２４により経路探索の条件として、出発地、目的地、出発時刻あるいは到着希望時刻などを設定する。本発明においては、更に、カーフェリーなど、車両を積載して運行する公共交通機関を用いた経路を経路探索の対象とするか否かを設定する構成を採る。このようにすれば、ユーザにおいてカーフェリーを利用する頻度が高くないと予想されるので、通常の経路探索の妨げとなることがない。勿論、全ての経路探索において自動的にこのような経路を経路探索対象とすることもできる。
【００９９】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、案内経路データ編集手段３２、コスト算出手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、ワープノード設定手段３６、時刻表データベース３７などを備えて構成される。経路探索用ネットワークデータ３５には、先に説明したように道路ネットワークデータ、交通ネットワークデータ、ワープ設定手段３６が設定したワープノードデータが蓄積され、これらのネットワークデータは経路探索の条件によって適宜結合され、経路探索が行われる。
【０１００】
経路探索サーバ３０は、端末装置２０から経路探索要求があると、これを探索要求記憶手段３８に一時記憶する。そして経路探索手段３９は、探索要求記憶手段３８に記憶した経路探索要求に従って経路探索用ネットワークデータベース３５を参照して出発地から目的地までの複数の候補経路を探索する。経路探索要求が通常の経路探索の要求である場合、経路探索の結果得られた案内経路のデータを地図データベース３４から読み出した地図データとともに端末装置２０に送信する。この経路探索の方法は通常のナビゲーションシステムにおける経路探索サーバと同様、ダイクストラ法に代表されるラベル確定法を用いるものである。
【０１０１】
経路探索の結果得られた案内経路のデータは、地図データとともに端末装置２０に送信される。地図データは端末装置２０の現在位置を含む所定範囲の単位地図データ（緯度・経度で所定の大きさのエリアに区分された地図データ）が地図データベース３４から読み出される。案内経路データ編集手段３２は、地図データや案内経路のデータを端末装置２０に送信するための案内情報（データ）に編集する。
【０１０２】
時刻表データベース３７には、電車、バス、航空機、船舶などの公共交通機関の路線データ、時刻表データが蓄積される。また、人が乗車する公共交通機関の他、カーフェリーやカートレインのような車両を積載して移動する経路の路線（航路）および時刻表データも蓄積されている。
【０１０３】
ワープノード設定手段３６は、カーフェリーやカートレインのような車両を積載して移動する経路の路線（航路）のデータに基づいて、その経路区間の両端点、例えば、出発地と経由地、経由地と経由地、経由地と到着地にワープノードを設定する。このワープノードは、端点のそれぞれの近傍の道路リンクに接続されるが、絶対位置情報（緯度・経度）を有しない同一ノードで表現したものである。ワープノードの具体例は、既に図４〜図６を参照して説明したとおりである。設定されたワープノードのネットワークデータは経路探索用ネットワークデータベース３５に蓄積される。
【０１０４】
端末装置２０からの経路探索要求に設定された経路探索条件が、カーフェリーなど、車両を積載して移動する経路区間を探索の対象に含む場合、経路探索手段３９が出発地から目的地までの経路を探索するにあたって、経路探索用ネットワークデータベース３５に蓄積された道路ネットワークデータに、ワープノードのデータを結合して経路探索をたん行う。ワープノードは、カーフェリーの経路区間の両端点に同一ノードとして設定され、端点のそれぞれの近傍の道路リンクに接続されるものであるから、道路ネットワークデータに容易に結合することができる（例えば、図４参照）。
【０１０５】
経路探索手段３９が経路探索を行う過程で、探索がワープノード、例えば、図６のリンクＬ１００（仙台側）からＷＮ１に到達すると、リンクコスト算出手段３３は、ワープノードから拡散するリンク（発芽するリンク、例えば、図６のリンクＬ２００（苫小牧側）のリンクコストを算出する。ここで算出するリンクコストは、リンクＬ２００のリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加えたものである。経路探索手段３９はワープノードＷＮ１から先に経路探索を進める際には、リンクＬ２００のリンクコストをリンクコスト算出手段３３が算出した前述の値（リンクＬ２００のリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加えたもの）を使用して到達ノード（例えば、図６のＮ２００）のポテンシャルを算出する。
【０１０６】
ここで、カーフェリーの利用コストとは、先に説明したように、該当するカーフェリーの運行時刻表を参照して算出される所要時間、または、該カーフェリーを用いる経路区間の平均所要時間であり、この利用コストには、ワープノードに到着してから、カーフェリーが出発するまでの待ち時間を含むようにしてもよい。従って、道路を用いて移動する通常の経路の探索とともに、カーフェリーの利用区間を含む経路探索を無駄な処理なく実行できるようになる。
【０１０７】
図８は、ワープノードから発芽するリンクのリンクコスト算出の手順を示すフローチャートである。経路探索手段３９が、探索が及んだリンクをダイクストラ法に従いメモリ（ヒープ：図１１参照）に記憶する際の処理を示している。経路探索手段３９は、経路探索の到達ノードがワープノード、例えば、ワープノードＷＮ１、ＷＮ２（図５参照）であるか否かをチッェクする。ワープノードであれば、探索がそのワープノードから拡散するか否かを判定する（ステップＤ１０１）。通常このステップではワープノードから拡散する判定が得られるが、そうでない場合（ステップＳ１０１のＮＯ）は何もせずにリターンする。ワープノードである場合（ステップＳ１０１のＹＥＳ）、ステップＳ１０２に進み、リンクコスト算出手段３３によりワープノードの出リンク（発芽するリンク）のリンクコストを算出させ、その値を出リンクのリンクコストとしてリターンする。
【０１０８】
ここで算出するリンクコストは、先に説明したように、例えば、図６に示すワープノードＷＮ１の場合、リンクＬ２００の道路リンクとしてのリンクコストＸに、仙台−苫小牧間のカーフェリーの利用コストＹを加算したものである。経路探索手段３９はこのようにして算出されたリンクコストを用いて到着側のワープノードから先の探索を継続する。
【０１０９】
例えば、カーフェリー航路の所要時間をコストに代入してもよいし、さらに正確には
そのワープノードへの到達時刻から、フェリーに乗船してワープノードの出リンクに至るまでの時間を、カーフェリー時刻表を参照して求める。具体的には、仙台のワープノードＷＮ１の到達時刻が１６：００。次に乗船できるカーフェリーの出港が１９：４０。苫小牧への到着が翌日の１１：００。もともとの、出リンクＬ２００コストが1分である場合は、出リンクＬ２００のコストを「１９時間1分」に変更してリターンする。なお、ワープノードからの出リンクが複数ある場合は、それぞれにリンクコストの算出（ステップＳ１０２）を実行する。また、時刻表がなく渡し船のように随時運行されるものについては、平均所要時間をコストに採用する。
【０１１０】
なお、上記実施例の説明において、ワープノード設定手段３６が予めカーフェリーなどの経路区間の端点にワープノードを設定し、経路探索用ネットワークデータベース３５に蓄積しておく例を説明したが、本発明はこれに限られるものではなく、経路探索条件としてカーフェリーなどの経路区間を経路探索の対象とする設定を含む経路探索要求があった場合に、ワープノード設定手段３６が時刻表データベースに蓄積されたデータに基づいてワープノードを設定し、経路探索用ネットワークデータベース３５の道路ネットワークデータに結合するようにしてもよい。
【０１１１】
また、実施例においては、ワープノードから発芽するリンクのリンクコスト算出をリンクコスト算出手段３３が行う例を示したが、これに限られるものではなく、経路探索手段３９が経路探索する過程で、このリンクコストの算出を行った上で該リンクによって到達するノードのポテンシャルを算出するようにしてもよい。また、装置の分散・統合の具体的形態は上記説明した実施形態のものに限られず、その全部または一部を、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１１２】
以上、詳細に説明したように、本発明によるナビゲーションシステムによれば、車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードであって、絶対位置情報は持たず、該経路区間の両端の近傍の道路リンクに接続されるワープノードを設定することによって、通常の道路を移動する経路野探索とともに、車両が他の交通手段に積載されて移動する経路も、効率よく探索することができるようになる。すなわち、カーフェリーを使う場合も、陸路だけで行く場合も同じ探索で探索が進むため、最適経路が求められる。出リンクのコストは大きくなるので、しばらくはメモリ（ヒープ）に留まるが、離島などを探索した場合は陸路では到達できないため、いずれヒープから取り出され、探索経路となる。
【産業上の利用可能性】
【０１１３】
本発明は、車載用のナビゲーションシステムに限らず、通信型の携帯ナビゲーションシステム、車載、携帯兼用のナビゲーションシステムにも適用することができる。また、本発明の経路探索は、実際に車両を積載せずに、ユーザのみがカーフェリーなどの交通手段を用いて移動する場合にも適用することができる。
【符号の説明】
【０１１４】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・経路再探索要求手段
２４・・・・条件設定手段
２５・・・・案内経路データ記憶手段
２６・・・・表示手段
２７・・・・操作入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・案内データ編集手段
３３・・・・リンクコスト算出手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・ワープノード設定手段
３７・・・・時刻表データベース
３８・・・・探索要求記憶手段
３９・・・・経路探索手段
【特許請求の範囲】
【請求項１】
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーションシステムにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項２に記載のナビゲーションシステム。
【請求項４】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項２に記載のナビゲーションシステム。
【請求項５】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項２ないし請求項４の何れか１項に記載のナビゲーションシステム。
【請求項６】
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする経路探索サーバ。
【請求項７】
前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項７に記載の経路探索サーバ。
【請求項１０】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項７ないし請求項９の何れか１項に記載の経路探索サーバ。
【請求項１１】
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする経路探索方法。
【請求項１２】
前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項１２に記載の経路探索方法。
【請求項１４】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項１２に記載の経路探索方法。
【請求項１５】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項１２ないし請求項１４の何れか１項に記載の経路探索方法。
【請求項１６】
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーション装置において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とするナビゲーション装置。
【請求項１７】
前記ナビゲーション装置は、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１６に記載のナビゲーション装置。
【請求項１８】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項１７に記載のナビゲーション装置。
【請求項１９】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項１７に記載のナビゲーション装置。
【請求項２０】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項１７ないし請求項１９の何れか１項に記載のナビゲーション装置。
【請求項１】
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーションシステムにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーションシステムは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項２に記載のナビゲーションシステム。
【請求項４】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項２に記載のナビゲーションシステム。
【請求項５】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項２ないし請求項４の何れか１項に記載のナビゲーションシステム。
【請求項６】
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおいて、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする経路探索サーバ。
【請求項７】
前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項６に記載の経路探索サーバ。
【請求項８】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項７に記載の経路探索サーバ。
【請求項９】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項７に記載の経路探索サーバ。
【請求項１０】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項７ないし請求項９の何れか１項に記載の経路探索サーバ。
【請求項１１】
出発地と目的地を含む経路探索条件を設定して経路探索要求を行う端末装置にネットワークを介して接続され、少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、前記設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えた経路探索サーバにおける経路探索方法において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とする経路探索方法。
【請求項１２】
前記経路探索サーバは、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１１に記載の経路探索方法。
【請求項１３】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項１２に記載の経路探索方法。
【請求項１４】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項１２に記載の経路探索方法。
【請求項１５】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項１２ないし請求項１４の何れか１項に記載の経路探索方法。
【請求項１６】
少なくとも道路をノードとリンクで表現した経路探索用ネットワークデータと、設定された出発地から目的地までの最適経路を、ラベル確定法を用いて探索する経路探索手段と、を備えたナビゲーション装置において、
車両が他の交通手段に積載されて移動する経路について、該経路の１つの経路区間の両端に同一ノードで表現されるワープノードを設定し、該ワープノードは絶対位置情報は持たず、前記経路探索用ネットワークデータの道路ネットワークにおける前記１つの経路区間の両端の近傍の道路にリンクで接続され、
前記経路探索手段は、ラベル確定法による探索が前記ワープノードに到達した際に、該ワープノードからの出リンクを用いて探索を継続することを特徴とするナビゲーション装置。
【請求項１７】
前記ナビゲーション装置は、リンクコスト算出手段を備え、前記リンクコスト算出手段は、ラベル確定法による探索が前記ワープノードに到達した際に、前記ワープノードからの出リンクのコスト算出にあたって、当該出リンクのリンクコストに、前記交通手段の利用コストを加算した値をリンクコストとすることを特徴とする請求項１６に記載のナビゲーション装置。
【請求項１８】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段の運行時刻表を参照して、該交通手段の利用コストを算出することを特徴とする請求項１７に記載のナビゲーション装置。
【請求項１９】
前記リンクコスト算出手段は、前記ワープノードからの出リンクの利用コスト算出にあたって、前記交通手段が運行時刻表を有さず随時運行される場合には、該交通手段を用いる経路の平均所要時間を利用コストとすることを特徴とする請求項１７に記載のナビゲーション装置。
【請求項２０】
前記利用コストには、前記ワープノードに到着してから、前記交通手段が出発するまでの待ち時間を含むことを特徴とする請求項１７ないし請求項１９の何れか１項に記載のナビゲーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−２７５２４（Ｐ２０１１−２７５２４Ａ）
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願番号】特願２００９−１７３００９（Ｐ２００９−１７３００９）
【出願日】平成２１年７月２４日（２００９．７．２４）
【特許番号】特許第４４１８８４９号（Ｐ４４１８８４９）
【特許公報発行日】平成２２年２月２４日（２０１０．２．２４）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願日】平成２１年７月２４日（２００９．７．２４）
【特許番号】特許第４４１８８４９号（Ｐ４４１８８４９）
【特許公報発行日】平成２２年２月２４日（２０１０．２．２４）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]