経路探索装置、経路探索方法、及び経路探索処理プログラム等
【課題】ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索することが可能な経路探索装置、経路探索方法、及び経路探索処理プログラム等を提供する。
【解決手段】本発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索する。
【解決手段】本発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地点から経由地点を通って目的地点までの経路を探索する経路探索装置及び方法等の技術分野に関する。
【背景技術】
【０００２】
従来から、出発地点から目的地点に至る複数の経路候補毎に、各リンクに設定されたリンクコスト（例えば、当該リンクに対応する道路等の区間における距離、道幅等の道路属性が考慮された重みづけ）を積算して総リンクコストを求め、総リンクコストが最小の経路候補を最適経路として探索する車載用ナビゲーション装置が知られている。
【０００３】
また、特許文献１に開示されたナビゲーション装置においては、リンクコストばかりでなく、複数のリンクを接続するノードにおけるノードコストをも考慮して総コスト（総リンクコストと総ノードコストとの和）を求め、最適経路を探索するようになっている。
【０００４】
このような最適経路の探索に当たって、出発地点から目的地点までの途中にある経由地点をユーザが指定できるようにした車載用ナビゲーション装置も知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−３２９５７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、ユーザが上記経由地点を指定する意図は、その経由地点（場所）に立ち寄りたい場合と、その経由地点を通り抜けたい（通過したい）場合との２通りが想定される。例えば、その経由地点を通り抜けたい場合には、その経由地点で折り返すことなく、通り抜けるように最適経路が探索されるべきである。
【０００７】
しかしながら、その経由地点に立ち寄りたい場合は、必ずしもそうではなく、経由地点で折り返すように最適経路が探索されても問題はない場合もある。従来の車載用ナビゲーション装置においては、ユーザがその経由地点で折り返さずに通り抜けたいのか、或いは、その経由地点で折り返しても良いのかを自動的に区別することはできず、そのため、ユーザが真に意図する最適経路を探索することに不都合があった。
【０００８】
そこで、このような不都合の解消を一つの課題とし、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索することが可能な経路探索装置、経路探索方法、及び経路探索処理プログラム等を提供することを目的する。
【課題を解決するための手段】
【０００９】
上記課題を解決するため、請求項１に記載の発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする。
【００１０】
請求項２に記載の発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする。
【００１１】
請求項３に記載の発明は、経路探索装置により実行される経路探索方法であって、前記経路探索方法は、目的地点及び経由地点を設定する設定工程と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、を含み、前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする。
【００１２】
請求項４に記載の発明は、経路探索装置により実行される経路探索方法であって、前記経路探索方法は、目的地点及び経由地点を設定する設定工程と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、を含み、前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする。
【００１３】
請求項５に記載の経路探索処理プログラムの発明は、目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索するように機能させることを特徴とする。
【００１４】
請求項６に記載の経路探索処理プログラムの発明は、目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索するように機能させることを特徴とする。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係る車載用ナビゲーション装置の概要構成例を示す図である。
【図２】実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。
【図３】経路探索処理により探索され、表示された最適経路（経由地点付近のみを示す）の一例を示す図である。
【図４】実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。
【図５】経由地点が非許容地点である場合における経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【図６】経由地点が許容地点である場合における経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本願の実施形態を添付図面に基づいて説明する。なお、以下に説明する実施の形態は、車載用ナビゲーション装置に対して本願を適用した場合の実施形態である。
【００１７】
先ず、図１等を参照して、本実施形態における車載用ナビゲーション装置の構成及び機能を説明する。
【００１８】
図１は、本実施形態に係る車載用ナビゲーション装置の概要構成例を示す図である。
【００１９】
図１に示すように、車載用ナビゲーション装置Ｓは、ＧＰＳ（Global Positioning System）受信部１、センサ部２、交通情報受信部３、情報記憶部４、表示部５、音声出力部６、操作部７、及びシステム制御部８等を備えて構成されている。
【００２０】
ＧＰＳ受信部１は、衛星軌道上に配置され地球を周回するＧＰＳ衛星から出力される航法電波を、図示しないアンテナを介して受信し、受信した信号に基づいて位置情報（経度及び緯度）を検出し、ＧＰＳデータとしてシステム制御部８へ出力するようになっている。
【００２１】
センサ部２は、例えば、車速パルスに基づき車両の速度を検出する速度センサ、地磁気を利用して車両の走行方位を検出する方位センサ（ジャイロセンサ）、車両の加速度を検出する加速度センサ、車両の走行距離を検出する距離センサ等を備えており、これらのセンサによって検出された各データ（速度データ、方位データ、加速度データ、走行距離データ等）を、システム制御部８へ出力するようになっている。
【００２２】
交通情報受信部３は、例えばＶＩＣＳ（Vehicle Information and Communication System）受信機を有しており、ＦＭ多重放送、道路（主要幹線道路や高速道路）上に設置された光（赤外線）ビーコン、電波（準マイクロ波）ビーコン等から発信された道路交通情報（例えば、渋滞等の交通状況に関する情報）を受信し、システム制御部８へ出力するようになっている。
【００２３】
情報記憶部４は、例えば、ＣＤ（Compact Disc）−ＲＯＭドライブ、ＤＶＤ（Digital Versatile Disc）−ＲＯＭドライブ、又はＨＤ（Hard Disc）ドライブ等を備えており、各ドライブが、システム制御部８の制御の下、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、又はＨＤ等の記録媒体に記録された経路探索や経路案内（経路誘導）等を行うためのデータ及びプログラムを読み出し、システム制御部８へ出力するようになっている。更に、情報記憶部４におけるＨＤ等には、過去に探索された経路及び案内された経路に関する履歴情報が記憶されている。
【００２４】
ここで、経路探索や経路案内等を行うためのデータには、例えば、地図データ、ＰＯＩ（Point Of Interest）データ、リンクデータ、ノードデータ、及び経路案内データ、更には、ユーザに対し入力指示や選択指示を促すためのデータ（例えば、メニューデータ）等が含まれている。
【００２５】
上記地図データは、表示部５における表示画面上に地図を表示するための画像データ、及び各地点の座標（緯度及び経度に対応する地図上における座標（X,Y））を示すデータ等を含んでおり、例えば、地図上における複数の行政区画の境界を示す複数の行政界データ（各行政区画に対応する住所を含む）、地図上における道路を示す道路データ（各道路名、各交差点名、及び各合流点（ジャンクション）名等を含む）、地図上における複数の平面区画（例えば、施設や建物等が設置される区画）の一例としての家形を示す複数の家形データ（各家形に対応する住所、郵便番号、及び電話番号等を含む）、及び河川や山岳の平面図等の形状を示す形状データ（河川や山岳の名称等を含む）等を含んでいる。なお、地図データにおける住所、道路名、及び交差点名等には、夫々座標を示すデータが対応付けられている。
【００２６】
また、上記ＰＯＩデータは、地図上における地点の内容（例えば、施設（遊園地、テーマパーク等）や建物（住宅、マンション、ホテル、ビルディング、事務所等））を示すＰＯＩの名称、住所、電話番号、郵便番号、及びＰＯＩの座標（緯度及び経度に対応する地図上における座標（X,Y））等が含まれており、家形データに対応付けられるようになっている。
【００２７】
また、上記道路データにて示される道路は、複数の線分としてのリンクから構成され、少なくとも２つのリンクは、１つのノードで接続される。このノードは、例えば、各道路の交差点、屈曲点、分岐点、合流点（ジャンクション）、又は有料道路のインターチェン等の接点（結節点）を含む接続部分に対応する。
【００２８】
また、上記リンクデータは、上記各リンク毎に、リンクのリンクＩＤ、当該リンクが接続される２つのノードのノードＩＤ、当該リンクに対応する道路の距離（道路区間の距離）、属性、及び方位等の情報を有している（これらの情報は、各リンク毎に対応付けられている）。なお、道路の属性には、例えば、道路の幅員、道路の車線数、一方通行と双方通行の別、右左折レーンの有無等の情報が該当する。
【００２９】
更に、各リンクには、そのリンクに対応する道路の距離や道路の属性等が考慮された重みづけとしてのリンクコストが設定される。例えば、道路の距離が短い場合や、道路の幅員が広い場合には、当該区間の走行に要する時間は短くなるので、リンクコストが小さく設定される。また、リンクコストは、交通情報受信部３により得られた渋滞等の交通状況により変化する（例えば、渋滞の場合、そのリンクに対応するリンクコストが小さく設定される）ようになっている。
【００３０】
また、上記ノードデータは、上記各ノード毎に、ノードのノードＩＤ、当該ノードの座標（緯度及び経度に対応する地図上における座標（X,Y））、及び当該ノードに接続されるリンクのリンクＩＤ等の情報を有している。
【００３１】
更に、各ノードには、１のリンクに対応する道路からそのノードに対応する接続部分を介して他のリンクに対応する道路への車両の移動（直進、右左折等）の困難さをあらわす重みづけとしてのノードコストが設定される。一例を挙げると、幅員が広い道路から交差点を介して狭い道路へ車両が右折する場合には、曲がりにくいので、ノードコストが大きく設定される。
【００３２】
これらのリンクデータ及びノードコストは、最適経路（例えば、出発地点（例えば現在地点、現在地点から先の地点でも良い）から目的地点までの最短距離の経路、出発地点から目的地点までの最短時間の経路等）の算出に用いられる。なお、折り返しコストについての詳細は後述する。
【００３３】
また、上記経路案内データには、後述する経路案内に用いられる画像データ、文字データ、及び音声データ等が含まれる。
【００３４】
なお、経路探索や経路案内（経路誘導）を行うためのデータ及びプログラムは、情報記憶部４に記録する代わりに、例えば、インターネット及び移動体通信網（無線基地局を含む）等を含む通信ネットワークに接続された所定のサーバに記憶保存しておき、適宜、当該サーバから送信され、システム制御部８へ出力されるように構成しても良い。
【００３５】
表示部５は、例えば、描画処理部、バッファメモリ及びディスプレイ（例えば、液晶ディスプレイ、又は有機ＥＬディスプレイ等）等を備えており、描画処理部が、システム制御部８の制御の下、上記地図データや、経路案内に係る画像データをバッファメモリに展開、描画した後、ディスプレイにおける表示画面に表示（例えば、地図表示、経路表示、経路の距離や料金等の一覧表示等）するようになっている。また、当該表示画面には、システム制御部８の制御の下、ユーザに対し入力指示や選択指示を促すための例えばメニューも表示される。
【００３６】
音声出力部６は、例えば、ＤＡＣ（デジタル／アナログ信号変換器）、アンプ、スピーカ等を備えており、システム制御部８から出力された経路案内に係る音声データをＤＡＣによりＤ／Ａ変換した後、アンプにより増幅してスピーカから音波として出力するようになっている。
【００３７】
操作部７は、ユーザからの入力指示や選択指示（例えば、目的地点の指示）等を受け付けるための複数の操作ボタンを有しており、ユーザにより押下された操作ボタンに対応する指示信号をシステム制御部８へ出力するようになっている。また、上記ディスプレイにおける表示画面に表示された地図は、ユーザからの操作部７を介した指示によりスクロール表示可能になっており、当該地図上における任意の地点を、ユーザが操作部７を介して目的地点又は経由地点として指定可能になっている。
【００３８】
システム制御部８は、演算機能を有するＣＰＵ、作業用ＲＡＭ、各種データやプログラムを記憶するＲＯＭ等を備えており、当該ナビゲーション装置Ｓにおける構成要素全体を統括制御するようになっている。そして、システム制御部８のＣＰＵが、例えば情報記憶部４に記憶された経路探索や経路案内等を行うためのプログラム（本願の経路探索処理プログラムを含む）を読み出し実行することにより、本願の地図表示制御手段、設定手段、及び経路探索手段等として機能するようになっている。
【００３９】
より具体的には、システム制御部８は、経路探索処理において、ユーザからの操作部７を介して指定された目的地点及び経由地点（経由地点の設定は任意）を設定し、出発地点（例えば現在地点）から、当該目的地点までの（経由地点が設定されている場合、設定された道路上の経由地点、又は設定された道路上にない経由地点の近傍に存在するある道路上（例えば、当該経由地点ら最も近い道路（経路を構成する路）上）の路上地点（以下、「経由地近傍地点」という）を通って）最適経路を探索するようになっている。
【００４０】
ここで、目的地点又は経由地点は、例えば表示部５における表示画面に表示されたメニューから選択可能なＰＯＩ検索（例えば、予めＰＯＩデータに登録されているＰＯＩの名称から検索）、住所検索（例えば、予め地図データ又はＰＯＩデータに登録されている住所から検索）、電話番号検索（例えば、予め地図データ又はＰＯＩデータに登録されている電話番号から検索）、道路検索（予め地図データに登録されている道路名から検索）、又は交差点等検索（予め地図データに登録されている交差点名、合流点名等から検索）等において、ユーザが操作部７を介して検索条件を指定することにより検索された内容から指定可能になっている。また、ユーザが操作部７を介して表示画面にスクロール可能に表示された地図上における任意の地点を目的地点又は経由地点として指定可能になっている。もちろん、ユーザが操作部７を介して所望の名称の文字入力することにより、目的地点又は経由地点として指定することもできる。こうして指定された目的地点及び経由地点の位置情報（緯度及び経度に対応する地図上における座標（X,Y））は、システム制御部８により認識される。なお、経由地点とは、１つの点（ドット）を示すことに限定されるものではなく、所定の範囲（例えば、道路検索の場合、当該検索された道路名に対応する一定距離の範囲）を示す場合もある。
【００４１】
また、現在地点の位置情報（緯度及び経度に対応する地図上における座標（X,Y））は、システム制御部８により、センサ部２からの速度データ、方位データ、及び加速度データ等、並びにＧＰＳ受信部１からのＧＰＳデータに基づいて算出され、認識される。なお、車両の現在地点の位置情報の算出方法は、公知の技術であるので、更なる詳しい説明を省略する。
【００４２】
そして、出発地点から目的地点までの最適経路の探索にあっては、システム制御部８は、例えば、出発地点から目的地点に至る経路候補を構成する複数のリンクの夫々のリンクコストを取得し、これらのリンクコストに基づいて各経路候補の総リンクコストを計算し、更に、上記少なくとも２つ以上のリンクを接続する複数のノードにおける夫々のノードコストを取得し、これらのノードコストに基づいて各経路候補の総ノードコストを計算する。そして、システム制御部８は、上記算出された総リンクコスト及び総ノードコストとの和である総コストを、各経路候補毎に算出して、そのうち、総コストが小さい（例えば、最小の）経路候補を最適経路として探索する。
【００４３】
更に、最適経路の探索にあたって、経由地点が設定されているとき、システム制御部８は、当該設定された道路上の経由地点、又は上記設定された道路上にない経由地点の近傍に存在するある道路上の経由地近傍地点が折り返すことを許容する許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ目的地点までの経路を探索するようになっている。一方、システム制御部８は、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを抑制しつつ目的地点までの経路を探索するようになっている。
【００４４】
一例として、設定された経由地点が、ユーザが立ち寄りたい立寄地点である場合、道路上の当該経由地点又は経由地近傍地点は折り返すことを許容する許容地点となり（つまり、ユーザが目的地点に行くまでの間で立ち寄ることを目的に経由地点として指定すると考えられるため）、折り返す経路の総コストが最小（折り返さない経路の総コストより小さい）であれば、当該折り返す経路が最適経路として探索される（上記道路上の経由地点又は経由地近傍地点での方向を考慮せず、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容した経路探索）。一方、例えば、上記道路上の経由地点又は上記経由地近傍地点が、ユーザが通過したい（折り返さずに直進して通り抜けたい）通過地点である場合には、上記道路上の経由地点又は上記経由地近傍地点は折り返すことを許容しない非許容地点となり（つまり、ユーザが上記道路上の経由地点又は上記経由地近傍地点を通って目的地点に行きたい（例えば、運転のし易さ）と考えられるため）、折り返す経路の総コストが最小であっても、当該折り返す経路は最適経路として探索されない（上記道路上の経由地点又は上記経由地近傍地点での方向を考慮し、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない経路探索）。なお、許容地点とは、１つの点（ドット）を示すことに限定されるものではなく、所定の範囲（例えば、道路検索の場合、当該検索された道路名に対応する一定距離の範囲）を示す場合もある。
【００４５】
また、別の例として、設定された経由地点に対して、折り返す困難さをあらわす重みづけとしての折り返しコストを設定し、当該折り返しコストが上記総コストに加算され、折り返しコストと総コストとの和が最小である経路が最適経路として検索されるように構成しても良い。この場合、例えば、設定された経由地点が立寄地点であれば当該折り返しコストを小さく設定することにより、実質的に上記道路上の経由地点又は上記経由地近傍地点で折り返すことを許容し、その結果、折り返す経路の「総コストと折り返しコストとの和」が最小であれば、当該折り返す経路が最適経路として探索される。一方、上記道路上の経由地点又は上記経由地近傍地点が通過地点であれば当該折り返しコストを大きく（例えば、当該折り返し経路が最適経路として探索されない程度の大きさ）設定することにより、実質的に上記道路上の経由地点又は上記経由地近傍地点で折り返すことを許容せず、当該折り返す経路は最適経路として探索されない。
【００４６】
ところで、設定された道路上の経由地点又は上記経由地近傍地点が上記許容地点であるか否か（言い換えれば、設定された経由地点等が立寄地点であるか通過地点であるか）は、例えば、経由地点の指定方法（ユーザがどのような方法で指定したか）等に応じて判断される。
【００４７】
以下にその具体例を示す。
（１）道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点である場合(下記（i）〜（iv）の場合)
（i）表示された地図上において道路（経路を構成する路）以外の所望の地点（例えば、家形上の地点、道路から所定）が経由地点として指定された場合、或いは、道路上の所望の地点が経由地点として指定され、且つ、ハウスナンバー（番地）も指定された場合
（ii）ＰＯＩ検索により所望のＰＯＩが経由地点として指定された場合
（iii）住所検索により所望の施設や建物の住所が経由地点として指定された場合
（iv）電話番号検索により所望の電話番号に対応する地点が経由地点として指定された場合
なお、上記（i）〜（iv）の場合であっても、上記指定された経由地点が道路上にない場合に、当該経由地点と、当該経由地点の近傍に存在する道路上経由地近傍地点との距離が予め設定された基準距離より短い場合は、当該経由地近傍地点を非許容地点としても良い。
（２）道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点である場合(下記（v）〜（vii）の場合)
（v）表示された地図上において道路上の所望の地点が経由地点として指定された場合
（vi）道路検索により所望の道路が経由地点として指定された場合
（vii）交差点等検索により所望の交差点又は合流点が経由地点として指定された場合
なお、上記（v）〜（vii）の場合であっても、当該経由地点を折り返さずに通過することで何十kmの遠回りする経路となると合理的であるとは言えないため、この場合に折り返す経路と、折り返さない経路との距離差が例えば所定距離（例えば、５ｋｍ）であれば、当該経由地点を許容地点として折り返しを許容するように構成することが望ましい。
【００４８】
次に、車載用ナビゲーション装置Ｓにおける経路探索処理を説明する。
【００４９】
（実施例１）
先ず、図２等を参照して、実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を説明する。
【００５０】
図２は、実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。なお、図２に示す経路探索処理は、ユーザにより目的地点及び経由地点が指定された場合における処理である。
【００５１】
先ず、ユーザは、上述したＰＯＩ検索、住所検索、電話番号検索、道路検索、又は交差点等により検索された内容から経由地点を指定、又は表示された地図上における任意の地点を経由地点として指定し、且つ目的地点を指定して、操作部７における検索実行ボタンを押下すると、図２に示す経路探索処理が開始される。なお、指定された経由地点及び目的地点は、ＲＡＭにおける所定の領域に記憶される。
【００５２】
図２に示す経路探索処理が開始されると、システム制御部８は、上記指定された経由地点及び目的地点を設定する（ステップＳ１）。
【００５３】
次いで、システム制御部８は、設定された経由地点と、当該経由地点の例えば最も近傍に存在する道路上の地点との距離を計算し（ステップＳ２）、当該計算された距離（設定された経由地点が道路上にある場合には、当該距離は「０」となる）が、予め設定された基準距離よりも短いか否かを判別する（ステップＳ３）。
【００５４】
そして、当該計算された距離が、基準距離よりも短くない（基準距離以上の）場合には（ステップＳ３：Ｎ）、当該経由地点の最も近傍に存在する経由地近傍地点が上記許容地点であるとし、システム制御部８は、上述したように、当該経由地近傍地点を折り返すことを許容した経路探索を実行（例えば、当該経由地点に対する折り返しコストを最小に設定して経路探索を実行）し（ステップＳ４）、最適経路を探索して、当該処理を終了する。
【００５５】
一方、当該計算された距離が、基準距離よりも短い場合（設定された経由地点が道路上にあるか、又は設定された経由地点が道路上になくても基準距離よりも短い場合）には（ステップＳ３：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であるとし、システム制御部８は、上述したように、当該道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない（折り返すことを抑制した）経路探索を実行（例えば、当該経由地点に対する折り返しコストを大きく設定して経路探索を実行）し（ステップＳ５）、最適経路を探索して、当該処理を終了する。
【００５６】
こうして最適経路が探索されると、システム制御部８は、経路案内処理を実行し、車両の現在地点の位置情報を認識しつつ、当該車両の現在位置が道路上に位置するか否かの整合性、いわゆるマップマッチング処理を行い、かつ、当該探索された最適経路を用いて、当該経路に関する情報（最適経路の経路（ルート）案内（誘導）、最適経路の距離や料金等）をユーザに提示、すなわち、当該情報を表示部５における表示画面上に表示させたり、音声出力部６から音声出力させたりする。
【００５７】
なお、上記処理においては、設定された、道路上にない経由地点と、当該経由地点の近傍に存在する道路上の経由地近傍地点との距離が予め設定された基準距離より短いか否かを判別することにより折り返しコストの設定を変えるようにしたが、これに限らず、例えば、基準距離との比較を行わなくとも、上記道路上にない経由地点と、上記経由地近傍地点との距離に応じて折り返しコストを変化させるようにしても良い。例えば、設定された、上記道路上にない経由地点と、上記経由地近傍地点との距離と折り返しコストとの関係を示すデータＴＢを用意し、上記計算された距離が当てはまる折り返しコストを抽出して変化させたり、該当する距離が上記データＴＢに存在しなかった場合には、一番近い距離の折り返しコストを抽出して変化させるなどが挙げられる。
【００５８】
図３（Ａ）及び（Ｂ）は、図２に示す経路探索処理により探索され、表示された最適経路（経由地点付近のみを示す）の一例を示す図である。
【００５９】
図３（Ａ）に示す例では、設定された道路上にない経由地点５１と、当該経由地点５１の近傍に存在する（例えば最も近くにある）道路上の地点５２との距離Ｘ１は、基準距離Ｙよりも短いため、当該地点５２で折り返さずに通過した最適経路が表示されている（なお、経由地点５１と地点５２とが一致する場合も同様）。一方、図３（Ｂ）に示す例では、設定された道路上にない経由地点５１と、当該経由地点５１の近傍に存在する（例えば最も近くにある）道路上の地点５２との距離Ｘ２は、基準距離Ｙ以上であるため、当該地点５２で折り返した最適経路が表示されている。
【００６０】
（実施例２）
次に、図４等を参照して、実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を説明する。
【００６１】
図４は、実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。なお、図４に示す経路探索処理も、ユーザにより目的地点及び経由地点が指定された場合における処理である。
【００６２】
先ず、実施例１と同様、ユーザは、上述したＰＯＩ検索、住所検索、電話番号検索、道路検索、又は交差点等により検索された内容から経由地点を指定、又は表示された地図上における任意の地点を経由地点として指定し、且つ目的地点を指定して、操作部７における検索実行ボタンを押下すると、図４に示す経路探索処理が開始される。
【００６３】
図４に示す経路探索処理が開始されると、システム制御部８は、上記指定された経由地点及び目的地点を設定する（ステップＳ１１）。
【００６４】
次いで、システム制御部８は、上記設定された経由地点が、表示された地図上から指定されたものであるか否かを判別し（ステップＳ１２）、地図上から指定された経由地点である場合には（ステップＳ１２：Ｙ）、更に、当該経由地点が、表示された地図上における道路上に存在する否かを判別（座標（X,Y）により判別）する（ステップＳ１３）。
【００６５】
そして、上記経由地点が、表示された地図上における道路上に存在する場合には（ステップＳ１３：Ｙ）、当該道路上の経由地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される一方、上記経由地点が、表示された地図上における道路上に存在しない場合には（ステップＳ１３：Ｎ）、当該経由地点の近傍に存在する道路上の経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６６】
一方、上記ステップＳ１２において、地図上から指定された経由地点でない場合には（ステップＳ１２：Ｎ）、システム制御部８は、上記設定された経由地点が、ＰＯＩ検索により（ＰＯＩ検索を通じて）指定されたものであるか否かを判別し（ステップＳ１４）、ＰＯＩ検索により指定されたものでない場合には（ステップＳ１４：Ｎ）、ステップＳ１５に移行し、ＰＯＩ検索により指定されたものである場合には（ステップＳ１４：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６７】
ステップＳ１５では、システム制御部８は、上記設定された経由地点が、道路検索により指定されたものであるか否かを判別し、道路検索により指定されたものでない場合には（ステップＳ１５：Ｎ）、更に、住所検索又は電話番号検索により施設や建物の住所又は電話番号が経由地点として指定されたものであるか否かを判別する（ステップＳ１６）。
【００６８】
一方、ステップＳ１５において、道路検索により指定されたものである場合には（ステップＳ１５：Ｙ）、システム制御部８は、ハウスナンバー（番地）が指定されたか否かを判別し（ステップＳ１７）、ハウスナンバーが指定されていない場合には（ステップＳ１７：Ｎ）、上記経由地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される一方、ハウスナンバーが指定されている場合には（ステップＳ１７：Ｙ）、上記経由地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６９】
一方、ステップＳ１６において、施設や建物の住所又は電話番号が経由地点として指定されたものである場合には（ステップＳ１６：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行され、施設や建物の住所又は電話番号が経由地点として指定されたものでない場合には（ステップＳ１６：Ｎ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される。
【００７０】
なお、施設や建物の住所又は電話番号が経由地点として指定されたものでない場合には（ステップＳ１６：Ｎ）、更に、他の方法（交差点等検索等）により指定された否かを判別して、折り返すことを許容する経路探索を行うか、折り返すことを許容しない経路探索を行うかを判別するように構成しても良い。
【００７１】
また、当該実施例２における経路探索処理において、上記実施例１と同様、設定された道路上の経由地点と、当該経由地点の近傍に存在する道路上の経由地近傍地点との距離を計算し、当該計算された距離が、予め設定された基準距離よりも短いか否かを判別する構成を加えても良い。例えば、ＰＯＩ検索、住所検索又は電話番号検索を通じて経由地点が指定された場合に、上記計算された距離が、予め設定された基準距離よりも短いか否かを判別して、折り返すことを許容する経路探索を行うか、折り返すことを許容しない経路探索を行うかを判別するように構成しても良い。
【００７２】
そして、ステップＳ１８における折り返すことを抑制した経路探索では、システム制御部８は、上述したように、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない経路探索を実行（例えば、当該経由地点に対する折り返しコストを大きく設定して経路探索を実行）し、最適経路を探索して、当該処理を終了する。
【００７３】
一方、ステップＳ１９における折り返すことを許容した経路探索では、上述したように、上記道路上の経由地点又は上記該経由地近傍地点を折り返すことを許容した経路探索を実行（例えば、当該経由地点に対する折り返しコストを最小に設定して経路探索を実行）し、最適経路を探索して、当該処理を終了する。
【００７４】
なお、これ以降は、実施例１と同様、経路案内処理が実行される。
【００７５】
図５及び図６は、上記経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【００７６】
図５に示す例では、道路上の経由地点が折り返すことを許容しない非許容地点となっており、当該経由地点を折り返さずに通過（経由地点手前における車両の進行方向を維持）した、目的地点までの最適経路が表示（例えば、出発地点から目的地点までの総距離が相対的に長くなっても最適経路として表示）されている。一方、図６に示す例では、道路上の経由地点が折り返すことを許容する許容地点となっており、当該経由地点を折り返した、目的地点までの最適経路が表示（例えば、出発地点と経由地点、経由地点と目的地点の夫々の区間で、純粋に最短となる経路が引かれ、最適経路として表示）されている。
【００７７】
以上説明したように上記実施形態によれば、目的地点及び経由地点を設定し、出発地点から、設定された道路上の経由地点又は設定された道路上にない経由地点の近傍に存在するある道路上の経由地近傍地点を通って、当該設定された目的地点までの経路を探索する車載用ナビゲーション装置Ｓが、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ上記目的地点までの最適経路を探索するように構成し、一方、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを抑制しつつ上記目的地点までの経路を探索するように構成したので、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００７８】
ここで、当該車載用ナビゲーション装置Ｓは、地図上における道路上にない地点が経由地点として設定された場合には、当該経由地点の近傍に存在するある道路上の経由地近傍地点を経由するように目的地点までの経路を探索するように構成されており、設定された道路上にない経由地点の上記地図上の位置に応じて、上記経由地近傍地点を折り返した経路の探索、または上記経由地近傍地点を折り返さずに通過する経路の探索のいずれかの探索を実行するように構成したので、地図上における道路上にない地点が経由地点として設定された場合であっても、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００７９】
また、上記経由地点の指定方法に応じて、上記道路上の経由地点又は上記経由地近傍地点が、許容地点であるか否かが判断されるように構成したので、ユーザは経由地点を指定する前に、上記経由地点等を通り抜けるか、或いは折り返しても良いかを決めた上で、その意図に合った最適な指定方法を選択することができる。
【００８０】
また、ユーザにより指定され、設定された経由地点と、その経由地点の近傍に存在する道路上の経由地近傍地点との距離が、予め設定された基準距離以上の場合には、当該経由地近傍地点が上記許容地点であるとし、当該経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８１】
また、表示された地図上に示された道路以外の地点がユーザにより経由地点として指定され、設定された場合には、当該経由地点の近傍に存在する道路上の経由地近傍地点が上記許容地点であるとし、当該経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８２】
また、ＰＯＩ検索、住所検索等を通じて施設又は建物がユーザにより経由地点として指定された場合には、道路上の上記経由地点又は上記経由地近傍地点が上記許容地点であるとし、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８３】
なお、上記実施形態における構成に加えて、上記道路上の経由地点又は上記経由地近傍地点における道路の状況（例えば、道路の幅員や、道路の交通状況等）に応じて当該経由地点に対する折り返しコストを変化させる（許容地点における折り返し難さを変化させる）ように構成しても良い。例えば、上記道路の幅員が基準値よりも広い場合、上記道路における交通量が基準値よりも多い場合、及び上記道路が渋滞状況にある場合等（その他、一方通行などの経由地点等を折り返すことに影響する情報に応じても良い）には、折り返しコストをその度合（基準値に対する交通量の度合、基準値に対する道路の幅員の広さの度合、又は渋滞状況の度合等）に応じて大きく設定（例えば、当該経由地点等が折り返すことを許容する許容地点であり、このときの折り返しコストが、渋滞状況にないとき“１”とし、渋滞状況にあるとき“１０”とする）し、経路探索処理において折り返し難くするように構成する。この構成によれば、上記道路上の経由地点又は上記経由地近傍地点が許容地点であっても、道路の幅員や、当該道路の交通状況等に応じて折り返し難くでき、したがって、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８４】
また、最適経路の探索に当たって、出発地点から目的地点までの推定所要時間を計算し、最短時間の経路を最適経路とするような装置の場合、上記道路上の経由地点又は上記経由地近傍地点が非許容地点であるときには、折り返す経路の推定所要時間に対して大きな時間を加算して経路探索処理において折り返し難くする（折り返さない経路が最適経路になるため）ように構成すれば良い。また、例えば、上記道路上の経由地点又は上記経由地近傍地点における道路の幅員が基準値よりも広い場合、上記道路における交通量が基準値よりも多い場合、及び上記道路が渋滞状況にある場合等には、折り返す経路の推定所要時間に対して、基準値に対する交通量の度合、基準値に対する道路の幅員の広さの度合、又は渋滞状況の度合等に応じた時間を加算して、経路探索処理において折り返し難くするように構成すれば良い。
【００８５】
また、上記実施形態において、上記道路上の経由地点又は上記経由地近傍地点が上記許容地点であるか否かを、過去に探索された経路又は案内された経路に関する履歴情報に基づいて判断するように構成しても良い。例えば、上記道路上の経由地点又は上記経由地近傍地点が過去に車両が停車（例えば、車両のギアをパーキングに入れた場合や車両のエンジンを停止した場合（例えば、店舗に寄ったときなど）等、停車と判断されその履歴が残る）した地点であった場合には、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であると判断される。また、上記道路上の経由地点又は上記経由地近傍地点が過去に車両が停車した地点であっても、停車後の車両の進行方向が、折り返す方向でなかった場合には、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であると判断される。また、例えば、上記道路上の経由地点又は上記経由地近傍地点が過去に目的地点として設定された場合には、そこに用事があるため立寄る可能性が高いと考えられるので、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であると判断される。
【００８６】
また、上記実施形態においては、上記車載用ナビゲーション装置に対して本願の経路探索装置及び方法等を適用した場合の例について説明したが、これに限定されるものではなく、歩行者ナビゲーション機能を有する携帯端末（例えば、携帯電話機、ＰＤＡ、ＰＨＳ等）等に対して適用しても良い。例えば、鉄道乗り換え案内など、公共の交通機関の経路探索（出発地点（例えば東京駅）から経由地点を通って目的地点（例えば新宿駅）までの経路を探索する）処理において、経由地点として路線上の駅が設定された場合には、設定された経由地点は折り返すことを許容しない非許容地点であるとして最適経路を探索する一方、経由地点としてデパート等の「建物」が設定された場合には、当該経由地近傍地点は折り返すことを許容する許容地点であるとして当該許容地点を折り返すことを許容（同じ路線の折り返しを許容）しつつ目的地点までの最適経路を探索する。
【００８７】
更に、上記実施形態においては、車両に搭載された車載用ナビゲーション装置Ｓに対して本願の経路探索装置及び方法等を適用した場合の例について説明したが、これに限定されるものではなく、車両に搭載される通信ナビゲーション端末と、当該通信ナビゲーション端末がアンテナ及び移動体通信ネットワーク（無線基地局等を含む）を介して接続される通信センタ装置と、により構成された通信ナビゲーションシステムに対して、本願の経路探索装置及び方法等を適用するように構成しても良い。このような構成において、通信センタ装置は、通信ナビゲーション端末からの移動体通信ネットワークを介して通信を行いつつ、上述した経路探索処理を行うこととなる。
【符号の説明】
【００８８】
１ ＧＰＳ受信部
２ センサ部
３ 交通情報受信部
４ 情報記憶部
５ 表示部
６ 音声出力部
７ 操作部
８ システム制御部
Ｓ 車載用ナビゲーション装置
【技術分野】
【０００１】
本発明は、出発地点から経由地点を通って目的地点までの経路を探索する経路探索装置及び方法等の技術分野に関する。
【背景技術】
【０００２】
従来から、出発地点から目的地点に至る複数の経路候補毎に、各リンクに設定されたリンクコスト（例えば、当該リンクに対応する道路等の区間における距離、道幅等の道路属性が考慮された重みづけ）を積算して総リンクコストを求め、総リンクコストが最小の経路候補を最適経路として探索する車載用ナビゲーション装置が知られている。
【０００３】
また、特許文献１に開示されたナビゲーション装置においては、リンクコストばかりでなく、複数のリンクを接続するノードにおけるノードコストをも考慮して総コスト（総リンクコストと総ノードコストとの和）を求め、最適経路を探索するようになっている。
【０００４】
このような最適経路の探索に当たって、出発地点から目的地点までの途中にある経由地点をユーザが指定できるようにした車載用ナビゲーション装置も知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−３２９５７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、ユーザが上記経由地点を指定する意図は、その経由地点（場所）に立ち寄りたい場合と、その経由地点を通り抜けたい（通過したい）場合との２通りが想定される。例えば、その経由地点を通り抜けたい場合には、その経由地点で折り返すことなく、通り抜けるように最適経路が探索されるべきである。
【０００７】
しかしながら、その経由地点に立ち寄りたい場合は、必ずしもそうではなく、経由地点で折り返すように最適経路が探索されても問題はない場合もある。従来の車載用ナビゲーション装置においては、ユーザがその経由地点で折り返さずに通り抜けたいのか、或いは、その経由地点で折り返しても良いのかを自動的に区別することはできず、そのため、ユーザが真に意図する最適経路を探索することに不都合があった。
【０００８】
そこで、このような不都合の解消を一つの課題とし、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索することが可能な経路探索装置、経路探索方法、及び経路探索処理プログラム等を提供することを目的する。
【課題を解決するための手段】
【０００９】
上記課題を解決するため、請求項１に記載の発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする。
【００１０】
請求項２に記載の発明は、目的地点及び経由地点を設定する設定手段と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、を備え、前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする。
【００１１】
請求項３に記載の発明は、経路探索装置により実行される経路探索方法であって、前記経路探索方法は、目的地点及び経由地点を設定する設定工程と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、を含み、前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする。
【００１２】
請求項４に記載の発明は、経路探索装置により実行される経路探索方法であって、前記経路探索方法は、目的地点及び経由地点を設定する設定工程と、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、を含み、前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする。
【００１３】
請求項５に記載の経路探索処理プログラムの発明は、目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索するように機能させることを特徴とする。
【００１４】
請求項６に記載の経路探索処理プログラムの発明は、目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索するように機能させることを特徴とする。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係る車載用ナビゲーション装置の概要構成例を示す図である。
【図２】実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。
【図３】経路探索処理により探索され、表示された最適経路（経由地点付近のみを示す）の一例を示す図である。
【図４】実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。
【図５】経由地点が非許容地点である場合における経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【図６】経由地点が許容地点である場合における経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本願の実施形態を添付図面に基づいて説明する。なお、以下に説明する実施の形態は、車載用ナビゲーション装置に対して本願を適用した場合の実施形態である。
【００１７】
先ず、図１等を参照して、本実施形態における車載用ナビゲーション装置の構成及び機能を説明する。
【００１８】
図１は、本実施形態に係る車載用ナビゲーション装置の概要構成例を示す図である。
【００１９】
図１に示すように、車載用ナビゲーション装置Ｓは、ＧＰＳ（Global Positioning System）受信部１、センサ部２、交通情報受信部３、情報記憶部４、表示部５、音声出力部６、操作部７、及びシステム制御部８等を備えて構成されている。
【００２０】
ＧＰＳ受信部１は、衛星軌道上に配置され地球を周回するＧＰＳ衛星から出力される航法電波を、図示しないアンテナを介して受信し、受信した信号に基づいて位置情報（経度及び緯度）を検出し、ＧＰＳデータとしてシステム制御部８へ出力するようになっている。
【００２１】
センサ部２は、例えば、車速パルスに基づき車両の速度を検出する速度センサ、地磁気を利用して車両の走行方位を検出する方位センサ（ジャイロセンサ）、車両の加速度を検出する加速度センサ、車両の走行距離を検出する距離センサ等を備えており、これらのセンサによって検出された各データ（速度データ、方位データ、加速度データ、走行距離データ等）を、システム制御部８へ出力するようになっている。
【００２２】
交通情報受信部３は、例えばＶＩＣＳ（Vehicle Information and Communication System）受信機を有しており、ＦＭ多重放送、道路（主要幹線道路や高速道路）上に設置された光（赤外線）ビーコン、電波（準マイクロ波）ビーコン等から発信された道路交通情報（例えば、渋滞等の交通状況に関する情報）を受信し、システム制御部８へ出力するようになっている。
【００２３】
情報記憶部４は、例えば、ＣＤ（Compact Disc）−ＲＯＭドライブ、ＤＶＤ（Digital Versatile Disc）−ＲＯＭドライブ、又はＨＤ（Hard Disc）ドライブ等を備えており、各ドライブが、システム制御部８の制御の下、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、又はＨＤ等の記録媒体に記録された経路探索や経路案内（経路誘導）等を行うためのデータ及びプログラムを読み出し、システム制御部８へ出力するようになっている。更に、情報記憶部４におけるＨＤ等には、過去に探索された経路及び案内された経路に関する履歴情報が記憶されている。
【００２４】
ここで、経路探索や経路案内等を行うためのデータには、例えば、地図データ、ＰＯＩ（Point Of Interest）データ、リンクデータ、ノードデータ、及び経路案内データ、更には、ユーザに対し入力指示や選択指示を促すためのデータ（例えば、メニューデータ）等が含まれている。
【００２５】
上記地図データは、表示部５における表示画面上に地図を表示するための画像データ、及び各地点の座標（緯度及び経度に対応する地図上における座標（X,Y））を示すデータ等を含んでおり、例えば、地図上における複数の行政区画の境界を示す複数の行政界データ（各行政区画に対応する住所を含む）、地図上における道路を示す道路データ（各道路名、各交差点名、及び各合流点（ジャンクション）名等を含む）、地図上における複数の平面区画（例えば、施設や建物等が設置される区画）の一例としての家形を示す複数の家形データ（各家形に対応する住所、郵便番号、及び電話番号等を含む）、及び河川や山岳の平面図等の形状を示す形状データ（河川や山岳の名称等を含む）等を含んでいる。なお、地図データにおける住所、道路名、及び交差点名等には、夫々座標を示すデータが対応付けられている。
【００２６】
また、上記ＰＯＩデータは、地図上における地点の内容（例えば、施設（遊園地、テーマパーク等）や建物（住宅、マンション、ホテル、ビルディング、事務所等））を示すＰＯＩの名称、住所、電話番号、郵便番号、及びＰＯＩの座標（緯度及び経度に対応する地図上における座標（X,Y））等が含まれており、家形データに対応付けられるようになっている。
【００２７】
また、上記道路データにて示される道路は、複数の線分としてのリンクから構成され、少なくとも２つのリンクは、１つのノードで接続される。このノードは、例えば、各道路の交差点、屈曲点、分岐点、合流点（ジャンクション）、又は有料道路のインターチェン等の接点（結節点）を含む接続部分に対応する。
【００２８】
また、上記リンクデータは、上記各リンク毎に、リンクのリンクＩＤ、当該リンクが接続される２つのノードのノードＩＤ、当該リンクに対応する道路の距離（道路区間の距離）、属性、及び方位等の情報を有している（これらの情報は、各リンク毎に対応付けられている）。なお、道路の属性には、例えば、道路の幅員、道路の車線数、一方通行と双方通行の別、右左折レーンの有無等の情報が該当する。
【００２９】
更に、各リンクには、そのリンクに対応する道路の距離や道路の属性等が考慮された重みづけとしてのリンクコストが設定される。例えば、道路の距離が短い場合や、道路の幅員が広い場合には、当該区間の走行に要する時間は短くなるので、リンクコストが小さく設定される。また、リンクコストは、交通情報受信部３により得られた渋滞等の交通状況により変化する（例えば、渋滞の場合、そのリンクに対応するリンクコストが小さく設定される）ようになっている。
【００３０】
また、上記ノードデータは、上記各ノード毎に、ノードのノードＩＤ、当該ノードの座標（緯度及び経度に対応する地図上における座標（X,Y））、及び当該ノードに接続されるリンクのリンクＩＤ等の情報を有している。
【００３１】
更に、各ノードには、１のリンクに対応する道路からそのノードに対応する接続部分を介して他のリンクに対応する道路への車両の移動（直進、右左折等）の困難さをあらわす重みづけとしてのノードコストが設定される。一例を挙げると、幅員が広い道路から交差点を介して狭い道路へ車両が右折する場合には、曲がりにくいので、ノードコストが大きく設定される。
【００３２】
これらのリンクデータ及びノードコストは、最適経路（例えば、出発地点（例えば現在地点、現在地点から先の地点でも良い）から目的地点までの最短距離の経路、出発地点から目的地点までの最短時間の経路等）の算出に用いられる。なお、折り返しコストについての詳細は後述する。
【００３３】
また、上記経路案内データには、後述する経路案内に用いられる画像データ、文字データ、及び音声データ等が含まれる。
【００３４】
なお、経路探索や経路案内（経路誘導）を行うためのデータ及びプログラムは、情報記憶部４に記録する代わりに、例えば、インターネット及び移動体通信網（無線基地局を含む）等を含む通信ネットワークに接続された所定のサーバに記憶保存しておき、適宜、当該サーバから送信され、システム制御部８へ出力されるように構成しても良い。
【００３５】
表示部５は、例えば、描画処理部、バッファメモリ及びディスプレイ（例えば、液晶ディスプレイ、又は有機ＥＬディスプレイ等）等を備えており、描画処理部が、システム制御部８の制御の下、上記地図データや、経路案内に係る画像データをバッファメモリに展開、描画した後、ディスプレイにおける表示画面に表示（例えば、地図表示、経路表示、経路の距離や料金等の一覧表示等）するようになっている。また、当該表示画面には、システム制御部８の制御の下、ユーザに対し入力指示や選択指示を促すための例えばメニューも表示される。
【００３６】
音声出力部６は、例えば、ＤＡＣ（デジタル／アナログ信号変換器）、アンプ、スピーカ等を備えており、システム制御部８から出力された経路案内に係る音声データをＤＡＣによりＤ／Ａ変換した後、アンプにより増幅してスピーカから音波として出力するようになっている。
【００３７】
操作部７は、ユーザからの入力指示や選択指示（例えば、目的地点の指示）等を受け付けるための複数の操作ボタンを有しており、ユーザにより押下された操作ボタンに対応する指示信号をシステム制御部８へ出力するようになっている。また、上記ディスプレイにおける表示画面に表示された地図は、ユーザからの操作部７を介した指示によりスクロール表示可能になっており、当該地図上における任意の地点を、ユーザが操作部７を介して目的地点又は経由地点として指定可能になっている。
【００３８】
システム制御部８は、演算機能を有するＣＰＵ、作業用ＲＡＭ、各種データやプログラムを記憶するＲＯＭ等を備えており、当該ナビゲーション装置Ｓにおける構成要素全体を統括制御するようになっている。そして、システム制御部８のＣＰＵが、例えば情報記憶部４に記憶された経路探索や経路案内等を行うためのプログラム（本願の経路探索処理プログラムを含む）を読み出し実行することにより、本願の地図表示制御手段、設定手段、及び経路探索手段等として機能するようになっている。
【００３９】
より具体的には、システム制御部８は、経路探索処理において、ユーザからの操作部７を介して指定された目的地点及び経由地点（経由地点の設定は任意）を設定し、出発地点（例えば現在地点）から、当該目的地点までの（経由地点が設定されている場合、設定された道路上の経由地点、又は設定された道路上にない経由地点の近傍に存在するある道路上（例えば、当該経由地点ら最も近い道路（経路を構成する路）上）の路上地点（以下、「経由地近傍地点」という）を通って）最適経路を探索するようになっている。
【００４０】
ここで、目的地点又は経由地点は、例えば表示部５における表示画面に表示されたメニューから選択可能なＰＯＩ検索（例えば、予めＰＯＩデータに登録されているＰＯＩの名称から検索）、住所検索（例えば、予め地図データ又はＰＯＩデータに登録されている住所から検索）、電話番号検索（例えば、予め地図データ又はＰＯＩデータに登録されている電話番号から検索）、道路検索（予め地図データに登録されている道路名から検索）、又は交差点等検索（予め地図データに登録されている交差点名、合流点名等から検索）等において、ユーザが操作部７を介して検索条件を指定することにより検索された内容から指定可能になっている。また、ユーザが操作部７を介して表示画面にスクロール可能に表示された地図上における任意の地点を目的地点又は経由地点として指定可能になっている。もちろん、ユーザが操作部７を介して所望の名称の文字入力することにより、目的地点又は経由地点として指定することもできる。こうして指定された目的地点及び経由地点の位置情報（緯度及び経度に対応する地図上における座標（X,Y））は、システム制御部８により認識される。なお、経由地点とは、１つの点（ドット）を示すことに限定されるものではなく、所定の範囲（例えば、道路検索の場合、当該検索された道路名に対応する一定距離の範囲）を示す場合もある。
【００４１】
また、現在地点の位置情報（緯度及び経度に対応する地図上における座標（X,Y））は、システム制御部８により、センサ部２からの速度データ、方位データ、及び加速度データ等、並びにＧＰＳ受信部１からのＧＰＳデータに基づいて算出され、認識される。なお、車両の現在地点の位置情報の算出方法は、公知の技術であるので、更なる詳しい説明を省略する。
【００４２】
そして、出発地点から目的地点までの最適経路の探索にあっては、システム制御部８は、例えば、出発地点から目的地点に至る経路候補を構成する複数のリンクの夫々のリンクコストを取得し、これらのリンクコストに基づいて各経路候補の総リンクコストを計算し、更に、上記少なくとも２つ以上のリンクを接続する複数のノードにおける夫々のノードコストを取得し、これらのノードコストに基づいて各経路候補の総ノードコストを計算する。そして、システム制御部８は、上記算出された総リンクコスト及び総ノードコストとの和である総コストを、各経路候補毎に算出して、そのうち、総コストが小さい（例えば、最小の）経路候補を最適経路として探索する。
【００４３】
更に、最適経路の探索にあたって、経由地点が設定されているとき、システム制御部８は、当該設定された道路上の経由地点、又は上記設定された道路上にない経由地点の近傍に存在するある道路上の経由地近傍地点が折り返すことを許容する許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ目的地点までの経路を探索するようになっている。一方、システム制御部８は、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを抑制しつつ目的地点までの経路を探索するようになっている。
【００４４】
一例として、設定された経由地点が、ユーザが立ち寄りたい立寄地点である場合、道路上の当該経由地点又は経由地近傍地点は折り返すことを許容する許容地点となり（つまり、ユーザが目的地点に行くまでの間で立ち寄ることを目的に経由地点として指定すると考えられるため）、折り返す経路の総コストが最小（折り返さない経路の総コストより小さい）であれば、当該折り返す経路が最適経路として探索される（上記道路上の経由地点又は経由地近傍地点での方向を考慮せず、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容した経路探索）。一方、例えば、上記道路上の経由地点又は上記経由地近傍地点が、ユーザが通過したい（折り返さずに直進して通り抜けたい）通過地点である場合には、上記道路上の経由地点又は上記経由地近傍地点は折り返すことを許容しない非許容地点となり（つまり、ユーザが上記道路上の経由地点又は上記経由地近傍地点を通って目的地点に行きたい（例えば、運転のし易さ）と考えられるため）、折り返す経路の総コストが最小であっても、当該折り返す経路は最適経路として探索されない（上記道路上の経由地点又は上記経由地近傍地点での方向を考慮し、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない経路探索）。なお、許容地点とは、１つの点（ドット）を示すことに限定されるものではなく、所定の範囲（例えば、道路検索の場合、当該検索された道路名に対応する一定距離の範囲）を示す場合もある。
【００４５】
また、別の例として、設定された経由地点に対して、折り返す困難さをあらわす重みづけとしての折り返しコストを設定し、当該折り返しコストが上記総コストに加算され、折り返しコストと総コストとの和が最小である経路が最適経路として検索されるように構成しても良い。この場合、例えば、設定された経由地点が立寄地点であれば当該折り返しコストを小さく設定することにより、実質的に上記道路上の経由地点又は上記経由地近傍地点で折り返すことを許容し、その結果、折り返す経路の「総コストと折り返しコストとの和」が最小であれば、当該折り返す経路が最適経路として探索される。一方、上記道路上の経由地点又は上記経由地近傍地点が通過地点であれば当該折り返しコストを大きく（例えば、当該折り返し経路が最適経路として探索されない程度の大きさ）設定することにより、実質的に上記道路上の経由地点又は上記経由地近傍地点で折り返すことを許容せず、当該折り返す経路は最適経路として探索されない。
【００４６】
ところで、設定された道路上の経由地点又は上記経由地近傍地点が上記許容地点であるか否か（言い換えれば、設定された経由地点等が立寄地点であるか通過地点であるか）は、例えば、経由地点の指定方法（ユーザがどのような方法で指定したか）等に応じて判断される。
【００４７】
以下にその具体例を示す。
（１）道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点である場合(下記（i）〜（iv）の場合)
（i）表示された地図上において道路（経路を構成する路）以外の所望の地点（例えば、家形上の地点、道路から所定）が経由地点として指定された場合、或いは、道路上の所望の地点が経由地点として指定され、且つ、ハウスナンバー（番地）も指定された場合
（ii）ＰＯＩ検索により所望のＰＯＩが経由地点として指定された場合
（iii）住所検索により所望の施設や建物の住所が経由地点として指定された場合
（iv）電話番号検索により所望の電話番号に対応する地点が経由地点として指定された場合
なお、上記（i）〜（iv）の場合であっても、上記指定された経由地点が道路上にない場合に、当該経由地点と、当該経由地点の近傍に存在する道路上経由地近傍地点との距離が予め設定された基準距離より短い場合は、当該経由地近傍地点を非許容地点としても良い。
（２）道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点である場合(下記（v）〜（vii）の場合)
（v）表示された地図上において道路上の所望の地点が経由地点として指定された場合
（vi）道路検索により所望の道路が経由地点として指定された場合
（vii）交差点等検索により所望の交差点又は合流点が経由地点として指定された場合
なお、上記（v）〜（vii）の場合であっても、当該経由地点を折り返さずに通過することで何十kmの遠回りする経路となると合理的であるとは言えないため、この場合に折り返す経路と、折り返さない経路との距離差が例えば所定距離（例えば、５ｋｍ）であれば、当該経由地点を許容地点として折り返しを許容するように構成することが望ましい。
【００４８】
次に、車載用ナビゲーション装置Ｓにおける経路探索処理を説明する。
【００４９】
（実施例１）
先ず、図２等を参照して、実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を説明する。
【００５０】
図２は、実施例１に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。なお、図２に示す経路探索処理は、ユーザにより目的地点及び経由地点が指定された場合における処理である。
【００５１】
先ず、ユーザは、上述したＰＯＩ検索、住所検索、電話番号検索、道路検索、又は交差点等により検索された内容から経由地点を指定、又は表示された地図上における任意の地点を経由地点として指定し、且つ目的地点を指定して、操作部７における検索実行ボタンを押下すると、図２に示す経路探索処理が開始される。なお、指定された経由地点及び目的地点は、ＲＡＭにおける所定の領域に記憶される。
【００５２】
図２に示す経路探索処理が開始されると、システム制御部８は、上記指定された経由地点及び目的地点を設定する（ステップＳ１）。
【００５３】
次いで、システム制御部８は、設定された経由地点と、当該経由地点の例えば最も近傍に存在する道路上の地点との距離を計算し（ステップＳ２）、当該計算された距離（設定された経由地点が道路上にある場合には、当該距離は「０」となる）が、予め設定された基準距離よりも短いか否かを判別する（ステップＳ３）。
【００５４】
そして、当該計算された距離が、基準距離よりも短くない（基準距離以上の）場合には（ステップＳ３：Ｎ）、当該経由地点の最も近傍に存在する経由地近傍地点が上記許容地点であるとし、システム制御部８は、上述したように、当該経由地近傍地点を折り返すことを許容した経路探索を実行（例えば、当該経由地点に対する折り返しコストを最小に設定して経路探索を実行）し（ステップＳ４）、最適経路を探索して、当該処理を終了する。
【００５５】
一方、当該計算された距離が、基準距離よりも短い場合（設定された経由地点が道路上にあるか、又は設定された経由地点が道路上になくても基準距離よりも短い場合）には（ステップＳ３：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であるとし、システム制御部８は、上述したように、当該道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない（折り返すことを抑制した）経路探索を実行（例えば、当該経由地点に対する折り返しコストを大きく設定して経路探索を実行）し（ステップＳ５）、最適経路を探索して、当該処理を終了する。
【００５６】
こうして最適経路が探索されると、システム制御部８は、経路案内処理を実行し、車両の現在地点の位置情報を認識しつつ、当該車両の現在位置が道路上に位置するか否かの整合性、いわゆるマップマッチング処理を行い、かつ、当該探索された最適経路を用いて、当該経路に関する情報（最適経路の経路（ルート）案内（誘導）、最適経路の距離や料金等）をユーザに提示、すなわち、当該情報を表示部５における表示画面上に表示させたり、音声出力部６から音声出力させたりする。
【００５７】
なお、上記処理においては、設定された、道路上にない経由地点と、当該経由地点の近傍に存在する道路上の経由地近傍地点との距離が予め設定された基準距離より短いか否かを判別することにより折り返しコストの設定を変えるようにしたが、これに限らず、例えば、基準距離との比較を行わなくとも、上記道路上にない経由地点と、上記経由地近傍地点との距離に応じて折り返しコストを変化させるようにしても良い。例えば、設定された、上記道路上にない経由地点と、上記経由地近傍地点との距離と折り返しコストとの関係を示すデータＴＢを用意し、上記計算された距離が当てはまる折り返しコストを抽出して変化させたり、該当する距離が上記データＴＢに存在しなかった場合には、一番近い距離の折り返しコストを抽出して変化させるなどが挙げられる。
【００５８】
図３（Ａ）及び（Ｂ）は、図２に示す経路探索処理により探索され、表示された最適経路（経由地点付近のみを示す）の一例を示す図である。
【００５９】
図３（Ａ）に示す例では、設定された道路上にない経由地点５１と、当該経由地点５１の近傍に存在する（例えば最も近くにある）道路上の地点５２との距離Ｘ１は、基準距離Ｙよりも短いため、当該地点５２で折り返さずに通過した最適経路が表示されている（なお、経由地点５１と地点５２とが一致する場合も同様）。一方、図３（Ｂ）に示す例では、設定された道路上にない経由地点５１と、当該経由地点５１の近傍に存在する（例えば最も近くにある）道路上の地点５２との距離Ｘ２は、基準距離Ｙ以上であるため、当該地点５２で折り返した最適経路が表示されている。
【００６０】
（実施例２）
次に、図４等を参照して、実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を説明する。
【００６１】
図４は、実施例２に係る車載用ナビゲーション装置Ｓの経路探索処理を示すフローチャートである。なお、図４に示す経路探索処理も、ユーザにより目的地点及び経由地点が指定された場合における処理である。
【００６２】
先ず、実施例１と同様、ユーザは、上述したＰＯＩ検索、住所検索、電話番号検索、道路検索、又は交差点等により検索された内容から経由地点を指定、又は表示された地図上における任意の地点を経由地点として指定し、且つ目的地点を指定して、操作部７における検索実行ボタンを押下すると、図４に示す経路探索処理が開始される。
【００６３】
図４に示す経路探索処理が開始されると、システム制御部８は、上記指定された経由地点及び目的地点を設定する（ステップＳ１１）。
【００６４】
次いで、システム制御部８は、上記設定された経由地点が、表示された地図上から指定されたものであるか否かを判別し（ステップＳ１２）、地図上から指定された経由地点である場合には（ステップＳ１２：Ｙ）、更に、当該経由地点が、表示された地図上における道路上に存在する否かを判別（座標（X,Y）により判別）する（ステップＳ１３）。
【００６５】
そして、上記経由地点が、表示された地図上における道路上に存在する場合には（ステップＳ１３：Ｙ）、当該道路上の経由地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される一方、上記経由地点が、表示された地図上における道路上に存在しない場合には（ステップＳ１３：Ｎ）、当該経由地点の近傍に存在する道路上の経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６６】
一方、上記ステップＳ１２において、地図上から指定された経由地点でない場合には（ステップＳ１２：Ｎ）、システム制御部８は、上記設定された経由地点が、ＰＯＩ検索により（ＰＯＩ検索を通じて）指定されたものであるか否かを判別し（ステップＳ１４）、ＰＯＩ検索により指定されたものでない場合には（ステップＳ１４：Ｎ）、ステップＳ１５に移行し、ＰＯＩ検索により指定されたものである場合には（ステップＳ１４：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６７】
ステップＳ１５では、システム制御部８は、上記設定された経由地点が、道路検索により指定されたものであるか否かを判別し、道路検索により指定されたものでない場合には（ステップＳ１５：Ｎ）、更に、住所検索又は電話番号検索により施設や建物の住所又は電話番号が経由地点として指定されたものであるか否かを判別する（ステップＳ１６）。
【００６８】
一方、ステップＳ１５において、道路検索により指定されたものである場合には（ステップＳ１５：Ｙ）、システム制御部８は、ハウスナンバー（番地）が指定されたか否かを判別し（ステップＳ１７）、ハウスナンバーが指定されていない場合には（ステップＳ１７：Ｎ）、上記経由地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される一方、ハウスナンバーが指定されている場合には（ステップＳ１７：Ｙ）、上記経由地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行される。
【００６９】
一方、ステップＳ１６において、施設や建物の住所又は電話番号が経由地点として指定されたものである場合には（ステップＳ１６：Ｙ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であるとし、ステップＳ１９（折り返すことを許容した経路探索）に移行され、施設や建物の住所又は電話番号が経由地点として指定されたものでない場合には（ステップＳ１６：Ｎ）、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であるとし、ステップＳ１８（折り返すことを抑制した経路探索）に移行される。
【００７０】
なお、施設や建物の住所又は電話番号が経由地点として指定されたものでない場合には（ステップＳ１６：Ｎ）、更に、他の方法（交差点等検索等）により指定された否かを判別して、折り返すことを許容する経路探索を行うか、折り返すことを許容しない経路探索を行うかを判別するように構成しても良い。
【００７１】
また、当該実施例２における経路探索処理において、上記実施例１と同様、設定された道路上の経由地点と、当該経由地点の近傍に存在する道路上の経由地近傍地点との距離を計算し、当該計算された距離が、予め設定された基準距離よりも短いか否かを判別する構成を加えても良い。例えば、ＰＯＩ検索、住所検索又は電話番号検索を通じて経由地点が指定された場合に、上記計算された距離が、予め設定された基準距離よりも短いか否かを判別して、折り返すことを許容する経路探索を行うか、折り返すことを許容しない経路探索を行うかを判別するように構成しても良い。
【００７２】
そして、ステップＳ１８における折り返すことを抑制した経路探索では、システム制御部８は、上述したように、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しない経路探索を実行（例えば、当該経由地点に対する折り返しコストを大きく設定して経路探索を実行）し、最適経路を探索して、当該処理を終了する。
【００７３】
一方、ステップＳ１９における折り返すことを許容した経路探索では、上述したように、上記道路上の経由地点又は上記該経由地近傍地点を折り返すことを許容した経路探索を実行（例えば、当該経由地点に対する折り返しコストを最小に設定して経路探索を実行）し、最適経路を探索して、当該処理を終了する。
【００７４】
なお、これ以降は、実施例１と同様、経路案内処理が実行される。
【００７５】
図５及び図６は、上記経路探索処理により探索され、表示された最適経路全体の一例を示す図である。
【００７６】
図５に示す例では、道路上の経由地点が折り返すことを許容しない非許容地点となっており、当該経由地点を折り返さずに通過（経由地点手前における車両の進行方向を維持）した、目的地点までの最適経路が表示（例えば、出発地点から目的地点までの総距離が相対的に長くなっても最適経路として表示）されている。一方、図６に示す例では、道路上の経由地点が折り返すことを許容する許容地点となっており、当該経由地点を折り返した、目的地点までの最適経路が表示（例えば、出発地点と経由地点、経由地点と目的地点の夫々の区間で、純粋に最短となる経路が引かれ、最適経路として表示）されている。
【００７７】
以上説明したように上記実施形態によれば、目的地点及び経由地点を設定し、出発地点から、設定された道路上の経由地点又は設定された道路上にない経由地点の近傍に存在するある道路上の経由地近傍地点を通って、当該設定された目的地点までの経路を探索する車載用ナビゲーション装置Ｓが、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ上記目的地点までの最適経路を探索するように構成し、一方、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地である場合には、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを抑制しつつ上記目的地点までの経路を探索するように構成したので、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００７８】
ここで、当該車載用ナビゲーション装置Ｓは、地図上における道路上にない地点が経由地点として設定された場合には、当該経由地点の近傍に存在するある道路上の経由地近傍地点を経由するように目的地点までの経路を探索するように構成されており、設定された道路上にない経由地点の上記地図上の位置に応じて、上記経由地近傍地点を折り返した経路の探索、または上記経由地近傍地点を折り返さずに通過する経路の探索のいずれかの探索を実行するように構成したので、地図上における道路上にない地点が経由地点として設定された場合であっても、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００７９】
また、上記経由地点の指定方法に応じて、上記道路上の経由地点又は上記経由地近傍地点が、許容地点であるか否かが判断されるように構成したので、ユーザは経由地点を指定する前に、上記経由地点等を通り抜けるか、或いは折り返しても良いかを決めた上で、その意図に合った最適な指定方法を選択することができる。
【００８０】
また、ユーザにより指定され、設定された経由地点と、その経由地点の近傍に存在する道路上の経由地近傍地点との距離が、予め設定された基準距離以上の場合には、当該経由地近傍地点が上記許容地点であるとし、当該経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８１】
また、表示された地図上に示された道路以外の地点がユーザにより経由地点として指定され、設定された場合には、当該経由地点の近傍に存在する道路上の経由地近傍地点が上記許容地点であるとし、当該経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８２】
また、ＰＯＩ検索、住所検索等を通じて施設又は建物がユーザにより経由地点として指定された場合には、道路上の上記経由地点又は上記経由地近傍地点が上記許容地点であるとし、上記道路上の経由地点又は上記経由地近傍地点を折り返すことを許容しつつ目的地点までの経路が探索されるように構成したので、簡単な構成で、ユーザが経由地点を指定した意図が反映され、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８３】
なお、上記実施形態における構成に加えて、上記道路上の経由地点又は上記経由地近傍地点における道路の状況（例えば、道路の幅員や、道路の交通状況等）に応じて当該経由地点に対する折り返しコストを変化させる（許容地点における折り返し難さを変化させる）ように構成しても良い。例えば、上記道路の幅員が基準値よりも広い場合、上記道路における交通量が基準値よりも多い場合、及び上記道路が渋滞状況にある場合等（その他、一方通行などの経由地点等を折り返すことに影響する情報に応じても良い）には、折り返しコストをその度合（基準値に対する交通量の度合、基準値に対する道路の幅員の広さの度合、又は渋滞状況の度合等）に応じて大きく設定（例えば、当該経由地点等が折り返すことを許容する許容地点であり、このときの折り返しコストが、渋滞状況にないとき“１”とし、渋滞状況にあるとき“１０”とする）し、経路探索処理において折り返し難くするように構成する。この構成によれば、上記道路上の経由地点又は上記経由地近傍地点が許容地点であっても、道路の幅員や、当該道路の交通状況等に応じて折り返し難くでき、したがって、よりユーザが意図する最適経路を探索し、ユーザに提示することができる。
【００８４】
また、最適経路の探索に当たって、出発地点から目的地点までの推定所要時間を計算し、最短時間の経路を最適経路とするような装置の場合、上記道路上の経由地点又は上記経由地近傍地点が非許容地点であるときには、折り返す経路の推定所要時間に対して大きな時間を加算して経路探索処理において折り返し難くする（折り返さない経路が最適経路になるため）ように構成すれば良い。また、例えば、上記道路上の経由地点又は上記経由地近傍地点における道路の幅員が基準値よりも広い場合、上記道路における交通量が基準値よりも多い場合、及び上記道路が渋滞状況にある場合等には、折り返す経路の推定所要時間に対して、基準値に対する交通量の度合、基準値に対する道路の幅員の広さの度合、又は渋滞状況の度合等に応じた時間を加算して、経路探索処理において折り返し難くするように構成すれば良い。
【００８５】
また、上記実施形態において、上記道路上の経由地点又は上記経由地近傍地点が上記許容地点であるか否かを、過去に探索された経路又は案内された経路に関する履歴情報に基づいて判断するように構成しても良い。例えば、上記道路上の経由地点又は上記経由地近傍地点が過去に車両が停車（例えば、車両のギアをパーキングに入れた場合や車両のエンジンを停止した場合（例えば、店舗に寄ったときなど）等、停車と判断されその履歴が残る）した地点であった場合には、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であると判断される。また、上記道路上の経由地点又は上記経由地近傍地点が過去に車両が停車した地点であっても、停車後の車両の進行方向が、折り返す方向でなかった場合には、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容しない非許容地点であると判断される。また、例えば、上記道路上の経由地点又は上記経由地近傍地点が過去に目的地点として設定された場合には、そこに用事があるため立寄る可能性が高いと考えられるので、上記道路上の経由地点又は上記経由地近傍地点が折り返すことを許容する許容地点であると判断される。
【００８６】
また、上記実施形態においては、上記車載用ナビゲーション装置に対して本願の経路探索装置及び方法等を適用した場合の例について説明したが、これに限定されるものではなく、歩行者ナビゲーション機能を有する携帯端末（例えば、携帯電話機、ＰＤＡ、ＰＨＳ等）等に対して適用しても良い。例えば、鉄道乗り換え案内など、公共の交通機関の経路探索（出発地点（例えば東京駅）から経由地点を通って目的地点（例えば新宿駅）までの経路を探索する）処理において、経由地点として路線上の駅が設定された場合には、設定された経由地点は折り返すことを許容しない非許容地点であるとして最適経路を探索する一方、経由地点としてデパート等の「建物」が設定された場合には、当該経由地近傍地点は折り返すことを許容する許容地点であるとして当該許容地点を折り返すことを許容（同じ路線の折り返しを許容）しつつ目的地点までの最適経路を探索する。
【００８７】
更に、上記実施形態においては、車両に搭載された車載用ナビゲーション装置Ｓに対して本願の経路探索装置及び方法等を適用した場合の例について説明したが、これに限定されるものではなく、車両に搭載される通信ナビゲーション端末と、当該通信ナビゲーション端末がアンテナ及び移動体通信ネットワーク（無線基地局等を含む）を介して接続される通信センタ装置と、により構成された通信ナビゲーションシステムに対して、本願の経路探索装置及び方法等を適用するように構成しても良い。このような構成において、通信センタ装置は、通信ナビゲーション端末からの移動体通信ネットワークを介して通信を行いつつ、上述した経路探索処理を行うこととなる。
【符号の説明】
【００８８】
１ ＧＰＳ受信部
２ センサ部
３ 交通情報受信部
４ 情報記憶部
５ 表示部
６ 音声出力部
７ 操作部
８ システム制御部
Ｓ 車載用ナビゲーション装置
【特許請求の範囲】
【請求項１】
目的地点及び経由地点を設定する設定手段と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、
を備え、
前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする経路探索装置。
【請求項２】
目的地点及び経由地点を設定する設定手段と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、
を備え、
前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする経路探索装置。
【請求項３】
経路探索装置により実行される経路探索方法であって、
前記経路探索方法は、
目的地点及び経由地点を設定する設定工程と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、
を含み、
前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする経路探索方法。
【請求項４】
経路探索装置により実行される経路探索方法であって、
前記経路探索方法は、
目的地点及び経由地点を設定する設定工程と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、
を含み、
前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする経路探索方法。
【請求項５】
目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、
前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索するように機能させることを特徴とする経路探索処理プログラム。
【請求項６】
目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、
前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索するように機能させることを特徴とする経路探索処理プログラム。
【請求項７】
請求項５または６に記載の経路探索処理プログラムがコンピュータ読み取り可能に記録されていることを特徴とする記録媒体。
【請求項１】
目的地点及び経由地点を設定する設定手段と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、
を備え、
前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする経路探索装置。
【請求項２】
目的地点及び経由地点を設定する設定手段と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索手段と、
を備え、
前記経路探索手段は、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする経路探索装置。
【請求項３】
経路探索装置により実行される経路探索方法であって、
前記経路探索方法は、
目的地点及び経由地点を設定する設定工程と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、
を含み、
前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索することを特徴とする経路探索方法。
【請求項４】
経路探索装置により実行される経路探索方法であって、
前記経路探索方法は、
目的地点及び経由地点を設定する設定工程と、
出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索する経路探索工程と、
を含み、
前記経路探索工程においては、前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索することを特徴とする経路探索方法。
【請求項５】
目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、
前記路上にない経由地点と前記路上地点との距離が所定距離以上の場合に、当該路上地点で折り返すことを許容しつつ前記目的地点までの経路を探索するように機能させることを特徴とする経路探索処理プログラム。
【請求項６】
目的地点及び経由地点を設定し、出発地点から、路上の前記経由地点又は路上にない前記経由地点の近傍に存在する路上地点を通って、前記目的地点までの経路を探索するコンピュータを、
前記路上にない経由地点と前記路上地点との距離に応じて当該路上地点で折り返す困難さを設定し、当該困難さに基づいて前記目的地点までの経路を探索するように機能させることを特徴とする経路探索処理プログラム。
【請求項７】
請求項５または６に記載の経路探索処理プログラムがコンピュータ読み取り可能に記録されていることを特徴とする記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−２０９２９２（Ｐ２０１１−２０９２９２Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１１−１２８９８１（Ｐ２０１１−１２８９８１）
【出願日】平成２３年６月９日（２０１１．６．９）
【分割の表示】特願２００８−５３４１５８（Ｐ２００８−５３４１５８）の分割
【原出願日】平成１８年９月１１日（２００６．９．１１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願日】平成２３年６月９日（２０１１．６．９）
【分割の表示】特願２００８−５３４１５８（Ｐ２００８−５３４１５８）の分割
【原出願日】平成１８年９月１１日（２００６．９．１１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【Ｆターム（参考）】
[ Back to top ]