JPH11304515A - 経路探索装置 - Google Patents

Abstract

(57)【要約】 【課題】利用者の設定した経由地を考慮することによ
り、利用者の有料道路使用／不使用の意図に適合するよ
うに経路を探索する。 【解決手段】処理装置１は、利用者より目的地までに経
由すべき経由地として有料道路の入り口ランプや出口ラ
ンプが設定されている場合には、経由地で区切られた各
区間の両端の入り口ランプ、出口ランプの組み合わせに
応じて、その区間の経路として有料道路／非有料道路を
優先的に使用した経路を探索する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、自動車に搭載され
るナビゲーション装置などにおいて、利用者によって選
択された経由地を経由する目的地までの経路を探索する
技術に関するものである。

【０００２】

【従来の技術】自動車に搭載されるナビゲーション装置
では、道路地図データに基づいて、設定された出発地か
ら目的地までの推奨される経路を探索し、利用者に提示
する経路探索の技術が既に実用化されている。また、経
路探索に際して、利用者より予め用意した複数の経由地
候補の中から１又は複数の経由地の選択を受け付け、出
発地から選択された各経由地を経由して目的地に至る経
路を探索する技術も既に実用化されている。

【０００３】なお、このような推奨経路探索は、たとえ
ば、ダイクストラ法と呼ばれる技術などによって、出発
地から経由地を経由して目的地までの間の取り得る経路
のうち、コストが最小となる経路を探索することにより
行われている。ここで、このような経路のコストとして
は、経路の総距離などを用いることが多い。

【０００４】さらに、近年では、ナビゲーション装置に
おいて、利用者の希望する条件により適合する経路を探
索する技術も実用化されている。たとえば、利用者の希
望に応じて、有料道路を優先的に使用した経路や、逆
に、有料道路以外の道路を優先的に使用した経路を探索
するナビゲーション装置が実用化されている。ここで、
このような条件付きの経路探索は、たとえば、ダイクス
トラ法において、有料道路のコストを、他の道路より小
さくもしくは大きくなるように設定したりすることによ
り実現できる。

【０００５】

【発明が解決しようとする課題】利用者の希望する条件
により適合する経路を探索する技術と、利用者より予め
用意した複数の経由地候補の中から１又は複数の経由地
の選択を受け付け、出発地から選択された各経由地を経
由して目的地に至る経路を探索する技術とを共に用いる
場合には次のような不具合が生じてしまう。

【０００６】たとえば、利用者が、目的地に至る経路に
対する全体的な希望として非有料道路を優先的に使用す
ることを希望して経路探索の条件を設定し、かつ、部分
的に有料道路を使用することを意図して、使用を意図す
る有料道路区間の開始地点となる有料道路の入り口ラン
プを第１の経由地として選択し、第２の経由地として使
用を意図する有料道路区間の終点となる出口ランプを第
２の経由地を選択した場合における経路探索を場合を考
える。

【０００７】この場合、ナビゲーション装置は、第１の
経由地の入り口ランプと第２の経由地の出口ランプの間
の経路についても、利用者が設定した非有料道路を優先
的に使用する探索条件に従って経路を探索してしまうた
め、第１の経由地の入り口ランプと第２の経由地の出口
ランプの間の経路として利用者が使用を意図した有料道
路を使用しない経路を探索してしまうことがある。そし
て、このような場合は、ナビゲーション装置は、利用者
の意図にそぐわない経路を探索してしまったことにな
る。

【０００８】そこで、本発明は、選択された経由地を考
慮して、利用者の意図により適合する経路を探索するこ
とを課題とする。

【０００９】

【課題を解決するための手段】前記課題達成のために本
発明は、たとえば、出発地から目的地までの経路を探索
する経路探索装置であって、利用者より目的地までに経
由すべき経由地を受け付ける手段と、出発地から目的地
までの間の各経由地で区切られた各区間のうち少なくと
も一部の区間の経路として、当該区間の端となる経由地
の種別に応じて、特定の種別の道路を優先的に使用した
経路もしくは特定の種別以外の道路を優先的に使用した
経路を探索する手段とを有することを特徴とする経路探
索装置を提供する。

【００１０】このような経路探索装置によれば、出発地
から目的地までの間の各経由地で区切られた各区間のう
ち少なくとも一部の区間については、当該区間の端とな
る経由地の種別から利用者の意図をくみ取り、その区間
については、くみ取った意図に応じて、有料道路などの
特定の種別の道路を優先的に使用した経路もしくは特定
の種別以外の道路を優先的に使用した経路を探索するこ
とができる。

【００１１】

【発明の実施の形態】以下、本発明に係る経路探索装置
の一実施形態を、車載用ナビゲーション装置への適用を
例にとり説明する。

【００１２】図１に、本実施形態に係るナビゲーション
装置の構成を示す。

【００１３】図中、１はマイクロプロセッサやメモリか
ら構成される処理装置、２は表示装置、３は地図データ
が記憶されたCD-ROMなどの記憶媒体のアクセスを担うド
ライブ装置、４は利用者の指示の入力を受け付ける入力
装置、５は車速センサや方位センサやＧＰＳ受信機など
から構成されるセンサ装置である。

【００１４】このような構成において、処理装置１は、
センサ装置５の方位センサから入力する車両の進行方位
や車速センサから入力する車速やＧＰＳ受信機から入力
する測定現在位置などに基づいて車両の現在位置を算出
したり、入力装置５を介して利用者より入力された目的
地と、入力装置５を介して利用者より入力されたもしく
はセンサ装置５からの入力より算出した現在位置に基づ
いて、目的地までの推奨経路の算出などを行う。

【００１５】また、処理装置１は、算出した現在位置
や、車両の進行方位や、入力装置５を介して利用者より
指定された内容に基づき、ドライブ装置３を制御し地図
データを読み出し、当該地図データの表す地図を表示装
置２に表示する。地図の表示は、たとえば、算出した現
在位置周辺の領域の地図を所定の縮尺で表示したり、利
用者より指定された地区の地図を所定のもしくは指定さ
れた縮尺で表示したり、現在位置から目的地までの推奨
経路を含む範囲の領域の地図を適当な縮尺で、推奨経路
と共に表示することにより行う。また、この際、地図上
に車両の現在位置と進行方位を表すマークを地図に重畳
して表示したりする。

【００１６】次に、ドライブ装置３に装着されるCD-ROM
などの記憶媒体に記録された地図データを図２に示す。

【００１７】図示するように、地図データは、各道路毎
に設けられた道路データより構成される。また、道路デ
ータは、道路情報と、リンク情報よりより構成される。

【００１８】道路情報には、道路を一意に表す道路番号
と、道路の名称を表す道路名称と、その道路の種別（有
料道路、国道、県道、ランプ）などを表す道路種別と、
その他の道路の情報を表すその他属性が含まれる。

【００１９】また、リンク情報には、道路を構成する各
リンクについて設けられた、リンクの情報を表すリンク
データが含まれる。ここで、リンクは、道路の形状位置
を集合として近似する直線の線分である。リンクデータ
は、リンクを一意に表すリンク番号と、リンクが構成す
る道路部分の種別を表すリンクの種別とを含む。また、
リンクデータは、その両端の点である２つのノードにつ
いて、それぞれ、ノードを一意に示すノード番号と、ノ
ードの位置を表すノード座標と、そのノードとリンクを
介して連結する全てのノードのノード番号のリストであ
る隣接ノード番号リストを含む。ここで、リンク同士の
連結は必ずノードにおいて行われる。たとえば、十字路
では、その中心にノードが設けられ、この中心に設けら
れたノードに４つのリンクが連結する。そして、この場
合、中心に設けられたノードの隣接ノード番号リストに
は、自ノードに連結する４つのリンクの他端の４つのノ
ードのノード番号が記述される。

【００２０】次に、図３に、図２に示した地図データに
付随して、ドライブ装置３に装着されるCD-ROMなどの記
憶媒体に記録された案内情報の構成を示す。

【００２１】図示するように、案内情報は、地図データ
がカバーする地理的範囲内に存在する代表的な施設の一
覧であり、この一覧中には、各施設について、施設名称
と施設座標と施設種別が記述されている。ここで、案難
情報に含まれる施設としては、各種公共施設や、名所
や、ガソリンスタンドや、レストランなどの施設種別の
施設の他、有料道路の入り口ランプや出口ランプや、有
料道路に付随するサービスエリアやパーキングエリアや
ジャンクションなどの道路関連の施設種別の施設も含ま
れる。

【００２２】以下、処理装置１が行う処理について説明
する。

【００２３】図４に、この処理の処理手順を示す。

【００２４】まず、処理装置１は、利用者より優先モー
ドの設定を受け付け記憶する。優先モードとしては有料
道路優先モードと非有料道路優先モードのいずれかを受
け付ける（ステップ４１）。

【００２５】次に、利用者より目的地と経由地を受け付
け、記憶する（ステップ４２）。経由地は、表示装置２
にドライブ装置３に装着されるCD-ROMなどの記憶媒体に
記録された案内情報に含まれる各施設の施設名称を表示
し、その内から利用者によって選択された施設名称の施
設を経由地として受け付ける。

【００２６】次に、処理装置１は現在位置から目的地ま
での経路の優先モードを決定する（ステップ４３）。

【００２７】優先モードは、現在位置と目的地の間の経
由地で区切られた各区間について、それぞれ決定する。
すなわち、経由地がｎ個設定されている場合には、現在
位置から第１番目の経由地までの間の経路の優先モード
と、各経由地間（１からn-1までのiについての、第i番
目の経由地と第i+1番目の経由地間）の経路の優先モー
ドと、ｎ番目の経由地から目的地までの経路の優先モー
ドを、それぞれ決定する。

【００２８】まず、ｎ番目の経由地から目的地までの経
路の優先モードは、利用者より設定を受け付けた優先モ
ードとする。

【００２９】次に、現在位置から第１の経由地までの間
の経路の優先モードは、図５に示すように、第１番目の
経由地として選択された施設の施設種別が有料道路の入
り口ランプの場合は（ステップ５１）、利用者がその入
り口ランプまでは非有料道路を使用して有料道路に入る
ことを意図しているものとして非有料道路優先モードと
し（ステップ５２）、第１番目の経由地として選択され
た施設の施設種別が有料道路の出口ランプの場合は（ス
テップ５３）、その出口ランプから有料道路を出るこ
と、すなわちその出口ランプまで有料道路を使用するこ
とを意図しているものとして有料道路優先モードとし
（ステップ５４）、第１番目の経由地として選択された
施設の施設種別が他の種別の場合は（ステップ５５）利
用者より設定を受け付けた優先モードとする（ステップ
５６）。

【００３０】次に、各経由地間（１からn-1までのiにつ
いての、第i番目の経由地と第i+1番目の経由地間）の経
路の優先モードは、図６に示す手順に従って決定する。

【００３１】すなわち、各経由地間（１からn-1までのi
についての、第i番目の経由地と第i+1番目の経由地間）
のそれぞれについて（ステップ６１）以下の処理を行
う。

【００３２】i+１番目の経由地として選択された施設の
施設種別が有料道路の入り口ランプである場合には（ス
テップ６２）、利用者がその入り口ランプまでの間に非
有料道路を使用して、その入り口ランプから有料道路に
入ることを意図しているものとして、i番目の経由地とi
+1番目の経由地間の優先モードを非有料道路優先モード
とする（ステップ６３）。

【００３３】また、i+１番目の経由地として選択された
施設の施設種別が有料道路の出口ランプである場合には
（ステップ６４）、利用者が、その出口ランプから有料
道路を出ること、すなわちその出口ランプまで有料道路
を使用することを意図しているものとして有料道路優先
モードとする（ステップ６５）。

【００３４】また、i+１番目の経由地として選択された
施設の施設種別が有料道路の入り口ランプでも出口ラン
プでもなければ（ステップ６６）、以下のように、i番
目の経由地に応じて優先モードを決定する。

【００３５】すなわち、第i番目の経由地として選択さ
れた施設の施設種別が有料道路の入り口ランプの場合は
（ステップ６７）、利用者が、その入り口ランプ以降有
料道路を使用することを意図しているものとして、i番
目の経由地からi+１番目の経由地間の優先モードを有料
道路優先モードとする（ステップ６８）。

【００３６】また、第i番目の経由地として選択された
施設の施設種別が有料道路の出口ランプの場合は（ステ
ップ６９）、その出口以降、非有料道路を使用すること
を意図しているものとして、i番目の経由地からi+１番
目の経由地間の優先モードを非有料道路優先モードとす
る（ステップ７０）。

【００３７】そして、第i番目の経由地として選択され
た施設の施設種別が有料道路の入り口ランプでも出口ラ
ンプでもない場合は（ステップ７１）、i番目の経由地
からi+１番目の経由地間の優先モードを利用者より設定
を受け付けた優先モードとする（ステップ７２）。

【００３８】次に、以上のように現在位置から目的地ま
での経路の優先モードを決定したならば、図４に戻り、
現在位置から目的地までの経路を、決定した優先モード
に従って探索する（ステップ４４）。

【００３９】この探索は、現在位置と目的地の間の経由
地で区切られた各区間の端点（経由地として設定された
施設の施設座標、出発地、もしくは、目的地）間の経路
を地図データに基づいて、各区間について決定した優先
モードに従って探索することにより行う。

【００４０】以上、本発明の実施形態について説明し
た。

【００４１】本実施形態によれば、経由地として有料道
路の入り口ランプや出口ランプが利用者によって設定さ
れた場合には、その設定の内容に応じて、経由地で区切
られた各区間の経路として有料道路／非有料道路を優先
的に使用した経路を探索することができる。したがっ
て、有料道路の入り口ランプや出口ランプの経由地とし
ての設定により利用者より暗示的に示された各区間にお
ける有料道路使用／不使用の意図に適合するように経路
を探索することができる。

【００４２】なお、本実施形態において、目的地として
有料道路の入り口ランプや出口ランプが利用者によって
設定された場合には、その設定の内容に応じて、目的地
を終点とする区間の経路として有料道路／非有料道路を
優先的に使用した経路を探索するようにしてもよい。こ
のためには、前記処理において、目的地を経由地と同様
に扱えばよい。

【００４３】また、本実施形態における処理装置１は、
CPUやメモリや適当なOSを備えた電子計算機であってよ
く、この場合、処理装置１が行う前記各処理は、CPU
が、各処理の手順を記述したプログラムを実行すること
により実現される。また、このばあい、これらのプログ
ラムはCD-ROMなどの記憶媒体を介して、処理装置１に供
給するようにしてもよい。

【００４４】

【発明の効果】以上のように本発明によれば、選択され
た経由地を考慮して、利用者の意図により適合する経路
を探索するこができる。

【図面の簡単な説明】

【図１】本発明の実施形態に係るナビゲーション装置の
構成を示すブロック図である。

【図２】本発明の実施形態に係る地図データの構成を示
す図である。

【図３】本発明の実施形態に係る案内情報の構成を示す
図である。

【図４】本発明の実施形態に係るナビゲーション装置の
動作を示すフローチャートである。

【図５】本発明の実施形態に係る優先モード決定手順を
示すフローチャートである。

【図６】本発明の実施形態に係る優先モード決定手順を
示すフローチャートである。

【符号の説明】

１ 処理装置 ２ 表示装置 ３ ドライブ装置 ４ 入力装置 ５ センサ装置

Claims (6)

【特許請求の範囲】
1. 【請求項１】出発地から目的地までの経路を探索する経
   路探索装置であって、 利用者より目的地と目的地までに経由すべき経由地を受
   け付ける手段と、 出発地から目的地までの間の各経由地で区切られた各区
   間のうち少なくとも一部の区間の経路として、当該区間
   の端となる経由地または目的地の種別に応じて、特定の
   種別の道路を優先的に使用した経路もしくは特定の種別
   以外の道路を優先的に使用した経路を探索する手段とを
   有することを特徴とする経路探索装置。
2. 【請求項２】出発地から目的地までの経路を探索する経
   路探索装置であって、 利用者より目的地までに経由すべき経由地を受け付ける
   手段と、 出発地から目的地までの間の各経由地で区切られた各区
   間のうち出発地から目的地までの間の両端を経由地で区
   切られた区間については、当該区間の経路として、当該
   区間の出発地側端の経由地が有料道路の入り口と、有料
   道路の出口と、その他の種別の地点のいずれであるか
   と、当該区間の目的地側端の経由地が有料道路の入り口
   と、有料道路の出口と、その他の種別の地点のいずれで
   あるかとに応じて有料道路を優先的に使用した経路もし
   くは有料道路以外の道路を優先的に使用した経路を探索
   する探索手段とを有することを特徴とする経路探索装
   置。
3. 【請求項３】請求項２記載の経路探索装置であって、 前記探索手段は、出発地から目的地までの間の各経由地
   で区切られた各区間のうち、出発地と経由地で区切られ
   た前記区間については、当該区間の経路として、当該区
   間の目的地側端の経由地が有料道路の入り口と、有料道
   路の出口と、その他の種別の地点のいずれであるかに応
   じて、有料道路を優先的に使用した経路もしくは有料道
   路以外の道路を優先的に使用した経路を探索することを
   特徴とする経路探索装置。
4. 【請求項４】請求項２または３記載の経路探索装置であ
   って、 利用者より、優先モードとして有料道路優先モードと非
   有料道路優先モードのうちのいずれかを受け付ける手段
   を有し、 前記探索手段は、出発地側端の経由地及び目的地側端の
   経由地が共に前記その他の種別の地点である区間につい
   ては、当該区間の経路として、受け付けた優先モードが
   前記有料道路優先モードであるときには有料道路を優先
   的に使用した経路を探索し、、受け付けた優先モードが
   前記非有料道路優先モードであるときには有料道路以外
   のを優先的に使用した経路を探索することを特徴とする
   経路探索装置。
5. 【請求項５】出発地から目的地までの経路を探索する方
   法であって、 利用者より目的地までに経由すべき経由地を受け付ける
   ステップと、 出発地から目的地までの間の各経由地で区切られた各区
   間のうち出発地から目的地までの間の両端を経由地で区
   切られた区間について、当該区間の経路として、当該区
   間の出発地側端の経由地が有料道路の入り口と、有料道
   路の出口と、その他の種別の地点のいずれであるかと、
   当該区間の目的地側端の経由地が有料道路の入り口と、
   有料道路の出口と、その他の種別の地点のいずれである
   かとに応じて有料道路を優先的に使用した経路もしくは
   有料道路以外の道路を優先的に使用した経路を探索する
   ステップとを含むことを特徴とする方法。
6. 【請求項６】電子計算機によって読み取られ実行される
   プログラムを記憶した記憶媒体であって、 前記プログラムは、 利用者より目的地までに経由すべき経由地を受け付ける
   ステップと、 出発地から目的地までの間の各経由地で区切られた各区
   間のうち出発地から目的地までの間の両端を経由地で区
   切られた区間について、当該区間の経路として、当該区
   間の出発地側端の経由地が有料道路の入り口と、有料道
   路の出口と、その他の種別の地点のいずれであるかと、
   当該区間の目的地側端の経由地が有料道路の入り口と、
   有料道路の出口と、その他の種別の地点のいずれである
   かとに応じて有料道路を優先的に使用した経路もしくは
   有料道路以外の道路を優先的に使用した経路を探索する
   ステップとを前記電子計算機に実施させるプログラムで
   あることを特徴とする記憶媒体。