(57)【要約】  【課題】  多角的な目的地の選定やナビゲーションをインタラクティブに行うことのできるナビゲーションシステムを提供する。  【解決手段】  ナビゲーションシステムは、クライアント装置１とサーバ装置２で構成される。クライアント装置１のタッチパネル部３では、ユーザによるマルチタッチ入力が行われ、マルチタップ入力で入力されたデータがサーバ装置２へ送信される。サーバ装置２は、予め算出された複数の地点間の距離を距離テーブルを記憶しており、マルチタッチ入力に基づいて複数の地点の中から１つの出発地と複数の目的地を選択し、距離テーブルを参照して出発点から目的地までの経路の評価のための処理を行う。評価の結果は、クライアント装置１へ送信され、タッチパネル部３に表示される。【選択図】  図１
2014190947.tif 000002
【特許請求の範囲】
【請求項１】
クライアント装置とサーバ装置で構成されるナビゲーションシステムであって、
前記クライアント装置は、
ユーザによるマルチタッチ入力が行われるタッチパネル部と、
前記ユーザによるマルチタップ入力で入力されたデータを、前記サーバ装置へ送信する第１通信部と、
を備え、
前記サーバ装置は、
予め算出された複数の地点間の距離を、距離テーブルとして記憶するテーブル記憶部と、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択する出発地選択部と、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択する目的地選択部と、
前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行う処理部と、
前記評価の結果を前記クライアント装置へ送信する第２通信部と、
を備え、
前記評価の結果が、前記タッチパネル部に表示されることを特徴とするナビゲーションシステム。
【請求項２】
前記処理部は、前記距離テーブルを参照して、前記複数の目的地の各々について、前記出発地から前記目的地までの距離が最小となる最短経路を求めるとともに、前記最短経路の距離のリストを作成する処理を行い、
前記経路と前記リストが、前記タッチパネル部に表示される、請求項１に記載のナビゲーションシステム。
【請求項３】
前記処理部は、前記距離テーブルを参照して、前記複数の目的地の各々について、前記目的地からの距離が所定の距離範囲内である周辺地点を求める処理を行い、
前記周辺地点の情報が、前記タッチパネル部に表示される、請求項２に記載のナビゲーションシステム。
【請求項４】
前記複数の目的地は、一つの最終目的地と、複数の立寄り目的地とを含み、
前記経路は、前記出発地から前記最終目的地までにすべての前記立寄り目的地をそれぞれ一度だけ経由する巡回経路であり、
前記処理部は、前記距離テーブルを参照して、前記出発地から前記最終目的地までの距離が最小となる巡回経路を、最短巡回経路として求める処理を行い、
前記最短巡回経路が、前記タッチパネル部に表示される、請求項１に記載のナビゲーションシステム。
【請求項５】
前記距離テーブルには、前記複数の地点間のコスト値のデータが含まれ、
前記コスト値のデータは、外部装置から取得される渋滞情報に基づいて更新され、
前記処理部は、前記距離テーブルを参照して、前記出発地から前記最終目的地までのコスト値が最小となる巡回経路を、前記最短巡回経路として求める処理を行う、請求項４に記載のナビゲーションシステム。
【請求項６】
ナビゲーションシステムにおいて実行される方法であって、
前記ナビゲーションシステムは、クライアント装置とサーバ装置で構成され、前記クライアント装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部を備え、前記サーバ装置は、予め算出された複数の地点間の距離を距離テーブルとして記憶するテーブル記憶部を備え、
前記方法は、
前記クライアント装置において、前記ユーザによるマルチタップ入力で入力されたデータを、前記クライアント装置から前記サーバ装置へ送信することと、
前記サーバ装置において、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択することと、
前記サーバ装置において、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択することと、
前記サーバ装置において、前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行うことと、
前記評価の結果を前記サーバ装置から前記クライアント装置へ送信することと、
前記クライアント装置において、前記評価の結果を前記タッチパネル部に表示させることと、
を含むことを特徴とする方法。
【請求項７】
ユーザによるマルチタッチ入力が行われるタッチパネル部と、
予め算出された複数の地点間の距離を、距離テーブルとして記憶するテーブル記憶部と、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択する出発地選択部と、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択する目的地選択部と、
前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行う処理部と、
を備え、
前記評価の結果が、前記タッチパネル部に表示されることを特徴とするナビゲーション装置。
【請求項８】
ナビゲーション装置において実行される方法であって、
前記ナビゲーション装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部と、予め算出された複数の地点間の距離を距離テーブルとして記憶するテーブル記憶部と、を備え、
前記方法は、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択することと、
前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択することと、
前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行うことと、
前記評価の結果を前記タッチパネル部に表示させることと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クライアント装置とサーバ装置で構成されるナビゲーションシステムに関する。
【背景技術】
【０００２】
ナビゲーション装置は、出発地から目的地までの経路案内をするための装置である。従来のナビゲーション装置では、出発地と目的地をユーザが設定すると、出発地から目的地までの経路の探索が行われる。そして、探索された経路が、ナビゲーション装置の画面に表示されるとともに、経路に応じた音声案内がユーザに通知される（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００４−３０１５２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のナビゲーション装置では、目的地を一つしか設定することができず、例えば、ユーザの行きたい場所が複数ある場合などに、複数の目的地（候補地）を比較しながら多角的に目的地を選定するのに適していなかった。また、従来のナビゲーション装置では、目的地の選定をインタラクティブに行うことについても、何ら考慮がなされていなかった。
【０００５】
本発明は、上記の課題に鑑みてなされたもので、多角的な目的地の選定やナビゲーションをインタラクティブに行うことのできるナビゲーションシステムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のナビゲーションシステムは、クライアント装置とサーバ装置で構成されるナビゲーションシステムであって、前記クライアント装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部と、前記ユーザによるマルチタップ入力で入力されたデータを、前記サーバ装置へ送信する第１通信部と、を備え、前記サーバ装置は、予め算出された複数の地点間の距離を、距離テーブルとして記憶するテーブル記憶部と、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択する出発地選択部と、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択する目的地選択部と、前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行う処理部と、前記評価の結果を前記クライアント装置へ送信する第２通信部と、を備え、前記評価の結果は、前記タッチパネル部に表示される。
【０００７】
これにより、複数の地点間の距離が予め算出され、距離テーブルとしてテーブル記憶部に記憶されている。ユーザは、タッチパネル部でマルチタッチ入力を行って、１つの出発地と複数の目的地を指定する。そして、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して出発地から目的地までの経路の評価が行われ、評価の結果がタッチパネル部に表示される。このように、複数の目的地について経路の評価が行われるので、多角的な目的地の選定やナビゲーションが可能になる。また、マルチタッチ入力によって、目的地の選定をインタラクティブに行うことができる。
【０００８】
また、本発明のナビゲーションシステムでは、前記処理部は、前記距離テーブルを参照して、前記複数の目的地の各々について、前記出発地から前記目的地までの距離が最小となる最短経路を求めるとともに、前記最短経路の距離のリストを作成する処理を行い、前記経路と前記リストが前記タッチパネル部に表示されてもよい。
【０００９】
これにより、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して、複数の目的地の各々について、最短経路が求められるとともに最短経路の距離のリストが作成される。そして、複数の目的地についての最短経路と距離のリストがタッチパネル部に表示される。これにより、ユーザは、経路（最短経路）とリスト（距離）を考慮して、多角的に目的地を選定することができる。
【００１０】
また、本発明のナビゲーションシステムでは、前記処理部は、前記距離テーブルを参照して、前記複数の目的地の各々について、前記目的地からの距離が所定の距離範囲内である周辺地点を求める処理を行い、前記周辺地点の情報が、前記タッチパネル部に表示されてもよい。
【００１１】
これにより、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して、複数の目的地の各々について、その目的地の周辺地点が求められ、その周辺地点の情報がタッチパネル部に表示される。これにより、ユーザは、目的地の周辺地点の情報を考慮して、多角的に目的地を選定することができる。
【００１２】
また、本発明のナビゲーションシステムでは、前記複数の目的地は、一つの最終目的地と、複数の立寄り目的地とを含み、前記経路は、前記出発地から前記最終目的地までにすべての前記立寄り目的地をそれぞれ一度だけ経由する巡回経路であり、前記処理部は、前記距離テーブルを参照して、前記出発地から前記最終目的地までの距離が最小となる巡回経路を、最短巡回経路として求める処理を行い、前記最短巡回経路が、前記タッチパネル部に表示されてもよい。
【００１３】
これにより、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の立寄り目的地と１つの最終目的地が選択されると、距離テーブルを参照して最短巡回経路（出発地から最終目的地までにすべての立寄り目的地をそれぞれ一度だけ経由し、出発地から最終目的地までの距離が最小となる巡回経路）が求められ、タッチパネル部に表示される。この場合、ユーザは、マルチタッチ入力によって、最短巡回経路の選定をインタラクティブに行うことができる。
【００１４】
また、本発明のナビゲーションシステムでは、前記距離テーブルには、前記複数の地点間のコスト値のデータが含まれ、前記コスト値のデータは、外部装置から取得される渋滞情報に基づいて更新され、前記処理部は、前記距離テーブルを参照して、前記出発地から前記最終目的地までのコスト値が最小となる巡回経路を、前記最短巡回経路として求めてもよい。
【００１５】
これにより、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の立寄り目的地と１つの最終目的地が選択されると、距離テーブルを参照して最短巡回経路（出発地から最終目的地までにすべての立寄り目的地をそれぞれ一度だけ経由し、出発地から最終目的地までのコスト値が最小となる巡回経路）が求められ、タッチパネル部に表示される。この場合、コスト値（時間）のデータは、渋滞情報に基づいて更新される。これにより、ユーザは、距離だけでなく、現在のコスト値（時間）を考慮して、多角的に目的地を選定することができる。
【００１６】
本発明の方法は、ナビゲーションシステムにおいて実行される方法であって、前記ナビゲーションシステムは、クライアント装置とサーバ装置で構成され、前記クライアント装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部を備え、前記サーバ装置は、予め算出された複数の地点間の距離を距離テーブルとして記憶するテーブル記憶部を備え、前記方法は、前記クライアント装置において、前記ユーザによるマルチタップ入力で入力されたデータを、前記クライアント装置から前記サーバ装置へ送信することと、前記サーバ装置において、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択することと、前記サーバ装置において、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択することと、前記サーバ装置において、前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行うことと、前記評価の結果を前記サーバ装置から前記クライアント装置へ送信することと、前記クライアント装置において、前記評価の結果を前記タッチパネル部に表示させることと、を含んでいる。
【００１７】
この方法によっても、上記のシステムと同様、複数の目的地について経路の評価が行われるので、多角的な目的地の選定やナビゲーションが可能になる。また、マルチタッチ入力によって、目的地の選定をインタラクティブに行うことができる。
【００１８】
本発明のナビゲーション装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部と、予め算出された複数の地点間の距離を、距離テーブルとして記憶するテーブル記憶部と、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択する出発地選択部と、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択する目的地選択部と、前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行う処理部と、を備え、前記評価の結果が、前記タッチパネル部に表示される。
【００１９】
この装置によっても、上記のシステムと同様、複数の目的地について経路の評価が行われるので、多角的な目的地の選定やナビゲーションが可能になる。また、マルチタッチ入力によって、目的地の選定をインタラクティブに行うことができる。
【００２０】
本発明の方法は、ナビゲーション装置において実行される方法であって、前記ナビゲーション装置は、ユーザによるマルチタッチ入力が行われるタッチパネル部と、予め算出された複数の地点間の距離を距離テーブルとして記憶するテーブル記憶部と、を備え、前記方法は、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から１つの出発地を選択することと、前記ユーザによるマルチタッチ入力に基づいて、前記複数の地点の中から複数の目的地を選択することと、前記距離テーブルを参照して、前記出発点から前記目的地までの経路の評価のための処理を行うことと、前記評価の結果を出力して前記タッチパネル部に表示させることと、を含んでいる。
【００２１】
この方法によっても、上記のシステムと同様、複数の目的地について経路の評価が行われるので、多角的な目的地の選定やナビゲーションが可能になる。また、マルチタッチ入力によって、目的地の選定をインタラクティブに行うことができる。
【発明の効果】
【００２２】
本発明によれば、多角的な目的地の選定やナビゲーションをインタラクティブに行うことができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施の形態におけるナビゲーションシステムのブロック図
【図２】本発明の第１の実施の形態におけるナビゲーションシステムの機能（リスト表示機能）の説明図
【図３】本発明の第１の実施の形態におけるナビゲーションシステムの機能（周辺地点探索機能）の説明図
【図４】本発明の第１の実施の形態におけるナビゲーションシステムの動作を説明するためのシーケンス図
【図５】本発明の第１の実施の形態の変形例（ナビゲーション装置）のブロック図
【図６】本発明の第２の実施の形態におけるナビゲーションシステムのブロック図
【図７】本発明の第２の実施の形態におけるナビゲーションシステムの機能（巡回経路探索機能）の説明図
【図８】本発明の第２の実施の形態におけるナビゲーションシステムの動作を説明するためのシーケンス図
【図９】本発明の第２の実施の形態の変形例（ナビゲーション装置）のブロック図
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態のナビゲーションシステムについて、図面を用いて説明する。本実施の形態では、車両用のナビゲーション装置等に用いられるナビゲーションシステムの場合を例示する。
【００２５】
（第１の実施の形態）
本発明の第１の実施の形態のナビゲーションシステムの構成を、図面を参照して説明する。図１は、本実施の形態のナビゲーションシステムの構成を示すブロック図である。図１に示すように、ナビゲーションシステムは、車両に搭載されるクライアント装置１と、センターなどに設置されるサーバ装置２とで構成されている。なお、クライアント装置１は、ユーザが所持する携帯端末などであってもよい。
【００２６】
クライアント装置１は、タッチパネル部３と制御部４と通信部５を備えている。タッチパネル部３では、ユーザによるマルチタッチ入力が行われる。制御部４は、クライアント装置１の種々の動作を制御する機能を備えている。通信部５は、サーバー装置との通信機能を備えており、マルチタップ入力で入力されたデータをサーバ装置２へ送信する。
【００２７】
サーバ装置２は、通信部６と制御部７とテーブル作成部８とテーブル記憶部９を備えている。テーブル作成部８は、経路全探索を行って複数の地点間の最短距離を算出して距離テーブルを作成する。経路全探索には、Floyd-warshall法などの公知の手法を利用できる。図２（ｂ）には、距離テーブルの一例が示されている。距離テーブルは、複数の地点間の距離を表（テーブル）の形式でまとめたものである。図２（ｂ）の距離テーブルでは、地点Ａと地点Ｂの間の距離（１．６ｋｍ）、地点Ａと地点Ｃの間の距離（３．３ｋｍ）、地点Ａと地点Ｄの間の距離（０．８ｋｍ）・・・が、表（テーブル）の形式でまとめられている。テーブル作成部８により作成された距離テーブルは、テーブル記憶部９に記憶される。
【００２８】
また、テーブル作成部８は、距離テーブルからソートテーブルを作成するソート部１０を備えている。図３（ｂ）には、ソートテーブルの一例が示されている。ソートテーブルは、ある地点からの距離が短い順に他の地点をソートしたものである。図３（ｂ）のソートテーブルでは、地点Ａからの距離が短い順に地点（地点Ｘ、Ｙ、Ｚ、Ｄ、・・・）がソートされている。ソート部１０により作成されたソートテーブルも、テーブル記憶部９に記憶される。
【００２９】
通信部６は、クライアント装置１と通信する機能を備えており、マルチタップ入力で入力されたデータをクライアント装置１から受信する。制御部７は、出発地選択部１１と目的地選択部１２と処理部１３を備えている。出発地選択部１１は、マルチタッチ入力に基づいて、複数の地点の中から１つの出発地（図２の例では出発地Ｏ）を選択する。目的地選択部１２は、マルチタッチ入力に基づいて、複数の地点の中から複数の目的地（図２の例では目的地Ａ，Ｂ、Ｃ）を選択する。
【００３０】
処理部１３は、距離テーブルを参照して、出発点から目的地までの経路の評価のための処理を行う。本実施の形態では、図２（ａ）に示すように、処理部１３は、距離テーブルを参照して、複数の目的地（目的地Ａ、Ｂ、Ｃ）の各々について、出発地から目的地までの距離が最小となる経路（最短経路）を求める。なお、経路の情報には、「遠いが直線」「曲がる回数が多い」「踏切がある」などの情報（通りやすさの情報）が付されても良い。また、処理部１３は、図２（ｂ）に示すように、複数の目的地（目的地Ａ、Ｂ、Ｃ）の各々について、最短経路の距離のリストを作成する処理を行う。なお、リストには、その経路を走行するときに必要な料金（高速道路や有料道路の料金など）が含まれても良い（図２（ｂ）参照）。処理部１３により求められた経路とリストは、通信部６からクライアント装置１へ送信され、タッチパネル部３に表示される。
【００３１】
また、図３（ａ）に示すように、処理部１３は、距離テーブルを参照して、複数の目的地（目的地Ａ、Ｂ、Ｃ）の各々について、目的地からの距離が所定の距離範囲内（例えば０．５ｋｍ以内）である周辺地点（地点Ｘ、Ｙ、Ｚ、Ｗ、Ｖ、・・・）を求める処理を行う。この場合、処理部１３は、図３（ｂ）に示すように、ソートテーブルを参照することにより、目的地（例えば、目的地Ａ）からの距離が所定の距離範囲内（例えば０．５ｋｍ以内）である周辺地点（地点Ｘ、Ｙ）を容易に求めることができる。処理部１３により求められた周辺地点の情報は、通信部６からクライアント装置１へ送信され、タッチパネル部３に表示される。
【００３２】
以上のように構成された第１の実施の形態のナビゲーションシステムについて、図４のシーケンス図を参照してその動作を説明する。
【００３３】
図４に示すように、本実施の形態のナビゲーションシステムでは、まず、サーバ装置２において、経路全探索を行ってすべての地点間の最短距離を算出して（Ｓ１）、距離テーブルを作成し（Ｓ２）、テーブル記憶部９に記憶しておく。また、距離テーブルからソートテーブルを作成して（Ｓ３）、テーブル記憶部９に記憶しておく。
【００３４】
クライアント装置１で、マルチタッチ入力により出発地と目的地の入力が行われると（Ｓ４、Ｓ５）、入力された出発地と目的地の情報がサーバ装置２へ送信される（Ｓ６）。サーバ装置２では、クライアント装置１から出発地と目的地の情報を受信すると、距離テーブルを参照して、複数の目的地（例えば、目的地Ａ、Ｂ、Ｃ）の各々について、出発地から目的地までの経路（最短経路）を求めるとともに（Ｓ７）、最短経路の距離のリストを作成する（Ｓ８）。経路とリストは、クライアント装置１へ送信され（Ｓ９）、タッチパネル部３で表示される（Ｓ１０）。
【００３５】
また、サーバ装置２では、ソートテーブルを参照して、複数の目的地（目的地Ａ、Ｂ、Ｃ）の各々について、目的地からの距離が所定の距離範囲内（例えば０．５ｋｍ以内）である周辺地点（地点Ｘ、Ｙ、Ｚ、Ｗ、Ｖ、・・・）を求める（Ｓ１１）。周辺地点の情報は、クライアント装置１へ送信され（Ｓ１２）、タッチパネル部３で表示される（Ｓ１３）。
【００３６】
このような第１の実施の形態のナビゲーションシステムによれば、多角的な目的地の選定やナビゲーションをインタラクティブに行うことができる。
【００３７】
すなわち、本実施の形態では、複数の地点間の距離が予め算出され、距離テーブルとしてテーブル記憶部９に記憶されている。ユーザは、タッチパネル部３でマルチタッチ入力を行って、１つの出発地と複数の目的地を指定する。そして、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して出発地から目的地までの経路の評価が行われ、評価の結果がタッチパネル部３に表示される。このように、複数の目的地について経路の評価が行われるので、多角的な目的地の選定やナビゲーションが可能になる。また、マルチタッチ入力によって、目的地の選定をインタラクティブに行うことができる。
【００３８】
また、本実施の形態では、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して、複数の目的地の各々について、最短経路が求められるとともに最短経路の距離のリストが作成される。そして、複数の目的地についての最短経路と距離のリストがタッチパネル部３に表示される。これにより、ユーザは、経路（最短経路）とリスト（距離）を考慮して、多角的に目的地を選定することができる。
【００３９】
また、本実施の形態では、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の目的地が選択されると、距離テーブルを参照して、複数の目的地の各々について、その目的地の周辺地点が求められ、その周辺地点の情報がタッチパネル部３に表示される。これにより、ユーザは、目的地の周辺地点の情報を考慮して、多角的に目的地を選定することができる。
【００４０】
なお、本実施の形態では、２つの装置（クライアント装置１とサーバ装置２）で構成されるナビゲーションシステムの例について説明したが、図５に示すように、１つの装置（ナビゲーション装置）でも、本実施の形態と同様の機能を実現することができる。
【００４１】
（第２の実施の形態）
次に、本発明の第２の実施の形態のナビゲーションシステムについて説明する。ここでは、第２の実施の形態のナビゲーションシステムが、第１の実施の形態と相違する点を中心に説明する。ここで特に言及しない限り、本実施の形態の構成および動作は、第１の実施の形態と同様である。
【００４２】
本実施の形態では、複数の目的地として、一つの最終目的地と複数の立寄り目的地が入力され、経路として、出発地から最終目的地までにすべての立寄り目的地をそれぞれ一度だけ経由する巡回経路が求められる。
【００４３】
図６は、本実施の形態のナビゲーションシステムの構成を示すブロック図である。図６に示すように、本実施の形態のサーバ装置２は、アルゴリズム記憶部２０を備えている。アルゴリズム記憶部２０には、出発地から最終目的地までにすべての立寄り目的地をそれぞれ一度だけ経由する巡回経路を求めるアルゴリズム（巡回セールスマン問題を解くアルゴリズム）が記憶されている。
【００４４】
サーバ装置２の処理部１３は、アルゴリズム記憶部２０に記憶されているアルゴリズムとテーブル記憶部９に記憶されている距離テーブルを参照して、出発地から最終目的地までの距離が最小となる巡回経路（最短巡回経路）を求める。例えば、図７（ａ）に示すように、出発地Ｏから最終目的地Ｕまでの距離が最小となる巡回経路（出発地Ｏ→立寄り目的地Ｐ→立寄り目的地Ｑ→立寄り目的地Ｒ→立寄り目的地Ｓ→立寄り目的地Ｔ→最終目的地Ｕ）が求められる。
【００４５】
また、図７（ｂ）に示すように、最終目的地は、出発地Ｏと同じでも良い。その場合、出発地Ｏから最終目的地Ｏまでの距離が最小となる巡回経路（出発地Ｏ→立寄り目的地Ｐ→立寄り目的地Ｑ→立寄り目的地Ｒ→立寄り目的地Ｓ→立寄り目的地Ｔ→立寄り目的地Ｕ→最終目的地Ｏ）が求められる。処理部１３により求められた巡回経路は、サーバ装置２からクライアント装置１へ送信され、タッチパネル部３に表示される。
【００４６】
また、本実施の形態では、距離テーブルに、複数の地点間のコスト値（時間）のデータが含まれる。そして、テーブル作成部８は、コスト更新部２１を備えており、コスト更新部２１は、距離テーブルのコスト値のデータを、外部装置から取得される渋滞情報に基づいて更新する。そして、処理部１３は、この距離テーブル（コスト値のデータが更新された距離テーブル）を参照して、出発地から最終目的地までのコスト値が最小となる巡回経路（最短巡回経路）を求める。
【００４７】
以上のように構成された第２の実施の形態のナビゲーションシステムについて、図８のシーケンス図を参照してその動作を説明する。
【００４８】
図８に示すように、本実施の形態のナビゲーションシステムでは、まず、サーバ装置２において、経路全探索を行ってすべての地点間の最短距離を算出して（Ｓ２１）、距離テーブルを作成し（Ｓ２２）、テーブル記憶部９に記憶しておく。そして、外部装置から取得される渋滞情報に基づいて、距離テーブルのコスト値のデータを更新する（Ｓ２３）。
【００４９】
クライアント装置１で、マルチタッチ入力により出発地と目的地（最終目的地と立寄り目的地）の入力が行われると（Ｓ２４、Ｓ２５）、入力された出発地と目的地（最終目的地と立寄り目的地）の情報がサーバ装置２へ送信される（Ｓ２６）。サーバ装置２では、クライアント装置１から出発地と目的地（最終目的地と立寄り目的地）の情報を受信すると、距離テーブルを参照して、出発地から最終目的地までの距離が最小となる最短巡回経路（例えば、出発地Ｏ→立寄り目的地Ｐ→立寄り目的地Ｑ→立寄り目的地Ｒ→立寄り目的地Ｓ→立寄り目的地Ｔ→最終目的地Ｕ）を求める（Ｓ２７）。最短巡回経路は、クライアント装置１へ送信され（Ｓ２８）、タッチパネル部３で表示される（Ｓ２９）。
【００５０】
このような第２の実施の形態のナビゲーションシステムによっても、第１の実施の形態と同様の作用効果が奏される。すなわち、多角的な目的地の選定やナビゲーションをインタラクティブに行うことができる。
【００５１】
また、本実施の形態では、ユーザによるマルチタッチ入力に基づいて、１つの出発地と複数の立寄り目的地と１つの最終目的地が選択されると、距離テーブルを参照して最短巡回経路（出発地から最終目的地までにすべての立寄り目的地をそれぞれ一度だけ経由し、出発地から最終目的地までの距離が最小となる巡回経路）が求められ、タッチパネル部３に表示される。この場合、ユーザは、マルチタッチ入力によって、最短巡回経路の選定をインタラクティブに行うことができる。
【００５２】
また、本実施の形態では、コスト値（時間）のデータが、渋滞情報に基づいて更新される。これにより、ユーザは、距離だけでなく、現在のコスト値（時間）を考慮して、多角的に目的地を選定することができる。
【００５３】
なお、本実施の形態では、２つの装置（クライアント装置１とサーバ装置２）で構成されるナビゲーションシステムの例について説明したが、図９に示すように、１つの装置（ナビゲーション装置）でも、本実施の形態と同様の機能を実現することができる。
【００５４】
以上、本発明の実施の形態を例示により説明したが、本発明の範囲はこれらに限定されるものではなく、請求項に記載された範囲内において目的に応じて変更・変形することが可能である。
【産業上の利用可能性】
【００５５】
以上のように、本発明にかかるナビゲーションシステムは、多角的な目的地の選定やナビゲーションをインタラクティブに行うことができるという効果を有し、車両用のナビゲーション装置等として有用である。
【符号の説明】
【００５６】
１  クライアント装置
２  サーバ装置
３  タッチパネル部
４  制御部
５  通信部
６  通信部
７  制御部
８  テーブル作成部
９  テーブル記憶部
１０  ソート部
１１  出発地選択部
１２  目的地選択部
１３  処理部
２０  アルゴリズム記憶部
２１  コスト更新部
【図１】
2014190947.tif 000003
【図２】
2014190947.tif 000004
【図３】
2014190947.tif 000005
【図４】
2014190947.tif 000006
【図５】
2014190947.tif 000007
【図６】
2014190947.tif 000008
【図７】
2014190947.tif 000009
【図８】
2014190947.tif 000010
【図９】
2014190947.tif 000011