JP4488967B2 - 経路探索装置及び経路探索方法 - Google Patents

Description

本発明は、自動車等の移動体を誘導するために、目的地に至る経路を生成する経路探索装置及び経路探索方法に関する。

カーナビゲーション装置に代表される経路探索装置は、地図情報を参照して、出発地(又は現在地)から目的地に至る経路を探索し、その結果得られた誘導経路に沿って移動体を目的地に誘導する装置である。一般的な経路探索装置は、ダイクストラ法又はそれを改良した方法を用いたアルゴリズムに基づいて、評価コスト(評価関数、経路価格又は経路コストなどと呼ばれることもある)が最低であるような誘導経路を探索する。

多くの経路探索装置では、探索指針となる評価コストの設定を変化させることで、距離優先、一般道路優先や有料道路優先などの異なる条件下で、経路探索が可能となっている(特許文献１参照)。また、出発地から目的地までに要する経済的な負担は、ユーザ(基本的にはドライバであるが、車両の同乗者でもあり得る)にとって非常に関心の高い問題の１つであることから、出発地から目的地までの燃費と、有料道路料金との和を評価コストとして、その和が最小となるような経済的経路を誘導経路として求める経路探索装置も存在する(特許文献２参照)。

特開平１１−２３３０４号公報 特開２００２−３０３５２２号公報

しかしながら、従来の経路探索装置や経路探索方法では、経路探索を行う際にユーザが置かれている立場の違いを、経路探索結果に反映することができないという問題があった。例えば、費用が極力安い経路を利用したい状況だけではなく、費用が安い経路を利用したいが、同時に時間的な余裕が無くて、費用が若干高くなっても目的地に早く到着したい状況も、ユーザには起こり得る。従来の経路探索装置又は方法では、後者のような状況において、ユーザは、時間を優先して有料道路優先で経路探索装置に経路探索を行わせるか、費用を優先して経路探索装置に経済的経路を求めさせるしかなく、実際の事情に合わない極端な条件に基づいて経路探索が行われていた。

また、経済的経路を求めることが可能な従来の経路探索装置では、現実的又は具体的な道路事情、例えば交差点やカーブ等の存在が評価コストにおいて考慮されていないために、十分に経済的な誘導経路が得られるとは言えない面があった。例えば、経路探索によって有料道路を利用しない誘導経路が得られても、実際にその経路を走行してみると、信号や交差点の数が多くて、自動車の停止及び発進を何度も行うこともある。この場合、想定を超える燃料が必要とされて、有料道路を通る経路を利用した方がより経済的な事態も起こり得る。

また、運転に不慣れなユーザ、高齢のユーザ、疲労が顕著なユーザ等には、費用が安いに越したことはないが、できれば目的地までの運転が楽な経路を利用したい状況が起こり得る。燃費及び有料道路料金の金銭的な負担と、運転を行う上での精神的及び肉体的負担とが比較考量される状況は、往々にして起こり得るが、従来の経路探索装置又は方法では、このような状況下において適切且つ有効な誘導経路を得ることが不可能であった。

本発明は、上記の問題を解決するものであり、ユーザが置かれている立場の違いを考慮して、さらには具体的な道路事情を考慮して、出発地から目的地に至る適切な経済的経路を探索する経路探索装置及び経路探索方法を提供する。また、本発明は、燃費や有料道路料金の金銭的な負担に加えて、運転を行う上での精神的及び肉体的負担を考慮して、出発地から目的地に至る経路を探索する経路探索装置及び経路探索方法を提供する。

本発明の経路探索装置は、異なる探索条件下で出発地から目的地に至る複数の経路を生成し、前記複数の経路の少なくとも何れか１つの一部であって、前記複数の経路の交点間を繋ぐ複数の経路部品を特定し、各経路部品について評価コストを算出し、前記複数の経路部品を選択的に組み合わせて生成される前記出発地から前記目的地に至る経路の各々について前記評価コストを求め、前記求めた評価コストが最も低い経路を案内することを特徴とする。

本発明の経路探索方法は、異なる探索条件下で出発地から目的地に至る複数の経路を生成する工程と、前記複数の経路の少なくとも何れか１つの一部であって、前記複数の経路の交点間を繋ぐ複数の経路部品を特定する工程と、各経路部品について前記評価コストを算出する工程と、前記複数の経路部品を選択的に組み合わせて生成される前記出発地から前記目的地に至る経路の各々について前記評価コストを求める工程と、前記求めた評価コストが最も低い経路を案内する工程と、を含むことを特徴とする。

上記の経路探索装置及び経路探索方法では、前記評価コストは、前記出発地から前記目的地までの移動に実際に要する第１費用、前記出発地から前記目的地までの移動に要する所用時間を金銭に換算した第２費用および前記出発地から前記目的地まで移動した場合にもたらされる面倒に相当する第３費用のうち１つ以上の費用を含むことを特徴とする。

上記の経路探索装置及び経路探索方法では、前記第１費用は、前記出発地から前記目的地までの移動で消費する消費燃料と燃料単価の積を含んでおり、前記消費燃料は、移動距離に比例する燃料とは別に、前記出発地から前記目的地に至るまでに存在する右折、左折、交差点、信号及びインターチェンジの少なくとも１つで消費する燃料を含むことを特徴とする。

上記の経路探索装置及び経路探索方法では、前記所用時間を金銭に換算する係数は、ユーザによって選択的に設定されることを特徴とする。

上記の経路探索装置及び経路探索方法では、前記面倒に相当する第３費用では、前記出発地から前記目的地に至るまでの右折回数、左折回数、交差点数、信号数、インターチェンジ数、及び経路のカーブの度合いの少なくとも１つが金銭に換算されていることを特徴とする。

上記の経路探索装置及び経路探索方法では、ある経路部品に関する前記評価コストの算出にて、前記所用時間を金銭に換算する係数および／または前記面倒に相当する第３費用を求めるために、その経路部品で生じるイベントを金銭に換算する係数は、前記出発地と前記目的地の間におけるその経路部品の位置に応じて変化することを特徴とする。

請求項１にかかる発明によれば、異なる探索条件下で出発地から目的地に至る複数の経路を生成し、前記複数の経路の少なくとも何れか１つの一部であって、前記複数の経路の交点間を繋ぐ複数の経路部品を特定し、各経路部品について評価コストを算出し、前記複数の経路部品を選択的に組み合わせて生成される前記出発地から前記目的地に至る経路の各々について前記評価コストを求め、前記求めた評価コストが最も低い経路を案内する。このような構成によれば、複数の経路部品及び複数の経路部品を選択的に組み合わせて生成される出発地から目的地までの経路の評価コストが算出されるため、異なる探索条件下で生成された経路の一部を組み合わせて、ユーザが所望する経路を生成し、案内することが可能となる。

また、評価コストは、前記出発地から前記目的地までの移動に実際に要する第１費用、前記出発地から前記目的地までの移動に要する所用時間を金銭に換算した第２費用および前記出発地から前記目的地まで移動した場合にもたらされる面倒に相当する第３費用のうち１つ以上の費用を含み、前記所用時間を金銭に換算する係数は、ユーザによって選択的に設定されるため、ユーザが実際に置かれている立場を考慮して経路探索を行い、誘導経路を決定することが可能となる。例えば、所用時間を金銭に換算する係数は、ユーザが急いでいる場合や比較的金銭的に余裕がある場合には、逆の場合と、つまり通常の場合と比較して大きく設定される。評価コストが低い経路が誘導経路として適切であると評価されることから、前者のように係数が設定されると、所用時間が小さい及び/又は有料道路区間が長い経路が高評価されることで、ユーザが置かれている立場に適した誘導経路が得られる。

以下、自動車用の車載式ナビゲーション装置(以下、「ナビゲーション装置」と称する)に本発明を適用した実施例について、図を用いて説明する。図１は、ナビゲーション装置(1)のブロック図である。本ナビゲーション装置(1)は、該装置(1)が搭載されている自動車の現在位置や方位等を決定する位置検出手段と、地図情報等を記録する記録手段と、記録手段に記録された情報を用いた経路探索、誘導経路に沿って自動車を誘導するために必要な処理(例えば、誘導用の画像データや音声データの作成)、及びナビゲーション装置(1)の統括的な制御等を行う制御手段と、自動車の現在位置とその周囲の地図等が示された誘導用画面や各種設定画面等を表示する表示手段と、誘導用音声を発生する音声出力手段と、ユーザがナビゲーション装置(1)に各種指示を行うための操作手段とを具えている。

位置検出手段は、ＧＰＳ(Global Positioning System)衛星から送信されるＧＰＳ信号をＧＰＳアンテナ(3)を介して受信して、ＧＰＳ信号を用いて自動車の現在位置(例えば、緯度及び経度)を特定するＧＰＳ受信部(5)を含んでいる。また、位置検出手段は、ジャイロスコープ(7)及び車速センサ(9)と、これらから送られた信号を処理して自動車の方位及び速度を特定するジャイロマイクロコンピュータ(以下、マイクロコンピュータを「マイコン」と称する)(11)を含んでいる。ナビゲーション装置(1)が自動車の経路誘導動作を行っている際、ＧＰＳ受信部(5)及びジャイロマイコン(11)は、自動車の位置、方位及び速度を決定し、それらの情報を制御手段に送ることを周期的に行う。

記録手段は、地図情報等を記録した記録媒体(13)と、制御手段からの指示に基づいて、記録媒体(13)から情報を読み出すドライバ(15)とを含んでいる。記録媒体(13)には、ＣＤ−ＲＯＭ、ＤＶＤ、ＨＤ、又はＩＣメモリ等が用いられる。地図情報は、地理的領域が所定の大きさのブロックに区分けされた形態で記録媒体(13)に記録されている。各ブロックに係るデータには、そのブロックに含まれる道路のノード及びリンクに関するデータ、ガソリンスタンド等の施設に関する位置データ、及びそのブロックの地図を表示手段に表示するためのデータ等が含まれている。

ノードは、道路の交差点、分岐点、合流点、終点、及びブロックにおける道路の端点に対応して設けられる。各ブロックに係るデータは、そのブロックに含まれる各ノードについて、そのノードのＩＤ番号と、そのノードの位置(例えば、緯度及び経度)と、そのノードの属性(例えば、交差点や有料道路の入口)と、そのノードに接続するリンクのＩＤと、そのノードに隣接するノードのＩＤ番号とを含んでいる。

リンクは、ノード間を繋ぐ道路の一区間に対応しており、通常、向きを持っている。各ブロックに係るデータは、そのブロックに含まれる各リンクについて、そのリングのＩＤ番号と、そのリンクの始端ノード及び終端ノードのＩＤ番号と、そのリンクの道路の種別(例えば、有料道路や国道)と、そのリンクの距離(長さ)、そのリンクに接続するリンクのＩＤと、評価コストを算出するために経路探索動作で参照される各種数値(有料道路料金を除く図４に示す項目)とを含んでいる。

制御手段には、ＣＰＵ(17)、ＲＡＭ(19)、ＲＯＭ(21)、フラッシュメモリ(23)や図示を省略したローカルバス等を含む制御マイコン(25)が用いられている。ＲＯＭ(21)には、ナビゲーション装置(1)の各種制御及び処理を実行するためのプログラム及びパラメータ等が記憶されている。経路探索動作や経路誘導動作を行うためのプログラムなど、更新される可能性があるプログラム及びパラメータ等は、フラッシュメモリ(23)に記憶される。これらのプログラムはＣＰＵ(17)により実行される。また、ＲＡＭ(19)は、経路探索動作や経路誘導動作にて読み出された地図情報や演算結果などの一時的なデータの記憶に用いられる。

表示手段は、描画ＩＣ(27)と、液晶表示装置(以下、「ＬＣＤ」と称する)(29)と、ＬＣＤＩ/Ｆ(31)とを含んでいる。経路探索結果の表示画面、経路誘導動作中に表示される誘導用画面や各種設定画面等を表示する指示が制御マイコン(25)から送られると、描画ＩＣ(27)は、その指示に基づいて画像データを作成して、それら画面を、ＬＣＤＩ/Ｆ(31)を介してＬＣＤ(29)に表示する。

音声出力手段は、デジタルアナログコンバータ(以下、「ＤＡＣ」と称する)(33)と、アンプ(35)と、スピーカ(37)とを含んでいる。制御手段は、ユーザを誘導経路に沿って案内する案内音声に係るデジタル音声信号を、経路誘導動作中に適宜作成して、ＤＡＣ(33)に送る。デジタル音声信号は、ＤＡＣ(33)にてアナログ音声信号に変換されてアンプ(35)に送られる。そして、アナログ音声信号はアンプ(35)にて増幅されて、スピーカ(37)から案内音声が出力される。

操作手段は、ナビゲーション装置(1)の筐体(図示せず)に設けられた各種操作キー(39)と、ＬＣＤ(29)上に配置されるタッチパネル(41)と、図示を省略したリモートコントローラ(以下、「リモコン」と称する)と、リモコンから送られる赤外線信号を受信するリモコン受光部(43)と、キーマイコン(45)とを含んでいる。操作キー(39)が押されると、キーマイコン(45)は、押された操作キー(39)を判別して、それに応じた動作コマンドを制御マイコン(25)に送る。また、キーマイコン(45)は、ＬＣＤ(29)に設定画面等が表示されている状態にて、タッチパネル(41)が押された領域を判別して、操作に対応した動作コマンドを制御マイコン(25)に送る。リモコン受光部(43)は、受光した赤外線信号を電気信号に変換及び復調してキーマイコン(45)に送り、キーマイコン(45)は、送られた信号から特定した動作コマンドを制御マイコン(25)に送る。

次に、本実施例のナビゲーション装置(1)が行う経路探索動作について説明する。図２は、経路探索動作の概要を示すフローチャートである。経路探索動作が開始されると、制御マイコン(25)は、目的地設定画面をＬＣＤ(29)に表示させる(Ｓ１)。ユーザが、操作キー(39)やリモコン等を操作して目的地を入力すると、制御マイコン(25)は、それらの位置を特定して、ＲＡＭ(19)に記憶する。ナビゲーション装置(1)では、種々の手順で、目的地を設定することが可能になっている。例えば、記録媒体(13)には、住所や名称等の目的地に関する情報と、目的地の位置とが対応づけられた検索用データベースが記録されており、ユーザが目的地に関する情報を入力すると、検索用データベースが参照されて、目的地の位置が特定される。また、目的地設定画面が表示されると、制御マイコン(25)は、ＧＰＳ受信部(5)で特定された自動車の現在位置を、出発地の位置としてＲＡＭ(19)に記憶する。なお、ナビゲーション装置(1)では、目的地を設定するように出発地を設定することも可能である。

制御マイコン(25)(のＣＰＵ(17))は、出発地及び目的地の設定が完了したか否かを、例えば、操作手段にて設定完了を指示する操作が行われたが否かを判別し(Ｓ２)、設定が完了すると、経路探索設定画面をＬＣＤ(29)に表示させる(Ｓ３)。経路探索設定画面では、以下にて行われる経路生成に関する各種設定が行われる。例えば、ユーザが目的地まで急いでいる状態であるか、通常の(急いでいない)状態であるかを設定できる。制御マイコン(25)は、経路探索設定画面での設定が完了したか否かを判別し(Ｓ４)、設定が完了すると、設定された出発地及び目的地を含む所定の範囲のノードデータ及びリンクデータが記録媒体(13)から読み出されて、制御マイコン(25)のＲＡＭ(19)に記憶される(Ｓ５)。

本実施例のナビゲーション装置(1)は、複数の探索条件の各々について経路探索を行って、特性の異なる複数の経路を求める。このため、ステップＳ５の後、複数の探索条件からある探索条件が選択されて、その探索条件に対応する評価コストに基づいて経路探索が行われる(Ｓ６)。ナビゲーション装置(1)は、例えば、有料道路優先、距離優先及び一般道路優先の３つの探索条件下で経路探索を行う。ステップＳ６の経路探索処理では、ダイクストラ法又はその改良法に基づいたアルゴリズムに基づいて、出発地に最も近いノード又は出発地のノード(以下、「出発地ノード」と称す)から、目的地に最も近いノード又は目的地のノード(以下、「目的地ノード」と称す)までの経路が探索される。制御マイコン(25)は、読み出されたリンクデータに含まれる必要な数値(距離等)を参照して演算を行い、ステップＳ５にて設定された条件に対応した評価コストが最も低い経路を求める。求められた経路は、リンク列で表現されて、そのデータはＲＡＭ(19)に記憶される。

ステップＳ６の後、全ての探索条件について経路探索処理(ステップＳ６)が行われたか否かが判断される(Ｓ７)。残りの探索条件がある場合は、探索条件を変えて再度ステップＳ６が行われる。このようにステップＳ６が繰り返して行われて、全ての探索条件について経路探索処理が行われた後、 得られた複数の経路の交点に対応するノード(以下、「交点ノード」と称する)が抽出されて、これら複数の経路の少なくとも何れかの経路の一部分であって、交点ノード間を繋ぐ経路部品を特定する処理が行われる(Ｓ８)。得られた経路部品の情報(例えば、経路部品が属する経路と、経路部品の始端及び終端の交点ノード)は、ＲＡＭ(19)に記憶される。ここで交点とは、経路探索で得られた複数の経路に含まれる２以上の経路が交差する交差点、又は、複数の経路に含まれる２以上の経路が重なった共通部分の端点(道路の合流点又は分岐点に相当する)であって、出発地及び目的地を含む。

図３(a)は、経路探索で得られた経路及び経路部分の一例を示す説明図である。図３(a)には、出発地ノードＮ₁から目的地ノードＮ₂に至る３本の経路である経路Ｒ₁、経路Ｒ₂及び経路Ｒ₃が示されており、例えば、経路Ｒ₁は、一般道路優先を探索条件として、経路Ｒ₂は、距離優先を探索条件として、経路Ｒ₃は、有料道路優先を探索条件として経路探索が行われて得られた経路である。これら３本の経路は、出発地ノードＮ₁及び目的地ノードＮ₂に加えて、交点ノードＮ₃にて交わっている。この場合、ステップＳ８では、経路Ｒ₁の一部であって、出発地ノードＮ₁から交点ノードＮ₃に至る経路部品Ｌ₁と、経路Ｒ₂の一部であって、出発地ノードＮ₁から交点ノードＮ₃に至る経路部品Ｌ₂と、経路Ｒ₃の一部であって、出発地ノードＮ₁から交点ノードＮ₃に至る経路部品Ｌ₃と、経路Ｒ₃の一部であって、交点ノードＮ₃から目的地ノードＮ₂に至る経路部品Ｌ₄と、経路Ｒ₂の一部であって、交点ノードＮ₃から目的地ノードＮ₂に至る経路部品Ｌ₅と、経路Ｒ₁の一部であって、交点ノードＮ₃から目的地ノードＮ₂に至る経路部品Ｌ₆とが特定される。

ステップＳ８の後、制御マイコン(25)は、ＲＡＭ(19)に記憶されている経路及び経路部品の情報やリンクデータ等を参照して、特定された経路部品の各々について、各種経路特性を求めてＲＡＭ(19)に記憶する(Ｓ９)。経路特性には、走行距離、制限速度及び有料道路料金に加えてその経路部品における右折回数、左折回数、交差点数、信号数、ＩＣ数及びカーブ度が含まれる。例として、図４に、図３(a)に示した経路部品の各々に関する経路特性をまとめた表を示す。

走行距離は、その経路部品を実際に走行する場合に要する移動距離である。制限速度は、その経路部品の法規制限速度である(法規制限速度が異なる複数の区間が経路部品に含まれる場合には、平均法規制限速度)。有料道路料金は、経路部品に含まれる有料道路区間の通行料金である。記録媒体(13)には、有料道路の通行料金に関するデータベースが記録されており、有料道路料金を求める際に参照される。なお、経路部品に有料道路区間が含まれない場合、有料道路料金はゼロにされる。

右折回数及び左折回数は、それぞれ、経路部品を走行する際に要する右折回数及び左折回数である。交差点数及びＩＣ数は、それぞれ、経路部品を走行する際に通過する交差点の及びＩＣの数である。カーブ度は、経路部品の走行距離から始端と終端間の直線距離を引いた値である。

ステップＳ９の後、制御マイコン(25)は、ステップＳ８で求めた経路特性に基づいて、各経路部品について評価コストを算出及び記憶する(Ｓ１０)。評価コストは、例えば、以下の式に基づいて算出される。

所用時間(ｈ)は、走行距離を制限速度で除算した値と、経路部品の経路イベント(右折、左折、交差点、信号及びＩＣ)に要する時間の合計である。ドライバ単価(円/ｈ)は、単位時間当たりについて、ドライバ(ユーザ)の労力に相当する金銭的価値を示すものである。本実施例のナビゲーション装置(1)では、ステップＳ３の経路探索設定画面を用いて、ユーザの事情に応じたドライバ単価の設定がなされる。時間的な余裕がなく目的地まで急いでいる状態にて、ユーザが経路探索設定画面にてその旨を指定すると、通常の場合(時間的な余裕がある、又は時間を気にしない場合)と比較して値が大きなドライバ単価が設定されて、ステップＳ１０の演算に使用される。例えば、ドライバ単価は、急いでいる場合には３０００円/ｈに設定されて、通常の場合には２０００円/ｈに設定される。なお、ドライバ単価は、ユーザが金銭的に余裕がある場合にも、通常の場合と比較して高めに設定されてもよい。

消費燃料(リットル)は、走行距離を移動するために消費する燃料の量と、経路イベントにて生じる停止及び発進等で消費する燃料の量との和である。燃料単価(円/リットル)は、単位体積当たりの燃料の価格である。

面倒度(ポイント)は、経路部品の経路イベントにて停止及び発進や方向確認等を行う際に、ユーザが面倒に感じる度合いを、言い換えるとユーザに与えられる精神的及肉体的な疲労感を数値化したものである。面倒度単価(円/ポイント)は、１ポイント当たりの面倒度の金額であって、面倒度を金銭的価値に換算するために用いられる。

右折や左折等を行うために必要な運転上の負担をユーザが気にしない場合は、面倒度及び面倒度単価を含めることなく評価コストが計算されるのが好ましい。よって、本実施例のナビゲーション装置(1)では、ステップＳ３の経路探索設定画面にてその旨が選択された場合、ステップＳ１０にて、面倒度及び面倒度単価を考慮することなく評価コストが算出される。

図５は、経路イベントの各々について、評価コストの計算に用いる数値の一例をまとめた表である。これら数値と、さらに、ドライバ単価、単位距離当たりの自動車の消費燃料、燃料単価及び面倒度単価の値とは、制御マイコン(25)のフラッシュメモリ(23)に記憶されており、ステップＳ１０にて参照される。例えば、ドライバ単価は２０００円/ｈ、自動車の消費燃料は１０リットル/ｋｍ、燃料単価は１００円/リットル、面倒度単価は１円/ポイントとされる。

具体例として、図４及び図５に示した数値と、上記に示す単価とを用いて、図３(a)に示す経路部品Ｌ₁の評価コストを計算してみる。図４から、経路部品Ｌ₁の有料道路料金は０円であって、所用時間、消費燃料及び面倒度の各々は、以下のように算出される。

従って、経路部品Ｌ₁の評価コストは、以下のように求められる(端数は切り捨て)。

その他の経路部品の評価コストも同様にして計算することにより、以下の結果が得られる。

このようにして、ステップＳ１０において、各経路部品の評価コストが算出された後、その結果を用いて、経路部品を組み合わせて得られる出発地から目的地に至る全経路について、評価コストが算出される(Ｓ１１)。ステップＳ１１の後、評価コストが最も安い経路が、経路誘導動作にて用いられる誘導経路として設定されると共に、ＬＣＤ(29)に表示される(Ｓ１２)。図６は、例示したケースにおける、出発地から目的地に至る全経路の評価コストと、評価順位とを示す表である。例示したケースでは、経路部品Ｌ₂及び経路部品Ｌ₄で構成される経路４の評価コストが最も安いことから、図３(b)にて太線で示す経路４が誘導経路として設定されて、また、この経路を表示する画面がＬＣＤ(29)に表示される。ステップＳ１２の後、ナビゲーション装置(1)の経路探索動作は終了し、設定された誘導経路に沿ってユーザを目的地まで導く経路誘導動作が開始される。なお、ステップＳ１２にて、評価コストが最も安い幾つかの経路(例えば、評価コストが１番目乃至５番目に低い５本の経路)をＬＣＤ(29)に表示させて、これらの中から誘導経路として採用する経路をユーザに選択させてもよい。

上記の実施例では、評価コストの計算において、各経路部品について面倒度単価の値は同じであったが、出発地から目的地に至る間で面倒度単価は可変にされてもよい。この場合、出発地から目的地に至るにつれて、運転動作に要するユーザの疲労感は増大することから、目的地に向かって増加するように面倒度単価は変化し、目的地に近い又は目的地を含む経路部品の評価コストの計算では、出発地に近い又は出発地を含む経路部品の評価コストの計算よりも、面倒度単価は大きくされる。

例えば、図３(a)に例示したケースでは、出発地側の経路部品Ｌ₁乃至Ｌ₃の評価コストが計算される際の面倒度単価は１円/ポイントに、目的地側の経路部品Ｌ₄乃至Ｌ₆の評価コストが計算される際の面倒度単価は１.５円/ポイントにされてよい。図３(a)に例示したケースは、説明の分かり易さを考慮した簡単な例であって、実際には、２本を超えるかなりの数の経路部品を組み合わせて得られる経路について、評価コストを求めるケースが多いであろう。故に、面倒度単価は、例えば、出発地側の(全経路の)３０％の経路部品については１円/ポイント、中間の４０％の経路部品については１.５円/ポイント、目的地側の残り３０％の経路部品については２円/ポイントになるように設定されてもよい。

また、出発地側では若干費用がかさんでも速く移動したい事情がある場合を考慮して、ドライバ単価は、上記の面倒度単価と似たように可変にされてもよい。例えば、図３(a)に例示したケースでは、出発地側の経路部品Ｌ₁乃至Ｌ₃の評価コストが計算される際のドライバ単価は２５００円に、目的地側の経路部品Ｌ₄乃至Ｌ₆の評価コストが計算される際のドライバ単価は２０００円にされてよい。さらに、ドライバ単価は、出発地側の(全経路の)３０％の経路部品については３０００円、中間の４０％の経路部品については２５００円、目的地側の残り３０％の経路部品については２０００円と設定されてもよい。なお、目的地側で速く移動したい事情がある場合には、逆に目的地に向かってより大きくなるようにドライバ単価は変化してもよい。

本発明の実施をするための装置構成は、上記実施例に限定されることはなく、例えば、図２と共に説明した経路探索動作における経路探索処理や評価コストの演算処理は、インターネット等を介してナビゲーション装置(1)と通信接続されたサーバ装置にて別途行われてもよい。また、本発明は、自動車用のナビゲーション装置に限定されることはなく、２輪車やその他の車両用のナビゲーション装置に適用されてよい。

上記実施例では、条件を変えて経路探索を複数回行って、出発地から目的地に至る性格の異なった複数の経路を求めて、その後、それら経路の交点間を繋ぐ経路部品を求めていたが、ある特定の条件下のみで経路探索を行うことで、複数の経路が得られてもよい。例えば、距離優先の条件で経路探索が行われて、評価コストが最も低い経路を含む、評価コストの値が異なる幾つかの経路が選択されてもよい。しかしながら、本発明では、似たような性格の複数の経路部品が存在することはあまり好ましくないことから、上記実施例のように、性格の異なる複数の経路を生成して、これら経路の経路部品を求めることが好ましい。また、このような複数の経路を用意することなく、先に示した数式に準じた評価コストを採用して経路探索を行うことで、誘導経路となる経路が生成されてもよい。しかしながら、上記実施例のように複数の経路から経路部品を特定し、その組合せによる経路について様々な要素を盛り込んだ評価コストを求めることで、車載式ナビゲーション装置において本発明の特徴とする経路探索が現実的に可能とされる(車載式ビゲーション装置(1)では、使用される制御マイコン(25)の演算能力は制限される)。必要な演算の大半がサーバ装置にて行われる実施形態では、先に示した数式に準じた評価コストを採用して経路探索を行うことで、誘導経路となる経路が生成されるのが好ましいであろう。

上記実施例の説明は、本発明を説明するためのものであって、特許請求の範囲に記載の発明を限定し、或は範囲を減縮する様に解すべきではない。本発明の各部構成は上記実施例に限らず、特許請求の範囲に記載の技術的範囲内で種々の変形が可能であることは勿論である。

本発明の実施例であるナビゲーション装置のブロック図である。 本発明の実施例であるナビゲーション装置の経路探索動作を示すフローチャートである。 図３(a)は、本発明の実施例であるナビゲーション装置で生成される経路部品の一例を示す説明図であり、図３(b)は、同ナビゲーション装置で生成される誘導経路を示す説明図である。 図３(a)に示した経路部品の各々に関する経路特性をまとめた表である。 経路イベントの各々について、評価コストの計算に用いる数値の一例をまとめた表である。 図３(a)に示した経路部品を組み合わせて得られる出発地から目的地に至る全経路の評価コストと、評価順位とを示す表である。

符号の説明

(1) ナビゲーション装置
(5) ＧＰＳ受信部
(13) 記録媒体
(25) 制御マイクロコンピュータ
(29) 液晶表示装置

Claims (12)

1. 異なる探索条件下で出発地から目的地に至る複数の経路を生成し、前記複数の経路の少なくとも何れか１つの一部であって、前記複数の経路の交点間を繋ぐ複数の経路部品を特定し、各経路部品について評価コストを算出し、前記複数の経路部品を選択的に組み合わせて生成される前記出発地から前記目的地に至る経路の各々について前記評価コストを求め、前記求めた評価コストが最も低い経路を案内することを特徴とする経路探索装置。
2. 前記評価コストは、前記出発地から前記目的地までの移動に実際に要する第１費用、前記出発地から前記目的地までの移動に要する所用時間を金銭に換算した第２費用および前記出発地から前記目的地まで移動した場合にもたらされる面倒に相当する第３費用のうち１つ以上の費用を含むことを特徴とする請求項１に記載の経路探索装置。
3. 前記第１費用は、前記出発地から前記目的地までの移動で消費する消費燃料と燃料単価の積を含んでおり、前記消費燃料は、移動距離に比例する燃料とは別に、前記出発地から前記目的地に至るまでに存在する右折、左折、交差点、信号及びインターチェンジの少なくとも１つで消費する燃料を含む、請求項２に記載の経路探索装置。
4. 前記所用時間を金銭に換算する係数は、ユーザによって選択的に設定されることを特徴とする請求項２に記載の経路探索装置。
5. 前記面倒に相当する第３費用では、前記出発地から前記目的地に至るまでの右折回数、左折回数、交差点数、信号数、インターチェンジ数、及び経路のカーブの度合いの少なくとも１つが金銭に換算されている、請求項２に記載の経路探索装置。
6. ある経路部品に関する前記評価コストの算出にて、前記所用時間を金銭に換算する係数および／または前記面倒に相当する第３費用を求めるために、その経路部品で生じるイベントを金銭に換算する係数は、前記出発地と前記目的地の間におけるその経路部品の位置に応じて変化する、請求項１乃至５の何れかに記載の経路探索装置。
7. 異なる探索条件下で出発地から目的地に至る複数の経路を生成する工程と、前記複数の経路の少なくとも何れか１つの一部であって、前記複数の経路の交点間を繋ぐ複数の経路部品を特定する工程と、各経路部品について前記評価コストを算出する工程と、前記複数の経路部品を選択的に組み合わせて生成される前記出発地から前記目的地に至る経路の各々について前記評価コストを求める工程と、前記求めた評価コストが最も低い経路を案内する工程と、を含む、経路探索方法。
8. 前記評価コストは、前記出発地から前記目的地までの移動に実際に要する第１費用、前記出発地から前記目的地までの移動に要する所用時間を金銭に換算した第２費用および前記出発地から前記目的地まで移動した場合にもたらされる面倒に相当する第３費用のうち１つ以上の費用を含むことを特徴とする請求項７に記載の経路探索方法。
9. 前記第１費用は、前記出発地から前記目的地までの移動で消費する消費燃料と燃料単価の積を含んでおり、前記消費燃料は、移動距離に比例する燃料とは別に、前記出発地から前記目的地に至るまでに存在する右折、左折、交差点、信号及びインターチェンジの少なくとも１つで消費する燃料を含む、請求項８に記載の経路探索方法。
10. 前記所用時間を金銭に換算する係数は、ユーザによって選択的に設定されることを特徴とする請求項８に記載の経路探索方法。
11. 前記面倒に相当する第３費用では、前記出発地から前記目的地に至るまでの右折回数、左折回数、交差点数、信号数、インターチェンジ数、及び経路のカーブの度合いの少なくとも１つが金銭に換算されている、請求項８に記載の経路探索方法。
12. ある経路部品に関する前記評価コストの算出にて、前記所用時間を金銭に換算する係数および／または前記面倒に相当する第３費用を求めるために、その経路部品で生じるイベントを金銭に換算する係数は、前記出発地と前記目的地の間におけるその経路部品の位置に応じて変化する、請求項７乃至１１の何れかに記載の経路探索方法。

Images