(57)【要約】【課題】既存の車載用ナビゲーション装置を用いる場合であっても、既に特定されている使用者が目的とする任意のルートを案内できるようにする。【解決手段】任意ルート情報の提供を受けて、任意ルートの出発地から目的地までのルートをルート探索部３０７が探索する。このルート探索結果と任意ルートとの不一致区間を不一致区間特定部３０８が特定し、任意ルート側の不一致区間上に設定手段が経由地を設定する。この後、（１）設定した経由地を考慮した再探索→（２）不一致区間特定→（３）経由地設定の３つの処理を、任意ルートとルート探索結果との不一致区間がなくなるまで繰り替えし、出発地、目的地、１以上の中継地からなるルート探索用設定情報を生成する。【選択図】図５
2020112479.tif 000002
【特許請求の範囲】
【請求項１】
使用者が移動を予定する出発地から目的地までの任意ルートを示す任意ルート情報を受け付ける受付手段と、
前記出発地から前記目的地までのルートを探索する手段であって、１以上の経由地が設定された場合には当該経由地も考慮してルートを探索する探索手段と、
前記任意ルート情報により特定される前記任意ルートと前記探索手段でのルート探索結果との不一致区間を特定する特定手段と、
前記任意ルート上の前記不一致区間に対して経由地を設定する設定手段と、
前記任意ルートと前記ルート探索結果とが一致するまで、不一致区間を特定し、任意ルート上の不一致区間に経由地を設定し、設定された経由地をも考慮して再ルート探索を行う一連の処理を繰り返すように、前記特定手段と前記設定手段と前記探索手段とを制御する制御手段と、
前記任意ルートと前記ルート探索結果とが一致した場合に、前記出発地と、前記目的地と、前記設定手段により設定された１つ以上の前記経由地とのそれぞれを示す情報を含むルート探索用設定情報を形成して提供する提供手段と
を備えることを特徴とするルート探索用設定情報生成装置。
【請求項２】
請求項１に記載のルート探索用設定情報生成装置であって、
前記特定手段は、前記任意ルートと前記ルート探索結果とについて、ルートの形状、道路種別、道路名称、道路番号、リンク番号の１つ以上を用いて不一致区間を特定する
ことを特徴とするルート探索用設定情報生成装置。
【請求項３】
請求項１に記載のルート探索用設定情報生成装置であって
前記設定手段は、前記不一致区間の前記任意ルートと前記ルート探索結果との間で最も乖離している前記任意ルート側の地点を前記経由地として設定する
ことを特徴とするルート探索用設定情報生成装置。
【請求項４】
請求項１に記載のルート探索用設定情報生成装置であって、
前記設定手段は、前記不一致区間の前記任意ルート上の距離的な中間地点を前記経由地として設定する
ことを特徴とするルート探索用設定情報生成装置。
【請求項５】
受付手段を通じて、使用者が移動を予定する出発地から目的地までの任意ルートを示す任意ルート情報を受け付ける受付工程と、
探索手段が、前記出発地から前記目的地までのルートを探索する工程であって、１以上の経由地が設定された場合には当該経由地も考慮してルートを探索する探索工程と、
特定手段が、前記任意ルート情報により特定される前記任意ルートと前記探索手段でのルート探索結果との不一致区間を特定する特定工程と、
設定手段が、前記任意ルート上の前記不一致区間に対して経由地を設定する設定工程と、
前記任意ルートと前記ルート探索結果とが一致するまで、前記特定工程において不一致区間を特定し、前記設定工程において任意ルート上の不一致区間に経由地を設定し、前記探索工程において設定された経由地をも考慮して再ルート探索を行う一連の処理を繰り返すように、制御手段が制御する制御工程と、
前記任意ルートと前記ルート探索結果とが一致した場合に、提供手段が、前記出発地と、前記目的地と、前記設定手段により設定された１つ以上の前記経由地とのそれぞれを示す情報を含むルート探索用設定情報を形成して提供する提供手段と
を有することを特徴とするルート探索用設定情報生成方法。
【請求項６】
情報処理装置に搭載されたコンピュータが実行するプログラムであって、
受付手段を通じて、使用者が移動を予定する出発地から目的地までの任意ルートを示す任意ルート情報を受け付ける受付ステップと、
探索手段が前記出発地から前記目的地までのルートを探索するステップであって、１以上の経由地が設定された場合には当該経由地も考慮してルートを探索する探索ステップと、
特定手段が、前記任意ルート情報により特定される前記任意ルートと前記探索手段でのルート探索結果との不一致区間を特定する特定ステップと、
設定手段が、前記任意ルート上の前記不一致区間に対して経由地を設定する設定ステップと、
前記任意ルートと前記ルート探索結果とが一致するまで、前記特定ステップにおいて不一致区間を特定し、前記設定ステップにおいて任意ルート上の不一致区間に経由地を設定し、前記探索ステップにおいて設定された経由地をも考慮して再ルート探索を行う一連の処理を繰り返すように、制御手段が制御する制御ステップと、
前記任意ルートと前記ルート探索結果とが一致した場合に、提供手段が、前記出発地と、前記目的地と、前記設定手段により設定された１つ以上の前記経由地とのそれぞれを示す情報を含むルート探索用設定情報を形成して提供する提供ステップと
を実行することを特徴とするルート探索用設定情報生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、車載用ナビゲーション装置などを用いて、既に特定されている使用者が目的とする任意のルートを、案内できるようにするための装置、方法、プログラムに関する。
【背景技術】
【０００２】
車載用ナビゲーション装置（いわゆるカーナビ）は、少なくとも出発地と目的地とを設定すれば、当該出発地から当該目的地までのルート（経路）を探索できる。そして、カーナビは、探索したルートをドライバが迷うことなく辿ることができるように、地図表示などの映像と音声とによって案内を行う。このように、カーナビの基本的な用途は、目的地までのルートが分からないドライバに対して道案内を行うことにある。しかし、目的とする観光ルートを辿る場合など、ドライバが予め定めるようにした任意のルートを迷うことなく辿りたい場合もある。このような要求に対応するため、後に記す特許文献１には、簡単な操作で、ユーザが希望するルートを探索可能にするナビゲーション装置に関する発明が開示されている。
【０００３】
特許文献１に開示されたナビゲーション装置においては、まず、（１）使用者により入力される出発地と目的地とに基づいて決まる地図上において、ユーザが指やペンを用いてなぞるようにして入力する概略的な経路を受け付ける。次に、（２）入力された概略的な経路の全長距離を演算し、全長距離に応じてサンプリング間隔を設定して、そのサンプリング間隔により特定される位置に最も近い道路上の中継地を探索する。そして、（３）この探索した中継地をも用いて、出発地から目的地までのルート探索を行う。これにより、ユーザが指やペンを用いて入力した概略的な経路に応じた、出発地から目的地までのナビゲーションに利用可能なルートが探索できる。ユーザは、このようにして探索される自分が意図するルートを経路案内に利用できる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−７４４８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した特許文献１に開示された発明の場合、出発地から目的地までの距離が長くなるほど、サンプリング間隔が長くなるため、ユーザが希望するルートとかけ離れるおそれがあると考えられる。また、特許文献１に開示された発明は、ナビゲーション装置に搭載される機能であるため、既存のナビゲーション装置では簡単には利用できない。既存のナビゲーション装置で当該機能を利用可能にするためには、搭載されているソフトウェアに大幅な改良が必要になってしまう。
【０００６】
以上のことに鑑み、この発明は、既存のナビゲーション装置を用いる場合であっても、既に特定されている使用者が目的とする任意のルートを案内できるようにすることを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、この発明のルート探索用設定情報生成装置は、
使用者が移動を予定する出発地から目的地までの任意ルートを示す任意ルート情報を受け付ける受付手段と、
前記出発地から前記目的地までのルートを探索する手段であって、１以上の経由地が設定された場合には当該経由地も考慮してルートを探索する探索手段と、
前記任意ルート情報により特定される前記任意ルートと前記探索手段でのルート探索結果との不一致区間を特定する特定手段と、
前記任意ルート上の前記不一致区間に対して経由地を設定する設定手段と、
前記任意ルートと前記ルート探索結果とが一致するまで、不一致区間を特定し、任意ルート上の不一致区間に経由地を設定し、設定された経由地をも考慮して再ルート探索を行う一連の処理を繰り返すように、前記特定手段と前記設定手段と前記探索手段とを制御する制御手段と、
前記任意ルートと前記ルート探索結果とが一致した場合に、前記出発地と、前記目的地と、前記設定手段により設定された１つ以上の前記経由地とのそれぞれを示す情報を含むルート探索用設定情報を形成して提供する提供手段と
を備えることを特徴とする。
【発明の効果】
【０００８】
この発明によれば、使用者が移動を予定する出発地から目的地までの任意ルートとルート探索結果との不一致区間について、経由地を設定することができる。そして、出発地と目的地とに加えて、設定された経由地をも含むルート探索用設定情報を既存のナビゲーション装置に提供して、このルート探索用設定情報を用いてルート探索を行うようにできる。これにより、既存のナビゲーション装置を用いる場合であっても、使用者が目的とする任意ルートを特定して、当該任意ルートを案内することができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態のナビゲーションシステムの構成を説明するためのブロック図である。
【図２】実施の形態のナビゲーションシステムの携帯端末の構成を説明するためのブロック図である。
【図３】地図情報と任意ルートの例について説明するための図である。
【図４】提供要求のフォーマットの例について説明するための図である。
【図５】実施の形態のナビゲーションシステムの地図情報等提供サーバ装置の構成を説明するためのブロック図である。
【図６】地図情報等サービスサーバの道路ネットワークデータベースに格納される情報について説明するための図である。
【図７】任意ルートとルート探索結果の例について説明するための図である。
【図８】ルートの再探索結果について説明するための図である。
【図９】ルートの再探索結果について説明するための図である。
【図１０】ルートの再探索結果について説明するための図である。
【図１１】実施の形態のナビゲーションシステムの車載装置の構成を説明するためのブロック図である。
【図１２】ルート探索用設定情報の例について説明するための図である。
【図１３】実施の形態の車載装置で実行される処理を説明するためのフローチャートである。
【図１４】実施の形態の携帯端末で実行される処理を説明するためのフローチャートである。
【図１５】実施の形態の地図情報等提供サーバ装置で実行される処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１０】
以下、この発明の装置、方法、プログラムの一実施の形態について説明する。この発明の装置、方法、プログラムは、種々のナビゲーション装置に対して、新たな機能として搭載することももちろん可能である。しかし、携帯端末とサーバ装置と既存のナビゲーション装置とから構成されるシステムに対して、この発明を適用することによって、既存のナビゲーション装置においても、使用者（ユーザ）が目的とする任意ルートの案内を行うようにすることができる。このため、以下においては、この発明の装置、方法、プログラムの一実施の形態について、携帯端末とサーバ装置と既存のナビゲーション装置とからなるシステムに対して適用した場合を例にして説明する。
【００１１】
なお、この明細書において、「任意ルート」との文言は、例えば、携帯端末などに表示された地図上の道路を、使用者がマウスカーソルや指や電子ペンなどを用いてなぞるようにして指示したルートであり、使用者が通行を希望する具体的なルートを意味する。また、この明細書において、「ルート探索結果」との文言は、指示された少なくとも出発地と目的地とに基づいて、また、１つ以上の経由地が指示されたときは、当該１つ以上の経由地をも考慮して、機器のルート探索機能により自動探索されたルートの探索結果を意味する。
【００１２】
［ナビゲーションシステムの構成例］
図１は、実施の形態のナビゲーションシステムの構成を説明するためのブロック図である。この実施の形態のナビゲーションシステムは、携帯端末１と地図情報等提供サーバ装置（以下、提供サーバと略称する。）３とが、ネットワーク２を通じて接続され、相互に通信可能にされている。また、携帯端末１と車載装置４とが、例えばＢｌｕｅｔｏｏｔｈ（登録商標）規格などの近距離無線通信により接続され、少なくとも携帯端末１から車載装置４に対して情報の提供が可能にされている。
【００１３】
携帯端末１は、例えば、タブレットＰＣ（Personal Computer）やスマートホン（高機能携帯電話端末）である。携帯端末１は、使用者からの指示入力に応じて、提供サーバ３に対して、目的とする情報の提供を要求し、当該情報の提供を受けて、これを出力する機能を備える。具体的に、携帯端末１は、地図情報提供要求を提供サーバ３に送信し、提供サーバ３から目的とする地図情報の提供を受けて、これを自機の表示画面に表示出力することができる。
【００１４】
そして、携帯端末１は、自機の表示画面に表示した地図を通じて、使用者が通行を希望する任意ルートの指示入力を受け付け、当該任意ルートを示す情報（任意ルート情報）を含み、当該任意ルートを探索可能にするためのルート探索用設定情報の提供要求を形成する。そして、携帯端末１は、形成したルート探索用設定情報の提供要求（設定情報提供要求）を提供サーバ３に送信し、提供サーバ３からルート探索用設定情報の提供を受けて、これを近距離無線通信により出力して車載装置４に提供する。
【００１５】
ネットワーク２は、主にインターネットであるが、携帯端末１や提供サーバ３からインターネットまでをつなぐ携帯電話網、電話網、無線ＬＡＮ（Local Area Network）などをも含む。図１において、参照符号２Ｂ（１）は、例えば、携帯電話網の基地局や無線ＬＡＮのアクセスポイントである。
【００１６】
提供サーバ３は、地図情報データベースや道路ネットワークデータベースを備え、携帯端末１からの要求に応じて、地図情報を抽出して携帯端末１に提供したり、ルート探索用設定情報を生成して、携帯端末１に提供したりする機能を実現する。車載装置４は、既存の車載ナビゲーション装置である。車載装置４は、近距離無線通信により携帯端末１からのルート探索用設定情報の提供を受けて、これに基づいてルート探索を行うことにより、使用者が目的とする任意ルートを特定する。そして、車載装置４は、特定した任意ルート上を辿ることができるように経路案内（ナビゲーション）を行う。
【００１７】
このように、この実施の形態のナビゲーションシステムにおいては、携帯端末１と提供サーバ３とが協働し、使用者が入力するようにした任意ルートを車載装置４において探索するためのルート探索用設定情報を形成する。当該ルート探索用設定情報を携帯端末１から車載装置４に提供し、車載装置４において、当該ルート探索用設定情報を用いてルート探索を行う。これにより、車載装置４において使用者が移動を希望する任意ルートが特定され、この特定された任意ルートを辿るように経路案内（ナビゲーション）を行うことができるようにしている。
【００１８】
この実施の形態においては、携帯端末１と車載装置４とは同一の使用者によって使用されるものとして説明する。そして、図１においては、同一の使用者によって使用される対になる携帯端末１と車載装置４とは、それぞれ１つずつしか示していないが、実際にはその他の多数の使用者ごとに、多数の携帯端末１と車載装置４とが存在する。以下に、この実施の形態のナビゲーションシステムを構成する携帯端末１、提供サーバ３、車載装置４のそれぞれの構成等について説明する。
【００１９】
［携帯端末１の構成］
図２は、携帯端末１の構成を説明するためのブロック図である。無線通信アンテナ１０１Ａ及び無線通信部１０１は、ネットワーク２を通じての通信機能を実現する。制御部１０２は、図示しないが、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、不揮発性メモリなどが接続されて構成されたいわゆるマイクロプロセッサである。制御部１０２は、種々のプログラムを実行して携帯端末１の各部を制御する。記憶装置１０３は、比較的に容量の大きな半導体メモリとそのドライバとを備え、データの書き込み、読み出し、書き換え、削除などを行う。また、記憶装置１０３は、種々の処理の途中結果を保持する作業領域としても用いられる。
【００２０】
操作部１０４は、電源のオン／オフボタンや幾つかのファンクションボタンなど、複数のいわゆるハードウェアキーを備え、使用者からの指示入力を受け付ける。近距離無線アンテナ１０５Ａ及び近距離無線通信部１０５は、例えばＢｌｕｅｔｏｏｔｈ（登録商標）規格の近距離無線通信機能を実現し、車載装置４に対して情報を提供する場合に用いられる。ＧＰＳアンテナ１０６Ａ及びＧＰＳ部１０６は、自機の現在位置を測位する機能を実現する。また、携帯端末１は、ユーザインターフェースとして、タッチパネル１０７を備える。タッチパネル１０７は、ＬＣＤ（Liquid Crystal Display）などの薄型の表示部（表示装置）１０７Ｄの表示画面の全面に対応するようにタッチセンサ１０７Ｓを設けて構成されたものであり、表示機能と入力機能とを実現する。
【００２１】
地図情報提供要求部１０８は、制御部１０２の制御の下、出発地を示す情報を含み、当該出発地が属する所定エリアの地図の提供を要求する地図情報提供要求を形成する。そして、地図情報提供要求部１０８は、形成した地図情報提供要求を無線通信部１０１及び無線通信アンテナ１０１Ａを通じてネットワーク２に送出し、提供サーバ３に送信する。これにより、提供サーバ３においては、当該地図情報提供要求に応じて、出発地が属する所定エリアの地図情報を抽出し、これを携帯端末１に提供する。
【００２２】
提供された地図は表示部１０７Ｄに表示され、任意ルートの指示入力の受け付けなどに用いられる。なお、出発地は、携帯端末１のＧＰＳ部１０６を通じて取得された現在地を用いることできるし、住所や電話番号を用いて指示することもできる。また、郵便番号を用いて大まかな地域を指定して地図情報の提供を受け、この提供を受けた地図上で出発地を指示するなどのことも可能である。
【００２３】
図３は、提供サーバ３より提供されて表示部１０７Ｄに表示された地図情報と使用者によって指示された任意ルートの例について示す図である。出発地Ｓを含む所定エリアの地図情報が提供サーバ３から提供され、これが制御部１０２の制御により、図３に示すように表示部１０７Ｄに表示される。表示部１０７Ｄに表示された地図情報は、縮小したり拡大したり、上下左右にスクロールさせたりすることが可能であり、不足する地図情報は、順次に提供サーバ３に提供を要求して、その提供を受けることができる。
【００２４】
そして、図３に示すように、携帯端末１の使用者は、表示部１０７Ｄに表示された地図上において、指ｆｇなどを用いて通行しようとする道路上をなぞることによって、任意ルートの入力を行うことができる。図３に示した例の場合には、出発地Ｓから目的地Ｇに向かうルートとして、内陸の「国道○○号線」を辿る最短ルートではなく、「○○湾」を望む太線で示した「□□湾岸道路」を利用するルートを任意ルートとして入力した場合を示している。
【００２５】
なお、図３に示した例の場合には、出発地Ｓと目的地Ｇとが１画面中に存在している場合を示しているが、これに限るものではない。出発地Ｓと目的地Ｇとが離れているために、出発地Ｓと目的地Ｇとを１画面中に納まるようにした場合には、細かなルートの指示が行えない場合もある。このような場合には、所定の縮尺の地図情報を、地図をスクロールさせながら複数の画面に渡って表示するようにし、任意ルートの指示を行うようにすることもできる。このようにすれば、より細かな道路（リンク）の選択も可能になる。
【００２６】
設定情報提供要求部１０９は、制御部１０２の制御の下、タッチパネル１０７を通じて入力された任意ルート情報を含み、当該任意ルートを車載装置４でルート探索するためのルート探索用設定情報の提供を要求する設定情報提供要求を形成する。そして、設定情報提供要求部１０９は、形成した設定情報提供要求を無線通信部１０１及び無線通信アンテナ１０１Ａを通じてネットワーク２に送出し、提供サーバ３に送信する。これにより、提供サーバ３において、当該設定情報提供要求に応じて、任意ルートを探索するためのルート探索用設定情報の生成処理が実行されて、ルート探索用設定情報が生成される。そして、この生成されたルート探索用設定情報が携帯端末１に提供され、例えば、記憶装置１０３の所定のエリアに記憶保持される。
【００２７】
図４は、携帯端末１で生成される提供要求のフォーマットの例について説明するための図である。携帯端末１で形成される提供要求は、図４に示すように、端末ＩＤ（端末識別情報）、種別、必要データからなる。端末ＩＤは、当該提供要求の送信元の携帯端末１を特定するための情報であり、この実施の形態ではＩＰ（Internet Protocol）アドレスが用いられる。種別は、当該提供要求が、何を要求するものであるかを示す情報であり、この実施の形態においては、「０」であれば、地図情報提供要求であり、「１」であれば設定情報提供要求であるものとされる。なお、設定情報提供要求は、上述もしたようにルート探索用設定情報の提供を要求するものである。
【００２８】
また、必要データは、地図情報提供要求の場合には出発地の緯度経度であり、設定情報提供要求の場合には任意ルートを特定することが可能な任意ルート情報である。なお、任意ルート情報は、図３において、リンクＬａ、Ｌｂ、Ｌｃ、Ｌｄ、Ｌｅ、Ｌｆ、Ｌｇ、Ｌｈが示すように、出発地から目的地までを接続する道路のリンク番号などからなる情報である。もちろん、リンク番号だけでなく、道路名称や道路番号など、入力された任意ルートを特定することが可能な種々の情報を用いることができる。図３を用いて説明した提供要求が、地図情報提供要求部１０８、設定情報提供要求部１０９において生成されて、提供サーバ３に送信される。
【００２９】
設定情報提供部１１０は、上述したように、記憶装置１０３に記憶保持された任意ルートを探索するためのルート探索用設定情報を、近距離無線通信部１０５及び近距離無線アンテナ１０５Ａを通じて送出し、車載装置４に提供する処理を行う。このように、携帯端末１は、地図情報の提供を受けて、当該地図を通じて任意ルートの指示入力を受け付ける。そして、携帯端末１は、当該任意ルートの探索を可能にするためのルート探索用設定情報の提供を要求し、これに応じて提供されたルート探索用設定情報を車載装置４に提供する処理を行う。
【００３０】
［地図情報等提供サーバ装置３の構成］
図５は、提供サーバ３の構成を説明するためのブロック図である。接続端３０１Ｔ及び通信Ｉ／Ｆ３０１は、ネットワーク２を通じての通信機能を実現する。制御部３０２は、図示しないが、ＣＰＵ、ＲＯＭ、ＲＡＭ、不揮発性メモリが接続されて構成されたいわゆるマイクロプロセッサであり、種々のプログラムを実行して提供サーバ３の各部を制御する。記憶装置３０３は、例えば、大容量のハードディスクとそのドライバとを備え、データの書き込み、読み出し、書き換え、削除などを行うものであり、種々の処理の途中結果を保持する作業領域としても用いられる。
【００３１】
地図情報データベース（以下、地図情報ＤＢ略称する。）３０４は、経路案内にも利用可能な市街図、道路図、広域図、地方図、全国図を表示するための地図情報を記憶する。市街図、道路図、広域図、地方図、全国図を表示するための地図情報は、地図を描画するための例えばベクトルデータやラスタデータ、注記（注釈）データなどを含む。
【００３２】
道路ネットワークデータベース（以下、道路ＮＷＤＢと略称する。）３０５は、経路探索に用いられる道路に関するネットワークデータを記憶保持する。図６は、道路ＮＷＤＢ３０５に格納される自動車用のネットワークデータの例を説明するための図である。図６（Ａ）は、ネットワークの一例を示している。ネットワークデータは、ノードデータとリンクデータとからなる。ノードデータは、ランドマーク、建物、施設、交差点、分岐点などの地点を表す。また、リンクデータは、ノードデータを結ぶ線分によって、国道、県道などの自動車が通行可能な道路などを示す。図６（Ａ）に示したネットワークの例は、４つのノードデータ（Ｎ１〜Ｎ４）と４つのリンクデータ（Ｌ１〜Ｌ４）とによって構成されている。
【００３３】
図６（Ｂ）は、図６（Ａ）に示した例のネットワークの場合のノードデータの構成を示している。各ノードデータには、各ノードの識別情報（Ｎ１、Ｎ２、…）と、そのノードの位置を示す緯度、経度情報と、ノード種別とが対応付けられている。ノード種別は、当該ノード部分が、交差点、分岐点などのどれであるかを示すものである。そして、図６（Ｂ）に示した例の場合、ノードＮ１〜Ｎ４は全て交差点であることが示されている。
【００３４】
図６（Ｃ）は、図６（Ａ）に示した例のネットワークの場合のリンクデータの構成を示している。各リンクデータには、各リンクの識別情報（Ｌ１、Ｌ２、…）と、そのリンクを構成するノードの識別情報（Ｎ１、Ｎ２、…）と、リンクコストと、種別と、道路名称と、道路番号と、その他とが対応付けられている。通常、リンクコストは、そのリンクの長さ（距離）、あるいは、通行に要する時間によって定められる。
【００３５】
そして、リンクコストは、例えばダイクストラ法により、リンクコストが最小となるルート（経路）を探索する場合に参照される。種別は、当該リンク部分が、国道、県道、市道、私道などのどれであるかを示すものである。道路名称は、例えば、「○○街道」、「□□通り」、「△△道路」といった、対応するリンクが構成する道路に付けられている名称を示す。また、道路番号は、対応するリンクが構成する道路に付けられている番号を示す。その他の情報としては、車線数や通常上の規制情報など、必要情報を保持することが可能である。
【００３６】
この図６を用いて説明したような、リンクデータとノードデータとが道路ネットワークＤＢ３０５に格納されている。なお、道路ＮＷＤＢ３０５に格納されているデータについては、変更が生じるごとに必要なタイミングで更新され、正確な情報が管理できるようになっている。なお、ネットワークデータの例として、リンクデータとノードデータからなる道路ネットワークデータについて説明したが、経路探索に利用可能であり、道路に関する情報を記憶保持できるデータであれば、これに限られない。
【００３７】
地図情報提供部３０６は、携帯端末１から地図情報提供要求を受信した場合に、制御部３０２の制御の下、地図情報提供要求に含まれる出発地を示す情報により特定される出発地を含む地域の地図情報を地図情報ＤＢ３０４から抽出する。そして、地図情報提供部３０６は、抽出した地図情報を通信Ｉ／Ｆ３０１及び接続端３０１Ｔを通じてネットワーク２に送出し、要求元の携帯端末１に対して提供する。
【００３８】
ルート探索部３０７、不一致区間特定部３０８、経由地設定部３０９、設定情報提供部３１０のそれぞれは、携帯端末１からの設定情報提供要求を受信した場合に、制御部３０２の制御の下にそれぞれが機能する。以下、各部の機能について説明する。ルート探索部３０７は、設定情報提供要求に含められる任意ルートを示す情報により特定される出発地と目的地とを用いて、当該出発地から目的地までのいわゆる推奨ルートを探索する。この推奨ルートは、例えばダイクストラ法を用いてリンクコストが最小になるように探索されたルートである。
【００３９】
図７は、任意ルートとルート探索結果の例について説明するための図である。図７において、点線で示した出発地Ｓから目的地Ｇに至るルートが、図３を用いて説明したように、携帯端末１の使用者によって入力された任意ルートであり、設定情報提供要求の任意ルート情報により特定される。この例において、任意ルートは、出発地Ｓ→リンクＬａ→Ｌｂ→Ｌｃ→Ｌｄ→Ｌｅ→Ｌｆ→Ｌｇ→Ｌｈ→目的地Ｇに至るルートである。
【００４０】
また、図７において、太線で示した出発地Ｓから目的地Ｇに至るルートが、任意ルートの出発地Ｓと目的地Ｇの２地点を設定情報として用いて、ルート探索部３０７において探索されることにより得られたルート探索結果である。この例において、ルート探索結果は、出発地Ｓ→リンクＬｗ→Ｌｘ→Ｌｙ→Ｌｚ→Ｌｈ→目的地Ｇに至るルートである。このように、提供サーバ３においては、携帯端末１からの設定情報提供要求に含まれる任意ルート情報により使用者によって設定された任意ルートを把握することができると共に、ルート探索部３０７の機能によって、ルート探索結果も得ることができる。
【００４１】
不一致区間特定部３０８は、設定情報提供要求に含まれる任意ルート情報により特定される任意ルートと、ルート探索部３０７によるルート探索結果とを比較し、不一致区間を特定する。この不一致区間の特定は、地図上に表現された任意ルートとルート探索結果との形状の違い、道路ＮＷＤＢ３０５のネットワークデータにより特定される道路種別、道路名称、道路番号、あるいはデータ上のリンク番号の比較によって行うことができる。図７に示した例の場合、任意ルートのリンクＬｂ、Ｌｃ、Ｌｄ、Ｌｅ、Ｌｆ、Ｌｇからなる区間と、ルート探索結果のリンクＬｗ、Ｌｘ、Ｌｙ、Ｌｚからなる区間とが不一致区間であると特定できる。
【００４２】
経由地設定部３０９は、不一致区間特定部３０８によって特定された任意ルートとルート探索結果との不一致区間のハウスドルフ距離を計測し、任意ルートとルート探索結果との間で最も乖離した地点を探し出す。そして、経由地設定部３０９は、探し出した乖離した地点のうち、任意ルート側の地点を経由地として設定する。なお、ハウスドルフ距離は、簡単には、任意ルート上の地点からルート探索結果上の地点までの最短距離を求めたもののうちの最大値を意味する。
【００４３】
なお、ここではハウスドルフ距離を用いるようにしたが、これに限るものではない。簡単には、不一致区間のうち、任意ルート側の距離的な中間地点を経由地としてもよい。例えば、任意ルート上の地点ａから地点ｂまでがルート探索結果とは不一致であった場合に、当該任意ルート上の地点ａから地点ｂまでの区間の中間地点ｃを、経由地として設定するようにしてもよい。
【００４４】
このようにして、（１）出発地から目的地までのルート探索、（２）任意ルートと探索結果の不一致区間の特定、（３）不一致区間の任意ルート側への経由地の設定を行ったとする。この場合、制御部３０２は、（３）で設定した経由地をも考慮して、（１）、（２）、（３）の処理を繰り返すように、ルート探索部３０７、不一致区間特定部３０８、経由地設定部３０９を制御する。そして、任意ルートとルート探索結果との間に不一致区間がなくなるまで、上記の（１）、（２）、（３）の処理を繰り返す。
【００４５】
なお、上記の（１）、（２）、（３）を繰り返す中で、先に設定された経由地が存在している場合には、任意ルート上の出発地から目的地に向かう方向の経路距離順に経由地の順序を整理する。すなわち、任意ルート上において、実際に辿る順番で経由地が設定されていない場合には、使用者が目的とする任意ルートを探索できるようにするためのルート探索用設定情報が生成できなくなってしまうためである。
【００４６】
図８〜図１０は、ルートの再探索結果について説明するための図である。図７を用いて説明したように、ルート探索部３０７と不一致区間特定部３０８とが機能して、任意ルートとルート探索区間との間における不一致区間を特定する。上述もしたように、図７に示した例の場合、任意ルートのリンクＬｂ、Ｌｃ、Ｌｄ、Ｌｅ、Ｌｆ、Ｌｇからなる区間と、ルート探索結果のリンクＬｗ、Ｌｘ、Ｌｙ、Ｌｚからなる区間とが不一致区間である。
【００４７】
このため、経由地設定部３０９が機能して、この実施の形態においては、ハウスドルフ距離を算出し、ハウスドルフ距離が最大となる任意ルート上の位置ｋ１を経由地として設定する。そして、ルート探索部３０７は、制御部３０２の制御の下、出発地Ｓと経由地ｋ１と目的地Ｇとの３地点を用いて、再度のルート探索を行う。この再度のルート探索により得られた再探索結果が、図８において、太線で示したルートであるとする。
【００４８】
この場合、不一致区間特定部３０８が機能して、任意ルートと再探索結果との不一致区間を特定する。図８に示した例の場合には、任意ルートのリンクＬｅ、Ｌｆ、Ｌｇからなる区間と、再探索結果のリンクＬｕ、Ｌｙ，Ｌｚからなる区間が不一致区間となる。従って、再度、経由地設定部３０９が機能して、不一致区間について、ハウスドルフ距離を算出し、ハウスドルフ距離が最大となる任意ルート上の位置ｋ２を経由地として設定する。そして、ルート探索部３０７は、制御部３０２の制御の下、出発地Ｓと経由地ｋ１と経由地ｋ２と目的地Ｇとの４点を用いて、再度のルート探索を行う。この再度のルート探索により得られた再探索結果が、図９において、太線で示したルートであるとする。
【００４９】
この場合、不一致区間特定部３０８が機能して、任意ルートと再探索結果との不一致区間を特定する。図９に示した例の場合には、任意ルートのリンクＬｆ、Ｌｇからなる区間と、再探索結果のリンクＬｖ、Ｌｚからなる区間が不一致区間となる。従って、再度、経由地設定部３０９が機能して、不一致区間について、ハウスドルフ距離を算出し、ハウスドルフ距離が最大となる任意ルート上の位置ｋ３を経由地として設定する。そして、ルート探索部３０７は、制御部３０２の制御の下、出発地Ｓと経由地ｋ１と経由地ｋ２と経由地ｋ３と目的地Ｇとの５点を用いて、再度のルート探索を行う。この再度のルート探索により得られた再探索結果が、図１０において、太線で示したルートであるとする。
【００５０】
この場合、図７において点線で示した任意ルートと、図１０において太線で示した再探索結果とが一致し、不一致区間が存在しないことが確認できる。従って、出発地Ｓと目的地Ｇに加えて、経由地ｋ１、ｋ２、ｋ３の３地点を通るようにルート探索を行うと、任意ルートに一致するルート探索結果が得られることが分かる。
【００５１】
このようにして、任意ルートとルート探索結果とが一致する１以上の経由地が設定できると、制御部３０２の制御の下、設定情報提供部３１０が機能して、ルート探索用設定情報を整えて、ネットワーク２を通じて携帯端末１に提供する。当該ルート探索用設定情報は、出発地と目的地と、これらの間に設定された１以上の経由地のそれぞれの位置を示す情報からなるものである。このように、提供サーバ３は、携帯端末１からの要求に応じて、地図情報を抽出して提供したり、ルート探索用設定情報を生成して提供したりする機能を実現している。
【００５２】
［車載装置４の構成］
上述もしたように、この実施の形態の車載装置４は、既存のナビゲーション装置であって、単体で自動車用のナビゲーション機能（経路案内機能）を実現できるものである。そして、車載装置４は、出発地及び目的地の他、複数箇所（例えば５箇所）の経由地の入力を受け付けて、出発地から目的地までのルート探索を行う機能を備える。しかし、ユーザがマウスカーソルや指などを用いて、表示された地図を通じて直接に任意ルートの指示入力は行えないものである。このため、車載装置４の使用者が、任意ルートを設定してナビゲーションを行うようにするためには、出発地と目的地に加えて、適切な地点（位置）に経由地を設定し、この経由地をも考慮したルート探索を行って任意ルートを設定する必要がある。
【００５３】
しかし、適切な位置に経由地が設定できなければ、使用者が目的とする任意ルートに一致するルート探索結果は得られない。このため、手動による適切な経由地の設定は簡単ではなく、何回も経由地の設定とルート探索を行う必要が生じる場合もあり面倒である。このため、車載装置４では、上述したように、携帯端末１と提供サーバ３とが協働することにより得られるルート探索用設定情報の提供を受けて、使用者が目的とする任意ルートを探索し、これをナビゲーション（経路案内）に利用できるようにしている。
【００５４】
図１１は、車載装置４の構成を説明するためのブロック図である。受信アンテナ４０１Ａ及び交通情報受信機４０１は、例えば、ＦＭ放送に多重化されている交通情報を受信して、自機で利用可能な情報に変換する機能を有する。また、交通情報受信機４０１は、高速道路上において電波ビーコンとして送信されている交通情報を受信して、これを利用可能にしたり、主要幹線道路において光ビーコンとして送信されている交通情報を受信して、これを利用可能にしたりする機能を備える場合もある。
【００５５】
制御部４０２は、図示しないが、ＣＰＵ、ＲＯＭ、ＲＡＭ、不揮発性メモリなどが接続されて構成されたいわゆるマイクロプロセッサであり、種々のプログラムを実行して車載装置４の各部を制御する。操作部４０３は、電源のオン／オフボタンや幾つかのファンクションボタンなど、複数のいわゆるハードウェアキーを備え、使用者からの指示入力を受け付ける。記憶装置４０４は、ハードディスクとそのドライバとを備え、データの書き込み、読み出し、書き換え、削除などを行う。また、記憶装置４０４は、種々の処理の途中結果を保持する作業領域としても用いられる。
【００５６】
地図情報ＤＢ４０５は、提供サーバ３の地図情報ＤＢ３０４と同様に、経路案内にも利用可能な市街図、道路図、広域図、地方図、全国図を表示するための地図情報を記憶する。市街図、道路図、広域図、地方図、全国図を表示するための地図情報は、地図を描画するための例えばベクトルデータやラスタデータ、注記（注釈）データなどを含む。道路ＮＷＤＢ４０６は、図６を用いて説明した提供サーバ３の道路ＮＷＤＢ３０５と同様に、経路探索に用いられる道路に関するネットワークデータを記憶保持する。
【００５７】
近距離無線アンテナ４０７Ａ及び近距離無線通信部４０７は、例えばＢｌｕｅｔｏｏｔｈ（登録商標）規格の近距離無線通信機能を実現し、携帯端末１から提供されるルート探索用設定情報などを受け付ける場合に用いられる。ＧＰＳアンテナ４０８Ａ及びＧＰＳ部４０８は、自機の現在位置を測位する機能を実現する。また、車載装置４は、ユーザインターフェースとして、タッチパネル４０９を備える。
【００５８】
タッチパネル４０９は、ＬＣＤなどの薄型の表示部（表示装置）４０９Ｄの表示画面の全面に対応するようにタッチセンサ４０９Ｓを設けて構成されたものであり、表示機能と入力機能とを実現する。従って、タッチパネル４０９の表示部に地図情報や選択項目等を表示して、使用者からのタッチ入力を受け付け、その入力情報に応じた処理を制御部４０２が行うといったことが可能にされる。
【００５９】
音声出力処理部４１０及びスピーカ４１１は、音声メッセージなどの出力機能を実現する。従って、音声出力処理部４１０及びスピーカ４１１を通じて、ナビゲーション処理の実行時には、音声による案内メッセージなどが放音される。経由地等設定部４１２は、ルート探索に用いる、出発地、目的地、１以上の経由地のそれぞれを示す情報を、ルート探索部４１３に対して設定する処理を行う。ここで用いられる出発地、目的地、１以上の経由地のそれぞれを示す情報は、通常は、タッチパネル４０９を通じて受け付けたものである。
【００６０】
しかし、この実施の形態の車載装置４の場合には、近距離無線アンテナ４０７Ａ及び近距離無線通信部４０７を通じて受け付けた携帯端末１からのルート探索用設定情報に基づくものが含まれる。図１２は、携帯端末１から提供されるルート探索用設定情報の例について説明するための図である。図１２に示すように、ルート探索用設定情報は、出発地、目的地、１以上の経由地のそれぞれの位置を示す緯度経度情報からなる。なお、ルート探索用設定情報には、例えば、各地点が存在するリンクのリンク番号、道路名称、道路番号などの出発地、目的地、１以上の経由地に関する情報を含めることもできる。
【００６１】
ルート探索部４１３は、道路ＮＷＤＢ４０６のネットワークデータを用い、経由地等設定部４１２によって設定された出発地、目的地に基づいて、また、１以上の経由地が指示された場合にはこれをも考慮して、ルート探索を行う。ルート案内処理部４１４は、表示部４０９Ｄに地図情報とルート探索部４１３でのルート探索結果とＧＰＳ部４０８を通じて測位される自機の現在位置とを表示して、ナビゲーション（経路案内）を行う。ルート案内処理部４１４は、表示部４０９Ｄに表示される表示情報だけでなく、音声出力処理部４１０及びスピーカ４１１を通じて放音する音声メッセージを併用してナビゲーションを行う。
【００６２】
このように、車載装置４は、既存の車載用ナビゲーション装置であるが、上述したように、携帯端末１からのルート探索用設定情報の提供を受けて、これを用いてルート探索を行うことができるものである。これにより、車載装置４に対して手動によりルート探索に用いる情報を入力することなく、携帯端末１を通じて入力された任意ルートに一致するルートを探索し、当該探索したルートを辿ることができるようにナビゲーションを行うことができる。端的に言えば、車載装置４において、簡単に任意ルートを用いたナビゲーションが実現できる。
【００６３】
［ナビゲーションシステムを構成する各機器で行われる処理のまとめ］
次に、実施の形態のナビゲーションシステムを構成する上述した構成を有する携帯端末１、提供サーバ３、車載装置４のそれぞれにおいて実行される処理についてまとめる。
【００６４】
＜車載装置４で実行される処理＞
図１３は、車載装置４で実行される処理を説明するためのフローチャートである。車載装置４に電源が投入されると、制御部４０２の制御の下、例えば、現在位置が属する所定の地図情報を表示部４０９Ｄに表示し、ルート探索用設定情報の入力を受け付ける（ステップＳ１０１）。ステップＳ１０１では、タッチパネル４０９を通じて、出発地、目的地、１以上の経由地の使用者の直接入力を受け付けたり、また、近距離無線アンテナ及び近距離無線通信部４０７を通じて、携帯端末１からのルート探索用設定情報を受け付けたりする。
【００６５】
この後、制御部４０２の制御の下、経由地等設定部４１２が機能して、ステップＳ１０１で受け付けたルート探索用設定情報をルート探索部４１３に設定し、ルート探索を実行する（ステップＳ１０２）。そして、制御部４０２は、ステップＳ１０２の処理により得られたルート探索結果を地図情報と共に表示部４０９Ｄに表示出力し（ステップＳ１０３）、使用者が確認できるようにする。
【００６６】
当該ルート探索結果に基づいてナビゲーションを行う場合には、制御部４０２の制御の下、ルート案内処理部４１４が機能して、ナビゲーション処理を開始する（ステップＳ１０４）。そして、目的地近傍に到着したり、終了操作を受け付けたりするなどの所定の終了事象が発生したか否かを判別する（ステップＳ１０５）。ステップＳ１０５の判別処理において、終了事象は発生していないと判別したときには、ステップＳ１０５の処理を繰り返し、ナビゲーション処理を継続させて、ナビゲーション処理の終了事象が発生するのを待つ。
【００６７】
ステップＳ１０５の判別処理において、終了事象が発生したと判別したときには、この図１３に示した処理を終了させる。なお、図１３には図示しなかったが、ステップＳ１０５の判別処理において、終了事象が発生したと判別したときには、表示部４０９Ｄの表示を、現在地を含む所定エリアの単なる地図表示にするなど、所定の終了処理が行われる場合もある。
【００６８】
このように、車載装置４においては特別な処理は行われないが、携帯端末１からルート探索用設定情報の提供を受けたときには、当該ルート探索用設定情報を用いてルート探索を行うことにより、携帯端末１の使用者が設定した任意ルートを探索できる。そして、この探索した任意ルートを辿ることができるように、ナビゲーション処理を行うことができる。
【００６９】
＜携帯端末１で実行される処理＞
図１４は、携帯端末１で実行される処理を説明するためのフローチャートである。携帯端末１においては、所定のメニューから「ルート探索用設定情報取得処理」に対応する項目を選択すると、図１４に示す処理、すなわち、「ルート探索用設定情報取得アプリケーションプログラム」が制御部１０２で実行される。そして、制御部１０２の制御の下、地図情報提供要求部１０８が機能して、出発地を示す情報を取得し、この出発地を示す情報を含む地図情報提供要求（図４）を形成して、提供サーバ３に送信する（ステップＳ２０１）。
【００７０】
なお、出発地を示す情報は、ＧＰＳ部１０６を通じて測位する自機の現在位置や入力された住所などにより特定される位置などが用いられる。また、提供サーバ３のＵＲＬ（Uniform Resource Locator）は、事前に記憶装置１０３などに設定登録されており、これを用いることができるようにされている。
【００７１】
そして、携帯端末１では、自機からの地図情報提供要求に応じて、提供サーバ３から送信されて来る地図情報を受信し、記憶装置１０３を作業領域として用いて、当該地図情報を表示部１０７Ｄに表示する（ステップＳ２０２）。次に、制御部１０２は、タッチパネル１０７を通じて、表示部１０７Ｄに表示された地図上において、出発地Ｓから目的地Ｇまでのルートを例えば指などを用いてなぞるようにして入力される任意ルートの指示入力を受け付ける（ステップＳ２０３）。
【００７２】
この後、制御部１０２の制御の下、設定情報提供要求部１０９が機能して、ステップＳ２０３で受け付けた任意ルート情報を含むルート探索用設定情報の提供要求（図４）を形成し、これを提供サーバ３に送信する（ステップＳ２０４）。そして、携帯端末１では、自機からのルート探索用設定情報の提供要求に応じて、提供サーバ３から送信されて来るルート探索用設定情報を受信し、記憶装置１０３に記憶保持する（ステップＳ２０５）。
【００７３】
そして、制御部１０２の制御の下、設定情報提供部１１０が機能して、ステップＳ２０５で受信して記憶保持したルート探索用設定情報を、車載装置４に提供する処理を行う（ステップＳ２０６）。ステップＳ２０６では、使用者により無線送信を指示する操作が行われた場合には、ステップＳ２０６で記憶保持したルート探索用設定情報を、近距離無線通信部１０５及び近距離無線アンテナ１０５Ａを通じて車載装置４に送信する処理を行う。
【００７４】
また、ステップＳ２０６では、使用者により表示出力を指示する操作が行われた場合には、ステップＳ２０６で記憶保持したルート探索用設定情報を、表示部１０７Ｄに表示する。これにより、使用者は、当該表示を参照しながら手動によりルート探索用設定情報を車載装置４に入力することができるようにされる。
【００７５】
ステップＳ２０６の処理の後においては、制御部１０２は、この図１４に示す処理を終了する。このように、図１４に示す処理により、携帯端末１は、提供サーバ３と協働することによって、携帯端末１の使用者が目的とする任意ルートを車載装置４においてルート探索できるようにするためのルート探索用設定情報を取得することができる。そして、携帯端末１は、取得したルート探索用設定情報を車載装置４に入力するようにできる。
【００７６】
＜提供サーバ３で実行される処理＞
図１５は、提供サーバ３で実行される処理を説明するためのフローチャートである。提供サーバ３では、常時、制御部３０２において、図１５に示す処理を実行するようにしている。すなわち、提供サーバ３では、制御部３０２の制御の下、自機宛ての要求等を受信するようにして、受信したか否かを判別している（ステップＳ３０１）。ステップＳ３０１の判別処理において、自機宛ての要求等を受信していないと判別した時には、ステップＳ３０１からの処理を繰り返し、自機宛ての要求等の到来を待つ。
【００７７】
ステップＳ３０１の判別処理において、自機宛ての要求等を受信したと判別した時には、制御部３０２は、受信した要求等は、ルート探索用設定情報の提供要求か否かを判別する（ステップＳ３０２）。ステップＳ３０２の判別処理において、受信した要求等はルート探索用設定情報の提供要求ではないと判別したとする。この場合、制御部３０２は、受信した要求等は、地図情報の提供要求か否かを判別する（ステップＳ３０３）。
【００７８】
ステップＳ３０３の判別処理において、受信した要求等は地図情報の提供要求であると判別したとする。この場合、制御部３０２の制御の下、地図情報提供部３０６が機能し、当該提供要求に含まれる出発地を示す情報に基づいて、出発地を含む所定のエリアの地図情報を地図情報ＤＢ３０４から抽出する（ステップＳ３０４）。そして、地図情報提供部３０６は、抽出した地図情報を要求元に提要する処理を行う（ステップＳ３０５）。この後、ステップＳ３０１からの処理を繰り返す。また、ステップＳ３０３の判別処理において、受信した要求等は地図情報の提供要求ではないと判別したときには、制御部３０２は、受信した要求等に応じたその他の処理を実行し（ステップＳ３０６）、ステップＳ３０１からの処理を繰り返す。
【００７９】
また、ステップＳ３０２の判別処理において、受信した要求等はルート探索用設定情報の提供要求であると判別したとする。この場合、制御部３０２は、まず、ルート探索用設定情報の提供要求に含まれる任意ルート情報から出発地と目的地とを特定し、ルート探索部３０７を制御して、当該出発地から目的地までのルート探索を実施する（ステップＳ３０７）。これにより、提供サーバ３では、図７を用いて説明したように、提供された任意ルート情報により任意ルートを把握すると共に、当該任意ルートの出発地から目的地までのルート探索結果を把握する。
【００８０】
そして、制御部３０２は、不一致区間特定部３０８を制御して、図８を用いて説明したように、任意ルートとルート探索結果との不一致区間を特定する（ステップＳ３０８）。ステップＳ３０８では、任意ルート側の不一致区間とルート探索結果側の不一致区間との両方が特定される。そして、制御部３０２は、経由地設定部３０９を制御し、ステップＳ３０８で特定した任意ルート側の不一致区間に中継地を設定する処理を実行する（ステップＳ３０９）。
【００８１】
ステップＳ３０９では、上述もしたように、ハウスドルフ距離を算出して乖離が一番大きくなるハウスドルフ距離の時の任意ルート側の不一致区間の位置を中継地として設定する。また、簡単には、任意ルート側の不一致区間の中間地点を中継地として設定するようにしてもよい。
【００８２】
そして、制御部３０２は、ルート探索部３０７を制御し、出発地と目的地とに加えて、ステップＳ３０９で設定した中継地をも用いて、再ルート探索を実施する（ステップＳ３１０）。なお、ステップＳ３１０においては、以前に設定された経由地が存在する場合には、任意ルート上において、出発地から目的地に向かう方向に経路距離順に経由地の順番を整えて経由地を用いるようにする。
【００８３】
この後、制御部３０２は、任意ルートと、設定した中継地をも考慮したステップＳ３１０の再ルート探索により得られたルート探索結果（再ルート探索結果）との間で、まだ不一致区間が存在しているか否かを判別する（ステップＳ３１１）。ステップＳ３１１の判別処理において、まだ不一致区間が存在していると判別した時には、ステップＳ３０８からの処理を繰り返す。これにより、図８、図９、図１０を順番に用いて説明したように、順次に異なる経由地が設定され、任意ルートと経由地を考慮したルート探索結果との不一致区間が徐々に解消（消滅）する。
【００８４】
そして、ステップＳ３１１の判別処理において、不一致区間は存在していないと判別した時には、出発地、目的地、設定した１以上の経由地とに基づいて、任意ルートに一致するルートの探索ができたことを意味する。そこで、制御部３０２の制御の下、設定情報提供部３１０が機能して、例えば、図１２を用いて説明した態様のルート探索用設定情報を整えて、これを携帯端末１などの要求元の端末に提供する処理を実行する（ステップＳ３１２）。この後、制御部３０２は、ステップＳ３０１からの処理を繰り返す。
【００８５】
このように、提供サーバ３は、携帯端末１などからの要求に応じて、地図情報を提供したり、任意ルートと同一のルートを探索できるようにするルート探索用設定情報を生成して提供したりすることができきる。これにより、上述したように、携帯端末１では、マウスカーソルや指などを用いて地図上をなぞる操作により任意ルートの指示入力が可能にされる。また、携帯端末１を介してルート探索用設定情報を車載装置４に提供することによって、任意ルートを特定し、当該任意ルートを辿るようにナビゲーション処理を行うことができる。
【００８６】
［実施の形態の効果］
上述した実施の形態のナビゲーションシステムの場合には、携帯端末１において、任意ルートの指示入力を可能し、提供サーバ３において任意ルートに一致するルートのルート探索を可能にするルート探索用設定情報の生成を可能にしている。そして、提供サーバ３において生成されたルート探索用設定情報を車載装置に提供することによって、車載装置４が任意ルートの指示入力機能を備えない既存の装置であっても、車載装置４において任意ルートを特定し、当該任意ルートを辿るように案内できる。
【００８７】
すなわち、携帯端末１と提供サーバ３とが協働し、任意ルートの指示入力機能を実現すると共に、当該任意ルートを既存のナビゲーション装置で案内するための１以上の経由地を含むルート探索用設定情報に変換する。このルート探索用設定情報を既存のナビゲーション装置に提供することによって、任意ルートの特定と案内が可能になる。従って、使用者は、自分が所有する携帯端末に、「ルート探索用設定情報取得アプリケーションプログラム」をダウンロードするなどして取得し、インストールしておけば、自分が使用する既存のナビゲーション装置で任意ルートの案内機能が実現できる。
【００８８】
［変形例］
なお、上述したように、任意ルートとの間で不一致区間の無い「ルート探索結果」が計算された後に、追加した（設定した）経由地がＮ（Ｎは２以上の整数）個存在することになったとする。この場合に、１以上の経由地を取り除きルート探索を行い、この「ルート探索結果」と「任意ルート」との間に不一致が生じない場合は、その経由地を減らすこともできる。このいわゆる経由地除外機能は、制御部３０２が、設定されたＮ個の経由地の内の１つを選択して取り除き、ルート探索部３０７、不一致区間特定部３０８を制御して再処理を行うようにすることによって実現できる。
【００８９】
また、当該経由地除外機能は、設定された経由地の数が所定の値（例えば、５地点）を越えた場合に実施するようにしてもよい。このように実施する基準を設けておけば、無駄に経由地除外機能を実行することもないし、車載装置における経由地の設定可能数に対応させることも可能である。
【００９０】
また、経由地除外機能による経由地の除外処理の試行回数は、理論的には２のＮ乗回となるが、除外を試みる経由地の順番を次のように定めることにより、効率的な計算を行うことができる。例えば、  
（１）任意ルートの中央部分の経由地から試みる。
（２）隣り合う２つの経由地間の距離が近い経由地から試みる。
（３）「任意ルート」と「ルート探索結果」との乖離距離が大きいものから試みる。
というように、除外を試みる経由地を定める。
【００９１】
そして、設定された経由地が所定数以下（例えば、５地点以下）になったら経由地除外機能による経由地の除外処理を終了させる。このようにすれば、常に２のＮ乗回の除外処理を行う必要がなり、効率良く設定された経由地の整理を行うことができる。もちろん、除外対象とする設定された経由地の順番を定めることなく、何処から経由地の除外処理を行うようにしても、設定された経由地が所定数以下（例えば、５地点以下）になったら経由地除外機能による経由地の除外処理を終了させるようにしてもよい。
【００９２】
また、設定された経由地の数が所定の数をどうしても超えてしまう場合は、目的地側から近いＮ点（例えば５点）の経由地までを経由地として用い、６点目を目的地として、車載装置４に入力するようにしてもよい。この場合には、任意ルートの案内が完全でない旨をユーザに通知するようにしてもよい。
【００９３】
また、逆に、出発地側から目的地側に向かう方向にＮ点（例えば５点）の経由地までを経由地として用いるようにする。そして、５点目の経由地に至る前に、再度、任意ルートの残りの部分について、携帯端末１から提供サーバ３に対してルート探索用設定情報の提供要求を送信して、新たに設定された中継地の情報を含むルート探索用設定情報の提供を受けるようにしてもよい。
【００９４】
すなわち、任意ルートが長い場合には、当該任意ルートを複数の区間に分けて、この複数の区間ごとにルート探索用設定情報の提供を受けるようにしてもよい。この場合、その時点における最後の中継地点が目的かどうかを確認するメッセージを車載装置４において出力すれば、任意ルートの次の区間のルート探索用設定情報の提供を受けるための処理を行う契機とすることができる。
【００９５】
また、提供サーバ３の機能は、地図情報ＤＢ３０４と道路ＮＥＤＢ３０５などの記憶機能と、その他の処理機能とを、それぞれ別のサーバに設けてクラウドシステムの機能として実現することもできる。また、提供サーバ３の機能を、例えば自宅のパーソナルコンピュータに実現し、このパーソナルコンピュータと携帯端末とを有線または無線で接続可能にする。これにより、当該パーソナルコンピュータと携帯端末とで、上述した提供サーバ３と携帯端末１とからなる部分と同様の機能を実現することができる。
【００９６】
また、高機能のタブレットＰＣを用いる場合、提供サーバ３と携帯端末１との両方の機能を当該タブレットＰＣに持たせることもできる。この場合、地図情報ＤＢや道路ＮＷＤＢについては、いわゆるクラウド上に設けられているものを用いるようにすることができる。
【００９７】
［その他］
また、上述した実施の形態の説明から分かるように、請求項のルート探索用設定情報生成装置の受付手段の機能は、実施の形態の提供サーバ３の接続端３０１Ｔ及び通信Ｉ／Ｆ３０１が実現している。請求項のルート探索用設定情報生成装置の探索手段の機能は、提供サーバ３のルート探索部３０７が実現し、同ルート探索用設定情報生成装置の特定手段の機能は、提供サーバ３の不一致区間特定部３０８が実現している。また、請求項のルート探索用設定情報生成装置の設定手段の機能は、提供サーバ３の経由地設定部３０９が実現し、同ルート探索用設定情報生成装置の制御手段の機能は、提供サーバ３の制御部３０２が実現している。また、請求項のルート探索用設定情報生成装置の出力手段の機能は、提供サーバ３の主に設定情報提供部３１０が実現している。
【００９８】
また、図１３のフローチャートを用いて説明した提供サーバ３で実行される処理が、この発明によるルート探索用設定情報生成方法、ルート探索用設定情報生成プログラムの一実施の形態が適用されたものである。
【符号の説明】
【００９９】
１…携帯端末、１０１Ａ…無線通信アンテナ、１０１…無線通信部、１０２…制御部、１０３…記憶装置、１０４…操作部、１０５Ａ…近距離無線アンテナ、１０５…近距離無線通信部、１０６Ａ…ＧＰＳアンテナ、１０６…ＧＰＳ部、１０７…タッチパネル、１０７Ｄ…表示部、１０７Ｓ…タッチセンサ、１０８…地図情報提供要求部、１０９…設定情報提供要求部、１１０…設定情報提供部、２…ネットワーク、２Ｂ（１）…基地局、３…地図情報等提供サーバ装置、３０１Ｔ…接続端、３０１…通信Ｉ／Ｆ、３０２…制御部、３０３…記憶装置、３０４…地図情報ＤＢ、３０５…道路ＮＷＤＢ、３０６…地図情報提供部、３０７…ルート探索部、３０８…不一致区間特定部、３０９…経由地設定部、３１０…設定情報提供部、４…車載装置、４０１Ａ…交通情報受信アンテナ、４０１…交通情報受信部、４０２…制御部、４０３…操作部、４０４…記憶装置、４０５…地図情報ＤＢ、４０６…道路ＮＷＤＢ、４０７Ａ…近距離無線アンテナ、４０７…近距離無線通信部、４０８Ａ…ＧＰＳアンテナ、４０８…ＧＰＳ部、４０９…タッチパネル、４０９Ｄ…表示部、４０９Ｓ…タッチセンサ、４１０…音声出力処理部、４１１…スピーカ、４１２…経由地等設定部、４１３…ルート探索部、４１４…ルート案内処理部
【図１】
2020112479.tif 000003
【図２】
2020112479.tif 000004
【図３】
2020112479.tif 000005
【図４】
2020112479.tif 000006
【図５】
2020112479.tif 000007
【図６】
2020112479.tif 000008
【図７】
2020112479.tif 000009
【図８】
2020112479.tif 000010
【図９】
2020112479.tif 000011
【図１０】
2020112479.tif 000012
【図１１】
2020112479.tif 000013
【図１２】
2020112479.tif 000014
【図１３】
2020112479.tif 000015
【図１４】
2020112479.tif 000016
【図１５】
2020112479.tif 000017