Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
経路探索システム、経路探索方法および経路探索プログラム
説明

経路探索システム、経路探索方法および経路探索プログラム

【課題】初期経路である既設経路と同じ区間を走行させる経路が探索される可能性を低減する。
【解決手段】現在地点Pから目的地点Gまでの既設経路Rを示す既設経路情報を取得し、現在地点Pから指定距離dだけ目的地点G側までの区間を指定区間Dとし、現在地点Pから最初に到達する交差点である始点交差点Iを始点とする区間を第1迂回区間Qとし、第1迂回区間Qの経路探索コストを補正する補正率を経路探索コストを増大させる第1補正率に設定し、指定区間Dのうち第1迂回区間Qを除く区間である第2迂回区間Wについての経路探索コストを補正する補正率を第1補正率よりも小さくかつ経路探索コストを増大させる第2補正率に設定し、第1迂回区間と第2迂回区間とのそれぞれに対応するリンクについての経路探索コストをそれぞれ第1補正率と第2補正率とに基づいて補正し、経路探索コストの総和を最小化させるリンク群に対応する経路を探索する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、経路探索システム、経路探索方法および経路探索プログラムに関する。
【背景技術】
【0002】
経路上の迂回区間について他の区間よりも大きい補正率を設定し、当該補正率に応じて補正した経路探索コストに基づいて、経路を再探索する手法が知られている(特許文献1、参照。)。迂回区間について他の区間よりも大きい補正率によって経路探索コストが増大されるため、迂回区間を迂回するように経路を再探索することができる。また、特許文献1において、ユーザは迂回区間の距離が指定できるため、ユーザの希望に即した範囲について迂回する経路を再探索することができる。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特許第3065978号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
多くの場合、渋滞等により既設の経路に不満を持った場合にユーザが経路の再探索を行う。しかしながら、特許文献1において、再探索を行っても現在走行している道路の次に走行する予定の道路(以下、次走行予定道路と表す)が再探索後の経路の構成区間として採用されるという問題があった。すなわち、経路を再探索したにも拘わらず、次の交差点で修正前と同じ次走行予定道路へと案内がなされることにより、ユーザが再探索後の経路に満足できないという問題があった。このような問題は、次走行予定道路についての経路探索コストが十分に大きくなっていないことに起因して生じる。なお、本明細書において道路とは始点と終点とが交差点となる道路区間を指し、地図情報上のリンクに対応する。一方、区間も道路区間を指すが、区間の始点と終点とが交差点となるとは限らず、区間が地図情報上のリンクに対応するとは限らない。
【0005】
次走行予定道路についての経路探索コストが十分に大きくならない理由の一つとして、次走行予定道路が短い(次の交差点までの距離が短い)ことが挙げられる。経路探索コストは道路の長さに比例するため、次走行予定道路全体が迂回区間に含まれることにより経路探索コストが大きく補正されたとしても、次走行予定道路が短ければ、次走行予定道路についての経路探索コストが十分に大きくならない。この場合、次走行予定道路を経由して次の交差点にて既設の経路とは別の道路へと退出する経路が再探索され得る。特に、次走行予定道路が短いと、当該次走行予定道路の車線と反対車線についての経路探索コストも小さくなるため、次走行予定道路を通過して次の交差点にて次走行予定道路の反対側車線へとUターンすることにより増加する経路探索コストも小さくなる。従って、次走行予定道路の反対側車線へとUターンする経路が再探索されるような場合も生じ、再探索した経路にユーザが大きな不満を抱く。
【0006】
次走行予定道路についての経路探索コストが十分に大きくならない別の理由の一つとして、次走行予定道路が長くても、最初に到達する交差点から近い位置にて迂回区間が終了していることが挙げられる。すなわち、次走行予定道路のうち迂回区間と重複する区間が短くなるため、当該重複する区間について経路探索コストを大きく補正しても、次走行予定道路についての経路探索コストが十分に大きくならない。特に引用文献1の場合、ユーザにより迂回区間の距離が指定されるため、ユーザにより迂回区間の距離が短く指定された場合には次走行予定道路のうち迂回区間と重複する区間が短くなりやすい。
本発明は、前記課題にかんがみてなされたものであり、最初に到達する交差点の通過後に既設経路と同じ区間を走行させる経路が探索される可能性を低減することを目的とする。
【課題を解決するための手段】
【0007】
前記の目的を達成するため、本発明の経路探索システムにおいて、既設経路情報取得手段は、現在地点から目的地点までの経路である既設経路を示す既設経路情報を取得する。指定区間設定手段は、既設経路上において現在地点からユーザにより指定された指定距離だけ目的地点側に進んだ地点までの区間を指定区間として設定する。第1迂回区間設定手段は、既設経路上において現在地点から最初に到達する交差点である始点交差点を始点とする前記既設経路上の区間を第1迂回区間として設定する。第1補正率設定手段は、第1迂回区間についての経路探索コストを補正する補正率を、経路探索コストを増大させる第1補正率に設定する。さらに、第2補正率設定手段は、指定区間のうち第1迂回区間を除く区間である第2迂回区間についての補正率を、第1補正率よりも小さく、かつ、経路探索コストを増大させる第2補正率に設定する。すなわち、第2迂回区間についても当該経路探索コストを増大させる第2補正率を設定するが、第1迂回区間についての第1補正率を第2迂回区間についての第2補正率よりも大きくする。そして、経路探索手段は、第1迂回区間と第2迂回区間とのそれぞれに対応するリンクについての経路探索コストをそれぞれ第1補正率と第2補正率とに基づいて補正し、経路探索コストの総和を最小化させるリンク群に対応する経路を既設経路の修正経路として探索する。すなわち、第2迂回区間についての経路探索コストを第2補正率によって増大させるように補正し、第1迂回区間についての経路探索コストを第2補正率よりも大きい第1補正率により増大させるように補正する。そして、第1補正率および第2補正率による補正がされた経路探索コストを最小化させるリンク群に対応する経路を既設経路の修正経路として探索する。
【0008】
以上の構成において、既設経路上において始点交差点を始点とする第1迂回区間は、既設経路上において始点交差点の通過後に走行する予定の道路(以下、次走行予定道路と表す)と始点が共通する。すなわち、第1迂回区間と次走行予定道路とは少なくとも一部が重複する関係を有する。この関係は、ユーザによって指定距離がどのように指定されても維持される。従って、第1補正率設定手段が次走行予定道路と少なくとも一部が重複する第1迂回区間について経路探索コストを増大させる第1補正率を設定することにより、指定距離に拘わらず次走行予定道路に対応するリンクの経路探索コストを第1補正率により増大させることができる。従って、次走行予定道路に対応するリンクが修正経路の構成リンクとして採用される可能性を低減できる。ここで、リンクの経路探索コストは、リンクに対応する道路の長さに比例し、例えば道路の道幅や車線数や渋滞度や平均移動速度等に応じた調整率を道路の長さに乗じることにより得られる。従って、次走行予定道路が短いほど、次走行予定道路に対応するリンクについての経路探索コストが小さくなる。しかし、第1迂回区間と重複する次走行予定道路について第2補正率よりも大きい第1補正率を設定することにより、次走行予定道路の長さが短い場合でも、次走行予定道路に対応するリンクについての経路探索コストを大きく確保することができる。従って、次走行予定道路の長さが短くても次走行予定道路に対応するリンクが修正経路の構成リンクとして採用される可能性を低減できる。
【0009】
一方、既設経路上において現在地点からユーザにより指定された指定距離だけ目的地点側に進んだ地点までの区間である指定区間から第1迂回区間を除いた第2迂回区間については、第2補正率により経路探索コストが増大させられる。第1迂回区間については、別途、経路探索コストを増大させる第1補正率が設定されるため、ユーザにより指定された指定距離を有する指定区間の全体について、経路探索コストを増大させる補正率(第1補正率、第2補正率)を設定できる。従って、ユーザにより指定された指定距離を有する指定区間に対応するリンクが修正経路の構成リンクとして採用される可能性を低減できる。すなわち、ユーザが指定した範囲について既設経路を迂回する修正経路が探索できる。また、第1迂回区間と第2迂回区間の双方に第1補正率を設定せず、第2迂回区間について第1補正率よりも小さい第2補正率を設定することにより、経路探索コストの総和が大きくなりすぎることの弊害が防止できる。
【0010】
なお、既設経路上において現在地点から始点交差点までの距離よりも、短い指定距離が指定された場合、指定区間の終点は第1迂回区間の始点よりも現在地点側となり、指定区間と第1迂回区間とは重複しないこととなる。この場合、指定区間から第1迂回区間を除いた第2迂回区間は、指定区間そのものとなる。また、この場合、指定区間の終点は第1迂回区間の始点よりも現在地点側となる。すなわち、現在地点から始点交差点に到達するまでの迂回し得ない区間内に指定区間(第2迂回区間)の全体が存在することとなり、当該第2迂回区間に対して第2補正率が設定されることとなる。このような場合であっても、始点交差点を始点とする第1迂回区間について第1補正率が設定されるため、ユーザによって指定距離がどのように指定されても次走行予定道路が修正経路の構成区間として採用される可能性を低減できる。
【0011】
既設経路情報取得手段は、現在地点から目的地点までの既設経路を示す既設経路情報を取得すればよく、既設経路は現在案内されている経路であってもよい。また、既設経路は、過去に探索された修正経路であってもよい。通常、出発地点から目的地点までの経路が探索されるが、当該経路のうち出発地点から経路上を移動して現在にて到達した現在地点から目的地点までの部分が既設経路に相当する。なお、出発地点にて修正経路の探索を行ってもよく、この場合、現在地点と出発地点とが一致する。
【0012】
指定区間設定手段は、既設経路上において現在地点から指定距離だけ目的地点側に進んだ指定区間を設定すればよく、指定距離はユーザから直接的または間接的に指定されてもよい。例えば既設経路上においてユーザから指定された指定地点を取得し、現在地点から指定地点までの既設経路上の距離を指定距離として間接的に取得してもよい。この場合、指定区間の終点が指定地点となる。
【0013】
第1迂回区間設定手段は、既設経路上において始点交差点を始点とする第1迂回区間を設定すればよく、第1迂回区間は所定距離の区間であってもよいし、所定数の交差点を含む区間であってもよい。地図情報において、交差点に対応するノードを接続するリンクにより道路が規定されるが、既設経路に対応するリンクのうち、始点交差点に対応するノードに接続するリンク(次走行予定道路に対応するリンク)が第1迂回区間に対応する最初のリンクとなる。なお、第1迂回区間内に次走行予定道路の終点が存在する場合もあるし、第1迂回区間の全体を次走行予定道路が含む場合もある。第1迂回区間内に次走行予定道路の終点が存在する場合、すなわち次走行予定道路が第1迂回区間よりも短い場合でも、第1迂回区間について第2補正率よりも大きい第1補正率を設定するため、第1迂回区間と重複する次走行予定道路についての経路探索コストを大きく確保することができる。
【0014】
第1補正率設定手段と第2補正率設定手段とは、経路探索コストを増大させ、かつ、(第1補正率)>(第2補正率)の関係を満足する第1補正率と第2補正率とをそれぞれ第1迂回区間と第2迂回区間とに設定すればよい。経路探索コストを増大させるとは、第1補正率と第2補正率に応じて補正した後の方が、第1補正率と第2補正率に応じて補正する前よりも経路探索コストが大きくなることを意味する。すなわち、第1補正率と第2補正率とが1よりも大きいことを意味する。第1補正率設定手段は、第1迂回区間に対応する地図情報上のリンクの全体または一部を特定し、当該リンクの全体または一部に対して第1補正率を設定すればよい。同様に第2補正率設定手段は、第2迂回区間に対応するリンクの全体または一部に対して第2補正率を設定すればよい。なお、リンクについての経路探索コストは、例えばリンクに対応する道路の道幅や車線数や渋滞度や平均移動速度等に応じた調整率を道路の長さに乗じることにより得られるが、第1補正率設定手段と第2補正率設定手段とは、調整率が乗算された経路探索コストに対して、さらに補正するための第1補正率と第2補正率とを設定することとなる。
【0015】
ここで、次走行予定道路を構成区間とした修正経路が探索される可能性を低減させるためには、第1補正率をできるだけ大きく設定するのが望ましい。ただし、経路探索コストの総和が大きくなり過ぎることの弊害が生じない程度に、第1補正率を設定すべきである。例えば、経路探索コストの総和が所定の制限桁数以上へと桁上がりを起こさない範囲で第1補正率を大きく設定してもよい。制限桁数は、例えば経路探索コストの総和を計算する演算装置が処理できる桁数の上限値や、当該総和を記録するレジスタが記録できる桁数の上限値や、プログラム上において当該総和について定義されたデータの型の桁数等によって定めることができる。なお、基本的に、経路探索コストの総和は現在地点と目的地点とが遠いほど大きくなるため、現在地点と目的地点とが遠いほど第1補正率を下方修正するようにしてもよい。一方、第2補正率は、第1補正率より小さく1よりも大きければよく、例えば第1補正率に1未満の所定係数を乗算した値であってもよい。また、第1補正率が大きいほど次走行予定道路が迂回される可能性が高くなるため、次走行予定道路の迂回希望度をユーザから受け付け、当該迂回希望度に応じて第1補正率を設定してもよい。
【0016】
経路探索手段は、第1迂回区間と第2迂回区間とのそれぞれに対応するリンクについての経路探索コストをそれぞれ第1補正率と第2補正率とに基づいて補正する。ここで、第1迂回区間と第2迂回区間とのそれぞれに対応するリンクには、全体が第1迂回区間と第2迂回区間とのそれぞれと重複する道路に対応するリンクが含まれる。また、第1迂回区間と第2迂回区間とのそれぞれに対応するリンクに、一部のみが第1迂回区間と第2迂回区間とのそれぞれに重複する道路に対応するリンクが含まれてもよい。この場合、第1迂回区間と重複する部分の長さの道路全体の長さに対する占有割合に応じて調整された第1補正率に基づいて、当該道路に対応するリンクの経路探索コストを補正してもよい。同様に、第2迂回区間と重複する部分の長さの道路全体の長さに対する占有割合に応じて調整された第2補正率に基づいて、当該道路に対応するリンクの経路探索コストを補正してもよい。経路探索手段は、補正後の経路探索コストの総和を最小化させるリンク群を探索すればよく、経路探索コストを利用した種々の経路探索手法を採用することができる。例えば、経路探索手法として、ダイクストラ法やA*アルゴリズム、それらの改良型アルゴリズムなどを採用してもよい。
【0017】
ここで、指定区間設定手段は、始点交差点を含む指定区間を設定してもよい。すなわち、指定区間設定手段は、既設経路上において現在地点から始点交差点までの距離よりも長い指定距離が指定されるようにしてもよい。既設経路上において現在地点から始点交差点までの距離よりも指定距離が長ければ、指定区間に始点交差点よりも目的地点側の区間が含まれることとなる。すなわち、現在地点から始点交差点に到達するまでの迂回し得ない区間内のみに存在する指定区間(第2迂回区間)に対して第2補正率が設定されることが防止できる。従って、迂回し得ない区間内のみに存在する第2迂回区間に対して第2補正率を設定することにより、経路探索コストが無駄に増大することが防止できる。
【0018】
この場合において、第1迂回区間設定手段は、既設経路上において始点交差点から目的地点側に一定距離だけ進んだ地点と、指定区間の終点とのうち、現在地点に近い方を第1迂回区間の終点と設定してもよい。これにより、指定区間の終点の方が始点交差点から目的地点側に一定距離だけ進んだ地点よりも現在地点に近い場合には、第1補正率が設定される第1迂回区間の終点を指定区間の終点と一致させることができる。既設経路上において指定区間の終点よりも目的地点側の区間については、ユーザが迂回を希望しない範囲あり、ユーザが迂回を希望しない範囲の区間にまで第1補正率が適用されることが防止できる。すなわち、既設経路上においてユーザが迂回を希望しない範囲(指定距離以遠)の区間まで迂回させるような経路探索を行うことが防止できる。この場合、第1迂回区間の長さが一定距離よりも短くなるが、第1迂回区間についての第1補正率を第2補正率よりも大きくしておくことにより、次走行予定道路についての補正後の経路探索コストを十分に大きく確保することができる。
【0019】
なお、第2補正率設定手段は、既設経路上における現在地点からの距離が短くなるほど第2補正率を大きく設定してもよい。これにより、第2迂回区間のうち現在地点に近い区間ほど、既設経路の構成区間として採用される可能性を低減できる。現在地点に近い既設経路上の区間ほど迂回される可能性が高くなるため、既設経路が修正されたことをユーザに強く印象づけることができる。この場合、第2迂回区間のうち現在地点に遠い区間ほど第2補正率が小さくされるが、第2補正率が小さくされる区間が既設経路上の始点交差点を含んでいたとしても、始点交差点を始点とする第1迂回区間については第2補正率よりも大きい第1補正率が設定されるため、既設経路の次走行予定道路を構成区間とした修正経路が探索される可能性を低減できる。
【0020】
また、第1迂回区間設定手段は、通過後に退出可能な退出リンクが複数接続する既設経路上の交差点のうち、現在地点から最初に到達する交差点を始点交差点と設定してもよい。すなわち、第1迂回区間は、通過後に退出できる退出リンクに2個以上の選択肢(そのうち1個は既設経路上の道路)が存在する交差点を始点とするのが望ましい。既設経路上の区間以外の退出リンクの選択肢が存在しない交差点を第1迂回区間の始点とし、当該交差点を始点とした第1迂回区間に第1補正率を設定したとしても、当該交差点にて当該第1迂回区間を迂回する経路は探索し得ないからである。すなわち、迂回し得ない第1迂回区間に第1補正率を設定しないことにより、経路探索コストが無駄に増大することが防止できる。むろん、通過後に退出可能な退出リンクが既設経路上の道路以外に1個以上接続する交差点であるか否かの判定を省略することにより、処理負荷を軽減してもよい。
【0021】
さらに、現在地点を始点とする直進優先区間が設定できるようにしてもよい。直進優先手段は、直進優先区間において、交差点を通過後において非直進方向に退出する退出リンクについての補正率である非直進補正率を、当該交差点を通過後において直進方向に退出する退出リンクについての補正率である直進補正率よりも大きく、かつ、第1補正率よりも小さく設定する。このようにして設定された補正率に応じて補正した経路探索コストを利用して経路探索手段が修正経路を探索することにより、直進優先区間においては直進を優先して修正経路を探索できる。すなわち、急な右左折を要する修正経路をユーザに案内することが防止できる。なお、交差点を通過後において直進方向に退出するとは、交差点に対する進入方向と退出方向との角度差が所定角度よりも小さいことであってもよい。この場合、交差点を通過後において非直進方向に退出するとは、交差点に対する進入方向と退出方向との角度差が所定角度以上であることを意味する。
【0022】
ここで、直進優先区間に始点交差点が存在する場合も考えられる。この場合において、第1補正率設定手段は、直進優先区間上の交差点から通過後に非直進方向に退出する退出リンクのうち第1迂回区間と重複する部分については非直進補正率に優先させて第1補正率を設定する。同様に、直進優先区間上の交差点から通過後に直進方向に退出する退出リンクのうち第1迂回区間と重複する部分については直進補正率に優先させて第1補正率を設定する。すなわち、第1迂回区間については始点交差点の通過後の退出方向に拘わらず第1補正率が設定される。この第1補正率は、非直進補正率よりも大きいため、既設経路において始点交差点の次に走行する予定の次走行予定道路が直進方向である場合でも、当該次走行予定道路を構成区間とした修正経路が探索される可能性を低減できる。なお、非直進補正率は直進補正率に対して相対的に大きければよく、必ずしも経路探索コストを増大させる値(>1)でなくてもよい。
【0023】
なお、本発明のように、第1補正率と第2補正率とを第1迂回区間と第2迂回区間とに設定して経路探索する手法は、この処理を行う方法やプログラムとしても適用可能である。また、本発明の手法を適用した経路探索システム、方法、プログラムは、単独の装置として実現される場合もあれば、複数の装置として実現される場合もある。例えば、経路探索システムを構成する各手段が複数の実体的な装置に備えられてもよい。むろん、複数の実体的な装置に備えられた各手段を連携させるための通信手段が備えられてもよい。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、経路探索システムを制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【図面の簡単な説明】
【0024】
【図1】ナビゲーション装置を示すブロック図である。
【図2】(2A),(2B)は既設経路を示す図、(2C),(2D)は補正率のグラフである。
【図3】修正経路探索処理のフローチャートである。
【図4】補正率テーブル作成処理のフローチャートである。
【図5】直進優先区間の説明図である。
【発明を実施するための形態】
【0025】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
(1)経路探索システムの構成:
(2)修正経路探索処理:
(3)他の実施形態:
【0026】
(1)経路探索システムの構成:
図1は、経路探索システムとしてのナビゲーション装置10の構成を示すブロック図である。ナビゲーション装置10は、車両Cに搭載される。車両Cは、GPS受信部41と車速センサ42とジャイロセンサ43とユーザI/F部44とを備える。GPS受信部41と車速センサ42とジャイロセンサ43とユーザI/F部44がナビゲーション装置10との間で各種信号を入出力するためのインタフェース(不図示)が備えられている。GPS受信部41は、GPS衛星からの電波を受信し、車両Cの現在地点を算出するための信号をナビゲーション装置10に出力する。車速センサ42は、車両Cが備える車輪の回転速度に対応した信号を、ナビゲーション装置10に出力する。ジャイロセンサ43は、車両Cの向きに対応した信号を、ナビゲーション装置10に出力する。ユーザI/F部44は、ナビゲーション装置10から出力された制御信号に基づいて経路案内のための画像や音声を出力する出力装置(ディスプレイ,スピーカ等)を含む。また、ユーザI/F部44は、ユーザの操作を受け付けるための入力装置(タッチセンサ,ボタン等)を含み、当該入力装置にて受け付けた操作に対応する操作信号をナビゲーション装置10に出力する。
【0027】
ナビゲーション装置10は、CPUとRAMとROM等を備える制御部11と記録媒体12とを備える。制御部11は、記録媒体12やROMに記録された経路探索プログラムとしてのナビゲーションプログラム100を実行する。記録媒体12は、地図情報12aと経路情報12bと補正率テーブル12cとを記録する。地図情報12aは、車両Cが走行する道路上の交差点に対応して設定されたノードの位置等を示すノードデータと、交差点間を接続する道路に対応するリンクを示すリンクデータと、リンクの形状を特定するための形状補間点データ等を含んでいる。また、リンクデータは、リンクの長さを示す。経路情報12bは、出発地点から目的地点へと到達するための経路の構成リンクを特定するデータである。補正率テーブル12cは、後述する経路探索処理において各リンクの経路探索コストを補正するための補正率を規定するデータである。
【0028】
ナビゲーションプログラム100は、ナビゲーション部110と既設経路情報取得部120と指定区間設定部130と第1迂回区間設定部140と第1補正率設定部150と第2補正率設定部160と経路探索部170とを含む。
ナビゲーション部110は、ユーザI/F部44によってユーザに経路を案内させる機能を制御部11に実行させるモジュールである。制御部11は、経路を経路情報12bに基づいて特定し、経路情報12bが修正されれば修正後の経路を案内させる。また、ナビゲーション部110の機能により制御部11は、GPS受信部41と車速センサ42とジャイロセンサ43からの出力信号、および、地図情報12a等に基づいて、車両Cが現在において位置している現在地点と、車両Cが走行している区間とを特定する。
【0029】
既設経路情報取得部120は、現在地点から目的地点までの経路である既設経路を示す既設経路情報を取得する機能を制御部11に実行させるモジュールである。すなわち、既設経路情報取得部120の機能により制御部11は、出発地点から目的地点までの経路を示す経路情報12bを取得し、当該経路情報12bが示す経路のうち現在地点から目的地点までの部分を示す既設経路情報を取得する。
【0030】
指定区間設定部130は、既設経路上において現在地点からユーザにより指定された指定距離だけ目的地点側に進んだ地点までの区間を指定区間として設定する機能を制御部11に実行させるモジュールである。指定区間設定部130の機能により制御部11は、地図情報12aと経路情報12bとを参照して、通過後に退出可能な退出道路が複数接続する既設経路上の交差点のうち、現在地点から最初に到達する交差点(以下、始点交差点と表す)を特定する。制御部11は、退出可能な退出リンクが複数接続するノードであって、現在地点を含む道路に対応するリンクが進入可能な進入リンクとして接続するノードに対応する交差点を始点交差点と表す。すなわち、現在地点から進入する進入道路と、通過後に退出できる既設経路上の退出道路と、通過後に退出できる既設経路上にない1個以上の退出道路が接続している交差点が始点交差点となり得る。なお、通過後に退出できる退出道路には、交差点をUターンして進入道路と反対方向に退出する退出道路も含まれる。従って、右折とUターンしかできない交差点等も始点交差点となり得る。一方、現在地点から進入する進入道路と、通過後に退出できる既設経路上の退出道路との他に、他の進入道路のみが接続する交差点は始点交差点となり得ない。例えば、高速道路の本線に対して、インターチェンジ等からの合流レーンが合流する合流地点においては、通過後に退出できる道路は高速道路の本線のみとなるため、当該合流地点は始点交差点となり得ない。
【0031】
また、指定区間設定部130の機能により制御部11は、始点交差点を含む指定区間を設定する。すなわち、制御部11は、既設経路上における現在地点から始点交差点までの距離を指定距離の下限値とする。そして、指定区間設定部130の機能により制御部11は、ユーザI/F部44を介して下限値よりも大きい指定距離の指定を受け付ける。例えば、制御部11は、ユーザI/F部44が備えるディスプレイやスピーカにて"この先、どれだけの距離を迂回しますか"等のメッセージを出力させ、下限値よりも大きい複数の指定距離を選択できるように提示する。そして、制御部11は、選択された指定距離を取得する。例えば、既設経路の前方に渋滞区間が生じている場合に、当該渋滞区間が指定区間に含まれるようにユーザが指定距離を指定する。
【0032】
指定距離が指定されると、指定区間設定部130の機能により制御部11は、既設経路上において現在地点から指定距離だけ目的地点側に進んだ地点までの区間を指定区間として設定する。上述のように指定距離の下限値は、既設経路上における現在地点から始点交差点までの距離とされるため、指定区間には始点交差点が含まれることとなる。指定区間設定部130の機能により制御部11は、指定区間を設定すると、長さが均等となるように指定区間をN(Nは1以上の整数、本実施形態でN=4)等分することにより分割指定区間を設定する。
【0033】
図2A,2Bは、既設経路Rを説明する図である。既設経路R上の道路に対応するリンクを太線矢印で示し、既設経路R上にない道路に対応するリンクを破線矢印で示し、各道路が接続する交差点に対応するノードを白丸で示し、現在地点Pを二重丸で示す。また、括弧内の記号は距離を表す。矢印の方向は車両Cが走行できる方向を示す。既設経路R上における現在地点Pと指定区間Dの終点TDとの距離が指定距離dDとなる。指定距離dDは、既設経路R上における現在地点Pと始点交差点Iとの距離よりも大きく、指定区間Dに始点交差点Iが含まれる。また、指定区間DをN(=4)等分した分割指定区間D1〜D4が設定されている。分割指定区間D1〜D4の長さは、指定距離dDの1/Nの長さとなる。現在地点Pおよび分割指定区間D1〜D4の始点と終点とは必ずしも交差点とならない。そこで、制御部11は、地図情報12aにおいて、分割指定区間D1〜D4の始点と終点とに対応する仮想ノードを設定し、当該仮想ノードを少なくとも一端とする仮想リンクを設定する。
【0034】
第1迂回区間設定部140は、既設経路R上において現在地点Pから最初に到達する始点交差点Iを始点とする既設経路R上の区間を第1迂回区間Qとして設定する機能を制御部11に実行させるモジュールである。具体的に、第1迂回区間設定部140の機能により制御部11は、既設経路R上において始点交差点Iから目的地点G側に一定距離dCだけ進んだ地点TCと、指定区間Dの終点TDとのうち、既設経路Rにおいて現在地点Pに近い方を第1迂回区間Qの終点TQと設定する。第1迂回区間Qの終点TQが交差点とならない場合も、地図情報12aにおいて、第1迂回区間Qの終点TQに対応する仮想ノードを終点とする仮想リンクを設定し、当該仮想リンクを第1迂回区間Qに対応する最後のリンクとする。一定距離dCは、予め定められた固定の距離であり、本実施形態では500[m]とされる。
【0035】
図2Aの例では、既設経路R上において始点交差点Iから目的地点G側に一定距離dCだけ進んだ地点TCの方が、指定区間Dの終点TDよりも、既設経路R上において現在地点Pに近いため、当該地点TCが第1迂回区間Qの終点TQと一致する。この場合、第1迂回区間Qの長さは一定距離dCとなる。また、図2Aの例において、既設経路R上において始点交差点Iの次に走行するとされた次走行予定道路Mの長さが一定距離dCよりも短く、当該次の交差点Hは第1迂回区間Q内に存在している。
【0036】
一方、図2Bの例では、既設経路R上において始点交差点Iから目的地点G側に一定距離dCだけ進んだ地点TCよりも、指定区間Dの終点TDの方が、既設経路R上において現在地点Pに近いため、指定区間Dの終点TDが第1迂回区間Qの終点TQと一致する。この場合、第1迂回区間Qの長さは一定距離dCよりも短くなる。また、図2Bの例において、始点交差点Iの次の交差点Hが終点TQよりも現在地点Pから遠く、第1迂回区間Qの終点TQは単一のリンクに対応する次走行予定道路M内に存在する。この場合、次走行予定道路Mに対応するリンクに第1迂回区間Qの全体に対応する仮想リンクが含まれることとなる。
【0037】
第1補正率設定部150は、第1迂回区間Qについての経路探索コストを補正する補正率を、経路探索コストを増大させる第1補正率に設定する機能を制御部11に実行させるモジュールである。経路探索コストは、リンクの長さに、例えばリンクに対応する道路の道幅や車線数や渋滞度や平均移動速度等に応じた調整率を乗じることにより得られる。すなわち、第1迂回区間Qに対応するリンクのそれぞれについて長さに比例した経路探索コストが得られるが、制御部11は、当該経路探索コストに乗算することにより、当該経路探索コストを補正する補正率を第1補正率に設定する。なお、第1補正率設定部150の機能により制御部11は、第1迂回区間Qに対応するリンクの全部または一部(仮想リンク)に対して第1補正率を設定する。
【0038】
図2C,2Dは、図2A,2Bに示す既設経路Rに対応するリンクの全部および一部(仮想リンク)に設定される補正率を示すグラフである。図2C,2Dの縦軸は補正率を示し、横軸は既設経路Rにおける現在地点Pからの距離を示す。図2Cに示すように、一定距離dCの長さを有する第1迂回区間Qに対応するリンクの全部および一部(仮想リンク)のそれぞれに対して実線で示す第1補正率が設定される。図2Dに示すように、次走行予定道路Mに対応するリンクに第1迂回区間Qに対応する仮想リンク(図2Dにてmと示す)が含まれており、このようなリンクについては仮想リンクに対応する部分に対して第1補正率が設定される。本実施形態において、第1補正率は160とする。
【0039】
本実施形態において、経路探索における経路探索コストの総和が所定の制限桁数以上へと桁上がりを起こさない範囲で第1補正率(160)が大きく設定されている。制限桁数は、ナビゲーションプログラム100において経路探索コストの総和について定義されたデータの型に対応する桁数とされる。ここで、第1迂回区間Qの最大の長さは一定距離dCであるため、一定距離dCに第1補正率を乗じた値が、第1補正率に依存して経路探索コストの総和が増加する最大値に相当すると考えることができる。第1補正率を設定することなく実験的に行った複数回の経路探索における経路探索コストの総和の最大値を得ておき、制限桁数以上へと桁上がりを起こす経路探索コストの総和の値から当該最大値を減算したマージン幅が、一定距離dCに第1補正率を乗じた値と等しくなるように、一定距離dCと第1補正率とが設定されている。
【0040】
第2補正率設定部160は、指定区間Dのうち第1迂回区間Qを除く区間である第2迂回区間Wについての補正率を、第1補正率よりも小さく、かつ、経路探索コストを増大させる第2補正率に設定する機能を制御部11に実行させるモジュールである。すなわち、第2補正率設定部160の機能により制御部11は、指定区間Dのうち第1迂回区間Qと重複しない第2迂回区間Wについては経路探索コストの補正率として第2補正率を設定する。本実施形態において、制御部11は、第2迂回区間Wのうち分割指定区間D1〜D4に対応する区間ごとに異なる第2補正率を設定する。ここでは、対応する分割指定区間D1〜D4が既設経路R上における現在地点Pとの距離が短いほど、第2補正率を大きく設定する。第2補正率は、第1補正率よりも小さく、かつ、1よりも大きい。図2C,2Dに示すように、本実施形態では第2迂回区間Wのうち分割指定区間D1〜D4に対応するリンクの一部(仮想リンク)について一点鎖線で示す第2補正率をそれぞれ35,33,31,29と設定する。
【0041】
経路探索部170は、第1迂回区間Qと第2迂回区間Wとのそれぞれに対応するリンクについての経路探索コストをそれぞれ第1補正率と第2補正率とに基づいて補正し、経路探索コストの総和を最小化させるリンク群に対応する経路を既設経路の修正経路として探索する機能を制御部11に実行させるモジュールである。まず、経路探索部170の機能により制御部11は、補正率テーブル12cにおいて仮想リンクが設定されたリンクについて、リンク全体についての補正率を算出する。制御部11は、リンクのうち第1補正率または第2補正率が設定された仮想リンクを除く残りの部分に対応する仮想リンクを設定し、当該残りの部分に対応する仮想リンクについての補正率を1と設定する。例えば、図2Dの次走行予定道路Mにおいて、第1補正率(実線で示す)が設定された仮想リンク(mと示す)を除いた部分についても仮想リンクを設定し、当該仮想リンクについての補正率を1(二点鎖線で図示)と設定する。そして、制御部11は、仮想リンクの長さを、当該仮想リンクを含むリンク全体の長さで除算した占有割合を算出し、当該占有割合に仮想リンクに対して設定された補正率(第1補正率、第2補正率または1)に乗じることにより、寄与補正率を算出する。さらに、制御部11は、単一のリンクを構成する各仮想リンクについての寄与補正率の合計を当該リンクについての補正率とし、補正率テーブル12cに記録する。これにより、補正率テーブル12cにおいてリンクごとに補正率が記録されたこととなる。
【0042】
経路探索部170の機能により制御部11は、リンク(例えば、既設経路Rから所定の探索範囲内の区間に対応するリンク)のそれぞれについて補正前の経路探索コストを取得する。すなわち、制御部11は、リンクの長さに、例えばリンクに対応する道路の道幅や車線数や渋滞度や平均移動速度等に応じた調整率を乗じた経路探索コストを取得する。なお、経路探索コストは、予め地図情報12aに記録されていてもよいし、経路探索を行うごとに算出されてもよい。経路探索部170の機能により制御部11は、補正率テーブル12cにおいてリンクごとに記録された補正率を、リンクごとに取得された経路探索コストに乗算することにより、経路探索コストを補正する。これにより、既設経路Rにおいて第1補正率と第2補正率が設定されたリンク、および、第1補正率と第2補正率が設定された仮想リンクを含むリンクについての経路探索コストが補正される。経路探索部170の機能により制御部11は、ダイクストラ法やA*アルゴリズム、それらの改良型アルゴリズムなどにより、現在地点Pから目的地点Gまで接続するリンクの補正後の経路探索コストの総和を最小化させるリンク群に対応する経路を既設経路Rの修正経路として探索する。
【0043】
以上の構成において、既設経路R上において現在地点Pからユーザにより指定された指定距離dDだけ目的地点Gへと進んだ地点までの指定区間Dから第1迂回区間Qを除いた第2迂回区間Wに対応するリンクについては、第2補正率により経路探索コストが増大させられる。また、指定区間Dのうち第1迂回区間Qと重複する区間については第2補正率よりも大きい第1補正率により経路探索コストが増大させられる。従って、ユーザにより指定された指定距離dDを有する指定区間Dが修正経路の構成区間として採用される可能性を低減できる。すなわち、ユーザが指定した範囲について既設経路Rを迂回する修正経路が探索できる。
【0044】
さらに、既設経路R上において始点交差点Iを始点とする第1迂回区間Qは、既設経路R上において始点交差点Iの通過後に走行する予定の次走行予定道路Mと始点SQが共通する。すなわち、第1迂回区間Qと次走行予定道路Mとは少なくとも一部が重複する関係を有する。この関係は、指定距離dDがどのように指定されても維持される。従って、第1補正率設定部150の機能により、次走行予定道路Mと少なくとも一部が重複する第1迂回区間Qについて第1補正率を設定することにより、指定距離dDに拘わらず次走行予定道路Mに対応するリンクの経路探索コストを第1補正率により増大させることができる。従って、次走行予定道路Mに対応するリンクが修正経路の構成リンクとして採用される可能性を低減できる。なお、第1迂回区間Qと重複する次走行予定道路Mについて第2補正率よりも大きい第1補正率を設定することにより、次走行予定道路Mの長さが短い場合でも、次走行予定道路Mについての経路探索コストを大きく確保することができる。従って、図2A,2Cに示すように次走行予定道路Mの長さが短くても次走行予定道路Mが修正経路の構成区間として採用される可能性を低減できる。また、第1迂回区間Qと第2迂回区間Wの双方に第1補正率を設定せず、第2迂回区間Wについて第1補正率よりも小さい第2補正率を設定することにより、経路探索コストの総和が大きくなりすぎることの弊害が防止できる。
【0045】
次走行予定道路Mが修正経路の構成区間として採用される可能性が低減できるため、次走行予定道路Mの終点の交差点Hから始点交差点IへとUターンするような修正経路が探索されることも防止できる。例えば、現在地点Pを含む車線(区間)の反対車線(区間)を経由して目的地点Gへと向かう経路についての経路探索コストの総和が他の修正経路よりも小さくなり、現在地点Pから始点交差点Iへと進入する場合のUターンが禁止され、かつ、次走行予定道路Mの終点の交差点HでのUターンが禁止されていないこととする。この場合において第1迂回区間Q(次走行予定道路M)に第1補正率を設定しないとすると、図2Aにて二点鎖線で示すように、始点交差点Iから走行予定区間Mへと退出し、走行予定区間Mの終点の交差点HにてUターンして、始点交差点Iにて左折する経路が修正経路として探索され得る。しかし、本実施形態のように、次走行予定道路Mに対して第1補正率を設定すれば、次走行予定道路Mが修正経路の構成区間として採用される可能性が低減できるため、次走行予定道路Mの終点にてUターンする経路が修正経路として探索されることが防止できる。なお、第1迂回区間Qの反対車線に対応する区間にてついても経路探索コストを増大させる補正率を設定することにより、次走行予定道路Mの終点の交差点HにおいてUターンをする経路が修正経路して探索される可能性をより低減させてもよい。
【0046】
第1迂回区間設定部140により制御部11は、既設経路R上において始点交差点Iから目的地点Gへと一定距離dCだけ進んだ地点TCと、指定区間Dの終点TDとのうち、現在地点Pに近い方を第1迂回区間Qの終点TQと設定する。従って、指定区間Dの終点TDの方が始点交差点Iから目的地点Gへと一定距離dCだけ進んだ地点TCよりも現在地点Pに近くない限りにおいて、図2Aに示すように第1迂回区間Qの長さを一定距離dCだけ確保できる。これにより、一定距離dCを有する第1迂回区間Qについての補正後の経路探索コストを大きく確保することができ、第1迂回区間Qに対応するリンクが修正経路の構成区間として採用される可能性を低減できる。
【0047】
一方、図2Bに示すように指定区間Dの終点TDの方が始点交差点Iから目的地点Gへと一定距離dCだけ進んだ地点TCよりも現在地点Pに近い場合には、第1補正率が設定される第1迂回区間Qの終点TQを指定区間Dの終点TDと一致させることができる。既設経路R上において指定区間Dの終点TDよりも目的地点G側の区間については、ユーザが迂回を希望しない範囲あり、ユーザが迂回を希望しない範囲(指定距離dD以遠)の区間にまで第1補正率が適用されることが防止できる。すなわち、既設経路R上においてユーザが迂回を希望しない範囲の区間まで迂回させるような経路探索を行うことが防止できる。この場合、第1迂回区間Qの長さが一定距離dCよりも短くなることにより、図2Bに示すように第1迂回区間Qの長さが次走行予定道路Mよりも短くなり得るが、第1迂回区間Qについての第1補正率を第2補正率よりも大きくしておくことにより、次走行予定道路Mについての補正後の経路探索コストを十分に大きく確保することができる。
【0048】
第2補正率設定部160の機能により制御部11は、既設経路R上における現在地点Pからの距離が短くなるほど第2補正率を大きく設定する。これにより、第2迂回区間Wのうち現在地点Pに近い分割指定区間D1〜D4に対応する区間ほど、既設経路Rの構成区間として採用される可能性を低減できる。この場合、第2迂回区間Wのうち現在地点Pに遠い区間ほど第2補正率が小さくされるが、図2Bに示すように当該第2補正率が小さくされる分割指定区間D4が既設経路R上の始点交差点Iを含んでいたとしても、始点交差点Iを始点SQとする第1迂回区間Qについては第2補正率よりも大きい第1補正率が設定されるため、既設経路Rの次走行予定道路Mに対応するリンクを構成リンクとした修正経路が探索される可能性を低減できる。
【0049】
また、第1迂回区間設定部140により制御部11は、通過後に退出可能な退出道路が既設経路R上の区間以外に1個以上接続する既設経路R上の交差点のうち、現在地点Pから最初に到達する交差点である始点交差点Iを第1迂回区間の始点SQと設定する。すなわち、迂回し得ない第1迂回区間Qに第1補正率を設定しないことにより、経路探索コストが無駄に増大することが防止できる。
【0050】
(2)修正経路探索処理:
図3はナビゲーション装置10が実行する修正経路探索処理のフローチャートである。ステップS100において制御部11は、予め定められた一定距離dCとユーザにより指定された指定距離dDとを取得し、これらに基づいて指定区間Dと第1迂回区間Qと第2迂回区間Wとを設定する。さらに、ステップS100において制御部11は、指定区間DをN等分して、分割指定区間D1〜D4も設定しておく。
【0051】
ステップS200において、制御部11は、補正率テーブル作成処理を実行する。図4は、補正率テーブル作成処理のフローチャートである。ステップS205において、制御部11は、経路情報12bが示す出発地点から目的地点Gまでの経路に対応するリンクの1つを処理対象のリンクとして選択する。ステップS210において、制御部11は、処理対象のリンクが、経路情報12bが示す経路において出発地点から現在地点P以遠の道路に対応するリンク(現在地点Pを含む道路に対応するリンクも含む)であるか否かを判定する。処理対象のリンクが出発地点から現在地点P以遠の道路に対応するリンクでない場合、ステップS205に戻る。すなわち、ステップS205〜S210では、現在地点Pから目的地点Gまでの既設経路Rに対応するリンクのみを処理対象のリンクを抽出するループ処理が実行される。
【0052】
ステップS210にて処理対象のリンクが出発地点から現在地点P以遠の道路に対応するリンクであると判定された場合、制御部11はステップS215実行する。ステップS215において、制御部11は、処理対象のリンクに対応する道路の少なくとも一部が、第1迂回区間Qと第2迂回区間Wとの少なくとも一方と重複しているか否かを判定する。処理対象のリンクに対応する道路の少なくとも一部が、第1迂回区間Qと第2迂回区間Wとの少なくとも一方と重複していない場合、制御部11はステップS260に進み、経路情報12bが示す経路に対応するリンクのすべてを処理対象としたか否かを判定する。そして、経路情報12bが示す経路に対応するリンクのすべてを処理対象としていない場合、ステップS205に戻り次のリンクを処理対象とする。すなわち、処理対象のリンクに対応する道路の少なくとも一部が、第1迂回区間Qまたは第2迂回区間Wと重複していない場合、当該リンクについて第1補正率と第2補正率のいずれも設定する必要がないとして、次のリンクを処理対象とする。
【0053】
ステップS215にて処理対象のリンクに対応する道路の少なくとも一部が、第1迂回区間Qと第2迂回区間Wとの少なくとも一方と重複していると判定された場合、制御部11はステップS220を実行する。ステップS220において、制御部11は、処理対象のリンクに対応する道路の全体が第1迂回区間Qと重複するか否かを判定する。処理対象のリンクに対応する道路の全体が第1迂回区間Qと重複する場合、制御部11はステップS225において処理対象のリンクの全体について第1補正率を設定する。
【0054】
一方、ステップS220にて処理対象のリンクに対応する道路の全体が第1迂回区間Qと重複すると判定されなかった場合、制御部11はステップS230を実行する。ステップS230において制御部11は、処理対象のリンクに対応する道路の一部に第1迂回区間Qの少なくとも一部が重複するか否かを判定する。処理対象のリンクに対応する道路の一部に第1迂回区間Qの少なくとも一部が重複する場合、制御部11はステップS235を実行する。ステップS235において制御部11は、第1迂回区間Qが重複する一部に対応する仮想リンクを処理対象のリンクについて設定し、当該仮想リンクに対して第1補正率を設定する。
【0055】
ステップS235において仮想リンクに対して第1補正率を設定すると、制御部11はステップS240を実行する。ステップS240において制御部11は、処理対象のリンクに対応する道路の一部に第2迂回区間の少なくとも一部が重複しているか否かを判定する。処理対象のリンクに対応する道路の一部に第2迂回区間の少なくとも一部が重複している場合、制御部11はステップS245を実行する。ステップS245において制御部11は、第2迂回区間と重複する一部に対応する仮想リンクを処理対象のリンクにおいて設定し、当該仮想リンクに対して第2補正率を設定する。ステップS230,S240がともに肯定された場合、処理対象のリンクに対応する道路に第1迂回区間Qと重複する部分と第2迂回区間Wと重複する部分とが共存するため、これらの部分のそれぞれに対応する仮想リンクに対して第1補正率(S235)と第2補正率(S245)とを設定する。一方、ステップS230のみが肯定された場合、処理対象のリンクに対応する道路に第1迂回区間Qと重複する部分のみが存在するため、当該部分に対応する仮想リンクに対して第1補正率(S235)を設定する。
【0056】
なお、ステップS245において制御部11は、分割指定区間D1〜D4に応じた第2補正率を設定する。なお、第2補正率を設定する仮想リンクに対応する道路の部分が複数の分割指定区間D1〜D4と重複する場合、当該仮想リンクを分割指定区間D1〜D4ごとにさらに分割した仮想リンクを設定し、当該仮想リンクごとに分割指定区間D1〜D4に対応する第2補正率を設定する。以下、第2補正率を設定する場合には、同様の処理を行うこととする。
【0057】
ステップS230にて処理対象のリンクに対応する道路の一部に第1迂回区間Qの少なくとも一部が重複すると判定されなかった場合、制御部11はステップS250を実行する。ステップS250において制御部11は、処理対象のリンクに対応する道路全体が第2迂回区間Wと重複するか否かを判定する。処理対象のリンクに対応する道路全体が第2迂回区間Wと重複する場合、制御部11はステップS255を実行する。ステップS255において制御部11は、処理対象のリンクの全体に対して第2補正率を設定する。
【0058】
ステップS250にて処理対象のリンクに対応する道路全体が第2迂回区間Wと重複すると判定されなかった場合、制御部11はステップS245を実行する。ステップS250にて処理対象のリンクに対応する道路全体が第2迂回区間Wと重複すると判定されなかった場合、処理対象のリンクに対応する道路の一部が第2迂回区間Wのみと重複することとなる。従って、ステップS245において制御部11は、処理対象のリンクに対応する道路のうち第2迂回区間Wと重複する一部に対応する仮想リンクを設定し、当該仮想リンクに対して第2補正率を設定する。
【0059】
以上のように第1補正率と第2補正率とを設定する処理(ステップS225,S235,S245,S255)を実行すると、制御部11はステップS260に進み、経路情報12bが示す経路に対応するリンクのすべてを処理対象としたか否かを判定する。そして、経路情報12bが示す経路に対応するリンクのすべてを処理対象としていない場合、制御部11は、ステップS205に戻り次のリンクを処理対象とする。以上のループ処理を実行することにより、既設経路Rに対応するリンクについて第1補正率と第2補正率とを設定していくことができる。
【0060】
ステップS260にて経路情報12bが示す経路に対応するリンクのすべてを処理対象としたと判定した場合、ステップS265において制御部11は、補正率テーブル12cを作成する。すなわち、仮想リンクが設定されたリンクについて、リンク全体の補正率を算出して、リンクごとにリンク全体の補正率を記録した補正率テーブル12cを作成する。上述したように、仮想リンクの占有割合に応じた寄与補正率を合計することにより、リンク全体の補正率を算出する。
【0061】
以上のようにして補正率テーブル12cが作成できると、制御部11は、図3のステップS300にて経路探索を行う。すなわち、制御部11は、リンクのそれぞれについて補正前の経路探索コストを算出し、補正率テーブル12cにおいてリンクごとに記録された補正率を乗算することにより、当該経路探索コストを補正する。さらに、制御部11は、現在地点Pから目的地点Gまで接続するリンクの補正後の経路探索コストの総和が小さくなるように既設経路Rの修正経路を探索する。ステップS400において制御部11は、探索された修正経路を経路情報12bに記録し、修正経路を案内するための画像や音声をユーザI/F部44を介して出力させる。
【0062】
(3)他の実施形態:
ところで、経路案内の開始直後に右左折するように案内されることを防止するために、現在地点Pを始点とする直進優先区間については直進するように修正経路を探索するようにしてもよい。制御部11は、直進優先区間において、交差点を通過後において非直進方向に退出する退出道路に対応する退出リンクについての補正率である非直進補正率を、当該交差点を通過後において直進方向に退出する退出道路に対応する退出リンクについての補正率である直進補正率よりも大きく、かつ、第1補正率よりも小さく設定する。本実施形態において、制御部11は、直進優先区間における交差点を非直進方向に退出する退出道路に対応する退出リンクについての非直進補正率を10とし、当該交差点を直進方向に退出する退出道路に対応する退出リンクについての直進補正率を0.8とする。制御部11は、当該補正率を補正率テーブル12cに記録する。本実施形態では、退出方向が進入方向に対して30度よりも大きい退出道路を、非直進方向に退出する退出道路とする。一方、退出方向が進入方向に対して30度以下の退出道路を、直進方向に退出する退出道路とする。以上のようにして設定された補正率に応じて補正した経路探索コストを利用して、制御部11が修正経路を探索することにより、直進優先区間においては直進を優先するように修正経路を探索できる。すなわち、急な右左折を要する修正経路をユーザに案内することが防止できる。
【0063】
図5は、直進優先区間Fを説明する図である。図5の線や記号は図2A,2Bと同様の対象を示す。同図の例では、現在地点Pから直進方向へ所定距離だけ直進優先区間Fが設定されており、当該直進優先区間F内に始点交差点Iが存在する。また、太線で示す既設経路Rが設定されており、始点交差点Iの通過後に直進方向に退出する退出道路が既設経路R上の次走行予定道路Mとされている。このような場合においても、第1迂回区間設定部140により制御部11は、直進優先区間Fに存在する始点交差点Iを始点SQとする第1迂回区間Qを設定する。さらに、第1補正率設定部150の機能により制御部11は、直進優先区間F上の交差点I,Hから通過後に非直進方向(右左折方向)に退出する退出道路に対応する退出リンクのうち第1迂回区間Qと重複する部分については非直進補正率に優先させて第1補正率を設定する。同様に、第1補正率設定部150の機能により制御部11は、直進優先区間F上の交差点I,Hから通過後に直進方向に退出する退出道路に対応する退出リンクのうち第1迂回区間Qと重複する部分については直進補正率に優先させて第1補正率を設定する。すなわち、第1迂回区間Qについては始点交差点の通過後の退出方向に拘わらず第1補正率が設定される。図5の例では、次走行予定道路間Mの全体、および、交差点Hから直進方向へ退出する退出道路Kに対応する退出リンクのうち破線の丸で囲んだ部分について、直進補正率に優先させて第1補正率が設定される。この第1補正率は、図5の始点交差点Iから右左折方向へ退出する退出道路(一点鎖線)に対応する退出リンクに設定される非直進補正率よりも大きいため、図5の既設経路Rにおいて始点交差点Iの次に走行する予定の次走行予定道路Mが直進方向である場合でも、当該当該次走行予定道路Mを構成区間とした修正経路が探索される可能性を低減できる。なお、直進優先区間Fを設定された場合、既設経路Rと直進優先区間Fとが重複する区間の終点を指定区間Dの始点SDとしてもよい。
【0064】
既設経路情報取得部120の機能により制御部11は、現在地点Pから目的地点Gまでの既設経路Rを示す既設経路情報を取得すればよく、既設経路Rは、過去に探索された修正経路であってもよい。指定区間設定部130の機能により制御部11は、既設経路R上において現在地点Pから指定距離dDだけ目的地点Gへと進んだ指定区間Dを設定すればよく、指定距離dDはユーザから間接的に指定されてもよい。例えば既設経路R上においてユーザから指定された指定地点を取得し、現在地点Pから指定地点までの既設経路R上の距離を指定距離dDとしてもよい。この場合、指定区間Dの終点TDが指定地点となる。前記実施形態では、現在地点Pと始点交差点Iまでの距離よりも指定距離dDが大きくなるように制限したが、指定距離dDが現在地点Pと始点交差点Iまでの距離以下であってもよい。この場合でも、始点交差点Iを始点とする第1迂回区間Qについて第1補正率が設定されるため、次走行予定道路Mに対応するリンクが修正経路の構成リンクとして採用されることが防止できる。また、ナビゲーション装置10がユーザから指定距離の指定を受け付けるユーザインターフェイスを備えていなくてもよく、例えば他の装置において指定された指定距離を通信等により取得してもよい。
【0065】
第1迂回区間設定部140の機能により制御部11は、既設経路R上において始点交差点Iを始点とする第1迂回区間Qを設定すればよく、第1迂回区間Qは既設経路R上において所定数の交差点を含む区間であってもよい。前記実施形態において、経路探索コストの総和がプログラム上のデータの型の桁数によって定まる制限桁数以上へと桁上がりを起こさない範囲で第1補正率を大きく設定することとしたが。制限桁数は、例えば経路探索コストの総和を計算する演算装置が処理できる桁数の上限値や、当該総和を記録するレジスタが記録できる桁数の上限値によって定めてもよい。なお、基本的に、経路探索コストの総和は現在地点Pと目的地点Gとが遠いほど大きくなるため、現在地点Pと目的地点Gとが遠くなるほど第1補正率を下方修正するようにしてもよい。一方、第2補正率は、第1補正率より小さく1よりも大きければよく、例えば第1補正率に1未満の所定係数を乗算した値であってもよい。また、第1補正率が大きいほど次走行予定道路Mが迂回される可能性が高くなるため、次走行予定道路Mの迂回希望度をユーザから受け付け、当該迂回希望度に応じて第1補正率を設定してもよい。
【符号の説明】
【0066】
10…ナビゲーション装置、11…制御部、12…記録媒体、12a…地図情報、12b…経路情報、12c…補正率テーブル、12…記録媒体、41…GPS受信部、42…車速センサ、43…ジャイロセンサ、44…ユーザI/F部、100…ナビゲーションプログラム、110…ナビゲーション部、120…既設経路情報取得部、130…指定区間設定部、140…第1迂回区間設定部、150…第1補正率設定部、160…第2補正率設定部、170…経路探索部、C…車両、D…指定区間、dC…一定距離、dD…指定距離、F…直進優先区間、G…目的地点、I…始点交差点、M…次走行予定道路、P…現在地点、Q…第1迂回区間、W…第2迂回区間、R…既設経路。



【特許請求の範囲】
【請求項1】
現在地点から目的地点までの経路である既設経路を示す既設経路情報を取得する既設経路情報取得手段と、
前記既設経路上において現在地点からユーザにより指定された指定距離だけ前記目的地点側に進んだ地点までの区間を指定区間として設定する指定区間設定手段と、
前記既設経路上において前記現在地点から最初に到達する交差点である始点交差点を始点とする前記既設経路上の区間を第1迂回区間として設定する第1迂回区間設定手段と、
前記第1迂回区間についての経路探索コストを補正する補正率を、前記経路探索コストを増大させる第1補正率に設定する第1補正率設定手段と、
前記指定区間のうち前記第1迂回区間を除く区間である第2迂回区間についての前記経路探索コストを補正する補正率を、前記第1補正率よりも小さく、かつ、前記経路探索コストを増大させる第2補正率に設定する第2補正率設定手段と、
前記第1迂回区間と前記第2迂回区間とのそれぞれに対応するリンクについての前記経路探索コストをそれぞれ前記第1補正率と前記第2補正率とに基づいて補正し、前記経路探索コストの総和を最小化させるリンク群に対応する経路を前記既設経路の修正経路として探索する経路探索手段と、
を備える経路探索システム。
【請求項2】
前記指定区間設定手段は、前記始点交差点を含む前記指定区間を設定し、
前記第1迂回区間設定手段は、前記既設経路上において前記始点交差点から前記目的地点へと一定距離だけ進んだ地点と、前記指定区間の終点とのうち、前記既設経路上において前記現在地点に近い方を前記第1迂回区間の終点と設定する、
請求項1に記載の経路探索システム。
【請求項3】
前記第2補正率設定手段は、前記既設経路上における前記現在地点からの距離が短くなるほど前記第2補正率を大きく設定する、
請求項1または請求項2のいずれかに記載の経路探索システム。
【請求項4】
前記第1迂回区間設定手段は、通過後に退出可能な退出リンクが複数接続する前記既設経路上の交差点のうち、前記現在地点から最初に到達する交差点を前記始点交差点と設定する、
請求項1から請求項3のいずれか一項に記載の経路探索システム。
【請求項5】
前記現在地点を始点とする直進優先区間において、交差点を通過後において非直進方向に退出する退出リンクについての前記経路探索コストを補正する補正率である非直進補正率を、当該交差点を通過後において直進方向に退出する退出リンクについての前記経路探索コストを補正する補正率である直進補正率よりも大きく、かつ、前記第1補正率よりも小さく設定する直進優先手段を備え、
前記第1補正率設定手段は、前記直進優先区間上の交差点から通過後に非直進方向に退出する退出リンクのうち前記第1迂回区間と重複する部分については前記非直進補正率に優先させて前記第1補正率を設定し、前記直進優先区間上の交差点から通過後に直進方向に退出する退出リンクのうち前記第1迂回区間と重複する部分については前記直進補正率に優先させて前記第1補正率を設定する、
請求項1から請求項4のいずれか一項に記載の経路探索システム。
【請求項6】
現在地点から目的地点までの経路である既設経路を示す既設経路情報を取得する既設経路情報取得工程と、
前記既設経路上において現在地点からユーザにより指定された指定距離だけ前記目的地点側に進んだ地点までの区間を指定区間として設定する指定区間設定工程と、
前記既設経路上において前記現在地点から最初に到達する交差点である始点交差点を始点とする前記既設経路上の区間を第1迂回区間として設定する第1迂回区間設定工程と、
前記第1迂回区間についての経路探索コストを補正する補正率を、前記経路探索コストを増大させる第1補正率に設定する第1補正率設定工程と、
前記指定区間のうち前記第1迂回区間を除く区間である第2迂回区間についての前記経路探索コストを補正する補正率を、前記第1補正率よりも小さく、かつ、前記経路探索コストを増大させる第2補正率に設定する第2補正率設定工程と、
前記第1迂回区間と前記第2迂回区間とのそれぞれに対応するリンクについての前記経路探索コストをそれぞれ前記第1補正率と前記第2補正率とに基づいて補正し、前記経路探索コストの総和を最小化させるリンク群に対応する経路を前記既設経路の修正経路として探索する探索する経路探索工程と、
を含む経路探索方法。
【請求項7】
現在地点から目的地点までの経路である既設経路を示す既設経路情報を取得する既設経路情報取得機能と、
前記既設経路上において現在地点からユーザにより指定された指定距離だけ前記目的地点側に進んだ地点までの区間を指定区間として設定する指定区間設定機能と、
前記既設経路上において前記現在地点から最初に到達する交差点である始点交差点を始点とする前記既設経路上の区間を第1迂回区間として設定する第1迂回区間設定機能と、
前記第1迂回区間についての経路探索コストを補正する補正率を、前記経路探索コストを増大させる第1補正率に設定する第1補正率設定機能と、
前記指定区間のうち前記第1迂回区間を除く区間である第2迂回区間についての前記経路探索コストを補正する補正率を、前記第1補正率よりも小さく、かつ、前記経路探索コストを増大させる第2補正率に設定する第2補正率設定機能と、
前記第1迂回区間と前記第2迂回区間とのそれぞれに対応するリンクについての前記経路探索コストをそれぞれ前記第1補正率と前記第2補正率とに基づいて補正し、前記経路探索コストの総和を最小化させるリンク群に対応する経路を前記既設経路の修正経路として探索する探索する経路探索機能と、
をコンピュータに実行させる経路探索プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate


【公開番号】特開2013−19849(P2013−19849A)
【公開日】平成25年1月31日(2013.1.31)
【国際特許分類】
【出願番号】特願2011−155130(P2011−155130)
【出願日】平成23年7月13日(2011.7.13)
【出願人】(000100768)アイシン・エィ・ダブリュ株式会社 (3,717)
【Fターム(参考)】