(57)【特許請求の範囲】
【請求項１】
車両が実際に走行した実走行経路を収集し、
複数の経路探索条件βi(i=1,…,N；Nは２以上の自然数)に基づいて実走行経路と出発地、目的地を同じくする経路をそれぞれ探索し、
前記収集された実走行経路と、前記探索された経路とを、経路の一致率若しくは相違率に基づいて比較し、この比較に基づき、
前記収集された実走行経路又はこれに近い経路を探索することができる経路探索条件を１又は複数決定することを特徴とする道路地図における経路探索条件の決定方法。
【請求項２】
前記の経路探索条件の決定方法は、複数の経路探索条件の下に経路を探索し、これらの探索された経路と、前記実走行経路との一致率若しくは相違率に基づいて経路探索条件を決定するものであることを特徴とする請求項１記載の道路地図における経路探索条件の決定方法。
【請求項３】
車両が実際に走行した複数の実走行経路を収集し、
複数の経路探索条件βi(i=1,…,N；Nは２以上の自然数)に基づいて実走行経路と出発地、目的地が同じ経路をそれぞれ探索し、
前記収集された実走行経路と、前記探索された経路とを、経路の一致率若しくは相違率に基づいて比較し、この比較に基づき、
前記収集された複数の実走行経路を代表する経路を探索することができる経路探索条件を１又は複数決定することを特徴とする道路地図における経路探索条件の決定方法。
【請求項４】
前記実走行経路を代表するとは、経路の一致率若しくは相違率分布の平均値、中央値、又は最大値をいう請求項３記載の道路地図における経路探索条件の決定方法。
【請求項５】
前記の経路探索条件の決定方法は、複数の経路探索条件の下に経路を探索し、これらの探索された経路と、前記実走行経路を代表する経路との一致率若しくは相違率に基づいて経路探索条件を決定するものであることを特徴とする請求項３記載の道路地図における経路探索条件の決定方法。
【請求項６】
前記経路探索条件は、リンク走行時間ベース、リンク距離ベース、リンクの道路属性考慮、右折回数考慮、右折タイミング考慮、最初に見つけた経路優先、目的地の方位に近いリンク優先、から選ばれた１又は複数の経路探索条件である請求項１又は請求項３記載の道路地図における経路探索条件の決定方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、各車両の実走行経路を収集し、これらの実走行経路を考慮した上で、道路地図上における目的地までの経路を探索する経路探索方法に関し、道路地図における経路探索条件の決定方法についてのものである。
【０００２】
【従来の技術】
地上の交通情報センターが、車両から目的地のデータを受け取ると、道路地図上における目的地までの経路を探索し、この経路データを車載装置に提供する技術が知られている。
また、車載装置においても、道路地図上における目的地までの経路を探索し、この探索経路を車内の表示画面に表示することが行われている。
【０００３】
【発明が解決しようとする課題】
ところで、前述のようにコンピュータ探索された経路は、リンク走行時間ベース、リンク距離ベース、リンクの道路属性考慮、右折回数考慮、右折タイミング考慮、最初に見つけた経路優先、目的地の方位に近いリンク優先などを加味した一定の経路探索条件に基づいて探索されたものである。
この経路探索条件に基づいて探索された経路は、必ずしもドライバの感覚にぴったりと一致した経路とはならない。例えば、コンピュータによる経路探索では、国道のような幹線道路が選ばれることが多く、ドライバのよく知っている抜け道が活用されることが少ないということがある。このために、現実の交通の流れとはかけ離れた経路になってしまう。
【０００４】
もしドライバの感覚に合致する経路の探索方法が確立すれば、将来の交通状況を正確に予測することが可能になり、道路交通の緩和策がとりやすくなる。
そこで、本発明により、実際に車両が走行した実走行経路を収集することにより、経路探索条件を最適化することができる経路探索条件の決定方法を提案する。
【０００５】
【課題を解決するための手段及び発明の効果】
(1)本発明の経路探索条件の決定方法は、車両が実際に走行した実走行経路を収集し、複数の経路探索条件βi(i=1,…,N；Nは２以上の自然数)に基づいて実走行経路と出発地、目的地を同じくする経路をそれぞれ探索し、前記収集された実走行経路と、前記探索された経路とを、経路の一致率若しくは相違率に基づいて比較し、この比較に基づき、前記収集された実走行経路又はこれに近い経路を探索することができる経路探索条件を１又は複数決定する方法である（請求項１）。
前記の構成によれば、実走行経路を収集して、ドライバが実際に走行する経路を導くような経路探索条件を決定することができる。
【０００６】
したがって、各車両がどのような道路を走行するのかを、把握することができるとともに、将来、車両がどのような道路を走行するかの予測もでき、道路交通の整理に役立てることができる。
探索された経路が実走行経路に一致し又は近づくかどうかの判断は、経路の一致率若しくは相違率に基づき行えばよい。
前記の経路探索条件は、複数の経路探索条件の下に経路を探索し、これらの探索された経路と、前記実走行経路との一致率又は相違率に基づいて経路探索条件を決定することができる（請求項２）。この決定方法として、線形計画法、二次計画法、遺伝子アルゴリズムなど公知の方法を用いることができる。
【０００７】
前記「一致率に基づいて」とは、例えば、実走行経路と一致率の大きさに応じて経路探索条件に重み付けを行い、重みの大きな経路探索条件から優先して、経路探索条件を決定することをいう。
前記実走行経路を収集するとき、複数の実走行経路を収集し、収集された実走行経路分布に基づいて、実走行経路を代表する経路を探索することができる経路探索条件を１又は複数決定してもよい（請求項３）。実走行経路は、車両ごとに異なるので、複数の実走行経路を求めて統計的処理をするほうが、経路探索条件決定の精度が上がり、好ましいからである。
【０００８】
前記実走行経路の分布を代表する経路を決めるのに、経路の一致率分布の平均値、中央値、又は最大値などを採用すればよい（請求項４）。
【００１２】
【発明の実施の形態】
交通情報センターで車両の実走行経路を収集し、経路探索をして車両に送信する場合の、本発明の実施の形態を、添付図面を参照しながら詳細に説明する。
図１は、交通情報センターＡのシステム概略図であり、交通情報センターＡは、車両の実走行経路及び道路交通情報を収集して、主要な交差点をつなぐ経路を随時探索し、通信回線を通してこの経路データを光ビーコンに送信するものである。
【００１３】
交通情報センターＡについて詳説すると、交通情報センターＡは、磁気ディスクなどの外部メモリ１３、コントローラ１１及び通信回線用モデム１２を有している。
コントローラ１１は、外部メモリ１３から必要なデータを得るメモリ制御部、ダイクストラ法又はポテンシャル法（柴田、天目、下浦「ストカスティック経路探索アルゴリズムの開発」住友電気第１４３号，ｐ．  １６５，１９９３年９月参照）により目的地から出発地までの最適経路を計算する経路計算処理部、ＳＲＡＭ及びＤＲＡＭなどにより構成されている。
【００１４】
外部メモリ１３は、経路情報提供エリア内に設置されているそれぞれの主要交差点等同士を結んだリンクに関する各種データ（経路ネットワークデータという）を記憶している。
リンクを具体的に示すと次のようになる。例えば道路地図が図２（ａ）  に示されるようなものであったとすると、リンクは、図２（ｂ）  に示すように、交差点Ｎ１  からＮ２  までを結ぶリンクＬ１２、交差点Ｎ２  からＮ１  までを結ぶリンクＬ２１，…といったように示される。Ｂ１  ，Ｂ２  ，Ｂ３  は、光ビーコンの設置点を示す。
【００１５】
前記経路ネットワークデータは、表１に示すように、経路ネットワークテーブルの形で記憶されている。経路ネットワークテーブルには、各リンクの識別番号（リンク番号）、リンク距離、国道、都道府県道、市町村道若しくは高速道路等、景色の善し悪し、踏切やトンネルの有無、カーブや山道の有無のなどの道路属性、そのリンクの始点と終点の座標、リンク方位、交差点形状、そのリンクの終点に接続される１本又は複数本の退出リンクへのアークコスト（後述）及び退出リンクへのポインタ等が含まれている。
【００１６】
【表１】
0003551241.tif 000002
【００１７】
ここで言葉の定義をしておくと、リンクの終点から、このリンクに接続される次のリンクを見た場合の、この次のリンクを「退出リンク」、リンクの始点から、このリンクに接続する前のリンクを見た場合の、この前のリンクを「進入リンク」という。なお、退出、進入という用語は、あくまでリンクの走行方向に注目したもので、経路を探索する方向とは無関係である。例えば、出発地から経路を探索するときは、各リンクの退出リンクを次々に辿っていき、目的地から経路を逆探索するときは、各リンクの進入リンクを次々に辿っていく。
【００１８】
「接続コスト」とは、当該リンクから退出リンクに出るための右左折又は直進のコストをいう。例えば、進入禁止の場合、接続コストは無限大となり、信号がある場合、右左折又は直進時の平均的な信号待ち時間を考慮したコストとなる。「アークコスト」とは、当該リンクを通過するときの走行時間であるリンクコストに、退出リンクに出るための接続コストを加算したものをいう（図３（ｂ）  参照）。ここで、アークというのは、図３（ａ）  に示すように、リンクの始端ノードの直後から次のリンクの始端ノードの直後までをいう。
【００１９】
アークコスト及び退出リンクへのポインタは、例えば、次の（１），（２）に示されるように、経路探索条件が変わっても対応できるように、経路探索条件ごとの値を記憶している。
（１）最短時間の経路探索条件：リンク旅行時間をベースにしたアークコスト。
前記アークコストは、法定速度走行時のコストを使ってもよいが、本実施形態では過去の車両走行速度から導かれる統計的なコストを使う。統計的なコストを使う場合は、日、曜日、時間帯ごとに異なる値（予測値）を採用してもよい。統計上、日、曜日、時間帯ごとに交通渋滞の程度や交通規制が変わることがあるからである。
【００２０】
また、交通情報センターＡに道路の渋滞情報等が入ってくれば、それを考慮した変更を行ってもよい。例えば、事故のため、あるリンクが上下とも不通になったときには、当該リンクのアークコストは、通行再開までそれぞれ無限大になる。またある道路の上り車線が渋滞中であれば、上りのアークコストがその渋滞に応じて増大する。
（２）最短距離の経路探索条件：リンク距離をベースにしたアークコスト。このアークコストも、交通情報センターＡに道路の渋滞情報等が入ってくれば、それを考慮した変更を行ってもよいことは、前記のとおりである。
また、アークコストは、経路探索過程の中でも処理される。例えば、
（ａ）できるだけ国道以上の道路を使う経路探索条件の場合：都道府県道、市町村道のアークコストを大きくする。
（ｂ）カーブや山道の道路をなるべく避ける経路探索条件の場合：カーブや山道を有するリンクのアークコストを大きくする。
（ｃ）高速道路を利用しない場合：属性が高速道路であるリンクのアークコストを大きくする。
（ｄ）右折回数を制限する場合：当該回数を超えて右折する場合には、右折退出リンクへのアークコストを大きくする。
（ｅ）右折タイミングを制限する場合：右折タイミングの制限とは、経路の初期、中期、終期いずれかのタイミングで右折することをいう。例えば経路の初期に右折するのであれば、出発地から当該地点までの旅行距離、旅行時間などで経路の初期と判断すれば、右折退出リンク以外の退出リンクへのアークコストを大きくし、経路の初期を過ぎたと判断すれば、右折退出リンクへのアークコストを大きくする。
（ｆ）最初に見つけた経路を優先する場合：最初にピボットテーブル（後述）から取り出して探索したリンクのアークコストを小さくして、後から探索される別の経路が最適経路として選ばれる確率を少なくする。
（ｇ）目的地までの方位に近い方位のリンクを優先する場合：リンク方位が目的地までの方位に近いリンクのアークコストを小さくする。
【００２１】
実際に採用される経路探索条件は、前記（１）（２）、前記（ａ）〜（ｇ）などの組み合わせになる。以下、組み合わせである経路探索条件の１つ１つをβ１，β２，β３，‥‥（代表してβｉと書く）と表記することとする。βｉは、例えば高速道路を利用する最短時間の経路探索条件であったり、右折制限３回付きの最短距離の経路探索条件であったりする。
次に、走行軌跡の一致率について説明する。
図４はリンクＬａ〜Ｌｆを含む道路地図であり、リンクＬａ，Ｌｂ，Ｌｃ，Ｌｄからなる実線の経路と、リンクＬａ，Ｌｅ，Ｌｆ，Ｌｄからなる破線の経路とが描かれている。リンクＬａの旅行時間をｔａ，距離をｄａ，リンクＬｂの旅行時間をｔｂ，距離をｄｂ，などと表すと、実線の経路を基準にした破線の経路の一致率δは、旅行時間を基にすれば（ｔａ＋ｔｄ）／（ｔａ＋ｔｂ＋ｔｃ＋ｔｄ）、旅行距離を基にすれば（ｄａ＋ｄｄ）／（ｄａ＋ｄｂ＋ｄｃ＋ｄｄ）となり、相違率は、旅行時間を基にすれば（ｔｅ＋ｔｆ）／（ｔａ＋ｔｂ＋ｔｃ＋ｔｄ）、旅行距離を基にすれば（ｄｅ＋ｄｆ）／（ｄａ＋ｄｂ＋ｄｃ＋ｄｄ）となる。
【００２２】
このように一致率又は相違率を定義しておくと、ある経路を基準にとって、それに近い経路、それから離れた経路を数値で評価することができる。したがって、複数の経路を一次元の軸上で表すことができる。
また、経路距離差ｄは、（ｄｅ＋ｄｆ）−（ｄｂ＋ｄｃ）となる。旅行時間差ｔは、（ｔｅ＋ｔｆ）−（ｔｂ＋ｔｃ）となる。経路距離差ｄや旅行時間差ｔを使っても、複数の経路を一次元の軸上で表すことができる。
【００２３】
次に、複数の車両の実走行経路を収集する手順を説明する。この収集は、光ビーコンＢを通して行う。
光ビーコンＢは、図５に示すように、通信回線と接続されるモデム２３，制御装置２４、経路メモリ２１，車載ナビゲーション装置とのデータの送受信をする端末機２２を有している。
光ビーコンＢは、車載ナビゲーション装置から、車両を特定するＩＤ符号、車両が前回光ビーコンと交信した地点、前回光ビーコンと交信した地点から今回交信した地点までの経路と実際にかかった旅行時間、車両の出発地からの経路、出発地からの旅行時間の情報を受ける。
【００２４】
これらの情報（以下「実走行データ」という。このうち収集された車両の経路を「実走行経路」という）は、制御装置２４により処理されてモデム２３から通信回線を通して交通情報センターＡに送られる。
交通情報センターＡは、各車両から実走行経路を収集すれば、それを外部メモリ１３に蓄積している。
交通情報センターＡは、指定された時刻ごとあるいは一定の時間ごとに、各主要交差点等に対応するリンクから経路提供エリア内の他の主要交差点等に対応するリンクまでの最適経路を計算する。
【００２５】
この計算に当たって、蓄積された実走行経路のデータに基づいて、実走行経路を探索することができる経路探索条件を１又は複数決定する。
その決定の内容をフローチャート（図６）に従って詳説する。交通情報センターＡのコントローラ１１は、出発地となるリンクＯを１つ決定し、目的地リンクＤを１つ決定する。そして、出発地Ｏと目的地Ｄとを通る実走行経路ｒｊ（ｊ＝１〜Ｍ）を抽出する（ステップＳ１）。
経路探索条件βｉをＮ（Ｎは２以上の自然数）とおり変えて経路Ｌｉを探索する（ステップＳ２）。経路探索方法については、後述する。
次に、経路探索条件βｉをいろいろ変えて探索された複数の経路Ｌｉのうち１つの経路Ｌｉを選び（これを「基準経路Ｌｉ」という）、横軸に実走行経路ｒｊと基準経路Ｌｉとの一致率δｊをとり、縦軸に実走行経路ｒｊの度数をとり、度数分布ｅｉを求める（ステップＳ３）。この処理は、基準経路Ｌｉ（ｉ＝１〜Ｎ）ごとに行う。
度数分布は、図７のようなグラフとなる。グラフには、実走行経路分布の平均値ｍｉと分散ｖｉを書き入れている。
【００２６】
基準経路Ｌｉは、複数あるから、図７のような分布図を、基準経路の数Ｎだけ描くことができる。図８は、各分布ｅｉ（ｉ＝１〜Ｎ）を同時に描いたグラフである。
各経路探索条件βｉごとの平均値ｍｉと分散ｖｉを使って、
Σｋｉ｛（１−ｍｉ）２＋ｖｉ｝              （ｉ＝１〜Ｎ，Σｋｉ＝１）                  （１）
を最小にする重み係数ｋｉを線形計画法、２次計画法などを用いて求める（ステップＳ４）。重み係数ｋｉは、実走行経路を実現する確率を表している。
【００２７】
なお、式（１）では平均値ｍｉと分散ｖｉを使ったが、これ以外に、最頻値、中央値などと分散ｖｉを組み合わせた式を用いてもよい。
そして、経路探索条件βｉの優先順位を、重み係数ｋｉの大きさの順に決定する（ステップＳ５）。
例えば、Ｎ＝２とし、β１が最短時間条件、β２が最短距離条件であるとする。式（１）を最小にするような重み係数を算出した結果、ｋ１＝０．６，ｋ２＝０．４となった場合には、最短時間条件β１が１番、最短距離条件β２が２番となる。
【００２８】
最適な経路探索条件を１つだけ決定する場合は、β１を決定することとなる。最適な経路探索条件を２つ決定する場合は、β１とβ２を決定することとなる。
このように、実走行経路を導くことができる１又は複数の経路探索条件を決定することができる。
前記経路探索条件の決定にあたっては、基準経路Ｌｉとの一致率δｊの度数分布ｅｉを求めていた。しかし、一致率δｊでなく、基準経路Ｌｉとの経路距離差ｄｊや旅行時間差ｔｊを用いてもよい。また経路距離の比や旅行時間の比を用いることもできる。
【００２９】
図９は、経路距離差ｄｊを用いて経路探索条件を１又は複数決定する手順を解説するためのフローチャートである。
図９に従って説明すると、出発地Ｏと目的地Ｄとを通る実走行経路ｒｊ（ｊ＝１〜Ｍ）を抽出する（ステップＴ１）。
経路探索条件βｉをＮとおり変えて経路Ｌｉを探索する（ステップＴ２）。
次に、基準経路Ｌｉごとに、横軸に実走行経路ｒｊと基準経路Ｌｉとの経路距離差ｄｊをとり、縦軸に実走行経路ｒｊの度数をとり、度数分布ｅｉを求める（ステップＴ３）。
度数分布は、図１０のようなグラフとなる。グラフには、実走行経路分布の平均値ｍｉと分散ｖｉを書き入れている。
【００３０】
基準経路Ｌｉは、複数あるから、図１０のような分布図を、基準経路の数Ｎだけ描くことができる。図１１は、各分布ｅｉ（ｉ＝１〜Ｎ）を同時に描いたグラフである。
各経路探索条件βｉごとの平均値ｍｉと分散ｖｉを使って、
Σｋｉ（ｍｉ２＋ｖｉ）  （ｉ＝１〜Ｎ，Σｋｉ＝１）                  （２）
が０に近くなるようにする重み係数ｋｉを線形計画法、２次計画法などを用いて求める（ステップＴ４）。重み係数ｋｉは、実走行経路を実現する確率を表している。
【００３１】
なお、式（２）では平均値ｍｉと分散ｖｉを使ったが、これ以外に、最頻値、中央値などと分散ｖｉを組み合わせた式を用いてもよい。
そして、経路探索条件βｉの優先順位を、重み係数ｋｉの大きさの順に決定する（ステップＴ５）。
以上の経路探索条件の決定は、出発地リンク、目的地リンクを１組特定した上で行ったものであり、地域内のすべての出発地リンク、目的地リンクの組に対して行ったものではない。実際、出発地リンク、目的地リンクを変えて、図６の経路探索条件の決定手順を繰り返し行うこともできる。しかし、すべての出発地リンク、目的地リンクの組の数は膨大なので、いくつかの代表的な出発地リンク、目的地リンクの組について、前記経路探索条件の決定を行えば、当該地域の経路探索条件を１又は複数決定することができると考えている。
【００３２】
交通情報センターＡは、決定された１又は複数の経路探索条件に基づいて出発地からの経路探索を行う。ここで、経路探索方法を簡単に説明する。
経路計算処理部は、外部メモリ１３から読み出された経路ネットワークデータに基づいて、ＤＲＡＭに設けられているピボットテーブル（後述）を利用して最適経路計算を行うとともに、経路計算の結果をＳＲＡＭにリザルトテーブル（後述）の形で記録させるものである。
【００３３】
前記「ピボットテーブル」とは、ダイクストラ法又はポテンシャル法により経路計算を行うときに、経路探索中のリンクを一時的に記憶する場所であって、経路ネットワークテーブルに記憶されている多数のリンクのうち、現在計算に必要なリンクを記憶している先入れ先出し型のテーブルである。ピボットテーブルは、表２に示すように、ピボットテーブルに経路探索すべきリンクが入っているかどうかを示すピボット有効フラグの欄と、リンクを特定するための経路ネットワークテーブルへのポインタの欄を備えている。
【００３４】
【表２】
0003551241.tif 000003
【００３５】
「リザルトテーブル」は、表３に示すように、リンク番号とリンク距離（これらは経路ネットワークテーブルからコピーされるものである）、ピボット登録フラグ、ピボットポインタ、経路コスト、進入リンクへのポインタの各欄を持っている。
【００３６】
【表３】
0003551241.tif 000004
【００３７】
ピボット登録フラグは、リンクがピボットテーブルに登録されているかどうかを示すフラグである。ピボットポインタは、リンクがピボットテーブルのどの場所に登録されているかを示すポインタである。経路コストは出発地リンクから当該リンクへの到達コストである。さらに正確には、あるリンクの経路コストとは、出発値から当該リンクまでつながった経路上の各リンクのアークコストを総和したものとなる（図３（ｂ）  参照）。
【００３８】
次に、前記経路ネットワークテーブル、リザルトテーブル及びピボットテーブルを利用した経路探索手法を説明する。以下の計算では、出発地から目的地までトリーを作って経路計算する方法を説明するが、これとは反対に目的地から出発地までトリーを作って経路計算する方法でもよいことを予め断っておく。前者では、出発地リンクが計算開始リンクとなるが、後者では目的地リンクが計算開始リンクとなる。
【００３９】
本実施形態の経路探索手法は、要するに、経路提供エリアの経路ネットワークデータを構成するいずれかのリンクを計算開始リンクとし、前記計算開始リンクから同エリア内の他の全てのリンクに到る最適経路トリーを取得して、この最適経路トリーを利用して前記計算開始リンクから計算開始リンクに到る経路を取得する手順である。
コントローラ１１の行う最適経路の計算手順は、よく知られたものであるので、以下では簡単に説明する。
【００４０】
まず、経路を求めたい日、曜日、時間帯に対応する経路ネットワークテーブルを外部メモリ１３から取得する。そして出発地リンクを１つ設定する。
さらに、重み係数ｋｉに基づく優先度の高い経路探索条件βｉから順に、経路を探索する。これは、車両の実走行経路に近い経路から順に探索するためである。
次に、現時点で入手されている道路交通情報に基づきアークコストを修正する。この修正は、時々刻々入手される渋滞情報、事故情報、工事情報等に基づいて行われるものである。この修正をすれば、アークコストは、実走行を考慮した上に、日時、曜日、渋滞、工事、事故などで変わる動的なコストを考慮したものとなる。
【００４１】
そして、リザルトテーブルを初期化する。すなわち、ピボット登録フラグを０にクリアし、経路コストを無限大（実際には、メモリのビット数で決まる最大値）にする。さらにピボットテーブルをも初期化する。具体的には、ピボット有効フラグを０クリアする。
次に出発地リンクＳをピボットテーブルに登録し、その行のピボット有効フラグを１にし、出発地リンクＳの経路コストをリザルトテーブル上で、有限な値、例えば当該出発地リンクＳのリンクコストに変更する。これは出発地リンクＳからの経路計算を開始するためである。
【００４２】
これ以後、経路探索を開始する。まず、ピボットテーブルを参照し、登録されたリンクがあるかないかを調べる。
リンクがあれば、当該リンク（リンクＬという）を取り出し、ピボットテーブルからリンクＬを削除し、ピボット有効フラグを０にする。
次に、経路ネットワークテーブルを参照してリンクＬの退出リンクＰを探索する。退出リンクＰを１つ特定すると、リザルトテーブル上でリンクＬの経路コスト（前に有限な値とおいたもの）を参照し、この経路コストにリンクＰへのアークコストを足したものを経路コストＡとし、リザルトテーブル上のリンクＰの経路コスト（初期値は無限大になっている）と比較する。経路コストＡのほうが小さければ、リザルトテーブル上のリンクＰの経路コストをＡに置き換える。そして、リザルトテーブル上でリンクＰの進入リンクとしてリンクＬを設定することにより、リンクの接続をする。
【００４３】
そしてリザルトテーブル上でリンクＰのピボットテーブル登録フラグを参照し、リンクＰをピボットテーブルに登録する。これは、リンクＰを基にして次のリンクを探索していくためである。
さらに、ピボットテーブルに登録されているリンクについて、他の退出リンクがあればそれについても経路探索を続けていく。この過程で、経路コストＡの方が大きいということになればそれ以上の経路探索を打ち切る。
【００４４】
ピボットテーブルに登録されているリンクについて探索が終われば、ピボットテーブルに登録されている他のリンクについても経路探索を続ける。
このようにしてピボットテーブルに登録されているリンクがなくなれば、最適経路のトリーが確定する。
リザルトテーブル上で、各リンクを逆に辿っていき、各経路の経路コスト、進入リンクを誘導テーブルの最適経路トリーの欄に登録する。
【００４５】
優先度の次に高い経路探索条件βｉに基づいても、前記と同様に最適経路トリーを求める。このようにして、１又は複数の経路探索条件βｉに基づいて最適経路トリーが求まる。
さらに、交通情報センターＡは、他の出発地リンクからの最適経路を計算してその結果をそれぞれの誘導テーブルに記録するのであれば、他の出発地リンクについても、前記と同じことをする。
【００４６】
また、日、曜日、時間帯の違う将来の予測をしたいのであれば、日、曜日、時間帯を変えて行う。したがって、最終的には、日、曜日、時間帯ごと、出発地リンク別、経路探索条件βｉ別に複数の最適経路トリー求まることになる。
交通情報センターＡは、それらの経路情報を誘導テーブルの形にして、当該出発地リンクに対応する光ビーコンＢに送信する。光ビーコンＢは、交通情報センターＡから前記経路情報を取得すれば、自己の経路メモリ２１の中に記憶する。
【００４７】
次に、車両が、光ビーコンＢに経路提供要求及び目的地のデータを送信すると、光ビーコンＢが、経路情報の中から日、曜日、時間帯、経路探索条件βｉを選択して送受信機２２を通して車両に対して経路を送信する。経路探索条件βｉが複数ある場合の経路の選択基準は、いろいろ考えられるが、例えば、車両一台ごとに経路探索条件βｉを変えた経路を送信してもよく、複数台ごとに経路探索条件βｉを変えてもよく、時間帯ごとに変えてもよい。優先度の高い経路探索条件βｉの経路を送信する回数が、優先度の低い経路探索条件βｉの経路を送信する回数よりも多くなるようにすることが好ましい。
【００４８】
図１２を参照して、車載ナビゲーション装置３０の構成を簡単に説明しておく。この車載ナビゲーション装置３０は、前記光ビーコンＢから経路情報を取得して、表示し誘導する機能を備えている。
この車載ナビゲーション装置３０は、方位センサとしてＧＰＳ受信機３２を備えており、車速センサとしてエンジンコントロールユニット（ＥＣＵ）３４の車速信号を取得するようにして、ＧＰＳ受信機３２で検出された方位情報と、車速信号に基づく位置情報とから、車載地図専用メモリ（図示せず）に格納されている道路パターンとの比較（いわゆる地図マッチング法、特開昭６４−５３１１２号公報参照）に基づいて車両位置を検出する機能を有している。
【００４９】
車載ナビゲーション装置３０は、さらに交通情報センターＡからの経路情報が提供される経路提供エリア内の、交通情報センターＡが持っているリンクの情報（各リンクの識別番号、そのリンクの始点と終点の座標等の情報）を持っており、リモコンキー３３によって、自車が行きたい目的地を画面上で入力すると、前記リンクの中から、この目的地に最も近いリンクを特定して、送受信機３１を通して、この目的地リンクと、自車の位置データとを光ビーコンＢに送ることができるようになっている。
【００５０】
以上で、本発明の実施の形態を説明たが、本発明の実施は、前記形態に限られるものではない。
例えば、実走行経路を収集する手段として、光ビーコン以外に、電波ビーコン、車載の自動車電話、携帯電話、道路に設置した車番読取カメラなどを採用してもよい。車両と交通情報センターの通信手段として、光ビーコン以外に、電波ビーコン、車載の自動車電話、携帯電話などを採用してもよい。
【００５１】
また、前記実施の形態では、交通情報センターで車両の実走行経路を収集し、経路探索をして車両に送信していたが、交通情報センターで車両の実走行経路を収集し、最適な経路探索条件βｉを求めて車両に送り、車両で経路を探索するという形でもよい。また、車両を省略して、交通情報センターで車両の実走行経路を収集し、最適な経路探索条件βｉを求めて経路を探索し、この探索経路を将来の交通状況の予測に役立てる、という実施も考えられる。
【図面の簡単な説明】
【図１】交通情報センターＡのシステム概略図である。
【図２】（ａ）は光ビーコンを含む道路地図であり、（ｂ）は（ａ）に対応するリンク図である。
【図３】（ａ）は接続される一連のリンクを示す図であり、（ｂ）はアークコスト及び経路コストの概念を解説するための図である。
【図４】経路の一致率を説明するための、リンクＬａ〜Ｌｆを含む道路地図である。
【図５】光ビーコンの概略構成図である。
【図６】収集された実走行経路又はこれに近い経路を探索することができる経路探索条件を、経路の一致率に基づいて１又は複数決定するための手順を示すフローチャートである。
【図７】横軸に実走行経路ｒｊと基準経路Ｌｉとの一致率δｊをとり、縦軸に実走行経路ｒｊの度数をとった度数分布図である。
【図８】各度数分布ｅｉ（ｉ＝１〜Ｎ）を同時に描いたグラフである。
【図９】経路距離差ｄｊを用いて、経路探索条件を１又は複数決定する手順を解説するためのフローチャートである。
【図１０】横軸に実走行経路ｒｊと基準経路Ｌｉとの経路距離差ｄδｊをとり、縦軸に実走行経路ｒｊの度数をとった度数分布図である。
【図１１】各度数分布ｅｉ（ｉ＝１〜Ｎ）を同時に描いたグラフである。
【図１２】車載ナビゲーション装置の概略構成図である。
【符号の説明】
１１コントローラ
１２通信回線用モデム
１３外部メモリ
２１経路メモリ
２２端末機
２３モデム
２４制御装置
３０車載ナビゲーション装置
３１送受信機
３２ＧＰＳ受信機
３３リモコンキー
３４エンジンコントロールユニット
【図１】
0003551241.tif 000005
【図２】
0003551241.tif 000006
【図３】
0003551241.tif 000007
【図４】
0003551241.tif 000008
【図５】
0003551241.tif 000009
【図６】
0003551241.tif 000010
【図７】
0003551241.tif 000011
【図８】
0003551241.tif 000012
【図９】
0003551241.tif 000013
【図１０】
0003551241.tif 000014
【図１１】
0003551241.tif 000015
【図１２】
0003551241.tif 000016