説明

経路選出方法およびシステム並びに記録媒体

【課題】 使用者が走行した道路を適切に反映させた経路を選出することができる経路選出方法およびシステム並びに記録媒体を提供する。
【解決手段】 区間走行経路作成部6は、現在位置・走行軌跡検出部2が検出した車両の走行軌跡と最適経路探索部5が探索した最適経路とを入力し、これらを比較して異なる道路区間を区間走行経路として抽出する。区間走行経路記憶部7は、抽出した区間走行経路およびその属性情報を記憶する。交差区間調査部8は、誘導案内の際には、まず最適経路探索部5が探索した最適経路上の任意の2地点を区間とする区間走行経路が、区間走行経路記憶部7に存在するかを調査し、存在する場合には当該区間走行経路を区間走行経路記憶部7から抜き出す。案内用経路作成部9は、最適経路と抜き出した区間走行経路とを元に、最適経路上の該当する2地点区間を区間走行経路に置き換えて、誘導案内用経路を作成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、経路選出方法およびシステム並びに記録媒体に関し、より特定的には、カーナビゲーションシステム等に用いられる、地図上で指定された出発地と目的地との間の最適経路を自動的に選出する方法、および当該方法を用いたシステム、並びに当該方法を実行するためのプログラムを記録した媒体に関する。
【背景技術】
【0002】
近年、電子技術の発展に伴い、車両の誘導案内を行うためのナビゲーションシステムが急速に普及し始めている。このナビゲーションシステムの中には、使用者の利便性を向上させるため、出発地から目的地までの最適経路(例えば、最短距離到達経路または最小時間到達経路)を自動的に選出する経路選出システムを備えたものが存在する。
以下、従来の経路選出システムについて簡単に説明する。
【0003】
従来の経路選出システムにおいて、車両を誘導案内するための最適経路を求める方法としては、例えば特開昭59−105113号公報「車両の自動誘導方法」に開示されている方法(以下、第1の従来方法という)がある。この第1の従来方法は、道路のネットワークを表すデータから、最適経路決定手法の1つであるダイクストラ法等を用いて、出発地と目的地との間の最適経路を求めるものである。なお、ダイクストラ法の理論については、例えば非特許文献1に示されている。
【0004】
また、上記第1の従来方法に対して、使用者の走行経験を加味した最適経路を求める方法としては、例えば特許文献1の「経路探索機能を有する車載ナビゲーション装置」に開示されている方法(以下、第2の従来方法という)がある。この第2の従来方法では、使用者が走行した道路の評価値を走行頻度に応じて変更して記憶し、次に経路探索を行った場合には評価値が小さい道路を優先的に選出させるようにしている。
【0005】
さらに、使用者の別の好みを加味した最適経路を求める他の方法としては、例えば特許文献2の「ナビゲーション装置」に開示されている方法(以下、第3の従来方法という)がある。この第3の従来方法では、出発地から目的地への探索で求めた最適経路に対して、使用者が修正した道順を付与して記憶し、同じ出発地から目的地への経路を再度探索した場合には、使用者が修正した道順を反映した経路を最短経路として提示することが述べられている。
【非特許文献1】A.V.エイホ等著,大野訳の「データ構造とアルゴリズム」(株式会社培風館,1990年発行,179〜183頁)
【特許文献1】特開平8−201088号公報
【特許文献2】特開平11−64030号公報
【発明の開示】
【発明が解決しようとする課題】
【0006】
しかしながら、上記第2の従来方法のように、使用者が走行した道路の評価値を変更する場合では、評価値を変更した時の経路と異なる経路(出発地および/または目的地が異なる経路)を探索する時には、走行経験のある(評価値の小さい)道路を無理矢理使用した経路が選出されてしまうことがあった。
また、上記第3の従来方法のように、使用者が修正した道順を付与して記憶する場合では、使用者が修正した出発地から目的地への経路に対して、異なった目的地への経路を探索した時に、使用者が修正した道順が反映されない経路が選出されてしまうことがあった。
【0007】
それ故、本発明の目的は、使用者が走行した道路を適切に反映させた経路を選出することができる経路選出方法およびシステム並びに記録媒体を提供することである。
【課題を解決するための手段】
【0008】
第1の発明は、車両走行における地図上の最適な経路を選出する経路選出方法であって、経路の選出に必要な地図データを用いて、2地点間の最適経路を探索するステップと、車両が走行した走行軌跡を収集するステップと、探索した最適経路と収集した走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として記憶するステップと、使用者に対して経路の誘導案内を行う場合、探索した最適経路と記憶した全ての区間走行経路とを比較し、1つの区間走行経路毎に当該最適経路と交わる区間走行経路(交差区間走行経路)が存在するか否かを調査するステップと、調査した交差区間走行経路について、最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成するステップと、作成した誘導案内用経路を使って、使用者に経路の誘導案内を行うステップとを備える。
【0009】
第2の発明は、車両走行における地図上の最適な経路を選出する経路選出システムであって、経路の選出に必要な地図データを記憶する地図データ記憶手段と、車両の現在位置および走行軌跡を求める現在位置・走行軌跡検出手段と、使用者の指示に従って、特定情報として経路を求める目的地を入力する地点入力手段と、地図データと特定情報とを用いて、2地点間の最適経路を探索する最適経路探索手段と、最適経路探索手段が探索した最適経路と、現在位置・走行軌跡検出手段が求めた走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として抽出する区間走行経路作成手段と、区間走行経路を記憶する区間走行経路記憶手段と、使用者に対して経路の誘導案内を行う場合、最適経路探索手段が探索した最適経路と、区間走行経路記憶手段に記憶した全ての区間走行経路とを比較し、1つの区間走行経路毎に交差区間走行経路が存在するか否かを調査する交差区間調査手段と、交差区間調査手段が調査した交差区間走行経路について、最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成する案内用経路作成手段と、案内用経路作成手段が作成した誘導案内用経路を使って、使用者に経路の誘導案内を行う地図表示出力手段とを備える。
【0010】
第3の発明は、コンピュータ装置において実行されるプログラムを記録した記録媒体であって、経路の選出に必要な地図データを用いて、2地点間の最適経路を探索するステップと、車両が走行した走行軌跡を収集するステップと、探索した最適経路と収集した走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として記憶するステップと、使用者に対して経路の誘導案内を行う場合、探索した最適経路と記憶した全ての区間走行経路とを比較し、1つの区間走行経路毎に交差区間走行経路が存在するか否かを調査するステップと、調査した交差区間走行経路について、最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成するステップと、作成した誘導案内用経路を使って、使用者に経路の誘導案内を行うステップとを含む動作環境を、コンピュータ装置上で実現するプログラムを記録している。
【発明の効果】
【0011】
本発明によれば、車両が最適経路を外れて走行した区間のみの区間走行経路を記憶し、次回にこの区間を使用できる最適経路が探索された時には、この区間を記憶した区間走行経路に置き換えた経路で誘導案内を行うようにしている。これにより、現在状況に応じて使用者が以前に走行した道路を適切に反映した経路を求め、誘導案内を行うことができる。
【発明を実施するための最良の形態】
【0012】
図1は、本発明の一実施形態に係る経路選出システムの構成を示すブロック図である。図1において、本実施形態に係る経路選出システムは、地図データ記憶部1と、現在位置・走行軌跡検出部2と、走行軌跡入力部3と、地点入力部4と、最適経路探索部5と、区間走行経路作成部6と、区間走行経路記憶部7と、交差区間調査部8と、案内用経路作成部9と、地図表示部10と、出力部11と、簡易復帰経路選出部12とを備える。
以下、本発明の一実施形態に係る経路選出システムの各構成が行う動作を、まず説明する。
【0013】
地図データ記憶部1は、地図を表示して使用者に提示するために用いる地図表示用データ、および車両の現在位置を検出するためや出発地から目的地までの最適経路を選出するために用いる道路網データを記憶している。なお、典型的には、地図データ記憶部1は、CD−ROM等の記録媒体の形態で上記各データを有しており、内蔵する駆動機構(図示せず)によって記録媒体から必要なデータを読み出す。
現在位置・走行軌跡検出部2は、まず車両の速度や車両が転回した角度および衛星からの電波(GPSによる電波)を用いて、おおよその車両の現在位置および走行軌跡を求め、次に地図データ記憶部1に記憶されている道路網データを参照して、正確に車両の現在位置および走行軌跡を求める。
走行軌跡入力部3は、使用者の入力操作に応答して動作し、使用者の指示に従って走行軌跡を作成し、この作成した走行軌跡を区間走行経路作成部6へ出力する。従って、この走行軌跡入力部3は、使用者が車両を実際に走行させないで走行軌跡(すなわち、仮想走行軌跡)を作成する場合に必要となる構成である。
地点入力部4は、使用者の入力操作に応答して動作し、使用者の指示に従って経路を求める目的地(必要であれば、出発地や現在時間帯・曜日や出発/到着予定時間帯・曜日等)の情報を、最適経路探索部5に出力する。
最適経路探索部5は、地図データ記憶部1に記憶されている道路網データを用いて、出発地から目的地への最適経路を探索して選出する。なお、出発地の設定には、現在位置・走行軌跡検出部2により検出された車両の現在位置、または地点入力部4から入力される出発地の情報が用いられる。また、目的地の設定には、地点入力部4から入力される目的地の情報が用いられる。また、最適経路探索部5は、必要に応じて、地点入力部4から現在時間帯・曜日または使用者が出発(または到着)を予定している時間帯・曜日等の情報(属性情報)を入力する。
【0014】
区間走行経路作成部6は、現在位置・走行軌跡検出部2または走行軌跡入力部3から車両の走行軌跡を、最適経路探索部5から選出された最適経路を入力する。そして、区間走行経路作成部6は、この最適経路と走行軌跡とを比較して、走行軌跡上で最適経路と異なる道路区間(道路の始点および終点の2地点が、最適経路上に位置する道路区間)を区間走行経路として抽出する。こうして抽出された区間走行経路は、区間走行経路作成部6から区間走行経路記憶部7へ出力される。ここで、区間走行経路作成部6は、すでに区間走行経路記憶部7に記憶されている区間走行経路の内、2地点が走行軌跡上に位置する区間走行経路を判断し、経路が走行軌跡と同一である区間走行経路に関して使用回数を増加させ、異なる区間走行経路に関して使用回数を減少させる。そして、区間走行経路作成部6は、増減した使用回数(属性情報)を区間走行経路記憶部7へ出力する。
区間走行経路記憶部7は、区間走行経路作成部6から入力する区間走行経路および使用回数を、区間走行経路データとして記憶する。このとき、区間走行経路記憶部7は、走行した時の時間帯・曜日等の属性情報も併せて記憶する。
【0015】
交差区間調査部8は、最適経路探索部5から最適経路を入力する。そして、交差区間調査部8は、最適経路上の任意の2地点(経路の進行方向に従う)を区間とする区間走行経路が、区間走行経路記憶部7に存在するかどうかを調査する。該当する区間走行経路が存在する場合、交差区間調査部8は、区間走行経路記憶部7からその区間走行経路を取得して、最適経路と共に案内用経路作成部9へ出力する。なお、最適経路上の任意の2地点を区間とする区間走行経路とは、始点および終点の双方が最適経路上に位置している道路だけではなく、道路の途中で最適経路と交差する道路であってもよい。
案内用経路作成部9は、交差区間調査部8から入力する最適経路と区間走行経路(全体または一部分)とを元に、最適経路上の該当する2地点区間を区間走行経路に置き換えて、誘導案内用経路を作成する。そして、案内用経路作成部9は、作成した誘導案内用経路を地図表示部10へ出力する。
【0016】
地図表示部10は、地図データ記憶部1に記憶された地図表示用データを参照することにより、現在位置・走行軌跡検出部2で求めた車両の現在位置とその付近の地図、または使用者が希望した範囲の地図を表示するための画像データを生成する。また、地図表示部10は、表示する地図の範囲内に、案内用経路作成部9で作成した誘導案内用経路(または、後述する簡易復帰経路選出部12で作成した新たな誘導案内用経路)が含まれる場合には、併せて誘導案内用経路の画像データを生成する。さらに、地図表示部10は、車両の現在位置と誘導案内用経路とに基づいて、車両を誘導案内するためのガイダンス情報(例えば、「100m先の交差点で右折して下さい」といった音声情報および/または表示情報)を出力する。なお、このガイダンス情報は、本発明の主眼ではないため、ここでの説明を省略する。
【0017】
出力部11は、ディスプレイやスピーカ等を含み、地図表示部10から与えられる画像データやガイダンス情報等を、画面表示および音声により出力する。
簡易復帰経路選出部12は、誘導案内中に車両が誘導案内用経路から離脱した場合に、地図表示部10から車両の現在位置と誘導案内用経路とを入力し、車両の現在位置と誘導案内用経路上の任意地点との2地点を区間とする区間走行経路が、区間走行経路記憶部7に存在するかどうかを調査する。そして、該当する区間走行経路が存在する場合、簡易復帰経路選出部12は、区間走行経路記憶部7からその区間走行経路を取得し、誘導案内用経路上の該当する2地点区間を取得した区間走行経路に置き換えた新たな誘導案内用経路を作成する。そして、簡易復帰経路選出部12は、作成した新たな誘導案内用経路を誘導案内用経路として、地図表示部10へ出力する。なお、該当する区間走行経路が存在しない場合は、簡易復帰経路選出部12(または最適経路探索部5)において、従来の技術に基づいた最適経路へ復帰する経路が探索される。
【0018】
次に、図2を参照して、図1の区間走行経路作成部6が行う動作について、具体例を挙げて詳細に説明する。
図2は、区間走行経路作成部6が行う区間走行経路の作成および属性情報の変換の一例を示す図である。図2(a)は、現在位置・走行軌跡検出部2(または走行軌跡入力部3)から入力した車両の走行軌跡と、最適経路探索部5で探索された最適経路とを表している。区間走行経路作成部6は、図2(a)に示す走行軌跡(破線で示す)と最適経路(実線で示す)とを比較して異なる道路区間を調べ、図2(b)のように異なる道路区間の始点から終点までの走行軌跡を、区間走行経路Aとして抽出する。同時に、区間走行経路作成部6は、車両が走行した時の時間帯(この例では7〜9時)および曜日(この例では金曜日)を調査する。さらに、区間走行経路作成部6は、この区間走行経路Aの属性情報である走行回数を「1回」に設定する。なお、区間走行経路Aが区間走行経路記憶部7にすでに記憶されている場合には、区間走行経路作成部6は、現在記憶されている走行回数を1つ増加させる。そして、区間走行経路作成部6は、こうして求めた区間走行経路Aを、その属性情報と共に区間走行経路記憶部7へ出力する。
一方、図2(c)に示すように、区間走行経路Aが区間走行経路記憶部7にすでに存在している場合において、最適経路の通りに走行した時には(最適経路=走行軌跡)、区間走行経路作成部6は、その区間走行経路Aの属性情報である走行回数を1つ減少させる。ここで、走行回数が「0回」になった区間走行経路については、区間走行経路記憶部7から消去するようにしてもよい。
【0019】
なお、図2(d)のように、最適経路の出発地と異なる場所から走行を開始した場合には、区間走行経路作成部6は、その走行開始地点から最適経路へ合流する地点までの道路区間を、区間走行経路Bとして抽出する。また、図2(e)のように、最適経路の目的地と異なる場所で走行を終了した場合には、区間走行経路作成部6は、最適経路から離脱した地点から走行終了地点までの道路区間を、区間走行経路Cとして抽出する。
【0020】
次に、図3を参照して、図1の区間走行経路記憶部7に記憶されている内容について、具体例を挙げて詳細に説明する。
図3は、区間走行経路記憶部7に記憶されている区間走行経路データの一例を示す図である。図3(a)は、道路網データとある区間走行経路とを表した図である。道路網データは、交差点と交差点間を結ぶ道路(リンク)とからなり、リンクにはそれぞれ固有の番号が付けられている。区間走行経路は、このリンク番号の列で表現され、図3(a)で示した区間走行経路は、「L53→L22→L62→L33」の順にリンクを通過する経路として記憶される。図3(b)は、区間走行経路記憶部7に区間走行経路データとして記憶している内容の一例を示しており、上述のリンク番号の列で表現された区間走行経路に対応して、それぞれ走行回数,走行した曜日,走行した時間帯が併せて記憶されている。
なお、区間走行経路記憶部7における区間走行経路の記憶をリンク番号の列で表現したが、例えば、通過する交差点を表すデータの列(ノード番号の列)等、経路がわかる形態であれば他のデータ形式による記憶方法であっても構わない。また、区間走行経路に対応する属性情報として、時間帯や曜日等の区別を記憶しているが、平日/休日での区別や、朝/昼/夜/深夜での区別や、集金日(ごと日)/それ以外の日での区別等、道路状況が変わることが想定される他の区別を記憶するようにしても構わない。
【0021】
次に、図4を参照して、図1の交差区間調査部8および案内用経路作成部9が行う動作について、具体例を挙げて詳細に説明する。
図4は、最適経路探索部5で探索された最適経路に対して、交差する区間走行経路を調査し、その調査結果に基づいて誘導案内用経路を作成するまでの手順の一例を説明する図である。図4(a)は、区間走行経路記憶部7に記憶されている区間走行経路データの区間走行経路D,Eを、地図平面上の位置で表したイメージ図である。図4(b)は、図4(a)に最適経路探索部5で求めた出発地から目的地までの最適経路を重ねて表示したイメージ図である。
このような位置関係(図4(b))において、交差区間調査部8は、まず、区間走行経路Dが最適経路と交差しているかどうかを調査する。この例では、区間走行経路Dと最適経路とは交差していないため、交差区間調査部8は、区間走行経路Dを処理対象としない。次に、交差区間調査部8は、区間走行経路Eが最適経路と交差しているかどうかを調査する。この例では、区間走行経路Eの始点および終点が最適経路と交差しているので、交差区間調査部8は、区間走行経路Eを処理対象として、区間走行経路Eから最適経路と交差している2地点区間の経路(交差区間の走行経路)を抜き出す。なお、この例では、区間走行経路Eの始点および終点の双方が最適経路上に位置しているので、区間走行経路Eがそのまま交差区間の走行経路として抜き出される。こうして抜き出された交差区間の走行経路と最適経路とは、案内用経路作成部9へ出力される。
そして、案内用経路作成部9は、図4(c)に示すように、最適経路の交差区間部分を削除し、代わりに抜き出した交差区間の走行経路を挿入した経路を作成し、これを誘導案内用経路として地図表示部10に出力する。
【0022】
次に、図5を参照して、図1の案内用経路作成部9において、区間走行経路データが誘導案内用経路に反映される最適経路と区間走行経路のパターンの一例を説明する。図5は、区間走行経路データに基づいて誘導案内用経路を作成するパターンを説明する図である。
まず、区間走行経路Fの始点と終点とが、共に最適経路と交差している場合である(図5(a))。この場合、区間走行経路Fの始点から終点までの経路を交差区間の走行経路として抜き出す、そして、対応する最適経路上の区間部分を、抜き出した交差区間の走行経路と置換して、誘導案内用経路を作成する。
次に、区間走行経路Fの途中で、最適経路と交差する地点が2つ存在する場合である(図5(b))。この場合、区間走行経路Fの内の交差した2地点間の経路のみを交差区間の走行経路として抜き出す。そして、対応する最適経路上の区間部分を、抜き出した交差区間の走行経路と置換して、誘導案内用経路を作成する。
【0023】
さらに、区間走行経路と最適経路とが1つの地点でしか交差していない場合である。この場合には、次の3つの状態に分けることができる。
まず、出発地と離れた所から最適経路が開始していて、かつその開始地点よりも区間走行経路Gの方が出発地に近い場合である(図5(c1))。この場合、出発地に一番近い区間走行経路G上の一方の地点(交差地点と仮定)と、区間走行経路Gが最適経路と交差する他方の地点との間の経路を、交差区間の走行経路として抜き出す。そして、最適経路上における他方の地点以前の部分を、抜き出した交差区間の走行経路と置換して、誘導案内用経路を作成する。
次に、目的地と離れた所で最適経路が終了していて、かつ、その終了地点よりも区間走行経路Hの方が目的地に近い場合である(図5(c2))。この場合、区間走行経路Hが最適経路と交差する一方の地点と、目的地に一番近い区間走行経路H上の他方の地点(交差地点と仮定)との間の経路を、交差区間の走行経路として抜き出す。そして、最適経路上における一方の地点以降の部分を、抜き出した交差区間の走行経路と置換して、誘導案内用経路を作成する。
次に、出発地や目的地とは離れた位置において、1つの地点でしか交差していない場合である(図5(c3))。この場合、区間走行経路Iが最適経路と交差する地点が2つ存在しないため、この区間走行経路Iは、誘導案内用経路の作成における処理対象とはならない。
なお、当然のごとく、最適経路と交差する地点が1つもない区間走行経路が、誘導案内用経路の作成における処理対象となることはない。
【0024】
次に、図6を参照して、図1の案内用経路作成部9において、区間走行経路データが誘導案内用経路に反映される条件の一例を説明する。
図6(a)は、区間走行経路Jの誘導案内用経路への反映を、走行回数による条件に基づいて行う場合を説明する図である。このような条件付けは、誘導案内用経路を作成する際に、突発的に走行した区間走行経路(例えば、道路工事により迂回させられた場合等)を除外して、利用頻度の高い区間走行経路だけを考慮できるようにしたものである。この条件付けとしては、例えば、案内用経路作成部9において、走行回数が「2回」以上の区間走行経路についてのみ、最適経路との置き換えを行うように設定しておく。
【0025】
このような設定条件において、まず、初めて走った経路の場合、まだその経路に関する区間走行経路は、区間走行経路記憶部7に記憶されていない。この場合には、最適経路探索部5が求めた最適経路が誘導案内用経路として使用者に提示される。ここで、使用者が誘導案内用経路(最適経路)とは違う道路を走行した場合には、その走行軌跡から新たな区間走行経路Jが作成され、その走行回数が「1回」として区間走行経路記憶部7に記憶される。
次に、再び同じ地点間の経路を探索した場合、最適経路は前回と同じ経路であり、また前回記憶した当該最適経路と交差している区間走行経路Jが存在する。そのため、交差区間調査部8は、最適経路と共にこの区間走行経路Jを抜き出して案内用経路作成部9へ出力する。この場合には、この区間走行経路Jの走行回数はまだ「1回」であるため、上記条件に制限されて、今回(2回目)の走行前の誘導案内用経路としては、前回初めて(1回目)走行した時の誘導案内用経路と同じ経路が出力されることとなる。ここで、2回目も1回目の走行軌跡と同じ道路を走行した場合、すでに記憶している区間走行経路Jの走行回数が1つ増加して「2回」となる。
そして、その後、さらに再び同じ地点間の経路を探索した場合には、1回目および2回目の走行前と同じ最適経路が求められるが、案内用経路作成部9へ出力される区間走行経路Jの走行回数が「2回」になっているため、誘導案内用経路としては、この区間走行経路Jへの置き換えを行った経路が設定される。よって、3回目の走行前には、1回目および2回目で実際に走行した経路(走行軌跡)と同じ経路によって、誘導案内を行うことができる。
【0026】
図6(b)は、区間走行経路Jの誘導案内用経路への反映を、時間帯・曜日による条件に基づいて行う場合を説明する図である。このような条件付けは、誘導案内用経路を作成する際に、時間的な要因で変化する交通事情(例えば、平日は通勤の車両で渋滞するが、休日は渋滞しないような場合等)を考慮できるようにしたものである。この条件付けとしては、例えば、属性情報の時間帯を3時間単位(1〜3時,4〜6時,7〜9時,10〜12時,13〜15時,16〜18時,19〜21時,22〜24時)で区分し、また、属性情報の曜日を、月曜日から金曜日までの平日と、土曜日・日曜日・祝祭日の休日とに区分して、区間走行経路記憶部7に記憶しておく。
【0027】
上述した例に基づくと、金曜日の8時に走行した時に作成された区間走行経路Kは、「7〜9時,平日」に分類される。この状態でこの区間走行経路Kを使用すべき最適経路が求められた場合、例えば、探索を行った曜日・時間が月曜日の8時であれば、この区間走行経路Kを反映した誘導案内用経路が作成される。しかし、月曜日の20時や、土曜日の8時に探索を行った時には、区間走行経路Kの属性情報(時間帯・曜日)の条件に一致しないので、区間走行経路Kが反映しない誘導案内用経路が作成される。
なお、ここでは一例として時間帯や曜日に基づいた区分を説明したが、使用者の好みによる区分であっても構わない。例えば、末尾に「8」の付く日(8日,18日,28日)のみに、区間走行経路を反映させるような条件を設定したり、使用者が自由に設定できるような入力装置を設けて区分を決めたりしてもよい。
【0028】
次に、図7を参照して、図1の簡易復帰経路選出部12が行う動作について、具体例を挙げて詳細に説明する。
図7(a)は、出発地から目的地までの経路を求めたときに、案内用経路作成部9で作成された誘導案内用経路に従って車両が走行している状態を示す。図7(b)は、使用者の意思によって、車両が誘導案内用経路から離脱した状態を示す。このとき、地図表示部10は、誘導案内用経路から車両が離脱したことを感知し、簡易復帰経路選出部12に対して、離脱前の誘導案内用経路と車両の現在位置とを出力する。これに対し、簡易復帰経路選出部12は、地図表示部10から与えられる車両の現在位置と誘導案内用経路とから、現在位置が存在し、かつ誘導案内用経路との交差地点を持つ区間走行経路を、区間走行経路記憶部7において調査する。ここで、対応する区間走行経路Lが存在する場合、簡易復帰経路選出部12は、区間走行経路記憶部7から区間走行経路Lを取得する(図7(c))。そして、簡易復帰経路選出部12は、取得した区間走行経路Lの現在位置地点から誘導案内用経路と交差している地点までを交差区間の走行経路として抜き出し、この交差区間の走行経路を誘導案内用経路と接続して、新たに現在位置から目的地へ至る誘導案内用経路を作成し(図7(d))、地図表示部10へ出力する。
【0029】
次に、図8〜図12を参照して、本発明の一実施形態に係る経路選出システムが行う経路選出動作を説明する。
図8は、本発明の一実施形態に係る経路選出システムが行う経路選出動作の一例を示すフローチャートである。図9〜図12は、それぞれ図8のサブルーチンステップS104〜S107のさらに詳細な動作の一例を示すフローチャートである。なお、ここでは、一例として、車両の現在位置から使用者が入力した目的地までを走行した場合の動作を説明する。また、説明をより明確にするために、区間走行経路データの属性情報に関しては、日時・曜日などの判断は行わず、走行回数のみを判断するようにしている。
【0030】
まず、図8を参照して、最適経路探索部5は、使用者の入力操作に応答して、地点入力部4から目的地の位置座標(経度,緯度)を入力する(ステップS101)。また、最適経路探索部5は、必要に応じて出発する日時も入力する。次に、最適経路探索部5は、現在位置・走行軌跡検出部2から車両の現在位置の座標(経度,緯度)や車両の進行方向を入力して、出発地を設定する(ステップS102)。そして、最適経路探索部5は、地図データ記憶部1に記憶されている道路網データ(場合によっては、さらに交通情報など)を使用して、出発地から目的地までの最適経路を探索して選出する(ステップS103)。このステップS103の経路探索処理は、従来から知られているダイクストラ法等の最短経路探索方法を用いて実行される。
次に、交差区間調査部8および案内用経路作成部9は、使用者を現在位置から目的地へ誘導案内するための誘導案内用経路を求めるため、案内用経路作成処理を実行する(ステップS104)。このステップS104における詳細な動作を、図9に示す。
【0031】
図9を参照して、案内用経路作成処理(図8,ステップS104)の動作を説明する。
案内用経路作成処理が開始されると、まず、交差区間調査部8は、調査によって求まる最適経路と交差する区間走行経路(以下、該当区間走行経路という)を記憶しておく領域を、初期化する(ステップS201)。次に、交差区間調査部8は、区間走行経路記憶部7に記憶されている区間走行経路データの全ての区間走行経路を調査したかどうかを判断する(ステップS202)。なお、現時点では上記ステップS201における初期化直後の未調査段階であるため、そのままステップS203へ進む。そして、交差区間調査部8は、区間走行経路データから未調査の区間走行経路の1つを調査対象として選出する(ステップS203)。
次に、交差区間調査部8は、上記ステップS203で選出した区間走行経路と上記ステップS103で求めた最適経路とを使用し、最適経路上を出発地から目的地方向へ辿って、選出した区間走行経路と交わる地点があるかどうかを調査する(ステップS204)。このステップS204の調査の結果、交わる地点がない場合は、上記ステップS202へ戻り、別の未調査の区間走行経路を調査する。一方、上記ステップS204の調査の結果、交わる地点がある場合は、当該交わる地点を交差地点Mとして記憶する(ステップS205)。
【0032】
上記ステップS205で交差地点Mを求めた後、交差区間調査部8は、最適経路上を交差地点Mから目的地方向へ辿って、再び区間走行経路と交わる地点があるかどうかを調査する(ステップS206)。このステップS206の調査の結果、再び交わる地点がある場合、交差区間調査部8は、当該再び交わる地点を交差地点Nとして記憶する(ステップS207)。一方、上記ステップS206の調査の結果、再び交わる地点がない場合、交差区間調査部8は、選出した区間走行経路上で、交差地点Mから車両が走行した軌跡方向に対して現在の目的地に一番近い地点(以下、目的最近傍地点という)をさらに捜索し、当該目的最近傍地点が最適経路上の最後の地点(経路の終点)よりも目的地に近いかどうかを調べる(ステップS208)。
【0033】
上記ステップS208において目的最近傍地点の方が目的地に近い場合、交差区間調査部8は、この目的最近傍地点を交差地点Nとして記憶する(ステップS207)。一方、上記ステップS208において目的最近傍地点の方が目的地から遠い場合、交差区間調査部8は、選出した区間走行経路の交差地点Mから車両が走行した軌跡方向の逆方向に対して出発地に一番近い地点(以下、出発最近傍地点という)をさらに捜索し、最適経路上の最初の地点(経路の始点)よりも出発地に近いかどうかを調べる(ステップS209)。このステップS209において出発最近傍地点の方が最初の地点に近い場合、交差区間調査部8は、先に記憶していた交差地点Mを交差地点Nとして記憶し直し、当該出発最近傍地点を新たな交差地点Mとして記憶する(ステップS210)。一方、上記ステップS209において出発最近傍地点の方が最初の地点より遠い場合、交差区間調査部8は、選出した区間走行経路が該当区間走行経路ではなかったと判断し、上記ステップS202へ戻って別の未調査の区間走行経路を調査する。
【0034】
次に、交差区間調査部8は、上記ステップS207またはS210を行った後、求めた交差地点Mから交差地点Nまでの経路を区間走行経路記憶部7から抜き出して、該当区間走行経路として記憶する(ステップS211)。なお、すでに他の該当区間走行経路が記憶されていてもその内容は削除(上書き)せずに、新たに抜き出した区間走行経路も追加する形で記憶しておく。そして、交差区間調査部8は、該当区間走行経路の記憶が終わると、上記ステップS202に戻って別の未調査の区間走行経路を調査する。
【0035】
上記ステップS202〜S211を繰り返して、交差区間調査部8における区間走行経路記憶部7に記憶された区間走行経路データの全ての区間走行経路の調査が終わると、次に、案内用経路作成部9は、上記ステップS103で求めた最適経路および記憶した該当区間走行経路のデータを取得する(ステップS212)。なお、このとき上記ステップS103で求めた最適経路は、交差区間調査部8にそのまま残しておく。次に、案内用経路作成部9は、最適経路上の該当区間走行経路の交差地点M〜交差地点N間に対応する部分を、その該当区間走行経路に置き換える(ステップS213)。
こうして、案内用経路作成部9によって該当区間走行経路を最適経路に反映した誘導案内用経路が作成され、ステップS104における案内用経路作成処理が終了して、図8に示すメインルーチンへ戻る。
【0036】
再び図8を参照して、案内用経路作成処理(ステップS104)が終了した後、地図表示部10、出力部11および簡易復帰経路選出部12は、使用者に誘導案内用経路を使用して案内情報を提供するため、走行状態処理を実行する(ステップS105)。このステップS105における詳細な動作を、図10に示す。
【0037】
図10を参照して、走行状態処理(図8,ステップS105)の動作を説明する。
走行状態処理が開始されると、地図表示部10は、上記ステップS104で求めた誘導案内用経路を、使用者へ提供する案内経路に設定する(ステップS301)。そして、地図表示部10は、現在位置・走行軌跡検出部2から車両の現在位置を入力する(ステップS302)。次に、地図表示部10は、入力した現在位置と案内経路とを比較して、車両が目的地へ到着したかどうかを調査する(ステップS303)。
上記ステップS303の調査の結果、車両が目的地へ到着していれば、このステップS105における走行状態処理を終了して、図8に示すメインルーチンへ戻る。一方、上記ステップS303の調査の結果、車両が目的地へ到着していなければ、地図表示部10は、さらに車両の現在位置が案内経路上にあるかどうかを判断する(ステップS304)。
【0038】
上記ステップS304において、車両の現在位置が案内経路上にあると判断した場合、地図表示部10は、車両の現在位置を元に案内経路に従った、例えば「300m先交差点を右折」などの誘導案内情報を作成して、出力部11を用いて使用者へ提示する(ステップS305)。そして、現在位置に関する誘導案内情報の提示が終了すると、再び上記ステップS302に戻り、車両が移動した次の現在位置を調査する。
こうして、現在位置が案内経路上を走行して目的地へ到着するまでの間は、上記ステップS302〜S305が繰り返される。
【0039】
しかし、上記ステップS304において、地図表示部10が車両の現在位置が案内経路上から外れたと判断した場合には、簡易復帰経路選出部12が、現在位置から案内経路上の地点までの間に該当する区間走行経路が区間走行経路記憶部7に存在するかどうかを調査する(ステップS306)。このステップS306の調査の結果、該当する区間走行経路が存在する場合、簡易復帰経路選出部12は、この該当する区間走行経路を現在位置から案内経路へ戻るまでの復帰経路として、区間走行経路記憶部7から抜き出す(ステップS307)。一方、上記ステップS306の調査の結果、該当する区間走行経路が存在しない場合、簡易復帰経路選出部12は、現在位置から案内経路へ戻るまでの復帰経路を、地図データ記憶部1からデータを読み出して最適経路を再び探索することによって求める(ステップS309)。
そして、簡易復帰経路選出部12は、上記ステップS307またはS309で求めた復帰経路を案内経路に接続した、現在地点から目的地へ至る新たな案内経路を作成する(ステップS308)。そして、この新たな案内経路の作成が完了すると、上記ステップS302へ戻って車両が移動した次の現在位置を調査する。
【0040】
再び図8を参照して、走行状態処理(ステップS105)が終了した後、区間走行経路作成部6は、区間走行経路追加処理(ステップS106)を行う。このステップS106における詳細な動作を、図11に示す。
【0041】
図11を参照して、区間走行経路追加処理(図8,ステップS106)の動作を説明する。
区間走行経路追加処理が開始されると、区間走行経路作成部6は、現在位置・走行軌跡検出部2または走行軌跡入力部3から、出発地から目的地へ到着するまで車両が走行した走行軌跡を入力すると共に、最適経路探索部5によって上記ステップS103で求められた最適経路を入力する(ステップS401)。そして、区間走行経路作成部6は、入力した走行軌跡と最適経路とを比較し、まず、出発地が異なっているかどうかを判断する(ステップS402)。このステップS402において異なっていないと判断した場合、そのままステップS407へ進む。一方、上記ステップS402において異なっていると判断した場合、区間走行経路作成部6は、走行軌跡について出発地から最適経路へ出るまでに走行した区間の軌跡を抜き出す(ステップS403)。そして、区間走行経路作成部6は、抜き出した走行軌跡が区間走行経路記憶部7に区間走行経路としてすでに記憶されているかどうかを調査する(ステップS404)。このステップS404において、すでに記憶されていれば、該当する区間走行経路の走行回数を1つ増加させ(ステップS405)、記憶されていなければ、上記ステップS403で抜き出した走行軌跡を新たな区間走行経路(走行回数は1回)として区間走行経路記憶部7へ記憶(ステップS406)した後、ステップS407へ進む。
【0042】
上記ステップS402において異なっていないと判断した場合、あるいは上記ステップS405またはS406の処理が終わると、区間走行経路作成部6は、目的地へ至るまでの走行軌跡と最適経路とが次に離れる地点をさらに調査する(ステップS407)。
上記ステップS407の調査の結果、目的地へ到着するまで走行軌跡と最適経路とが同じであれば、区間走行経路作成部6は、このステップS106における区間走行経路追加処理を終了して、図8に示すメインルーチンへ戻る。一方、上記ステップS407の調査の結果、走行軌跡と最適経路とが離れる地点(離脱地点)があれば、区間走行経路作成部6は、その離脱地点から後で、再び走行軌跡と最適経路とが合流する地点(合流地点)をさらに調査する(ステップS408)。そして、区間走行経路作成部6は、このステップS408の調査の結果、合流地点が見つかれば、離脱地点から合流地点までの区間の走行軌跡を抜き出し(ステップS409)、合流地点が見つからなければ、離脱地点から目的地までの区間の走行軌跡を抜き出す(ステップS410)。
次に、区間走行経路作成部6は、上記ステップS409またはS410において抜き出した走行軌跡が、区間走行経路記憶部7にすでに区間走行経路として記憶されているかどうかを調査する(ステップS411)。このステップS411の調査の結果、すでに記憶されていれば、該当する区間走行経路の走行回数を1つ増加させ(ステップS412)、記憶されていなければ、抜き出した走行軌跡を新たな区間走行経路(走行回数は1回)として区間走行経路記憶部7へ記憶(ステップS413)した後、上記ステップS407へ戻る。
【0043】
再び図8を参照して、区間走行経路追加処理(ステップS106)が終了した後、区間走行経路作成部6は、区間走行経路削除処理(ステップS107)を行う。このステップS107における詳細な動作を、図12に示す。
【0044】
図12を参照して、区間走行経路削除処理(図8,ステップS107)の動作を説明する。
区間走行経路削除処理が開始されると、区間走行経路作成部6は、現在位置・走行軌跡検出部2(または必要に応じて走行軌跡入力部3)から、出発地から目的地へ到着するまでの車両が走行した走行軌跡を入力する(ステップS501)。次に、区間走行経路作成部6は、区間走行経路記憶部7に記憶されている区間走行経路データの全ての区間走行経路を調査したかどうかを判断する(ステップS502)。なお、現時点では上記ステップS501後の未調査段階であるため、そのままステップS503へ進む。そして、区間走行経路作成部6は、区間走行経路データから未調査の区間走行経路の1つを調査対象として選出する(ステップS503)。
次に、区間走行経路作成部6は、選出した区間走行経路について、走行経路の始点と終点とが両方とも上記ステップS501で入力した走行軌跡上に存在するかどうかを調査する(ステップS504)。このステップS504の調査の結果、始点および終点が走行軌跡上に存在しなければ、区間走行経路作成部6は、選出した区間走行経路を調査済みとして上記ステップS502へ戻り、別の未調査の区間走行経路を調査する。一方、上記ステップS504の調査の結果、始点および終点が走行軌跡上に存在すれば、区間走行経路作成部6は、始点と終点の区間の走行経路が、上記ステップS501で入力した走行軌跡と異なるかどうかをさらに調査する(ステップS505)。
【0045】
上記ステップS505の調査の結果、同じであれば、区間走行経路作成部6は、選出した区間走行経路を調査済みとして上記ステップS502へ戻り、別の未調査の区間走行経路を調査する。一方、上記ステップS505の調査の結果、異なっていれば、区間走行経路作成部6は、選出した区間走行経路の走行回数が1回かどうかを調査する(ステップS506)。このステップS506の調査の結果、走行回数が1回であれば、区間走行経路作成部6は、選出している区間走行経路のデータを区間走行経路記憶部7から削除した後に、走行回数が2回以上であれば、走行回数を1つ減少させて区間走行経路記憶部7へ記憶し、選出した区間走行経路を調査済みとした後に、上記ステップS502へ戻って別の未調査の区間走行経路を調査する。
上記ステップS502〜S508を繰り返して、区間走行経路作成部6における区間走行経路記憶部7に記憶された区間走行経路データの全ての区間走行経路の調査が終わると、このステップS107における区間走行経路削除処理を終了して、図8のメインルーチンへ戻る。
再び図8を参照して、区間走行経路削除処理(ステップS107)が終了すると、経路選出動作の全ての動作が完了する。
【0046】
以上のように、本発明の一実施形態に係る経路選出システムおよび方法によれば、車両が最適経路を外れて走行した区間のみの区間走行経路をその属性情報と共に記憶し、次回にこの区間を使用できる最適経路が探索された時には、この区間を記憶した区間走行経路に置き換えた経路で誘導案内を行うようにしている。
これにより、現在状況に応じて使用者が以前に走行した道路を適切に反映した経路を求め、誘導案内を行うことができる。
【0047】
なお、上記一実施形態では、最適経路探索部5においてダイクストラ法を使用すると記載したが、その他の経路探索方法を使用してもよい。また、上記一実施形態では、区間走行経路作成部6での区間走行経路追加処理(ステップS106)や区間走行経路削除処理(ステップS107)を、走行状態処理(ステップS105)を実行して目的地へ到着した後に行うようにしたが、車両が目的地へ向かって走行している最中に、走行状態処理(ステップS105)と並行して行っても構わない。
【産業上の利用可能性】
【0048】
本発明の経路選出方法及びシステムは、カーナビゲーションシステム等に利用可能であり、特に地図上で指定された出発地と目的地との間の最適経路を自動的に選出する場合等に適している。
【図面の簡単な説明】
【0049】
【図1】本発明の一実施形態に係る経路選出システムの構成を示すブロック図
【図2】図1の区間走行経路作成部6が行う動作の一例を示す図
【図3】図1の区間走行経路記憶部7に記憶されている区間走行経路データの一例を示す図
【図4】図1の交差区間調査部8および案内用経路作成部9が行う動作の一例を説明する図
【図5】図1の案内用経路作成部9において、区間走行経路データに基づいて誘導案内用経路を作成するパターンの一例を説明する図
【図6】図1の案内用経路作成部9において、区間走行経路データを使用する時の条件の一例を説明する図
【図7】図1の簡易復帰経路選出部12が行う動作の一例を示す図
【図8】本発明の一実施形態に係る経路選出システムが行う経路選出動作の一例を示すフローチャート
【図9】図8のサブルーチンステップS104の詳細な動作の一例を示すフローチャート
【図10】図8のサブルーチンステップS105の詳細な動作の一例を示すフローチャート
【図11】図8のサブルーチンステップS106の詳細な動作の一例を示すフローチャート
【図12】図8のサブルーチンステップS107の詳細な動作の一例を示すフローチャート
【符号の説明】
【0050】
1 地図データ記憶部
2 現在位置・走行軌跡検出部
3 走行軌跡入力部
4 地点入力部
5 最適経路探索部
6 区間走行経路作成部
7 区間走行経路記憶部
8 交差区間調査部
9 案内用経路作成部
10 地図表示部
11 出力部
12 簡易復帰経路選出部

【特許請求の範囲】
【請求項1】
車両走行における地図上の最適な経路を選出する経路選出方法であって、
経路の選出に必要な地図データを用いて、2地点間の最適経路を探索するステップと、
車両が走行した走行軌跡を収集するステップと、
探索した前記最適経路と収集した前記走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として記憶するステップと、
使用者に対して経路の誘導案内を行う場合、探索した前記最適経路と記憶した全ての前記区間走行経路とを比較し、1つの区間走行経路毎に当該最適経路と交わる区間走行経路(以下、交差区間走行経路という)が存在するか否かを調査するステップと、
調査した前記交差区間走行経路について、前記最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成するステップと、
作成した前記誘導案内用経路を使って、使用者に経路の誘導案内を行うステップとを備える、経路選出方法。
【請求項2】
車両走行における地図上の最適な経路を選出する経路選出システムであって、
経路の選出に必要な地図データを記憶する地図データ記憶手段と、
車両の現在位置および走行軌跡を求める現在位置・走行軌跡検出手段と、
使用者の指示に従って、特定情報として経路を求める目的地を入力する地点入力手段と、
前記地図データと前記特定情報とを用いて、2地点間の最適経路を探索する最適経路探索手段と、
前記最適経路探索手段が探索した最適経路と、前記現在位置・走行軌跡検出手段が求めた走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として抽出する区間走行経路作成手段と、
前記区間走行経路を記憶する区間走行経路記憶手段と、
使用者に対して経路の誘導案内を行う場合、前記最適経路探索手段が探索した最適経路と、前記区間走行経路記憶手段に記憶した全ての前記区間走行経路とを比較し、1つの区間走行経路毎に当該最適経路と交わる区間走行経路(以下、交差区間走行経路という)が存在するか否かを調査する交差区間調査手段と、
前記交差区間調査手段が調査した前記交差区間走行経路について、前記最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成する案内用経路作成手段と、
前記案内用経路作成手段が作成した前記誘導案内用経路を使って、使用者に経路の誘導案内を行う地図表示出力手段とを備える、経路選出システム。
【請求項3】
コンピュータ装置において実行されるプログラムを記録した記録媒体であって、
経路の選出に必要な地図データを用いて、2地点間の最適経路を探索するステップと、
車両が走行した走行軌跡を収集するステップと、
探索した前記最適経路と収集した前記走行軌跡とを比較して、当該走行軌跡上の異なる道路区間の始点から終点までの走行軌跡を1つの区間走行経路として記憶するステップと、
使用者に対して経路の誘導案内を行う場合、探索した前記最適経路と記憶した全ての前記区間走行経路とを比較し、1つの区間走行経路毎に当該最適経路と交わる区間走行経路(以下、交差区間走行経路という)が存在するか否かを調査するステップと、
調査した前記交差区間走行経路について、前記最適経路上の当該交差区間走行経路と交わる区間経路の部分を、当該交差区間走行経路の該当する部分に置き換えて誘導案内用経路を作成するステップと、
作成した前記誘導案内用経路を使って、使用者に経路の誘導案内を行うステップとを含む動作環境を、前記コンピュータ装置上で実現するプログラムを記録した、記録媒体。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate


【公開番号】特開2006−3369(P2006−3369A)
【公開日】平成18年1月5日(2006.1.5)
【国際特許分類】
【出願番号】特願2005−200527(P2005−200527)
【出願日】平成17年7月8日(2005.7.8)
【分割の表示】特願平11−362694の分割
【原出願日】平成11年12月21日(1999.12.21)
【出願人】(000005821)松下電器産業株式会社 (73,050)
【Fターム(参考)】