リンク選択プログラム、リンク選択方法、リンク選択装置、経路探索プログラム、経路探索方法、及び、経路探索装置
【課題】経路探索の信頼性を高めて適切な推奨経路を得る。
【解決手段】地点に対するリンクを選択するに当たって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する（１６Ａ）他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し（１６Ｂ）、当該全体領域内から任意の地点（例えば出発地点や目的地点）を取得する（１１Ａ）。そして、障害領域と交差せずに当該地点からアクセスするのに適したリンクを選択する（１１Ｂ）。
【解決手段】地点に対するリンクを選択するに当たって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する（１６Ａ）他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し（１６Ｂ）、当該全体領域内から任意の地点（例えば出発地点や目的地点）を取得する（１１Ａ）。そして、障害領域と交差せずに当該地点からアクセスするのに適したリンクを選択する（１１Ｂ）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、典型的には、車両の出発地点から目的地点までの推奨経路を探索するためのプログラム／方法／装置、及び、それらの一部を成すリンク選択のプログラム／方法／装置に関する。
【背景技術】
【０００２】
自車両を出発地点から目的地点まで誘導する経路探索装置（例えば、車載ナビゲーション装置）は既に周知である。この経路探索装置は、出発地点から目的地点までの最適経路を所定の経路探索ロジックを用いて演算し、この演算結果である最適経路を、ディスプレイやスピーカ等の出力装置を介して画像や音声で搭乗者に案内するものである。
【０００３】
かかる最適経路の探索のために、経路探索装置は、道路を、その最小単位のリンクに分解して記憶するとともに、リンク同士の接続点はノードとして記憶している（例えば、特許文献１参照）。また、経路探索装置は、リンクに関するその他種々の情報を記憶している。このような情報に基づいて、例えば、距離や道路種別等を考慮したリンクコストが最小となる最適経路を特定の経路探索ロジックによって算出するのが一般的であり、この経路探索ロジックとしては、例えばダイクストラ法やポテンシャル法が利用される（特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３８６９０５５号
【特許文献２】特開平７−１０３７７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のような従来の経路探索装置では、例えば、車両の出発地点（現在位置又は、出発地点として指定した地点）が広大な敷地内にあって、その周辺に複数の公道や河川があるとき、目的地への経路探索を実行すると、河川と交差して最寄りの道路へアクセスするような推奨経路が得られる場合がある。
【０００６】
図８は、このような一例を地図上に示す図である。図において、出発地点Ｐから最寄りの道路リンクＡにアクセスする経路が推奨されても、川を横切る形となり、実際には行けない。また、目的地として装置に設定した場所へ、同様の理由によって、道路から進入できない推奨経路が得られる場合もある。
これらの場合には、推奨経路の通りに走行することができず、経路探索の信頼性が乏しい。
【０００７】
かかる従来の問題点に鑑み、本発明は、経路探索の信頼性を高めて適切な推奨経路を得ることを目的とする。
【課題を解決するための手段】
【０００８】
（１）本発明のリンク選択プログラムは、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、前記全体領域内から任意の地点を取得する機能と、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する機能とをコンピュータに実現させるものである。
【０００９】
上記のようなリンク選択プログラムによって各機能を実現するコンピュータは、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１０】
（２）また、上記リンク選択プログラムにおいて、障害データには、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、全体領域内に設定された位置及び形状データが含まれるものであってもよい。
この場合、実際には横切って通過できないこれらの障害を通過するかのような誤ったリンク選択を防止することができる。
【００１１】
（３）また、上記（１）又は（２）のリンク選択プログラムにおいて、障害データは、ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっていることが好ましい（Ｎは２以上の整数）。
この場合、ネットワークデータに対して、障害データは少なくとも１次元低いので、比較的コンパクトなデータサイズとすることができる。
なお、点や線で表される情報は１次元、平面的な広がりを持つ情報は２次元、そして、平面的な広がりに加えて高さの情報を持つものは３次元である。従って、道路の単なる１本のリンクデータは１次元、複数のリンクデータを網状に繋ぎ合わせた道路のネットワークデータや、平面情報のみのデジタル地図などの情報は２次元、そして、平面情報に加えて高低の情報が加えられているデジタル地図などの情報は３次元である。
【００１２】
（４）一方、本発明のリンク選択方法は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、前記全体領域内から任意の地点を取得し、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するものである。
【００１３】
上記のようなリンク選択方法においては、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１４】
（５）また、本発明のリンク選択装置は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、前記全体領域内から任意の地点を取得する地点取得部と、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するリンク選択部とを備えたものである。
【００１５】
上記のようなリンク選択装置は、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１６】
（６）また、他の観点から見た本発明は、始点から終点までの経路を探索する機能をコンピュータに実現させるための経路探索プログラムであって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、前記全体領域内から前記始点及び終点を取得する機能と、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する機能と、前記開始リンクから前記終了リンクまでの推奨経路を探索する機能とを、コンピュータに実現させるための経路探索プログラムである。
【００１７】
上記のような経路探索プログラムによって各機能を実現するコンピュータは、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００１８】
（７）また、上記（６）の経路探索プログラムにおいて、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、全体領域内に設定された位置及び形状データが含まれるものであってもよい。
この場合、実際には横切って通過できないこれらの障害を通過するかのような誤ったリンク選択を防止することができる。
【００１９】
（８）また、上記（６）又は（７）の経路探索プログラムにおいて、障害データは、ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっていることが好ましい。
この場合、ネットワークデータに対して、障害データは少なくとも１次元低いので、比較的コンパクトなデータサイズとすることができる。
【００２０】
（９）また、本発明は、始点から終点までの経路を探索する経路探索方法であって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、前記全体領域内から前記始点及び終点を取得し、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択し、前記開始リンクから前記終了リンクまでの推奨経路を探索するものである。
【００２１】
上記のような経路探索方法においては、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００２２】
（１０）また、本発明は、始点から終点までの経路を探索する経路探索装置であって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、前記全体領域内から前記始点及び終点を取得する地点取得部と、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択するリンク選択部と、前記開始リンクから前記終了リンクまでの推奨経路を探索する経路探索部とを備えたものである。
【００２３】
上記のような経路探索装置は、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００２４】
（１１）また、さらに他の観点から見た本発明は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスをしにくくするための領域であるアクセス制限領域を成す制限データを取得する機能と、前記全体領域内から任意の地点を取得する機能と、前記地点と、その近傍に存在する複数のリンクそれぞれとの近接度を、前記地点から前記複数の各リンクまでの直線の距離に基づいて算出する機能と、算出される前記近接度に基づいて、前記複数のリンクから一のリンクを選択する機能と、をコンピュータに実現させるためのリンク選択プログラムであって、前記直線が前記アクセス制限領域と交差する場合に算出される近接度が、当該リンクが選択されにくいような値となること、を特徴とするものである。
【００２５】
上記のようなリンク選択プログラムによって各機能を実現するコンピュータは、アクセス制限領域と交差するリンクの近接度を、選択されにくい値にするので、結果的に、このようなリンクをなるべく避けつつ、地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である制限データも考慮して、アクセスすべきリンクを選択し、しかも、いわば、恣意的に最適な（若しくは賢明な）リンクを選択することができる。
なお、前記近接度とは、前記任意の地点から各リンクまでの直線距離の長さに基づいて算出される指標であり、一般的には、当該距離の長さが短いほど近接度が大きいものとして算出される。本発明では、アクセス制限領域と交差する直線の場合には、例えば、実際の直線距離の長さに対して、所定の定数を加算したり、直線距離を２倍にする処理をしたりすることで、近接度を小さくすることができる。
【発明の効果】
【００２６】
本発明のリンク選択プログラム／方法／装置、及び、経路探索プログラム／方法／装置によれば、経路探索の信頼性（物理的な面でのリンク選択の信頼性の他、恣意的なリンク選択の信頼性も含む。）を高めて適切な推奨経路を得ることができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施形態に係る経路検索装置を有するナビゲーションシステムの全体構成を示す概略構成図である。
【図２】図１のシステムの機能ブロック図である。
【図３】図１のシステムを利用した経路探索処理のフローチャートである。
【図４】図３のステップＳ１におけるリンク選択の内容を示すフローチャートである。
【図５】図４のステップＳ１−１，Ｓ１−２に共通の、リンク選択処理の内容を示すフローチャートである。
【図６】図５のフローチャートによる処理の概念を地図上で表現した具体例である。
【図７】経路探索の処理、特に、リンク選択の処理の主体を装置として機能的に見たときのブロック図である。
【図８】最寄りのリンクを探す状態の一例（従来例）である。
【発明を実施するための形態】
【００２８】
《システムの全体構成》
図１は、本発明の一実施形態に係る経路検索装置（経路探索プログラムや、リンク選択プログラム／装置も含む。）を有するナビゲーションシステムの全体構成を示す概略構成図であり、図２は、同システムの機能ブロック図である。
図１及び図２に示すように、本実施形態のナビゲーションシステム１は、サーバ装置２と、複数の車両３にそれぞれ搭載された車載装置４とによって構成されている。
なお、本明細書において、「車両」とは、自動車、原動機付き自転車、軽車両及びトロリーバス等のことをいう。また、「車載装置」とは、車両に搭載されており、その搭乗者に対して目的地までの経路を案内するいわゆるナビゲーション装置のことをいう。
【００２９】
このナビゲーションシステム１は、予め入会登録された会員（ユーザ）の車両３自体をセンサとして、各車両３からサーバ装置２が情報収集し、メンバー間で相互に情報提供し合って運用することにより、サーバ装置２が各会員に対して有用な交通情報を提供するようにしたものである。
従って、本システム１によれば、通常のＶＩＣＳ（登録商標：Vehicle Information and Communication System）情報とともに、このＶＩＣＳ情報に含まれていないより詳細かつ動的な交通情報を、各会員の車両３に提供することができる。
【００３０】
本システム１のサーバ装置２は、専用の通信回線を介して交通情報センタ５に接続されており、必要に応じてＶＩＣＳ情報を交通情報センタ５から入手している。また、サーバ装置２は、インターネット網６を通じて携帯電話機８の無線基地局７と双方向で通信可能である。
各車両３の車載装置４は、搭乗者の携帯端末である携帯電話機８を介して、無線基地局７と双方向で通信可能であり、無線基地局７は上記インターネット網８に接続されている。このため、各車両３の車載装置４は、ほぼリアルタイムでサーバ装置２に対して情報を送受信可能となっている。
【００３１】
各車両３の車載装置４は、ＧＰＳ（Global Positioning System）アンテナと、ＧＰＳ受信機と、道路地図データベースと、入力デバイスと、ディスプレイ及びスピーカ等よりなる出力装置とを備えており、ＧＰＳ受信機で検出した現在位置をディスプレイの画面上に表示できるようになっている。
また、車載装置４は、入力デバイスで入力された所定の旅行条件に基づいて、旅行ルートを演算可能なルート演算装置（図示せず）を備えている。
【００３２】
車載装置４に入力可能な旅行条件としては、出発地点（現在位置又は指定した地点）や目的地点のほか、経由地や優先経路（一般道路優先又は有料道路優先や、距離優先又は道幅優先）等がある。ルート演算装置のメモリには、入力される情報や自身で演算した旅行ルートに加えて、サーバ装置２から提供されたルート探索情報を保存することもできる。
なお、本実施形態の車載装置４は、ＥＴＣ対応であり、有料道路の料金所等に設置されたＥＴＣ路側処理装置と無線による路車間通信を行うことができる。
【００３３】
《サーバ装置の内部構成》
図２に示すように、サーバ装置２は、ワークステーション等よりなるコンピュータ１１と、このコンピュータ１１に接続された通信インターフェースよりなる第１及び第２通信部１２，１３と、各種データベース１４〜１６とから構成されている。
第１通信部１２は、専用回線で交通情報センタ５に接続されている。また、第２通信部１３は、インターネット網６を介して前記無線基地局７に接続され、この無線基地局７と車両３の搭乗者の携帯電話機８との間の無線通信を通じて、車載装置４との間で情報の送受信を行う。
【００３４】
《会員データベース》
各データベース１４〜１６のうち、会員データベース１４には、当該システム１に参加する登録会員の識別情報が保存されている。
コンピュータ１１は、会員データベース１４に記録されている特定の登録会員から受信した入力情報（出発地点及び目的地点等）に基づいて、後述する経路探索処理を実行する。
【００３５】
《交通情報データベース》
交通情報データベース１５には、第１通信部１２が受信した交通情報センタ５からのＶＩＣＳ情報が保存される。このＶＩＣＳ情報は、コンピュータ１１が交通情報センタ５からのＶＩＣＳ情報を抽出するごとに更新され、ほぼ最新の情報が保持される。
また、交通情報データベース１５には、特定の登録会員から受信したリンク番号、リンク進入時刻、リンク退出時刻、リンク旅行時間等よりなる交通情報（プローブ情報）も保存される。
【００３６】
この場合、車載装置４は、所定時間毎（例えば、０．１秒毎）又は所定距離毎（例えば、５ｍ毎）に位置を検出しており、各リンクについて、検出位置がリンクの始端の位置を通過（一致）した時刻をリンク進入時刻とし、検出位置がリンクの終端の位置を通過（一致）した時刻をリンク退出時刻とし、リンク退出時刻とリンク進入時刻との差をリンク旅行時間として算出する。
【００３７】
更に、交通情報データベース１５には、高速道路等の有料道路の料金情報１７が含まれている。
この料金情報１７は、例えばＮＥＸＣＯが公表している各ＩＣ間の通行料金テーブルよりなり、この通行料金テーブルは、深夜割引、通勤割引及び早朝夜間割等の割引制度ごとに定められた複数のテーブルよりなる。
【００３８】
《地図データベース》
地図データベース１６には道路地図データが記録されている。この道路地図データには、道路網を構成する単位をリンクとして、各リンクに関する種々の情報が含まれている。例えば、当該情報には、ネットワークデータとしての「交差点データ」と「リンクデータ」とが含まれている。
このうち、「交差点データ」は、交差点ＩＤと交差点位置とを対応付けたデータである。また、「リンクデータ」は、特定リンクのリンクＩＤに対して、特定リンクの始点・終点（ノード）・補間点の位置、特定リンクの始点に接続するリンクＩＤ、特定リンクの終点に接続するリンクＩＤ、特定リンクのリンクコスト等、を対応付けたデータよりなる。
【００３９】
また、平均速度や渋滞状況については、交通情報データベース１５のＶＩＣＳ情報やプローブ情報に基づいて設定される。従って、これらの各情報が更新される度に、リンクデータに含まれる各リンクの平均速度及び渋滞状況も更新される。
また、地図データベース１６には、地図上の各道路に対応するリンクが一般道路か有料道路かの道路種別も含まれている。
【００４０】
一方、リンクコストは、例えば、特定リンクとその終点に接続するリンクの組み合わせの数だけ用意されており、特定リンクの始点に進入してから当該特定リンクの終点を退出し、次に接続するリンクの始点に進入するまでに要するコスト（時間）を含んでいる。
すなわち、リンクコストには、特定リンクの始点から終点までを走行するのに要する時間コストと、その特定リンクの終点から次のリンクの始点までを走行するのに要する時間コスト、つまり、交差点通過に要する時間コストとが含まれる。
【００４１】
上記時間コストは、平日、土曜、日曜及び祝日といった日種別ごとに、現時点から１日先までの５分毎のデータが用意されており、この５分毎のデータは、交通情報データベース１５のＶＩＣＳ情報や、特定会員から受信したプローブ情報に基づいて作成される。
【００４２】
一方、地図データベース１６には、上記のようなネットワークデータの他に、車両通行の障害となる領域（障害領域）を示す障害データとして、当該領域の位置や形状データが格納されている。障害データとは例えば、河川等の水領域（海岸線も含む。）、崖、及び、フェンス、柵、塀その他のフェンス状建造物であり、車両は、これらと交差する経路で通行する（すなわち横切る）ことはできない。
【００４３】
また、障害データは、リンクと同様に、特定の障害データ単位ＩＤに対して、始点・終点（ノード）・補間点の位置、始点に接続する他の障害データ単位ＩＤ、終点に接続する他の障害データ単位ＩＤ等、を対応付けたデータより構成することができる。
【００４４】
これらの障害データは、ネットワークデータにより表される道路網が２次元（平面）であれば、１次元の障害線（ポリライン）により表現することができる。また、道路網が３次元であれば、２次元の閉じた面（ポリゴン）からなる障害面として表現することができる。すなわち、Ｎ次元（Ｎは２以上の整数）の道路網に対しては（Ｎ−１）次元の障害データとすればよい。この場合、ネットワークデータに対して、障害データは１次元低いので、比較的コンパクトなデータサイズとすることができる。なお、ネットワークデータがリンクアクセス（リンクへのアクセス）や経路探索のための肯定的な情報であるとすれば、障害データは、否定的な情報となるものであり、単なる地図上のグラフィックデータではない。
【００４５】
なお、データの次元は、上記の関係に限定される訳ではなく、障害データの次元が、ネットワークデータの次元と同じであってもよいし、ネットワークデータが３次元で障害データが１次元というような、２次元差があっても構わない。すなわち、ネットワークデータがＮ次元であれば、障害データはＮ次元以下とすることができる。但し、上記のように、障害データのデータサイズを比較的コンパクトにするためには、ネットワークデータがＮ次元であれば、障害データは（Ｎ−１）次元以下とすることが好ましい。
【００４６】
《コンピュータの構成及び機能》
一方、コンピュータ１１は、ＨＤＤやメモリ等よりなる記憶装置１８と、この記憶装置１８から各種のコンピュータプログラムを読み出して実行する演算装置１９とを含んでいる。
【００４７】
このコンピュータプログラムのうちの１つは、車両３が出発地点から目的地点まで走行する場合の推奨経路の探索が可能なプログラムであり、このプログラムには、具体的にはダイクストラ法やポテンシャル法による経路探索ロジックが含まれている。
すなわち、演算装置１９は、上記経路探索ロジックを含むプログラムを実行することにより、出発地点から目的地点までの最小のリンクコストとなる経路（推奨経路）を探索する。
【００４８】
ここで、ダイクストラ法では、開始リンクから始まるリンクのツリーを構成していくに当たって、あるリンクから複数のリンクに枝分かれする場合に、各枝のリンクの経路コスト（開始リンクから当該リンクに至るリンクコストの総和）の大小を比較し、この経路コストの小さい順に並べ変えて、経路コストの小さいリンクからさらに探索を続けて行くという方法を採用している。
従って、最初に終了リンクに到達すれば、その時点で終了リンクに到達する最小コストの経路が決定される。リンクコストの小さいリンクから順に探索を行うので、真先に終了リンクに到達した経路がそのまま最小コストの経路となるからである。
【００４９】
一方、ポテンシャル法では、あるリンクから複数のリンクに枝分かれする場合に、各枝のリンクの経路コストの大小の比較をせずに、すべてのリンクを同等に扱い、各枝のリンクからさらに探索を続けていくという方法を採用している。
従って、最初に終了リンクに到達しても、その時点では、他の経路を通って終了リンクに到達する可能性が残されているため、ネットワークにあるすべてのリンクを探索し終わった時点で初めて、終了リンクに到達する最小コストの経路が決定される。
【００５０】
《経路探索処理の内容》
図３は、本システム１を利用した経路探索処理のフローチャートである。
図３に示すように、まず、車両３の搭乗者が車載装置４に対して出発地点と目的地点の設定を行う（ステップＳ０）。この場合、出発地点の設定がない場合には、車両３の現在位置が出発地点となる。
【００５１】
上記出発地点と目的地点は、携帯電話機８（図２）を通じてサーバ装置２に送信され、コンピュータ１１によって経路探索処理が行われる。
サーバ装置２のコンピュータ１１（具体的には、演算装置１９）は、まず、地点に対してリンクを選択するリンク選択の処理を行う（ステップＳ１）。これにより、出発地点からのアクセスに最適なリンクが開始リンクとされ、かつ、目的地点への到達直前のリンクとして最適なもの（目的地点から見れば、アクセスに最適なリンク）が終了リンクとされる。
【００５２】
図４は、上記ステップＳ１におけるリンク選択の内容を示すフローチャートである。図において、コンピュータ１１は、出発地点（始点）に関する開始リンクの選択（ステップＳ１−１）と、目的地点（終点）に関する終了リンクの選択（ステップＳ１−２）とを実行する。
図５はさらに具体的に、図４のステップＳ１−１，Ｓ１−２に共通の、リンク選択処理の内容を示すフローチャートである。
【００５３】
次に、図５において、例えば開始リンク選択の処理（ステップＳ１−１）を想定して説明する。また、図６は、図５のフローチャートによる処理の概念を地図上で表現した具体例であり、出発地点をＰとする。
【００５４】
図５において、コンピュータ１１は、まず、最寄りの道路（リンク）を探索するための最近傍距離Ｌｍｉｎを初期設定する（ステップＳ１０）。この距離は例えばＰから半径２ｋｍである。そして、コンピュータ１１は、Ｐから当該距離内にあるネットワークデータ及び障害データを地図データベース１６（図２）から読み込む。このフローチャートの処理の一つの目的は、最短距離にあるリンクを選択することである。そのため、コンピュータ１１は、Ｐから各リンクの最近傍点までに引いた線分の長さを全てチェックし、それらの中で最短となるものを探す。最初の時点では、まだ何もチェックしていないため、コンピュータ１１は、ステップＳ１１からステップＳ１２へ進み、次の線分すなわち最初の線分についての処理を行う。
【００５５】
ここで、コンピュータ１１は、リンクの存在している領域内でいずれかのリンクの最近傍点までに線分を引いて交点Ｑ（図６参照）を設定し、その座標を求める（ステップＳ１３）。さらに、コンピュータ１１は、ＰとＱと間の距離Ｌを求め（ステップＳ１４）、これを最近傍距離Ｌｍｉｎと比較する（ステップＳ１５）。ここで、Ｌｍｉｎ＞Ｌでなければコンピュータ１１はステップＳ１１，Ｓ１２に戻り、次の線分についてステップＳ１３〜Ｓ１５の処理を行う。そのうちに、Ｌｍｉｎ＞Ｌを満たす距離Ｌが現れると、コンピュータ１１は、線分Ｐ−Ｑが障害線と交差するか否かを調べる（ステップＳ１６，Ｓ１７）。ここで、障害線とは例えば河川であり、データ的には河川の中央を、複数のリンクを接続して折れ線状に示すものの他、川幅方向の両端を同様の折れ線状に示すものであってもよい。
【００５６】
コンピュータ１１は、線分Ｐ−Ｑが障害線と交差する場合（ステップＳ１７のＹｅｓ）には、次の線分のチェックを行う（ステップＳ１１，Ｓ１２）。このことは、当該線分Ｐ−Ｑの距離を、最近傍距離の更新（ステップＳ１８）の対象としないことを意味し、さらには、当該線分に係るリンクを選択しないことを意味する。言い換えれば、ステップＳ１６，Ｓ１７の処理を行うことによって、障害線は、リンク選択若しくはリンクアクセスに対する否定的要素すなわち、通過を妨げる要素としての意味を持つ。すなわち、このフローチャートの処理のもう一つの目的は、障害線によってアクセスできないリンクを選択対象から除外することにある。
【００５７】
そして、ステップＳ１５においてＬｍｉｎ＞Ｌを満たす距離Ｌが現れ、しかも、線分Ｐ−Ｑが障害線と交差しないとき（ステップＳ１７のＮｏ）は、コンピュータ１１は、当該Ｌをもって、最近傍距離Ｌｍｉｎを更新する（ステップＳ１８）。以下同様に、さらに小さい距離Ｌが現れ、かつ、障害線と交差しないという条件が満たされれば、コンピュータ１１は、最近傍距離Ｌｍｉｎを更新する（ステップＳ１８）。全ての線分のチェックが終了すれば、コンピュータ１１は、最近傍距離にあるリンクを開始リンクとして選択する（ステップＳ１９）。こうして、地点Ｐとの距離に相当する線分が障害領域（障害線）と交差しないリンクの中で、最短距離にあるリンクが、開始リンクとして選択される。
【００５８】
なお、図６の一例で言えば、単に最短距離にあるリンクＡではなく、川と交差せずに最短距離でアクセスできるリンクＢが選択されることになる。
開始リンクの選択後、同様にして、終了リンクが選択される（図４のステップＳ１−２）。なお、選択の順序は逆でもよい。
図３に戻り、コンピュータ１１は、前述のリンクデータの中で、開始リンクから終了リンクまでを含むネットワークデータを、地図データベース１６から取得する（ステップＳ２）。
【００５９】
次に、コンピュータ１１は、取得したネットワークデータに対して前記経路探索ロジックを実行する（ステップＳ３）。
具体的には、コンピュータ１１は、開始リンクから終了リンクに至るリンクを順次加算してリンクのツリーを構成して行き、終了リンクに至るツリーの中で次の式で定義されるリンクコストが最も少ない経路をダイクストラ法又はポテンシャル法による経路探索ロジックにより求めて、推奨経路を特定する（ステップＳ４）。
【００６０】
リンクコスト＝ （ａ×リンク旅行時間）
＋（ｂ×リンクの距離）
＋（ｃ×道路種別）
＋（ｄ×通行料金）
＋（ｅ×交差点通過時間）
ただし、ａ〜ｅはルート計算種別及びユーザごとに設定可能な係数である。
【００６１】
特定された推奨経路を示す情報は、コンピュータ１１から車載装置４に送信される（ステップＳ５）。情報提供（ステップＳ６）を受けた車両３の搭乗者は、自身の判断で推奨経路を選択するか否かを判断する（ステップＳ７）。
そして、搭乗者が推奨経路を選択する場合には、車両３をその推奨経路に沿って走行させ、目的地点に到着することになる（ステップＳ８）。
【００６２】
上記のような経路探索の処理、特に、リンク選択の処理は、主としてコンピュータ１１及び地図データベース１６等によって実行することができるが、処理主体を装置として機能的に見れば、図７に示すブロック図で表現することができる。すなわち、コンピュータ１１は、地点取得部１１Ａと、リンク選択部１１Ｂと、経路探索部１１Ｃとを備えている。地図データベース１６は、ネットワークデータ記憶部１６Ａと、障害データ記憶部１６Ｂとを備えている。
【００６３】
ここで、ネットワークデータ記憶部１６Ａは、道路網を構成し、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有する。障害データ記憶部１６Ｂは、その全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する。地点取得部１１Ａは、車載装置４（図３）から、上記全体領域内から始点及び終点を取得する。リンク選択部１１Ｂは、障害領域と交差せずに始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する。そして、ステップＳ２〜Ｓ５（図３）に対応する機能部分である経路探索部１１Ｃは、開始リンクから終了リンクまでの推奨経路を探索する。
【００６４】
本発明は、上記のような各部の機能をコンピュータ１１により実現するプログラムでもあり、また、方法でもある。
上記のような経路探索プログラム／方法／装置、特に、リンク選択プログラム／方法／装置によれば、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータ１１は、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。また、その結果、経路探索の信頼性を高めて実際の走行に支障のない推奨経路を得ることができる。
【００６５】
なお、上記実施形態でのリンク選択の一つのルールは、典型的には、より距離が近いリンクを探すことであるが、これに限定される訳ではない。例えば、アクセスの方向性を選択ルールに含めてもよい。
具体的には、例えば、終了リンクとなる道路から左折して目的地点に達する場合と、右折して目的地点に達する場合とでは、一般には左折の方が簡単であるため、運転者のストレスが異なる。そこで、終了リンクから左折して目的地点に達するような経路探索（リンク選択）をするようにしてもよい。また、目的地点前の道路脇に駐車が可能な場合において、左寄せして駐車し、降車して道路を横切り、右方向の目的地点に向かう場合と、左寄せして駐車し、降車してそのまま左方向の目的地点に向かう場合とでは、便利さが異なる。そこで、目的地点が道路の左方向にあるような経路探索（リンク選択）をするようにしてもよい。
また、有料道路・一般道路のどちらを優先するか、を選択ルールに加えてもよい。
【００６６】
《障害データのその他の活用》
なお、障害領域として２次元の領域を登録している場合、通常、当該領域には車両を乗り入れることが不可能である。かかる２次元の領域とは、例えば、そもそも車両の乗り入れを禁止されている歩行者天国や行楽地の敷地内などの走行禁止領域、又は、河川や海などの走行が不可能な領域である。
そこで、障害領域を２次元のデータとして保持している場合には、当該データを用いて以下のような機能を実現することが可能である。
【００６７】
例えば、ドライバが指定した現在地、目的地や経由地などが、障害領域内である場合、経路探索をすることができないため、指定された地点が車両の乗り入れ不可能な地域であるために経路探索ができない旨の情報を視覚的あるいは聴覚的な情報としてドライバに報知することができる。なお、ドライバが指定した地点でなくても、ＧＰＳによって取得される自車両の現在地がＧＰＳのシステム誤差の影響で障害領域内である場合にも同様に報知することが可能である。
このように、経路探索が不可能な原因をドライバに報知することで、ドライバが条件を変更して経路探索を再試行することが可能となるので、ナビゲーションシステムの利便性を高めることができる。
【００６８】
以上のように、単に地図表示画面上に描画するためだけに河川や海等の地形データを記憶しておくだけではなく、走行禁止領域のような障害データをデータベースとして保持しておくことで、当該障害データを、カーナビゲーションシステムの様々な目的に活用することができる。
なお、このような走行禁止領域等の設定においては、当該境界線近辺については、ある程度縮退させておくことが望ましい。これは、地図上でドライバが地点を指定する際の誤差やＧＰＳ等による現在位置の取得誤差などに配慮するためである。
【００６９】
《その他一般論》
今回開示した各実施形態は本発明の例示であって制限的なものではない。本発明の権利範囲は、上記実施形態ではなく特許請求の範囲によって示され、特許請求の範囲とその構成と均等な範囲でのすべての変更が含まれる。
【００７０】
《その他変形例１》
なお、上記実施形態では、サーバ装置２と車載装置４との間の無線通信を、携帯電話機８を通じて行っているが、この無線通信は、例えば、光ビーコン、無線ＬＡＮ、ＤＳＲＣ（Dedicated Short Range Communication ）等の比較的エリアの狭い路車間通信で行うこともできる。
また、上記実施形態ではコンピュータ１１が経路探索を実行しているが、各車両３に搭載された車載装置４が独自に、当該経路探索やリンク選択を行うことにしてもよい。すなわち、本発明の経路探索装置（リンク選択装置）は、車載装置４の演算装置に組み込むことも可能である。
【００７１】
さらに、上記実施形態では、サーバ装置２と複数の車載装置４とからなるナビゲーションシステム１を例示しているが、当該システム１の構成要素は車載装置４以外のものであってもよい。例えば、サーバ装置２とインターネット通信可能な携帯電話機やノートＰＣ等の端末装置を、上記ナビゲーションシステム１の構成要素とすることもできる。
この場合、出発地点や目的地点の設定作業をＷＥＢサイトの入力画面を通じてユーザが行うことにより、その地点情報をサーバ装置２に送信することができる。
【００７２】
なお、上記実施形態では車両を対象とした経路探索やリンク選択について説明したが、歩行者を対象とする経路探索（いわゆる歩行者ナビ）等であっても同様である。この場合、障害データとしては同様に河川等を設定することができる。また、例えば、地下街での経路探索であれば、３次元空間のネットワークデータが必要であり、障害データとしては、例えば、地上へ出られる出口以外の地面部分は、上には上がれない障害面として設定することができる。
【００７３】
《その他変形例２》
また、以上の実施形態においては、通行不可能な領域である障害領域を設定する例を示したが、通行不可能ではないがアクセスを制限したいアクセス制限領域（当該領域をまたいだリンクの選択がされにくくなるようにするための制限領域）を設定することも可能である。
【００７４】
すなわち通常の処理であれば、ある地点を基準として選択されるリンクは、そのリンクまでの直線距離が最も短いもの（最も近接度が高いもの）、となるが、ある特定の地点を基準とした場合に、直線距離が最短のリンク以外のリンクを選ばせたいケースもある。
例えば、行政区画として指定された領域内を走行することを推奨される車両等において、当該行政区画外のリンクを極力選択しないことが望ましい場合等である。このような場合には、通行不可能な障害領域を設定する方法よりも、アクセスを制限するようなアクセス制限領域を、前記行政区画の境界線のところに設けておく方法を採用すると良い。
【００７５】
そして、前記特定の地点からその近傍にある複数のリンクまでの直線距離を算出する場合において、各リンクに至る直線がアクセス制限領域を交差した場合には、その交差回数等に応じて直線距離に所定の定数を加算する処理や、直線距離に１より大きい所定の係数（例えば２等）を乗算する処理等（近接度が小さくなるような処理）をすれば良い。
【００７６】
このようにすれば、直線距離が短いリンクであっても、実際の直線距離よりも長い距離として算出される（近接度が小さい値として算出される）ため、アクセス制限領域を交差しない他のリンクが選択される確率を高めることができるようになる。
このような方法を用いれば、前記所定の定数等の値の大きさを変えることで、リンクが選択される確率を自由に制御することが可能となり、障害領域を跨いだリンクの選択自体を不可能とする実施形態の方法に比べて、さらに柔軟性の高いシステムを構築することが可能となる。
【００７７】
なお、この場合、例えば、絶対に選ばせたくないリンクがある場合には、当該リンクに至るまでに設けられたアクセス制限領域を交差した場合に加算される所定の定数の値を無限大とすれば良い。そうすることで、実施形態において示した障害領域と同じように、実質的に通行不可能な領域を設定することも可能となる。
【００７８】
《その他応用例》
なお、上記実施形態では道路網におけるリンク選択について説明したが、本発明のリンク選択プログラム／方法／装置は、道路網以外の各種経路網にも適用可能である。要は、複数のリンクとノードとを含む何らかのネットワークデータについて、適用可能である。
また、障害データとしては、河川、崖、フェンス状建造物その他の物理的な障害のデータの他、行政区画上の境界、国境その他の法的な障害のデータもあり得る。
【００７９】
例えば、道路と同様のインフラである上下水道の配管は、経路網を構成するものであり、複数のリンクとノードとを含むネットワークデータとして表すことができる。そして、住宅を新築する際に、どの上水管から水道を引き込み、どの下水管へ汚水を流すかを計画するに当たって、上述のリンク選択の考え方を適用し、アクセスライン上に障害データのない管路（リンク）であって距離最短のもの、を選択することができる。
【００８０】
この場合の障害とは、例えば行政区画の境界線である。すなわち、距離的に近いからと言って、隣の市町村の管路を拝借することは基本的にはできないので、かかる「障害」を避けて、自己の管轄エリア内で最も近い等の選択ルールに基づいて、アクセスに最適なリンクを選択することになる。なお、上下水道（特に下水道）の配管は、立体的な経路網として扱うべきものである。従って、障害データも２次元で設定することが好ましい。
また、障害として活断層のラインを設定すれば、これをなるべく通さないことで、大地震に配慮した配管設計も可能である。
【００８１】
また、例えば、ある地点から既設の電線や光ファイバにどう繋ぐかという場合にも、リンク単位で構成された配線のネットワーク（経路網）について、上述のリンク選択の考え方を適用し、アクセスライン上に障害データのない接続線（リンク）であって距離最短のもの、を選択することができる。障害としては、例えば、営業管轄の境界線や、高圧線を通せない領域との境界面が考えられる。
【００８２】
なお、上記の応用例において障害データによって示される障害領域は、１次元：障害線、２次元：障害面（閉じた面）、３次元：立体形状の障害曲面とすることができる。
【符号の説明】
【００８３】
１１ コンピュータ
１６ 地図データベース
１１Ａ 地点取得部
１１Ｂ リンク選択部
１１Ｃ 経路探索部
１６Ａ ネットワークデータ記憶部
１６Ｂ 障害データ記憶部
Ａ，Ｂ リンク
Ｐ 地点
【技術分野】
【０００１】
本発明は、典型的には、車両の出発地点から目的地点までの推奨経路を探索するためのプログラム／方法／装置、及び、それらの一部を成すリンク選択のプログラム／方法／装置に関する。
【背景技術】
【０００２】
自車両を出発地点から目的地点まで誘導する経路探索装置（例えば、車載ナビゲーション装置）は既に周知である。この経路探索装置は、出発地点から目的地点までの最適経路を所定の経路探索ロジックを用いて演算し、この演算結果である最適経路を、ディスプレイやスピーカ等の出力装置を介して画像や音声で搭乗者に案内するものである。
【０００３】
かかる最適経路の探索のために、経路探索装置は、道路を、その最小単位のリンクに分解して記憶するとともに、リンク同士の接続点はノードとして記憶している（例えば、特許文献１参照）。また、経路探索装置は、リンクに関するその他種々の情報を記憶している。このような情報に基づいて、例えば、距離や道路種別等を考慮したリンクコストが最小となる最適経路を特定の経路探索ロジックによって算出するのが一般的であり、この経路探索ロジックとしては、例えばダイクストラ法やポテンシャル法が利用される（特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３８６９０５５号
【特許文献２】特開平７−１０３７７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のような従来の経路探索装置では、例えば、車両の出発地点（現在位置又は、出発地点として指定した地点）が広大な敷地内にあって、その周辺に複数の公道や河川があるとき、目的地への経路探索を実行すると、河川と交差して最寄りの道路へアクセスするような推奨経路が得られる場合がある。
【０００６】
図８は、このような一例を地図上に示す図である。図において、出発地点Ｐから最寄りの道路リンクＡにアクセスする経路が推奨されても、川を横切る形となり、実際には行けない。また、目的地として装置に設定した場所へ、同様の理由によって、道路から進入できない推奨経路が得られる場合もある。
これらの場合には、推奨経路の通りに走行することができず、経路探索の信頼性が乏しい。
【０００７】
かかる従来の問題点に鑑み、本発明は、経路探索の信頼性を高めて適切な推奨経路を得ることを目的とする。
【課題を解決するための手段】
【０００８】
（１）本発明のリンク選択プログラムは、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、前記全体領域内から任意の地点を取得する機能と、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する機能とをコンピュータに実現させるものである。
【０００９】
上記のようなリンク選択プログラムによって各機能を実現するコンピュータは、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１０】
（２）また、上記リンク選択プログラムにおいて、障害データには、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、全体領域内に設定された位置及び形状データが含まれるものであってもよい。
この場合、実際には横切って通過できないこれらの障害を通過するかのような誤ったリンク選択を防止することができる。
【００１１】
（３）また、上記（１）又は（２）のリンク選択プログラムにおいて、障害データは、ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっていることが好ましい（Ｎは２以上の整数）。
この場合、ネットワークデータに対して、障害データは少なくとも１次元低いので、比較的コンパクトなデータサイズとすることができる。
なお、点や線で表される情報は１次元、平面的な広がりを持つ情報は２次元、そして、平面的な広がりに加えて高さの情報を持つものは３次元である。従って、道路の単なる１本のリンクデータは１次元、複数のリンクデータを網状に繋ぎ合わせた道路のネットワークデータや、平面情報のみのデジタル地図などの情報は２次元、そして、平面情報に加えて高低の情報が加えられているデジタル地図などの情報は３次元である。
【００１２】
（４）一方、本発明のリンク選択方法は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、前記全体領域内から任意の地点を取得し、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するものである。
【００１３】
上記のようなリンク選択方法においては、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１４】
（５）また、本発明のリンク選択装置は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、前記全体領域内から任意の地点を取得する地点取得部と、前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するリンク選択部とを備えたものである。
【００１５】
上記のようなリンク選択装置は、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。
【００１６】
（６）また、他の観点から見た本発明は、始点から終点までの経路を探索する機能をコンピュータに実現させるための経路探索プログラムであって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、前記全体領域内から前記始点及び終点を取得する機能と、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する機能と、前記開始リンクから前記終了リンクまでの推奨経路を探索する機能とを、コンピュータに実現させるための経路探索プログラムである。
【００１７】
上記のような経路探索プログラムによって各機能を実現するコンピュータは、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００１８】
（７）また、上記（６）の経路探索プログラムにおいて、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、全体領域内に設定された位置及び形状データが含まれるものであってもよい。
この場合、実際には横切って通過できないこれらの障害を通過するかのような誤ったリンク選択を防止することができる。
【００１９】
（８）また、上記（６）又は（７）の経路探索プログラムにおいて、障害データは、ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっていることが好ましい。
この場合、ネットワークデータに対して、障害データは少なくとも１次元低いので、比較的コンパクトなデータサイズとすることができる。
【００２０】
（９）また、本発明は、始点から終点までの経路を探索する経路探索方法であって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、前記全体領域内から前記始点及び終点を取得し、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択し、前記開始リンクから前記終了リンクまでの推奨経路を探索するものである。
【００２１】
上記のような経路探索方法においては、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００２２】
（１０）また、本発明は、始点から終点までの経路を探索する経路探索装置であって、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、前記全体領域内から前記始点及び終点を取得する地点取得部と、前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択するリンク選択部と、前記開始リンクから前記終了リンクまでの推奨経路を探索する経路探索部とを備えたものである。
【００２３】
上記のような経路探索装置は、アクセスを妨げる障害領域と交差せずに始点・終点からアクセスするのに適した開始リンク・終了リンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべき開始リンク・終了リンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択して、推奨経路を探索することができる。
【００２４】
（１１）また、さらに他の観点から見た本発明は、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、前記全体領域内でリンクへのアクセスをしにくくするための領域であるアクセス制限領域を成す制限データを取得する機能と、前記全体領域内から任意の地点を取得する機能と、前記地点と、その近傍に存在する複数のリンクそれぞれとの近接度を、前記地点から前記複数の各リンクまでの直線の距離に基づいて算出する機能と、算出される前記近接度に基づいて、前記複数のリンクから一のリンクを選択する機能と、をコンピュータに実現させるためのリンク選択プログラムであって、前記直線が前記アクセス制限領域と交差する場合に算出される近接度が、当該リンクが選択されにくいような値となること、を特徴とするものである。
【００２５】
上記のようなリンク選択プログラムによって各機能を実現するコンピュータは、アクセス制限領域と交差するリンクの近接度を、選択されにくい値にするので、結果的に、このようなリンクをなるべく避けつつ、地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータは、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である制限データも考慮して、アクセスすべきリンクを選択し、しかも、いわば、恣意的に最適な（若しくは賢明な）リンクを選択することができる。
なお、前記近接度とは、前記任意の地点から各リンクまでの直線距離の長さに基づいて算出される指標であり、一般的には、当該距離の長さが短いほど近接度が大きいものとして算出される。本発明では、アクセス制限領域と交差する直線の場合には、例えば、実際の直線距離の長さに対して、所定の定数を加算したり、直線距離を２倍にする処理をしたりすることで、近接度を小さくすることができる。
【発明の効果】
【００２６】
本発明のリンク選択プログラム／方法／装置、及び、経路探索プログラム／方法／装置によれば、経路探索の信頼性（物理的な面でのリンク選択の信頼性の他、恣意的なリンク選択の信頼性も含む。）を高めて適切な推奨経路を得ることができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施形態に係る経路検索装置を有するナビゲーションシステムの全体構成を示す概略構成図である。
【図２】図１のシステムの機能ブロック図である。
【図３】図１のシステムを利用した経路探索処理のフローチャートである。
【図４】図３のステップＳ１におけるリンク選択の内容を示すフローチャートである。
【図５】図４のステップＳ１−１，Ｓ１−２に共通の、リンク選択処理の内容を示すフローチャートである。
【図６】図５のフローチャートによる処理の概念を地図上で表現した具体例である。
【図７】経路探索の処理、特に、リンク選択の処理の主体を装置として機能的に見たときのブロック図である。
【図８】最寄りのリンクを探す状態の一例（従来例）である。
【発明を実施するための形態】
【００２８】
《システムの全体構成》
図１は、本発明の一実施形態に係る経路検索装置（経路探索プログラムや、リンク選択プログラム／装置も含む。）を有するナビゲーションシステムの全体構成を示す概略構成図であり、図２は、同システムの機能ブロック図である。
図１及び図２に示すように、本実施形態のナビゲーションシステム１は、サーバ装置２と、複数の車両３にそれぞれ搭載された車載装置４とによって構成されている。
なお、本明細書において、「車両」とは、自動車、原動機付き自転車、軽車両及びトロリーバス等のことをいう。また、「車載装置」とは、車両に搭載されており、その搭乗者に対して目的地までの経路を案内するいわゆるナビゲーション装置のことをいう。
【００２９】
このナビゲーションシステム１は、予め入会登録された会員（ユーザ）の車両３自体をセンサとして、各車両３からサーバ装置２が情報収集し、メンバー間で相互に情報提供し合って運用することにより、サーバ装置２が各会員に対して有用な交通情報を提供するようにしたものである。
従って、本システム１によれば、通常のＶＩＣＳ（登録商標：Vehicle Information and Communication System）情報とともに、このＶＩＣＳ情報に含まれていないより詳細かつ動的な交通情報を、各会員の車両３に提供することができる。
【００３０】
本システム１のサーバ装置２は、専用の通信回線を介して交通情報センタ５に接続されており、必要に応じてＶＩＣＳ情報を交通情報センタ５から入手している。また、サーバ装置２は、インターネット網６を通じて携帯電話機８の無線基地局７と双方向で通信可能である。
各車両３の車載装置４は、搭乗者の携帯端末である携帯電話機８を介して、無線基地局７と双方向で通信可能であり、無線基地局７は上記インターネット網８に接続されている。このため、各車両３の車載装置４は、ほぼリアルタイムでサーバ装置２に対して情報を送受信可能となっている。
【００３１】
各車両３の車載装置４は、ＧＰＳ（Global Positioning System）アンテナと、ＧＰＳ受信機と、道路地図データベースと、入力デバイスと、ディスプレイ及びスピーカ等よりなる出力装置とを備えており、ＧＰＳ受信機で検出した現在位置をディスプレイの画面上に表示できるようになっている。
また、車載装置４は、入力デバイスで入力された所定の旅行条件に基づいて、旅行ルートを演算可能なルート演算装置（図示せず）を備えている。
【００３２】
車載装置４に入力可能な旅行条件としては、出発地点（現在位置又は指定した地点）や目的地点のほか、経由地や優先経路（一般道路優先又は有料道路優先や、距離優先又は道幅優先）等がある。ルート演算装置のメモリには、入力される情報や自身で演算した旅行ルートに加えて、サーバ装置２から提供されたルート探索情報を保存することもできる。
なお、本実施形態の車載装置４は、ＥＴＣ対応であり、有料道路の料金所等に設置されたＥＴＣ路側処理装置と無線による路車間通信を行うことができる。
【００３３】
《サーバ装置の内部構成》
図２に示すように、サーバ装置２は、ワークステーション等よりなるコンピュータ１１と、このコンピュータ１１に接続された通信インターフェースよりなる第１及び第２通信部１２，１３と、各種データベース１４〜１６とから構成されている。
第１通信部１２は、専用回線で交通情報センタ５に接続されている。また、第２通信部１３は、インターネット網６を介して前記無線基地局７に接続され、この無線基地局７と車両３の搭乗者の携帯電話機８との間の無線通信を通じて、車載装置４との間で情報の送受信を行う。
【００３４】
《会員データベース》
各データベース１４〜１６のうち、会員データベース１４には、当該システム１に参加する登録会員の識別情報が保存されている。
コンピュータ１１は、会員データベース１４に記録されている特定の登録会員から受信した入力情報（出発地点及び目的地点等）に基づいて、後述する経路探索処理を実行する。
【００３５】
《交通情報データベース》
交通情報データベース１５には、第１通信部１２が受信した交通情報センタ５からのＶＩＣＳ情報が保存される。このＶＩＣＳ情報は、コンピュータ１１が交通情報センタ５からのＶＩＣＳ情報を抽出するごとに更新され、ほぼ最新の情報が保持される。
また、交通情報データベース１５には、特定の登録会員から受信したリンク番号、リンク進入時刻、リンク退出時刻、リンク旅行時間等よりなる交通情報（プローブ情報）も保存される。
【００３６】
この場合、車載装置４は、所定時間毎（例えば、０．１秒毎）又は所定距離毎（例えば、５ｍ毎）に位置を検出しており、各リンクについて、検出位置がリンクの始端の位置を通過（一致）した時刻をリンク進入時刻とし、検出位置がリンクの終端の位置を通過（一致）した時刻をリンク退出時刻とし、リンク退出時刻とリンク進入時刻との差をリンク旅行時間として算出する。
【００３７】
更に、交通情報データベース１５には、高速道路等の有料道路の料金情報１７が含まれている。
この料金情報１７は、例えばＮＥＸＣＯが公表している各ＩＣ間の通行料金テーブルよりなり、この通行料金テーブルは、深夜割引、通勤割引及び早朝夜間割等の割引制度ごとに定められた複数のテーブルよりなる。
【００３８】
《地図データベース》
地図データベース１６には道路地図データが記録されている。この道路地図データには、道路網を構成する単位をリンクとして、各リンクに関する種々の情報が含まれている。例えば、当該情報には、ネットワークデータとしての「交差点データ」と「リンクデータ」とが含まれている。
このうち、「交差点データ」は、交差点ＩＤと交差点位置とを対応付けたデータである。また、「リンクデータ」は、特定リンクのリンクＩＤに対して、特定リンクの始点・終点（ノード）・補間点の位置、特定リンクの始点に接続するリンクＩＤ、特定リンクの終点に接続するリンクＩＤ、特定リンクのリンクコスト等、を対応付けたデータよりなる。
【００３９】
また、平均速度や渋滞状況については、交通情報データベース１５のＶＩＣＳ情報やプローブ情報に基づいて設定される。従って、これらの各情報が更新される度に、リンクデータに含まれる各リンクの平均速度及び渋滞状況も更新される。
また、地図データベース１６には、地図上の各道路に対応するリンクが一般道路か有料道路かの道路種別も含まれている。
【００４０】
一方、リンクコストは、例えば、特定リンクとその終点に接続するリンクの組み合わせの数だけ用意されており、特定リンクの始点に進入してから当該特定リンクの終点を退出し、次に接続するリンクの始点に進入するまでに要するコスト（時間）を含んでいる。
すなわち、リンクコストには、特定リンクの始点から終点までを走行するのに要する時間コストと、その特定リンクの終点から次のリンクの始点までを走行するのに要する時間コスト、つまり、交差点通過に要する時間コストとが含まれる。
【００４１】
上記時間コストは、平日、土曜、日曜及び祝日といった日種別ごとに、現時点から１日先までの５分毎のデータが用意されており、この５分毎のデータは、交通情報データベース１５のＶＩＣＳ情報や、特定会員から受信したプローブ情報に基づいて作成される。
【００４２】
一方、地図データベース１６には、上記のようなネットワークデータの他に、車両通行の障害となる領域（障害領域）を示す障害データとして、当該領域の位置や形状データが格納されている。障害データとは例えば、河川等の水領域（海岸線も含む。）、崖、及び、フェンス、柵、塀その他のフェンス状建造物であり、車両は、これらと交差する経路で通行する（すなわち横切る）ことはできない。
【００４３】
また、障害データは、リンクと同様に、特定の障害データ単位ＩＤに対して、始点・終点（ノード）・補間点の位置、始点に接続する他の障害データ単位ＩＤ、終点に接続する他の障害データ単位ＩＤ等、を対応付けたデータより構成することができる。
【００４４】
これらの障害データは、ネットワークデータにより表される道路網が２次元（平面）であれば、１次元の障害線（ポリライン）により表現することができる。また、道路網が３次元であれば、２次元の閉じた面（ポリゴン）からなる障害面として表現することができる。すなわち、Ｎ次元（Ｎは２以上の整数）の道路網に対しては（Ｎ−１）次元の障害データとすればよい。この場合、ネットワークデータに対して、障害データは１次元低いので、比較的コンパクトなデータサイズとすることができる。なお、ネットワークデータがリンクアクセス（リンクへのアクセス）や経路探索のための肯定的な情報であるとすれば、障害データは、否定的な情報となるものであり、単なる地図上のグラフィックデータではない。
【００４５】
なお、データの次元は、上記の関係に限定される訳ではなく、障害データの次元が、ネットワークデータの次元と同じであってもよいし、ネットワークデータが３次元で障害データが１次元というような、２次元差があっても構わない。すなわち、ネットワークデータがＮ次元であれば、障害データはＮ次元以下とすることができる。但し、上記のように、障害データのデータサイズを比較的コンパクトにするためには、ネットワークデータがＮ次元であれば、障害データは（Ｎ−１）次元以下とすることが好ましい。
【００４６】
《コンピュータの構成及び機能》
一方、コンピュータ１１は、ＨＤＤやメモリ等よりなる記憶装置１８と、この記憶装置１８から各種のコンピュータプログラムを読み出して実行する演算装置１９とを含んでいる。
【００４７】
このコンピュータプログラムのうちの１つは、車両３が出発地点から目的地点まで走行する場合の推奨経路の探索が可能なプログラムであり、このプログラムには、具体的にはダイクストラ法やポテンシャル法による経路探索ロジックが含まれている。
すなわち、演算装置１９は、上記経路探索ロジックを含むプログラムを実行することにより、出発地点から目的地点までの最小のリンクコストとなる経路（推奨経路）を探索する。
【００４８】
ここで、ダイクストラ法では、開始リンクから始まるリンクのツリーを構成していくに当たって、あるリンクから複数のリンクに枝分かれする場合に、各枝のリンクの経路コスト（開始リンクから当該リンクに至るリンクコストの総和）の大小を比較し、この経路コストの小さい順に並べ変えて、経路コストの小さいリンクからさらに探索を続けて行くという方法を採用している。
従って、最初に終了リンクに到達すれば、その時点で終了リンクに到達する最小コストの経路が決定される。リンクコストの小さいリンクから順に探索を行うので、真先に終了リンクに到達した経路がそのまま最小コストの経路となるからである。
【００４９】
一方、ポテンシャル法では、あるリンクから複数のリンクに枝分かれする場合に、各枝のリンクの経路コストの大小の比較をせずに、すべてのリンクを同等に扱い、各枝のリンクからさらに探索を続けていくという方法を採用している。
従って、最初に終了リンクに到達しても、その時点では、他の経路を通って終了リンクに到達する可能性が残されているため、ネットワークにあるすべてのリンクを探索し終わった時点で初めて、終了リンクに到達する最小コストの経路が決定される。
【００５０】
《経路探索処理の内容》
図３は、本システム１を利用した経路探索処理のフローチャートである。
図３に示すように、まず、車両３の搭乗者が車載装置４に対して出発地点と目的地点の設定を行う（ステップＳ０）。この場合、出発地点の設定がない場合には、車両３の現在位置が出発地点となる。
【００５１】
上記出発地点と目的地点は、携帯電話機８（図２）を通じてサーバ装置２に送信され、コンピュータ１１によって経路探索処理が行われる。
サーバ装置２のコンピュータ１１（具体的には、演算装置１９）は、まず、地点に対してリンクを選択するリンク選択の処理を行う（ステップＳ１）。これにより、出発地点からのアクセスに最適なリンクが開始リンクとされ、かつ、目的地点への到達直前のリンクとして最適なもの（目的地点から見れば、アクセスに最適なリンク）が終了リンクとされる。
【００５２】
図４は、上記ステップＳ１におけるリンク選択の内容を示すフローチャートである。図において、コンピュータ１１は、出発地点（始点）に関する開始リンクの選択（ステップＳ１−１）と、目的地点（終点）に関する終了リンクの選択（ステップＳ１−２）とを実行する。
図５はさらに具体的に、図４のステップＳ１−１，Ｓ１−２に共通の、リンク選択処理の内容を示すフローチャートである。
【００５３】
次に、図５において、例えば開始リンク選択の処理（ステップＳ１−１）を想定して説明する。また、図６は、図５のフローチャートによる処理の概念を地図上で表現した具体例であり、出発地点をＰとする。
【００５４】
図５において、コンピュータ１１は、まず、最寄りの道路（リンク）を探索するための最近傍距離Ｌｍｉｎを初期設定する（ステップＳ１０）。この距離は例えばＰから半径２ｋｍである。そして、コンピュータ１１は、Ｐから当該距離内にあるネットワークデータ及び障害データを地図データベース１６（図２）から読み込む。このフローチャートの処理の一つの目的は、最短距離にあるリンクを選択することである。そのため、コンピュータ１１は、Ｐから各リンクの最近傍点までに引いた線分の長さを全てチェックし、それらの中で最短となるものを探す。最初の時点では、まだ何もチェックしていないため、コンピュータ１１は、ステップＳ１１からステップＳ１２へ進み、次の線分すなわち最初の線分についての処理を行う。
【００５５】
ここで、コンピュータ１１は、リンクの存在している領域内でいずれかのリンクの最近傍点までに線分を引いて交点Ｑ（図６参照）を設定し、その座標を求める（ステップＳ１３）。さらに、コンピュータ１１は、ＰとＱと間の距離Ｌを求め（ステップＳ１４）、これを最近傍距離Ｌｍｉｎと比較する（ステップＳ１５）。ここで、Ｌｍｉｎ＞Ｌでなければコンピュータ１１はステップＳ１１，Ｓ１２に戻り、次の線分についてステップＳ１３〜Ｓ１５の処理を行う。そのうちに、Ｌｍｉｎ＞Ｌを満たす距離Ｌが現れると、コンピュータ１１は、線分Ｐ−Ｑが障害線と交差するか否かを調べる（ステップＳ１６，Ｓ１７）。ここで、障害線とは例えば河川であり、データ的には河川の中央を、複数のリンクを接続して折れ線状に示すものの他、川幅方向の両端を同様の折れ線状に示すものであってもよい。
【００５６】
コンピュータ１１は、線分Ｐ−Ｑが障害線と交差する場合（ステップＳ１７のＹｅｓ）には、次の線分のチェックを行う（ステップＳ１１，Ｓ１２）。このことは、当該線分Ｐ−Ｑの距離を、最近傍距離の更新（ステップＳ１８）の対象としないことを意味し、さらには、当該線分に係るリンクを選択しないことを意味する。言い換えれば、ステップＳ１６，Ｓ１７の処理を行うことによって、障害線は、リンク選択若しくはリンクアクセスに対する否定的要素すなわち、通過を妨げる要素としての意味を持つ。すなわち、このフローチャートの処理のもう一つの目的は、障害線によってアクセスできないリンクを選択対象から除外することにある。
【００５７】
そして、ステップＳ１５においてＬｍｉｎ＞Ｌを満たす距離Ｌが現れ、しかも、線分Ｐ−Ｑが障害線と交差しないとき（ステップＳ１７のＮｏ）は、コンピュータ１１は、当該Ｌをもって、最近傍距離Ｌｍｉｎを更新する（ステップＳ１８）。以下同様に、さらに小さい距離Ｌが現れ、かつ、障害線と交差しないという条件が満たされれば、コンピュータ１１は、最近傍距離Ｌｍｉｎを更新する（ステップＳ１８）。全ての線分のチェックが終了すれば、コンピュータ１１は、最近傍距離にあるリンクを開始リンクとして選択する（ステップＳ１９）。こうして、地点Ｐとの距離に相当する線分が障害領域（障害線）と交差しないリンクの中で、最短距離にあるリンクが、開始リンクとして選択される。
【００５８】
なお、図６の一例で言えば、単に最短距離にあるリンクＡではなく、川と交差せずに最短距離でアクセスできるリンクＢが選択されることになる。
開始リンクの選択後、同様にして、終了リンクが選択される（図４のステップＳ１−２）。なお、選択の順序は逆でもよい。
図３に戻り、コンピュータ１１は、前述のリンクデータの中で、開始リンクから終了リンクまでを含むネットワークデータを、地図データベース１６から取得する（ステップＳ２）。
【００５９】
次に、コンピュータ１１は、取得したネットワークデータに対して前記経路探索ロジックを実行する（ステップＳ３）。
具体的には、コンピュータ１１は、開始リンクから終了リンクに至るリンクを順次加算してリンクのツリーを構成して行き、終了リンクに至るツリーの中で次の式で定義されるリンクコストが最も少ない経路をダイクストラ法又はポテンシャル法による経路探索ロジックにより求めて、推奨経路を特定する（ステップＳ４）。
【００６０】
リンクコスト＝ （ａ×リンク旅行時間）
＋（ｂ×リンクの距離）
＋（ｃ×道路種別）
＋（ｄ×通行料金）
＋（ｅ×交差点通過時間）
ただし、ａ〜ｅはルート計算種別及びユーザごとに設定可能な係数である。
【００６１】
特定された推奨経路を示す情報は、コンピュータ１１から車載装置４に送信される（ステップＳ５）。情報提供（ステップＳ６）を受けた車両３の搭乗者は、自身の判断で推奨経路を選択するか否かを判断する（ステップＳ７）。
そして、搭乗者が推奨経路を選択する場合には、車両３をその推奨経路に沿って走行させ、目的地点に到着することになる（ステップＳ８）。
【００６２】
上記のような経路探索の処理、特に、リンク選択の処理は、主としてコンピュータ１１及び地図データベース１６等によって実行することができるが、処理主体を装置として機能的に見れば、図７に示すブロック図で表現することができる。すなわち、コンピュータ１１は、地点取得部１１Ａと、リンク選択部１１Ｂと、経路探索部１１Ｃとを備えている。地図データベース１６は、ネットワークデータ記憶部１６Ａと、障害データ記憶部１６Ｂとを備えている。
【００６３】
ここで、ネットワークデータ記憶部１６Ａは、道路網を構成し、所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有する。障害データ記憶部１６Ｂは、その全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する。地点取得部１１Ａは、車載装置４（図３）から、上記全体領域内から始点及び終点を取得する。リンク選択部１１Ｂは、障害領域と交差せずに始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する。そして、ステップＳ２〜Ｓ５（図３）に対応する機能部分である経路探索部１１Ｃは、開始リンクから終了リンクまでの推奨経路を探索する。
【００６４】
本発明は、上記のような各部の機能をコンピュータ１１により実現するプログラムでもあり、また、方法でもある。
上記のような経路探索プログラム／方法／装置、特に、リンク選択プログラム／方法／装置によれば、アクセスを妨げる障害領域と交差せずに地点からアクセスするのに適したリンクを選択することができる。すなわち、コンピュータ１１は、ネットワークデータにのみ依存してリンクを選択するのではなく、否定的な情報である障害データも考慮して、アクセスすべきリンクを選択する。従って、現実にアクセス可能な、最適なリンクを選択することができる。また、その結果、経路探索の信頼性を高めて実際の走行に支障のない推奨経路を得ることができる。
【００６５】
なお、上記実施形態でのリンク選択の一つのルールは、典型的には、より距離が近いリンクを探すことであるが、これに限定される訳ではない。例えば、アクセスの方向性を選択ルールに含めてもよい。
具体的には、例えば、終了リンクとなる道路から左折して目的地点に達する場合と、右折して目的地点に達する場合とでは、一般には左折の方が簡単であるため、運転者のストレスが異なる。そこで、終了リンクから左折して目的地点に達するような経路探索（リンク選択）をするようにしてもよい。また、目的地点前の道路脇に駐車が可能な場合において、左寄せして駐車し、降車して道路を横切り、右方向の目的地点に向かう場合と、左寄せして駐車し、降車してそのまま左方向の目的地点に向かう場合とでは、便利さが異なる。そこで、目的地点が道路の左方向にあるような経路探索（リンク選択）をするようにしてもよい。
また、有料道路・一般道路のどちらを優先するか、を選択ルールに加えてもよい。
【００６６】
《障害データのその他の活用》
なお、障害領域として２次元の領域を登録している場合、通常、当該領域には車両を乗り入れることが不可能である。かかる２次元の領域とは、例えば、そもそも車両の乗り入れを禁止されている歩行者天国や行楽地の敷地内などの走行禁止領域、又は、河川や海などの走行が不可能な領域である。
そこで、障害領域を２次元のデータとして保持している場合には、当該データを用いて以下のような機能を実現することが可能である。
【００６７】
例えば、ドライバが指定した現在地、目的地や経由地などが、障害領域内である場合、経路探索をすることができないため、指定された地点が車両の乗り入れ不可能な地域であるために経路探索ができない旨の情報を視覚的あるいは聴覚的な情報としてドライバに報知することができる。なお、ドライバが指定した地点でなくても、ＧＰＳによって取得される自車両の現在地がＧＰＳのシステム誤差の影響で障害領域内である場合にも同様に報知することが可能である。
このように、経路探索が不可能な原因をドライバに報知することで、ドライバが条件を変更して経路探索を再試行することが可能となるので、ナビゲーションシステムの利便性を高めることができる。
【００６８】
以上のように、単に地図表示画面上に描画するためだけに河川や海等の地形データを記憶しておくだけではなく、走行禁止領域のような障害データをデータベースとして保持しておくことで、当該障害データを、カーナビゲーションシステムの様々な目的に活用することができる。
なお、このような走行禁止領域等の設定においては、当該境界線近辺については、ある程度縮退させておくことが望ましい。これは、地図上でドライバが地点を指定する際の誤差やＧＰＳ等による現在位置の取得誤差などに配慮するためである。
【００６９】
《その他一般論》
今回開示した各実施形態は本発明の例示であって制限的なものではない。本発明の権利範囲は、上記実施形態ではなく特許請求の範囲によって示され、特許請求の範囲とその構成と均等な範囲でのすべての変更が含まれる。
【００７０】
《その他変形例１》
なお、上記実施形態では、サーバ装置２と車載装置４との間の無線通信を、携帯電話機８を通じて行っているが、この無線通信は、例えば、光ビーコン、無線ＬＡＮ、ＤＳＲＣ（Dedicated Short Range Communication ）等の比較的エリアの狭い路車間通信で行うこともできる。
また、上記実施形態ではコンピュータ１１が経路探索を実行しているが、各車両３に搭載された車載装置４が独自に、当該経路探索やリンク選択を行うことにしてもよい。すなわち、本発明の経路探索装置（リンク選択装置）は、車載装置４の演算装置に組み込むことも可能である。
【００７１】
さらに、上記実施形態では、サーバ装置２と複数の車載装置４とからなるナビゲーションシステム１を例示しているが、当該システム１の構成要素は車載装置４以外のものであってもよい。例えば、サーバ装置２とインターネット通信可能な携帯電話機やノートＰＣ等の端末装置を、上記ナビゲーションシステム１の構成要素とすることもできる。
この場合、出発地点や目的地点の設定作業をＷＥＢサイトの入力画面を通じてユーザが行うことにより、その地点情報をサーバ装置２に送信することができる。
【００７２】
なお、上記実施形態では車両を対象とした経路探索やリンク選択について説明したが、歩行者を対象とする経路探索（いわゆる歩行者ナビ）等であっても同様である。この場合、障害データとしては同様に河川等を設定することができる。また、例えば、地下街での経路探索であれば、３次元空間のネットワークデータが必要であり、障害データとしては、例えば、地上へ出られる出口以外の地面部分は、上には上がれない障害面として設定することができる。
【００７３】
《その他変形例２》
また、以上の実施形態においては、通行不可能な領域である障害領域を設定する例を示したが、通行不可能ではないがアクセスを制限したいアクセス制限領域（当該領域をまたいだリンクの選択がされにくくなるようにするための制限領域）を設定することも可能である。
【００７４】
すなわち通常の処理であれば、ある地点を基準として選択されるリンクは、そのリンクまでの直線距離が最も短いもの（最も近接度が高いもの）、となるが、ある特定の地点を基準とした場合に、直線距離が最短のリンク以外のリンクを選ばせたいケースもある。
例えば、行政区画として指定された領域内を走行することを推奨される車両等において、当該行政区画外のリンクを極力選択しないことが望ましい場合等である。このような場合には、通行不可能な障害領域を設定する方法よりも、アクセスを制限するようなアクセス制限領域を、前記行政区画の境界線のところに設けておく方法を採用すると良い。
【００７５】
そして、前記特定の地点からその近傍にある複数のリンクまでの直線距離を算出する場合において、各リンクに至る直線がアクセス制限領域を交差した場合には、その交差回数等に応じて直線距離に所定の定数を加算する処理や、直線距離に１より大きい所定の係数（例えば２等）を乗算する処理等（近接度が小さくなるような処理）をすれば良い。
【００７６】
このようにすれば、直線距離が短いリンクであっても、実際の直線距離よりも長い距離として算出される（近接度が小さい値として算出される）ため、アクセス制限領域を交差しない他のリンクが選択される確率を高めることができるようになる。
このような方法を用いれば、前記所定の定数等の値の大きさを変えることで、リンクが選択される確率を自由に制御することが可能となり、障害領域を跨いだリンクの選択自体を不可能とする実施形態の方法に比べて、さらに柔軟性の高いシステムを構築することが可能となる。
【００７７】
なお、この場合、例えば、絶対に選ばせたくないリンクがある場合には、当該リンクに至るまでに設けられたアクセス制限領域を交差した場合に加算される所定の定数の値を無限大とすれば良い。そうすることで、実施形態において示した障害領域と同じように、実質的に通行不可能な領域を設定することも可能となる。
【００７８】
《その他応用例》
なお、上記実施形態では道路網におけるリンク選択について説明したが、本発明のリンク選択プログラム／方法／装置は、道路網以外の各種経路網にも適用可能である。要は、複数のリンクとノードとを含む何らかのネットワークデータについて、適用可能である。
また、障害データとしては、河川、崖、フェンス状建造物その他の物理的な障害のデータの他、行政区画上の境界、国境その他の法的な障害のデータもあり得る。
【００７９】
例えば、道路と同様のインフラである上下水道の配管は、経路網を構成するものであり、複数のリンクとノードとを含むネットワークデータとして表すことができる。そして、住宅を新築する際に、どの上水管から水道を引き込み、どの下水管へ汚水を流すかを計画するに当たって、上述のリンク選択の考え方を適用し、アクセスライン上に障害データのない管路（リンク）であって距離最短のもの、を選択することができる。
【００８０】
この場合の障害とは、例えば行政区画の境界線である。すなわち、距離的に近いからと言って、隣の市町村の管路を拝借することは基本的にはできないので、かかる「障害」を避けて、自己の管轄エリア内で最も近い等の選択ルールに基づいて、アクセスに最適なリンクを選択することになる。なお、上下水道（特に下水道）の配管は、立体的な経路網として扱うべきものである。従って、障害データも２次元で設定することが好ましい。
また、障害として活断層のラインを設定すれば、これをなるべく通さないことで、大地震に配慮した配管設計も可能である。
【００８１】
また、例えば、ある地点から既設の電線や光ファイバにどう繋ぐかという場合にも、リンク単位で構成された配線のネットワーク（経路網）について、上述のリンク選択の考え方を適用し、アクセスライン上に障害データのない接続線（リンク）であって距離最短のもの、を選択することができる。障害としては、例えば、営業管轄の境界線や、高圧線を通せない領域との境界面が考えられる。
【００８２】
なお、上記の応用例において障害データによって示される障害領域は、１次元：障害線、２次元：障害面（閉じた面）、３次元：立体形状の障害曲面とすることができる。
【符号の説明】
【００８３】
１１ コンピュータ
１６ 地図データベース
１１Ａ 地点取得部
１１Ｂ リンク選択部
１１Ｃ 経路探索部
１６Ａ ネットワークデータ記憶部
１６Ｂ 障害データ記憶部
Ａ，Ｂ リンク
Ｐ 地点
【特許請求の範囲】
【請求項１】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、
前記全体領域内から任意の地点を取得する機能と、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する機能と
をコンピュータに実現させるためのリンク選択プログラム。
【請求項２】
前記障害データには、河川等の水領域、崖、フェンス状建造物その他の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、前記全体領域内に設定された位置及び形状データが含まれる請求項１記載のリンク選択プログラム。
【請求項３】
前記障害データは、前記ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっている請求項１又は２に記載のリンク選択プログラム。
【請求項４】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、
前記全体領域内から任意の地点を取得し、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する
ことを特徴とするリンク選択方法。
【請求項５】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、
前記全体領域内から任意の地点を取得する地点取得部と、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するリンク選択部と
を備えたことを特徴とするリンク選択装置。
【請求項６】
始点から終点までの経路を探索する機能をコンピュータに実現させるための経路探索プログラムであって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、
前記全体領域内から前記始点及び終点を取得する機能と、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する機能と、
前記開始リンクから前記終了リンクまでの推奨経路を探索する機能と
をコンピュータに実現させるための経路探索プログラム。
【請求項７】
前記障害データには、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、前記全体領域内に設定された位置及び形状データが含まれる請求項６記載の経路探索プログラム。
【請求項８】
前記障害データは、前記ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっている請求項６又は７に記載の経路探索プログラム。
【請求項９】
始点から終点までの経路を探索する経路探索方法であって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、
前記全体領域内から前記始点及び終点を取得し、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択し、
前記開始リンクから前記終了リンクまでの推奨経路を探索する
ことを特徴とする経路探索方法。
【請求項１０】
始点から終点までの経路を探索する経路探索装置であって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、
前記全体領域内から前記始点及び終点を取得する地点取得部と、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択するリンク選択部と、
前記開始リンクから前記終了リンクまでの推奨経路を探索する経路探索部と
を備えたことを特徴とする経路探索装置。
【請求項１１】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスをしにくくするための領域であるアクセス制限領域を成す制限データを取得する機能と、
前記全体領域内から任意の地点を取得する機能と、
前記地点と、その近傍に存在する複数のリンクそれぞれとの近接度を、前記地点から前記複数の各リンクまでの直線の距離に基づいて算出する機能と、
算出される前記近接度に基づいて、前記複数のリンクから一のリンクを選択する機能と、
をコンピュータに実現させるためのリンク選択プログラムであって、
前記直線が前記アクセス制限領域と交差する場合に算出される近接度が、当該リンクが選択されにくいような値となること、を特徴とするリンク選択プログラム。
【請求項１】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、
前記全体領域内から任意の地点を取得する機能と、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する機能と
をコンピュータに実現させるためのリンク選択プログラム。
【請求項２】
前記障害データには、河川等の水領域、崖、フェンス状建造物その他の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、前記全体領域内に設定された位置及び形状データが含まれる請求項１記載のリンク選択プログラム。
【請求項３】
前記障害データは、前記ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっている請求項１又は２に記載のリンク選択プログラム。
【請求項４】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、
前記全体領域内から任意の地点を取得し、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択する
ことを特徴とするリンク選択方法。
【請求項５】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、
前記全体領域内から任意の地点を取得する地点取得部と、
前記障害領域と交差せずに前記地点からアクセスするのに適したリンクを選択するリンク選択部と
を備えたことを特徴とするリンク選択装置。
【請求項６】
始点から終点までの経路を探索する機能をコンピュータに実現させるための経路探索プログラムであって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得する機能と、
前記全体領域内から前記始点及び終点を取得する機能と、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択する機能と、
前記開始リンクから前記終了リンクまでの推奨経路を探索する機能と
をコンピュータに実現させるための経路探索プログラム。
【請求項７】
前記障害データには、河川等の水領域、崖、フェンス状建造物の物理的な障害のデータ、並びに、行政区画上の境界、国境その他の法的な障害のデータ、のいずれかに対応して、前記全体領域内に設定された位置及び形状データが含まれる請求項６記載の経路探索プログラム。
【請求項８】
前記障害データは、前記ネットワークデータがＮ次元で表される場合に、（Ｎ−１）以下の次元のデータになっている請求項６又は７に記載の経路探索プログラム。
【請求項９】
始点から終点までの経路を探索する経路探索方法であって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する他、当該全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを取得し、
前記全体領域内から前記始点及び終点を取得し、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択し、
前記開始リンクから前記終了リンクまでの推奨経路を探索する
ことを特徴とする経路探索方法。
【請求項１０】
始点から終点までの経路を探索する経路探索装置であって、
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを有するネットワークデータ記憶部と、
前記全体領域内でリンクへのアクセスを妨げる障害領域を成す障害データを有する障害データ記憶部と、
前記全体領域内から前記始点及び終点を取得する地点取得部と、
前記障害領域と交差せずに前記始点及び終点からそれぞれアクセスするのに適したリンクである、開始リンク及び終了リンクをそれぞれ選択するリンク選択部と、
前記開始リンクから前記終了リンクまでの推奨経路を探索する経路探索部と
を備えたことを特徴とする経路探索装置。
【請求項１１】
所定の広がりを有する全体領域に含まれる複数のリンクとノードとからなるネットワークデータを取得する機能と、
前記全体領域内でリンクへのアクセスをしにくくするための領域であるアクセス制限領域を成す制限データを取得する機能と、
前記全体領域内から任意の地点を取得する機能と、
前記地点と、その近傍に存在する複数のリンクそれぞれとの近接度を、前記地点から前記複数の各リンクまでの直線の距離に基づいて算出する機能と、
算出される前記近接度に基づいて、前記複数のリンクから一のリンクを選択する機能と、
をコンピュータに実現させるためのリンク選択プログラムであって、
前記直線が前記アクセス制限領域と交差する場合に算出される近接度が、当該リンクが選択されにくいような値となること、を特徴とするリンク選択プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−２７６３４（Ｐ２０１１−２７６３４Ａ）
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願番号】特願２００９−１７５６９８（Ｐ２００９−１７５６９８）
【出願日】平成２１年７月２８日（２００９．７．２８）
【出願人】（５０４１２６１１２）住友電工システムソリューション株式会社 (78)
【Ｆターム（参考）】
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願日】平成２１年７月２８日（２００９．７．２８）
【出願人】（５０４１２６１１２）住友電工システムソリューション株式会社 (78)
【Ｆターム（参考）】
[ Back to top ]