(57)【要約】【課題】  複数の地点データによって目的とする指定ルートが指定されている場合に、適切な指定ルートを作成（特定）できるようにする。【解決手段】  道路ＮＷＤＢ１０６には、ノードデータとリンクデータとが記憶されている。記憶装置１０３の経路指示データファイルには、辿るべきルートを特定するための地点を指示する経路指示データが、辿る順序が分かる態様で記憶されている。候補リンク取得部１２１は、経路指示データファイルの経路指示データにより指示される地点ごとに、道路ＮＷＤＢ１０６のノードデータとリンクデータとに基づき使用可能な候補リンクを取得し、候補リンク絞込部１２２が、取得したリンクからより使用に適したリンクを絞り込む。候補リンク絞込部１２２によって１つのルートが絞り込めた場合には、当該ルートを指示ルートとして特定する。【選択図】図１
2018040712.tif 000002
【特許請求の範囲】
【請求項１】
所定の地点であるノードに関する情報と、前記ノード間を結ぶ線分によって表される通行可能な路線であるリンクに関する情報とを記憶する探索用データ記憶手段と、
辿るべきルートを特定するための地点を指示する緯度経度からなる経路指示データを、辿る順序が分かる態様で記憶する経路指示データ記憶手段と、
前記経路指示データ記憶手段の前記経路指示データが指示する地点ごとに、前記探索用データ記憶手段を参照し、辿るべきリンクの候補を取得する取得手段と、
前記取得手段で取得された候補となる前記リンクから、使用する可能性の高いリンクを絞り込む絞込手段と
を備え、
前記絞込手段によって１つのルートが絞り込めた場合に、当該ルートを指示ルートとして特定することを特徴とする指定ルート作成装置。
【請求項２】
請求項１に記載の指定ルート作成装置であって、
前記絞込手段によって１つのルートが絞り込めなかった場合に、前記絞込手段により絞り込まれた前記リンクを利用して、目的地に至るルートを探索し、探索したルート同士を比較して指示ルートを特定する比較手段
を備えることを特徴とする指定ルート作成装置。
【請求項３】
請求項２に記載の指定ルート作成装置であって、
前記比較手段は、通った路線を戻るルートは除外し、同じ種別のリンク列が１つしかない場合には、同じ種別の当該リンク列を指定ルートとして特定し、同じ種別のリンク列がないか、同じ種別のリンク列が複数存在する場合には、各リンク列の距離に基づき、指定ルートを特定することを特徴とする指定ルート作成装置。
【請求項４】
請求項１から請求項３のいずれかに記載の指定ルート作成装置であって、
前記取得手段は、前記指示データ記憶手段の前記指示データにより指示される地点を基準として特定される第１の範囲内に位置するノードを抽出し、抽出した前記ノードに接続されるリンクを候補として取得する
ことを特徴とする指定ルート作成装置。
【請求項５】
請求項４に記載の指定ルート作成装置であって、
前記取得手段は、前記第１の範囲内に位置するノードが抽出できなかった場合に、前記指示データ記憶手段の前記指示データにより指示される地点を基準として特定される第２の範囲内に位置するリンクを取得し、当該リンクに対して前記基準とした前記地点から垂線を引いた場合の交点に近いノードを抽出し、抽出した前記ノードに接続されるリンクを候補として取得する
ことを特徴とする指定ルート作成装置。
【請求項６】
請求項１から請求項５のいずれかに記載の指定ルート作成装置であって、
前記取得手段は、候補として取得した前記リンクのうち、重複するリンクは１つを残して除去することを特徴とする指定ルート作成装置。
【請求項７】
請求項１から請求項６のいずれかに記載の指定ルート作成装置であって、
前記探索用データ記憶手段の前記リンクに関する情報は、リンクごとに種別を示す情報を備えており、
前記絞込手段は、対応する前記経路指示データにより指示される地点に対応するリンクの種別と、同じ種別を有するリンクの候補を優先して選択するように絞り込みを行うことを特徴とする指定ルート作成装置。
【請求項８】
請求項１から請求項７のいずれかに記載の指定ルート作成装置であって、
前記探索用データ記憶手段の前記リンクに関する情報が、リンクごとに当該リンクが属する路線の名称を備えている場合には、
前記絞込手段は、対応する前記経路指示データにより指示される地点に対応するリンクの路線の名称と、同じ路線の名称を有するリンクの候補を優先して選択するように絞り込みを行うことを特徴とする指定ルート作成装置。
【請求項９】
請求項１から請求項８のいずれかに記載の指定ルート作成装置であって、
前記絞込手段は、前記指示データ記憶手段の処理対象の前記経路指示データが指示する地点と次の前記経路指示データが指示する地点とを結ぶ直線と、真北方向とのなす角の角度に基づいて絞込を行うことを特徴とする指定ルート作成装置。
【請求項１０】
請求項１から請求項９のいずれかに記載の指定ルート作成装置であって、
前記経路指示データにより指示される地点と、特定された前記指定ルートとを表示した地図を、表示手段に表示する表示制御手段を備えることを特徴とする指定ルート作成装置。
【請求項１１】
所定の地点であるノードに関する情報と、前記ノード間を結ぶ線分によって表される通行可能な路線であるリンクに関する情報とを記憶する探索用データ記憶手段と、辿るべきルートを特定するための地点を指示する緯度経度からなる経路指示データを、辿る順序が分かる態様で記憶する経路指示データ記憶手段とが利用可能であり、
取得手段が、前記経路指示データ記憶手段の前記経路指示データが指示する地点ごとに、前記探索用データ記憶手段を参照し、辿るべきリンクの候補を取得する取得工程と、
絞込手段が、前記取得工程で取得された候補となる前記リンクから、使用する可能性の高いリンクを絞り込む絞込工程と
を有し、
前記絞込工程において、１つのルートが絞り込めた場合に、当該ルートを指示ルートとして特定することを特徴とする指定ルート作成方法。
【請求項１２】
所定の地点であるノードに関する情報と、前記ノード間を結ぶ線分によって表される通行可能な路線であるリンクに関する情報とを記憶する探索用データ記憶手段と、辿るべきルートを特定するための地点を指示する緯度経度からなる経路指示データを、辿る順序が分かる態様で記憶する経路指示データ記憶手段とが利用可能なコンピュータが、
前記経路指示データ記憶手段の前記経路指示データが指示する地点ごとに、前記探索用データ記憶手段を参照し、辿るべきリンクの候補を取得する取得手段、
前記取得手段が取得した候補となる前記リンクから、使用する可能性の高いリンクを絞り込む絞込手段、
として機能し、前記絞込手段により１つのルートが絞り込めた場合に、当該ルートを指示ルートとして特定することを特徴とする指定ルート作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、タッチパネルなどを通じて大まかに指定された複数の地点に基づいて、実際に移動することが可能な最適なルートを作成（特定）することができる装置、方法、プログラムに関する。
【背景技術】
【０００２】
自動車用ナビゲーション装置が、多くの自動車に搭載されて広く一般の使用者（ユーザー）に利用されている。また、スマートフォンなどと呼ばれる高機能携帯電話端末やタブレット端末などと呼ばれるタブレット型のパーソナルコンピュータの普及に伴い、これらの機器により実現される歩行者用ナビゲーション装置も広く一般の使用者に利用されている。
【０００３】
このようなナビゲーション装置においては、出発地、経由地、目的地を、これらを特定可能な住所や施設名称などを入力することにより設定し、ルート探索を行う。そして、探索したルートを使用者が辿ることができるように、表示画面に地図を表示すると共に、当該地図上に辿るべきルートと使用者の現在位置とを表示し、さらに音声案内も用いてルート案内が行われる。
【０００４】
また、後に記す特許文献１に開示されているように、出発地、目的地などの地点を、地図が表示されているタッチパネルに対する指などによるタッチ操作で簡単に指示（入力）することができるものもある。この場合、住所や施設名称などの文字入力を行わなくてもよいので、操作が単純化され、使い勝手もよくなっている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１４−００６０５４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の自動車用ナビゲーション装置の一般的な利用態様は、出発地と目的地とを入力し、必要に応じて、高速優先、一般道優先、時間優先、距離優先などといった探索条件を入力することで、最適なルートが探索される。この探索されたルートを辿ることができるように、地図などの表示と音声案内とによってルート案内（経路案内）が行われる。
【０００７】
しかし、自動車用ナビゲーション装置の新たな利用態様として、自動車用ナビゲーション装置でルート探索を行うのではなく、使用者が細かくルートを指定し、その指定ルートを辿ることができるようにルート案内を行うようにしたいとする要求がある。例えば、旅行に出かける場合に、単に自宅から目的とする観光地に向かうのではなく、途中、複数個所の寄り道をしたい場合などである。
【０００８】
例えば、自宅から観光地に向かう場合に、Ａ、Ｂ、Ｃというお店によって買い物をし、Ｄというレストランで食事をして、Ｅという美術館によって、Ｆという景勝地で休憩し、目的地である観光地のホテルに向かうといった場合がある。このような場合には、計画を立てる段階で辿るべきルートがほぼ決まってくるため、走行する道路や曲がり角、中継地などを細かく使用者が指定する。そして、自動車用ナビゲーション装置では、指示された地点を結ぶようにして指定ルートを作成（特定）し、当該指定ルートを辿れるように案内を行うことになる。
【０００９】
この場合に、使用者は、例えば地図が表示されたタッチパネルを通じて、出発地や最終の目的地だけでなく、右折や左折をする交差点、直進する交差点、必要に応じて走行する道路の途中地点、寄り道をする中継地などを指定（入力）することになる。しかし、タッチパネルに対する指などによる接触入力の場合、指での大まかな指示になるため、指示した地点が、本来指示すべき地点からずれてしまう場合があると考えられる。
【００１０】
例えば、図１５（Ａ）に示すように、図の下側から交差点Ａに向かうルートの次に、交差点Ａを左折し、交差点Ｂを直進するルートを指示するため、使用者が、タッチパネルＴＰを通じて地点Ｐ１と地点Ｐ２とを指定したとする。この場合に、指定した地点Ｐ１が、図１５（Ａ）に示すように、交差点Ａを若干過ぎた地点となってしまったとする。
【００１１】
自動車用ナビゲーション装置では、上述したように、指示された地点を結ぶようにして指定ルートを作成することになる。図１５（Ａ）に示した例の場合、本来、指定したいルートは、点線で示したルートＲ１であるが、左折したい交差点Ａの手前でなく、交差点Ａを過ぎた地点Ｐ１を指定してしまったために、自動車用ナビゲーション装置では、地点Ｐ１を通るルートを選択する。このため、図１５（Ａ）において、実線で示したルートＲ２が指定されたルートとして作成（特定）されてしまう。この場合には、かなり遠回りのルートＲ２が、指定ルートとなってしまう。
【００１２】
また、図１５（Ｂ）に示すように、図の下側から交差点Ａに向かうルートの次に、交差点Ａを左折し、交差点Ｂを直進するルートを指示するため、使用者が、地点Ｐ３と地点Ｐ４とを指定したとする。この場合に、タッチパネルＴＰを通じて指定した地点Ｐ３が、本来走行すべき路線の反対路線上の地点となってしまったとする。
【００１３】
この図１５（Ｂ）に示す例の場合、本来、指定したいルートは、点線で示したルートＲ３である。しかし、自動車用ナビゲーション装置では、指定された地点を必ず通るルートを作成する。このため、自動車用ナビゲーション装置では、図１５（Ｂ）において、交差点Ａ、交差点Ｃを通過し、交差点Ｄ、交差点Ｅ、交差点Ｆを順番に右折し、交差点Ｃを左折して、交差点Ａを右折するという実線で示したルートＲ４が作成される。ルートＲ３とルートＲ４とを比較すると分かるように、かなり大回りとなるルートＲ４が指定ルートとして作成（特定）されてしまう。
【００１４】
このようなことは、タッチパネルを通じてルート上の地点を指示する場合以外でも発生する。例えば、パーソナルコンピュータの表示画面に表示した地図上でルート上の地点を指示し、この指示した地点を示す緯度経度データを、自動車用ナビゲーション装置で用いて指示されたルートを作成する場合にも発生する。この場合には、パーソナルコンピュータで使用されている地図と自動車用ナビゲーション装置で使用されている地図との違い、いわゆる基図の違いによって指示した地点がずれてしまうということが発生すると考えられる。
【００１５】
また、音声入力によりスマートフォンに指示を与えるといったことも実現されているが、自動車用ナビゲーション装置に対しても音声により指示を与えることができるようになると考えられる。この場合に、音声によって、右折や左折する交差点や走行する道路上の地点を指示する場合にも、指示位置が交差点の代表点や道路上の代表点などとなり、走行可能なルートを適切に作成できない場合があると考えられる。
【００１６】
ここでは、自動車用ナビゲーション装置の場合を例に説明したが、同様のことは、歩行者用ナビゲーション装置でも発生すると考えられる。特に、徒歩だけでなく、バス、電車、タクシーなどの公共交通機関を利用して移動する場合には、ルート上の適宜の地点を指定してルートを作成するようにしても、ナビゲーション装置において、指定された地点に基づいて、指定ルートを適切に作成できない場合があると考えられる。
【００１７】
以上のことに鑑み、この発明は、複数の地点データによって目的とする指定ルートが指定されている場合に、適切な指定ルートを作成（特定）できるようにすることを目的とする。
【課題を解決するための手段】
【００１８】
上記課題を解決するため、請求項１に記載の発明の指定ルート作成装置は、
所定の地点であるノードに関する情報と、前記ノード間を結ぶ線分によって表される通行可能な路線であるリンクに関する情報とを記憶する探索用データ記憶手段と、
辿るべきルートを特定するための地点を指示する緯度経度からなる経路指示データを、辿る順序が分かる態様で記憶する経路指示データ記憶手段と、
前記経路指示データ記憶手段の前記経路指示データが指示する地点ごとに、前記探索用データ記憶手段を参照し、辿るべきリンクの候補を取得する取得手段と、
前記取得手段で取得された候補となる前記リンクから、使用する可能性の高いリンクを絞り込む絞込手段と
を備え、
前記絞込手段によって１つのルートが絞り込めた場合に、当該ルートを指示ルートとして特定することを特徴とする。
【００１９】
この請求項１に記載の発明の指定ルート作成装置によれば、探索用データ記憶手段には、所定の地点であるノードに関する情報と、このノードの間を結ぶ線分によって表される通行可能な路線であるリンクに関する情報とが記憶されている。また、指示データ記憶手段には、辿るべきルート上の地点を指示する緯度経度からなる指示データが、辿る順序が分かる態様で記憶されている。
【００２０】
取得手段は、指示データ記憶手段の指示データにより指示される地点ごとに、当該地点を基準にして、探索用データ記憶手段のノードに関する情報とリンクに関する情報とに基づき使用可能な候補リンクを取得し、この取得した候補リンクの中から絞込手段が、より使用に適したリンクを絞り込む。そして、絞込手段によって１つのルートが絞り込めた場合には、当該ルートが指示ルートとして特定される。
【００２１】
このように、経路指示データにより指示された地点をそのまま辿るルートを指定ルートとして作成（特定）するのではなく、経路指示データにより指示された地点に基づき、実際に辿るルートとして適切なリンクを選択することができる。これにより、経路指示データにより指示される地点が、本来指示されるべき地点からずれている場合であっても、実際に辿るルートとして適切な指定ルートが作成（特定）できるようにされる。
【発明の効果】
【００２２】
この発明によれば、複数の地点データによって目的とする指定ルートが指定されている場合に、当該指定ルートを作成する上で適切でない地点データを含んでいても、各地点データが指示する地点に基づいて、利用可能な最適なリンクを特定することができる。これにより、指示された複数の地点データに基づいて、目的とする適切な指定ルートを作成（特定）できる。
【図面の簡単な説明】
【００２３】
【図１】実施の形態の自動車用ナビゲーション装置の構成例について説明するためのブロック図である。
【図２】道路ネットワークデータベースに格納される自動車用のネットワークデータの例を説明するための図である。
【図３】ネットワークデータの１つであるリンクデータの例を説明するための図である。
【図４】ネットワークデータの１つであるノードデータの例を説明するための図である。
【図５】経路指示データファイルに格納される経路指示データの例を説明するための図である。
【図６】指定ルート作成機能の実行時の処理の概要について説明するためのフローチャートである。
【図７】図６のステップＳ１において実行される候補リンク取得処理（第１処理）について説明するためのフローチャートである。
【図８】図７の候補リンク取得処理の詳細を説明するための図である。
【図９】図７の候補リンク取得処理の詳細を説明するための図である。
【図１０】図６のステップＳ２において実行される候補リンク絞込処理（第２処理）について説明するためのフローチャートである。
【図１１】図１０の候補リンク絞込処理において行われる［進行角度照合］について説明するための図である。
【図１２】図６のステップＳ４において実行される検索ルート比較処理（第３処理）について説明するためのフローチャートである。
【図１３】この実施形態のナビゲーション装置における指定ルートの表示例を説明するための図である。
【図１４】この実施形態のナビゲーション装置における指定ルートの表示例を説明するための図である。
【図１５】従来のナビゲーション装置での指定ルートの作成処理の例について説明するための図である。
【発明を実施するための形態】
【００２４】
以下、図を参照しながら、この発明による装置、方法、プログラムの一実施形態について説明する。以下に説明する実施形態においては、この発明を自動車用ナビゲーション装置に適用した場合を例にして説明する。
【００２５】
［自動車用ナビゲーション装置の構成例］
図１は、この実施の形態の自動車用ナビゲーション装置の構成例について説明するためのブロック図である。なお、以下においては、自動車用ナビゲーション装置を単にナビゲーション装置と記載する。図１に示したナビゲーション装置において、送受信アンテナ１０１Ａ及び無線通信部１０１は通信機能を、制御部１０２は当該ナビゲーション装置の各部を制御する機能を、記憶装置１０３は例えば記録媒体としてハードディスクを備え、情報記憶保持機能を実現する。操作部１０４は、電源のオン／オフスイッチや幾つかのファンクションボタンなどが設けられたものである。
【００２６】
また、この実施形態のナビゲーション装置は、地図情報ＤＢ１０５、道路ＮＷＤＢ１０６を備えている。なお、地図情報ＤＢ１０５における文字「ＤＢ」は、「Data Base」の略称である。また、道路ＮＷＤＢ１０６における文字「ＮＷＤＢ」は、「Network Data Base」の略称である。
【００２７】
地図情報ＤＢ１０５は、移動経路や現在位置などを使用者に示すために使用する市街図、道路図、広域図、地方図、全国図を表示するための地図データを記憶する。市街図、道路図、広域図、地方図、全国図を表示するための地図データは、地図を描画するための例えばベクトルデータやラスタデータ、注記（注釈）データなどを含む。
【００２８】
道路ＮＷＤＢ１０６は、自動車用の道路ネットワークデータ（以下、単にネットワークデータと記載する。）を記憶保持する。図２〜図４は、道路ＮＷＤＢ１０６に格納される自動車用のネットワークデータの例を説明するための図である。図２は、道路ネットワークの一例を示している。ネットワークデータは、ノード（データ）とリンク（データ）とからなる。ノードは、ランドマーク、建物、施設、交差点、分岐点、屈曲点などの地点を表す。また、リンクは、ノードを結ぶ線分によって、国道、県道などの自動車が通行可能な道路などを示す。
【００２９】
図２では、上側が北、下側が南、右側が東、左側が西であるものとし、南北方向に延びる道路Ｒｄ１と、これに交差する東西方向に延びる道路Ｒｄ２、Ｒｄ３とを示している。いずれの道路も、片側１車線の２車線道路である。そして、道路Ｒｄ１と道路Ｒｄ２が交差する交差点には、４つのノードＮ１、Ｎ２、Ｎ３、Ｎ４が設けられており、道路Ｒｄ１と道路Ｒｄ３が交差する交差点には、４つのノードＮ５、Ｎ６、Ｎ７、Ｎ８が設けられている場合を示している。
【００３０】
そして、図２において、道路Ｒｄ１については、ノードＮ１に向かうリンクＬ１、ノードＮ１からＮ２に向かうリンクＬ２、ノードＮ２からＮ５に向かうリンクＬ３、ノードＮ５からＮ６に向かうリンクＬ４、ノードＮ６から北進するリンクＬ５がある。また、道路Ｒｄ１については、ノードＮ７に向かうリンクＬ６、ノードＮ７からＮ８に向かうリンクＬ７、ノードＮ８からＮ３に向かうリンクＬ８、ノードＮ３からＮ４に向かうリンクＬ９、ノードＮ４から南進するリンクＬ１０がある。
【００３１】
また、道路Ｒｄ２については、ノードＮ４に向かうリンクＬ１１、ノードＮ４からＮ１に向かうリンクＬ１２、ノードＮ１から西進するリンクＬ１３がある。また、道路Ｒｄ２については、ノードＮ２に向かうリンクＬ１４、ノードＮ２からＮ３に向かうリンクＬ１５、ノードＮ３から東進するリンクＬ１６がある。また、道路Ｒｄ３については、ノードＮ８に向かうリンクＬ１７、ノードＮ８からＮ５に向かうリンクＬ１８、ノードＮ５から西進するリンクＬ１９がある。また、道路Ｒｄ３については、ノードＮ６に向かうリンクＬ２０、ノードＮ６からＮ７に向かうリンクＬ２１、ノードＮ７から東進するリンクＬ２２がある。
【００３２】
図３は、図２に示した例のネットワークの場合のネットワークデータの１つであるリンクデータの例を説明するための図である。各リンクデータには、各リンクの識別情報（Ｌ１、Ｌ２、…）と、そのリンクの両端のノードの識別情報（Ｎ１、Ｎ２、…）と、リンクコスト（図２では単にコストと記載）と、リンク種別（図２では単に種別と記載）と、距離と、名称と、適用とが対応付けられている。
【００３３】
通常、リンクコストは、そのリンクの長さ（距離）、あるいは、通行に要する時間によって定められる。そして、リンクコストは、例えばダイクストラ法などにより、リンクコストが最小となるルート（経路）を探索する場合に参照される。リンク種別は、当該リンク部分が、国道、県道、市道、私道などのどれであるかを示すものである。
【００３４】
距離は、そのリンクの距離（長さ）を示し、名称は、そのリンクの名称、例えば、○○号線、第三京浜、青梅街道、□□通りなどといった、そのリンクが含まれる道路に付けられた名称であり、道路の略称、通称、俗称などをも含む。摘要は、この例では、北進路線、南進路線、西進路線、東進路線とったリンクの進行方向を示す。この他にも、摘要として、上り路線、下り路線、○○方面などといった情報により、進行方向を示す場合もある。この他にも、車線数や走行可能な自動車の種別など、種々の情報を登録し、管理することもできる。
【００３５】
なお、図３において、ノードＮａ、Ｎｃ、Ｎｄは、図２で省略したノードであり、リンクＬ１、Ｌ１１、Ｌ１３の一方の端部のノードを示している。そして、図３のリンクデータにおいて、例えば、リンクＬ１についてその登録内容は、以下のようになっている。リンクＬ１は、両端がノード「Ｎａ、Ｎ１」であり、リンクコストが「２０」で、リンク種別が「国道」で、リンクの距離（長さ）が「５００ｍ」で、名称が「○○号線」で、摘要が「北進路線」であることが分かる。その他のリンクについても、同様の内容が把握できる。
【００３６】
図４は、図２に示した例のネットワークの場合のネットワークデータの１つであるノードデータの例を説明するための図である。各ノードデータには、各ノードの識別情報（Ｎ１、Ｎ２、…）と、そのノードの位置を示す緯度、経度情報と、ノード種別（図４では単に種別と記載。）と、名称等と、摘要と、その他の情報とが対応付けられている。ノード種別は、当該ノード部分が、交差点、分岐点などのどれであるかを示すものである。そして、図４に示した例の場合、各ノードは交差点であることが示されている。
【００３７】
また、名称等は、そのノードの名称であり、そのノードが交差点であれば、例えば、○○町１丁目、□□町南、△△駅入口などといった名称が記録される。また、摘要は、この例においては、そのノードが示す地点がどのような地点なのかを示すものであり、そのノードが交差点に対応するノードある場合には、例えば、その交差点の代表点なのか、左折する位置を示す左折ポイントなのか、右折する位置を示す右折ポイントなのかなどを示す情報が記録される。
【００３８】
なお、図４のノードデータにおいて、例えば、ノードＮ１についてその登録内容は、以下のようになっている。ノードＮ１は、緯度、経度が（Ｘ１，Ｙ１）で示される地点であり、ノード種別は「交差点」であり、名称は「○○○○」であり、提供は、「北進左折ポイント」あるいは「西進右折ポイント」であることが分かる。その他のノードについても、同様の内容が把握できる。
【００３９】
また、地図情報ＤＢ１０５、道路ネットワークＤＢ１０６に格納されているデータについては、変更が生じるごとに必要なタイミングで更新され、正確な情報が管理できるようになっている。地図情報ＤＢ１０５、道路ネットワークＤＢ１０６に格納されているデータの更新は、例えば、送受信アンテナ１０１Ａ及び無線通信部１０１を通じて更新データの提供を受けて行うことができるようにされる。
【００４０】
外部Ｉ／Ｆ１０７及び入出力端子１０７Ｔは、例えば、ＵＳＢ（Universal serial Bus）規格のインターフェース部であり、ＵＳＢメモリやスマートフォンなどを接続して、経路指示データなどの提供を受けるなどのことができるようにされる。また、記憶装置１０３に保持されている走行履歴を、外部Ｉ／Ｆ１０７及び入出力端子１０７Ｔを通じて、ＵＳＢメモリや外部機器に供給してバックアップをとるなどのこともできるようにされる。
【００４１】
センサＩ／Ｆ１０８は、当該ナビゲーション装置が搭載された自動車側に設けられている種々のセンサからの情報を受け付けて、これを制御部１０２に供給する。これにより、後述するＧＰＳ機能により現在位置が正確に測位できない場合において、自律航行を可能にするなどのことができるようになっている。自動車側に設けられている種々のセンサからの情報としては、速度情報、ステアリングの操作情報などの種々の情報が含まれる。
【００４２】
ＧＰＳアンテナ１０９Ａ及びＧＰＳ部１０９は、現在位置取得機能を実現する。表示部１１０Ｄ及びタッチセンサ１１０Ｓとからなるタッチパネル１１０と、音声出力部１１１と、スピーカ１１２と、マイクロホン１１４と、音声入力部１１３とは、ユーザーインターフェースを構成する。表示部１１０Ｄには、地図と自車の現在位置とを表示したり、必要となる案内情報を表示したりできる。また、音声出力部１１１とスピーカ１１２とを通じて、種々の案内メッセージを放音することができる。また、マイクロホン１１４と音声入力部１１３とを通じて、音声による指示入力などを受け付けることができる。
【００４３】
［指定ルート作成機能を実現する主要部］
そして、候補リンク取得部１２１、候補リンク絞込部１２２、ルート探索部１２３、探索ルート比較部１２４、有料ルート作成部１２５が、この実施形態のナビゲーション装置が備える指定ルート作成機能を実現する主要部分となる。指定ルート作成機能は、複数の地点のそれぞれを示す緯度、経度データである経路指示データによってルートが指示されている場合に、当該経路指示データに基づいて、実際に辿ることができる最適な指示ルートを作成（特定）する機能である。
【００４４】
このような指定ルート作成機能が必要になるのは、例えば、タッチパネルを通じて通行する地点を指示することにより経路指示データを作成した場合などに、指示した地点が本来指示すべき地点から僅かにずれてしまうような場合があるためである。この場合、経路指示データが示す地点が、例えば目的とする交差点から僅かにずれただけで、図１５を用いて説明したように、目的とする指定ルートとは異なる遠回りのルートが指定ルートとして作成（特定）されてしまう場合があるからである。
【００４５】
したがって、当該指定ルート作成機能を用いる場合には、例えば、記憶装置１０３に経路指示データファイルが作成されている必要がある。図５は、この実施形態において、記憶装置１０３に作成される経路指示データファイルに格納される経路指示データの例を説明するための図である。図５に示すように、経路指示データファイルには、ルートを指定するために指示された地点を示す経路指示データが、辿る順番に格納されている。経路指示データは、緯度、経度データである。
【００４６】
図５に示した例の場合には、経路指示データとして、スタート地点は、地点（Ｌａｔ１，Ｌｏｎ１）であり、次に地点（Ｌａｔ２，Ｌｏｎ２）を通り、次には地点（Ｌａｔ３，Ｌｏｎ３）を通るというように、辿る順番にその辿るべき地点を示す緯度、経度が記憶保持されている。このような経路指示データは、例えば、タッチパネル１１０に対する指によるタッチ操作により入力されたものである。すなわち、指示された地点に対応する緯度経度が、地図情報ＤＢ１０５の地図情報から取得され、これを用いて経路指示データが形成される。
【００４７】
この他にも、例えば、外部のパーソナルコンピュータにおいて作成された経路指示データを、入出力端子１０７Ｔ及び外部Ｉ／Ｆ１０７を通じて取り込んで、これを記憶装置１０３に記録することにより、経路指示データファイルを形成できる。また、マイクロホン１１４及び音声入力部１１３を通じて、例えば、「○○交差点」、「△△交差点」などのような地点を指示する音声情報を受け付け、これに基づいて、地図情報ＤＢ１０５を参照し、対応する交差点の緯度、経度を取得する。このようにして取得した緯度、経度を、経路指示データとして、記憶装置１０３に記録することにより、経路指示データファイルを形成できる。
【００４８】
そして、記憶装置１０３に作成された経路指示データファイルの経路指示データを用いて、指示ルート作成機能を働かせることにより、適切な指示ルートが作成（特定）できる。まず、候補リンク取得部１２１、候補リンク絞込部１２２、ルート探索部１２３、探索ルート比較部１２４、有料ルート作成部１２５によって実現される指定ルート作成機能の実行時の処理の概要について説明する。
【００４９】
図６は、指定ルート作成機能の実行時の処理の概要について説明するためのフローチャートである。この図６に示すフローチャートの処理は、この実施形態のナビゲーション装置において、所定のメニューから指示ルート作成処理に対応する項目が選択されて実行するようにされた場合に、主に制御部１０２によって実行される。
【００５０】
まず、制御部１０２の制御の下、候補リンク取得部１２１が機能し、記憶装置１０３の経路指示データファイルの経路指示データのそれぞれごとに、道路ＮＷＤＢ１０６を参照し、辿るべきリンクの候補（候補リンク）を取得する候補リンク取得処理を実行する（ステップＳ１）。次に、制御部１０２の制御の下、候補リンク絞込部１２２が機能し、各経路指示データが示す地点ごとに対応して、候補リンク取得部１２１によって取得された候補リンクについて、使用する可能性の高いリンクを絞り込む候補リンク絞込処理を行う（ステップＳ２）。
【００５１】
このステップＳ２においては、絞り込まれたリンクが高速道路などの有料道路のリンクだけである場合には、有料ルート作成部１２５が機能し、有料道路選択処理を行う。この有料道路選択処理は、次の経路指示データが、有料道路の料金所付近の地点を指示するものである場合には、これを無視し、有料道路上のルートを維持するようにして、指定ルート（リンク列）を特定する処理である。
【００５２】
例えば、高速道路上を比較的に長い距離移動する場合には、経路指示データとして、高速道路の通過する料金所付近の地点を指示する場合がある。このような場合、料金所付近の地点が指示されているために、ナビゲーション装置でルートを選択する場合には、降りる必要がないのに、高速道路を降りるルートを選択してしまう場合がある。このような不都合を生じさせることがないように、有料ルート作成部１２５は、ステップＳ２において、高速道路などの有料道路上を移動するリンクを適切に選択できるようにしている。
【００５３】
このステップＳ１、ステップＳ２の処理を通じて、各経路指示データが示す地点に沿うように接続されるリンク列が１つだけに絞り込めた場合には、目的とする指定ルートが作成（特定）できたことになる。このため、ステップＳ２の処理の後、すなわち、経路指示データにより指示された全ての地点について、候補リンクを絞り込んだ後において、候補リンク絞込部１２２は、１つのルートに絞り込めたか否かを判別する（ステップＳ３）。ステップＳ３の判別処理において、１つのルートに絞り込めていないと判別した時には、制御部１０２の制御の下、ルート探索部１２３と探索ルート比較部１２４とが機能し、探索ルート比較処理を実行する（ステップＳ４）。
【００５４】
このステップＳ４では、まず、ルート探索部１２３が機能し、候補リンク絞込部１２２により絞り込まれたリンクを利用した目的地での複数のルートを探索する。次に、探索ルート比較部１２４が機能し、ルート探索部１２３で探索されたルートのそれぞれを比較してより有利なルート（リンク列）を指定ルートとして特定する。
【００５５】
そして、ステップＳ３の判別処理において、１つのルートに絞り込めたと判別した場合と、ステップＳ４の探索ルート比較処理の後においては、ステップＳ２の処理で絞り込まれた１つのルートを、あるいは、ステップＳ４の処理で特定された１つのルートを、指定ルートとして決定し（ステップＳ５）、この図６に示す処理を終了する。このようにして、決定された指定ルートを辿ることができるノードとリンクとからなり一連のデータが、指定ルートを辿るための指定ルートデータとなり、記憶装置１０３の所定の記憶領域に記録され、経路案内処理に用いられることになる。このノードとリンクとからなり一連のデータである指定ルートデータを作成する機能が、指定ルート作成機能である。
【００５６】
これにより、記憶装置１０３の経路指示データファイルの経路指示データの中に、本来指示すべき場所と異なる場所を指示する経路指示データが含まれていても、出発地から目的地に至る適切な指示ルートを作成（特定）し、この指示ルートを辿るように経路案内を行うことができる。
【００５７】
なお、この実施形態のナビゲーション装置において、指定ルートが作成（特定）された後に当該指定ルートを辿るように経路案内を行う機能は制御部１０２により実現される。すなわち、作成された指定ルートを案内するために、表示部１１０Ｄへの地図表示、当該地図上への指定ルートや自車位置の表示、経路案内メッセージの形成と音声出力部１１１及ぶスピーカ１１２を通じた出力などは、制御部１０２の制御により行われる。
【００５８】
次に、図６のフローチャートに示した候補リンク取得処理（第１処理）、候補リンク絞込処理（第２処理）、探索ルート比較処理（第３処理）のそれぞれについて、その詳細を説明する。
【００５９】
［候補リンク取得処理（第１処理）］
図７は、図６のステップＳ１において実行される候補リンク取得処理（第１処理）について説明するためのフローチャートである。また、図８、図９は、図７の候補リンク取得処理の詳細を説明するための図である。上述もしたように、図７に示す候補リンク取得処理は、制御部１０２の制御の下、主に候補リンク取得部１２１によって行われる。
【００６０】
まず、制御部１０２は、候補リンク取得部１２１を制御して、記憶装置１０３の経路指示データファイルから処理対象とする経路指示データを読み出す（ステップＳ１１）。そして、読み出した経路指示データが示す地点を中心にして、所定範囲内に存在するノードを、利用するノード候補として道路ＮＷＤＢ１０６から取得する（ステップＳ１２）。
【００６１】
ステップＳ１２での処理を具体的に説明する。例えば、図８（Ａ）に示すように、交差点付近の地点Ｐ１が読み出した経路指示データにより指示された地点であるとする。この場合、候補リンク取得部１２１は、読み出した経路指示データにより指示された地点Ｐ１を中心にして、点線の円で示したように、例えば半径５０ｍの円形エリア内に存在するノードを周辺ノード候補として取得する。図８（Ａ）の場合には、点線で示した円形エリア内には、４つのノードＮ１、Ｎ２、Ｎ３、Ｎ４が存在している。このため候補リンク取得部１２１は、図８（Ｂ）に示すように、周辺ノード候補として、当該４つのノードＮ１、Ｎ２、Ｎ３、Ｎ４を取得する。
【００６２】
そして、候補リンク取得部１２１は、周辺ノード候補が取得できたか否かを判別する（ステップＳ１３）。ステップＳ１３の判別処理において、周辺ノード候補が取得できたと判別した時には、候補リンク取得部１２１は、取得した周辺ノード候補のそれぞれに接続されるリンクを取得する（ステップＳ１４）。この場合、図８（Ａ）に示すように、ノードＮ１にはリンクＬ１、Ｌ２、Ｌ１２、Ｌ１３が、ノードＮ２にはリンクＬ２、Ｌ３、Ｌ１４、Ｌ１５が接続されている。また、ノードＮ３にはリンクＬ８、Ｌ９、Ｌ１５、Ｌ１６が、ノードＮ４にはリンクＬ９、Ｌ１０、Ｌ１１、Ｌ１２が接続されている。このため、候補リンク取得部１２１は、ステップＳ１４において、図８（Ｂ）の接続リンクの欄に示したように、各ノードＮ１、Ｎ２、Ｎ３、Ｎ４のそれぞれに接続されたリンクを接続リンクとして取得する。
【００６３】
次に、候補リンク取得部１２１は、ステップＳ１４で取得した接続リンクから重複するリンクや進行方向が異なるリンクを除去する処理を行う（ステップＳ１５）。図８（Ｂ）に示したように、ステップＳ１４では、ノードＮ１、Ｎ２、Ｎ３、Ｎ４ごとに、４つずつの接続リンクが取得されているので、重複するリンクについてはそのうちの１つを残して除去し、進行方向が異なるリンクは全部除去する。
【００６４】
まず、図８（Ｂ）に示したように、下線を付して示したリンクＬ２、Ｌ１５、Ｌ９、Ｌ１２は重複しているため除去する。また、図８（Ａ）において矢印で示したように、進行方向は、リンクＬ１に沿ってノードＮ１に向かう方向であるので、これに交差する方向のリンクとなる四角で囲んで示したリンクＬ１１、Ｌ１２、Ｌ１３、Ｌ１４、Ｌ１５、Ｌ１６は除去する。また、矢印で示した進行方向とは、逆の路線のリンクである四角で囲んで示したリンクＬ８、Ｌ９、Ｌ１０も除去する。これにより、図８（Ｂ）の候補リンクの欄に示すように、リンクＬ１、Ｌ２、Ｌ３が、候補リンク（列）として特定できる。この図８（Ｂ）に示した情報が、候補ルートを示す情報として、各経路指示データに対応して、記憶装置１０３の所定のエリアに記録される。
【００６５】
また、図９（Ａ）に示すように、交差点からも道路からも離れた地点Ｐ１が読み出した経路指示データにより指示された地点であるとする。この場合、候補リンク取得部１２１は、読み出した経路指示データにより指示された地点Ｐ１を中心にして、例えば半径５０ｍの点線で示した円形エリア内に存在するノードはない。したがって、ステップＳ１３の判別処理においては、周辺ノード候補は取得できなかったと判別される。
【００６６】
この場合には、候補リンク取得部１２１は、周辺リンク候補を取得する（ステップＳ１６）。すなわち、点線で示した円形エリア内にあるリンクを周辺リンク候補として取得する。この例の場合、図９（Ａ）に示すように、点線で示した円形エリア内に存在するリンクはリンクＬ１３、Ｌ１４である。したがって、図９（Ｂ）に示すように、周辺リンク候補として、リンクＬ１３、Ｌ１４が取得できる。
【００６７】
この後、候補リンク取得部１２１は、経路指示データで示される地点Ｐ１から周辺リンク候補Ｌ１３、Ｌ１４に垂線を引き、この垂線とリンクＬ１３、Ｌ１４の交点Ｋ１、Ｋ２に近いノードを、周辺ノード候補として取得する（ステップＳ１７）。この例では、図９（Ａ）に示すように、交点Ｋ１、Ｋ２に近いノードは、ノードＮ１、Ｎ２であるので、図９（Ｂ）に示すように、周辺ノード候補としてノードＮ１、Ｎ２が取得できる。
【００６８】
このステップＳ１７の処理の後においては、上述したステップＳ１４、ステップＳ１５の処理が行われる。すなわち、周辺ノード候補として取得したノードＮ１にはリンクＬ１、Ｌ２、Ｌ１２、Ｌ１３が、ノードＮ２にはリンクＬ２、Ｌ３、Ｌ１４、Ｌ１５が接続されている。このため、候補リンク取得部１２１は、ステップＳ１４において、図９（Ｂ）の接続リンクの欄に示したように、各ノードＮ１、Ｎ２のそれぞれに接続されたリンクを接続リンクとして取得する。
【００６９】
次に、候補リンク取得部１２１は、ステップＳ１４で取得した接続リンクから重複するリンクや進行方向が異なるリンクを除去する処理を行う（ステップＳ１５）。したがって、候補リンク取得部１２１は、図９（Ｂ）の接続リンクの欄に示したように、丸で囲んだリンクＬ２は重複するので除外する。また、この例においても、図９（Ａ）において矢印で示したように、進行方向は、リンクＬ１に沿ってノードＮ１に向かう方向である。このため、図９（Ｂ）の接続リンクの欄に示したように、四角で囲んだリンクＬ１２、Ｌ１３、Ｌ１４、Ｌ１５は進行方向が異なるので除外する。これにより、図９（Ｂ）の候補リンクの欄に示すように、リンクＬ１、Ｌ２、Ｌ３が、候補リンク（列）として特定できる。この図９（Ｂ）に示した情報もまた、候補ルートを示す情報として、各経路指示データに対応して、記憶装置１０３の所定のエリアに記録される。
【００７０】
そして、ステップＳ１５の処理の後において、記憶装置１０３の経路指示データファイルに格納されている全ての経路指示データを読み出して処理したか否かを判別する（ステップＳ１６）。ステップＳ１６の判別処理において、まだ全ての経路指示データについて処理を終えていないと判別したときには、ステップＳ１１からの処理を繰り返す。また、ステップＳ１６の判別処理において、全ての経路指示データについて処理を終えたと判別したときには、この図７に示す処理を終了し、図６の処理に戻って次の処理を行うことになる。
【００７１】
このようにして、制御部１０２の制御の下、候補リンク取得部１２１が機能し、経路指示データにより指示された地点を基準にして、利用する候補となるリンクである候補リンクが取得できる。なお、図８、図９に示した例は、１方向のリンク列を構成するリンクＬ１、Ｌ２、Ｌ３が取得できた場合を示したが、実際には、複数の方向のリンク列が取得できる場合もある。
【００７２】
［候補リンク絞込処理（第２処理）］
図１０は、図６のステップＳ２において実行される候補リンク絞込処理（第２処理）について説明するためのフローチャートである。また、図１１は、図１０の候補リンク絞込処理において行われる［進行角度照合］について説明するための図である。上述もしたように、図１０に示す候補リンク絞込処理は、制御部１０２の制御の下、主に候補リンク絞込部１２２によって行われる処理である。
【００７３】
まず、制御部１０２は、候補リンク絞込部１２２を制御し、経路指示データにより指示された地点ごとに、取得された候補リンクについて道路種別の照合を行う（ステップＳ２１）。このステップＳ２１の処理は、上述した候補リンク取得処理により、各経路指示データにより指示された地点ごとに取得された候補リンクの中に、対応する経路指示データにより指示された地点が位置する道路と同じリンク種別を有するものがあるかを照合する。
【００７４】
この照合は、道路ＮＷＤＢ１０６のリンクデータの対応するリンクのリンク種別を用いて行うことができる。そして、同じリンク種別を有する候補リンクを優先的に用いるように絞り込む。なお、対応する経路指示データにより指示された地点が道路上にない場合には、例えば、対応する経路指示データにより指示された地点に最も近い道路のリンク種別と照合する。
【００７５】
例えば、対応する経路指示データにより指示された地点が位置する道路に対応したリンクのリンク種別が「国道」で、候補リンクの中にリンク種別が「国道」であるものがあれば、そのリンクを優先的に選択する。したがって、対応する経路指示データにより指示された地点が位置する道路に対応したリンクのリンク種別が「国道」で、候補リンクの中にリンク種別が「国道」であるものが１つしかなければ、候補リンクをリンク種別が「国道」である１つのリンクに絞り込むことができる。
【００７６】
また、ステップＳ２１の道路種別照合において、絞り込まれたリンクが、高速道路などの有料道路が１つだけである場合には、上述もしたように、有料道路選択処理を行って、当該有料道路を降りるまでの一連のリンク列を利用するリンク列として特定する。この有料道路選択処理は、各経路指示データにより指示された地点ごとに取得され、絞りこまれたリンクが、同じ有料道路のリンクである場合に、それらのリンクを連続して使用するリンク列として特定する処理である。
【００７７】
そして、ステップＳ２１の処理の後、候補リンク絞込部１２２は、候補リンクを１つに絞り込めたか否かを判別する（ステップＳ２２）。ステップＳ２２の判別処理において、候補リンクを１つに絞り込めていないと判別した時には、候補リンク絞込部１２２は、進行角度照合を行う（ステップＳ２３）。
【００７８】
ステップＳ２３で行われる進行角度照合は、図１１に示すように、まず、今回の処理対象となっている経路指示データにより指示された地点Ｐ１と、次の経路指示データにより指示された地点Ｐ２とを結んだ直線Ｌと、真北方向とのなす角θの角度を求める。図１１に示した例の場合には、直線Ｌと真北方向とのなす角θの角度は９０度である。この直線Ｌと真北方向とのなす角θの範囲内にある候補リンクであって、各候補リンクと真北方向とのなす角の角度が、より角θに近いリンクを優先的に選択する。
【００７９】
図１１では、説明を簡単にするため、今回の処理対象となっている経路指示データにより指示された地点Ｐ１と、候補リンクであるリンクＬＡ、ＬＢの始点となるノードＮＡ、ＮＢが同じである場合を示している。そして、候補リンクＬＡと真北方向とのなす角θＡの角度は６０度であり、候補リンクＬＢと真北方向とのなす角θＢの角度は３０度である場合を示している。この例の場合、候補リンクＬＡと真北方向とのなす角θＡの角度（６０度）の方が、より直線Ｌと真北方向とのなす角θの角度（９０度）に近いため、候補リンクＬＡが優先的に選択される。
【００８０】
また、ステップＳ２３の処理は、今回の処理対象となっている経路指示データにより指示された地点Ｐ１と、次の経路指示データにより指示された地点Ｐ２との距離が長すぎると、対象となるリンクが多くなる場合があり、適切に絞り込みが行えない場合がある。このため、今回の処理対象となっている経路指示データにより指示された地点Ｐ１と、次の経路指示データにより指示された地点Ｐ２との距離が、所定距離以内である場合にだけ、ステップＳ２３の進行角度照合を行うようにする。なお、当該所定距離は、例えば、１ｋｍ（キロメートル）とするなどのように、予め決めておくことになる。もちろん、当該所定距離は、絞り込み効果が得られる適宜の距離とすることができる。
【００８１】
ステップＳ２３の処理の後、候補リンク絞込部１２２は、候補リンクを１つに絞り込めたか否かを判別する（ステップＳ２４）。ステップＳ２４の判別処理で、候補リンクを１つに絞り込めていないと判別した時には、候補リンク絞込部１２２は、道路名称の照合を行う（ステップＳ２５）。このステップＳ２５の処理は、上述した候補リンク取得処理により、各経路指示データにより指示された地点ごとに取得された候補リンクの中に、対応する経路指示データにより指示された地点が位置する道路と同じ道路名称を有するものがあるかを照合する。
【００８２】
この照合は、道路ＮＷＤＢ１０６のリンクデータの対応するリンクの名称（道路名称）を用いて行うことができる。そして、同じ道路名称を有する候補リンクを優先的に用いるように選択する。なお、対応する経路指示データにより指示された地点が道路上にない場合には、例えば、対応する経路指示データにより指示された地点に最も近い道路の道路名称と照合する。
【００８３】
例えば、対応する経路指示データにより指示された地点が位置する道路に対応したリンクの道路名称が「１２３号線」で、候補リンクの中に道路名称が「１２３号線」であるものがあれば、そのリンクを優先的に選択する。したがって、対応する経路指示データにより指示された地点が位置する道路に対応したリンクの道路名称が「１２３号線」で、候補リンクの中に道路名称が「１２３号線」であるものが１つしかなければ、候補リンクを道路名称が「１２３号線」である１つのリンクに絞り込むことができる。
【００８４】
なお、例えば、経路指示データごとに、道路名称が付加されていれば、すなわち、経路指示データが、経路指示データごとに道路名称を備えるものであれば、この経路指示データごとの道路名称と、絞り込まれたリンクのリンクデータにある道路名称を照合してもよい。すなわち、経路指示データの作成時において、例えば、タッチパネル１１０を通じて指示された地点が道路上であった場合には、その地点に合致するリンクデータ（図３）を確認し、道路種別や道路名称を取得し、緯度経度データと共に、記憶するようにしておけばよい。
【００８５】
そして、候補リンク絞込部１２２は、ステップＳ２２、ステップＳ２４において、候補リンクを１つに絞り込めたと判別した場合と、ステップＳ２５の処理の後においては、当該候補リンク絞込処理が終了したか否かを判別する（ステップＳ２６）。そなわち、ステップＳ２６の判別処理は、全ての経路指示データによって指示された地点ごとに取得した候補リンクについて、絞り込み処理が終了したか否かを判別する処理である。
【００８６】
ステップＳ２６の判別処理において、絞り込み処理は終了していないと判別した時には、ステップＳ２１からの処理を行って、次の経路指示データによって指示された地点に対して取得した候補リンクについて絞り込み処理を行うようにする。ステップＳ２６の判別処理において、全ての経路指示データによって指示された地点ごとに取得した候補リンクについて、絞り込み処理が終了したと判別した時には、この図７に示す処理を終了し、図６の処理に戻って次の処理を行うことになる。
【００８７】
このようにして、全ての経路指示データによって指示された地点ごとに取得した候補リンクについて、絞り込み処理を行い、経路指示データにより指示された地点に基づいて決まる指示ルートを絞り込むことができるようにされる。そして、この候補リンク絞込処理により、ただ１つのリンク列に絞り込むことができたときには、そのリンク列を指定ルートとして特定することができる。
【００８８】
すなわち、各経路指示データにより指示された地点のそれぞれごとに、１つのリンク、あるいは１つの方向に向かう連続するリンク列だけに絞り込めた場合には、そのリンクを接続したリンク列が、指示ルートとして特定できる。例えば、右折するリンク列や左折するリンク列が１つだけ存在する場合には、当該右折するリンク列や左折するリンク列は、１つの方向に向かう連続するリンク列になる。なお、言うまでもなく、向かう方向が異なるリンクが複数ある場合には、１つのリンクに絞り込めていないことになる。
【００８９】
［探索ルート比較処理（第３処理）］
図１２は、図６のステップＳ４において実行される検索ルート比較処理（第３処理）について説明するためのフローチャートである。この図１２に示す検索ルート比較処理は、図６に示した候補リンク取得処理（第１処理）及び候補リンク絞込処理（第２処理）を通じて指定ルートを１つに絞り込むことができなかった場合に実行される処理である。そして、この検索ルート比較処理（第３処理）は、制御部１０２の制御の下、主にルート探索部１２３及び探索ルート比較部１２４によって行われる処理である。
【００９０】
まず、制御部１０２は、ルート探索部１２３を制御して、上述した候補リンク取得処理及び候補リンク絞込処理を通じて、経路指示データにより指示される地点ごとに対応して絞り込まれたリンクを用いた複数のルートを探索する（ステップＳ３１）。この場合、ルート探索部１２３は、絞り込まれたリンクと道路ＮＷＤＢ１０６のネットワークデータをも参照しながら、出発地から目的地までのルートであって、絞り込まれたリンクを用いた複数のルートを探索する。
【００９１】
そして、この実施形態においてルート探索部１２３は、制御部１０２の制御の下、探索したルートのうち、前点から通ってきた道を戻るルート、いわゆるＵターンを行う部分を含むルートは候補から除外する処理を行う（ステップＳ３２）。次に、残ったルートについて、進行距離判定を行う（ステップＳ３３）。この進行距離判定では、例えば地図上で把握される経路指示データにより示される地点間の距離と、残ったルートごとの当該地点間を接続するリンク列についての、図３に示したリンクデータにある各リンクの距離から把握できる距離とを比較する。そして、より経路指示データにより示される地点間の距離に近いリンク列のあるルートを指定ルートとして特定する。これにより、最終的に１つの指定ルートが特定できる。
【００９２】
なお、図５に示した経路指示データの作成時において、経路指示データにより示される地点間の距離を求めておき、これを経路指示データに含めておくようにしてもよい。この場合には、この経路指示データに含まれる地点間の距離を用いて、図１２のステップＳ３３で行われる進行距離判定を行うことができる。
【００９３】
また、図１２に示したステップＳ３２までの処理により、指定ルートが１つに特定できれば、ステップＳ３３の進行距離判定を行うことなく、指定ルートは特定される。
【００９４】
このように、図６に示した候補リンク取得処理（第１処理）と候補リンク絞込処理（第２処理）を通じて１つの指定ルートが特定できない場合でも、探索ルート比較処理（第３処理）を通じて１つの指定ルートを特定できる。
【００９５】
［スコア評価の利用］
上述した実施形態のナビゲーション装置では、まず、候補リンク取得処理（第１処理）により、（１）候補ノードと候補リンクを抽出し、候補リンク絞込処理（第２処理）で、（２）候補リンクを絞り込んでいる。この候補リンク絞込処理では、（３）道路種別によるフィルタリングや（４）高速道路などの有料道路を継続して使用する場合のロジックの切り替えを行っている。すなわち、有料道路をルートとして用いる場合に、料金所などの中間点の指定を無視するロジックを用いている。また、候補リンク絞込処理では、（５）道路名称を用いた絞り込みや（６）進行角度によるリンクの絞り込みも行っている。そして、探索ルート比較処理では、（７）イレギュラールート（Ｕターンルートなど）の除去や（８）進行距離により絞り込みを行っている。
【００９６】
そして、上述した実施形態では、最も適したルートを１つを特定できる場合として説明したが、実際には複数のリンクや複数のルートについて評価していかなければならない。このため、各絞り込みの処理においては、候補リンク（リンク列）についてスコア（点数）を付けて評価し、最もスコアのよいリンク（リンク列）を優先的に利用するようにし、最もスコアのよいリンク（リンク列）を集めたルートを指定ルートとして特定するようにすればよい。
【００９７】
具体的には、例えば、道路種別や道路名称で絞り込みを行う場合には、一致すれば「１０点」、一致しなければ「０点」というように評価する。また、進行方向により絞り込む場合にも、経路指示データにより指示された地点に向かう方向に一致すれば「１０点」、一致しなければ「０点」というように評価する。
【００９８】
また、進行角度により絞り込む場合には、まず、今回の処理対象となっている経路指示データにより指示された地点Ｐ１と、次の経路指示データにより指示された地点Ｐ２とを結んだ直線Ｌと、真北方向とのなす角の角度を基準角度と求める。そして、各候補リンクについて、候補リンクの方向と真北方向とのなす角の角度（リンク角度）を求め、この求めたリンク角度がより基準角度に近いリンクのスコアを高くするように評価する。例えば、リンク角度が一番、基準角度に近いリンクを「１０点」、次に近いリンクを「９点」というように、スコアに差を付けて評価する。
【００９９】
また、進行距離により絞り込む場合にも、地図上で把握される経路指示データにより示される地点間の距離を基準距離とし、対応する点間を接続するリンク列についての、図３に示したリンクデータにある各リンクの距離から把握できる距離が、当該基準距離に対して一番近いものから順に、「１０点」、「９点」、「８点」のようにスコアを付けて評価する。
【０１００】
このように、候補リンク（候補リンク列）についてスコアにより評価を行い、一番スコアの高いリンクやリンク列をピックアップしていくことで、最適な指示ルートが作成（特定）できる。
【０１０１】
［実施形態の効果］
上述した実施形態の説明からも分かるように、この実施形態のナビゲーション装置においては、複数の地点が指示されることにより、ルートが指定される場合に、当該複数の地点の中に、本来指示されるべき地点からずれた地点が含まれていても、適切な指示ルートを作成（特定）することができる。より具体的には、図１３に示すように、タッチパネル１１０を通じて、地点ＰＡ、ＰＢ、ＰＣ、ＰＤが指定された場合を考える。この場合に、地点ＰＡは、左折すべき交差点を過ぎた地点であり、地点ＰＣは、通行すべき道路上からずれた地点であったとする。
【０１０２】
しかし、この実施形態のナビゲーション装置が有する指定ルート作成機能を用いることにより、左折すべき交差点を過ぎた地点ＰＡが指示されていても、対応する交差点を左折するルートを適切に特定できる。また、通行すべき道路上からずれた地点ＰＣが存在していても、走行すべき道路上を通り、さらに次に指定された地点ＰＤに向かうルートを適切に特定できる。これにより、図１３において実線で示したように、使用者が目的とする指定ルートＲＴを適切に作成（特定）できる。
【０１０３】
そして、図１３に示すように、使用者により指示された地点ＰＡ、ＰＢ、ＰＣ、ＰＤを示すマークと、作成（特定）した指定ルートＲＴとを示す実線とを表示部１１０Ｄに表示することにより、使用者は、指示した地点に応じた指定ルートが適切に作成されていることを確認できる。そして、作成（特定）された指定ルートを辿るように経路案内処理（ナビゲーション処理）を行うことができる。
【０１０４】
また、高速道路などの有料道路を通行するルートを指定するために、有料道路の例えば料金所付近の地点を指定したとしても、当該指定された地点で有料道路を降りてしまうという使用者が意図しないルートが作成（特定）されることもない。したがって、図１４に示すように、高速道路上を比較的に長い距離走行するルートを指定するために、各料金所付近の地点が指示された場合であっても、指示された料金所で高速道路を乗ったり、降りたりする不自然なルートが作成されることはない。この図１４に示した例の場合には、高速道路上に実線で示したように、高速道路上に連続した指定ルートＲＴを作成（特定）することができる。
【０１０５】
また、上述した実施形態のナビゲーション装置は、例えば、個人の乗用車に搭載され、個人である使用者が例えば旅行などに行く場合に利用して好適なものである。しかし、これに限るものではなく、例えば、観光バスで移動する経路を指定する場合や大型トラックが移動する経路を指定する場合など、いわゆる業務用途にも好適なものである。
【０１０６】
［変形例］
なお、上述した実施形態のナビゲーション装置においては、図５に示した経路指示データが示す地点ごとに、候補リンクを抽出して絞り込むようにしたが、これに限るものではない。例えば、連続する経路指示データが示す地点間の距離が非常に長い場合には、当該連続する経路指示データが示す地点間に、１つ以上の注目地点を設定するようにし、この注目地点についても、経路指示データにより指示される地点と同様に、候補リンクの取得と絞り込みを行って、連続するリンク列を特定しやすくするようにしてもよい。なお、注目点は、連続する経路指示データが示す地点間において、分岐発生する交差点の近傍にしたり、連続する２つの経路指示データが示す地点が位置する同じ道路上の、当該２つの経路指示データが示す地点の中間地点にしたりするなどのことができる。
【０１０７】
また、上述した実施形態のナビゲーション装置は、自動車用ナビゲーション装置であるものとして説明したが、これに限るものではない。歩行者用ナビゲーション装置、自電車用ナビゲーション装置などにも適用できる。例えば、歩行者用ナビゲーション装置に摘要した場合、経由したい地点（場所）を大まかに指定すれば、目的地に向かう適切な指定ルートを作成できる。
【０１０８】
この場合、指示した地点が、乗車すべきバス停とは反対方向のバス停側の地点を指定してしまった場合でも、ノードとリンクとを適切に絞り込んでいくことができるので、乗車するバスの行き先（進行方向）を間違えるなどのこともない。もちろん、電車、タクシーなどの他の公共交通機関を利用する場合でも同様に、行き先（進行方向）を間違えることなく、適切な指定ルートを作成（特定）できる。
【０１０９】
また、この発明は、ナビゲーション装置に摘要できるだけでなく、パーソナルコンピュータなどの情報処理装置において、地点を指定していくことにより、目的とするルートを作成する場合にも適用できる。
【０１１０】
［その他］
なお、指定ルート作成装置の各手段とナビゲーション装置の各部とを対応付けると、探索用データ記憶手段の機能は、道路ＮＷＤＢ１０６が実現し、経路指示データ記憶手段の機能は、記憶装置１０３が実現している。また、取得手段の機能は、候補リンク取得部１２１が実現し、絞込手段の機能は、候補リンク絞込部１２２が実現し、比較手段の機能は、ルート探索部１２３と探索ルート比較部１２４とが協働して実現している。また、表示手段の機能は、表示部１１０Ｄが実現し、表示制御手段の機能は、制御部１０２が実現している。
【０１１１】
また、図６、図７、図１０、図１２に示したフローチャートで説明した処理が、この発明の指定ルート作成方法の一実施形態に対応している。また、図６、図７、図１０、図１２に示したフローチャートで説明した処理を実行するプログラムが、この発明の指定ルート作成プログラムの一実施形態に対応している。
【０１１２】
また、図１に示した、候補リンク取得部１２１、候補リンク絞込部１２２、ルート探索部１２３、探索ルート比較部１２４、有料ルート作成部１２５の各部の機能は、制御部１０２で実行されるプログラムにより、制御部１０２の機能として実現することもできる。したがって、図６、図７、図１０、図１２に示したフローチャートで説明した処理を実行するプログラム作成し、これを実行することが可能なパーソナルコンピュータ、スマートフォン、タブレット端末などに搭載することにより、この発明の指定ルート作成装置を実現できる。
【符号の説明】
【０１１３】
１０１Ａ…送受信アンテナ、１０１…無線通信部、１０２…制御部、１０３…記憶装置、１０４…操作部、１０５…地図情報ＤＢ、１０６…道路ＮＷＤＢ、１０７…外部Ｉ／Ｆ、１０７Ｔ…入出力端子、１０８…センサＩ／Ｆ、１０９…ＧＰＳ部、１０９Ａ…ＧＰＳアンテナ、１１０…タッチパネル、１１０Ｄ…表示部、１１０Ｓ…タッチセンサ、１１１…音声出力部、１１２…スピーカ、１１３…音声入力部、１１４…マイクロホン、１２１…候補リンク取得部、１２２…候補リンク絞込部、１２３…ルート探索部、１２４…探索ルート比較部、１２５…有料ルート作成部
【図１】
2018040712.tif 000003
【図２】
2018040712.tif 000004
【図３】
2018040712.tif 000005
【図４】
2018040712.tif 000006
【図５】
2018040712.tif 000007
【図６】
2018040712.tif 000008
【図７】
2018040712.tif 000009
【図８】
2018040712.tif 000010
【図９】
2018040712.tif 000011
【図１０】
2018040712.tif 000012
【図１１】
2018040712.tif 000013
【図１２】
2018040712.tif 000014
【図１３】
2018040712.tif 000015
【図１４】
2018040712.tif 000016
【図１５】
2018040712.tif 000017