経路案内装置
【課題】新設された道路の利点を考慮した経路案内ができる経路案内装置を提供する。
【解決手段】経路案内装置１は、記憶部１１に記憶されている道路のリンクに関する情報の中に低減期間終了日等の情報を追加しておく。そして、経路探索処理においてリンクに関する情報が参照された場合は、その情報に基づいて当該リンクの移動コストを低減するための新設係数を算出し、その新設係数に基づいて移動コストを補正する。補正により新設された道路の移動コストが低減され、推奨経路に含められやすくなる。このように探索した推奨経路に基づいて経路案内を行うことにより、新設された道路の利点を考慮した経路案内ができる。
【解決手段】経路案内装置１は、記憶部１１に記憶されている道路のリンクに関する情報の中に低減期間終了日等の情報を追加しておく。そして、経路探索処理においてリンクに関する情報が参照された場合は、その情報に基づいて当該リンクの移動コストを低減するための新設係数を算出し、その新設係数に基づいて移動コストを補正する。補正により新設された道路の移動コストが低減され、推奨経路に含められやすくなる。このように探索した推奨経路に基づいて経路案内を行うことにより、新設された道路の利点を考慮した経路案内ができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路案内装置に関する。
【背景技術】
【０００２】
従来、地図データを差分更新する経路案内装置が知られている（たとえば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−２４９６２４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
新設された道路は、その存在の周知度が低いために交通量が少なかったり、表面の凹凸が少なかったりするため、車両の走行が円滑になされる。従来技術では、地図データが更新され、新設された道路が地図データに追加されたとしても、新設された道路の利点を十分に考慮した経路案内ができないおそれがあった。
【課題を解決するための手段】
【０００５】
本発明の経路案内装置は、道路の移動コストに関する情報を含む道路情報を記憶する道路情報記憶手段と、道路情報における各道路の移動コストのうち新設された道路の移動コストを低減するコスト低減手段と、目的地を特定する目的地特定手段と、道路情報における移動コストおよびコスト低減手段により低減された移動コストに基づいて、目的地に到達するまでの移動に要する移動コストが小さい経路を特定する経路特定手段と、経路特定手段により特定される経路に従って車両を案内する経路案内手段とを備えることを特徴とする。
【発明の効果】
【０００６】
新設された道路の利点を考慮した経路案内ができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態である経路案内装置の構成の一例である。
【図２】本発明の一実施形態において使用する道路の評価値について説明するための図である。
【図３】本発明が注目する新設された道路に関して説明するための図である。
【図４】本発明の一実施形態における地図データについて説明するための図である。
【図５】本発明の一実施形態である経路案内装置における経路探索処理の一例を示すフローチャートである。
【図６】本発明の一実施形態における経路探索処理について説明するための図である。
【図７】本発明の一実施形態における経路探索処理について説明するための図である。
【図８】本発明の一実施形態における経路探索処理について説明するための図である。
【図９】本発明の一実施形態における経路探索処理について説明するための図である。
【図１０】本発明の一実施形態における経路探索処理について説明するための図である。
【図１１】本発明の一実施形態における経路探索処理について説明するための図である。
【図１２】本発明の一実施形態における経路探索処理について説明するための図である。
【図１３】本発明の一実施形態における経路探索処理について説明するための図である。
【図１４】本発明の一実施形態における経路探索処理について説明するための図である。
【図１５】本発明の一実施形態における経路探索処理について説明するための図である。
【図１６】本発明の一実施形態における経路探索処理について説明するための図である。
【図１７】本発明の一実施形態における経路探索処理について説明するための図である。
【図１８】本発明の一実施形態における経路探索処理について説明するための図である。
【発明を実施するための形態】
【０００８】
本発明の一実施の形態による経路案内装置の構成について、図１を用いて説明する。図１の経路案内装置１は、制御部１０、記憶部１１、表示モニタ１２、スピーカ１３、ＧＰＳ受信部１４、ジャイロセンサ１５、および入力装置１６を備える。経路案内装置１は、車両と有線または無線で接続されており、車両の走行速度などの情報を取得することができる。経路案内装置１は、ブラケットや吸盤などにより車両などに固定してもよい。以降、経路案内装置１を搭載した車両のことを搭載車両と記載する。
【０００９】
図１の制御部１０は、経路案内装置１を動作させるための各種処理を実行するための部分であり、マイクロプロセッサ、各種周辺回路、ＲＡＭ、ＲＯＭなどによって構成される。制御部１０により実行される処理には、たとえば経路探索処理や、マップマッチング処理、経路案内処理などがある。これらの処理については、多くの手法が公知となっている。
【００１０】
制御部１０が実行する経路探索処理とは、予め設定された探索条件に基づいて、搭載車両の現在位置などの出発地から目的地までの推奨経路を探索するものである。目的地は、経路案内装置１の利用者が入力装置１６を介して入力すればよい。搭載車両の現在位置は、制御部１０がＧＰＳ受信部１４を利用して算出することにより特定できる。経路の探索は、記憶部１１に記憶されている地図データに基づいて実行される。なお、推奨経路を探索するとき、目的地だけでなく経由地を選択することとしてもよい。また、出発地は、搭載車両の現在位置だけでなくユーザが入力装置１６を介して入力したものを用いてもよい。
【００１１】
探索条件は、従来から様々なものが知られており、たとえば目的地に到達するまでに要する移動コストが最も少ない経路を探索するものなどがある。以降の説明では、経路探索処理の探索条件が移動コストの最も少ない経路を探索するものに設定されているものとする。
【００１２】
制御部１０が実行する経路案内処理とは、経路探索処理により探索された推奨経路に沿って運転手が搭載車両を運転できるように、表示モニタ１２やスピーカ１３などを利用して運転手に案内を行う処理である。制御部１０は、表示モニタ１２に搭載車両の位置を示す印を付した地図を表示し、スピーカ１３から音声案内を出力する。
【００１３】
図１の記憶部１１は、ハードディスクなどを含む記憶媒体の集まりであり、道路地図を表す地図データや、アイコン等の画像データ、音声データを含む各種データが記憶されている。記憶部１１に記憶されているデータは、必要に応じて制御部１０により記憶部１１から読み出され、制御部１０が実行する様々な処理や制御に利用される。
【００１４】
記憶部１１に記憶される地図データには、地図上の地点を表すノードに関する情報と、ノードが表す地点と地点の間を繋ぐ道路を表すリンクに関する情報とが含まれる。ノードに関する情報には、位置情報や地点名称に関する情報などが含まれる。リンクに関する情報には、リンクが表す道路の長さであるリンク長や、道路種別、車両の通行が許可されている方向などの情報が含まれる。これらの情報に基づいて経路探索処理や、マップマッチング処理、経路案内処理などが実行される。
【００１５】
各リンクを通過するのに要する移動コストは、リンクに関する情報に基づいて算出される。たとえば、各リンクのリンク長に図２に示す評価値を乗ずることにより算出することができる。図２の評価値表２０は、リンクの道路種別にそれぞれ対応するリンクの評価値を示したものである。たとえば、リンクの道路種別が「国道」の「本線」の場合は評価値「６０」であり、「一般道」の「本線」は評価値「１００」である。すなわち、一般道の本線は国道の本線とリンク長が同じであっても、移動コストは国道の本線の５／３倍となる。
【００１６】
制御部１０は、記憶部１１に新たなデータを記憶することや既に記憶されている地図データなどのデータを更新することができる。たとえば、新しく道路が作られた場合、新しいノードに関する情報やリンクに関する情報を地図データに追加することができる。地図データの更新方法には、ＨＤＤ１１に記憶している地図データと最新の地図データとの差分を更新する方法や、地図データファイルを置き換える方法などがある。地図データの更新に用いるデータは、ＤＶＤ（図示せず）やＵＳＢメモリ（図示せず）などの電子メディアから取得してもよいし、ナビゲーション装置１の外部からダウンロードすることにより取得してもよい。本実施の形態では、地図データの差分更新により新設された道路に関するノードやリンクの情報を地図データに追加する。追加した地図データの具体例については後述する。
【００１７】
図１の表示モニタ１２は、様々な画像や映像などを表示するための装置であり、液晶ディスプレイ等が用いられる。制御部１０の制御に基づいて表示モニタ１２に地図や搭載車両の現在位置を表示することにより、経路案内装置１は搭載車両を誘導する案内表示を行うことができる。
【００１８】
図１のスピーカ１３は、制御部１０の制御により、搭載車両の走行に関する様々な音声情報を出力する。たとえば、制御部１０により探索された経路に従って搭載車両を目的地まで案内するための案内用の音声や、警告音などを出力する。
【００１９】
図１のＧＰＳ受信部１４は、ＧＰＳ衛星から送信されるＧＰＳ信号を受信して制御部１０へ出力する。ＧＰＳ信号には、搭載車両の現在位置と現在日時を特定するための情報として、そのＧＰＳ信号を送信したＧＰＳ衛星の位置と送信時刻が含まれている。したがって、制御部１０は、所定数以上のＧＰＳ衛星からのＧＰＳ信号により、これらの情報に基づいて搭載車両の現在位置および現在日時を算出することができる。制御部１０は、ＧＰＳ信号に基づいて算出された搭載車両の現在位置の時間変化を算出し、その搭載車両の現在位置の時間変化に基づいて、搭載車両が走行している方向と走行した距離を特定することができる。
【００２０】
経路案内装置１の制御部１０は、記憶部１１に記憶された地図データや上記のようにして算出した搭載車両の現在位置が変化した軌跡などに基づいて、搭載車両がどの道路の上に存在するかを特定する。このような処理をマップマッチング処理という。
【００２１】
図１のジャイロセンサ１５は、搭載車両の向きの変化に応じた角速度を検出するためのセンサである。このジャイロセンサ１５により検出された角速度に基づいて、搭載車両の向きが求められ、搭載車両が走行している方向を特定できる。
【００２２】
搭載車両がトンネル内を走行しているときや、高架下にあるサービスエリア内にあるときなど、ＧＰＳ受信部１４がＧＰＳ信号を受信できない場合がある。制御部１０は、ジャイロセンサ１５により検出される角速度、搭載車両からハーネスや無線通信等を介して送信される搭載車両の走行速度、および記憶部１１に記憶される地図データに基づいて、搭載車両の現在位置および走行している方向に関する情報を特定することもできる。このようにして特定された搭載車両の現在位置の軌跡に基づいてもマップマッチング処理を実行することができる。ＧＰＳ信号に基づいたマップマッチング処理と、角速度や走行速度等に基づいたマップマッチング処理とは併用することができる。
【００２３】
図１の入力装置１６は、経路案内装置１を動作させるためにユーザから入力される各種操作を検出するための装置であり、各種の入力スイッチ類を有している。ユーザは、入力装置１６を操作することにより、たとえば、目的地に設定したい施設や地名等を入力したり、予め登録された登録地の中から目的地を選択したり、表示モニタ１２に表示された地図を任意の方向にスクロールしたりすることができる。入力装置１６は、操作パネルやリモコンなどによって実現することができる。あるいは、入力装置１６を表示モニタ１２と一体化されたタッチパネルとしてもよい。
【００２４】
本実施の形態では、前述の経路探索処理を行うとき、新設された道路の移動コストを従来よりも低くなるように補正する。新設された道路の移動コストの補正について図３を用いて説明する。
【００２５】
図３は、新設された道路を含む道路地図の一例である。図３では、出発地と目的地との間に三本の道路Ｒ１〜Ｒ３が存在する。道路Ｒ１は、出発地から目的地までの間を直接つなぐ道路であるが、新設された道路ではない。道路Ｒ２およびＲ３は、新しく整備された道路であって、道路Ｒ２、道路Ｒ３の順に通過することによって目的地に到達することができる。
【００２６】
図３では、出発地から目的地まで到達するまでの経路は、道路Ｒ１を通る経路と、道路Ｒ２およびＲ３を通る経路の二つが存在する。ダイクストラ法などに基づいた経路探索処理を実行すると、考えられる複数の経路の中から出発地から目的地までに通過する道路の移動コストの和が最小となるものが出力される。以降、出発地から経路上の各地点までに通過する道路の移動コストの総和を到達コストと記載し、推奨経路は到達コストが最小となる経路を指すこととする。
【００２７】
図３の道路Ｒ１〜Ｒ３のリンク長をそれぞれｌ１〜ｌ３とすると、各リンク長ｌ１〜ｌ３に基づいて道路Ｒ１〜Ｒ３の移動コストがそれぞれ算出される。たとえば、図３では、道路Ｒ１〜Ｒ３の移動コストとして、それぞれ５，２，４の値が求められている。従来の新設された道路の移動コストの補正を行わない方法では、道路Ｒ１を通る経路の到達コストは５、道路Ｒ２およびＲ３を通る経路の到達コストは６（＝２＋４）となる。したがって、従来の経路探索処理では、道路Ｒ１を通る経路が推奨経路として出力される。
【００２８】
一方、本実施の形態における経路探索処理では、新設された道路の移動コストを低減する補正を行う。たとえば、新設された道路Ｒ２およびＲ３にそれぞれ新設係数０．８を乗じる補正を行う。この場合、道路Ｒ２およびＲ３を通る経路の到達コストは４．８（＝２×０．８＋４×０．８）となり、道路Ｒ１を通る経路の到達コストである５よりも小さくなる。したがって、道路Ｒ２およびＲ３を通る経路が推奨経路として出力される。
【００２９】
本実施の形態では、新設された道路の移動コストに対して補正を行う。補正に用いる新設係数は、経験的に定められた定数であってもよいし、道路が作られてからの時間経過に伴って１に近づく変数としてもよい。
【００３０】
本実施の形態では、新設された道路であるか、すなわち補正の対象となる道路であるかは、地図データに基づいて判定する。その判定方法について図４を用いて説明する。図４（ａ）は、図３の道路地図をノードＮ１〜Ｎ３およびリンクＬ１〜Ｌ３を用いて表現したものである。リンクＬ１〜Ｌ３は、それぞれ道路Ｒ１〜Ｒ３を表している。ノードＮ１は、図３の出発地に対応している。ノードＮ３は、図３の目的地に対応している。ノードＮ２は、道路Ｒ２と道路Ｒ３とを接続する地点に対応している。
【００３１】
図４（ｂ）は、図４（ａ）のリンクＬ１〜Ｌ３に関する情報が記憶部１１に記憶されている様子を示している。図４（ｂ）の地図データ４０は、差分更新における地図データの更新分４２がオリジナルの地図データ４１とは区別して記憶されている。リンクＬ１のデータは、オリジナルの地図データ４１に記憶されているものとし、リンクＬ２およびＬ３の地図データは、地図データの更新分４２に記憶されているものとする。地図データの更新分４２に含まれるリンクに関する情報には、オリジナルの地図データ４１にも含まれる情報に加えて、「低減期間終了日」という情報４０１が追加される。
【００３２】
低減期間終了日４０１は、道路が新設された日付に基づいた情報であり、前述した新設された道路に対する補正を行う期間の終了日を表す。図４（ｂ）の例では、図３の道路Ｒ２およびＲ３をそれぞれ表す図４（ａ）のリンクＬ２およびＬ３に対しては２０ＸＸ年ＹＹ月ＺＺ日に補正を行う期間が終了することを表している。なお、補正に用いる新設係数を時間経過に伴って変化させる場合は、この低減期間終了日とＧＰＳ信号に基づいて算出した現在日時とに基づいて新設係数を算出すればよい。
【００３３】
低減期間終了日４０２に基づいた補正を行うか否かの判定は、各リンクの移動コストを参照するときに実行される。経路探索処理において、各リンクの移動コストが参照されるタイミングについて図５を用いて説明する。
【００３４】
図５は、ダイクストラ法に基づいた経路探索処理に対して、新設された道路の補正に関する処理を追加したフローチャートである。図５の経路探索処理は、出発地のノードと目的地のノードを入力とし、出発地から目的地までの推奨経路と到達コストを出力する。なお、以降の図５のフローチャートの説明では、説明を簡単にするため、出発地および目的地はノードの上にあるものとする。
【００３５】
図５のフローチャートの処理では、未確定集合と確定集合というノードの集合を用いる。確定集合とは、出発地からそのノードまでの到達コストと最短経路が確定したノードを要素とする集合である。未確定集合とは、出発地から目的地までの到達コストと最短経路とが確定するまでの処理において参照されたノードであって、確定集合に含まれないノードを要素とする集合である。なお、図５の処理が開始するとき、確定集合も未確定集合も空集合である。
【００３６】
経路探索処理においてノードが参照されると、参照されたノードはまず未確定集合の要素となる。制御部１０は、未確定集合の要素となったノードに対して、到達コストと先行ノードという二つの情報を生成する。生成された到達コストと先行ノードの値は、各ノードが未確定集合の要素である間は逐次更新され、確定集合の要素となったときに確定する。先行ノードとは、到達コストが記憶された時点での出発地から各ノードまでの最短経路において、各ノードに到達する一つ前のノードである。たとえば、図４（ａ）において、ノードＮ３の最短経路がノードＮ１，Ｎ２，Ｎ３の順に到達するものであった場合、ノードＮ３の先行ノードはノードＮ２であり、ノードＮ２の先行ノードはノードＮ１である。
【００３７】
ダイクストラ法に基づいた経路探索処理では、各ノードに対応した到達コストおよび最短経路は、出発地に近いノードから順番に確定する。未確定集合の要素であるノードについての到達コストおよび最短経路が確定したとき、そのノードは未確定集合から取り出され、確定集合の要素として記憶される。目的地のノードが確定集合の要素となったとき、先行ノードに基づいて目的地から出発地に向かって確定集合に含まれるノードを辿ることにより推奨経路が得られる。
【００３８】
地図データに含まれるノードからは１以上のリンクが延びており別のノードに接続されている。以降、ノードから延びるリンクに接続されている別のノードのことを隣接ノードと記載する。たとえば、図４（ａ）の場合、ノードＮ１からリンクＬ２およびＬ３が延びているため、ノードＮ１の隣接ノードはノードＮ２およびＮ３である。
【００３９】
図５のステップＳ１０１では、制御部１０は、出発地のノードを未確定集合の要素とする。このとき、出発地のノードの到達コストは０とし、先行ノードはＮＵＬＬ（空情報）とする。出発地のノードを未確定集合の要素とする処理が完了したら、図５の処理はステップＳ１０２に進む。
【００４０】
図５のステップＳ１０２では、制御部１０は、未確定集合が空集合か否かを判定する。図５の処理は、未確定集合が空集合の場合はステップＳ１５３に進み、そうでない場合はステップＳ１０３に進む。
【００４１】
図５のステップＳ１０３では、制御部１０は、未確定集合の中から到達コストが最も小さいノードである最小ノードを取り出す。取り出したノードは、未確定集合の中から削除し、削除が完了したらステップＳ１０４に進む。
【００４２】
図５のステップＳ１０４では、制御部１０は、ステップＳ１０３で最小ノードとして取り出したノードを確定集合に加える。最小ノードが確定集合の要素となったら図５の処理はステップＳ１０５に進む。
【００４３】
図５のステップＳ１０５では、制御部１０は、最小ノードが目的地か否かを判定する。図５の処理は、最小ノードが目的地である場合はステップＳ１５６に進み、そうでない場合はステップＳ１０６に進む。
【００４４】
図５のステップＳ１０６では、制御部１０は、最小ノードの隣接ノードの各々について逐次にステップＳ１０７０以降の処理を繰り返す。
【００４５】
図５のステップＳ１０７０では、制御部１０は、最小ノードと処理中の隣接ノードの間のリンクについて、地図データに基づいて低減期間終了日と移動コストを取得し、新設された道路の移動コストの補正に用いる新設係数を算出する。当該リンクがオリジナルの地図データ４１に含まれる場合は、低減期間終了日が取得できないため係数を１とする。係数の算出が完了したら、図５の処理はステップＳ１０８０に進む。
【００４６】
図５のステップＳ１０８０では、制御部１０は、処理中の隣接ノードが未確定集合の中に含まれるか否かを判定する。図５の処理は、当該隣接ノードが未確定集合に含まれる場合はステップＳ１０９０に進み、そうでない場合はステップＳ１０８１に進む。
【００４７】
図５のステップＳ１０８１では、制御部１０は、処理中の隣接ノードを未確定集合の要素に加える。このとき、処理中の隣接ノードの先行ノードはＮＵＬＬとし、その到達コストは到達コストとして設定し得る最大の値とする。当該隣接ノードを未確定集合に含めたら、図５の処理はステップＳ１０９０に進む。
【００４８】
図５のステップＳ１０９０では、制御部１０は、下記の判定式（１）を評価する。図５の処理は、判定式（１）が肯定判定されたら処理中の隣接ノードの到達コストを緩和するためにステップＳ１０９１に進む。一方、判定式（１）が否定判定された場合は、処理中の隣接ノードの処理を終了し、ステップＳ１０６に進み、次の隣接ノードの処理を開始する。最小ノードの隣接ノードすべてについて処理が終了した場合は、ステップＳ１０２に戻る。判定式（１）において、Ｃadjは処理中の隣接ノードの到達コスト、Ｃminは最小ノードの到達コスト、ｌadjは最小ノードと当該隣接ノードとの間のリンクの移動コストである。
【００４９】
【数１】
―――（１）
【００５０】
図５のステップＳ１０９１では、制御部１０は、処理中の隣接ノードの到達コストをＣmin＋ｌadjに更新する。処理中の隣接ノードの到達コストを変更したら、図５の処理はステップＳ１０９２に進む。
【００５１】
図５のステップＳ１０９２では、制御部１０は、処理中の隣接ノードの先行ノードを最小ノードに更新する。処理中の隣接ノードの先行ノードを更新したら、処理中の隣接ノードの処理を終了し、ステップＳ１０６に進み、次の隣接ノードの処理を開始する。全ての隣接ノードについて処理が終了したらステップＳ１０２に戻る。
【００５２】
図５の処理がステップＳ１５３に到った場合、制御部１０は、目的地までの経路が存在しない、すなわち推奨経路を出力できないと判断する。図５の処理がステップＳ１５３に到った場合、制御部１０は、図５の処理を終了させる。なお、ステップＳ１５３において制御部１０は、図５の処理を終了させる前に表示モニタ１２などを介して目的地に到達する経路がないことをユーザに報知することが望ましい。
【００５３】
図５のステップＳ１５６では、制御部１０は、先行ノードに基づいて推奨経路を出力し、図５の処理を終了する。
【００５４】
図５のフローチャートの処理の具体例として、図４（ａ）の地図データに対して処理を適用した場合について図６〜図１８を用いて説明する。
【００５５】
図５のステップＳ１０１では、制御部１０は、出発地のノードＮ１を未確定集合の要素とする。ノードＮ１の到達コストおよび先行ノードは、それぞれ０およびＮＵＬＬとする。ステップＳ１０１が終了した時点の各データの状況を図６に図示する。
【００５６】
出発地が未確定集合に含まれているため、ステップＳ１０２は否定判定され、図５の処理はステップＳ１０３に進む。ステップＳ１０３では、制御部１０は、未確定集合の中から最小ノードとしてノードＮ１を取り出す。ステップＳ１０４では、制御部１０は、ノードＮ１を確定集合の要素にする。ステップＳ１０４が終了した時点の各データの状況を図７に図示する。
【００５７】
ノードＮ１は目的地ではないため、ステップＳ１０５は否定判定され、ステップＳ１０６に進む。最小ノードであるノードＮ１からはリンクＬ１およびＬ２がノードＮ３およびＮ２に向かって延びている。すなわち、ノードＮ１の隣接ノードはノードＮ２およびＮ３である。ステップＳ１０６の処理が開始した時点の各データの状況を図８に示す。
【００５８】
ステップＳ１０６では、たとえばノードＮ２が選択されてステップＳ１０７０以降の処理を開始する。最小ノードＮ１とその隣接ノードＮ２の間のリンクＬ２の低減期間終了日は、図４（ｂ）にあるように２０ＸＸ年ＹＹ月ＺＺ日である。図５のステップＳ１０７０では現在時刻が２０ＸＸ年ＹＹ月ＺＺ日より前、すなわち低減期間が終了する前であれば、リンクＬ２は補正の対象となる新設された道路であるので、リンクＬ２に対する新設係数はたとえば０．８と決定される。
【００５９】
ステップＳ１０８０では、処理中の接続ノードＮ２が未確定集合に含まれていないため否定判定され、ステップ１０８１に進む。ステップＳ１０８１では、処理中の隣接ノードＮ２を未確定集合の要素にする。このとき、処理中の隣接ノードＮ２の到達コストは取りうる最大の値（ここでは仮に∞とする）とし、先行ノードはＮＵＬＬとする。
【００６０】
経路探索処理は、ステップＳ１０９０に移り、処理中の隣接ノードＮ２について判定式（１）を評価する。処理中の隣接ノードＮ２に関しては∞＞０＋２×０．８であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０の処理が終了した時点の各データの状況を図９に示す。
【００６１】
ステップＳ１０９１では、処理中の隣接ノードＮ２の到達コストを１．６（＝０＋２×０．８）に変更する。ステップＳ１０９２では、処理中の隣接ノードＮ２の先行ノードをノードＮ１に変更する。これにより最小ノードＮ１の隣接ノードのうち、ノードＮ２に関する処理を終了する。ステップＳ１０９２の処理が終了した時点の各データの状況を図１０に示す。
【００６２】
最小ノードＮ１の隣接ノードは、Ｎ２のほかにＮ３があるため、ノードＮ３の処理を開始する。ステップＳ１０７０（２回目）では、最小ノードＮ１とその隣接ノードＮ３の間のリンクＬ１は、新設された道路ではないため、補正に用いる係数を１とする。
【００６３】
ステップＳ１０８０（２回目）では、処理中の接続ノードＮ３が未確定集合に含まれていないため否定判定され、ステップ１０８１に進む。ステップＳ１０８１（２回目）では、処理中の隣接ノードＮ３を未確定集合の要素にする。このとき、処理中の隣接ノードＮ３の到達コストは取りうる最大の値とし、先行ノードはＮＵＬＬとする。
【００６４】
ステップＳ１０９０（２回目）では、処理中の隣接ノードＮ３について判定式（１）を評価する。処理中の隣接ノードＮ３に関しては∞＞０＋５×１であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０（２回目）の処理が終了した時点の各データの状況を図１１に示す。
【００６５】
ステップＳ１０９１（２回目）では、処理中の隣接ノードＮ３の到達コストを５（＝０＋５×１）に変更する。ステップＳ１０９２（２回目）では、処理中の隣接ノードＮ３の先行ノードをノードＮ１に変更する。ステップＳ１０９２（２回目）終了した時点の各データの状況を図１２に示す。
【００６６】
最小ノードＮ１の隣接ノードＮ２およびＮ３に関する処理が共に終了したので、ステップＳ１０２に戻る。ノードＮ２およびＮ３が未確定集合に含まれているため、ステップＳ１０２（２回目）は否定判定され、ステップＳ１０３に進む。ステップＳ１０３（２回目）では、ノードＮ２の到達コスト１．６がノードＮ３の到達コスト５よりも小さいため、制御部１０は未確定集合の中から最小ノードとしてノードＮ２を取り出す。ステップＳ１０４（２回目）では、制御部１０はノードＮ２を確定集合の要素にする。ステップＳ１０４（２回目）終了した時点の各データの状況を図１３に示す。
【００６７】
ノードＮ２は目的地ではないため、ステップＳ１０５では否定判定され、ステップＳ１０６に進む。最小ノードであるノードＮ２からはリンクＬ３がノードＮ３に向かって延びている。すなわち、ノードＮ２の隣接ノードはノードＮ３である。ステップＳ１０６では、隣接ノードとしてノードＮ３が選択されてステップＳ１０７０以降の処理を開始する。ステップＳ１０６の処理を開始した時点の各データの状況を図１４に示す。
【００６８】
リンクＬ３の低減期間終了日は、図４（ｂ）にあるように２０ＸＸ年ＹＹ月ＺＺ日である。ステップＳ１０７０（３回目）では、リンクＬ２と同様にリンクＬ３が補正の対象となる新設された道路と判断され、リンクＬ３に対する係数はたとえば０．８と決定される。
【００６９】
ステップＳ１０８０（３回目）では、処理中の接続ノードＮ３が未確定集合に含まれているため肯定判定され、ステップ１０９０に進む。
【００７０】
ステップＳ１０９０（３回目）では、処理中の隣接ノードＮ３について判定式（１）を評価する。処理中の隣接ノードＮ３に関しては５＞１．６＋４×０．８であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０（３回目）終了時点の各データの状況を図１５に示す。
【００７１】
ステップＳ１０９１（３回目）では、処理中の隣接ノードＮ３の到達コストを４．８（＝１．６＋４×０．８）に変更する。ステップＳ１０９２（３回目）では、処理中の隣接ノードＮ３の先行ノードをノードＮ２に変更する。これにより最小ノードＮ２の隣接ノードに関する処理が終了したので、ステップＳ１０２に戻る。ステップＳ１０９２（３回目）終了時点の各データの状況を図１６に示す。
【００７２】
ノードＮ３が未確定集合に含まれているため、ステップＳ１０２（３回目）は否定判定され、ステップＳ１０３に進む。ステップＳ１０３（３回目）では、制御部１０は未確定集合の中から最小ノードとしてノードＮ３を取り出す。ステップＳ１０４（３回目）では、制御部１０はノードＮ３を確定集合の要素にする。ステップＳ１０４（３回目）終了時点の各データの状況を図１７に示す。
【００７３】
ノードＮ３は目的地であるため、ステップＳ１０５では肯定判定され、ステップＳ１５６に進む。ステップＳ１５６では、図１８のように、目的地のノードＮ３から出発地のノードＮ１まで先行ノードを辿り、その結果に基づいてノードＮ１，ノードＮ２，ノードＮ３という推奨経路を出力する。
【００７４】
以上で説明した実施形態によれば、次の作用効果を奏する。
【００７５】
本実施の形態の経路案内装置１の記憶部１１には、道路の移動コストに関する情報と新設された道路の移動コストを補正する期間である低減期間終了日とが含まれる地図データが記憶されている（図４（ｂ））。そして、新設された道路に設定された低減期間終了日よりも現在時刻が前である場合は、新設された道路の移動コストを低減する補正を行い（図５のステップＳ１０７０）、ユーザが入力装置１２を介して特定した目的地に到達するまでの移動コストが少ない経路を特定する（図５）。そして、特定された推奨経路に基づいて経路案内を行う。これにより、新設された道路の利点を考慮した経路案内ができる。
【００７６】
以上で説明した実施形態は、以下のように変形して実施できる。
【００７７】
（１）本実施の形態では、低減期間終了日に関する情報を地図データの更新分４２だけに含めているが、オリジナルの地図データ４１にも含めてよい。また、地図データの更新分４２の更新日を記憶しておき、その更新日に基づいて低減期間終了日を定めてもよい。
【００７８】
（２）本実施の形態では、移動コストの算出にリンク長を使用したが、他の情報に基づいて移動コストを算出してもよい。たとえば、旅行時間に基づいて算出してもよい。
【００７９】
（３）本実施の形態では、移動コストをリンク長と評価値の乗算により算出したが、乗算結果を予め地図データに記憶してもよい。
【００８０】
（４）本実施の形態では、経路探索処理の一例としてダイクストラ法を基にした処理を提示したが、リンクに関する情報に基づいた移動コストが最も小さくなる経路を出力できるものであればこれに限定するものではない。たとえば、ベルマン・フォード法に基づいた処理でもよい。
【００８１】
以上で説明した各実施の形態や各種の変形例はあくまで一例であり、発明の特徴が損なわれない限り、本発明はこれらの内容に限定されない。
【符号の説明】
【００８２】
１ 経路案内装置
１０ 制御部
１１ 記憶部
１２ 表示モニタ
１３ スピーカ
１４ ＧＰＳ受信部
１５ ジャイロセンサ
１６ 入力装置
２０ 評価値表
４０ 地図データ
４０１ 低減期間終了日
【技術分野】
【０００１】
本発明は、経路案内装置に関する。
【背景技術】
【０００２】
従来、地図データを差分更新する経路案内装置が知られている（たとえば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−２４９６２４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
新設された道路は、その存在の周知度が低いために交通量が少なかったり、表面の凹凸が少なかったりするため、車両の走行が円滑になされる。従来技術では、地図データが更新され、新設された道路が地図データに追加されたとしても、新設された道路の利点を十分に考慮した経路案内ができないおそれがあった。
【課題を解決するための手段】
【０００５】
本発明の経路案内装置は、道路の移動コストに関する情報を含む道路情報を記憶する道路情報記憶手段と、道路情報における各道路の移動コストのうち新設された道路の移動コストを低減するコスト低減手段と、目的地を特定する目的地特定手段と、道路情報における移動コストおよびコスト低減手段により低減された移動コストに基づいて、目的地に到達するまでの移動に要する移動コストが小さい経路を特定する経路特定手段と、経路特定手段により特定される経路に従って車両を案内する経路案内手段とを備えることを特徴とする。
【発明の効果】
【０００６】
新設された道路の利点を考慮した経路案内ができる。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態である経路案内装置の構成の一例である。
【図２】本発明の一実施形態において使用する道路の評価値について説明するための図である。
【図３】本発明が注目する新設された道路に関して説明するための図である。
【図４】本発明の一実施形態における地図データについて説明するための図である。
【図５】本発明の一実施形態である経路案内装置における経路探索処理の一例を示すフローチャートである。
【図６】本発明の一実施形態における経路探索処理について説明するための図である。
【図７】本発明の一実施形態における経路探索処理について説明するための図である。
【図８】本発明の一実施形態における経路探索処理について説明するための図である。
【図９】本発明の一実施形態における経路探索処理について説明するための図である。
【図１０】本発明の一実施形態における経路探索処理について説明するための図である。
【図１１】本発明の一実施形態における経路探索処理について説明するための図である。
【図１２】本発明の一実施形態における経路探索処理について説明するための図である。
【図１３】本発明の一実施形態における経路探索処理について説明するための図である。
【図１４】本発明の一実施形態における経路探索処理について説明するための図である。
【図１５】本発明の一実施形態における経路探索処理について説明するための図である。
【図１６】本発明の一実施形態における経路探索処理について説明するための図である。
【図１７】本発明の一実施形態における経路探索処理について説明するための図である。
【図１８】本発明の一実施形態における経路探索処理について説明するための図である。
【発明を実施するための形態】
【０００８】
本発明の一実施の形態による経路案内装置の構成について、図１を用いて説明する。図１の経路案内装置１は、制御部１０、記憶部１１、表示モニタ１２、スピーカ１３、ＧＰＳ受信部１４、ジャイロセンサ１５、および入力装置１６を備える。経路案内装置１は、車両と有線または無線で接続されており、車両の走行速度などの情報を取得することができる。経路案内装置１は、ブラケットや吸盤などにより車両などに固定してもよい。以降、経路案内装置１を搭載した車両のことを搭載車両と記載する。
【０００９】
図１の制御部１０は、経路案内装置１を動作させるための各種処理を実行するための部分であり、マイクロプロセッサ、各種周辺回路、ＲＡＭ、ＲＯＭなどによって構成される。制御部１０により実行される処理には、たとえば経路探索処理や、マップマッチング処理、経路案内処理などがある。これらの処理については、多くの手法が公知となっている。
【００１０】
制御部１０が実行する経路探索処理とは、予め設定された探索条件に基づいて、搭載車両の現在位置などの出発地から目的地までの推奨経路を探索するものである。目的地は、経路案内装置１の利用者が入力装置１６を介して入力すればよい。搭載車両の現在位置は、制御部１０がＧＰＳ受信部１４を利用して算出することにより特定できる。経路の探索は、記憶部１１に記憶されている地図データに基づいて実行される。なお、推奨経路を探索するとき、目的地だけでなく経由地を選択することとしてもよい。また、出発地は、搭載車両の現在位置だけでなくユーザが入力装置１６を介して入力したものを用いてもよい。
【００１１】
探索条件は、従来から様々なものが知られており、たとえば目的地に到達するまでに要する移動コストが最も少ない経路を探索するものなどがある。以降の説明では、経路探索処理の探索条件が移動コストの最も少ない経路を探索するものに設定されているものとする。
【００１２】
制御部１０が実行する経路案内処理とは、経路探索処理により探索された推奨経路に沿って運転手が搭載車両を運転できるように、表示モニタ１２やスピーカ１３などを利用して運転手に案内を行う処理である。制御部１０は、表示モニタ１２に搭載車両の位置を示す印を付した地図を表示し、スピーカ１３から音声案内を出力する。
【００１３】
図１の記憶部１１は、ハードディスクなどを含む記憶媒体の集まりであり、道路地図を表す地図データや、アイコン等の画像データ、音声データを含む各種データが記憶されている。記憶部１１に記憶されているデータは、必要に応じて制御部１０により記憶部１１から読み出され、制御部１０が実行する様々な処理や制御に利用される。
【００１４】
記憶部１１に記憶される地図データには、地図上の地点を表すノードに関する情報と、ノードが表す地点と地点の間を繋ぐ道路を表すリンクに関する情報とが含まれる。ノードに関する情報には、位置情報や地点名称に関する情報などが含まれる。リンクに関する情報には、リンクが表す道路の長さであるリンク長や、道路種別、車両の通行が許可されている方向などの情報が含まれる。これらの情報に基づいて経路探索処理や、マップマッチング処理、経路案内処理などが実行される。
【００１５】
各リンクを通過するのに要する移動コストは、リンクに関する情報に基づいて算出される。たとえば、各リンクのリンク長に図２に示す評価値を乗ずることにより算出することができる。図２の評価値表２０は、リンクの道路種別にそれぞれ対応するリンクの評価値を示したものである。たとえば、リンクの道路種別が「国道」の「本線」の場合は評価値「６０」であり、「一般道」の「本線」は評価値「１００」である。すなわち、一般道の本線は国道の本線とリンク長が同じであっても、移動コストは国道の本線の５／３倍となる。
【００１６】
制御部１０は、記憶部１１に新たなデータを記憶することや既に記憶されている地図データなどのデータを更新することができる。たとえば、新しく道路が作られた場合、新しいノードに関する情報やリンクに関する情報を地図データに追加することができる。地図データの更新方法には、ＨＤＤ１１に記憶している地図データと最新の地図データとの差分を更新する方法や、地図データファイルを置き換える方法などがある。地図データの更新に用いるデータは、ＤＶＤ（図示せず）やＵＳＢメモリ（図示せず）などの電子メディアから取得してもよいし、ナビゲーション装置１の外部からダウンロードすることにより取得してもよい。本実施の形態では、地図データの差分更新により新設された道路に関するノードやリンクの情報を地図データに追加する。追加した地図データの具体例については後述する。
【００１７】
図１の表示モニタ１２は、様々な画像や映像などを表示するための装置であり、液晶ディスプレイ等が用いられる。制御部１０の制御に基づいて表示モニタ１２に地図や搭載車両の現在位置を表示することにより、経路案内装置１は搭載車両を誘導する案内表示を行うことができる。
【００１８】
図１のスピーカ１３は、制御部１０の制御により、搭載車両の走行に関する様々な音声情報を出力する。たとえば、制御部１０により探索された経路に従って搭載車両を目的地まで案内するための案内用の音声や、警告音などを出力する。
【００１９】
図１のＧＰＳ受信部１４は、ＧＰＳ衛星から送信されるＧＰＳ信号を受信して制御部１０へ出力する。ＧＰＳ信号には、搭載車両の現在位置と現在日時を特定するための情報として、そのＧＰＳ信号を送信したＧＰＳ衛星の位置と送信時刻が含まれている。したがって、制御部１０は、所定数以上のＧＰＳ衛星からのＧＰＳ信号により、これらの情報に基づいて搭載車両の現在位置および現在日時を算出することができる。制御部１０は、ＧＰＳ信号に基づいて算出された搭載車両の現在位置の時間変化を算出し、その搭載車両の現在位置の時間変化に基づいて、搭載車両が走行している方向と走行した距離を特定することができる。
【００２０】
経路案内装置１の制御部１０は、記憶部１１に記憶された地図データや上記のようにして算出した搭載車両の現在位置が変化した軌跡などに基づいて、搭載車両がどの道路の上に存在するかを特定する。このような処理をマップマッチング処理という。
【００２１】
図１のジャイロセンサ１５は、搭載車両の向きの変化に応じた角速度を検出するためのセンサである。このジャイロセンサ１５により検出された角速度に基づいて、搭載車両の向きが求められ、搭載車両が走行している方向を特定できる。
【００２２】
搭載車両がトンネル内を走行しているときや、高架下にあるサービスエリア内にあるときなど、ＧＰＳ受信部１４がＧＰＳ信号を受信できない場合がある。制御部１０は、ジャイロセンサ１５により検出される角速度、搭載車両からハーネスや無線通信等を介して送信される搭載車両の走行速度、および記憶部１１に記憶される地図データに基づいて、搭載車両の現在位置および走行している方向に関する情報を特定することもできる。このようにして特定された搭載車両の現在位置の軌跡に基づいてもマップマッチング処理を実行することができる。ＧＰＳ信号に基づいたマップマッチング処理と、角速度や走行速度等に基づいたマップマッチング処理とは併用することができる。
【００２３】
図１の入力装置１６は、経路案内装置１を動作させるためにユーザから入力される各種操作を検出するための装置であり、各種の入力スイッチ類を有している。ユーザは、入力装置１６を操作することにより、たとえば、目的地に設定したい施設や地名等を入力したり、予め登録された登録地の中から目的地を選択したり、表示モニタ１２に表示された地図を任意の方向にスクロールしたりすることができる。入力装置１６は、操作パネルやリモコンなどによって実現することができる。あるいは、入力装置１６を表示モニタ１２と一体化されたタッチパネルとしてもよい。
【００２４】
本実施の形態では、前述の経路探索処理を行うとき、新設された道路の移動コストを従来よりも低くなるように補正する。新設された道路の移動コストの補正について図３を用いて説明する。
【００２５】
図３は、新設された道路を含む道路地図の一例である。図３では、出発地と目的地との間に三本の道路Ｒ１〜Ｒ３が存在する。道路Ｒ１は、出発地から目的地までの間を直接つなぐ道路であるが、新設された道路ではない。道路Ｒ２およびＲ３は、新しく整備された道路であって、道路Ｒ２、道路Ｒ３の順に通過することによって目的地に到達することができる。
【００２６】
図３では、出発地から目的地まで到達するまでの経路は、道路Ｒ１を通る経路と、道路Ｒ２およびＲ３を通る経路の二つが存在する。ダイクストラ法などに基づいた経路探索処理を実行すると、考えられる複数の経路の中から出発地から目的地までに通過する道路の移動コストの和が最小となるものが出力される。以降、出発地から経路上の各地点までに通過する道路の移動コストの総和を到達コストと記載し、推奨経路は到達コストが最小となる経路を指すこととする。
【００２７】
図３の道路Ｒ１〜Ｒ３のリンク長をそれぞれｌ１〜ｌ３とすると、各リンク長ｌ１〜ｌ３に基づいて道路Ｒ１〜Ｒ３の移動コストがそれぞれ算出される。たとえば、図３では、道路Ｒ１〜Ｒ３の移動コストとして、それぞれ５，２，４の値が求められている。従来の新設された道路の移動コストの補正を行わない方法では、道路Ｒ１を通る経路の到達コストは５、道路Ｒ２およびＲ３を通る経路の到達コストは６（＝２＋４）となる。したがって、従来の経路探索処理では、道路Ｒ１を通る経路が推奨経路として出力される。
【００２８】
一方、本実施の形態における経路探索処理では、新設された道路の移動コストを低減する補正を行う。たとえば、新設された道路Ｒ２およびＲ３にそれぞれ新設係数０．８を乗じる補正を行う。この場合、道路Ｒ２およびＲ３を通る経路の到達コストは４．８（＝２×０．８＋４×０．８）となり、道路Ｒ１を通る経路の到達コストである５よりも小さくなる。したがって、道路Ｒ２およびＲ３を通る経路が推奨経路として出力される。
【００２９】
本実施の形態では、新設された道路の移動コストに対して補正を行う。補正に用いる新設係数は、経験的に定められた定数であってもよいし、道路が作られてからの時間経過に伴って１に近づく変数としてもよい。
【００３０】
本実施の形態では、新設された道路であるか、すなわち補正の対象となる道路であるかは、地図データに基づいて判定する。その判定方法について図４を用いて説明する。図４（ａ）は、図３の道路地図をノードＮ１〜Ｎ３およびリンクＬ１〜Ｌ３を用いて表現したものである。リンクＬ１〜Ｌ３は、それぞれ道路Ｒ１〜Ｒ３を表している。ノードＮ１は、図３の出発地に対応している。ノードＮ３は、図３の目的地に対応している。ノードＮ２は、道路Ｒ２と道路Ｒ３とを接続する地点に対応している。
【００３１】
図４（ｂ）は、図４（ａ）のリンクＬ１〜Ｌ３に関する情報が記憶部１１に記憶されている様子を示している。図４（ｂ）の地図データ４０は、差分更新における地図データの更新分４２がオリジナルの地図データ４１とは区別して記憶されている。リンクＬ１のデータは、オリジナルの地図データ４１に記憶されているものとし、リンクＬ２およびＬ３の地図データは、地図データの更新分４２に記憶されているものとする。地図データの更新分４２に含まれるリンクに関する情報には、オリジナルの地図データ４１にも含まれる情報に加えて、「低減期間終了日」という情報４０１が追加される。
【００３２】
低減期間終了日４０１は、道路が新設された日付に基づいた情報であり、前述した新設された道路に対する補正を行う期間の終了日を表す。図４（ｂ）の例では、図３の道路Ｒ２およびＲ３をそれぞれ表す図４（ａ）のリンクＬ２およびＬ３に対しては２０ＸＸ年ＹＹ月ＺＺ日に補正を行う期間が終了することを表している。なお、補正に用いる新設係数を時間経過に伴って変化させる場合は、この低減期間終了日とＧＰＳ信号に基づいて算出した現在日時とに基づいて新設係数を算出すればよい。
【００３３】
低減期間終了日４０２に基づいた補正を行うか否かの判定は、各リンクの移動コストを参照するときに実行される。経路探索処理において、各リンクの移動コストが参照されるタイミングについて図５を用いて説明する。
【００３４】
図５は、ダイクストラ法に基づいた経路探索処理に対して、新設された道路の補正に関する処理を追加したフローチャートである。図５の経路探索処理は、出発地のノードと目的地のノードを入力とし、出発地から目的地までの推奨経路と到達コストを出力する。なお、以降の図５のフローチャートの説明では、説明を簡単にするため、出発地および目的地はノードの上にあるものとする。
【００３５】
図５のフローチャートの処理では、未確定集合と確定集合というノードの集合を用いる。確定集合とは、出発地からそのノードまでの到達コストと最短経路が確定したノードを要素とする集合である。未確定集合とは、出発地から目的地までの到達コストと最短経路とが確定するまでの処理において参照されたノードであって、確定集合に含まれないノードを要素とする集合である。なお、図５の処理が開始するとき、確定集合も未確定集合も空集合である。
【００３６】
経路探索処理においてノードが参照されると、参照されたノードはまず未確定集合の要素となる。制御部１０は、未確定集合の要素となったノードに対して、到達コストと先行ノードという二つの情報を生成する。生成された到達コストと先行ノードの値は、各ノードが未確定集合の要素である間は逐次更新され、確定集合の要素となったときに確定する。先行ノードとは、到達コストが記憶された時点での出発地から各ノードまでの最短経路において、各ノードに到達する一つ前のノードである。たとえば、図４（ａ）において、ノードＮ３の最短経路がノードＮ１，Ｎ２，Ｎ３の順に到達するものであった場合、ノードＮ３の先行ノードはノードＮ２であり、ノードＮ２の先行ノードはノードＮ１である。
【００３７】
ダイクストラ法に基づいた経路探索処理では、各ノードに対応した到達コストおよび最短経路は、出発地に近いノードから順番に確定する。未確定集合の要素であるノードについての到達コストおよび最短経路が確定したとき、そのノードは未確定集合から取り出され、確定集合の要素として記憶される。目的地のノードが確定集合の要素となったとき、先行ノードに基づいて目的地から出発地に向かって確定集合に含まれるノードを辿ることにより推奨経路が得られる。
【００３８】
地図データに含まれるノードからは１以上のリンクが延びており別のノードに接続されている。以降、ノードから延びるリンクに接続されている別のノードのことを隣接ノードと記載する。たとえば、図４（ａ）の場合、ノードＮ１からリンクＬ２およびＬ３が延びているため、ノードＮ１の隣接ノードはノードＮ２およびＮ３である。
【００３９】
図５のステップＳ１０１では、制御部１０は、出発地のノードを未確定集合の要素とする。このとき、出発地のノードの到達コストは０とし、先行ノードはＮＵＬＬ（空情報）とする。出発地のノードを未確定集合の要素とする処理が完了したら、図５の処理はステップＳ１０２に進む。
【００４０】
図５のステップＳ１０２では、制御部１０は、未確定集合が空集合か否かを判定する。図５の処理は、未確定集合が空集合の場合はステップＳ１５３に進み、そうでない場合はステップＳ１０３に進む。
【００４１】
図５のステップＳ１０３では、制御部１０は、未確定集合の中から到達コストが最も小さいノードである最小ノードを取り出す。取り出したノードは、未確定集合の中から削除し、削除が完了したらステップＳ１０４に進む。
【００４２】
図５のステップＳ１０４では、制御部１０は、ステップＳ１０３で最小ノードとして取り出したノードを確定集合に加える。最小ノードが確定集合の要素となったら図５の処理はステップＳ１０５に進む。
【００４３】
図５のステップＳ１０５では、制御部１０は、最小ノードが目的地か否かを判定する。図５の処理は、最小ノードが目的地である場合はステップＳ１５６に進み、そうでない場合はステップＳ１０６に進む。
【００４４】
図５のステップＳ１０６では、制御部１０は、最小ノードの隣接ノードの各々について逐次にステップＳ１０７０以降の処理を繰り返す。
【００４５】
図５のステップＳ１０７０では、制御部１０は、最小ノードと処理中の隣接ノードの間のリンクについて、地図データに基づいて低減期間終了日と移動コストを取得し、新設された道路の移動コストの補正に用いる新設係数を算出する。当該リンクがオリジナルの地図データ４１に含まれる場合は、低減期間終了日が取得できないため係数を１とする。係数の算出が完了したら、図５の処理はステップＳ１０８０に進む。
【００４６】
図５のステップＳ１０８０では、制御部１０は、処理中の隣接ノードが未確定集合の中に含まれるか否かを判定する。図５の処理は、当該隣接ノードが未確定集合に含まれる場合はステップＳ１０９０に進み、そうでない場合はステップＳ１０８１に進む。
【００４７】
図５のステップＳ１０８１では、制御部１０は、処理中の隣接ノードを未確定集合の要素に加える。このとき、処理中の隣接ノードの先行ノードはＮＵＬＬとし、その到達コストは到達コストとして設定し得る最大の値とする。当該隣接ノードを未確定集合に含めたら、図５の処理はステップＳ１０９０に進む。
【００４８】
図５のステップＳ１０９０では、制御部１０は、下記の判定式（１）を評価する。図５の処理は、判定式（１）が肯定判定されたら処理中の隣接ノードの到達コストを緩和するためにステップＳ１０９１に進む。一方、判定式（１）が否定判定された場合は、処理中の隣接ノードの処理を終了し、ステップＳ１０６に進み、次の隣接ノードの処理を開始する。最小ノードの隣接ノードすべてについて処理が終了した場合は、ステップＳ１０２に戻る。判定式（１）において、Ｃadjは処理中の隣接ノードの到達コスト、Ｃminは最小ノードの到達コスト、ｌadjは最小ノードと当該隣接ノードとの間のリンクの移動コストである。
【００４９】
【数１】
―――（１）
【００５０】
図５のステップＳ１０９１では、制御部１０は、処理中の隣接ノードの到達コストをＣmin＋ｌadjに更新する。処理中の隣接ノードの到達コストを変更したら、図５の処理はステップＳ１０９２に進む。
【００５１】
図５のステップＳ１０９２では、制御部１０は、処理中の隣接ノードの先行ノードを最小ノードに更新する。処理中の隣接ノードの先行ノードを更新したら、処理中の隣接ノードの処理を終了し、ステップＳ１０６に進み、次の隣接ノードの処理を開始する。全ての隣接ノードについて処理が終了したらステップＳ１０２に戻る。
【００５２】
図５の処理がステップＳ１５３に到った場合、制御部１０は、目的地までの経路が存在しない、すなわち推奨経路を出力できないと判断する。図５の処理がステップＳ１５３に到った場合、制御部１０は、図５の処理を終了させる。なお、ステップＳ１５３において制御部１０は、図５の処理を終了させる前に表示モニタ１２などを介して目的地に到達する経路がないことをユーザに報知することが望ましい。
【００５３】
図５のステップＳ１５６では、制御部１０は、先行ノードに基づいて推奨経路を出力し、図５の処理を終了する。
【００５４】
図５のフローチャートの処理の具体例として、図４（ａ）の地図データに対して処理を適用した場合について図６〜図１８を用いて説明する。
【００５５】
図５のステップＳ１０１では、制御部１０は、出発地のノードＮ１を未確定集合の要素とする。ノードＮ１の到達コストおよび先行ノードは、それぞれ０およびＮＵＬＬとする。ステップＳ１０１が終了した時点の各データの状況を図６に図示する。
【００５６】
出発地が未確定集合に含まれているため、ステップＳ１０２は否定判定され、図５の処理はステップＳ１０３に進む。ステップＳ１０３では、制御部１０は、未確定集合の中から最小ノードとしてノードＮ１を取り出す。ステップＳ１０４では、制御部１０は、ノードＮ１を確定集合の要素にする。ステップＳ１０４が終了した時点の各データの状況を図７に図示する。
【００５７】
ノードＮ１は目的地ではないため、ステップＳ１０５は否定判定され、ステップＳ１０６に進む。最小ノードであるノードＮ１からはリンクＬ１およびＬ２がノードＮ３およびＮ２に向かって延びている。すなわち、ノードＮ１の隣接ノードはノードＮ２およびＮ３である。ステップＳ１０６の処理が開始した時点の各データの状況を図８に示す。
【００５８】
ステップＳ１０６では、たとえばノードＮ２が選択されてステップＳ１０７０以降の処理を開始する。最小ノードＮ１とその隣接ノードＮ２の間のリンクＬ２の低減期間終了日は、図４（ｂ）にあるように２０ＸＸ年ＹＹ月ＺＺ日である。図５のステップＳ１０７０では現在時刻が２０ＸＸ年ＹＹ月ＺＺ日より前、すなわち低減期間が終了する前であれば、リンクＬ２は補正の対象となる新設された道路であるので、リンクＬ２に対する新設係数はたとえば０．８と決定される。
【００５９】
ステップＳ１０８０では、処理中の接続ノードＮ２が未確定集合に含まれていないため否定判定され、ステップ１０８１に進む。ステップＳ１０８１では、処理中の隣接ノードＮ２を未確定集合の要素にする。このとき、処理中の隣接ノードＮ２の到達コストは取りうる最大の値（ここでは仮に∞とする）とし、先行ノードはＮＵＬＬとする。
【００６０】
経路探索処理は、ステップＳ１０９０に移り、処理中の隣接ノードＮ２について判定式（１）を評価する。処理中の隣接ノードＮ２に関しては∞＞０＋２×０．８であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０の処理が終了した時点の各データの状況を図９に示す。
【００６１】
ステップＳ１０９１では、処理中の隣接ノードＮ２の到達コストを１．６（＝０＋２×０．８）に変更する。ステップＳ１０９２では、処理中の隣接ノードＮ２の先行ノードをノードＮ１に変更する。これにより最小ノードＮ１の隣接ノードのうち、ノードＮ２に関する処理を終了する。ステップＳ１０９２の処理が終了した時点の各データの状況を図１０に示す。
【００６２】
最小ノードＮ１の隣接ノードは、Ｎ２のほかにＮ３があるため、ノードＮ３の処理を開始する。ステップＳ１０７０（２回目）では、最小ノードＮ１とその隣接ノードＮ３の間のリンクＬ１は、新設された道路ではないため、補正に用いる係数を１とする。
【００６３】
ステップＳ１０８０（２回目）では、処理中の接続ノードＮ３が未確定集合に含まれていないため否定判定され、ステップ１０８１に進む。ステップＳ１０８１（２回目）では、処理中の隣接ノードＮ３を未確定集合の要素にする。このとき、処理中の隣接ノードＮ３の到達コストは取りうる最大の値とし、先行ノードはＮＵＬＬとする。
【００６４】
ステップＳ１０９０（２回目）では、処理中の隣接ノードＮ３について判定式（１）を評価する。処理中の隣接ノードＮ３に関しては∞＞０＋５×１であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０（２回目）の処理が終了した時点の各データの状況を図１１に示す。
【００６５】
ステップＳ１０９１（２回目）では、処理中の隣接ノードＮ３の到達コストを５（＝０＋５×１）に変更する。ステップＳ１０９２（２回目）では、処理中の隣接ノードＮ３の先行ノードをノードＮ１に変更する。ステップＳ１０９２（２回目）終了した時点の各データの状況を図１２に示す。
【００６６】
最小ノードＮ１の隣接ノードＮ２およびＮ３に関する処理が共に終了したので、ステップＳ１０２に戻る。ノードＮ２およびＮ３が未確定集合に含まれているため、ステップＳ１０２（２回目）は否定判定され、ステップＳ１０３に進む。ステップＳ１０３（２回目）では、ノードＮ２の到達コスト１．６がノードＮ３の到達コスト５よりも小さいため、制御部１０は未確定集合の中から最小ノードとしてノードＮ２を取り出す。ステップＳ１０４（２回目）では、制御部１０はノードＮ２を確定集合の要素にする。ステップＳ１０４（２回目）終了した時点の各データの状況を図１３に示す。
【００６７】
ノードＮ２は目的地ではないため、ステップＳ１０５では否定判定され、ステップＳ１０６に進む。最小ノードであるノードＮ２からはリンクＬ３がノードＮ３に向かって延びている。すなわち、ノードＮ２の隣接ノードはノードＮ３である。ステップＳ１０６では、隣接ノードとしてノードＮ３が選択されてステップＳ１０７０以降の処理を開始する。ステップＳ１０６の処理を開始した時点の各データの状況を図１４に示す。
【００６８】
リンクＬ３の低減期間終了日は、図４（ｂ）にあるように２０ＸＸ年ＹＹ月ＺＺ日である。ステップＳ１０７０（３回目）では、リンクＬ２と同様にリンクＬ３が補正の対象となる新設された道路と判断され、リンクＬ３に対する係数はたとえば０．８と決定される。
【００６９】
ステップＳ１０８０（３回目）では、処理中の接続ノードＮ３が未確定集合に含まれているため肯定判定され、ステップ１０９０に進む。
【００７０】
ステップＳ１０９０（３回目）では、処理中の隣接ノードＮ３について判定式（１）を評価する。処理中の隣接ノードＮ３に関しては５＞１．６＋４×０．８であるため、判定式（１）が肯定判定され、ステップＳ１０９１に進む。ステップＳ１０９０（３回目）終了時点の各データの状況を図１５に示す。
【００７１】
ステップＳ１０９１（３回目）では、処理中の隣接ノードＮ３の到達コストを４．８（＝１．６＋４×０．８）に変更する。ステップＳ１０９２（３回目）では、処理中の隣接ノードＮ３の先行ノードをノードＮ２に変更する。これにより最小ノードＮ２の隣接ノードに関する処理が終了したので、ステップＳ１０２に戻る。ステップＳ１０９２（３回目）終了時点の各データの状況を図１６に示す。
【００７２】
ノードＮ３が未確定集合に含まれているため、ステップＳ１０２（３回目）は否定判定され、ステップＳ１０３に進む。ステップＳ１０３（３回目）では、制御部１０は未確定集合の中から最小ノードとしてノードＮ３を取り出す。ステップＳ１０４（３回目）では、制御部１０はノードＮ３を確定集合の要素にする。ステップＳ１０４（３回目）終了時点の各データの状況を図１７に示す。
【００７３】
ノードＮ３は目的地であるため、ステップＳ１０５では肯定判定され、ステップＳ１５６に進む。ステップＳ１５６では、図１８のように、目的地のノードＮ３から出発地のノードＮ１まで先行ノードを辿り、その結果に基づいてノードＮ１，ノードＮ２，ノードＮ３という推奨経路を出力する。
【００７４】
以上で説明した実施形態によれば、次の作用効果を奏する。
【００７５】
本実施の形態の経路案内装置１の記憶部１１には、道路の移動コストに関する情報と新設された道路の移動コストを補正する期間である低減期間終了日とが含まれる地図データが記憶されている（図４（ｂ））。そして、新設された道路に設定された低減期間終了日よりも現在時刻が前である場合は、新設された道路の移動コストを低減する補正を行い（図５のステップＳ１０７０）、ユーザが入力装置１２を介して特定した目的地に到達するまでの移動コストが少ない経路を特定する（図５）。そして、特定された推奨経路に基づいて経路案内を行う。これにより、新設された道路の利点を考慮した経路案内ができる。
【００７６】
以上で説明した実施形態は、以下のように変形して実施できる。
【００７７】
（１）本実施の形態では、低減期間終了日に関する情報を地図データの更新分４２だけに含めているが、オリジナルの地図データ４１にも含めてよい。また、地図データの更新分４２の更新日を記憶しておき、その更新日に基づいて低減期間終了日を定めてもよい。
【００７８】
（２）本実施の形態では、移動コストの算出にリンク長を使用したが、他の情報に基づいて移動コストを算出してもよい。たとえば、旅行時間に基づいて算出してもよい。
【００７９】
（３）本実施の形態では、移動コストをリンク長と評価値の乗算により算出したが、乗算結果を予め地図データに記憶してもよい。
【００８０】
（４）本実施の形態では、経路探索処理の一例としてダイクストラ法を基にした処理を提示したが、リンクに関する情報に基づいた移動コストが最も小さくなる経路を出力できるものであればこれに限定するものではない。たとえば、ベルマン・フォード法に基づいた処理でもよい。
【００８１】
以上で説明した各実施の形態や各種の変形例はあくまで一例であり、発明の特徴が損なわれない限り、本発明はこれらの内容に限定されない。
【符号の説明】
【００８２】
１ 経路案内装置
１０ 制御部
１１ 記憶部
１２ 表示モニタ
１３ スピーカ
１４ ＧＰＳ受信部
１５ ジャイロセンサ
１６ 入力装置
２０ 評価値表
４０ 地図データ
４０１ 低減期間終了日
【特許請求の範囲】
【請求項１】
道路の移動コストに関する情報を含む道路情報を記憶する道路情報記憶手段と、
前記道路情報における各道路の移動コストのうち新設された道路の移動コストを低減するコスト低減手段と、
目的地を特定する目的地特定手段と、
前記道路情報における移動コストおよび前記コスト低減手段により低減された移動コストに基づいて、前記目的地に到達するまでの移動に要する移動コストが小さい経路を特定する経路特定手段と、
前記経路特定手段により特定される経路に従って車両を案内する経路案内手段とを備えることを特徴とする経路案内装置。
【請求項２】
請求項１に記載の経路案内装置において、
前記道路情報は、前記新設された道路を特定するための日付情報を更に含み、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路を特定し、当該新設された道路の移動コストを低減することを特徴とする経路案内装置。
【請求項３】
請求項２に記載の経路案内装置において、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路の移動コストを低減する期間を決定することを特徴とする経路案内装置。
【請求項４】
請求項３に記載の経路案内装置において、
現在日時を取得する現在日時取得手段を更に備え、
前記コスト低減手段は、前記現在日時が前記移動コストを低減する期間内である道路を新設された道路として特定することを特徴とする経路案内装置。
【請求項５】
請求項２から４のいずれか一項に記載の経路案内装置において、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路の移動コストの低減量を時間経過に応じて変化させることを特徴とする経路案内装置。
【請求項６】
請求項２から５のいずれか一項に記載の経路案内装置において、
前記道路情報の一部を更新するための差分更新情報を他から取得する差分更新情報取得手段を更に備え、
前記日付情報は、前記差分更新情報に含まれることを特徴とする経路案内装置。
【請求項１】
道路の移動コストに関する情報を含む道路情報を記憶する道路情報記憶手段と、
前記道路情報における各道路の移動コストのうち新設された道路の移動コストを低減するコスト低減手段と、
目的地を特定する目的地特定手段と、
前記道路情報における移動コストおよび前記コスト低減手段により低減された移動コストに基づいて、前記目的地に到達するまでの移動に要する移動コストが小さい経路を特定する経路特定手段と、
前記経路特定手段により特定される経路に従って車両を案内する経路案内手段とを備えることを特徴とする経路案内装置。
【請求項２】
請求項１に記載の経路案内装置において、
前記道路情報は、前記新設された道路を特定するための日付情報を更に含み、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路を特定し、当該新設された道路の移動コストを低減することを特徴とする経路案内装置。
【請求項３】
請求項２に記載の経路案内装置において、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路の移動コストを低減する期間を決定することを特徴とする経路案内装置。
【請求項４】
請求項３に記載の経路案内装置において、
現在日時を取得する現在日時取得手段を更に備え、
前記コスト低減手段は、前記現在日時が前記移動コストを低減する期間内である道路を新設された道路として特定することを特徴とする経路案内装置。
【請求項５】
請求項２から４のいずれか一項に記載の経路案内装置において、
前記コスト低減手段は、前記日付情報に基づいて、前記新設された道路の移動コストの低減量を時間経過に応じて変化させることを特徴とする経路案内装置。
【請求項６】
請求項２から５のいずれか一項に記載の経路案内装置において、
前記道路情報の一部を更新するための差分更新情報を他から取得する差分更新情報取得手段を更に備え、
前記日付情報は、前記差分更新情報に含まれることを特徴とする経路案内装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１１−２５７１６８（Ｐ２０１１−２５７１６８Ａ）
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願番号】特願２０１０−１２９６８１（Ｐ２０１０−１２９６８１）
【出願日】平成２２年６月７日（２０１０．６．７）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願日】平成２２年６月７日（２０１０．６．７）
【出願人】（０００００１４８７）クラリオン株式会社 (1,722)
【Ｆターム（参考）】
[ Back to top ]