経路探索装置、経路探索方法、コンピュータプログラム及び地図データベース
【課題】 車線変更の負担を軽減した推奨経路を探索することができる経路探索装置を提供する。
【解決手段】 本発明は、出発地点から目的地点までの推奨経路をリンクコストに基づいて探索する経路探索装置２に関する。この経路探索装置２は、複数車線の区間に含まれるリンクＬ１，Ｌ２に対して、その複数車線の区間において車線変更を行うのに必要な車線変更用コストを設定し、設定された車線変更用コストをリンクコストに含めて推奨経路を探索する。
【解決手段】 本発明は、出発地点から目的地点までの推奨経路をリンクコストに基づいて探索する経路探索装置２に関する。この経路探索装置２は、複数車線の区間に含まれるリンクＬ１，Ｌ２に対して、その複数車線の区間において車線変更を行うのに必要な車線変更用コストを設定し、設定された車線変更用コストをリンクコストに含めて推奨経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地点から目的地点までの経路の中から、車線変更に代表される運転負担がなるべく少ない推奨経路を探索することができる経路探索装置、経路探索方法及びこれらを実行するためのコンピュータプログラム、並びに、その探索処理に用いる地図データベースに関する。
【背景技術】
【０００２】
自車両を出発地点から目的地点まで誘導する経路探索装置（例えば、車載ナビゲーション装置）は既に周知である。この経路探索装置は、出発地点から目的地点までの最適経路を所定の経路探索ロジックを用いて演算し、この演算結果である最適経路を、ディスプレイやスピーカ等の出力装置を介して画像や音声で搭乗者に案内するものである。
かかる最適経路の探索手法は、例えば、リンクコストが最小となる最適経路を特定の経路探索ロジックによって算出するのが一般的であり、この経路探索ロジックとしては、例えばダイクストラ法やポテンシャル法が利用される（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−１０３７７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
都市部の一般道路や高速道路では、片側方向の車線が複数の道路が含まれている。このような複数車線の区間を走行中にナビゲーション装置から右折や左折の指示が出されたとしても、右左折が禁止或いは困難な車線を走行している場合には、自車両が交差点に到達するまでに車線変更が間に合わず、指示通りの経路を走行できないことがある。
また、例えば、初心者、高齢者及び女性等の車両運転が比較的上手くないドライバの場合には、そもそも走行中の車線変更自体を嫌がる傾向があるので、なるべく車線変更が少なくて済む経路を案内するのが好ましい。
【０００５】
しかしながら、上記従来の経路探索装置では、リンクコストの構成要素として、旅行時間、距離、料金及び道路種別等が含まれているが、目的地点に到達するまでに必要な車線変更に関するコストは含まれていないので、車線変更の負担がなるべく軽減されるような推奨経路を探索することができなかった。
本発明は、このような問題点に鑑み、車線変更の負担を軽減した推奨経路を探索することができる経路探索装置等を提供することを目的とする。
【課題を解決するための手段】
【０００６】
（１） 本発明の経路探索装置は、出発地点から目的地点までの推奨経路をリンクコストに基づいて探索する経路探索装置であって、複数車線の区間に含まれるリンクに対して、その複数車線の区間において車線変更を行うのに必要な車線変更用コストを設定するコスト設定手段と、設定された前記車線変更用コストを前記リンクコストに含めて前記推奨経路を探索する探索手段と、を備えていることを特徴とする。
【０００７】
本発明の経路探索装置によれば、前記コスト設定手段が、複数車線の区間に含まれるリンクに対して、その複数車線の区間において車線変更を行うのに必要な車線変更用コストを設定し、前記探索手段が、設定された車線変更用コストをリンクコストに含めて推奨経路を探索するので、車線変更の負担を軽減した推奨経路を探索することができる。
このため、探索された推奨経路を、例えば車載のディスプレイやスピーカ等の出力装置を通じてユーザ（車両の搭乗者）に提供するようにすれば、そのユーザに対して車線変更の負担が少ない快適な走行ルートを事前に案内することができる。
【０００８】
（２） 本発明の経路探索装置において、前記コスト設定手段は、例えば、車線変更が可能な区間の距離（区間距離）、その区間の速度（区間速度）、その区間の渋滞度のうちの少なくとも１つに基づいて、前記車線変更用コストを設定することができる。
（３） また、 前記コスト設定手段は、自車両の車種に対応して前記車線変更用コストを設定することもできる。
その理由は、車線変更に伴うドライバの負担である車線変更用コストは、経験則上、上記各パラメータの変動に伴って変化するので、当該各パラメータの変動に対応したコスト設定が可能となるからである。
【０００９】
（４） 例えば、区間距離に関しては、前記コスト設定手段において、車線変更が可能な区間の距離が長いほど、車線変更が容易なので、前記車線変更用コストを小さく設定するようにすればよい。
（５） また、区間速度に関しては、前記コスト設定手段において、車線変更が可能な区間の速度が当該車線変更に適した速度範囲内の場合には、前記車線変更用コストを小さく設定するようにすればよい。
【００１０】
（６） 本発明のコンピュータプログラムは、本発明の経路探索装置が行う探索処理をコンピュータに実行させるためのコンピュータプログラムであって、当該経路探索装置と同様の作用効果を奏する。
（７） また、本発明の経路探索方法は、本発明の経路探索装置が行う探索方法であって、当該経路探索装置と同様の作用効果を奏する。
【００１１】
（８） 本発明の地図データベースは、出発地点から目的地点までの推奨経路をリンクコストに基づいて探索する経路探索処理に用いる地図データベースであって、複数車線の道路についてその車線ごとに設定された複数のリンクと、前記リンクとその終点に接続する前記リンクの組み合わせの数だけコスト値が設定され、その終点に接続する前記リンクへの移動が車線変更を伴う場合の前記コスト値が非ゼロ値になっている車線変更用コストと、を含むことを特徴とする。
【００１２】
本発明の地図データベースによれば、上記車線変更用コストが、リンクとその終点に接続するリンクの組み合わせの数だけリンクコストとしてのコスト値が設定されており、その終点に接続するリンクへの移動が車線変更を伴う場合のコスト値が非ゼロ値になっているので、当該地図データベースに設定されたリンクコストに基づいて、従前の経路探索ロジック（ダイクストラ法やポテンシャル法）による探索処理を実行すれば、車線変更の負担を軽減した推奨経路を探索することができる。
【００１３】
（９） 本発明の地図データベースにおいて、車線変更が可能な車線に対応するリンク（以下、「可能リンク」ということがある。）については、車両が、その可能リンクの下流の同一車線に対応するリンクと、その可能リンクの下流の異なる車線に対応するリンクのいずれにも向かう可能性があるので、これらのリンクの双方に接続する必要がある。
これに対して、車線変更が不可能な車線に対応するリンク（以下、「不可能リンク」ということがある。）については、そもそも車線変更ができないことから、車両が、その不可能リンクの下流の異なる車線に対応するリンクに向かう可能性がないので、このリンクに接続する必要がない。
【００１４】
そこで、本発明の地図データベースにおいて、車線変更が不可能な車線に対応する前記リンク（不可能リンク）については、当該リンクの下流の同一車線に対応する前記リンクにのみ接続されていることが好ましい。
かかる地図データベースによれば、不可能リンクがその下流の同一車線に対応するリンクにのみ接続されているので、不可能リンクをその下流の全リンクと接続する場合に比べて、リンクのネットワーク構造を簡素化できるという利点がある。
【００１５】
（１０） もっとも、本発明の地図データベースにおいて、不可能リンクについても、当該リンクの下流の同一車線に対応する第１のリンクと、当該リンクの下流の異なる車線に対応する１又は複数の第２のリンクとに接続することにしてもよい。
この場合、不可能リンクから第２のリンクに進入する車線変更用コストのコスト値を十分に大きい値に設定することにより、その第２のリンクに繋がる推奨経路が求まりにくくなるため、当該第２リンクへの車線変更を実質的に不可能にすることができる。
【００１６】
（１１） また、本発明の地図データベースは、センターラインがない双方向道路に対応する複数のリンクと、前記双方向道路に対応するリンクほど前記リンクコストとしてのコスト値が大きくなるように設定されたセンターライン用コストと、を更に含むものであってもよい。
この場合、上記センターライン用コストは、双方向道路に対応するリンクほどリンクコストとしてのコスト値が大きくなっているので、当該地図データベースに設定されたリンクコストに基づいて、従前の経路探索ロジック（ダイクストラ法やポテンシャル法）による探索処理を実行すれば、車線変更の負担だけでなく、片側１車線の双方向道路における走行負担を軽減した推奨経路を探索することができる。
【発明の効果】
【００１７】
以上の通り、本発明によれば、複数車線の区間に含まれるリンクに対して、車線変更を行うのに必要な車線変更用コストを設定し、設定された車線変更用コストをリンクコストに含めて推奨経路を探索するようにしたので、車線変更の負担を軽減した推奨経路を探索することができる。
【図面の簡単な説明】
【００１８】
【図１】ナビゲーションシステムの全体構成を示す概略構成図である。
【図２】ナビゲーションシステムの機能ブロック図である。
【図３】ナビゲーションシステムによる経路探索処理のフローチャートである。
【図４】複数車線の道路とリンクの対応関係を示す図であり、（ａ）は交差点手前の道路区間の平面図、（ｂ）はその道路区間に対応するリンクの接続図である。
【図５】（ａ）は区間距離と車両速度によって車線変更用コストを設定する場合の設定テーブルであり、（ｂ）は区間距離と渋滞度によって車線変更用コストを設定する場合の設定テーブルである。
【図６】車種によって車線変更用コストを設定する場合の設定テーブルである。
【図７】複数車線の区間に対応するリンクの接続構造の一例を示す接続図である。
【図８】複数車線の区間に対応するリンクの接続構造の別例を示す接続図である。
【発明を実施するための形態】
【００１９】
〔システムの全体構成〕
図１は、本発明の経路検索装置を有するナビゲーションシステムの全体構成を示す概略構成図であり、図２は、同システムの機能ブロック図である。
図１及び図２に示すように、本実施形態のナビゲーションシステム１は、サーバ装置２と、複数の車両３にそれぞれ搭載された車載装置４とから構成されている。
なお、本明細書において、「車両」とは、自動車、原動機付き自転車、軽車両及びトロリーバス等のことをいう。また、「車載装置」とは、車両に搭載されており、その搭乗者に対して目的地までの経路を案内するいわゆるナビゲーション装置のことをいう。
【００２０】
このナビゲーションシステム１は、予め入会登録された会員（ユーザ）の車両３自体をセンサとして、各車両３からサーバ装置２が情報収集し、メンバー間で相互に情報提供し合って運用することにより、サーバ装置２が各会員に対して有用な交通情報を提供するようにしたものである。
従って、本システム１によれば、通常のＶＩＣＳ（登録商標：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 ]