説明

巡回経路選出方法

【課題】 実用時間でより実用的な巡回経路を選出することができる巡回経路選出方法を提供する。
【解決手段】 ステップS301では、出発地および目的地が選択される。次のステップS302では、各巡回地点(各配送地)が選択される。次のステップS303では、各巡回地点間の最小コスト経路を求める地点間経路計算処理が行われる。次のステップS304では、各巡回地点をどのような順序で通過するのが最適かを決定する巡回順序決定処理が実行される。次のステップS305では、ステップS304で得られた巡回順序に従って、ステップS303の地点間経路計算処理で求められた経路データをつなぎ合わせて、出発地から目的地までの一本の巡回経路が構成される。次のステップS306では、求められた巡回経路がユーザーに提示されたり、現在位置が変化する車両が巡回経路上を誘導されたりする。

【発明の詳細な説明】
【0001】
【発明の属する技術分野】本発明は、巡回経路選出方法に関し、より特定的には、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法に関する。
【0002】
【従来の技術】周知のごとく、近年、交通管制技術やITS関連技術への社会的関心が高まっている。かかる社会的関心により、目的地までの実用的な経路を自動的に選出する経路探索方法が盛んに研究開発され、既にいろいろな分野で応用されている。その応用例には、車載カーナビゲーションシステム、またはATIS等の交通情報提供システムのセンター側装置がある。これらは、「特開平4−204881号」公報に開示された技術等を使って、ある地点(出発地)から別の地点(目的地)への最適経路を求めている。
【0003】また、配送管理システム等への応用のため、選択された複数の地点を全て通過する最適経路を求める巡回経路探索技術への要望も高まっている。巡回経路探索技術は、数学的には「巡回セールスマン問題」と呼ばれており、古くから計算量の多い計算困難な問題として知られている。巡回セールスマン問題の完全解を求める方法は確立されておらず、実用的な近似解を求める方法が存在するだけである。近似解を求める方法は、「特開平3−191464号」公報、および「特開平4−57147号」公報に開示されている。「特開平3−191464号」公報は、各地点の重心からの角度順により初期経路を構成して、一定地点数の範囲で最適化を繰り返す方法を開示している。また、「特開平4−57147号」公報は、順次増加コストの一番小さい地点を追加して初期経路を構成し、地点の並べ替えを行って最適化する方法を開示している。
【0004】まず、「特開平3−191464号」公報に開示された従来の巡回経路探索方法(以下、第1の巡回経路探索方法と称す)の概略を説明する。第1の巡回経路探索方法では、まず、選択された各地点の重心と、各地点とがなす角度を求めた後に、求められた各角度に基づいて初期経路が構成される。次に、構成された初期経路が一定地点数毎に分割される。次に、分割された領域毎に「深さ優先探索方法」が適用され、当該領域に含まれる地点が、より短い経路を構成するように並び替えられる。これによって、第1の巡回経路探索方法は、選択された各地点の最短コスト経路を求めている。さらに、分割した領域間で、それぞれに含まれる地点が交換された後に、上記の一連の処理が繰り返される。最終的に、コストが小さくならなくなれば、第1の巡回経路探索方法の処理は終了する。以下、第1の巡回経路探索方法の詳細を、図37のフローチャートを参照して説明する。特に、図37(a)は、第1の巡回経路探索方法の処理手順を示すメインフローチャートである。
【0005】図37(a)において、設定された地点群の中心座標が決定された後(ステップS37a1)、中心座標と各地点座標とを結んだ角度順に、各地点がつながれ(ステップS37a2)、これによって、巡回順序の初期経路が構成される。次に、初期経路を基に、最適化ループ処理が行われ(ステップS37a3)、最小コスト経路に近づける補正処理が行われる。ここで、図37R>7(b)は、図37(a)のステップS37a3またはS37a6の詳細な処理手順を示すサブフローチャートである。図37(b)において、分割のためのスタート地点が決められ(ステップS37b1)、設定された地点群が、初期経路の順序に従いつつ、決定されたスタート地点を基準として一定地点数毎の領域に分割される。次に、分割された領域毎に、総当たり方法によって最小コスト経路が求められる(ステップS37b2)。次に、各分割領域を合成して、1周の経路(巡回経路)が構成される(ステップS37b3)。最後に、ステップS37b3で得られた巡回経路コストが、前回のものより小さくなっていれば(ステップS37b4)、巡回経路コストがより小さくなる可能性があるとして、ステップS37b1に戻る。そして、次回は、ステップS37b3で得られた巡回経路コストを基に、ステップS37b1〜S37b4の処理が繰り返される。一方、ステップS37b4で、今回得られた巡回経路コストが、前回のものよりも小さくなっていなければ、ほぼ最小コストの巡回経路となったと判断する。そして、前回の巡回経路が最適のものとして、最適化ループ処理(ステップS37a3)が終了する。
【0006】次に、図37(a)に戻り、各地点や各辺が交換された後、効率順にm組のつなぎ替え方が調べられる(ステップS37a4)。次に、1番目(m=1)のつなぎ替えが行われる(ステップS37a5)。さらに、ステップS37a3と同様の最適化ループ処理が行われる(ステップS37a6)。次に、ステップS37a6で得られた巡回経路のコストが今までで最小であるかが判断され(ステップS37a7)、最小であれば、巡回経路コストがより小さくなる可能性があるとして、ステップS37a6で得られた巡回経路コストを基準として、ステップS37a4〜S37a7の処理が繰り返される。一方、ステップS37a7で、ステップS37a6で得られた巡回経路のコストが今までで最小でなければ、ステップS37a8が行われる。次に、m組全てについて巡回経路のコストが確認したかが判断され(ステップS37a8)、確認済みであれば、第1の巡回経路探索方法が終了する。一方、ステップS37a8で、m組全てについて確認が終わっていなければ、今回選択された巡回経路(つまり、つなぎ替えが行われた後の巡回経路)は最小コストにならないことから、巡回経路は、つなぎ替えが行われる前のものに戻される(ステップS37a9)。さらに、次の組合せ(m=m+1)のつなぎ替えが行われた後(ステップS37a10)、ステップS37a6が再度実行され、S37a6〜S37a7の処理が繰り返される。
【0007】次に、「特開平4−57147号」公報に開示された従来の巡回経路探索方法(以下、第2の巡回経路探索方法と称す)の概略を説明する。第2の巡回経路探索方法では、まず、巡回する地点群の中から、コストの小さい三角形を構成する地点を順次追加して初期経路が構成される。その後、ランダムに地点を切り離して、巡回経路の再構成を行う処理が繰り返され、これによって、最小のコストを有する巡回経路が探索される。以下、第2の巡回経路探索方法の詳細を、図38のフローチャートを参照して説明する。図38において、地点データが入力されると、入力された各地点間の距離を記録した行列が作成される(ステップS3801)。次に、入力された地点群の中から3地点が選択された後に、選択された3地点を用いて、最初の3角形が作成される(ステップS3802)。次に、未選択の地点群から最適三角形を構成する1地点が選択され、選択された地点を巡回経路に加える処理が行われる。この処理は、未選択の地点群が無くなるまで繰り返され、これによって、巡回経路が構成される(ステップS3803)。次に、構成された巡回経路の全距離が計算され、今回算出された全距離が、今までに求められた巡回経路の中で最短か否かが判断される。全距離が最短であれば、今回の巡回経路が最適なものとして採用される(ステップS3804)。次に、処理回数・時間により処理を打ちきるか否かが判断される(ステップS3805)。所定処理回数・所定時間を超えていれば処理が終了し、所定処理回数・所定時間を超えていなければステップS3806が行われる。構成された巡回経路から、ランダムに地点が切り離され、地点が未選択の状態に戻された後(ステップS3806)、ステップS3803の処理に戻り、以降の処理が繰り返される。
【0008】また、上記方法とは別に、遺伝アルゴリズムやニューラルネットを応用した各種方法も学会等で報告されている。
【0009】
【発明が解決しようとする課題】しかしながら、後者の遺伝アルゴリズムやニューラルネットを応用した方式では、極小解に陥る可能性があり、最悪の場合を考えると経路品質面で問題がある。また、第1の巡回経路探索方法は、巡回経路のコストが最小かどうかに基づいて、巡回経路の修正を続けるかどうか判断している。そのため、巡回経路のコストが極小解に陥る可能性があり、最適な巡回経路を求めることができない場合が生じる。さらに、巡回経路のコストが最終的に収束するまでの処理時間が長くなる可能性がある。
【0010】さらに、第2の巡回経路探索方法は、ランダムに地点を切り離して再構成する処理を、回数・時間等で制限し打ちきっているため、最終的に巡回経路コスト(距離)がどこまで最適なものに収束するかは一定しないという問題点があった。
【0011】それ故に、本発明の目的は、実用時間でより実用的な巡回経路を選出することができる巡回経路選出方法を提供することである。
【0012】
【課題を解決するための手段および発明の効果】第1の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、第3のステップは、現在調査対象となっている巡回順序の途中までの合計評価値(以下、第1の合計評価値と称す)を、第2のステップで得られた各評価値に基づいて計算する、第5のステップと、現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値(以下、第2の合計評価値と称す)を、第2のステップで得られた各評価値に基づいて計算する、第6のステップと、第6のステップで計算された第2の合計評価値の最小値を記録する第7のステップとを含み、第5のステップで計算された第1の合計評価値が、第7のステップで記録された第2の合計評価値の最小値を超えた場合、現在の調査が打ち切られる。
【0013】第1の発明によれば、巡回する順序を決定する処理において、深さ優先探索方法に基づく巡回経路の調査処理中に、第1の合計評価値が、第2の合計評価値の最小値(つまり、過去最小であった第2の合計評価値)を超えた場合、その巡回経路に関しては、そこから派生するそれ以降の調査処理が打ち切られる。これによって、最適な巡回経路となり得ない巡回地点の組合せに関する調査を省略することができるので、最適な巡回経路の選出時間を短縮する事ができる。
【0014】第2の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を決定する第4のステップとを含み、第3のステップは、複数の巡回地点を管理するために、当該各巡回地点が連鎖的につなげられた管理情報を作成する第5のステップと、第5のステップで作成された管理情報に基づいて、巡回順序を構成していく第6のステップとを含む。
【0015】第2の発明によれば、巡回する順序を決定する処理において、調査対象としての未選択の巡回地点が連鎖的につながっている管理情報が適用される。これによって、未選択の巡回地点を効率的に選出できるので、最小コスト巡回経路の選出時間を短縮することができる。
【0016】第3の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、第2のステップは、少なくとも、出発地または目的地と、各巡回地点とを含む範囲の地図データを読み込む第5のステップと、出発地または目的地と、各巡回地点とを探索開始点として順次設定する第6のステップと、第5のステップで読み込まれた地図データを利用して、第6のステップで設定された探索開始点と、当該探索開始点以外の地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各評価値を計算する第7のステップを含む。
【0017】第3の発明によれば、各地点間の評価値を求める処理において、当該各地点を探索開始地点として順に選択し、ダイクストラ法に基づく単方向探索処理が行われる。これによって、m個の地点に含まれる各2地点間の探索処理をm×(m−1)回からm回に削減することができるので、最適な巡回経路の選出時間を削減することができる。
【0018】第4の発明は、選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、複数の巡回地点として選択可能な候補地点が予め決定されており、当該各候補地点間の経路が求められており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに複数の候補地点の中から複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、第2のステップは、第1のステップで選択された複数の巡回地点に含まれる各2地点間の各評価値を、予め記録されている経路情報の中から読み込むことにより得る。
【0019】第4の発明によれば、予め巡回地点として選択可能な地点を決定し、各地点間経路を求めておいて経路情報を記録しておくことにより、各巡回地点間の経路を計算する必要がないので、最適な巡回経路の選出時間を短縮することができる。
【0020】第5の発明は第4の発明に従属しており、第2のステップは、出発地および/または目的地が、候補地点に含まれていない場合、当該出発地および/または当該目的地ならびに各巡回地点を含む範囲の地図データを読み込む第5のステップと、第1のステップで選択された出発地および目的地を探索開始点として順次設定する第6のステップと、第5のステップで読み込まれた地図データを利用して、第6のステップで設定された探索開始点と、各巡回地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各評価値を得る第7のステップを含む。
【0021】第5の発明によれば、任意の出発地または目的地を探索開始点として、ダイクストラ法に基づく探索処理が行われる。これによって、出発地から各巡回地点、または各巡回地点から目的地への経路が1回の探索処理で求められるので、任意の出発地からの最適な巡回経路、または任意の目的地への最適な巡回経路の選出時間を短縮することができる。
【0022】第6の発明は第4の発明に従属しており、候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、当該出入口地点と当該各候補地点との間の経路が予め求められており、さらに、少なくとも当該出入口地点と各候補地点との間の経路の評価値を含む経路情報が予め記録されており、第2のステップは、出発地または目的地が、候補地点を含む区域外だった場合、出入口地点の中から、仮の出発地または仮の目的地を選択する。
【0023】第6の発明によれば、巡回区域へアクセス可能な道路上の地点が、予め出入口地点として決定されている。また、各出入口地点と各巡回地点(候補地点)との間、および各巡回地点(候補地点)と各出入口地点との間の経路もまた予め求められている。これらは、経路情報として予め記録されている。そして、巡回区域への入口地点を仮の出発地、または巡回区域からの出口地点を仮の目的地として選択することにより、仮の出発地からの巡回経路、または仮の目的地までの巡回経路を求めることができる。これによって、例えば、車載機のようにRAM容量が少ない環境において、出発地から各巡回地点への経路または各巡回地点から目的地までの経路が求められなかった場合でも、選択された地点を巡回する巡回経路を求めることができる。
【0024】第7の発明は第6の発明に従属しており、出入口地点には、候補地点が含まれる区域の境界を横切る主要な道路上の地点が予め選択されており、第2のステップは、出入口地点を探索開始点または探索終了点として、出発地または目的地に対して、双方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する。第7の発明によれば、上記出入口地点として、上記巡回区域の境界を横切る主要な道路上の地点を選択することにより、最低限必要な出入口地点を機械的に設定することができる。これによって、出入口地点の選択を簡略化することができ、さらに、探索処理を用いて自動的に適切な仮の出発地、または仮の目的地を選択することができる。
【0025】第8の発明は第6の発明に従属しており、出入口地点には、候補地点が含まれる区域の境界を横切る主要な道路上の地点と、当該候補地点が含まれる区域の周辺を通過するより主要な道路上の地点とが予め選択されており、第2のステップは、出入口地点を探索終了点として、さらに第1のステップで選択された出発地または目的地を探索開始点として、一方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する。
【0026】第8の発明によれば、上記出入口地点として、上記巡回区域には含まれないが、周辺を通過するより主要な道路上の地点が選択される。これによって、出発地または目的地からの一方向の階層別探索方法で最小コストで到達する出入口地点を選択できるので、巡回経路選出処理を簡略化でき、選出時間を短縮できる。
【0027】第9の発明は第6の発明に従属しており、第2のステップは、ユーザーの選択に基づいて、出入口地点の中から、仮の出発地および/または仮の目的地を選択する。
【0028】第9の発明によれば、上記仮の出発地、または仮の目的地は、出入口地点の中から、ユーザーにより選択される。これによって、ユーザーが好きな方向から巡回区域に進入または脱出できるので、ユーザーの好みで巡回区域までの進入道路または巡回区域からの脱出道路を選択することができる。
【0029】第10の発明は、選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、複数の巡回地点として選択可能な候補地点が予め決定されており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに複数の候補地点の中から、複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第3のステップと、第3のステップで決定された巡回順序に従って、第1のステップで選択された出発地から目的地へ至る1本の巡回経路を構成する第4のステップとを含み、第4のステップは、第3のステップで決定された巡回順序に従って、第1のステップで選択された出発地から目的地までの部分的な経路を繰り返し求める第5のステップと、第5のステップで求められた部分的な経路をつなぎ合わせて、1本の巡回経路を構成する第6のステップとを含む。
【0030】第10の発明によれば、予め巡回地点として選択可能な地点(候補地点)が予め決定されている。また、各地点間経路に基づいて得られた地点間経路コストのみが予め記録されている。この状態で、巡回経路の部分経路を2地点間探索処理を繰り返して求めることにより、経路データを記録する必要がないので、記憶領域に記憶されるデータ量を削減することができる。
【0031】第11の発明は第10の発明に従属しており、複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が記録されており、第2のステップは、第1のステップで選択された出発地または目的地が、候補地点を含む区域外だった場合、出入口地点の中から仮の出発地または仮の目的地を選択し、第5のステップは、第1のステップで選択された出発地から最初の巡回地点までの部分的な経路、または、最後の巡回地点から当該第1のステップで選択された目的地までの部分的な経路を求める時に、第2のステップで選択された仮の出発地または仮の目的地を省いて求める。
【0032】第11の発明によれば、第2のステップで選択された仮の出発地または仮の目的地を飛ばして、出発地から目的地までの巡回経路の部分経路が求められる。これによって、ユーザーが真に立ち寄りたい巡回地点から最適な巡回経路が選出されるので、自動的に選択された仮の出発地または仮の目的地を不自然に通過する巡回経路の選出を防ぐことができる。
【0033】第12の発明は第10の発明に従属しており、複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点を含む区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が記録されており、第2のステップは、第1のステップで選択された出発地または目的地が、候補地点を含む区域外だった場合、ユーザーの選択に基づいて、出入口地点の中から仮の出発地または仮の目的地を選択し、第5のステップは、第1のステップで選択された出発地から、第2のステップで選択された仮の出発地を経由して最初の巡回地点に至る部分的な経路、または、最後の巡回地点から、当該第2のステップで選択された仮の目的地を経由して当該第1のステップで選択された目的地に至る部分的な経路を求める。
【0034】第12の発明によれば、ユーザー自身が設定した仮の出発地または仮の目的地は飛ばさずに、出発地から目的地までの巡回経路の部分経路が求められる。これによって、ユーザーが設定した仮の出発地または仮の目的地を通過する巡回経路が選出されるので、必ずユーザーが意図したアクセス道路を通って巡回区域に進入、または巡回区域から脱出する巡回経路を求めることができる。
【0035】第13の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、第3のステップは、複数の巡回地点の内、近接するもの同士を階層的なグループにまとめる第5のステップと、第5のステップでまとめられたグループの巡回順序を階層毎に決定し、最終的に、複数の巡回地点を巡回する順序を決定する第6のステップとを含む。
【0036】第13の発明によれば、近隣の巡回地点が階層的にグループ化される。階層的なグループに基づいて巡回経路が求められる。これによって、調査対象となる組合せの数が減少するので、特に巡回対象となる地点数が多い場合に、巡回経路選出時間を短縮することができる。
【0037】第14の発明は第13の発明に従属しており、第5のステップは、2地点間の空間距離に基づいて、複数の巡回地点をまとめる。第14の発明によれば、2地点間の空間距離が近いものから優先的に1グループにまとめることができる。これによって、近接する巡回地点をグループ化できるので、比較的簡単な処理で経路品質を向上することができる。
【0038】第15の発明は第13の発明に従属しており、第5のステップは、2地点間の経路距離に基づいて、複数の巡回地点をまとめる。第15の発明によれば、2地点間の経路の距離が近いものから優先的に1グループにまとめることができる。これによって、空間距離的には近くても2地点間の道路は迂回しているような巡回地点がグループ化されることを避けることができるので、より経路品質を向上することができる。
【0039】第16の発明は第13の発明に従属しており、第5のステップは、他のグループと比較して、過度に広範囲なグループを形成しない。第16の発明によれば、他のグループと比較して広い範囲がグループが形成されない。これによって、各グループの大きさを平均化でき、いびつな巡回経路の選出を防ぐことができるので、より経路品質を向上することができる。
【0040】第17の発明は第13の発明に従属しており、第6のステップは、階層的な各グループの内、上位階層のグループから巡回順序を決定する。第17の発明によれば、階層化されたグループにおいて、上位階層のグループから巡回順序を決定することにより、まず上位階層で大まかな巡回順序を決定し、全体の計算量を削減することができる。これによって、最適な巡回経路の選出時間を短縮することができる。
【0041】第18の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、出発地、目的地および各巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、第2のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、第3のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含む。
【0042】第18の発明によれば、第2のステップで得られる評価値は、各2地点間に対するものである。したがって、かかる評価値を基に決定される巡回順序は、実際に車両が走行する道路を想定したものとなる。これによって、ユーザーにとって違和感のない効率的な巡回順序を求めることができる。
【0043】第19の発明は第18の発明に従属しており、第2のステップは、出発地と各巡回地点または目的地との間、複数の巡回地点に含まれる各2地点間、および当該各巡回地点と目的地との間の経路を求め、求めた各経路の評価値に基づいて、出発地と各巡回地点または目的地との間の評価値、複数の巡回地点に含まれる各2地点間の各評価値、および当該各巡回地点と目的地との間の評価値を取得する。
【0044】第19の発明によれば、第2のステップでは、評価値が、各2地点間の経路を実際に求めることにより得られる。そのため、より好ましい巡回順序を決定することが可能となる。
【0045】第20の発明は第18の発明に従属しており、第2のステップは、出発地、目的地および各巡回地点のそれぞれを探索開始点として、予め記憶される地図情報を用いて、出発地側探索処理および/または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各2地点間、および当該各巡回地点と当該目的地との間の経路を求め、求めた各経路の評価値に基づいて、出発地と各巡回地点または目的地との間の評価値、複数の巡回地点に含まれる各2地点間の各評価値、および当該各巡回地点と目的地との間の評価値を取得する。
【0046】第20の発明によれば、第2のステップで、各地点を探索開始点とした出発地側探索処理および/または目的地側探索処理により、2地点間の経路が求められるので、探索処理の回数を最小限に抑えることができる。これによって、必要な組み合わせすべてについて、経路を短時間で求めることができる。
【0047】第21の発明は第20の発明に従属しており、地図情報は階層構造を有しており、下位階層の地図情報は、相対的に狭い範囲を詳細に記録した地図を表しており、上位階層の地図情報は、相対的に広い範囲を粗く記録した地図を表しており、第2のステップは、使用すべき地図情報の階層を選択し、選択された階層の地図情報を用いて、出発地、目的地および各巡回地点のそれぞれを探索開始点として、出発地側探索処理および/または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各2地点間、および当該各巡回地点と当該目的地との間の経路を探索し、選択された階層の地図情報では、経路を求めることができない場合、上位階層の地図情報を用いて、当該経路を求める。
【0048】第21の発明によれば、第2のステップでは、まず、下位階層の地図情報を用いて、各探索開始点からの探索処理を開始する。そして、下位階層の地図情報では求めることができない経路があった場合に、上位階層の地図情報を用いて探索処理を続ける。これによって、各階層に記録された道路網に適した探索範囲を設定することができるので、距離がある2地点間の経路を短時間で求めることができる。
【0049】第22の発明は第19の発明に従属しており、第4のステップは、第3のステップで決定された巡回経路に従って、出発地、目的地および各巡回地点から選択可能な2地点の組み合わせ数分だけ、2地点間探索を繰り返すことにより、1本の巡回経路を構成する。
【0050】第22の発明によれば、第4のステップで、再度2地点間探索を行うことにより、第2のステップでは求めた経路を残しておかなくとも、巡回経路を構成することが可能となる。これによって、巡回経路選出のために必要となるRAMの容量を抑えることが可能となる。
【0051】第23の発明は第19の発明に従属しており、第2のステップはさらに、必要な2地点間毎に、最小の評価値を有する経路データを記録し、第4のステップは、第3のステップで決定された巡回経路に従って、第2のステップで記録された経路データに基づいて、1本の巡回経路を構成する。
【0052】第23の発明によれば、第2のステップで記録された最小評価値の経路データに基づいて巡回経路が構成されるので、第4のステップでは、探索処理を改めて行う必要がなくなる。これによって、巡回経路選出に必要となる時間を抑えることができる。
【0053】
【発明の実施の形態】図1は、本巡回経路選出方法が採用されるカーナビゲーションシステムの構成を示すブロック図である。図1において、カーナビゲーションシステムは、ロケーター101と、データ記憶部102と、操作部103と、ナビゲーション装置104と、情報提示部105とを備えている。
【0054】ロケーター101は、GPS、車速センサ、角速度センサ、絶対方位センサ等を含み、車両の現在位置を計算するためのデータを収集する。データ記憶部102は、通常CDやDVDが使用され、交差点や道路の接続状況や座標・形状・属性・規制情報など、道路ネットワークに関する地図情報、地点設定を行うための索引情報等、ナビゲーションに必要となる各種情報を記憶している。操作部103は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力したり、ユーザーの選択したい項目を指定したりする。ナビゲーション装置104は、CPUやメモリ(プログラムメモリ、ワーキングメモリ)等を含む。ナビゲーション装置104は、基本的には、ロケーター101から入手した車両の移動情報を基に現在位置を特定するロケーション機能、目的地までの経路を自動的に選出し案内する経路誘導機能、索引情報を検索したり任意の場所の地図を表示したりする情報検索機能とを有している。情報提示部105は、表示装置(液晶ディスプレイ、CRTディスプレイ等)やスピーカ等を含み、ユーザーに対して、現在車両位置の提示、誘導経路の案内、検索情報の提示を行う。
【0055】次に、図1のように構成されたカーナビゲーションシステムの各機能について説明する。まず、ロケーション機能について概説する。ロケーター101は、刻々と変化する車両位置に関する情報(車両向きの変化角、車両の走行距離、絶対位置等)を収集する。ナビゲーション装置104は、ロケーター101により得られた車両位置に関する情報から、車両の移動軌跡を計算する。ナビゲーション装置104はさらに、マップマッチング技術等を利用しつつ、算出された車両の移動軌跡と、データ記憶部102から得られた周辺地図上の道路ネットワークとを比較して、地図上における車両の現在位置を特定する。情報提供部105は、ナビゲーション装置104により特定された、車両の現在位置を地図上に表示する。
【0056】次に、情報検索機能について概説する。操作部103は、情報提示部105のディスプレイ上に表示された各種項目の中から、検索したい内容を選択する。選択された項目の中から指定のものを、データ記憶部102の記録情報の中から検索し、情報提示部105のディスプレイ上に表示する。必要であれば、情報提示部105のスピーカーから音声等を出力する。
【0057】さらに、本発明に関わる経路誘導機能について概説する。まず、ユーザーは、操作部103を操作して、出発地および目的地を設定する。すなわち、ユーザーは、操作部103を操作することにより、情報提示部105に表示された地図の画像をスクロールさせ、希望する地点を出発地および目的地として入力する。なお、出発地は、上述のロケーション機能で検出した車両の現在位置を使用してもよい。次に、ナビゲーション装置104は、上記のように設定された出発地および目的地の位置に対して、データ記憶部102に記憶された地図上のノードまたはリンク上の一番近い点を、探索開始点および探索終了点として採用する。さらに、ナビゲーション装置104は、周知のダイクストラ法などを用いて最短コスト経路を計算し、求められた経路を、リンク列、ード列または座標列に変換し、誘導経路とする。本実施形態では、請求項における「評価値」の一例としてコストを採用する。以下の第1〜第4の巡回経路選出方法では、コストを旅行時間とみなし、旅行時間が短い経路を選出するものとする。最後に、情報提示部105は、ナビゲーション装置104で求められた誘導経路と現在車両位置と、データ記憶部102に記憶された地図データとに基づいて、誘導経路上を進むにはどの方向へ進めば良いかを、音声や表示を行なってユーザーに案内する。
【0058】また、ナビゲーションシステムでは、出発地・目的地の間に複数の巡回地点が設定できる。ユーザーは、目的地の設定と同様に、操作部103を操作して、複数の巡回地点を設定する。この時に、巡回する地点を設定する前に、巡回する地域を選択するようにしても良い。さらに、ナビゲーション装置104は、出発地・目的地・巡回地点間等の経路コストを参照し、設定された各巡回地点を通過し、しかもより小さな経路コストで出発地から目的地へ至る最適巡回経路を選出する。本巡回経路選出方法に関しては、後でフローチャートを用いて詳述する。
【0059】また、図2は、本巡回経路選出方法を適用可能な配送車両管理システムの一般的な構成を示すブロック図である。図2において、配送車両管理システムは、無線装置201と、データ記憶部202と、操作部203と、コンピュータ204と、情報提示部205とを備えている。無線装置201は、携帯電話、専用無線等を含み、各配送車両に搭載されたロケーションシステムから、各配送車両の現在位置を収集する。データ記憶部202には、大容量ハードディスクが通常使用される。データ記憶部202は、交差点および/または道路の接続状況、座標、形状、属性ならびに規制情報など、道路ネットワークに関する地図情報、地点設定を行うための索引情報、もしくは配送先管理情報等、配送管理業務に必要となる各種情報を記憶する。操作部203は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力したり、ユーザーの選択したい項目を指定したりする。コンピュータ204は、CPUやメモリ(プログラムメモリ、ワーキングメモリ)等を含む。コンピュータ204は、基本的には、無線装置201から入手した各配送車両の現在位置を管理する位置管理機能、各車両に対し複数の配送先を指定して最適な配送経路を自動的に選出する経路選出機能、配送先情報を検索・入力する配送先情報管理機能とを有している。情報提示部205は、表示装置(液晶ディスプレイ、CRTディスプレイ等)やスピーカ等を含み、ユーザーに対して、各配送車両の現在位置の提示、配送経路の案内、配送先情報の提示を行う。
【0060】次に、図2のように構成された配送車両管理システムの各機能について説明する。まず、位置管理機能について概説する。無線装置201は、刻々と変化する各配送車両の位置情報を収集する。コンピュータ204は、無線装置201から各配送車両の位置に関する情報を入手し、データ記憶部202に記憶された地図データから得られた配送エリアの道路ネットワークを、情報提示部205のディスプレイ上に表示する。さらに、情報提示部205は、表示された道路ネットワークには、各配送車両の現在位置を重ねて表示する。
【0061】次に、配送先情報管理機能について概説する。操作部203は、情報提示部205のディスプレイ上に表示された配送エリアの地図上に重ねて表示されたカーソルを、マウスで希望する位置に移動することにより任意の位置を指定できる。配送先に関する付属情報(ID、配送先名称、連絡先、補足情報)は、操作部203のキーボードから入力される。また、過去に入力された配送先に関する付属情報は、データ記憶部202に記憶されており、それらの情報は、操作部203のマウス操作により呼び出され選択される。そして、操作部203のキーボード操作により、配送先に関する付属情報の修正、削除等を行う。
【0062】さらに、本発明に関わる経路選出機能について概説する。まず、ユーザーは、操作部203を操作して、配送地点を設定する。すなわち、ユーザーは、操作部203のマウスを操作することにより、情報提示部205のディスプレイ上に表示された配送エリアの地図上を参照して、実際に配送する配送先を選択する。なお、出発地および目的地は配送センターまたは上述の位置管理機能により把握された配送車両の現在位置を使うことができる。次に、コンピュータ204は、配送先がどの区域に属するか判定し、どの配送車両に割り振るか判断する。特定の配送車両に配送先が集中するようであれば、周辺区域受け持ちであり配送先が少ない他の配送車両に振り分けるようにしても良い。さらに、コンピュータ204は、各配送車両毎に出発地から出発し、割り振られた全配送先を通過して目的地に到達する最適巡回経路を選出する。本巡回経路選出方法に関しては、以降にフローチャートを用いて詳述する。
【0063】(1)第1の巡回経路選出方法図3は、第1の巡回経路選出方法の処理手順を示すメインフローチャートである。図3のメインフローチャートに従う処理は、図1のナビゲーション装置104または図2のコンピュータ204により行われる。図3において、ユーザーは、上述したようにして、出発地・目的地と、各巡回地点(各配送地)とを選択する(ステップS301,S302)。次に、各巡回地点間の最小コスト経路を求める地点間経路計算処理が行われる(ステップS303)。ここで、図4は、図3のステップS303の詳細な処理手順を示すフローチャートである。図4において、まず、出発地・目的地・各巡回地点を含む範囲の地図データが一括して読み込まれる(ステップS401)。次に、出発地と各巡回地点の中から未選択の地点が1つ選択される(ステップS402)。選択された地点は、探索開始点として、以降の処理で用いられる。次に、読み込まれた地図データ全域に対して、探索開始点を起点として、公知のダイクストラ法に基づく探索処理が広げられる(ステップS403)。これによって、探索開始点から、終点としての他の地点(各巡回地点、目的地)への経路が構成され、構成された経路コストがコストマトリクスに記録され、さらに、経路の道順を示す経路データが記録される(ステップS404)。ここで、コストマトリクスとは、起点から終点への経路コストを、起点を行とし終点を列とする行列に記録したものである。図5はコストマトリクスの一構成例である。図5R>5の例では、出発地および目的地以外の巡回地点数はn個としている。なお、目的地を起点とする経路コスト、出発地を終点とする経路コスト、および出発地から目的地への経路コストは、後で行われる巡回順序決定処理(ステップS304)には必要ないので、「−」マークで記載されている。
【0064】図4のステップS404の次に、探索開始点としての未選択の地点が残っているか否かが判断される(ステップS405)。未選択の地点があれば、ステップS402に戻り、未選択地点の1つが、次の探索開始点として選択される。その後、上記一連の処理(ステップS403〜S405)が繰り返される。一方、ステップS405において、未選択の地点がなければ、地点間経路計算処理(図3のステップS303)は終了する。地点間経路計算処理の終了時点で、図5のコストマトリクスが完成し、各欄が埋め尽くされる。なお、上述したステップS402では、出発地と各巡回地点とから探索開始点が選択されていたが、目的地と各巡回地点とから探索開始点が選択されてもよい。この場合、ステップS403では、目的地と各巡回地点とから選択された探索開始点を基に探索処理が広げられる。このように、探索開始点として方向性を考慮した上で探索処理を行っても良い。
【0065】次に、図3のステップS304に進み、各巡回地点をどのような順序で通過するのが最適かを決定する巡回順序決定処理が実行される(ステップS304)。ここで、図6は、図3のステップS304の詳細な処理手順を示すフローチャートである。図6において、全巡回地点が未選択状態にされた後、巡回地点が1個ずつ選択される。この時、同じ巡回地点は重複して選択されてはならない。巡回地点は、選択された順に、未選択巡回地点の管理情報に登録される(ステップS601)。この管理情報は、図7に例示するリスト構造を有している。リスト構造とは、先頭の地点から次の地点を連鎖的に次々と指し示したものである。図7では、n個の巡回地点(N1〜Nn)が添え字の小さいものから連続的に並べられている。「先頭」には先頭の地点として<N1>が記録されており、「1番目」には、「先頭」の次の地点として<N2>が記録されている。以降、同様にして、選択された順番通りに、各巡回地点がつなげられていく。さらに、「(n−1)番目」には、最後に選択された地点として<Nn>が記録されており、「n番目」には巡回経路の終了を示すID情報として<終了>マークが記録されている。以上のリスト構造が採用されることにより、「先頭」から順番に次の地点を調べていくことが可能になる。これによって、後で行われる巡回再帰処理(ステップS604)において、未選択状態の巡回地点Ni(i=1,2…,n)を効率よく見つけだすことができる。
【0066】再度図6を参照する。ステップS601の次に、出発地が、巡回コストXの算出に必要となる前の巡回先PPとして選択される(ステップS602)。さらに、巡回コストXが初期化される(ステップS603)。すなわち、X=0に設定される。この後、巡回再帰処理が行われる(ステップS604)。ここで、図8は、図6のステップS604の詳細な処理手順を示すフローチャートである。まず、図8の処理手順で使用される、総巡回コストY、最小の総巡回コストYminおよび途中段階の巡回コストXについて説明する。今、n個(nは自然数)の巡回地点N1〜Nnが選択されていると仮定する。本実施形態において、巡回経路とは、図9(a)〜(c)に例示するように、同じ巡回地点を重複して通過することなく、全ての巡回地点N1〜Nnを通過しつつ、出発地から目的地まで至る経路を意味する。まず、総巡回コストYは、1本の巡回経路のコストである。出発地から各巡回地点Ni(iはi≦nを満たす自然数)までのコスト、2個の巡回地点NiおよびNj(jは、i≠jかつj≦nを満たす自然数)の間のコスト、各巡回地点Njから目的地までのコストは、図5のコストマトリクスに記載されている。したがって、巡回地点N1〜Nnを巡回する順序が決まれば、1本の巡回経路を構成するために必要となる各コストは特定される。特定された各コストを合計すれば、総巡回コストYを算出することができる。
【0067】深さ優先探索方法では、ある巡回経路の総巡回コストYを得た後、別の総巡回コストYを算出するという処理が繰り返される。最小の総巡回コストYminは、既に算出されている総巡回コストYの内、最小の値を有するものである。さらに、深さ優先探索方法では、1本の巡回経路を構成する際、互いに異なる巡回地点Niが1つずつ選択されていく。途中段階の巡回コストXとは、出発地から、現在選択された巡回地点Niまでの経路(途中までの巡回経路)のコストである。この途中段階の巡回コストXも、総巡回コストYと同様に、図5のコストマトリクスを参照して算出される。
【0068】図8のステップS801では、途中段階の巡回コストXと、最小の総巡回コストYminとが比較され、X≧Yminを満たすか否かが判定される(ステップS801)。X≧Yminと判定された場合、現在調査対象の巡回経路は最小の総巡回コストYminをとる可能性が全くない。そのため、以降の処理を行っても無駄であるから、巡回再帰処理は打ち切られる。また、X<Yminと判定された場合、現在調査対象の巡回経路は最小の総巡回コストYminをとる可能性があるので、以降の処理を行うべく、ステップS802が行われる。なお、ステップS801の時点で、巡回経路が1本も得られていなければ、最小の巡回コストYminは無限大とみなされる。したがって、この場合もX<Yminと判定される。
【0069】次に、図7の管理情報の「先頭」に設定された巡回地点Niが、現在の巡回先CPとして選択される(ステップS802)。これによって、出発地NSPの次に巡回すべき巡回地点Niが選択される。次に、前の巡回先PPが起点として選択され、現在の巡回先CPが終点として選択される。その後、起点と終点との間のコストがコストマトリクス(図5参照)から読み出される。読み出されたコストは、巡回コストXに加算される(ステップS803)。これによって、現在調査対象の巡回経路の途中段階の巡回コストXが得られる。
【0070】次に、図7の管理情報を参照して、「先頭」の巡回地点Niが最後の巡回先LPか否かが判定される(ステップS804)。この巡回地点Niの直後に<終了>マークが有れば、現在の巡回先CPが最後の巡回先LPとなる。つまり、調査対象の巡回経路が一通り構成されたことになるので、ステップS811が行われる。本ステップでは、現在の巡回先CP(つまり、最後の巡回先LP)が起点として選択され、目的地NDが終点として選択される。その後、起点と終点との間のコストがコストマトリクスから読み出される。読み出されたコストは、巡回コストXに加算される(ステップS811)。これによって、現在調査対象である巡回経路の総巡回コストY(合計)が算出される。
【0071】次に、今回得られた総巡回コストYと、最小の総巡回コストYminとが比較され、Y<Yminを満たすか否かが判定される(ステップS812)。Y<Yminと判定された場合、今回得られた総巡回コストYが最小の総巡回コストYminとして新たに記録される(ステップS813)。さらに、今回調査対象となった巡回地点N1、N2、…Nnの巡回順序も新たに記録される。なお、ステップS812の時点で、最小の総巡回コストYminが求められていない場合、最小の巡回コストYminは無限大とみなされる。したがって、この場合も、Y<Yminと判定される。このステップS812の後、巡回再帰処理が終了する。一方、Y≧Yminと判定された場合、今回得られた総巡回コストYが記録されることなく、そのまま巡回再帰処理は終了する。
【0072】ステップS804で、「先頭」の巡回地点Niが最後の巡回先LPでなければ、調査対象の巡回経路は完全に構成されていないので、次の巡回地点Nj(j≠i)を選択して巡回コストXを算出するために、ステップS805が行われる。ステップS805では、現在の巡回先CPが前の巡回先PPとして選択される。さらに、現在の巡回先CPとして選択されていた巡回地点Niは図7の管理情報から削除される(ステップS805)、これによって、未選択の巡回地点Nj(j≠i)のみが図7の管理情報に残る。さらに、未選択の巡回地点Nj(j≠i)のいずれかが「先頭」となる。
【0073】次のステップS806では、図8の巡回再帰処理が再度呼び出される。本ステップに移行した時点(つまり、初期状態)で、現在調査対象の巡回経路の途中までの巡回コストXが算出されている。今回の巡回再帰処理では、まず、この途中段階の巡回コストX≧最小の総巡回コストYminか否かが判断される(ステップS801)。X≧Yminの場合、上述したように、巡回再帰処理が終了する。X<Yminの場合、上述したように、ステップS802が行われる。次に、管理情報(図7参照)の「先頭」に現在設定されている巡回地点Njが、現在の巡回先CPとして選択される(ステップS802)。これによって、次に巡回すべき巡回地点Njが選択される。その後、上述したように、起点(=前の巡回先PP)と終点(=現在の巡回先CP)との間のコストが巡回コストXに加算される(ステップS803)。これによって、出発地NSPから今回選択された巡回地点Njまでの巡回コストXが得られる。
【0074】図7の管理情報において、「先頭」の巡回地点Njが最後の巡回先LPでなければ(ステップS804)、当該現在の巡回先CPが前の巡回先PPとして選択される。さらに、現在の巡回先CPとして選択されていた巡回地点Njは図7の管理情報から削除される(ステップS805)、これによって、未選択の巡回地点Nk(k≠i,k≠j)のみが図7の管理情報に残る。さらに、未選択の巡回地点Nkのいずれかが「先頭」となる。
【0075】その後、図8の巡回再帰処理が再度呼び出される(ステップS806)。このように、巡回再帰処理は、ステップS801で打ち切られない限り、巡回地点Niが管理情報からなくなるまで(つまり、巡回経路が一通り構成されるまで)、繰り返し呼び出される。各巡回再帰処理では、管理情報に残っている未選択の巡回地点Niから現在の巡回先CPが選択され(ステップS802)、その後、当該現在の巡回先CPが前の巡回先PPとして設定されるとともに、当該現在の巡回先CPが管理情報から削除される。設定された前の巡回先PPおよび現在の巡回先CPが削除された管理情報が、次回の巡回再帰処理に引き継がれる。このような状況で、次回の巡回再帰処理は再帰される。
【0076】以上のステップ806が終了すると、ステップS805で削除された現在の巡回先CPが図7の管理情報に戻される(ステップS807)。さらに、途中段階の巡回コストXが、ステップS803での加算前の状態に戻される(ステップS808)。次のステップS809では、新しい巡回経路を調査対象とするために、前の巡回先PPをステップS805で変更する前の状態に戻す。さらに、図7の管理情報において、ステップS807で戻された現在の巡回先CPの直後につながっている巡回地点Niが、新たな現在の巡回先CPとして選択される(ステップS809)。
【0077】次に、新たな現在の巡回先CPとして、<終了>マークが選択されたか否かが判定される(ステップS810)。これが<終了>マークであれば、弥山宅の巡回地点を全て調査したとして、巡回再帰処理が終了する。一方、これが<終了>マークでなければ、未選択の巡回地点を全て調査していないとして、ステップS803に戻り、上述と同様に繰り返される。以上の図8の巡回再帰処理は、最初に呼び出されたものが終了した時点で、全通りの巡回経路が調査され、最小の巡回コストYminが記録されている。そのため、図6のステップS604の巡回再帰処理が終了し、巡回順序決定処理が終了する。
【0078】ここで、巡回順序決定処理(ステップS304)の一具体例として、n=5の場合、つまり巡回地点N1〜N5の巡回順序を決定する場合について説明する。この場合、コストマトリクスは図10のように作成される。まず、ステップS304が開始されると、図11R>1(a)のような管理情報が作成される(ステップS601)。図11において、管理情報は、5個の巡回地点(N1〜N5)が、添え字の小さいものから順番に並べられる。最後の「5番目」には<終了>マークが記録される。これによって、選択対象となる5個の巡回地点N1〜N5が保持される。
【0079】次に、出発地NSPが、前の巡回先PPとして選択され(ステップS602)、巡回コストXが「0」に初期化される(ステップS603)。その後、最初の巡回再帰処理が呼び出され、1つ目の巡回経路TR1の総巡回コストY1が算出され始める。ここで、図1212(a)は、ステップS304において得られる巡回経路TR1および総巡回コストY1を示している。まず、現在の巡回コストXは最小の総巡回コストYmin(=∞)よりも小さいので(ステップS801)、「先頭」の巡回地点N1(図11(a)参照)が、現在の巡回先CPとして選択され(ステップS802)、これによって、出発地NSPの次に巡回すべき地点が選ばれる。次に、前の巡回先PP(=出発地NSP)と現在の巡回先(巡回地点N1)との間のコスト(その値はC01とする)が、図10のコストマトリクスから読み出され、巡回コストX(=0)に加算される(ステップS803)。その結果、現在の巡回コストXは、X=C01となる。
【0080】巡回地点N1は、図11(a)に示すように最後の巡回先LPでないので(ステップS804)、現在の巡回先CPとしての巡回地点N1は前の巡回先PPとして設定された後に、管理情報から削除される(ステップS805)。削除された巡回地点N1は、次回以降の巡回再帰処理では管理情報から除外されているので、現在の巡回先CPとして選択されない。これによって、同じ巡回地点Nを重複選択することなく、巡回経路TRが構成されていく。また、管理情報は、図11(b)のように、巡回地点N1が抜かれた分、他の巡回地点N2〜N5および<終了>マークが順番を詰める。
【0081】ステップS805の後、巡回地点N1の次の巡回先を選択して、そこまでの巡回コストXを算出すべく、2番目の巡回再帰処理が呼び出され実行される(ステップS806)。現在の巡回コストXはC01である。また、巡回経路TR1は、出発地NSP→巡回地点N1まで構成されている。また、巡回地点N1が前の巡回先PPとして選ばれている。さらに、管理情報の「先頭」は、図11(b)のように巡回地点N2である。この時点の状態(初期状態)で、2番目の巡回再帰処理が再帰される。2番目の巡回再帰処理(ステップS807)でも、巡回経路TRは1本も得られていないので、巡回コストX(=C01)は最小の総巡回コストYmin(=∞)よりも小さい(ステップS801)。そのため、現在「先頭」にある巡回地点N2(図11(b)参照)が、現在の巡回先CPとして、つまり巡回地点N1の次の巡回先が選択される(ステップS802)。次に、前の巡回先PP(=巡回地点N1)と現在の巡回先CP(巡回地点N2)との間のコスト(その値はC12とする)が巡回コストX(=C01)に加算される。その結果、現在の巡回コストXは、X=C01+C12となる。
【0082】巡回地点N2は、図11(b)の管理情報に示すように、最後の巡回先LPではないので(ステップS804)、巡回地点N2(現在の巡回先CP)は前の巡回先PPとして設定された後に、管理情報から削除される(ステップS805)。その結果、管理情報は、図11(c)の状態に遷移し、巡回地点N2が抜かれた分、他の巡回地点N3〜N5および<終了>マークが順番を詰める。
【0083】ステップS805の後、3番目の巡回再帰処理が呼び出される(ステップS806)。この時点で、巡回コストXはC01+C12である。また、巡回経路TR1は、出発地NSP→巡回地点N1→巡回地点N2まで構成されている。また、巡回地点N2が前の巡回先PPとして設定されている。さらに、「先頭」は、図11(c)のように巡回地点N3である。この時点の状態(初期状態)で、3番目の巡回再帰処理が実行されると、ステップS801およびS802が実行された後、前の巡回先PP(=巡回地点N2)と現在の巡回先(=巡回地点N3)との間のコスト(その値はC23とする)が巡回コストX(=C01+C12)に加算される(ステップS803)。その結果、現在の巡回コストXは、X=C01+C12+C23となる。さらに、ステップS804の実行後、巡回地点N3(現在の巡回地点CP)は前の巡回先PPとして設定された後に、図11R>1(d)に示すように管理情報から削除される(ステップS805)。
【0084】以降、4番目および5番目の巡回再帰処理(ステップS806)が呼び出される。便宜上、4番目の巡回再帰処理の説明を省略する。その後、5番目の巡回再帰処理が呼び出された時点で、巡回コストXはC01+C12+C23+C34である。また、巡回経路TR1は、出発地NSP→巡回地点N1→巡回地点N2→巡回地点N3→巡回地点N4まで構成されている。また、巡回地点N4が前の巡回先PPとして設定されている。さらに、管理情報は図11(e)のような状態にあり、「先頭」には巡回地点N5が設定されている。この時点の状態(初期状態)で、5番目の巡回再帰処理が実行されると、ステップS803において、前の巡回先PP(巡回地点N4)と現在の巡回先CP(巡回地点N5)との間のコスト(その値はC45とする)が巡回コストXに加算され(ステップS803)、巡回コストXは、C01+C12+C23+C34からC01+C12+C23+C34+C45に更新される。
【0085】次に、管理情報は現在、図11(e)の状態にあるので、「先頭」の巡回地点N5は、最後の巡回先LPと判定される(ステップS804)。そして、最後の巡回先LP(巡回地点N5)と目的地NDとの間のコスト(その値はC56とする)が、現在の巡回コストXに加算される(ステップS811)。これによって、巡回経路TR1が一通り構成されたことになる。巡回経路TR1は、巡回地点N1→巡回地点N2→巡回地点N3→巡回地点N4→巡回地点N5の順番で、出発地NSPから目的地NDへと至る経路である。また、巡回順序TR1が完全に構成されたことから、現在の巡回コストX(=C01+C12+C23+C34+C45+C56)は、総巡回コストY1として保持される。
【0086】次に、総巡回コストY1は、最小の総巡回コストYmin(=∞)よりも小さいので(ステップS812)、今回構成された巡回経路TR1および総巡回コストY1は、最適な巡回経路および最小の総巡回コストYminとして記録される(ステップS813)。その結果、5番目の巡回再帰処理(ステップS807)が終了し、巡回経路TR1について実行された巡回再帰処理が終了する。5番目の巡回再帰処理が閉じられると、4番目の巡回再帰処理のステップS807以降が行われ、2番目の巡回経路TR2に関する巡回再帰処理の準備が行われる。まず、4番目の巡回再帰処理のステップS805で削除された現在の巡回先CP(巡回地点N4)が、管理情報に戻される(ステップS807)。その結果、管理情報は、図11(e)の状態から、図13(a)の状態へと遷移する。また、現在の巡回コストXが、4番目の巡回再帰処理のステップS803が実行される前の状態に戻される。つまり、現在の巡回コストは、ステップS803でC34が加算される直前の状態に戻される。その結果、現在の巡回コストXは、X=C01+C12+C23に戻される。また、ステップS809において、前の巡回先PPが、第4回目の巡回再帰処理が呼び出された時のものに戻される。したがって、前の巡回先PPは、巡回地点N3に戻される。さらに、現在の巡回先CPは、4番目の巡回再帰処理で設定されていたものから、新しいものに更新される(ステップS809)。より具体的には、現在の管理情報(図13(a)参照)において、4番目の巡回再帰処理で使用された巡回地点N4の直後につながっている巡回地点N5が、新たな現在の巡回先CPとして設定される。
【0087】ステップS807〜S809の実行により、2番目の巡回経路TR2は、図12(b)に示すように、出発地NSP→巡回地点N1→巡回地点N2→巡回地点N3→巡回地点N5まで構成されたことになる。なお、出発地NSP→巡回地点N1→巡回地点N2→巡回地点N3の巡回コストXは既に得られている。この巡回コストXは、2番目の巡回経路TR2の総巡回コストYを求める際にも利用される。そして、この途中までの巡回経路TR2の巡回コストXを算出すべく、ステップS803が実行される。つまり、図12(b)に示すように、前の巡回先PP(=巡回地点N3)と現在の巡回先(巡回地点N5)との間のコスト(その値はC35とする)が、現在の巡回コストX(=C01+C12+C23)に加算され、その結果、現在の巡回コストXはC01+C12+C23+C35となる。
【0088】「先頭」の巡回地点N4は、図13(a)の管理情報に示すように、最後の巡回先LPではないので(ステップS804)、巡回地点N5(現在の巡回先CP)は前の巡回先PPとして設定された後に、管理情報から削除される(ステップS805)。その結果、管理情報は、図13(a)の状態から図13(b)の状態に遷移し、巡回地点N5が抜かれた分、<終了>マークが順番を詰める。
【0089】ステップS805の後、6番目の巡回再帰処理が呼び出される(ステップS806)。この時点で、巡回コストXはC01+C12+C23+C35である。また、巡回経路TR2は、出発地NSP→巡回地点N1→巡回地点N2→巡回地点N3→巡回地点N5まで構成されている。また、巡回地点N5が前の巡回先PPとして設定されている。さらに、「先頭」は、図13(b)のように巡回地点N4である。この時点の状態(初期状態)で、6番目の巡回再帰処理が実行される。まず、現在の巡回コストX(=C01+C12+C23+C35)は最小の総巡回コストYmin(=Y1)以上か否かが判断される(ステップS801)。今、X≧Ymin(=Y1)であると仮定する。この仮定下では、巡回経路TR2は最適であり得ない。したがって、以降の処理(ステップS802〜S813)を行う必要がなく、6番目の巡回再帰処理は打ち切られ、終了する。これによって、無駄な処理が行われなくなるので、演算回数が減ることとなる。
【0090】以降、1番目の巡回再帰処理が閉じられるまで、図8のフローチャートに示された処理が行われる。1番目の巡回再帰処理が閉じられた時点で、最小の総巡回コストYminを有する最適な巡回経路が記録されていることになる。これによって、図3のステップS304(巡回順序決定処理)が終了する。次のステップS305では、現在記録されている最適な巡回順序に従って、出発地NSPから目的地NDに至る一本の巡回経路を構成する。ステップS306では、求められた巡回経路がユーザーに提示されたり、車両の移動に伴う現在位置が巡回経路上に表示されたりする。
【0091】以上のように、本実施形態のステップS304(巡回順序決定処理)では、深さ優先探索方法を基本方法とした処理が行われ、最適な巡回順序が調査される。この巡回順序決定処理では、現在得られている途中段階の巡回コストXが、今まで最小の総巡回コストYminを超えた時点で、現在の巡回先CPから派生する調査処理を打ち切る。つまり、最小の総巡回コストYminとなりえない組合せの調査処理を省略することができる。これによって、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【0092】また、本ステップS304(巡回順序決定処理)では、選択対象としての巡回地点Niは、選択された時点で、図7の管理情報(リスト構造)から削除される。したがって、各巡回再帰処理が開始された時点で、図7の管理情報には、未選択の巡回地点Nj(j≠i)のみが管理されている。さらに、各巡回再帰処理では、現在の巡回先CPは、図7の管理情報の「先頭」から選択するだけである。これによって、効率的に未選択の巡回地点Niが選択される。その結果、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【0093】また、本ステップS303(地点間経路計算処理)において、出発地NSP、目的地NDおよびn個の巡回地点N1〜Nnに含まれる2地点間の最小コスト経路を求める際に、各地点が探索開始地点として順に選択され(ステップS402)、その後、ダイクストラ法を用いて単方向探索処理(ステップS403およびS404)が行われる。これによって、m地点(mは、出発地NSP、目的地NDおよびn個の巡回地点N1〜Nnを合計した地点数)の各2地点間の探索処理をm×(m−1)回からm回に削減することができる。これによっても、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【0094】(2)第2の巡回経路選出方法第2の巡回経路選出方法では、第1の実施形態におけるデータ記憶部102(図1)、および第2の実施形態におけるデータ記憶部202(図2)に、予め決められた地点間の最小コスト経路結果(地点間コストおよび経路データ)が追加記録されている。さらに、予め決められた地点には、その地点周辺にアクセスするための主要道路上の地点も含むこととする。この地点を出入口地点と呼ぶ。ここで、図14は、予め決められた地点の一例である。図14において、網掛けされた観光区域α内に、丸印で表された観光地点SPが予め決められた地点として選択されている。また、この観光区域αにアクセスする道路として、二重丸の国道上の地点(C1〜C3)と三重丸の高速IC上の地点(S1)が、出入口地点として予め決められた地点に追加されている。第2の巡回経路選出方法は、車載ナビゲーションシステム上で、観光区域α内の複数の観光地SPを巡回する最適な巡回順序を求める場合を想定している。第2の巡回経路選出方法の概略は、第1のそれと異なり、巡回地点N1〜Nnは、予め決められた地点の中から選択された後に、データ記憶部102(または202)に記憶された各地点間の経路コストが読み出される。その後に、図5のようなコストマトリクスが作成され、第1の巡回経路選出方法と同様に最適な巡回順序が決定される。以下、本発明の第2の巡回経路選出方法をより詳細に説明する。
【0095】図15は、第2の巡回経路選出方法の処理手順を示すメインフローチャートである。図15において、まず、第1の巡回経路選出方法と同様に、出発地NSPおよび目的地NDがユーザーにより選択される(ステップS1001)。次に、予め決められた地点群の中から、n個の巡回地点(配送地点)N1〜Nnが選択される(ステップS1002)。つまり、この予め決められた地点は、巡回地点N1〜Nnを選択するための候補地点である。次に、予め記憶された各地点間の最小コスト経路結果から、ステップS1002で選択された各巡回地点Niに含まれる地点間コストと経路データとが読み出される(ステップS1003)。読み出された地点間コストと経路データとは、地点間経路情報としてRAM上に記憶される。
【0096】次に、予め定められた地点ではない出発地NSPと目的地NDとを含む巡回経路TRを求めるために、端地点追加処理が行われる(ステップS1004)。端地点追加処理は、簡単に述べると、出発地NSPから各巡回地点N1〜Nnまで、および各巡回地点N1〜Nnから目的地NDまでの地点間コストおよび経路データを求めるための処理である。図16は、端地点追加処理の処理手順を示すフローチャートである。図16において、まず、出発地NSPは予め決められた地点に含まれるか否かが判断される(ステップS1101)。予め決められた地点に含まれるのであれば、出発地NSPから各巡回地点N1〜Nnへの最小コスト経路結果はデータ記憶部102(または202)に記録されているので、無処理でステップS1104に進む。一方、出発地NSPが予め決められた地点に含まれていなければ、ステップS1102およびS1103を行って、出発地NSPから選択された各巡回地点N1〜Nnへの最小コスト経路を求める。ステップS1102では、まず、出発地NSP、および選択された巡回地点N1〜Nnを含む領域の地図データがRAM(図示せず)上に読み込まれる。さらに、出発地NSPを探索開始点としてダイクストラ法を用い、出発地側探索処理(車両の進む方向に対して順方向に探索を広げる探索処理)が行われる(ステップS1102)。次に、選択された各巡回地点N1〜Nnから経路構成が行われた後、出発地NSPから当該各巡回地点N1〜Nnまでの最小コスト経路が求められる。そして、最小コスト経路としての地点間コストと経路データが地点間経路情報に追加される(ステップS1103)。その後、ステップS1104が行われる。
【0097】次に、目的地NDは予め決められた地点に含まれるか否かが判断される(ステップS1104)。予め決められた地点に含まれるのであれば、各巡回地点N1〜Nnから目的地NDへの最小コスト経路結果はデータ記憶部102(または202)に記録されているので、端地点追加処理は終了する。一方、目的地NDが予め決められた地点に含まれていなければ、ステップS1105およびS1106が行われ、選択された各巡回地点N1〜Nnから目的地NDへの最小コスト経路が求められる。ステップS1105では、まず、目的地ND、および選択された巡回地点N1〜Nnを含む領域の地図データがRAM上に読み込まれる。さらに、目的地NDを探索開始点としてダイクストラ法を用い、目的地側探索処理(車両の進む方向に対して逆方向に探索を広げる探索処理)を行う(ステップS1105)。次に、ステップS1106で、選択された各巡回地点N1〜Nnから経路構成が行われた後、選択された各巡回地点N1〜Nnから目的地NDまでの最小コスト経路が求められる。そして、最小コスト経路としての地点間コストと経路データとが地点間経路情報に追加される。以上で端地点追加処理(ステップS1004)が終了し、これによって、出発地NSP、目的地NDおよび各巡回地点N1〜Nnに含まれる2地点間の地点間情報が得られたことになる。
【0098】再度図15を参照する。ステップS1004(端地点追加処理)が終了すると、端地点(出発地NSPおよび目的地ND)と、各巡回地点N1〜Nnとの間の最小コスト経路が求められたかどうかが判定される(ステップS1005)。ステップS1005の判定は、ステップS1004の端地点追加処理において、RAMに読み込んだ地図データの範囲内で、出発地NSPから各巡回地点N1〜Nn、または各巡回地点N1〜Nnから目的地NDまでの経路が求められなかった場合のために行われる。ステップS1005で、経路が求められていたならば、ステップS1007に直接進み、巡回順序決定処理に進む。一方、ステップS1005で、経路が求められていなければ、出発地NSPの代わりに仮の出発地DNSP、または目的地NDの代わりに仮の目的地DNDを設定するための出入口地点選択処理が行われる。
【0099】図17は、出入口地点選択処理(ステップS1006)の詳細な処理手順を示すフローチャートである。図17において、まず、出発地NSPから各巡回地点N1〜Nnまでの経路が求められたか否かが判定される(ステップS1201)。ステップS1201で経路が求められていると判定されれば、無処理でステップS1205に進む。一方、ステップS1201で経路が求められていないと判定されれば、ステップS1202が行われる。ステップS1202では、出発地NSPを探索開始点として、一方向の階層別探索処理を広げる。つまり、ダイクストラ法等を使用して、最下位階層の地図データで出発地NSPから探索処理を広げて、一定の範囲が探索終了すれば、より粗い道路網で、より広い範囲を記録した1階層上の地図データを用いて探索を行う処理が最上位階層まで繰り返される。本探索処理中に、一階層の探索処理が終了した後で、出入口地点(例えば、図14のC1〜C3、S1)が探索終了状態になったか否かがチェックされた後に、接続コストが記録される。次に、出発地NSPから最小経路コストで到達可能な出入口地点が、仮の出発地DNSPと設定される(ステップS1203)。この時、観光区域αの境界上の地点(C1〜C3)が探索終了状態になっていれば、観光区域αから離れた主要道路上の地点(S1)よりも優先させてもよい。次に、出発地NSPから仮の出発地DNSPへの経路コストと経路データとが記録され(ステップS1204)、出発地側の処理が終了する。
【0100】次に、各巡回地点N1〜Nnから目的地NDまでの経路が求められたかどうかが判定される(ステップS1205)。ステップS1205で経路が求められていると判定されれば、出入口地点選択処理(ステップS1006)を終了する。一方、ステップS1205で経路が求められていないと判断されれば、ステップS1206が行われる。ステップS1206では、目的地NDを探索開始点として、上述した一方向の階層別探索処理を広げる。本探索処理中に、一階層の探索処理が終了した後で、出入口地点(例えば、図14のC1〜C3、S1)が探索終了状態になったかどうかがチェックされた後に、接続コストが記録される。次に、ステップS1207では、目的地NDまで最小経路コストで到達可能な出入口地点が、仮の目的地DNDと設定される。この時、観光区域αの境界上の地点(C1〜C3)が探索終了状態になっていれば、観光区域から離れた主要道路上の地点(S1)よりも優先させてもよい。次に、仮の目的地DNDから目的地NDへの経路コストと経路データとが記録され(ステップS1208)、目的地側の処理を終了する。以上で、図15のステップS1006(出入口地点選択処理)は終了する。
【0101】なお、以上の説明では、一方向探索の階層別探索方法を採用したが、観光区域αの境界上の地点(C1〜C3)が属する道路が記録されている地図の階層以上においては、観光区域αの境界上の地点(C1〜C3)の初期コストを0として逆方向の探索を実施し、双方向の階層別探索方法が採用されても良い。この場合には、観光区域αから離れた主要道路上の地点(S1)は、出入口地点として、予め決められた地点に含めなくとも良い。また、以上の説明では、出発地NSP(または目的地ND)からの最小経路コストで到達可能な出入口地点を自動的に仮の出発地DNSP(または仮の目的地DND)として採用したが、ユーザーにどのアクセス道路を選びたいか選択させても良い。
【0102】再度図15を参照する。ステップS1006が行われた後、各巡回地点N1〜Nnを巡回する順序を決定する巡回順序決定処理が行われる(ステップS1007)。ステップS1007の処理は、前述の図3のステップS304の処理と同様なので、詳細は省略する。ただし、ステップS1007では、ステップS1006の出入口地点選択処理で、仮の出発地DNSPまたは仮の目的地DNDが選択されていれば、これらは出発地NSPまたは目的地NDと同等に扱われる事とする。次に、ステップS1007で得られた最適な巡回順序に従って、ステップS1003、ステップS1004、ステップS1006で求められた経路データがつなぎ合わされ、出発地NSP(仮の出発地DNSPを含む)から目的地ND(仮の目的地DNDを含む)までの一本の巡回経路TRが構成される(ステップS1008)。最後に、求められた巡回経路TRをユーザーに提示したり、車両の移動に伴う現在位置を巡回経路上に表示し、進むべき方向を案内したりする(ステップS1009)。
【0103】以上のように、第2の巡回経路選出方法によれば、前提条件として、巡回地点N1〜Nnとして選択可能な地点が予め決定されている。さらに、これらの地点に関する地点間情報(地点間コストおよび経路データ)が予め求められている。これによって、各巡回地点間の経路を計算する必要がなくなる場合があり、最小の総巡回コストYminを有する巡回順序を選出するために必要な時間を短縮することができる。
【0104】また、第2の巡回経路選出方法によれば、任意の出発地NSPまたは目的地NDを探索開始点としてダイクストラ法を基本とした探索処理を行うことにより、出発地NSPから各巡回地点N1〜Nn、または各巡回地点N1〜Nnから目的地NDへの経路が1回の探索処理で求められる。これによって、任意の出発地NSPからの最小コスト巡回経路、または任意の目的地NDまでの最小コスト巡回経路の選出時間を短縮することができる。
【0105】また、第2の巡回経路選出方法によれば、巡回区域(図14における観光区域αに相当)へアクセスする道路上の地点が、出入口地点として予め決定されている。そして、上記予め決められた巡回用の地点と同様に、各出入口地点と各巡回地点N1〜Nnとして選択可能な地点との間、および各巡回地点N1〜Nnとして選択可能な地点と、各出入口地点との間の経路は、予め求められ経路情報として記録されている。そのため、巡回区域への入口地点を仮の出発地DNSP、または当該巡回区域からの出口地点を仮の目的地DNDとして選択することにより、仮の出発地DNSPからの巡回経路TR、または仮の目的地DNDまでの巡回経路TRを求めることができる。これによって、車載機のようにRAMの容量が少ない環境において、出発地NSPから各巡回地点N1〜Nnへの経路、または各巡回地点N1〜Nnから目的地NDまでの経路が求められない場合でも、選択された巡回地点N1〜Nnの巡回経路TRを求めることができる。
【0106】また、第2の巡回経路選出方法によれば、上記出入口地点として、上記巡回区域の境界を横切る主要道路上の複数の地点が選択される。これによって、最低限必要な出入口地点を機械的に簡単に設定することができるので、出入口地点の選択を簡略化することができ、さらに、探索処理を用いて自動的に適切な仮の出発地DNSP、または仮の目的地DNDを選択することができる。
【0107】また、第2の実施形態によれば、上記出入口地点として、上記巡回区域には含まれないが、その周辺を通過するより主要な道路上の地点が選択される。これによって、出発地NSPまたは目的地NDからの一方向の階層別探索方法で、当該出発地NSPまたは目的地NDへ最小コストで到達可能な出入口地点を選択することができる。その結果、巡回経路選出処理を簡略化でき、最適な巡回順序の選出までに必要な時間を短縮できる。
【0108】さらに、第2の実施形態によれば、上記仮の出発地DNSP、または仮の目的地DNDは、出入口地点の中からユーザーにより選択可能にされることにより、好きな方向から巡回区域に進入または脱出できるので、ユーザーの好みで巡回区域までの進入道路または巡回区域からの脱出道路を選択することができる。
【0109】(3)第3の巡回経路選出方法第3の巡回経路選出方法では、第1の実施形態におけるデータ記憶部102(図1)、および第2の実施形態におけるデータ記憶部202(図2)に、予め決められた地点間の最小コスト経路結果(地点間コストのみ)を追加記録しておく。予め決められた地点には、その地点周辺にアクセスするための主要道路上の地点も含むこととする。この主要道路上の地点を、以下、出入口地点と呼ぶ。第3の巡回経路選出方法と第2のそれとが異なる点は、予め決められた地点間の経路データが予め記録されていない点にある。その上で、巡回地点選出時に、予め決められた地点の中から巡回する地点が選択される。その後、データ記憶部102(または202)に記憶された各地点間の経路コストが読み出され、コストマトリクスが作成される。その後、第2の巡回経路選出方法と同様に、選択された巡回地点N1〜Nnを巡回する順序が決定される。以下、第3の巡回経路選出方法について説明する。
【0110】図18は、第3の巡回経路選出方法の処理手順を示すメインフローチャートである。図18のフローチャートは、第2の巡回経路選出方法を示すメインフローチャート(図15)とほぼ同一である。以下、異なる点について説明する。第3の巡回経路選出方法(図18R>8)と第2のそれ(図15)との相違点は、以下の2点である。第1の相違点は、図18のフローチャートでは、図15のステップS1003の代わりに、ステップS1303が実行されることである。第2の巡回経路選出方法では、図15のステップS1003において、選択した各巡回地点N1〜Nn間の経路コストと経路データとは、予め求められているため、RAM上に読み込まれてきた。しかし、第3の巡回経路選出手方法では、上記の通りデータ記憶部102(または202)には、予め定められた地点間の経路コストしか記録されていないので、図18のステップS1303において、選択した各巡回地点N1〜Nnに含まれる2地点間の経路コストのみがRAM上に読み込まれる。
【0111】第2の相違点は、図18のステップS1307(図15のステップS1007に相当)とステップS1309(図15のステップS1008に相当)の間に、ステップS1308の地点間経路選出処理が行われる事である。第3の巡回経路選出方法では、上記の通りデータ記憶部102(または202)には、各地点間の経路データが記録されていない。そのため、ステップS1307の巡回順序決定処理で各巡回地点N1〜Nnの巡回順序が決定された後、ステップS1309で出発地NSPから目的地NDまでの巡回経路TRをつなぎ合わせることができない。そこで、ステップS1308の地点間経路選出処理で、出発地NSPから最初の巡回地点Niまで、最初の巡回地点Niから2番目の巡回地点Nj、…、最後の巡回地点Nkから目的地NDまでの部分経路を、周知の2地点間探索方法を繰り返すことにより求める。
【0112】ここで、図19は、ステップS1308(地点間経路選出処理)の詳細な処理手順を示すフローチャートである。図19において、まず、出発地NSPが起点として選択される(ステップS1401)。次に、ステップS1307(図18)の巡回順序決定処理で決定された巡回順序に従って、起点の次の巡回地点Niを終点とする(ステップS1402)。ここで、ステップS1306(図18)の出入口地点選択処理で、仮の出発地DNSPまたは仮の目的地DNDが機械的に設定されている場合には、これらを終点として設定しない方が好ましい。ただし、仮の出発地DNSPおよび仮の目的地DNDがユーザー自身により設定された場合等には、これらを終点として設定する。
【0113】次に、ダイクストラ法に代表される従来の2地点間探索方法を用いて、起点から終点までの最小コスト経路が算出された後、経路データがRAM上に記録される(ステップS1403)。次に、終点は目的地NDかどうかが判定される(ステップS1404)。ステップS1404で目的地NDと判定されれば、出発地NSPから目的地NDまでの巡回経路TRの部分経路が全て求められたとして、地点間経路選出処理は終了する。一方、ステップS1404で目的地NDでないと判定されれば、ステップS1405が行われ、今回の終点が次回の起点として選択された上で、ステップS1402の処理に戻り、上記の処理を繰り返す。
【0114】以上の地点間経路選出処理で求められた部分経路データを、図18のステップS1309でつなぎ合わせることにより、各巡回地点N1〜Nnを通過して出発地NSPから目的地NDまでに至る巡回経路TRが構成される。
【0115】以上のように、第3の巡回経路選出方法によれば、巡回地点N1〜Nnとして選択可能な地点が予め決定されている。また、各選択可能な地点間の経路コストのみが予め記録されている。巡回経路TRの部分経路は2地点間探索処理を繰り返して求められる。これによって、第2の巡回経路選出方法のように、経路データが予め記録される必要がないので、データ記憶部102または202の記憶領域を有効利用することができる。
【0116】また、第3の巡回経路選出方法によれば、出入口地点選択処理(ステップS1306)で決定された仮の出発地DNSPまたは仮の目的地DNDを飛ばして、出発地NSPから目的地NDまでの巡回経路TRの部分経路が求められる。これによって、ユーザが真に立ち寄りたい巡回地点N1〜Nnに関する、最小の総巡回コストYminを有する巡回経路TRのみを選出することができる。これによって、自動的に選択された仮の出発地DNSPまたは仮の目的地DNDを不自然に通過する巡回経路TRの選出を防ぐことができる。
【0117】また、第3の巡回経路選出方法によれば、ユーザー自身が設定した仮の出発地DNSPまたは仮の目的地DNDを飛ばさずに、出発地NSPから目的地NDまでの巡回経路TRの部分経路が求められる。これによって、ユーザーが設定した仮の出発地DNSPまたは仮の目的地DNDを通過する巡回経路TRを選出することができる。その結果、ユーザーが意図したアクセス道路を必ず通って巡回区域に進入、または巡回区域から脱出する巡回経路TRを求めることができる。
【0118】(4)第4の巡回経路選出方法本巡回経路選出方法のメインフローチャートは、上記第1〜第3の巡回経路選出方法のメインフローチャート(図3、図15、図18)と同様とする。ここで、上記第1〜第3の巡回経路選出方法では、同一の巡回順序決定処理(図6)を用いていた。この巡回順序決定処理は、巡回すべき地点数が十数地点以上になると処理時間が増大し、実用的な時間で最適な巡回順序を求めることは難しいという問題点がある。そこで、この問題を解決するため、図6の巡回順序決定処理の代わりに、下記のような巡回順序決定処理を採用する。
【0119】図20は、第4の巡回経路選出方法に係る巡回順序決定処理を示すフローチャートである。図20において、選択された全ての巡回地点N1〜Nnが対象地点群として選択される(ステップS1501)。次に、多数の全巡回地点N1〜Nnを一定数以下のグループに分割する再帰グループ化処理が行われる(ステップS1502)。ここで、図21は、再帰グループ化処理の詳細な手順を示すフローチャートである。図21において、まず、対象地点群には、一定数以上の巡回地点N1〜Nnが含まれるか否かが判定される(ステップS1601)。この一定数の値は、使用する装置のハード性能に依存するものが、ここでは10個としておく。ただし、十分短時間で巡回経路が求められる時間であれば、上記一定数の値はいくつでもかまわない。ステップS1601で一定数未満と判断されたならば、グループ化する必要はないとして、再帰グループ化処理を終了する。
【0120】一方、ステップS1601で一定数以上と判断されたならば、ステップSS1602が実行される。ステップS1602では、まず、対象地点群の内、2地点間コストが最も小さい2個の巡回地点Niが選択される。選択された2地点は同一グループとしてまとめられる(ステップS1602)。次に、グループ数が一定数以上であるか否かが判定される(ステップS1603)。ここで、グループ化されていない巡回地点Nj(j≠i)については、1地点が1グループとして換算される。ここで、一定数の値は、ステップS1601での一定数の値と同一とし、10個を採用する。ステップS1603において、グループ数が一定数以上であれば、さらにグループ化する必要があると判断し、ステップS1602の処理に戻る。一方、ステップS1603において、グループ数が一定数未満であれば、これ以上グループ化を行う必要はないと判断し、ステップS1604に進む。以降のステップS1604〜S1608は、ステップS1602およびS1603で構成されたグループに対して、下記のような調査が行われる。
【0121】まず、未調査のグループの中の1つが調査対象として選択される(ステップS1604)。次に、調査対象のグループに含まれる巡回地点Niの数が一定数以上かどうかが判定される(ステップS1605)。ここで、一定数の値は、ステップS1601での一定数の値と同一とし、10個を採用する。ステップS1605で、巡回地点Niの数が一定数未満であれば、調査対象のグループをさらにグループ化する必要(つまり、下位層のグループを作成する必要)はないと判断され、無処理でステップS1608が行われる。
【0122】一方、ステップS1605で、地点数が一定数以上であれば、処理時間が増大するとみなして、さらに下層グループを作って、調査対象のグループを分割する必要があると判断され、ステップS1606およびS1607が行われる。まず、調査対象のグループに含まれる全ての巡回地点Niが処理対象として設定される(ステップS1606)。次に、処理対象となる巡回地点Niを下位層グループに分割するために、図21の再帰グループ化処理が再帰的に実行される。この再帰グループ化処理により、グループが階層的に構成されていく。再帰グループ化処理は、各下位層グループに含まれる巡回地点Nj(j⊂i)の数が一定数未満になるまで繰り返される。
【0123】次に、ステップS1608に進み、全グループがステップS1604において調査対象となったか否かが判定される(ステップS1608)。ステップS1608で、全グループの調査が終了していなければ、ステップS1604に戻り、次の調査対象グループを選択し、以降の処理を繰り返す。一方、ステップS1608で、全グループの調査が終了していれば、再帰グループ化処理が終了する。なお、本実施形態では、グループ化する際(ステップS1602)に2地点間コストが小さい地点同士からグループ化を行ったが、空間距離で近い地点同士からグループ化を行っても良い。また、別々のグループに属する2地点をグループ化した結果、大きなグループができる場合がある。このグループが他のグループよりもはるかに大きい場合には、グループ化を行わないようにしても良い。
【0124】ここで、上記再帰グループ化処理によりグループ分けされた地点の例を、図22に示す。図22において、巡回地点Nが17地点(白丸参照)あるが、図21の再帰グループ化処理により、8個のグループG1〜G8(網掛け部)が形成されている。また、出発地NSPを☆印、目的地NDを★印で表している。再度図20R>0を参照する。ステップS1502の再帰グループ化処理が終了すると、当該グループ分けした結果に従って、ステップS1503の階層的巡回順序決定処理が行われる。このステップS1503では、上位層のグループの巡回順序が決定された後、下位層のグループの巡回順序が決定されるという処理が繰り返し実行される。その結果、最終的には、近似的に最小の総巡回コストYminを有する巡回順序が求められる。以下、階層的巡回順序決定処理(ステップS1503)の詳細な手順を、図23R>3を参照して説明する。なお、この階層的巡回順序決定処理もまた再帰的な処理である。
【0125】最初の階層的巡回再帰処理が呼び出されると、まず、図23のステップS1801において、先頭の巡回地点Ntを含むグループが先頭巡回グループとして選択される。さらに、最終の巡回地点Neを含むグループが最終巡回グループとして選択される(ステップS1801)。ただし、最初の階層的巡回処理では、出発地NSPから最小経路コストで到達できる巡回地点を含むグループが先頭巡回グループとして、目的地NDへ最小経路コストで到達できる巡回地点を含むグループが最終巡回グループとして選択される。ステップS1801の次に、先頭巡回グループおよび最終巡回グループ以外のグループが未選択状態に設定される。さらに、未選択状態のグループについて、初期の管理情報(リスト構造)が作成される(ステップS1802)。今回作成される管理情報の説明は、第1の巡回経路選出方法で詳述したので割愛する。ただし、第1の巡回経路選出方法では巡回地点Niについて管理情報が作成されたが、最初の階層的巡回順序決定処理では、最上位層のグループGiについて管理情報が作成される点には注意を要する。つまり、最初の階層的巡回順序決定処理では、最上位のグループGiがひとまとまりになって巡回地点としてみなされる。
【0126】次に、先頭巡回グループが、前の巡回先PPとして選択される。さらに、最終巡回グループが、便宜上、目的地NDとして選択される(ステップS1803)。さらに、現在の巡回コストXが初期化される(ステップS1804)。次に、最上位層のグループGiを、同じグループを重複通過することなく、効率的に巡回する巡回経路TRを求めるために、巡回再帰処理が行われる。本巡回再帰処理の説明は、第1の巡回経路選出方法で詳述した巡回再帰処理(図8)と同様なので省略する。ただし、本巡回再帰処理においては、最上位のグループGiを第1の巡回経路選出方法で説明した巡回地点Niと同様に扱う。また、あるグループGaと他のグループGbとの間のグループ間コスト(第1の巡回経路選出方法における地点間コストに相当)は、あるグループGaに属するいずれかの巡回地点Naと、他のグループGbに属するいずれかの巡回地点Nbとの組合せの中で、地点間コストが最小コストであるものとする。この時、あるグループGa内で選択された巡回地点Nj(j∈a)が、当該グループGa内で最終の巡回地点Neとなる。また、他のグループGb内で選択された巡回地点Nk(k∈b)が、当該グループGb内での先頭の巡回地点となる。
【0127】以上、ステップS1801〜ステップS1805の処理で、最上位層のグループGiを最も効率的に巡回できる巡回順序を求めることができる。参考までに、この一連の処理で得られた最上位層のグループGiの巡回経路TRの一例を、図24に示す。図24において、まず、出発地NSPから、全ての最上位層のグループG1〜G8を通過し、目的地NDに至る巡回経路TRの概要(太い矢印の経路)を決定することができる。ステップS1806以降の処理では、各グループ内に含まれる巡回地点Niの最適な巡回順序が決定される。まず、未調査のグループGiの中の1つが、調査対象として選択される(ステップS1806)。次に、調査対象のグループGx(x∈i)の中に、2個以上の巡回地点Nx(x∈i)が含まれるか否かが判定される(ステップS1807)。ステップS1806で巡回地点Nxが1つであれば、無処理でステップS1810に進む。一方、ステップS1806で巡回地点Nxが2個以上含まれていれば、ステップS1808が行われる。
【0128】ステップS1808において、調査対象のグループGxに含まれる全ての巡回地点Nxが処理対象として選択される(ステップS1808)。次に、調査対象のグループGxに含まれる巡回地点Nxの最適な巡回順序を決定するために、図23の階層的巡回順序決定処理が再帰的に実行される(ステップS1809)。この階層的巡回順序決定処理が再帰されることにより、最終的には、全ての巡回地点Niが一本の巡回経路TRでつながることになる。次に、全てのグループGiを調査したかどうかが判定される(ステップS1810)。ステップS1810で、未調査のグループGiが存在すれば、ステップS1806に戻り、次のグループを調査対象とし、以上の処理が繰り返される。一方、ステップS1810で、全てのグループが調査済みであれば、階層的巡回順序決定処理は終了する。これによって、図20に示された巡回順序決定処理が終了する。参考までに、以上の処理により得られた巡回経路TRの一例を、図25R>5に示す。このように、各階層のグループ間経路を合成することにより、全ての巡回地点Niがつながった全体の巡回経路TRを求めることができる。
【0129】なお、第4の巡回経路選出方法では、上位階層のグループから下位層のグループへと処理を進めることにより巡回経路TRを求めていったが、下位階層のグループから上位層のグループへと処理を進めることにより巡回経路TRを求めるようにしても良い。つまり、下位層から各地点(グループ)が始点および終点となる最小経路コストの部分巡回経路が求められ記録される。部分巡回経路は、同じ階層に含まれる2地点(または2グループ)の全ての組み合わせについて記録される。そして、全体として最小経路コストとなる巡回経路TRが選出されればよい。
【0130】以上のように、第4の巡回経路選出方法によれば、近接する巡回地点Niが1グループにまとめられた上で、巡回経路が求められるので、調査対象となる組合せの数が減少するので、特に巡回地点Niの個数が多い場合には、巡回経路TRを選出するまでに要する時間を短縮することができる。また、第4の巡回経路選出方法では、2地点間の空間距離が近いものが優先的に1グループにまとめられるので、比較的簡単な処理で選出された巡回経路TRの品質を向上することができる。また、第4の巡回経路選出方法によれば、2地点間の距離(または旅行時間)に関する評価値(経路コストに相当)の小さいものが優先的に1グループにまとめられる。したがって、空間距離的には近くても、2地点間の道路が迂回しているような2個の巡回地点Niのグループ化を避けることができる。これによって、選出された巡回経路TRの品質を向上することができる。
【0131】また、第4の巡回経路選出方法によれば、グループ化された結果、他のグループと比較して非常に広範囲な一つのグループができあがる場合がある。そのグループ化が無効とされるので、各グループの大きさを平均化することができる。その結果、いびつな巡回経路TRの選出を防ぐことができる。これによって、選出された巡回経路TRの品質を向上することができる。また、第4の巡回経路選出方法によれば、最適な巡回順序が決定されるとき、上位層のグループから巡回順序を決定することにより、まず上位層で大まかな巡回順序が決定される。これによって、全体の計算量を削減することができるので、最適な巡回順序を選出するために必要な処理時間を短縮することができる。
【0132】(5)第5の巡回経路選出方法図1に示すカーナビゲーションシステムは車載されるという性質上、当該システム内のRAMの容量に制限があったり、プロセッサが非力だったりする。かかる事情から、処理負荷が軽く、かつ使用するRAMの容量が少ない巡回経路選出方法が要望されている。かかる要望は、以下の第5の巡回経路選出方法により実現される。
【0133】図26は、第5の巡回経路選出方法の処理手順を示すフローチャートである。図26のメインフローチャートに従う処理は、主として、図1のナビゲーション装置104により行われる。図26において、ユーザーは、前述と同様にして、出発地および目的地と、複数の巡回地点とを指定する(ステップS2601,S2602)。
【0134】次に、選択された出発地、目的地および複数の巡回地点に基づいて、地点間経路計算処理が行われる(ステップS2603)。地点間経路計算処理を概説すると、指定された出発地、目的地、複数の巡回地点から選択可能な2地点が選択され、選択された2地点間の最小コストと、最小コスト経路とが求められる。ここで、最小コストは、好ましくは、選択された2地点間を車両で移動する際の旅行時間の内、最小の値を意味する。また、最小コスト経路とは、旅行時間が最小となる経路を意味する。求められた最小コストは、最適な巡回経路を求める際の評価値として、コストマトリクスに記述される。
【0135】ここで、コストマトリクスは、図5を参照して既に説明したように、選択された2地点の内の起点から終点までの評価値(最小コスト)を、起点を行とし終点を列とする行列に記録したものである。図5には、出発地および目的地の他に、巡回地点数をn地点として場合の例が示されている。例えば、出発地を起点とし、巡回地点N1を終点とする際の最小コストは50分である。ここで注意を要するのは、目的地を起点とするコスト、出発地を終点とするコスト、および出発地から目的地へのコストは必要ないので、コストマトリクスには「−」マークが予め記述される。なお、上記コストは起点から終点へと到達するまでの評価値を表していれば良く、2地点間の移動距離または直線距離でも良いし、通過料金を考慮したものでもよい。
【0136】図27は、図26のステップS2603の詳細な処理手順を示すフローチャートである。図27において、まず、経路探索を開始する地図情報の階層が設定される(ステップS2701)。ここで、第5の巡回経路選出方法に係るデータ記憶部102には、階層構造を有する地図情報が記録されている。つまり、最下位層の地図情報は、最も大きな縮尺で表された詳細な地図をデータ化したものである。また、最階層の地図情報は、予め定められた範囲(例えば、約1.5km四方)を、細街路まで詳細に表す。かかる最階層の地図情報がいくつも集まって、広い範囲の地図を構成することとなる。そして、より上位階層の地図情報になるほど、より小さな縮尺の地図となり、より広い範囲を粗く表す(つまり、より主要な道路が記録される)地図となる。そのため、ステップS2701では、各2地点間の評価値を計算する際に、どの階層から計算するか決定する。通常は、最下位階層から計算することが望ましいが、処理に必要となるRAM容量や、処理負荷を削減するため、中間階層以上から探索を開始しても良い。また、出発地、目的地および各巡回地点が主要な道路上の地点であれば、当該主要な道路が記録されている階層から探索を開始しても良い。
【0137】ステップS2701の次に、設定された階層の地図情報を用いて探索処理が行われる(ステップS2702)。図28は、ステップS2702の詳細な処理手順を示すフローチャートである。まず、出発地、目的地および各巡回地点が探索開始点候補として設定される(ステップS2801)。次に、探索開始点候補の中から、未選択の地点がひとつ選択され、選択された地点が探索開始点として設定される。次に、設定された探索開始点およびその周辺の地図情報が、データ記憶部102からRAMへと読み込まれる(ステップS2803)。読み込まれる地図情報が表す範囲は、予め定められている。
【0138】ステップS2803の次に、探索開始点または後述する上位移行地点から、出発地側探索処理および目的地側探索処理が行われる(ステップS2804)。これらの探索手法としては、周知技術であるダイクストラ手法を用いることができる。ただし、探索開始点または上位移行地点から、出発地に対しては出発地側探索処理、当該探索開始点等から目的地に対しては目的地側探索処理のみでよい。各探索処理実行中には探索結果として、探索開始点から他の地点への到達コストと、当該2地点間での通過リンク(または、ひとつ前の通過ノード)の情報を記録しておく。次に、探索範囲の端点であり、上位階層に記録されている道路上の地点が上位移行地点として記録され、探索開始点から当該上位移行地点への到達コストが記録される。また、探索開始点から上位移行地点までの経路データを候補経路として記録する(ステップS2805)。なお、ステップS2805では、経路データの記録を行わない場合もあり得る。その場合は、後述のステップS2605(図26)において、ステップS2604で決定された巡回順序に従って、従来の2地点間探索を繰り返すことにより、経路データを作成する。
【0139】ステップS2805の次に、未選択の地点があるかどうかが判定され、あればステップS2802に戻り、次の探索開始点が選択された後、以降の処理が繰り返される。未選択の地点がなければ、階層内探索処理を終了する。
【0140】ここで、図27を再度参照する。ステップS2702が終了すると、現在設定されている階層において、2地点間経路が求められたかどうかを判定する接続判定処理が行われる(ステップS2703)。図29は、この接続判定処理の詳細な手順を示すフローチャートである。最初に、未接続の2地点間が判定対象候補として設定される(ステップS2901)。
【0141】次に、設定された判定対象候補のうち、未判定のものがひとつ選択され、判定対象として設定される(ステップS2902)。次に、上記階層内探索処理において、判定対象の2地点間経路が求められたかどうかが判断される(ステップS2903)。例えば、地点Aから地点Bへの2地点間経路が求められたかどうか判断するためには、地点Aからの出発地側探索結果と、地点Bからの目的地側探索結果とを参照し、共通する探索済み地点が存在するかどうか調査する。もし、共通する探索済み地点が存在すれば、地点A側から共通の探索済み地点への到達コストと、地点B側から当該探索済み地点への到達コストとを基に、地点Aから地点Bまでの総コストが計算され、総コストが最小となる地点を通過する経路が当該地点間の経路とみなされる。
【0142】もし、ステップS2903で、共通する探索済み地点が存在しなければ、2地点間経路が求められなかったものとして、無処理でステップS2906に進む。一方、ステップS2903で、共通する探索済み地点が存在すれば、当該ステップで求められた2地点間経路の総コストが、2地点間コストとしてコストマトリクスに記録される(ステップS2904)。
【0143】さらに、ステップS2903で求められた地点間経路の経路データが構成される(ステップS2905)。その際に、現在設定されている階層における探索経路の端点が、下位階層からの上位移行地点であれば、ステップS2805で記録された下位階層の候補経路データから該当するものを選択して端点に追加することで、地点Aから地点Bまでの全ての経路が構成され、その経路が地点間経路情報として記録される。なお、ステップS2905が行われない場合もあり得る。その場合は、後述のステップS2605(図26)において、ステップS2604で決定された巡回順序に従って、従来の2地点間探索を繰り返すことにより、経路データを作成する。当然ながら、ステップS2805(図28)での経路データの記録も必要ではなくなる。
【0144】次に、判定対象候補のうち、未判定の地点間が存在するかどうかが判断され(ステップS2906)、存在すればステップS2902に戻り、別の判定対象が選択された後、以降の処理が繰り返される。一方、ステップS2906で未判定の地点間が存在しなければ接続判定処理を終了する。
【0145】再度図27を参照する。ステップS2703が終了すると、必要な全地点間の経路(例えば、図5の数値が書かれている欄の起点・終点間の経路)が求められたかどうかが判断される(ステップS2704)。求められていない地点間の経路が存在すれば、探索対象の階層を上位階層へ移し(ステップS2705)、ステップS2702に戻って、当該階層において階層内探索処理から繰り返す。一方、ステップS2704で、必要な地点間の経路が全て求められていれば、地点間経路計算処理を終了する。以上で、コストマトリクスの空欄が埋められた事になる。
【0146】再度図26を参照する。ステップS2603の次に、巡回地点の巡回順序が決定される(ステップS2604)。カーナビゲーションシステムで巡回順序を決定する場合、巡回地点数は数地点程度(例えば、5地点)であるので、通常の深さ優先探索手法を用いれば良い。次に、決定された巡回順序に従って、出発地から目的地までの経路データが作成される(ステップS2605)。本実施形態では、図29のステップS2905において、各2地点間の経路データを記録しているので、ステップS2604で決定された巡回順序に従って、各2地点間の経路データを順次読み出してくればよい。
【0147】なお、図28のステップS2805での候補経路の経路データの記録、および/または、図29のステップS2906での地点間経路の経路情報の記録が行われていない場合には、ステップS2604で決定された巡回順序に従って、通常の2地点間探索処理を各区間分だけ繰り返す事により、経路データを作成することも可能である。ステップS2605の次に、求められた巡回経路をユーザーに提示したり、現在地の移動に伴い巡回経路上を誘導したりする。
【0148】以上説明した、図26の地点間経路計算処理(ステップS2603)により、各地点間の経路算出処理の負荷が次のように軽減される。例えば、巡回地点が3地点(N1、N2、N3)の場合、巡回地点同士の各2地点間の組合せは6通りである。この6通りの経路を2地点間探索を6回繰り返して探索すると図30から図35のようになる。ここで、図30〜図35は、2地点間探索の繰り返しで各地点間経路を求める処理の説明図である。本説明図においては、使用する地図情報は2階層と仮定している。この場合、下位階層の出発地側および目的地側探索回数は12回、上位階層の出発地側および目的地側探索回数は同じく12回となる。
【0149】それに対して、本実施形態に係る地点間経路計算処理では、図36のような処理となる。図36は、本実施形態で各地点間経路を求める処理の説明図である。本実施形態においては、図36に示すように、下位階層で各巡回地点から出発地側および目的地側探索処理を広げ、その後上位階層へ移行して続きの探索処理を続行する動きとなる。そのため、下位階層の出発地側および目的地側探索回数は6回、上位階層の出発地側および目的地側探索回数も同じく6回で済む。このように、比較的軽い負荷で各地点間経路を求めることができる。
【0150】ここで、上記実施形態では、データ記憶部102に記録されている地図情報は階層構造としたが、1階層でも良い。その場合、図27のステップS2701、ステップS2704およびステップS2705の処理は不要となるが、図28のステップS2804の探索処理は、各地点間経路が求められるように十分広い範囲で探索処理を実施する必要がある。なお、図28のステップS2804で実施される探索処理で使われる評価値と、コストマトリクスに記録される評価値は必ずしも同一である必要はない。例えば、得られた地点間経路を基に、コストマトリクスに記録する評価値を計算し直しても良い。
【0151】以上のように、本実施形態によれば、各地点間の最小評価値経路を求めた上で、経路上の評価値を2地点間評価値として採用することにより、実際に走行する道路を想定した評価値にすることができるので、違和感のない効率的な巡回経路を求めることができる。また、本実施形態によれば、各地点(出発地、目的地および各巡回地点)を探索開始点とし、少なくとも出発地側探索処理または目的地側探索処理のどちらか一方を全地点に対して行って、各地点間経路を求めることにより、探索処理回数を最小限に押さえることができるので、全地点間の経路を短時間で選出することができる。
【0152】また、本実施形態によれば、階層化された地図情報を使用し、下位階層において各地点を探索開始点とした探索処理を全地点に対して実施後、接続判断を行い、接続していない経路があれば上位階層に移行して関連する地点の探索処理を続行することにより、その階層に記録された道路網に適した探索範囲を設定することができるので、遠い地点であっても全地点間の経路を短時間で選出することができる。
【0153】また、本実施形態によれば、最後に必要な区間経路を探索し直す事により、各地点間の最小評価値経路を計算する際に経路データを残しておかなくても巡回経路を構成することができるので、車載機上で使用するRAM容量を削減することができる。また、本実施形態によれば、各地点間の最小評価値経路を計算する際に経路データを残しておくことにより、この経路データを参照することで巡回経路を構成することができるので、経路構成のために探索処理を実施しなくてすむため、巡回経路選出時間を短縮することができる。
【0154】また、上記第1〜第5の巡回経路選出方法の説明では、深さ優先探索方法を例に採り上げて、最適な巡回経路を求めるようにしていた。しかし、深さ優先探索方法だけでなく、シュミレーテッドアニーリング法(いわゆるSA法)、遺伝アルゴリズム(いわゆるGA法)またはニューラルネット法等、従来から知られている方法に、上記各巡回経路選出方法を適用しても良い。
【0155】なお、第1および第2の実施形態において、各機能ブロックは、ハードウェアによって構成されても良いし、マイクロコンピュータのマルチタスクなどのプログラム処理の結果として構成されても良い。また、本発明は、プログラムによって実現し、これをフロッピーディスク等の記録媒体に記録して移送することにより、独立した他のコンピュータ・システムで容易に実施することができる。この場合、記録媒体は、フロッピーディスクに限らず、光ディスク、ICカード、ROMカセット等、プログラムを記録できるものであれば、同様に実施することができる。
【図面の簡単な説明】
【図1】本発明の第1の実施形態に係るカーナビゲーションシステムの構成を示すブロック図である。
【図2】本発明の第2の実施形態に係る配送車両管理システムの構成を示すブロック図である。
【図3】第1の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図4】図3の地点間経路計算処理(ステップS303)の詳細な手順を示すフローチャートである。
【図5】コストマトリクスの一例を示している。
【図6】図3の巡回順序決定処理(ステップS304)の詳細な手順を示すフローチャートである。
【図7】リスト構造を有する管理情報の一例を示している。
【図8】図6の巡回再帰処理(ステップS604)の詳細な手順を示すフローチャートである。
【図9】巡回経路の3つの例を示している。
【図10】巡回地点N1〜N5が選択された場合に構成されるコストマトリクスを示している。
【図11】図8の巡回再帰処理の過程における管理情報の状態遷移を示している。
【図12】図8の巡回再帰処理の過程において算出される総巡回コストY1および巡回経路TR2について処理が打ち切られる様子を示している。
【図13】図8の巡回再帰処理の過程における管理情報の状態遷移を示している。
【図14】網掛けされた観光区域α内に、丸印で表された観光地点SPが予め決められた地点の一例として示されている。
【図15】第2の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図16】図15の端地点追加処理(ステップS1004)の詳細な手順を示すフローチャートである。
【図17】図15の出入口地点選択処理(ステップS1006)の詳細な手順を示すフローチャートである。
【図18】第3の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図19】図18の地点間経路選出処理(ステップS1308)の詳細な手順を示すフローチャートである。
【図20】第4の巡回経路選出方法に係る巡回順序決定処理の詳細な手順を示すフローチャートである。
【図21】図20の再帰グループ化処理(ステップS1502)の詳細な手順を示すフローチャートである。
【図22】図20の再帰グループ化処理によりグループ化された巡回地点Nの1例を示している。
【図23】図20の階層的巡回順序決定処理(ステップS1503)の詳細な手順を示すフローチャートである。
【図24】図23の階層的巡回順序決定処理により求められた最上位階層のグループ間の巡回経路の1例を示している。
【図25】図23の階層的巡回順序決定処理により求められた巡回経路の1例を示している。
【図26】第4の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図27】図26の地点間経路計算処理(ステップS2603)の詳細な手順を示すフローチャートである。
【図28】図27の階層内探索処理(ステップS2702)の詳細な手順を示すフローチャートである。
【図29】図27の接続判定処理(ステップS2703)の詳細な手順を示すフローチャートである。
【図30】2地点間探索の繰り返しにおいて、巡回地点N1→N2の経路を求める処理を説明するための図である。
【図31】2地点間探索の繰り返しにおいて、巡回地点N1→N3の経路を求める処理を説明するための図である。
【図32】2地点間探索の繰り返しにおいて、巡回地点N2→N3の経路を求める処理を説明するための図である。
【図33】2地点間探索の繰り返しにおいて、巡回地点N2→N1の経路を求める処理を説明するための図である。
【図34】2地点間探索の繰り返しにおいて、巡回地点N3→N1の経路を求める処理を説明するための図である。
【図35】2地点間探索の繰り返しにおいて、巡回地点N3→N2の経路を求める処理を説明するための図である。
【図36】第4の巡回経路選出方法で、巡回地点N1〜N3の2地点間の経路を求める処理を説明するための図である。
【図37】従来の巡回経路探索方法の処理手順を示すフローチャートである。
【図38】従来の他の巡回経路探索方法の処理手順を示すフローチャートである。
【符号の説明】
101 ロケーター
102 データ記憶部
103 操作部
104 ナビゲーション装置
105 情報提示部
201 無線装置
202 データ記憶部
203 操作部
204 コンピュータ
205 情報提示部

【特許請求の範囲】
【請求項1】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第3のステップは、現在調査対象となっている巡回順序の途中までの合計評価値(以下、第1の合計評価値と称す)を、前記第2のステップで得られた各評価値に基づいて計算する、第5のステップと、現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値(以下、第2の合計評価値と称す)を、前記第2のステップで得られた各評価値に基づいて計算する、第6のステップと、前記第6のステップで計算された第2の合計評価値の最小値を記録する第7のステップとを含み、前記第5のステップで計算された第1の合計評価値が、前記第7のステップで記録された第2の合計評価値の最小値を超えた場合、現在の調査が打ち切られる、巡回経路選出方法。
【請求項2】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を決定する第4のステップとを含み、前記第3のステップは、前記複数の巡回地点を管理するために、当該各巡回地点が連鎖的につなげられた管理情報を作成する第5のステップと、前記第5のステップで作成された管理情報に基づいて、巡回順序を構成していく第6のステップとを含む、巡回経路選出方法。
【請求項3】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第2のステップは、少なくとも、前記出発地または前記目的地と、各前記巡回地点とを含む範囲の地図データを読み込む第5のステップと、前記出発地または前記目的地と、各前記巡回地点とを探索開始点として順次設定する第6のステップと、前記第5のステップで読み込まれた地図データを利用して、前記第6のステップで設定された探索開始点と、当該探索開始点以外の地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各前記評価値を計算する第7のステップを含む、巡回経路選出方法。
【請求項4】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、当該各候補地点間の経路が求められており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに前記複数の候補地点の中から複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第2のステップは、前記第1のステップで選択された複数の巡回地点に含まれる各2地点間の各評価値を、予め記録されている経路情報の中から読み込むことにより得る、巡回経路選出方法。
【請求項5】 前記第2のステップは、前記出発地および/または前記目的地が、前記候補地点に含まれていない場合、当該出発地および/または当該目的地ならびに各巡回地点を含む範囲の地図データを読み込む第5のステップと、前記第1のステップで選択された出発地および目的地のいずれかを探索開始点として順次設定する第6のステップと、前記第5のステップで読み込まれた地図データを利用して、前記第6のステップで設定された探索開始点と、各前記巡回地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各前記評価値を得る第7のステップを含む、請求項4に記載の巡回経路選出方法。
【請求項6】 前記候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、当該出入口地点と当該各候補地点との間の経路が予め求められており、さらに、少なくとも当該出入口地点と各候補地点との間の経路の評価値を含む経路情報が予め記録されており、前記第2のステップは、前記出発地または前記目的地が、前記候補地点を含む区域外だった場合、前記出入口地点の中から、仮の出発地または仮の目的地を選択する、請求項4に記載の巡回経路選出方法。
【請求項7】 前記出入口地点には、前記候補地点が含まれる区域の境界を横切る主要な道路上の地点が予め選択されており、前記第2のステップは、前記出入口地点を探索開始点または探索終了点として、前記出発地または前記目的地に対して、双方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する、請求項6に記載の巡回経路選出方法。
【請求項8】 前記出入口地点には、前記候補地点が含まれる区域の境界を横切る主要な道路上の地点と、当該候補地点が含まれる区域の周辺を通過するより主要な道路上の地点とが予め選択されており、前記第2のステップは、前記出入口地点を探索終了点として、さらに前記第1のステップで選択された出発地または目的地を探索開始点として、一方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する、請求項6に記載の巡回経路選出方法。
【請求項9】 前記第2のステップは、ユーザーの選択に基づいて、前記出入口地点の中から、仮の出発地および/または仮の目的地を選択する、請求項6に記載の巡回経路選出方法。
【請求項10】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに前記複数の候補地点の中から、複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記第1のステップで選択された出発地から目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第4のステップは、前記第3のステップで決定された巡回順序に従って、前記第1のステップで選択された出発地から目的地までの部分的な経路を繰り返し求める第5のステップと、前記第5のステップで求められた部分的な経路をつなぎ合わせて、1本の巡回経路を構成する第6のステップとを含む、巡回経路選出方法。
【請求項11】 前記複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が記録されており、前記第2のステップは、前記第1のステップで選択された出発地または目的地が、前記候補地点を含む区域外だった場合、前記出入口地点の中から仮の出発地または仮の目的地を選択し、前記第5のステップは、前記第1のステップで選択された出発地から最初の巡回地点までの部分的な経路、または、最後の巡回地点から当該第1のステップで選択された目的地までの部分的な経路を求める時に、前記第2のステップで選択された仮の出発地または仮の目的地を省いて求める、請求項10に記載の巡回経路選出方法。
【請求項12】 前記複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点を含む区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が少なくとも記録されており、前記第2のステップは、前記第1のステップで選択された出発地または目的地が、前記候補地点を含む区域外だった場合、ユーザーの選択に基づいて、前記出入口地点の中から仮の出発地または仮の目的地を選択し、前記第5のステップは、前記第1のステップで選択された出発地から、前記第2のステップで選択された仮の出発地を経由して最初の巡回地点に至る部分的な経路、または、最後の巡回地点から、当該第2のステップで選択された仮の目的地を経由して当該第1のステップで選択された目的地に至る部分的な経路を求める、請求項10に記載の巡回経路選出方法。
【請求項13】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第3のステップは、前記複数の巡回地点の内、近接するもの同士を階層的なグループにまとめる第5のステップと、前記第5のステップでまとめられたグループの巡回順序を階層毎に決定し、最終的に、前記複数の巡回地点を巡回する順序を決定する第6のステップとを含む、巡回順序選出方法。
【請求項14】 前記第5のステップは、2地点間の空間距離に基づいて、前記複数の巡回地点をまとめる、請求項13に記載の巡回経路選出方法。
【請求項15】 前記第5のステップは、2地点間の経路距離に基づいて、前記複数の巡回地点をまとめる、請求項13に記載の巡回経路選出方法。
【請求項16】 前記第5のステップは、他のグループと比較して、過度に広範囲なグループを形成しない、請求項13記載の巡回経路選出方法。
【請求項17】 前記第6のステップは、階層的な各グループの内、上位階層のグループから巡回順序を決定する、請求項13記載の巡回経路選出方法。
【請求項18】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含む、巡回経路選出方法。
【請求項19】 前記第2のステップは、前記出発地と各前記巡回地点または前記目的地との間、前記複数の巡回地点に含まれる各2地点間、および当該各巡回地点と前記目的地との間の経路を求め、求めた各経路の評価値に基づいて、前記出発地と各前記巡回地点または前記目的地との間の評価値、前記複数の巡回地点に含まれる各2地点間の各評価値、および当該各巡回地点と前記目的地との間の評価値を取得する、請求項18に記載の巡回経路選出方法。
【請求項20】 前記第2のステップは、前記出発地、前記目的地および各前記巡回地点のそれぞれを探索開始点として、予め記憶される地図情報を用いて、出発地側探索処理および/または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各2地点間、および当該各巡回地点と当該目的地との間の経路を求め、求めた各経路の評価値に基づいて、前記出発地と各前記巡回地点または前記目的地との間の評価値、前記複数の巡回地点に含まれる各2地点間の各評価値、および当該各巡回地点と前記目的地との間の評価値を取得する、請求項18に記載の巡回経路選出方法。
【請求項21】 前記地図情報は階層構造を有しており、下位階層の地図情報は、相対的に狭い範囲を詳細に記録した地図を表しており、上位階層の地図情報は、相対的に広い範囲を粗く記録した地図を表しており、前記第2のステップは、使用すべき地図情報の階層を選択し、選択された階層の地図情報を用いて、前記出発地、前記目的地および各前記巡回地点のそれぞれを探索開始点として、出発地側探索処理および/または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各2地点間、および当該各巡回地点と当該目的地との間の経路を探索し、選択された階層の地図情報では、経路を求めることができない場合、上位階層の地図情報を用いて、当該経路を求める、請求項20に記載の巡回経路選出方法。
【請求項22】 前記第4のステップは、前記第3のステップで決定された巡回経路に従って、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点の組み合わせ数分だけ、2地点間探索を繰り返すことにより、1本の巡回経路を構成する、請求項19に記載の巡回経路選出方法。
【請求項23】 前記第2のステップはさらに、必要な2地点間毎に、最小の評価値を有する経路データを記録し、前記第4のステップは、前記第3のステップで決定された巡回経路に従って、前記第2のステップで記録された経路データに基づいて、1本の巡回経路を構成する、請求項19に記載の巡回経路選出方法。
【請求項24】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、出発地、目的地および複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記巡回順序決定部は、現在調査対象となっている巡回順序の途中までの合計評価値(以下、第1の合計評価値と称す)を、前記第2のステップで得られた各評価値に基づいて計算する、第1の合計評価値計算部と、現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値(以下、第2の合計評価値と称す)を、前記評価値取得部で得られた各評価値に基づいて計算する、第2の合計評価値計算部と、前記第2の合計評価値計算部で計算された第2の合計評価値の最小値を記録する最小値記録部とを含み、前記第1の合計評価値計算部は、現在計算中の第1の合計評価値が、前記記録部で記録された第2の合計評価値の最小値を超えた場合、当該第1の合計評価値の計算を打ち切る、巡回経路選出装置。
【請求項25】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、出発地、目的地および複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記巡回経路決定部は、前記複数の巡回地点を管理するために、当該各巡回地点が連鎖的につなげられた管理情報を作成して、作成した管理情報に基づいて、巡回順序を決定する、巡回経路選出装置。
【請求項26】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、出発地、目的地および複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記評価値取得部は、少なくとも、前記出発地または前記目的地と、各前記巡回地点とを含む範囲の地図データを読み込み、前記出発地または前記目的地と、各前記巡回地点とを探索開始点として順次設定し、読み込んだ地図データを利用して、設定した探索開始点と、当該探索開始点以外の地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各前記評価値を計算する、巡回経路選出装置。
【請求項27】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、当該各候補地点間の経路が求められており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報を記憶するデータ記憶部と、出発地および目的地、ならびに前記複数の候補地点の中から複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する巡回順序決定部と、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記評価値取得部は、前記地点選択部で選択された複数の巡回地点に含まれる各2地点間の各評価値を、前記データ記憶部に記録されている経路情報の中から読み込むことにより得る、巡回経路選出装置。
【請求項28】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報を記憶するデータ記憶部と、出発地および目的地、ならびに前記複数の候補地点の中から、複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記地点選択部で選択された出発地から目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記巡回経路構成部は、前記巡回順序決定部で決定された巡回順序に従って、前記地点選択部で選択された出発地から目的地までの部分的な経路を繰り返し求め、求めた部分的な経路をつなぎ合わせて、1本の巡回経路を構成する、巡回経路選出装置。
【請求項29】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、出発地、目的地および複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含み、前記巡回順序決定部は、前記複数の巡回地点の内、近接するもの同士を階層的なグループにまとめた後、当該グループの巡回順序を階層毎に決定し、最終的に、前記複数の巡回地点を巡回する順序を決定する、巡回順序選出装置。
【請求項30】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、出発地、目的地および複数の巡回地点を選択する地点選択部と、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する評価値取得部と、前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する巡回順序決定部と、前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する巡回経路構成部とを含む、巡回経路選出装置。
【請求項31】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第3のステップは、現在調査対象となっている巡回順序の途中までの合計評価値(以下、第1の合計評価値と称す)を、前記第2のステップで得られた各評価値に基づいて計算する、第5のステップと、現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値(以下、第2の合計評価値と称す)を、前記第2のステップで得られた各評価値に基づいて計算する、第6のステップと、前記第6のステップで計算された第2の合計評価値の最小値を記録する第7のステップとを含み、前記第5のステップで計算された第1の合計評価値が、前記第7のステップで記録された第2の合計評価値の最小値を超えた場合、現在の調査が打ち切られる、プログラムを記録した記録媒体。
【請求項32】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を決定する第4のステップとを含み、前記第3のステップは、前記複数の巡回地点を管理するために、当該各巡回地点が連鎖的につなげられた管理情報を作成する第5のステップと、前記第5のステップで作成された管理情報に基づいて、巡回順序を構成していく第6のステップとを含む、プログラムを記録した記録媒体。
【請求項33】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第2のステップは、少なくとも、前記出発地または前記目的地と、各前記巡回地点とを含む範囲の地図データを読み込む第5のステップと、前記出発地または前記目的地と、各前記巡回地点とを探索開始点として順次設定する第6のステップと、前記第5のステップで読み込まれた地図データを利用して、前記第6のステップで設定された探索開始点と、当該探索開始点以外の地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各前記評価値を計算する第7のステップを含む、プログラムを記録した記録媒体。
【請求項34】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、当該各候補地点間の経路が求められており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに前記複数の候補地点の中から複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第2のステップは、前記第1のステップで選択された複数の巡回地点に含まれる各2地点間の各評価値を、予め記録されている経路情報の中から読み込むことにより得る、プログラムを記録した記録媒体。
【請求項35】 選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、前記複数の巡回地点として選択可能な候補地点が予め決定されており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに前記複数の候補地点の中から、複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記第1のステップで選択された出発地から目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第4のステップは、前記第3のステップで決定された巡回順序に従って、前記第1のステップで選択された出発地から目的地までの部分的な経路を繰り返し求める第5のステップと、前記第5のステップで求められた部分的な経路をつなぎ合わせて、1本の巡回経路を構成する第6のステップとを含む、プログラムを記録した記録媒体。
【請求項36】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含み、前記第3のステップは、前記複数の巡回地点の内、近接するもの同士を階層的なグループにまとめる第5のステップと、前記第5のステップでまとめられたグループの巡回順序を階層毎に決定し、最終的に、前記複数の巡回地点を巡回する順序を決定する第6のステップとを含む、プログラムを記録した記録媒体。
【請求項37】 複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、出発地、目的地および複数の巡回地点を選択する第1のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な2地点間のうち、必要な2地点間の評価値を取得する第2のステップと、前記第2のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第3のステップと、前記第3のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る1本の巡回経路を構成する第4のステップとを含む、プログラムを記録した記録媒体。

【図1】
image rotate


【図2】
image rotate


【図3】
image rotate


【図6】
image rotate


【図7】
image rotate


【図4】
image rotate


【図5】
image rotate


【図8】
image rotate


【図9】
image rotate


【図13】
image rotate


【図10】
image rotate


【図11】
image rotate


【図12】
image rotate


【図14】
image rotate


【図15】
image rotate


【図16】
image rotate


【図17】
image rotate


【図18】
image rotate


【図19】
image rotate


【図20】
image rotate


【図21】
image rotate


【図22】
image rotate


【図31】
image rotate


【図23】
image rotate


【図24】
image rotate


【図25】
image rotate


【図26】
image rotate


【図27】
image rotate


【図30】
image rotate


【図28】
image rotate


【図29】
image rotate


【図32】
image rotate


【図33】
image rotate


【図34】
image rotate


【図35】
image rotate


【図36】
image rotate


【図37】
image rotate


【図38】
image rotate


【公開番号】特開2001−91284(P2001−91284A)
【公開日】平成13年4月6日(2001.4.6)
【国際特許分類】
【出願番号】特願2000−41238(P2000−41238)
【出願日】平成12年2月18日(2000.2.18)
【出願人】(000005821)松下電器産業株式会社 (73,050)