(57)【特許請求の範囲】
【請求項１】
複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、
出発地、目的地および複数の巡回地点を選択する第１のステップと、
前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、
前記第２のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、
前記第３のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、
前記第３のステップは、
現在調査対象となっている巡回順序の途中までの合計評価値（以下、第１の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第５のステップと、
現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値（以下、第２の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第６のステップと、
前記第６のステップで計算された第２の合計評価値の最小値を記録する第７のステップとを含み、
前記第５のステップで計算された第１の合計評価値が、前記第７のステップで記録された第２の合計評価値の最小値を超えた場合、前記巡回経路に関してはそこから派生するそれ以降の調査処理が打ち切られる、巡回経路選出方法。
【請求項２】
複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための装置であって、
出発地、目的地および複数の巡回地点を選択する地点選択部と、
前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する評価値取得部と、
前記評価値取得部で得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する巡回順序決定部と、
前記巡回順序決定部で決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する巡回経路構成部とを含み、
前記巡回順序決定部は、
現在調査対象となっている巡回順序の途中までの合計評価値（以下、第１の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第１の合計評価値計算部と、
現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値（以下、第２の合計評価値と称す）を、前記評価値取得部で得られた各評価値に基づいて計算する、第２の合計評価値計算部と、
前記第２の合計評価値計算部で計算された第２の合計評価値の最小値を記録する最小値記録部とを含み、
前記第１の合計評価値計算部は、現在計算中の第１の合計評価値が、前記記録部で記録された第２の合計評価値の最小値を超えた場合、前記巡回経路に関してはそこから派生するそれ以降の調査処理を打ち切る、巡回経路選出装置。
【請求項３】
複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための環境をコンピュータ装置上で実現するためのプログラムを記録した記録媒体であって、
出発地、目的地および複数の巡回地点を選択する第１のステップと、
前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、
前記第２のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、
前記第３のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、
前記第３のステップは、
現在調査対象となっている巡回順序の途中までの合計評価値（以下、第１の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第５のステップと、
現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値（以下、第２の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第６のステップと、
前記第６のステップで計算された第２の合計評価値の最小値を記録する第７のステップとを含み、
前記第５のステップで計算された第１の合計評価値が、前記第７のステップで記録された第２の合計評価値の最小値を超えた場合、前記巡回経路に関してはそこから派生するそれ以降の調査処理が打ち切られる、プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、巡回経路選出方法に関し、より特定的には、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法に関する。
【０００２】
【従来の技術】
周知のごとく、近年、交通管制技術やＩＴＳ関連技術への社会的関心が高まっている。かかる社会的関心により、目的地までの実用的な経路を自動的に選出する経路探索方法が盛んに研究開発され、既にいろいろな分野で応用されている。その応用例には、車載カーナビゲーションシステム、またはＡＴＩＳ等の交通情報提供システムのセンター側装置がある。これらは、「特開平４−２０４８８１号」公報に開示された技術等を使って、ある地点（出発地）から別の地点（目的地）への最適経路を求めている。
【０００３】
また、配送管理システム等への応用のため、選択された複数の地点を全て通過する最適経路を求める巡回経路探索技術への要望も高まっている。巡回経路探索技術は、数学的には「巡回セールスマン問題」と呼ばれており、古くから計算量の多い計算困難な問題として知られている。巡回セールスマン問題の完全解を求める方法は確立されておらず、実用的な近似解を求める方法が存在するだけである。近似解を求める方法は、「特開平３−１９１４６４号」公報、および「特開平４−５７１４７号」公報に開示されている。
「特開平３−１９１４６４号」公報は、各地点の重心からの角度順により初期経路を構成して、一定地点数の範囲で最適化を繰り返す方法を開示している。また、「特開平４−５７１４７号」公報は、順次増加コストの一番小さい地点を追加して初期経路を構成し、地点の並べ替えを行って最適化する方法を開示している。
【０００４】
まず、「特開平３−１９１４６４号」公報に開示された従来の巡回経路探索方法（以下、第１の巡回経路探索方法と称す）の概略を説明する。第１の巡回経路探索方法では、まず、選択された各地点の重心と、各地点とがなす角度を求めた後に、求められた各角度に基づいて初期経路が構成される。次に、構成された初期経路が一定地点数毎に分割される。次に、分割された領域毎に「深さ優先探索方法」が適用され、当該領域に含まれる地点が、より短い経路を構成するように並び替えられる。これによって、第１の巡回経路探索方法は、選択された各地点の最短コスト経路を求めている。さらに、分割した領域間で、それぞれに含まれる地点が交換された後に、上記の一連の処理が繰り返される。最終的に、コストが小さくならなくなれば、第１の巡回経路探索方法の処理は終了する。以下、第１の巡回経路探索方法の詳細を、図３７のフローチャートを参照して説明する。特に、図３７（ａ）は、第１の巡回経路探索方法の処理手順を示すメインフローチャートである。
【０００５】
図３７（ａ）において、設定された地点群の中心座標が決定された後（ステップＳ３７ａ１）、中心座標と各地点座標とを結んだ角度順に、各地点がつながれ（ステップＳ３７ａ２）、これによって、巡回順序の初期経路が構成される。次に、初期経路を基に、最適化ループ処理が行われ（ステップＳ３７ａ３）、最小コスト経路に近づける補正処理が行われる。ここで、図３７（ｂ）は、図３７（ａ）のステップＳ３７ａ３またはＳ３７ａ６の詳細な処理手順を示すサブフローチャートである。
図３７（ｂ）において、分割のためのスタート地点が決められ（ステップＳ３７ｂ１）、設定された地点群が、初期経路の順序に従いつつ、決定されたスタート地点を基準として一定地点数毎の領域に分割される。次に、分割された領域毎に、総当たり方法によって最小コスト経路が求められる（ステップＳ３７ｂ２）。次に、各分割領域を合成して、１周の経路（巡回経路）が構成される（ステップＳ３７ｂ３）。最後に、ステップＳ３７ｂ３で得られた巡回経路コストが、前回のものより小さくなっていれば（ステップＳ３７ｂ４）、巡回経路コストがより小さくなる可能性があるとして、ステップＳ３７ｂ１に戻る。そして、次回は、ステップＳ３７ｂ３で得られた巡回経路コストを基に、ステップＳ３７ｂ１〜Ｓ３７ｂ４の処理が繰り返される。
一方、ステップＳ３７ｂ４で、今回得られた巡回経路コストが、前回のものよりも小さくなっていなければ、ほぼ最小コストの巡回経路となったと判断する。そして、前回の巡回経路が最適のものとして、最適化ループ処理（ステップＳ３７ａ３）が終了する。
【０００６】
次に、図３７（ａ）に戻り、各地点や各辺が交換された後、効率順にｍ組のつなぎ替え方が調べられる（ステップＳ３７ａ４）。次に、１番目（ｍ＝１）のつなぎ替えが行われる（ステップＳ３７ａ５）。さらに、ステップＳ３７ａ３と同様の最適化ループ処理が行われる（ステップＳ３７ａ６）。次に、ステップＳ３７ａ６で得られた巡回経路のコストが今までで最小であるかが判断され（ステップＳ３７ａ７）、最小であれば、巡回経路コストがより小さくなる可能性があるとして、ステップＳ３７ａ６で得られた巡回経路コストを基準として、ステップＳ３７ａ４〜Ｓ３７ａ７の処理が繰り返される。
一方、ステップＳ３７ａ７で、ステップＳ３７ａ６で得られた巡回経路のコストが今までで最小でなければ、ステップＳ３７ａ８が行われる。次に、ｍ組全てについて巡回経路のコストが確認したかが判断され（ステップＳ３７ａ８）、確認済みであれば、第１の巡回経路探索方法が終了する。
一方、ステップＳ３７ａ８で、ｍ組全てについて確認が終わっていなければ、今回選択された巡回経路（つまり、つなぎ替えが行われた後の巡回経路）は最小コストにならないことから、巡回経路は、つなぎ替えが行われる前のものに戻される（ステップＳ３７ａ９）。さらに、次の組合せ（ｍ＝ｍ＋１）のつなぎ替えが行われた後（ステップＳ３７ａ１０）、ステップＳ３７ａ６が再度実行され、Ｓ３７ａ６〜Ｓ３７ａ７の処理が繰り返される。
【０００７】
次に、「特開平４−５７１４７号」公報に開示された従来の巡回経路探索方法（以下、第２の巡回経路探索方法と称す）の概略を説明する。第２の巡回経路探索方法では、まず、巡回する地点群の中から、コストの小さい三角形を構成する地点を順次追加して初期経路が構成される。その後、ランダムに地点を切り離して、巡回経路の再構成を行う処理が繰り返され、これによって、最小のコストを有する巡回経路が探索される。以下、第２の巡回経路探索方法の詳細を、図３８のフローチャートを参照して説明する。
図３８において、地点データが入力されると、入力された各地点間の距離を記録した行列が作成される（ステップＳ３８０１）。次に、入力された地点群の中から３地点が選択された後に、選択された３地点を用いて、最初の３角形が作成される（ステップＳ３８０２）。次に、未選択の地点群から最適三角形を構成する１地点が選択され、選択された地点を巡回経路に加える処理が行われる。この処理は、未選択の地点群が無くなるまで繰り返され、これによって、巡回経路が構成される（ステップＳ３８０３）。次に、構成された巡回経路の全距離が計算され、今回算出された全距離が、今までに求められた巡回経路の中で最短か否かが判断される。全距離が最短であれば、今回の巡回経路が最適なものとして採用される（ステップＳ３８０４）。次に、処理回数・時間により処理を打ちきるか否かが判断される（ステップＳ３８０５）。所定処理回数・所定時間を超えていれば処理が終了し、所定処理回数・所定時間を超えていなければステップＳ３８０６が行われる。構成された巡回経路から、ランダムに地点が切り離され、地点が未選択の状態に戻された後（ステップＳ３８０６）、ステップＳ３８０３の処理に戻り、以降の処理が繰り返される。
【０００８】
また、上記方法とは別に、遺伝アルゴリズムやニューラルネットを応用した各種方法も学会等で報告されている。
【０００９】
【発明が解決しようとする課題】
しかしながら、後者の遺伝アルゴリズムやニューラルネットを応用した方式では、極小解に陥る可能性があり、最悪の場合を考えると経路品質面で問題がある。
また、第１の巡回経路探索方法は、巡回経路のコストが最小かどうかに基づいて、巡回経路の修正を続けるかどうか判断している。そのため、巡回経路のコストが極小解に陥る可能性があり、最適な巡回経路を求めることができない場合が生じる。さらに、巡回経路のコストが最終的に収束するまでの処理時間が長くなる可能性がある。
【００１０】
さらに、第２の巡回経路探索方法は、ランダムに地点を切り離して再構成する処理を、回数・時間等で制限し打ちきっているため、最終的に巡回経路コスト（距離）がどこまで最適なものに収束するかは一定しないという問題点があった。
【００１１】
それ故に、本発明の目的は、実用時間でより実用的な巡回経路を選出することができる巡回経路選出方法を提供することである。
【００１２】
【課題を解決するための手段および発明の効果】
第１の発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、前記第２のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、前記第３のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、前記第３のステップは、現在調査対象となっている巡回順序の途中までの合計評価値（以下、第１の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第５のステップと、現在調査対象となっている巡回順序が一通り構成されると、構成された巡回順序の合計評価値（以下、第２の合計評価値と称す）を、前記第２のステップで得られた各評価値に基づいて計算する、第６のステップと、前記第６のステップで計算された第２の合計評価値の最小値を記録する第７のステップとを含み、前記第５のステップで計算された第１の合計評価値が、前記第７のステップで記録された第２の合計評価値の最小値を超えた場合、前記巡回経路に関してはそこから派生するそれ以降の調査処理が打ち切られる。
【００１３】
第１の発明によれば、巡回する順序を決定する処理において、深さ優先探索方法に基づく巡回経路の調査処理中に、第１の合計評価値が、第２の合計評価値の最小値（つまり、過去最小であった第２の合計評価値）を超えた場合、その巡回経路に関しては、そこから派生するそれ以降の調査処理が打ち切られる。これによって、最適な巡回経路となり得ない巡回地点の組合せに関する調査を省略することができるので、最適な巡回経路の選出時間を短縮する事ができる。
【００１４】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、
出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第３のステップと、第３のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を決定する第４のステップとを含み、第３のステップは、複数の巡回地点を管理するために、当該各巡回地点が連鎖的につなげられた管理情報を作成する第５のステップと、第５のステップで作成された管理情報に基づいて、巡回順序を構成していく第６のステップとを含む。
【００１５】
本発明によれば、巡回する順序を決定する処理において、調査対象としての未選択の巡回地点が連鎖的につながっている管理情報が適用される。これによって、未選択の巡回地点を効率的に選出できるので、最小コスト巡回経路の選出時間を短縮することができる。
【００１６】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、
出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第３のステップと、第３のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、第２のステップは、少なくとも、出発地または目的地と、各巡回地点とを含む範囲の地図データを読み込む第５のステップと、出発地または目的地と、各巡回地点とを探索開始点として順次設定する第６のステップと、第５のステップで読み込まれた地図データを利用して、第６のステップで設定された探索開始点と、当該探索開始点以外の地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各評価値を計算する第７のステップを含む。
【００１７】
本発明によれば、各地点間の評価値を求める処理において、当該各地点を探索開始地点として順に選択し、ダイクストラ法に基づく単方向探索処理が行われる。これによって、ｍ個の地点に含まれる各２地点間の探索処理をｍ×（ｍ−１）回からｍ回に削減することができるので、最適な巡回経路の選出時間を削減することができる。
【００１８】
本発明は、選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、複数の巡回地点として選択可能な候補地点が予め決定されており、当該各候補地点間の経路が求められており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに複数の候補地点の中から複数の巡回地点を選択する第１のステップと、出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第３のステップと、第３のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、第２のステップは、第１のステップで選択された複数の巡回地点に含まれる各２地点間の各評価値を、予め記録されている経路情報の中から読み込むことにより得る。
【００１９】
本発明によれば、予め巡回地点として選択可能な地点を決定し、各地点間経路を求めておいて経路情報を記録しておくことにより、各巡回地点間の経路を計算する必要がないので、最適な巡回経路の選出時間を短縮することができる。
【００２０】
本発明の第２のステップは、出発地および／または目的地が、候補地点に含まれていない場合、当該出発地および／または当該目的地ならびに各巡回地点を含む範囲の地図データを読み込む第５のステップと、第１のステップで選択された出発地および目的地を探索開始点として順次設定する第６のステップと、第５のステップで読み込まれた地図データを利用して、第６のステップで設定された探索開始点と、各巡回地点との間の経路を、ダイクストラ法を基本とした手法により導出して、各評価値を得る第７のステップを含む。
【００２１】
本発明によれば、任意の出発地または目的地を探索開始点として、ダイクストラ法に基づく探索処理が行われる。これによって、出発地から各巡回地点、または各巡回地点から目的地への経路が１回の探索処理で求められるので、任意の出発地からの最適な巡回経路、または任意の目的地への最適な巡回経路の選出時間を短縮することができる。
【００２２】
本発明は、候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、当該出入口地点と当該各候補地点との間の経路が予め求められており、さらに、少なくとも当該出入口地点と各候補地点との間の経路の評価値を含む経路情報が予め記録されており、第２のステップは、出発地または目的地が、候補地点を含む区域外だった場合、出入口地点の中から、仮の出発地または仮の目的地を選択する。
【００２３】
本発明によれば、巡回区域へアクセス可能な道路上の地点が、予め出入口地点として決定されている。また、各出入口地点と各巡回地点（候補地点）との間、および各巡回地点（候補地点）と各出入口地点との間の経路もまた予め求められている。これらは、経路情報として予め記録されている。そして、巡回区域への入口地点を仮の出発地、または巡回区域からの出口地点を仮の目的地として選択することにより、仮の出発地からの巡回経路、または仮の目的地までの巡回経路を求めることができる。これによって、例えば、車載機のようにＲＡＭ容量が少ない環境において、出発地から各巡回地点への経路または各巡回地点から目的地までの経路が求められなかった場合でも、選択された地点を巡回する巡回経路を求めることができる。
【００２４】
本発明は、出入口地点には、候補地点が含まれる区域の境界を横切る主要な道路上の地点が予め選択されており、第２のステップは、出入口地点を探索開始点または探索終了点として、出発地または目的地に対して、双方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する。
本発明によれば、上記出入口地点として、上記巡回区域の境界を横切る主要な道路上の地点を選択することにより、最低限必要な出入口地点を機械的に設定することができる。これによって、出入口地点の選択を簡略化することができ、さらに、探索処理を用いて自動的に適切な仮の出発地、または仮の目的地を選択することができる。
【００２５】
本発明は、出入口地点には、候補地点が含まれる区域の境界を横切る主要な道路上の地点と、当該候補地点が含まれる区域の周辺を通過するより主要な道路上の地点とが予め選択されており、第２のステップは、出入口地点を探索終了点として、さらに第１のステップで選択された出発地または目的地を探索開始点として、一方向の階層別探索処理を行うことにより、仮の出発地または仮の目的地を選択する。
【００２６】
本発明によれば、上記出入口地点として、上記巡回区域には含まれないが、周辺を通過するより主要な道路上の地点が選択される。これによって、出発地または目的地からの一方向の階層別探索方法で最小コストで到達する出入口地点を選択できるので、巡回経路選出処理を簡略化でき、選出時間を短縮できる。
【００２７】
本発明の第２のステップは、ユーザーの選択に基づいて、出入口地点の中から、仮の出発地および／または仮の目的地を選択する。
【００２８】
本発明によれば、上記仮の出発地、または仮の目的地は、出入口地点の中から、ユーザーにより選択される。これによって、ユーザーが好きな方向から巡回区域に進入または脱出できるので、ユーザーの好みで巡回区域までの進入道路または巡回区域からの脱出道路を選択することができる。
【００２９】
本発明は、選択された複数の巡回地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、複数の巡回地点として選択可能な候補地点が予め決定されており、さらに、少なくとも当該各候補地点間の評価値を含む経路情報が記録されており、出発地および目的地、ならびに複数の候補地点の中から、複数の巡回地点を選択する第１のステップと、出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第３のステップと、第３のステップで決定された巡回順序に従って、第１のステップで選択された出発地から目的地へ至る１本の巡回経路を構成する第４のステップとを含み、第４のステップは、第３のステップで決定された巡回順序に従って、第１のステップで選択された出発地から目的地までの部分的な経路を繰り返し求める第５のステップと、第５のステップで求められた部分的な経路をつなぎ合わせて、１本の巡回経路を構成する第６のステップとを含む。
【００３０】
本発明によれば、予め巡回地点として選択可能な地点（候補地点）が予め決定されている。また、各地点間経路に基づいて得られた地点間経路コストのみが予め記録されている。この状態で、巡回経路の部分経路を２地点間探索処理を繰り返して求めることにより、経路データを記録する必要がないので、記憶領域に記憶されるデータ量を削減することができる。
【００３１】
本発明は、複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点が含まれる区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が記録されており、第２のステップは、第１のステップで選択された出発地または目的地が、候補地点を含む区域外だった場合、出入口地点の中から仮の出発地または仮の目的地を選択し、第５のステップは、第１のステップで選択された出発地から最初の巡回地点までの部分的な経路、または、最後の巡回地点から当該第１のステップで選択された目的地までの部分的な経路を求める時に、第２のステップで選択された仮の出発地または仮の目的地を省いて求める。
【００３２】
本発明によれば、第２のステップで選択された仮の出発地または仮の目的地を飛ばして、出発地から目的地までの巡回経路の部分経路が求められる。これによって、ユーザーが真に立ち寄りたい巡回地点から最適な巡回経路が選出されるので、自動的に選択された仮の出発地または仮の目的地を不自然に通過する巡回経路の選出を防ぐことができる。
【００３３】
本発明は、複数の巡回地点として選択可能な候補地点が予め決定されており、当該候補地点を含む区域にアクセスする複数の道路上の地点が出入口地点として予め決定されており、さらに、少なくとも、当該各候補地点間の評価値、および当該出入口地点と各候補地点との間の評価値を含む経路情報が記録されており、第２のステップは、第１のステップで選択された出発地または目的地が、候補地点を含む区域外だった場合、ユーザーの選択に基づいて、出入口地点の中から仮の出発地または仮の目的地を選択し、第５のステップは、第１のステップで選択された出発地から、第２のステップで選択された仮の出発地を経由して最初の巡回地点に至る部分的な経路、または、最後の巡回地点から、当該第２のステップで選択された仮の目的地を経由して当該第１のステップで選択された目的地に至る部分的な経路を求める。
【００３４】
本発明によれば、ユーザー自身が設定した仮の出発地または仮の目的地は飛ばさずに、出発地から目的地までの巡回経路の部分経路が求められる。これによって、ユーザーが設定した仮の出発地または仮の目的地を通過する巡回経路が選出されるので、必ずユーザーが意図したアクセス道路を通って巡回区域に進入、または巡回区域から脱出する巡回経路を求めることができる。
【００３５】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、  出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を決定する第３のステップと、第３のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、第３のステップは、複数の巡回地点の内、近接するもの同士を階層的なグループにまとめる第５のステップと、    第５のステップでまとめられたグループの巡回順序を階層毎に決定し、最終的に、複数の巡回地点を巡回する順序を決定する第６のステップとを含む。
【００３６】
本発明によれば、近隣の巡回地点が階層的にグループ化される。階層的なグループに基づいて巡回経路が求められる。これによって、調査対象となる組合せの数が減少するので、特に巡回対象となる地点数が多い場合に、巡回経路選出時間を短縮することができる。
【００３７】
本発明の第５のステップは、２地点間の空間距離に基づいて、複数の巡回地点をまとめる。第１４の発明によれば、２地点間の空間距離が近いものから優先的に１グループにまとめることができる。これによって、近接する巡回地点をグループ化できるので、比較的簡単な処理で経路品質を向上することができる。
【００３８】
本発明の第５のステップは、２地点間の経路距離に基づいて、複数の巡回地点をまとめる。第１５の発明によれば、２地点間の経路の距離が近いものから優先的に１グループにまとめることができる。これによって、空間距離的には近くても２地点間の道路は迂回しているような巡回地点がグループ化されることを避けることができるので、より経路品質を向上することができる。
【００３９】
本発明の第５のステップは、他のグループと比較して、過度に広範囲なグループを形成しない。第１６の発明によれば、他のグループと比較して広い範囲がグループが形成されない。これによって、各グループの大きさを平均化でき、いびつな巡回経路の選出を防ぐことができるので、より経路品質を向上することができる。
【００４０】
本発明の第６のステップは、階層的な各グループの内、上位階層のグループから巡回順序を決定する。第１７の発明によれば、階層化されたグループにおいて、上位階層のグループから巡回順序を決定することにより、まず上位階層で大まかな巡回順序を決定し、全体の計算量を削減することができる。これによって、最適な巡回経路の選出時間を短縮することができる。
【００４１】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、  出発地、目的地および各巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、第２のステップで得られた各評価値を利用して、複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、第３のステップで決定された巡回順序に従って、出発地、複数の巡回地点および目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含む。
【００４２】
本発明によれば、第２のステップで得られる評価値は、各２地点間に対するものである。したがって、かかる評価値を基に決定される巡回順序は、実際に車両が走行する道路を想定したものとなる。これによって、ユーザーにとって違和感のない効率的な巡回順序を求めることができる。
【００４３】
本発明の第２のステップは、出発地と各巡回地点または目的地との間、複数の巡回地点に含まれる各２地点間、および当該各巡回地点と目的地との間の経路を求め、求めた各経路の評価値に基づいて、出発地と各巡回地点または目的地との間の評価値、複数の巡回地点に含まれる各２地点間の各評価値、および当該各巡回地点と目的地との間の評価値を取得する。
【００４４】
本発明によれば、第２のステップでは、評価値が、各２地点間の経路を実際に求めることにより得られる。そのため、より好ましい巡回順序を決定することが可能となる。
【００４５】
本発明の第２のステップは、出発地、目的地および各巡回地点のそれぞれを探索開始点として、予め記憶される地図情報を用いて、出発地側探索処理および／または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各２地点間、および当該各巡回地点と当該目的地との間の経路を求め、    求めた各経路の評価値に基づいて、出発地と各巡回地点または目的地との間の評価値、複数の巡回地点に含まれる各２地点間の各評価値、および当該各巡回地点と目的地との間の評価値を取得する。
【００４６】
本発明によれば、第２のステップで、各地点を探索開始点とした出発地側探索処理および／または目的地側探索処理により、２地点間の経路が求められるので、探索処理の回数を最小限に抑えることができる。これによって、必要な組み合わせすべてについて、経路を短時間で求めることができる。
【００４７】
本発明の地図情報は、階層構造を有しており、下位階層の地図情報は、相対的に狭い範囲を詳細に記録した地図を表しており、上位階層の地図情報は、相対的に広い範囲を粗く記録した地図を表しており、第２のステップは、使用すべき地図情報の階層を選択し、    選択された階層の地図情報を用いて、出発地、目的地および各巡回地点のそれぞれを探索開始点として、出発地側探索処理および／または目的地側探索処理を行って、当該出発地と各当該巡回地点または当該目的地との間、当該複数の巡回地点に含まれる各２地点間、および当該各巡回地点と当該目的地との間の経路を探索し、選択された階層の地図情報では、経路を求めることができない場合、上位階層の地図情報を用いて、当該経路を求める。
【００４８】
本発明によれば、第２のステップでは、まず、下位階層の地図情報を用いて、各探索開始点からの探索処理を開始する。そして、下位階層の地図情報では求めることができない経路があった場合に、上位階層の地図情報を用いて探索処理を続ける。これによって、各階層に記録された道路網に適した探索範囲を設定することができるので、距離がある２地点間の経路を短時間で求めることができる。
【００４９】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、前記第２のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、前記第３のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、前記第２のステップは、前記出発地と各前記巡回地点または前記目的地との間、前記複数の巡回地点に含まれる各２地点間、および当該各巡回地点と前記目的地との間の経路を求め、求めた各経路の評価値に基づいて、前記出発地と各前記巡回地点または前記目的地との間の評価値、前記複数の巡回地点に含まれる各２地点間の各評価値、および当該各巡回地点と前記目的地との間の評価値を取得し、前記第４のステップは、前記第３のステップで決定された巡回経路に従って、前記出発地、前記目的地および各前記巡回地点から選択可能な２地点の組み合わせ数分だけ、２地点間探索を繰り返すことにより、１本の巡回経路を構成する。
【００５０】
本発明によれば、第２のステップで得られる評価値は、各２地点間に対するものである。したがって、かかる評価値を基に決定される巡回順序は、実際に車両が走行する道路を想定したものとなる。これによって、ユーザーにとって違和感のない効率的な巡回順序を求めることができる。また、第２のステップでは、評価値が、各２地点間の経路を実際に求めることにより得られる。そのため、より好ましい巡回順序を決定することが可能となる。また、第４のステップで、再度２地点間探索を行うことにより、第２のステップでは求めた経路を残しておかなくとも、巡回経路を構成することが可能となる。これによって、巡回経路選出のために必要となるＲＡＭの容量を抑えることが可能となる。
【００５１】
本発明は、複数の地点を効率よく巡回し、出発地から目的地へ至る巡回経路を選出するための方法であって、出発地、目的地および複数の巡回地点を選択する第１のステップと、前記出発地、前記目的地および各前記巡回地点から選択可能な２地点間のうち、必要な２地点間の評価値を取得する第２のステップと、前記第２のステップで得られた各評価値を利用して、前記複数の巡回地点を巡回する順序を、深さ優先探索方法に基づいて決定する第３のステップと、前記第３のステップで決定された巡回順序に従って、前記出発地、前記複数の巡回地点および前記目的地をつなぎ合わせて、当該出発地から当該目的地へ至る１本の巡回経路を構成する第４のステップとを含み、前記第２のステップは、前記出発地と各前記巡回地点または前記目的地との間、前記複数の巡回地点に含まれる各２地点間、および当該各巡回地点と前記目的地との間の経路を求め、求めた各経路の評価値に基づいて、前記出発地と各前記巡回地点または前記目的地との間の評価値、前記複数の巡回地点に含まれる各２地点間の各評価値、および当該各巡回地点と前記目的地との間の評価値を取得し、前記第２のステップはさらに、必要な２地点間毎に、最小の評価値を有する経路データを記録し、前記第４のステップは、前記第３のステップで決定された巡回経路に従って、前記第２のステップで記録された経路データに基づいて、１本の巡回経路を構成する。
【００５２】
本発明によれば、第２のステップで得られる評価値は、各２地点間に対するものである。したがって、かかる評価値を基に決定される巡回順序は、実際に車両が走行する道路を想定したものとなる。これによって、ユーザーにとって違和感のない効率的な巡回順序を求めることができる。また、第２のステップでは、評価値が、各２地点間の経路を実際に求めることにより得られる。そのため、より好ましい巡回順序を決定することが可能となる。また、第２のステップで記録された最小評価値の経路データに基づいて巡回経路が構成されるので、第４のステップでは、探索処理を改めて行う必要がなくなる。これによって、巡回経路選出に必要となる時間を抑えることができる。
【００５３】
【発明の実施の形態】
図１は、本巡回経路選出方法が採用されるカーナビゲーションシステムの構成を示すブロック図である。図１において、カーナビゲーションシステムは、ロケーター１０１と、データ記憶部１０２と、操作部１０３と、ナビゲーション装置１０４と、情報提示部１０５とを備えている。
【００５４】
ロケーター１０１は、ＧＰＳ、車速センサ、角速度センサ、絶対方位センサ等を含み、車両の現在位置を計算するためのデータを収集する。
データ記憶部１０２は、通常ＣＤやＤＶＤが使用され、交差点や道路の接続状況や座標・形状・属性・規制情報など、道路ネットワークに関する地図情報、地点設定を行うための索引情報等、ナビゲーションに必要となる各種情報を記憶している。
操作部１０３は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力したり、ユーザーの選択したい項目を指定したりする。
ナビゲーション装置１０４は、ＣＰＵやメモリ（プログラムメモリ、ワーキングメモリ）等を含む。ナビゲーション装置１０４は、基本的には、ロケーター１０１から入手した車両の移動情報を基に現在位置を特定するロケーション機能、目的地までの経路を自動的に選出し案内する経路誘導機能、索引情報を検索したり任意の場所の地図を表示したりする情報検索機能とを有している。
情報提示部１０５は、表示装置（液晶ディスプレイ、ＣＲＴディスプレイ等）やスピーカ等を含み、ユーザーに対して、現在車両位置の提示、誘導経路の案内、検索情報の提示を行う。
【００５５】
次に、図１のように構成されたカーナビゲーションシステムの各機能について説明する。
まず、ロケーション機能について概説する。ロケーター１０１は、刻々と変化する車両位置に関する情報（車両向きの変化角、車両の走行距離、絶対位置等）を収集する。ナビゲーション装置１０４は、ロケーター１０１により得られた車両位置に関する情報から、車両の移動軌跡を計算する。ナビゲーション装置１０４はさらに、マップマッチング技術等を利用しつつ、算出された車両の移動軌跡と、データ記憶部１０２から得られた周辺地図上の道路ネットワークとを比較して、地図上における車両の現在位置を特定する。情報提供部１０５は、ナビゲーション装置１０４により特定された、車両の現在位置を地図上に表示する。
【００５６】
次に、情報検索機能について概説する。操作部１０３は、情報提示部１０５のディスプレイ上に表示された各種項目の中から、検索したい内容を選択する。選択された項目の中から指定のものを、データ記憶部１０２の記録情報の中から検索し、情報提示部１０５のディスプレイ上に表示する。必要であれば、情報提示部１０５のスピーカーから音声等を出力する。
【００５７】
さらに、本発明に関わる経路誘導機能について概説する。まず、ユーザーは、操作部１０３を操作して、出発地および目的地を設定する。すなわち、ユーザーは、操作部１０３を操作することにより、情報提示部１０５に表示された地図の画像をスクロールさせ、希望する地点を出発地および目的地として入力する。なお、出発地は、上述のロケーション機能で検出した車両の現在位置を使用してもよい。次に、ナビゲーション装置１０４は、上記のように設定された出発地および目的地の位置に対して、データ記憶部１０２に記憶された地図上のノードまたはリンク上の一番近い点を、探索開始点および探索終了点として採用する。さらに、ナビゲーション装置１０４は、周知のダイクストラ法などを用いて最短コスト経路を計算し、求められた経路を、リンク列、ード列または座標列に変換し、誘導経路とする。本実施形態では、請求項における「評価値」の一例としてコストを採用する。以下の第１〜第４の巡回経路選出方法では、コストを旅行時間とみなし、旅行時間が短い経路を選出するものとする。最後に、情報提示部１０５は、ナビゲーション装置１０４で求められた誘導経路と現在車両位置と、データ記憶部１０２に記憶された地図データとに基づいて、誘導経路上を進むにはどの方向へ進めば良いかを、音声や表示を行なってユーザーに案内する。
【００５８】
また、ナビゲーションシステムでは、出発地・目的地の間に複数の巡回地点が設定できる。ユーザーは、目的地の設定と同様に、操作部１０３を操作して、複数の巡回地点を設定する。この時に、巡回する地点を設定する前に、巡回する地域を選択するようにしても良い。さらに、ナビゲーション装置１０４は、出発地・目的地・巡回地点間等の経路コストを参照し、設定された各巡回地点を通過し、しかもより小さな経路コストで出発地から目的地へ至る最適巡回経路を選出する。本巡回経路選出方法に関しては、後でフローチャートを用いて詳述する。
【００５９】
また、図２は、本巡回経路選出方法を適用可能な配送車両管理システムの一般的な構成を示すブロック図である。図２において、配送車両管理システムは、無線装置２０１と、データ記憶部２０２と、操作部２０３と、コンピュータ２０４と、情報提示部２０５とを備えている。
無線装置２０１は、携帯電話、専用無線等を含み、各配送車両に搭載されたロケーションシステムから、各配送車両の現在位置を収集する。
データ記憶部２０２には、大容量ハードディスクが通常使用される。データ記憶部２０２は、交差点および／または道路の接続状況、座標、形状、属性ならびに規制情報など、道路ネットワークに関する地図情報、地点設定を行うための索引情報、もしくは配送先管理情報等、配送管理業務に必要となる各種情報を記憶する。
操作部２０３は、リモートコントローラ、タッチセンサ、キーボード、マウス等を含み、ユーザの操作に従って地点情報等を入力したり、ユーザーの選択したい項目を指定したりする。
コンピュータ２０４は、ＣＰＵやメモリ（プログラムメモリ、ワーキングメモリ）等を含む。コンピュータ２０４は、基本的には、無線装置２０１から入手した各配送車両の現在位置を管理する位置管理機能、各車両に対し複数の配送先を指定して最適な配送経路を自動的に選出する経路選出機能、配送先情報を検索・入力する配送先情報管理機能とを有している。
情報提示部２０５は、表示装置（液晶ディスプレイ、ＣＲＴディスプレイ等）やスピーカ等を含み、ユーザーに対して、各配送車両の現在位置の提示、配送経路の案内、配送先情報の提示を行う。
【００６０】
次に、図２のように構成された配送車両管理システムの各機能について説明する。
まず、位置管理機能について概説する。無線装置２０１は、刻々と変化する各配送車両の位置情報を収集する。コンピュータ２０４は、無線装置２０１から各配送車両の位置に関する情報を入手し、データ記憶部２０２に記憶された地図データから得られた配送エリアの道路ネットワークを、情報提示部２０５のディスプレイ上に表示する。さらに、情報提示部２０５は、表示された道路ネットワークには、各配送車両の現在位置を重ねて表示する。
【００６１】
次に、配送先情報管理機能について概説する。操作部２０３は、情報提示部２０５のディスプレイ上に表示された配送エリアの地図上に重ねて表示されたカーソルを、マウスで希望する位置に移動することにより任意の位置を指定できる。配送先に関する付属情報（ＩＤ、配送先名称、連絡先、補足情報）は、操作部２０３のキーボードから入力される。また、過去に入力された配送先に関する付属情報は、データ記憶部２０２に記憶されており、それらの情報は、操作部２０３のマウス操作により呼び出され選択される。そして、操作部２０３のキーボード操作により、配送先に関する付属情報の修正、削除等を行う。
【００６２】
さらに、本発明に関わる経路選出機能について概説する。まず、ユーザーは、操作部２０３を操作して、配送地点を設定する。すなわち、ユーザーは、操作部２０３のマウスを操作することにより、情報提示部２０５のディスプレイ上に表示された配送エリアの地図上を参照して、実際に配送する配送先を選択する。なお、出発地および目的地は配送センターまたは上述の位置管理機能により把握された配送車両の現在位置を使うことができる。次に、コンピュータ２０４は、配送先がどの区域に属するか判定し、どの配送車両に割り振るか判断する。特定の配送車両に配送先が集中するようであれば、周辺区域受け持ちであり配送先が少ない他の配送車両に振り分けるようにしても良い。さらに、コンピュータ２０４は、各配送車両毎に出発地から出発し、割り振られた全配送先を通過して目的地に到達する最適巡回経路を選出する。本巡回経路選出方法に関しては、以降にフローチャートを用いて詳述する。
【００６３】
（１）第１の巡回経路選出方法
図３は、第１の巡回経路選出方法の処理手順を示すメインフローチャートである。図３のメインフローチャートに従う処理は、図１のナビゲーション装置１０４または図２のコンピュータ２０４により行われる。
図３において、ユーザーは、上述したようにして、出発地・目的地と、各巡回地点（各配送地）とを選択する（ステップＳ３０１，Ｓ３０２）。次に、各巡回地点間の最小コスト経路を求める地点間経路計算処理が行われる（ステップＳ３０３）。
ここで、図４は、図３のステップＳ３０３の詳細な処理手順を示すフローチャートである。図４において、まず、出発地・目的地・各巡回地点を含む範囲の地図データが一括して読み込まれる（ステップＳ４０１）。次に、出発地と各巡回地点の中から未選択の地点が１つ選択される（ステップＳ４０２）。選択された地点は、探索開始点として、以降の処理で用いられる。次に、読み込まれた地図データ全域に対して、探索開始点を起点として、公知のダイクストラ法に基づく探索処理が広げられる（ステップＳ４０３）。これによって、探索開始点から、終点としての他の地点（各巡回地点、目的地）への経路が構成され、構成された経路コストがコストマトリクスに記録され、さらに、経路の道順を示す経路データが記録される（ステップＳ４０４）。ここで、コストマトリクスとは、起点から終点への経路コストを、起点を行とし終点を列とする行列に記録したものである。図５はコストマトリクスの一構成例である。図５の例では、出発地および目的地以外の巡回地点数はｎ個としている。なお、目的地を起点とする経路コスト、出発地を終点とする経路コスト、および出発地から目的地への経路コストは、後で行われる巡回順序決定処理（ステップＳ３０４）には必要ないので、「−」マークで記載されている。
【００６４】
図４のステップＳ４０４の次に、探索開始点としての未選択の地点が残っているか否かが判断される（ステップＳ４０５）。未選択の地点があれば、ステップＳ４０２に戻り、未選択地点の１つが、次の探索開始点として選択される。その後、上記一連の処理（ステップＳ４０３〜Ｓ４０５）が繰り返される。一方、ステップＳ４０５において、未選択の地点がなければ、地点間経路計算処理（図３のステップＳ３０３）は終了する。地点間経路計算処理の終了時点で、図５のコストマトリクスが完成し、各欄が埋め尽くされる。
なお、上述したステップＳ４０２では、出発地と各巡回地点とから探索開始点が選択されていたが、目的地と各巡回地点とから探索開始点が選択されてもよい。この場合、ステップＳ４０３では、目的地と各巡回地点とから選択された探索開始点を基に探索処理が広げられる。このように、探索開始点として方向性を考慮した上で探索処理を行っても良い。
【００６５】
次に、図３のステップＳ３０４に進み、各巡回地点をどのような順序で通過するのが最適かを決定する巡回順序決定処理が実行される（ステップＳ３０４）。
ここで、図６は、図３のステップＳ３０４の詳細な処理手順を示すフローチャートである。図６において、全巡回地点が未選択状態にされた後、巡回地点が１個ずつ選択される。この時、同じ巡回地点は重複して選択されてはならない。巡回地点は、選択された順に、未選択巡回地点の管理情報に登録される（ステップＳ６０１）。この管理情報は、図７に例示するリスト構造を有している。リスト構造とは、先頭の地点から次の地点を連鎖的に次々と指し示したものである。図７では、ｎ個の巡回地点（Ｎ１〜Ｎｎ）が添え字の小さいものから連続的に並べられている。「先頭」には先頭の地点として＜Ｎ１＞が記録されており、「１番目」には、「先頭」の次の地点として＜Ｎ２＞が記録されている。以降、同様にして、選択された順番通りに、各巡回地点がつなげられていく。さらに、「（ｎ−１）番目」には、最後に選択された地点として＜Ｎｎ＞が記録されており、「ｎ番目」には巡回経路の終了を示すＩＤ情報として＜終了＞マークが記録されている。以上のリスト構造が採用されることにより、「先頭」から順番に次の地点を調べていくことが可能になる。これによって、後で行われる巡回再帰処理（ステップＳ６０４）において、未選択状態の巡回地点Ｎｉ（ｉ＝１，２…，ｎ）を効率よく見つけだすことができる。
【００６６】
再度図６を参照する。ステップＳ６０１の次に、出発地が、巡回コストＸの算出に必要となる前の巡回先ＰＰとして選択される（ステップＳ６０２）。さらに、巡回コストＸが初期化される（ステップＳ６０３）。すなわち、Ｘ＝０に設定される。この後、巡回再帰処理が行われる（ステップＳ６０４）。
ここで、図８は、図６のステップＳ６０４の詳細な処理手順を示すフローチャートである。まず、図８の処理手順で使用される、総巡回コストＹ、最小の総巡回コストＹｍｉｎおよび途中段階の巡回コストＸについて説明する。今、ｎ個（ｎは自然数）の巡回地点Ｎ１〜Ｎｎが選択されていると仮定する。本実施形態において、巡回経路とは、図９（ａ）〜（ｃ）に例示するように、同じ巡回地点を重複して通過することなく、全ての巡回地点Ｎ１〜Ｎｎを通過しつつ、出発地から目的地まで至る経路を意味する。
まず、総巡回コストＹは、１本の巡回経路のコストである。出発地から各巡回地点Ｎｉ（ｉはｉ≦ｎを満たす自然数）までのコスト、２個の巡回地点ＮｉおよびＮｊ（ｊは、ｉ≠ｊかつｊ≦ｎを満たす自然数）の間のコスト、各巡回地点Ｎｊから目的地までのコストは、図５のコストマトリクスに記載されている。したがって、巡回地点Ｎ１〜Ｎｎを巡回する順序が決まれば、１本の巡回経路を構成するために必要となる各コストは特定される。特定された各コストを合計すれば、総巡回コストＹを算出することができる。
【００６７】
深さ優先探索方法では、ある巡回経路の総巡回コストＹを得た後、別の総巡回コストＹを算出するという処理が繰り返される。最小の総巡回コストＹｍｉｎは、既に算出されている総巡回コストＹの内、最小の値を有するものである。
さらに、深さ優先探索方法では、１本の巡回経路を構成する際、互いに異なる巡回地点Ｎｉが１つずつ選択されていく。途中段階の巡回コストＸとは、出発地から、現在選択された巡回地点Ｎｉまでの経路（途中までの巡回経路）のコストである。この途中段階の巡回コストＸも、総巡回コストＹと同様に、図５のコストマトリクスを参照して算出される。
【００６８】
図８のステップＳ８０１では、途中段階の巡回コストＸと、最小の総巡回コストＹｍｉｎとが比較され、Ｘ≧Ｙｍｉｎを満たすか否かが判定される（ステップＳ８０１）。
Ｘ≧Ｙｍｉｎと判定された場合、現在調査対象の巡回経路は最小の総巡回コストＹｍｉｎをとる可能性が全くない。そのため、以降の処理を行っても無駄であるから、巡回再帰処理は打ち切られる。
また、Ｘ＜Ｙｍｉｎと判定された場合、現在調査対象の巡回経路は最小の総巡回コストＹｍｉｎをとる可能性があるので、以降の処理を行うべく、ステップＳ８０２が行われる。なお、ステップＳ８０１の時点で、巡回経路が１本も得られていなければ、最小の巡回コストＹｍｉｎは無限大とみなされる。したがって、この場合もＸ＜Ｙｍｉｎと判定される。
【００６９】
次に、図７の管理情報の「先頭」に設定された巡回地点Ｎｉが、現在の巡回先ＣＰとして選択される（ステップＳ８０２）。これによって、出発地ＮＳＰの次に巡回すべき巡回地点Ｎｉが選択される。次に、前の巡回先ＰＰが起点として選択され、現在の巡回先ＣＰが終点として選択される。その後、起点と終点との間のコストがコストマトリクス（図５参照）から読み出される。読み出されたコストは、巡回コストＸに加算される（ステップＳ８０３）。これによって、現在調査対象の巡回経路の途中段階の巡回コストＸが得られる。
【００７０】
次に、図７の管理情報を参照して、「先頭」の巡回地点Ｎｉが最後の巡回先ＬＰか否かが判定される（ステップＳ８０４）。この巡回地点Ｎｉの直後に＜終了＞マークが有れば、現在の巡回先ＣＰが最後の巡回先ＬＰとなる。つまり、調査対象の巡回経路が一通り構成されたことになるので、ステップＳ８１１が行われる。
本ステップでは、現在の巡回先ＣＰ（つまり、最後の巡回先ＬＰ）が起点として選択され、目的地ＮＤが終点として選択される。その後、起点と終点との間のコストがコストマトリクスから読み出される。読み出されたコストは、巡回コストＸに加算される（ステップＳ８１１）。これによって、現在調査対象である巡回経路の総巡回コストＹ（合計）が算出される。
【００７１】
次に、今回得られた総巡回コストＹと、最小の総巡回コストＹｍｉｎとが比較され、Ｙ＜Ｙｍｉｎを満たすか否かが判定される（ステップＳ８１２）。
Ｙ＜Ｙｍｉｎと判定された場合、今回得られた総巡回コストＹが最小の総巡回コストＹｍｉｎとして新たに記録される（ステップＳ８１３）。さらに、今回調査対象となった巡回地点Ｎ１、Ｎ２、…Ｎｎの巡回順序も新たに記録される。なお、ステップＳ８１２の時点で、最小の総巡回コストＹｍｉｎが求められていない場合、最小の巡回コストＹｍｉｎは無限大とみなされる。したがって、この場合も、Ｙ＜Ｙｍｉｎと判定される。このステップＳ８１２の後、巡回再帰処理が終了する。
一方、Ｙ≧Ｙｍｉｎと判定された場合、今回得られた総巡回コストＹが記録されることなく、そのまま巡回再帰処理は終了する。
【００７２】
ステップＳ８０４で、「先頭」の巡回地点Ｎｉが最後の巡回先ＬＰでなければ、調査対象の巡回経路は完全に構成されていないので、次の巡回地点Ｎｊ（ｊ≠ｉ）を選択して巡回コストＸを算出するために、ステップＳ８０５が行われる。
ステップＳ８０５では、現在の巡回先ＣＰが前の巡回先ＰＰとして選択される。さらに、現在の巡回先ＣＰとして選択されていた巡回地点Ｎｉは図７の管理情報から削除される（ステップＳ８０５）、これによって、未選択の巡回地点Ｎｊ（ｊ≠ｉ）のみが図７の管理情報に残る。さらに、未選択の巡回地点Ｎｊ（ｊ≠ｉ）のいずれかが「先頭」となる。
【００７３】
次のステップＳ８０６では、図８の巡回再帰処理が再度呼び出される。本ステップに移行した時点（つまり、初期状態）で、現在調査対象の巡回経路の途中までの巡回コストＸが算出されている。今回の巡回再帰処理では、まず、この途中段階の巡回コストＸ≧最小の総巡回コストＹｍｉｎか否かが判断される（ステップＳ８０１）。Ｘ≧Ｙｍｉｎの場合、上述したように、巡回再帰処理が終了する。Ｘ＜Ｙｍｉｎの場合、上述したように、ステップＳ８０２が行われる。
次に、管理情報（図７参照）の「先頭」に現在設定されている巡回地点Ｎｊが、現在の巡回先ＣＰとして選択される（ステップＳ８０２）。これによって、次に巡回すべき巡回地点Ｎｊが選択される。その後、上述したように、起点（＝前の巡回先ＰＰ）と終点（＝現在の巡回先ＣＰ）との間のコストが巡回コストＸに加算される（ステップＳ８０３）。これによって、出発地ＮＳＰから今回選択された巡回地点Ｎｊまでの巡回コストＸが得られる。
【００７４】
図７の管理情報において、「先頭」の巡回地点Ｎｊが最後の巡回先ＬＰでなければ（ステップＳ８０４）、当該現在の巡回先ＣＰが前の巡回先ＰＰとして選択される。さらに、現在の巡回先ＣＰとして選択されていた巡回地点Ｎｊは図７の管理情報から削除される（ステップＳ８０５）、これによって、未選択の巡回地点Ｎｋ（ｋ≠ｉ，ｋ≠ｊ）のみが図７の管理情報に残る。さらに、未選択の巡回地点Ｎｋのいずれかが「先頭」となる。
【００７５】
その後、図８の巡回再帰処理が再度呼び出される（ステップＳ８０６）。このように、巡回再帰処理は、ステップＳ８０１で打ち切られない限り、巡回地点Ｎｉが管理情報からなくなるまで（つまり、巡回経路が一通り構成されるまで）、繰り返し呼び出される。各巡回再帰処理では、管理情報に残っている未選択の巡回地点Ｎｉから現在の巡回先ＣＰが選択され（ステップＳ８０２）、その後、当該現在の巡回先ＣＰが前の巡回先ＰＰとして設定されるとともに、当該現在の巡回先ＣＰが管理情報から削除される。設定された前の巡回先ＰＰおよび現在の巡回先ＣＰが削除された管理情報が、次回の巡回再帰処理に引き継がれる。このような状況で、次回の巡回再帰処理は再帰される。
【００７６】
以上のステップ８０６が終了すると、ステップＳ８０５で削除された現在の巡回先ＣＰが図７の管理情報に戻される（ステップＳ８０７）。さらに、途中段階の巡回コストＸが、ステップＳ８０３での加算前の状態に戻される（ステップＳ８０８）。次のステップＳ８０９では、新しい巡回経路を調査対象とするために、前の巡回先ＰＰをステップＳ８０５で変更する前の状態に戻す。さらに、図７の管理情報において、ステップＳ８０７で戻された現在の巡回先ＣＰの直後につながっている巡回地点Ｎｉが、新たな現在の巡回先ＣＰとして選択される（ステップＳ８０９）。
【００７７】
次に、新たな現在の巡回先ＣＰとして、＜終了＞マークが選択されたか否かが判定される（ステップＳ８１０）。これが＜終了＞マークであれば、弥山宅の巡回地点を全て調査したとして、巡回再帰処理が終了する。一方、これが＜終了＞マークでなければ、未選択の巡回地点を全て調査していないとして、ステップＳ８０３に戻り、上述と同様に繰り返される。
以上の図８の巡回再帰処理は、最初に呼び出されたものが終了した時点で、全通りの巡回経路が調査され、最小の巡回コストＹｍｉｎが記録されている。そのため、図６のステップＳ６０４の巡回再帰処理が終了し、巡回順序決定処理が終了する。
【００７８】
ここで、巡回順序決定処理（ステップＳ３０４）の一具体例として、ｎ＝５の場合、つまり巡回地点Ｎ１〜Ｎ５の巡回順序を決定する場合について説明する。この場合、コストマトリクスは図１０のように作成される。
まず、ステップＳ３０４が開始されると、図１１（ａ）のような管理情報が作成される（ステップＳ６０１）。図１１において、管理情報は、５個の巡回地点（Ｎ１〜Ｎ５）が、添え字の小さいものから順番に並べられる。最後の「５番目」には＜終了＞マークが記録される。これによって、選択対象となる５個の巡回地点Ｎ１〜Ｎ５が保持される。
【００７９】
次に、出発地ＮＳＰが、前の巡回先ＰＰとして選択され（ステップＳ６０２）、巡回コストＸが「０」に初期化される（ステップＳ６０３）。その後、最初の巡回再帰処理が呼び出され、１つ目の巡回経路ＴＲ１の総巡回コストＹ１が算出され始める。ここで、図１２（ａ）は、ステップＳ３０４において得られる巡回経路ＴＲ１および総巡回コストＹ１を示している。まず、現在の巡回コストＸは最小の総巡回コストＹｍｉｎ（＝∞）よりも小さいので（ステップＳ８０１）、「先頭」の巡回地点Ｎ１（図１１（ａ）参照）が、現在の巡回先ＣＰとして選択され（ステップＳ８０２）、これによって、出発地ＮＳＰの次に巡回すべき地点が選ばれる。次に、前の巡回先ＰＰ（＝出発地ＮＳＰ）と現在の巡回先（巡回地点Ｎ１）との間のコスト（その値はＣ０１とする）が、図１０のコストマトリクスから読み出され、巡回コストＸ（＝０）に加算される（ステップＳ８０３）。その結果、現在の巡回コストＸは、Ｘ＝Ｃ０１となる。
【００８０】
巡回地点Ｎ１は、図１１（ａ）に示すように最後の巡回先ＬＰでないので（ステップＳ８０４）、現在の巡回先ＣＰとしての巡回地点Ｎ１は前の巡回先ＰＰとして設定された後に、管理情報から削除される（ステップＳ８０５）。削除された巡回地点Ｎ１は、次回以降の巡回再帰処理では管理情報から除外されているので、現在の巡回先ＣＰとして選択されない。これによって、同じ巡回地点Ｎを重複選択することなく、巡回経路ＴＲが構成されていく。また、管理情報は、図１１（ｂ）のように、巡回地点Ｎ１が抜かれた分、他の巡回地点Ｎ２〜Ｎ５および＜終了＞マークが順番を詰める。
【００８１】
ステップＳ８０５の後、巡回地点Ｎ１の次の巡回先を選択して、そこまでの巡回コストＸを算出すべく、２番目の巡回再帰処理が呼び出され実行される（ステップＳ８０６）。現在の巡回コストＸはＣ０１である。また、巡回経路ＴＲ１は、出発地ＮＳＰ→巡回地点Ｎ１まで構成されている。また、巡回地点Ｎ１が前の巡回先ＰＰとして選ばれている。さらに、管理情報の「先頭」は、図１１（ｂ）のように巡回地点Ｎ２である。この時点の状態（初期状態）で、２番目の巡回再帰処理が再帰される。
２番目の巡回再帰処理（ステップＳ８０７）でも、巡回経路ＴＲは１本も得られていないので、巡回コストＸ（＝Ｃ０１）は最小の総巡回コストＹｍｉｎ（＝∞）よりも小さい（ステップＳ８０１）。そのため、現在「先頭」にある巡回地点Ｎ２（図１１（ｂ）参照）が、現在の巡回先ＣＰとして、つまり巡回地点Ｎ１の次の巡回先が選択される（ステップＳ８０２）。次に、前の巡回先ＰＰ（＝巡回地点Ｎ１）と現在の巡回先ＣＰ（巡回地点Ｎ２）との間のコスト（その値はＣ１２とする）が巡回コストＸ（＝Ｃ０１）に加算される。その結果、現在の巡回コストＸは、Ｘ＝Ｃ０１＋Ｃ１２となる。
【００８２】
巡回地点Ｎ２は、図１１（ｂ）の管理情報に示すように、最後の巡回先ＬＰではないので（ステップＳ８０４）、巡回地点Ｎ２（現在の巡回先ＣＰ）は前の巡回先ＰＰとして設定された後に、管理情報から削除される（ステップＳ８０５）。その結果、管理情報は、図１１（ｃ）の状態に遷移し、巡回地点Ｎ２が抜かれた分、他の巡回地点Ｎ３〜Ｎ５および＜終了＞マークが順番を詰める。
【００８３】
ステップＳ８０５の後、３番目の巡回再帰処理が呼び出される（ステップＳ８０６）。この時点で、巡回コストＸはＣ０１＋Ｃ１２である。また、巡回経路ＴＲ１は、出発地ＮＳＰ→巡回地点Ｎ１→巡回地点Ｎ２まで構成されている。また、巡回地点Ｎ２が前の巡回先ＰＰとして設定されている。さらに、「先頭」は、図１１（ｃ）のように巡回地点Ｎ３である。この時点の状態（初期状態）で、３番目の巡回再帰処理が実行されると、ステップＳ８０１およびＳ８０２が実行された後、前の巡回先ＰＰ（＝巡回地点Ｎ２）と現在の巡回先（＝巡回地点Ｎ３）との間のコスト（その値はＣ２３とする）が巡回コストＸ（＝Ｃ０１＋Ｃ１２）に加算される（ステップＳ８０３）。その結果、現在の巡回コストＸは、Ｘ＝Ｃ０１＋Ｃ１２＋Ｃ２３となる。
さらに、ステップＳ８０４の実行後、巡回地点Ｎ３（現在の巡回地点ＣＰ）は前の巡回先ＰＰとして設定された後に、図１１（ｄ）に示すように管理情報から削除される（ステップＳ８０５）。
【００８４】
以降、４番目および５番目の巡回再帰処理（ステップＳ８０６）が呼び出される。便宜上、４番目の巡回再帰処理の説明を省略する。その後、５番目の巡回再帰処理が呼び出された時点で、巡回コストＸはＣ０１＋Ｃ１２＋Ｃ２３＋Ｃ３４である。また、巡回経路ＴＲ１は、出発地ＮＳＰ→巡回地点Ｎ１→巡回地点Ｎ２→巡回地点Ｎ３→巡回地点Ｎ４まで構成されている。また、巡回地点Ｎ４が前の巡回先ＰＰとして設定されている。さらに、管理情報は図１１（ｅ）のような状態にあり、「先頭」には巡回地点Ｎ５が設定されている。この時点の状態（初期状態）で、５番目の巡回再帰処理が実行されると、ステップＳ８０３において、前の巡回先ＰＰ（巡回地点Ｎ４）と現在の巡回先ＣＰ（巡回地点Ｎ５）との間のコスト（その値はＣ４５とする）が巡回コストＸに加算され（ステップＳ８０３）、巡回コストＸは、Ｃ０１＋Ｃ１２＋Ｃ２３＋Ｃ３４からＣ０１＋Ｃ１２＋Ｃ２３＋Ｃ３４＋Ｃ４５に更新される。
【００８５】
次に、管理情報は現在、図１１（ｅ）の状態にあるので、「先頭」の巡回地点Ｎ５は、最後の巡回先ＬＰと判定される（ステップＳ８０４）。そして、最後の巡回先ＬＰ（巡回地点Ｎ５）と目的地ＮＤとの間のコスト（その値はＣ５６とする）が、現在の巡回コストＸに加算される（ステップＳ８１１）。これによって、巡回経路ＴＲ１が一通り構成されたことになる。巡回経路ＴＲ１は、巡回地点Ｎ１→巡回地点Ｎ２→巡回地点Ｎ３→巡回地点Ｎ４→巡回地点Ｎ５の順番で、出発地ＮＳＰから目的地ＮＤへと至る経路である。また、巡回順序ＴＲ１が完全に構成されたことから、現在の巡回コストＸ（＝Ｃ０１＋Ｃ１２＋Ｃ２３＋Ｃ３４＋Ｃ４５＋Ｃ５６）は、総巡回コストＹ１として保持される。
【００８６】
次に、総巡回コストＹ１は、最小の総巡回コストＹｍｉｎ（＝∞）よりも小さいので（ステップＳ８１２）、今回構成された巡回経路ＴＲ１および総巡回コストＹ１は、最適な巡回経路および最小の総巡回コストＹｍｉｎとして記録される（ステップＳ８１３）。その結果、５番目の巡回再帰処理（ステップＳ８０７）が終了し、巡回経路ＴＲ１について実行された巡回再帰処理が終了する。５番目の巡回再帰処理が閉じられると、４番目の巡回再帰処理のステップＳ８０７以降が行われ、２番目の巡回経路ＴＲ２に関する巡回再帰処理の準備が行われる。
まず、４番目の巡回再帰処理のステップＳ８０５で削除された現在の巡回先ＣＰ（巡回地点Ｎ４）が、管理情報に戻される（ステップＳ８０７）。その結果、管理情報は、図１１（ｅ）の状態から、図１３（ａ）の状態へと遷移する。
また、現在の巡回コストＸが、４番目の巡回再帰処理のステップＳ８０３が実行される前の状態に戻される。つまり、現在の巡回コストは、ステップＳ８０３でＣ３４が加算される直前の状態に戻される。その結果、現在の巡回コストＸは、Ｘ＝Ｃ０１＋Ｃ１２＋Ｃ２３に戻される。
また、ステップＳ８０９において、前の巡回先ＰＰが、第４回目の巡回再帰処理が呼び出された時のものに戻される。したがって、前の巡回先ＰＰは、巡回地点Ｎ３に戻される。さらに、現在の巡回先ＣＰは、４番目の巡回再帰処理で設定されていたものから、新しいものに更新される（ステップＳ８０９）。より具体的には、現在の管理情報（図１３（ａ）参照）において、４番目の巡回再帰処理で使用された巡回地点Ｎ４の直後につながっている巡回地点Ｎ５が、新たな現在の巡回先ＣＰとして設定される。
【００８７】
ステップＳ８０７〜Ｓ８０９の実行により、２番目の巡回経路ＴＲ２は、図１２（ｂ）に示すように、出発地ＮＳＰ→巡回地点Ｎ１→巡回地点Ｎ２→巡回地点Ｎ３→巡回地点Ｎ５まで構成されたことになる。なお、出発地ＮＳＰ→巡回地点Ｎ１→巡回地点Ｎ２→巡回地点Ｎ３の巡回コストＸは既に得られている。この巡回コストＸは、２番目の巡回経路ＴＲ２の総巡回コストＹを求める際にも利用される。そして、この途中までの巡回経路ＴＲ２の巡回コストＸを算出すべく、ステップＳ８０３が実行される。つまり、図１２（ｂ）に示すように、前の巡回先ＰＰ（＝巡回地点Ｎ３）と現在の巡回先（巡回地点Ｎ５）との間のコスト（その値はＣ３５とする）が、現在の巡回コストＸ（＝Ｃ０１＋Ｃ１２＋Ｃ２３）に加算され、その結果、現在の巡回コストＸはＣ０１＋Ｃ１２＋Ｃ２３＋Ｃ３５となる。
【００８８】
「先頭」の巡回地点Ｎ４は、図１３（ａ）の管理情報に示すように、最後の巡回先ＬＰではないので（ステップＳ８０４）、巡回地点Ｎ５（現在の巡回先ＣＰ）は前の巡回先ＰＰとして設定された後に、管理情報から削除される（ステップＳ８０５）。その結果、管理情報は、図１３（ａ）の状態から図１３（ｂ）の状態に遷移し、巡回地点Ｎ５が抜かれた分、＜終了＞マークが順番を詰める。
【００８９】
ステップＳ８０５の後、６番目の巡回再帰処理が呼び出される（ステップＳ８０６）。この時点で、巡回コストＸはＣ０１＋Ｃ１２＋Ｃ２３＋Ｃ３５である。また、巡回経路ＴＲ２は、出発地ＮＳＰ→巡回地点Ｎ１→巡回地点Ｎ２→巡回地点Ｎ３→巡回地点Ｎ５まで構成されている。また、巡回地点Ｎ５が前の巡回先ＰＰとして設定されている。さらに、「先頭」は、図１３（ｂ）のように巡回地点Ｎ４である。この時点の状態（初期状態）で、６番目の巡回再帰処理が実行される。
まず、現在の巡回コストＸ（＝Ｃ０１＋Ｃ１２＋Ｃ２３＋Ｃ３５）は最小の総巡回コストＹｍｉｎ（＝Ｙ１）以上か否かが判断される（ステップＳ８０１）。今、Ｘ≧Ｙｍｉｎ（＝Ｙ１）であると仮定する。この仮定下では、巡回経路ＴＲ２は最適であり得ない。したがって、以降の処理（ステップＳ８０２〜Ｓ８１３）を行う必要がなく、６番目の巡回再帰処理は打ち切られ、終了する。これによって、無駄な処理が行われなくなるので、演算回数が減ることとなる。
【００９０】
以降、１番目の巡回再帰処理が閉じられるまで、図８のフローチャートに示された処理が行われる。１番目の巡回再帰処理が閉じられた時点で、最小の総巡回コストＹｍｉｎを有する最適な巡回経路が記録されていることになる。これによって、図３のステップＳ３０４（巡回順序決定処理）が終了する。
次のステップＳ３０５では、現在記録されている最適な巡回順序に従って、出発地ＮＳＰから目的地ＮＤに至る一本の巡回経路を構成する。ステップＳ３０６では、求められた巡回経路がユーザーに提示されたり、車両の移動に伴う現在位置が巡回経路上に表示されたりする。
【００９１】
以上のように、本実施形態のステップＳ３０４（巡回順序決定処理）では、深さ優先探索方法を基本方法とした処理が行われ、最適な巡回順序が調査される。この巡回順序決定処理では、現在得られている途中段階の巡回コストＸが、今まで最小の総巡回コストＹｍｉｎを超えた時点で、現在の巡回先ＣＰから派生する調査処理を打ち切る。つまり、最小の総巡回コストＹｍｉｎとなりえない組合せの調査処理を省略することができる。これによって、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【００９２】
また、本ステップＳ３０４（巡回順序決定処理）では、選択対象としての巡回地点Ｎｉは、選択された時点で、図７の管理情報（リスト構造）から削除される。したがって、各巡回再帰処理が開始された時点で、図７の管理情報には、未選択の巡回地点Ｎｊ（ｊ≠ｉ）のみが管理されている。さらに、各巡回再帰処理では、現在の巡回先ＣＰは、図７の管理情報の「先頭」から選択するだけである。これによって、効率的に未選択の巡回地点Ｎｉが選択される。その結果、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【００９３】
また、本ステップＳ３０３（地点間経路計算処理）において、出発地ＮＳＰ、目的地ＮＤおよびｎ個の巡回地点Ｎ１〜Ｎｎに含まれる２地点間の最小コスト経路を求める際に、各地点が探索開始地点として順に選択され（ステップＳ４０２）、その後、ダイクストラ法を用いて単方向探索処理（ステップＳ４０３およびＳ４０４）が行われる。これによって、ｍ地点（ｍは、出発地ＮＳＰ、目的地ＮＤおよびｎ個の巡回地点Ｎ１〜Ｎｎを合計した地点数）の各２地点間の探索処理をｍ×（ｍ−１）回からｍ回に削減することができる。これによっても、最適な巡回順序の選出に必要となる時間を短縮する事ができる。
【００９４】
（２）第２の巡回経路選出方法
第２の巡回経路選出方法では、第１の実施形態におけるデータ記憶部１０２（図１）、および第２の実施形態におけるデータ記憶部２０２（図２）に、予め決められた地点間の最小コスト経路結果（地点間コストおよび経路データ）が追加記録されている。さらに、予め決められた地点には、その地点周辺にアクセスするための主要道路上の地点も含むこととする。この地点を出入口地点と呼ぶ。
ここで、図１４は、予め決められた地点の一例である。図１４において、網掛けされた観光区域α内に、丸印で表された観光地点ＳＰが予め決められた地点として選択されている。また、この観光区域αにアクセスする道路として、二重丸の国道上の地点（Ｃ１〜Ｃ３）と三重丸の高速ＩＣ上の地点（Ｓ１）が、出入口地点として予め決められた地点に追加されている。第２の巡回経路選出方法は、車載ナビゲーションシステム上で、観光区域α内の複数の観光地ＳＰを巡回する最適な巡回順序を求める場合を想定している。第２の巡回経路選出方法の概略は、第１のそれと異なり、巡回地点Ｎ１〜Ｎｎは、予め決められた地点の中から選択された後に、データ記憶部１０２（または２０２）に記憶された各地点間の経路コストが読み出される。その後に、図５のようなコストマトリクスが作成され、第１の巡回経路選出方法と同様に最適な巡回順序が決定される。以下、本発明の第２の巡回経路選出方法をより詳細に説明する。
【００９５】
図１５は、第２の巡回経路選出方法の処理手順を示すメインフローチャートである。図１５において、まず、第１の巡回経路選出方法と同様に、出発地ＮＳＰおよび目的地ＮＤがユーザーにより選択される（ステップＳ１００１）。次に、予め決められた地点群の中から、ｎ個の巡回地点（配送地点）Ｎ１〜Ｎｎが選択される（ステップＳ１００２）。つまり、この予め決められた地点は、巡回地点Ｎ１〜Ｎｎを選択するための候補地点である。次に、予め記憶された各地点間の最小コスト経路結果から、ステップＳ１００２で選択された各巡回地点Ｎｉに含まれる地点間コストと経路データとが読み出される（ステップＳ１００３）。読み出された地点間コストと経路データとは、地点間経路情報としてＲＡＭ上に記憶される。
【００９６】
次に、予め定められた地点ではない出発地ＮＳＰと目的地ＮＤとを含む巡回経路ＴＲを求めるために、端地点追加処理が行われる（ステップＳ１００４）。端地点追加処理は、簡単に述べると、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎまで、および各巡回地点Ｎ１〜Ｎｎから目的地ＮＤまでの地点間コストおよび経路データを求めるための処理である。
図１６は、端地点追加処理の処理手順を示すフローチャートである。図１６において、まず、出発地ＮＳＰは予め決められた地点に含まれるか否かが判断される（ステップＳ１１０１）。
予め決められた地点に含まれるのであれば、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎへの最小コスト経路結果はデータ記憶部１０２（または２０２）に記録されているので、無処理でステップＳ１１０４に進む。
一方、出発地ＮＳＰが予め決められた地点に含まれていなければ、ステップＳ１１０２およびＳ１１０３を行って、出発地ＮＳＰから選択された各巡回地点Ｎ１〜Ｎｎへの最小コスト経路を求める。ステップＳ１１０２では、まず、出発地ＮＳＰ、および選択された巡回地点Ｎ１〜Ｎｎを含む領域の地図データがＲＡＭ（図示せず）上に読み込まれる。さらに、出発地ＮＳＰを探索開始点としてダイクストラ法を用い、出発地側探索処理（車両の進む方向に対して順方向に探索を広げる探索処理）が行われる（ステップＳ１１０２）。次に、選択された各巡回地点Ｎ１〜Ｎｎから経路構成が行われた後、出発地ＮＳＰから当該各巡回地点Ｎ１〜Ｎｎまでの最小コスト経路が求められる。そして、最小コスト経路としての地点間コストと経路データが地点間経路情報に追加される（ステップＳ１１０３）。その後、ステップＳ１１０４が行われる。
【００９７】
次に、目的地ＮＤは予め決められた地点に含まれるか否かが判断される（ステップＳ１１０４）。
予め決められた地点に含まれるのであれば、各巡回地点Ｎ１〜Ｎｎから目的地ＮＤへの最小コスト経路結果はデータ記憶部１０２（または２０２）に記録されているので、端地点追加処理は終了する。
一方、目的地ＮＤが予め決められた地点に含まれていなければ、ステップＳ１１０５およびＳ１１０６が行われ、選択された各巡回地点Ｎ１〜Ｎｎから目的地ＮＤへの最小コスト経路が求められる。ステップＳ１１０５では、まず、目的地ＮＤ、および選択された巡回地点Ｎ１〜Ｎｎを含む領域の地図データがＲＡＭ上に読み込まれる。さらに、目的地ＮＤを探索開始点としてダイクストラ法を用い、目的地側探索処理（車両の進む方向に対して逆方向に探索を広げる探索処理）を行う（ステップＳ１１０５）。次に、ステップＳ１１０６で、選択された各巡回地点Ｎ１〜Ｎｎから経路構成が行われた後、選択された各巡回地点Ｎ１〜Ｎｎから目的地ＮＤまでの最小コスト経路が求められる。そして、最小コスト経路としての地点間コストと経路データとが地点間経路情報に追加される。
以上で端地点追加処理（ステップＳ１００４）が終了し、これによって、出発地ＮＳＰ、目的地ＮＤおよび各巡回地点Ｎ１〜Ｎｎに含まれる２地点間の地点間情報が得られたことになる。
【００９８】
再度図１５を参照する。ステップＳ１００４（端地点追加処理）が終了すると、端地点（出発地ＮＳＰおよび目的地ＮＤ）と、各巡回地点Ｎ１〜Ｎｎとの間の最小コスト経路が求められたかどうかが判定される（ステップＳ１００５）。ステップＳ１００５の判定は、ステップＳ１００４の端地点追加処理において、ＲＡＭに読み込んだ地図データの範囲内で、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎ、または各巡回地点Ｎ１〜Ｎｎから目的地ＮＤまでの経路が求められなかった場合のために行われる。
ステップＳ１００５で、経路が求められていたならば、ステップＳ１００７に直接進み、巡回順序決定処理に進む。
一方、ステップＳ１００５で、経路が求められていなければ、出発地ＮＳＰの代わりに仮の出発地ＤＮＳＰ、または目的地ＮＤの代わりに仮の目的地ＤＮＤを設定するための出入口地点選択処理が行われる。
【００９９】
図１７は、出入口地点選択処理（ステップＳ１００６）の詳細な処理手順を示すフローチャートである。図１７において、まず、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎまでの経路が求められたか否かが判定される（ステップＳ１２０１）。ステップＳ１２０１で経路が求められていると判定されれば、無処理でステップＳ１２０５に進む。一方、ステップＳ１２０１で経路が求められていないと判定されれば、ステップＳ１２０２が行われる。
ステップＳ１２０２では、出発地ＮＳＰを探索開始点として、一方向の階層別探索処理を広げる。つまり、ダイクストラ法等を使用して、最下位階層の地図データで出発地ＮＳＰから探索処理を広げて、一定の範囲が探索終了すれば、より粗い道路網で、より広い範囲を記録した１階層上の地図データを用いて探索を行う処理が最上位階層まで繰り返される。本探索処理中に、一階層の探索処理が終了した後で、出入口地点（例えば、図１４のＣ１〜Ｃ３、Ｓ１）が探索終了状態になったか否かがチェックされた後に、接続コストが記録される。
次に、出発地ＮＳＰから最小経路コストで到達可能な出入口地点が、仮の出発地ＤＮＳＰと設定される（ステップＳ１２０３）。この時、観光区域αの境界上の地点（Ｃ１〜Ｃ３）が探索終了状態になっていれば、観光区域αから離れた主要道路上の地点（Ｓ１）よりも優先させてもよい。次に、出発地ＮＳＰから仮の出発地ＤＮＳＰへの経路コストと経路データとが記録され（ステップＳ１２０４）、出発地側の処理が終了する。
【０１００】
次に、各巡回地点Ｎ１〜Ｎｎから目的地ＮＤまでの経路が求められたかどうかが判定される（ステップＳ１２０５）。ステップＳ１２０５で経路が求められていると判定されれば、出入口地点選択処理（ステップＳ１００６）を終了する。一方、ステップＳ１２０５で経路が求められていないと判断されれば、ステップＳ１２０６が行われる。
ステップＳ１２０６では、目的地ＮＤを探索開始点として、上述した一方向の階層別探索処理を広げる。本探索処理中に、一階層の探索処理が終了した後で、出入口地点（例えば、図１４のＣ１〜Ｃ３、Ｓ１）が探索終了状態になったかどうかがチェックされた後に、接続コストが記録される。次に、ステップＳ１２０７では、目的地ＮＤまで最小経路コストで到達可能な出入口地点が、仮の目的地ＤＮＤと設定される。この時、観光区域αの境界上の地点（Ｃ１〜Ｃ３）が探索終了状態になっていれば、観光区域から離れた主要道路上の地点（Ｓ１）よりも優先させてもよい。次に、仮の目的地ＤＮＤから目的地ＮＤへの経路コストと経路データとが記録され（ステップＳ１２０８）、目的地側の処理を終了する。以上で、図１５のステップＳ１００６（出入口地点選択処理）は終了する。
【０１０１】
なお、以上の説明では、一方向探索の階層別探索方法を採用したが、観光区域αの境界上の地点（Ｃ１〜Ｃ３）が属する道路が記録されている地図の階層以上においては、観光区域αの境界上の地点（Ｃ１〜Ｃ３）の初期コストを０として逆方向の探索を実施し、双方向の階層別探索方法が採用されても良い。この場合には、観光区域αから離れた主要道路上の地点（Ｓ１）は、出入口地点として、予め決められた地点に含めなくとも良い。
また、以上の説明では、出発地ＮＳＰ（または目的地ＮＤ）からの最小経路コストで到達可能な出入口地点を自動的に仮の出発地ＤＮＳＰ（または仮の目的地ＤＮＤ）として採用したが、ユーザーにどのアクセス道路を選びたいか選択させても良い。
【０１０２】
再度図１５を参照する。ステップＳ１００６が行われた後、各巡回地点Ｎ１〜Ｎｎを巡回する順序を決定する巡回順序決定処理が行われる（ステップＳ１００７）。ステップＳ１００７の処理は、前述の図３のステップＳ３０４の処理と同様なので、詳細は省略する。ただし、ステップＳ１００７では、ステップＳ１００６の出入口地点選択処理で、仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤが選択されていれば、これらは出発地ＮＳＰまたは目的地ＮＤと同等に扱われる事とする。次に、ステップＳ１００７で得られた最適な巡回順序に従って、ステップＳ１００３、ステップＳ１００４、ステップＳ１００６で求められた経路データがつなぎ合わされ、出発地ＮＳＰ（仮の出発地ＤＮＳＰを含む）から目的地ＮＤ（仮の目的地ＤＮＤを含む）までの一本の巡回経路ＴＲが構成される（ステップＳ１００８）。最後に、求められた巡回経路ＴＲをユーザーに提示したり、車両の移動に伴う現在位置を巡回経路上に表示し、進むべき方向を案内したりする（ステップＳ１００９）。
【０１０３】
以上のように、第２の巡回経路選出方法によれば、前提条件として、巡回地点Ｎ１〜Ｎｎとして選択可能な地点が予め決定されている。さらに、これらの地点に関する地点間情報（地点間コストおよび経路データ）が予め求められている。これによって、各巡回地点間の経路を計算する必要がなくなる場合があり、最小の総巡回コストＹｍｉｎを有する巡回順序を選出するために必要な時間を短縮することができる。
【０１０４】
また、第２の巡回経路選出方法によれば、任意の出発地ＮＳＰまたは目的地ＮＤを探索開始点としてダイクストラ法を基本とした探索処理を行うことにより、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎ、または各巡回地点Ｎ１〜Ｎｎから目的地ＮＤへの経路が１回の探索処理で求められる。これによって、任意の出発地ＮＳＰからの最小コスト巡回経路、または任意の目的地ＮＤまでの最小コスト巡回経路の選出時間を短縮することができる。
【０１０５】
また、第２の巡回経路選出方法によれば、巡回区域（図１４における観光区域αに相当）へアクセスする道路上の地点が、出入口地点として予め決定されている。そして、上記予め決められた巡回用の地点と同様に、各出入口地点と各巡回地点Ｎ１〜Ｎｎとして選択可能な地点との間、および各巡回地点Ｎ１〜Ｎｎとして選択可能な地点と、各出入口地点との間の経路は、予め求められ経路情報として記録されている。そのため、巡回区域への入口地点を仮の出発地ＤＮＳＰ、または当該巡回区域からの出口地点を仮の目的地ＤＮＤとして選択することにより、仮の出発地ＤＮＳＰからの巡回経路ＴＲ、または仮の目的地ＤＮＤまでの巡回経路ＴＲを求めることができる。これによって、車載機のようにＲＡＭの容量が少ない環境において、出発地ＮＳＰから各巡回地点Ｎ１〜Ｎｎへの経路、または各巡回地点Ｎ１〜Ｎｎから目的地ＮＤまでの経路が求められない場合でも、選択された巡回地点Ｎ１〜Ｎｎの巡回経路ＴＲを求めることができる。
【０１０６】
また、第２の巡回経路選出方法によれば、上記出入口地点として、上記巡回区域の境界を横切る主要道路上の複数の地点が選択される。これによって、最低限必要な出入口地点を機械的に簡単に設定することができるので、出入口地点の選択を簡略化することができ、さらに、探索処理を用いて自動的に適切な仮の出発地ＤＮＳＰ、または仮の目的地ＤＮＤを選択することができる。
【０１０７】
また、第２の実施形態によれば、上記出入口地点として、上記巡回区域には含まれないが、その周辺を通過するより主要な道路上の地点が選択される。これによって、出発地ＮＳＰまたは目的地ＮＤからの一方向の階層別探索方法で、当該出発地ＮＳＰまたは目的地ＮＤへ最小コストで到達可能な出入口地点を選択することができる。その結果、巡回経路選出処理を簡略化でき、最適な巡回順序の選出までに必要な時間を短縮できる。
【０１０８】
さらに、第２の実施形態によれば、上記仮の出発地ＤＮＳＰ、または仮の目的地ＤＮＤは、出入口地点の中からユーザーにより選択可能にされることにより、好きな方向から巡回区域に進入または脱出できるので、ユーザーの好みで巡回区域までの進入道路または巡回区域からの脱出道路を選択することができる。
【０１０９】
（３）第３の巡回経路選出方法
第３の巡回経路選出方法では、第１の実施形態におけるデータ記憶部１０２（図１）、および第２の実施形態におけるデータ記憶部２０２（図２）に、予め決められた地点間の最小コスト経路結果（地点間コストのみ）を追加記録しておく。予め決められた地点には、その地点周辺にアクセスするための主要道路上の地点も含むこととする。この主要道路上の地点を、以下、出入口地点と呼ぶ。第３の巡回経路選出方法と第２のそれとが異なる点は、予め決められた地点間の経路データが予め記録されていない点にある。
その上で、巡回地点選出時に、予め決められた地点の中から巡回する地点が選択される。その後、データ記憶部１０２（または２０２）に記憶された各地点間の経路コストが読み出され、コストマトリクスが作成される。その後、第２の巡回経路選出方法と同様に、選択された巡回地点Ｎ１〜Ｎｎを巡回する順序が決定される。以下、第３の巡回経路選出方法について説明する。
【０１１０】
図１８は、第３の巡回経路選出方法の処理手順を示すメインフローチャートである。図１８のフローチャートは、第２の巡回経路選出方法を示すメインフローチャート（図１５）とほぼ同一である。以下、異なる点について説明する。第３の巡回経路選出方法（図１８）と第２のそれ（図１５）との相違点は、以下の２点である。
第１の相違点は、図１８のフローチャートでは、図１５のステップＳ１００３の代わりに、ステップＳ１３０３が実行されることである。第２の巡回経路選出方法では、図１５のステップＳ１００３において、選択した各巡回地点Ｎ１〜Ｎｎ間の経路コストと経路データとは、予め求められているため、ＲＡＭ上に読み込まれてきた。しかし、第３の巡回経路選出手方法では、上記の通りデータ記憶部１０２（または２０２）には、予め定められた地点間の経路コストしか記録されていないので、図１８のステップＳ１３０３において、選択した各巡回地点Ｎ１〜Ｎｎに含まれる２地点間の経路コストのみがＲＡＭ上に読み込まれる。
【０１１１】
第２の相違点は、図１８のステップＳ１３０７（図１５のステップＳ１００７に相当）とステップＳ１３０９（図１５のステップＳ１００８に相当）の間に、ステップＳ１３０８の地点間経路選出処理が行われる事である。第３の巡回経路選出方法では、上記の通りデータ記憶部１０２（または２０２）には、各地点間の経路データが記録されていない。そのため、ステップＳ１３０７の巡回順序決定処理で各巡回地点Ｎ１〜Ｎｎの巡回順序が決定された後、ステップＳ１３０９で出発地ＮＳＰから目的地ＮＤまでの巡回経路ＴＲをつなぎ合わせることができない。そこで、ステップＳ１３０８の地点間経路選出処理で、出発地ＮＳＰから最初の巡回地点Ｎｉまで、最初の巡回地点Ｎｉから２番目の巡回地点Ｎｊ、…、最後の巡回地点Ｎｋから目的地ＮＤまでの部分経路を、周知の２地点間探索方法を繰り返すことにより求める。
【０１１２】
ここで、図１９は、ステップＳ１３０８（地点間経路選出処理）の詳細な処理手順を示すフローチャートである。図１９において、まず、出発地ＮＳＰが起点として選択される（ステップＳ１４０１）。次に、ステップＳ１３０７（図１８）の巡回順序決定処理で決定された巡回順序に従って、起点の次の巡回地点Ｎｉを終点とする（ステップＳ１４０２）。ここで、ステップＳ１３０６（図１８）の出入口地点選択処理で、仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤが機械的に設定されている場合には、これらを終点として設定しない方が好ましい。ただし、仮の出発地ＤＮＳＰおよび仮の目的地ＤＮＤがユーザー自身により設定された場合等には、これらを終点として設定する。
【０１１３】
次に、ダイクストラ法に代表される従来の２地点間探索方法を用いて、起点から終点までの最小コスト経路が算出された後、経路データがＲＡＭ上に記録される（ステップＳ１４０３）。次に、終点は目的地ＮＤかどうかが判定される（ステップＳ１４０４）。ステップＳ１４０４で目的地ＮＤと判定されれば、出発地ＮＳＰから目的地ＮＤまでの巡回経路ＴＲの部分経路が全て求められたとして、地点間経路選出処理は終了する。
一方、ステップＳ１４０４で目的地ＮＤでないと判定されれば、ステップＳ１４０５が行われ、今回の終点が次回の起点として選択された上で、ステップＳ１４０２の処理に戻り、上記の処理を繰り返す。
【０１１４】
以上の地点間経路選出処理で求められた部分経路データを、図１８のステップＳ１３０９でつなぎ合わせることにより、各巡回地点Ｎ１〜Ｎｎを通過して出発地ＮＳＰから目的地ＮＤまでに至る巡回経路ＴＲが構成される。
【０１１５】
以上のように、第３の巡回経路選出方法によれば、巡回地点Ｎ１〜Ｎｎとして選択可能な地点が予め決定されている。また、各選択可能な地点間の経路コストのみが予め記録されている。巡回経路ＴＲの部分経路は２地点間探索処理を繰り返して求められる。これによって、第２の巡回経路選出方法のように、経路データが予め記録される必要がないので、データ記憶部１０２または２０２の記憶領域を有効利用することができる。
【０１１６】
また、第３の巡回経路選出方法によれば、出入口地点選択処理（ステップＳ１３０６）で決定された仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤを飛ばして、出発地ＮＳＰから目的地ＮＤまでの巡回経路ＴＲの部分経路が求められる。これによって、ユーザが真に立ち寄りたい巡回地点Ｎ１〜Ｎｎに関する、最小の総巡回コストＹｍｉｎを有する巡回経路ＴＲのみを選出することができる。これによって、自動的に選択された仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤを不自然に通過する巡回経路ＴＲの選出を防ぐことができる。
【０１１７】
また、第３の巡回経路選出方法によれば、ユーザー自身が設定した仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤを飛ばさずに、出発地ＮＳＰから目的地ＮＤまでの巡回経路ＴＲの部分経路が求められる。これによって、ユーザーが設定した仮の出発地ＤＮＳＰまたは仮の目的地ＤＮＤを通過する巡回経路ＴＲを選出することができる。その結果、ユーザーが意図したアクセス道路を必ず通って巡回区域に進入、または巡回区域から脱出する巡回経路ＴＲを求めることができる。
【０１１８】
（４）第４の巡回経路選出方法
本巡回経路選出方法のメインフローチャートは、上記第１〜第３の巡回経路選出方法のメインフローチャート（図３、図１５、図１８）と同様とする。ここで、上記第１〜第３の巡回経路選出方法では、同一の巡回順序決定処理（図６）を用いていた。この巡回順序決定処理は、巡回すべき地点数が十数地点以上になると処理時間が増大し、実用的な時間で最適な巡回順序を求めることは難しいという問題点がある。そこで、この問題を解決するため、図６の巡回順序決定処理の代わりに、下記のような巡回順序決定処理を採用する。
【０１１９】
図２０は、第４の巡回経路選出方法に係る巡回順序決定処理を示すフローチャートである。図２０において、選択された全ての巡回地点Ｎ１〜Ｎｎが対象地点群として選択される（ステップＳ１５０１）。次に、多数の全巡回地点Ｎ１〜Ｎｎを一定数以下のグループに分割する再帰グループ化処理が行われる（ステップＳ１５０２）。
ここで、図２１は、再帰グループ化処理の詳細な手順を示すフローチャートである。図２１において、まず、対象地点群には、一定数以上の巡回地点Ｎ１〜Ｎｎが含まれるか否かが判定される（ステップＳ１６０１）。この一定数の値は、使用する装置のハード性能に依存するものが、ここでは１０個としておく。ただし、十分短時間で巡回経路が求められる時間であれば、上記一定数の値はいくつでもかまわない。ステップＳ１６０１で一定数未満と判断されたならば、グループ化する必要はないとして、再帰グループ化処理を終了する。
【０１２０】
一方、ステップＳ１６０１で一定数以上と判断されたならば、ステップＳＳ１６０２が実行される。ステップＳ１６０２では、まず、対象地点群の内、２地点間コストが最も小さい２個の巡回地点Ｎｉが選択される。選択された２地点は同一グループとしてまとめられる（ステップＳ１６０２）。次に、グループ数が一定数以上であるか否かが判定される（ステップＳ１６０３）。ここで、グループ化されていない巡回地点Ｎｊ（ｊ≠ｉ）については、１地点が１グループとして換算される。ここで、一定数の値は、ステップＳ１６０１での一定数の値と同一とし、１０個を採用する。ステップＳ１６０３において、グループ数が一定数以上であれば、さらにグループ化する必要があると判断し、ステップＳ１６０２の処理に戻る。一方、ステップＳ１６０３において、グループ数が一定数未満であれば、これ以上グループ化を行う必要はないと判断し、ステップＳ１６０４に進む。以降のステップＳ１６０４〜Ｓ１６０８は、ステップＳ１６０２およびＳ１６０３で構成されたグループに対して、下記のような調査が行われる。
【０１２１】
まず、未調査のグループの中の１つが調査対象として選択される（ステップＳ１６０４）。次に、調査対象のグループに含まれる巡回地点Ｎｉの数が一定数以上かどうかが判定される（ステップＳ１６０５）。ここで、一定数の値は、ステップＳ１６０１での一定数の値と同一とし、１０個を採用する。ステップＳ１６０５で、巡回地点Ｎｉの数が一定数未満であれば、調査対象のグループをさらにグループ化する必要（つまり、下位層のグループを作成する必要）はないと判断され、無処理でステップＳ１６０８が行われる。
【０１２２】
一方、ステップＳ１６０５で、地点数が一定数以上であれば、処理時間が増大するとみなして、さらに下層グループを作って、調査対象のグループを分割する必要があると判断され、ステップＳ１６０６およびＳ１６０７が行われる。まず、調査対象のグループに含まれる全ての巡回地点Ｎｉが処理対象として設定される（ステップＳ１６０６）。次に、処理対象となる巡回地点Ｎｉを下位層グループに分割するために、図２１の再帰グループ化処理が再帰的に実行される。この再帰グループ化処理により、グループが階層的に構成されていく。再帰グループ化処理は、各下位層グループに含まれる巡回地点Ｎｊ（ｊ⊂ｉ）の数が一定数未満になるまで繰り返される。
【０１２３】
次に、ステップＳ１６０８に進み、全グループがステップＳ１６０４において調査対象となったか否かが判定される（ステップＳ１６０８）。ステップＳ１６０８で、全グループの調査が終了していなければ、ステップＳ１６０４に戻り、次の調査対象グループを選択し、以降の処理を繰り返す。一方、ステップＳ１６０８で、全グループの調査が終了していれば、再帰グループ化処理が終了する。
なお、本実施形態では、グループ化する際（ステップＳ１６０２）に２地点間コストが小さい地点同士からグループ化を行ったが、空間距離で近い地点同士からグループ化を行っても良い。また、別々のグループに属する２地点をグループ化した結果、大きなグループができる場合がある。このグループが他のグループよりもはるかに大きい場合には、グループ化を行わないようにしても良い。
【０１２４】
ここで、上記再帰グループ化処理によりグループ分けされた地点の例を、図２２に示す。図２２において、巡回地点Ｎが１７地点（白丸参照）あるが、図２１の再帰グループ化処理により、８個のグループＧ１〜Ｇ８（網掛け部）が形成されている。また、出発地ＮＳＰを☆印、目的地ＮＤを★印で表している。
再度図２０を参照する。ステップＳ１５０２の再帰グループ化処理が終了すると、当該グループ分けした結果に従って、ステップＳ１５０３の階層的巡回順序決定処理が行われる。このステップＳ１５０３では、上位層のグループの巡回順序が決定された後、下位層のグループの巡回順序が決定されるという処理が繰り返し実行される。その結果、最終的には、近似的に最小の総巡回コストＹｍｉｎを有する巡回順序が求められる。以下、階層的巡回順序決定処理（ステップＳ１５０３）の詳細な手順を、図２３を参照して説明する。なお、この階層的巡回順序決定処理もまた再帰的な処理である。
【０１２５】
最初の階層的巡回再帰処理が呼び出されると、まず、図２３のステップＳ１８０１において、先頭の巡回地点Ｎｔを含むグループが先頭巡回グループとして選択される。さらに、最終の巡回地点Ｎｅを含むグループが最終巡回グループとして選択される（ステップＳ１８０１）。ただし、最初の階層的巡回処理では、出発地ＮＳＰから最小経路コストで到達できる巡回地点を含むグループが先頭巡回グループとして、目的地ＮＤへ最小経路コストで到達できる巡回地点を含むグループが最終巡回グループとして選択される。
ステップＳ１８０１の次に、先頭巡回グループおよび最終巡回グループ以外のグループが未選択状態に設定される。さらに、未選択状態のグループについて、初期の管理情報（リスト構造）が作成される（ステップＳ１８０２）。今回作成される管理情報の説明は、第１の巡回経路選出方法で詳述したので割愛する。ただし、第１の巡回経路選出方法では巡回地点Ｎｉについて管理情報が作成されたが、最初の階層的巡回順序決定処理では、最上位層のグループＧｉについて管理情報が作成される点には注意を要する。つまり、最初の階層的巡回順序決定処理では、最上位のグループＧｉがひとまとまりになって巡回地点としてみなされる。
【０１２６】
次に、先頭巡回グループが、前の巡回先ＰＰとして選択される。さらに、最終巡回グループが、便宜上、目的地ＮＤとして選択される（ステップＳ１８０３）。さらに、現在の巡回コストＸが初期化される（ステップＳ１８０４）。次に、最上位層のグループＧｉを、同じグループを重複通過することなく、効率的に巡回する巡回経路ＴＲを求めるために、巡回再帰処理が行われる。本巡回再帰処理の説明は、第１の巡回経路選出方法で詳述した巡回再帰処理（図８）と同様なので省略する。ただし、本巡回再帰処理においては、最上位のグループＧｉを第１の巡回経路選出方法で説明した巡回地点Ｎｉと同様に扱う。また、あるグループＧａと他のグループＧｂとの間のグループ間コスト（第１の巡回経路選出方法における地点間コストに相当）は、あるグループＧａに属するいずれかの巡回地点Ｎａと、他のグループＧｂに属するいずれかの巡回地点Ｎｂとの組合せの中で、地点間コストが最小コストであるものとする。この時、あるグループＧａ内で選択された巡回地点Ｎｊ（ｊ∈ａ）が、当該グループＧａ内で最終の巡回地点Ｎｅとなる。また、他のグループＧｂ内で選択された巡回地点Ｎｋ（ｋ∈ｂ）が、当該グループＧｂ内での先頭の巡回地点となる。
【０１２７】
以上、ステップＳ１８０１〜ステップＳ１８０５の処理で、最上位層のグループＧｉを最も効率的に巡回できる巡回順序を求めることができる。参考までに、この一連の処理で得られた最上位層のグループＧｉの巡回経路ＴＲの一例を、図２４に示す。図２４において、まず、出発地ＮＳＰから、全ての最上位層のグループＧ１〜Ｇ８を通過し、目的地ＮＤに至る巡回経路ＴＲの概要（太い矢印の経路）を決定することができる。
ステップＳ１８０６以降の処理では、各グループ内に含まれる巡回地点Ｎｉの最適な巡回順序が決定される。まず、未調査のグループＧｉの中の１つが、調査対象として選択される（ステップＳ１８０６）。次に、調査対象のグループＧｘ（ｘ∈ｉ）の中に、２個以上の巡回地点Ｎｘ（ｘ∈ｉ）が含まれるか否かが判定される（ステップＳ１８０７）。ステップＳ１８０６で巡回地点Ｎｘが１つであれば、無処理でステップＳ１８１０に進む。一方、ステップＳ１８０６で巡回地点Ｎｘが２個以上含まれていれば、ステップＳ１８０８が行われる。
【０１２８】
ステップＳ１８０８において、調査対象のグループＧｘに含まれる全ての巡回地点Ｎｘが処理対象として選択される（ステップＳ１８０８）。次に、調査対象のグループＧｘに含まれる巡回地点Ｎｘの最適な巡回順序を決定するために、図２３の階層的巡回順序決定処理が再帰的に実行される（ステップＳ１８０９）。この階層的巡回順序決定処理が再帰されることにより、最終的には、全ての巡回地点Ｎｉが一本の巡回経路ＴＲでつながることになる。
次に、全てのグループＧｉを調査したかどうかが判定される（ステップＳ１８１０）。ステップＳ１８１０で、未調査のグループＧｉが存在すれば、ステップＳ１８０６に戻り、次のグループを調査対象とし、以上の処理が繰り返される。一方、ステップＳ１８１０で、全てのグループが調査済みであれば、階層的巡回順序決定処理は終了する。これによって、図２０に示された巡回順序決定処理が終了する。参考までに、以上の処理により得られた巡回経路ＴＲの一例を、図２５に示す。このように、各階層のグループ間経路を合成することにより、全ての巡回地点Ｎｉがつながった全体の巡回経路ＴＲを求めることができる。
【０１２９】
なお、第４の巡回経路選出方法では、上位階層のグループから下位層のグループへと処理を進めることにより巡回経路ＴＲを求めていったが、下位階層のグループから上位層のグループへと処理を進めることにより巡回経路ＴＲを求めるようにしても良い。つまり、下位層から各地点（グループ）が始点および終点となる最小経路コストの部分巡回経路が求められ記録される。部分巡回経路は、同じ階層に含まれる２地点（または２グループ）の全ての組み合わせについて記録される。そして、全体として最小経路コストとなる巡回経路ＴＲが選出されればよい。
【０１３０】
以上のように、第４の巡回経路選出方法によれば、近接する巡回地点Ｎｉが１グループにまとめられた上で、巡回経路が求められるので、調査対象となる組合せの数が減少するので、特に巡回地点Ｎｉの個数が多い場合には、巡回経路ＴＲを選出するまでに要する時間を短縮することができる。
また、第４の巡回経路選出方法では、２地点間の空間距離が近いものが優先的に１グループにまとめられるので、比較的簡単な処理で選出された巡回経路ＴＲの品質を向上することができる。
また、第４の巡回経路選出方法によれば、２地点間の距離（または旅行時間）に関する評価値（経路コストに相当）の小さいものが優先的に１グループにまとめられる。したがって、空間距離的には近くても、２地点間の道路が迂回しているような２個の巡回地点Ｎｉのグループ化を避けることができる。これによって、選出された巡回経路ＴＲの品質を向上することができる。
【０１３１】
また、第４の巡回経路選出方法によれば、グループ化された結果、他のグループと比較して非常に広範囲な一つのグループができあがる場合がある。そのグループ化が無効とされるので、各グループの大きさを平均化することができる。その結果、いびつな巡回経路ＴＲの選出を防ぐことができる。これによって、選出された巡回経路ＴＲの品質を向上することができる。
また、第４の巡回経路選出方法によれば、最適な巡回順序が決定されるとき、上位層のグループから巡回順序を決定することにより、まず上位層で大まかな巡回順序が決定される。これによって、全体の計算量を削減することができるので、最適な巡回順序を選出するために必要な処理時間を短縮することができる。
【０１３２】
（５）第５の巡回経路選出方法
図１に示すカーナビゲーションシステムは車載されるという性質上、当該システム内のＲＡＭの容量に制限があったり、プロセッサが非力だったりする。かかる事情から、処理負荷が軽く、かつ使用するＲＡＭの容量が少ない巡回経路選出方法が要望されている。かかる要望は、以下の第５の巡回経路選出方法により実現される。
【０１３３】
図２６は、第５の巡回経路選出方法の処理手順を示すフローチャートである。図２６のメインフローチャートに従う処理は、主として、図１のナビゲーション装置１０４により行われる。
図２６において、ユーザーは、前述と同様にして、出発地および目的地と、複数の巡回地点とを指定する（ステップＳ２６０１，Ｓ２６０２）。
【０１３４】
次に、選択された出発地、目的地および複数の巡回地点に基づいて、地点間経路計算処理が行われる（ステップＳ２６０３）。地点間経路計算処理を概説すると、指定された出発地、目的地、複数の巡回地点から選択可能な２地点が選択され、選択された２地点間の最小コストと、最小コスト経路とが求められる。ここで、最小コストは、好ましくは、選択された２地点間を車両で移動する際の旅行時間の内、最小の値を意味する。また、最小コスト経路とは、旅行時間が最小となる経路を意味する。求められた最小コストは、最適な巡回経路を求める際の評価値として、コストマトリクスに記述される。
【０１３５】
ここで、コストマトリクスは、図５を参照して既に説明したように、選択された２地点の内の起点から終点までの評価値（最小コスト）を、起点を行とし終点を列とする行列に記録したものである。図５には、出発地および目的地の他に、巡回地点数をｎ地点として場合の例が示されている。例えば、出発地を起点とし、巡回地点Ｎ１を終点とする際の最小コストは５０分である。ここで注意を要するのは、目的地を起点とするコスト、出発地を終点とするコスト、および出発地から目的地へのコストは必要ないので、コストマトリクスには「−」マークが予め記述される。
なお、上記コストは起点から終点へと到達するまでの評価値を表していれば良く、２地点間の移動距離または直線距離でも良いし、通過料金を考慮したものでもよい。
【０１３６】
図２７は、図２６のステップＳ２６０３の詳細な処理手順を示すフローチャートである。図２７において、まず、経路探索を開始する地図情報の階層が設定される（ステップＳ２７０１）。ここで、第５の巡回経路選出方法に係るデータ記憶部１０２には、階層構造を有する地図情報が記録されている。つまり、最下位層の地図情報は、最も大きな縮尺で表された詳細な地図をデータ化したものである。また、最階層の地図情報は、予め定められた範囲（例えば、約１．５ｋｍ四方）を、細街路まで詳細に表す。かかる最階層の地図情報がいくつも集まって、広い範囲の地図を構成することとなる。そして、より上位階層の地図情報になるほど、より小さな縮尺の地図となり、より広い範囲を粗く表す（つまり、より主要な道路が記録される）地図となる。そのため、ステップＳ２７０１では、各２地点間の評価値を計算する際に、どの階層から計算するか決定する。通常は、最下位階層から計算することが望ましいが、処理に必要となるＲＡＭ容量や、処理負荷を削減するため、中間階層以上から探索を開始しても良い。また、出発地、目的地および各巡回地点が主要な道路上の地点であれば、当該主要な道路が記録されている階層から探索を開始しても良い。
【０１３７】
ステップＳ２７０１の次に、設定された階層の地図情報を用いて探索処理が行われる（ステップＳ２７０２）。図２８は、ステップＳ２７０２の詳細な処理手順を示すフローチャートである。まず、出発地、目的地および各巡回地点が探索開始点候補として設定される（ステップＳ２８０１）。次に、探索開始点候補の中から、未選択の地点がひとつ選択され、選択された地点が探索開始点として設定される。次に、設定された探索開始点およびその周辺の地図情報が、データ記憶部１０２からＲＡＭへと読み込まれる（ステップＳ２８０３）。読み込まれる地図情報が表す範囲は、予め定められている。
【０１３８】
ステップＳ２８０３の次に、探索開始点または後述する上位移行地点から、出発地側探索処理および目的地側探索処理が行われる（ステップＳ２８０４）。これらの探索手法としては、周知技術であるダイクストラ手法を用いることができる。ただし、探索開始点または上位移行地点から、出発地に対しては出発地側探索処理、当該探索開始点等から目的地に対しては目的地側探索処理のみでよい。各探索処理実行中には探索結果として、探索開始点から他の地点への到達コストと、当該２地点間での通過リンク（または、ひとつ前の通過ノード）の情報を記録しておく。
次に、探索範囲の端点であり、上位階層に記録されている道路上の地点が上位移行地点として記録され、探索開始点から当該上位移行地点への到達コストが記録される。また、探索開始点から上位移行地点までの経路データを候補経路として記録する（ステップＳ２８０５）。なお、ステップＳ２８０５では、経路データの記録を行わない場合もあり得る。その場合は、後述のステップＳ２６０５（図２６）において、ステップＳ２６０４で決定された巡回順序に従って、従来の２地点間探索を繰り返すことにより、経路データを作成する。
【０１３９】
ステップＳ２８０５の次に、未選択の地点があるかどうかが判定され、あればステップＳ２８０２に戻り、次の探索開始点が選択された後、以降の処理が繰り返される。未選択の地点がなければ、階層内探索処理を終了する。
【０１４０】
ここで、図２７を再度参照する。ステップＳ２７０２が終了すると、現在設定されている階層において、２地点間経路が求められたかどうかを判定する接続判定処理が行われる（ステップＳ２７０３）。図２９は、この接続判定処理の詳細な手順を示すフローチャートである。最初に、未接続の２地点間が判定対象候補として設定される（ステップＳ２９０１）。
【０１４１】
次に、設定された判定対象候補のうち、未判定のものがひとつ選択され、判定対象として設定される（ステップＳ２９０２）。
次に、上記階層内探索処理において、判定対象の２地点間経路が求められたかどうかが判断される（ステップＳ２９０３）。例えば、地点Ａから地点Ｂへの２地点間経路が求められたかどうか判断するためには、地点Ａからの出発地側探索結果と、地点Ｂからの目的地側探索結果とを参照し、共通する探索済み地点が存在するかどうか調査する。もし、共通する探索済み地点が存在すれば、地点Ａ側から共通の探索済み地点への到達コストと、地点Ｂ側から当該探索済み地点への到達コストとを基に、地点Ａから地点Ｂまでの総コストが計算され、総コストが最小となる地点を通過する経路が当該地点間の経路とみなされる。
【０１４２】
もし、ステップＳ２９０３で、共通する探索済み地点が存在しなければ、２地点間経路が求められなかったものとして、無処理でステップＳ２９０６に進む。一方、ステップＳ２９０３で、共通する探索済み地点が存在すれば、当該ステップで求められた２地点間経路の総コストが、２地点間コストとしてコストマトリクスに記録される（ステップＳ２９０４）。
【０１４３】
さらに、ステップＳ２９０３で求められた地点間経路の経路データが構成される（ステップＳ２９０５）。その際に、現在設定されている階層における探索経路の端点が、下位階層からの上位移行地点であれば、ステップＳ２８０５で記録された下位階層の候補経路データから該当するものを選択して端点に追加することで、地点Ａから地点Ｂまでの全ての経路が構成され、その経路が地点間経路情報として記録される。
なお、ステップＳ２９０５が行われない場合もあり得る。その場合は、後述のステップＳ２６０５（図２６）において、ステップＳ２６０４で決定された巡回順序に従って、従来の２地点間探索を繰り返すことにより、経路データを作成する。当然ながら、ステップＳ２８０５（図２８）での経路データの記録も必要ではなくなる。
【０１４４】
次に、判定対象候補のうち、未判定の地点間が存在するかどうかが判断され（ステップＳ２９０６）、存在すればステップＳ２９０２に戻り、別の判定対象が選択された後、以降の処理が繰り返される。一方、ステップＳ２９０６で未判定の地点間が存在しなければ接続判定処理を終了する。
【０１４５】
再度図２７を参照する。ステップＳ２７０３が終了すると、必要な全地点間の経路（例えば、図５の数値が書かれている欄の起点・終点間の経路）が求められたかどうかが判断される（ステップＳ２７０４）。求められていない地点間の経路が存在すれば、探索対象の階層を上位階層へ移し（ステップＳ２７０５）、ステップＳ２７０２に戻って、当該階層において階層内探索処理から繰り返す。一方、ステップＳ２７０４で、必要な地点間の経路が全て求められていれば、地点間経路計算処理を終了する。以上で、コストマトリクスの空欄が埋められた事になる。
【０１４６】
再度図２６を参照する。ステップＳ２６０３の次に、巡回地点の巡回順序が決定される（ステップＳ２６０４）。カーナビゲーションシステムで巡回順序を決定する場合、巡回地点数は数地点程度（例えば、５地点）であるので、通常の深さ優先探索手法を用いれば良い。
次に、決定された巡回順序に従って、出発地から目的地までの経路データが作成される（ステップＳ２６０５）。本実施形態では、図２９のステップＳ２９０５において、各２地点間の経路データを記録しているので、ステップＳ２６０４で決定された巡回順序に従って、各２地点間の経路データを順次読み出してくればよい。
【０１４７】
なお、図２８のステップＳ２８０５での候補経路の経路データの記録、および／または、図２９のステップＳ２９０６での地点間経路の経路情報の記録が行われていない場合には、ステップＳ２６０４で決定された巡回順序に従って、通常の２地点間探索処理を各区間分だけ繰り返す事により、経路データを作成することも可能である。
ステップＳ２６０５の次に、求められた巡回経路をユーザーに提示したり、現在地の移動に伴い巡回経路上を誘導したりする。
【０１４８】
以上説明した、図２６の地点間経路計算処理（ステップＳ２６０３）により、各地点間の経路算出処理の負荷が次のように軽減される。例えば、巡回地点が３地点（Ｎ１、Ｎ２、Ｎ３）の場合、巡回地点同士の各２地点間の組合せは６通りである。この６通りの経路を２地点間探索を６回繰り返して探索すると図３０から図３５のようになる。ここで、図３０〜図３５は、２地点間探索の繰り返しで各地点間経路を求める処理の説明図である。本説明図においては、使用する地図情報は２階層と仮定している。この場合、下位階層の出発地側および目的地側探索回数は１２回、上位階層の出発地側および目的地側探索回数は同じく１２回となる。
【０１４９】
それに対して、本実施形態に係る地点間経路計算処理では、図３６のような処理となる。図３６は、本実施形態で各地点間経路を求める処理の説明図である。本実施形態においては、図３６に示すように、下位階層で各巡回地点から出発地側および目的地側探索処理を広げ、その後上位階層へ移行して続きの探索処理を続行する動きとなる。そのため、下位階層の出発地側および目的地側探索回数は６回、上位階層の出発地側および目的地側探索回数も同じく６回で済む。このように、比較的軽い負荷で各地点間経路を求めることができる。
【０１５０】
ここで、上記実施形態では、データ記憶部１０２に記録されている地図情報は階層構造としたが、１階層でも良い。その場合、図２７のステップＳ２７０１、ステップＳ２７０４およびステップＳ２７０５の処理は不要となるが、図２８のステップＳ２８０４の探索処理は、各地点間経路が求められるように十分広い範囲で探索処理を実施する必要がある。
なお、図２８のステップＳ２８０４で実施される探索処理で使われる評価値と、コストマトリクスに記録される評価値は必ずしも同一である必要はない。例えば、得られた地点間経路を基に、コストマトリクスに記録する評価値を計算し直しても良い。
【０１５１】
以上のように、本実施形態によれば、各地点間の最小評価値経路を求めた上で、経路上の評価値を２地点間評価値として採用することにより、実際に走行する道路を想定した評価値にすることができるので、違和感のない効率的な巡回経路を求めることができる。
また、本実施形態によれば、各地点（出発地、目的地および各巡回地点）を探索開始点とし、少なくとも出発地側探索処理または目的地側探索処理のどちらか一方を全地点に対して行って、各地点間経路を求めることにより、探索処理回数を最小限に押さえることができるので、全地点間の経路を短時間で選出することができる。
【０１５２】
また、本実施形態によれば、階層化された地図情報を使用し、下位階層において各地点を探索開始点とした探索処理を全地点に対して実施後、接続判断を行い、接続していない経路があれば上位階層に移行して関連する地点の探索処理を続行することにより、その階層に記録された道路網に適した探索範囲を設定することができるので、遠い地点であっても全地点間の経路を短時間で選出することができる。
【０１５３】
また、本実施形態によれば、最後に必要な区間経路を探索し直す事により、各地点間の最小評価値経路を計算する際に経路データを残しておかなくても巡回経路を構成することができるので、車載機上で使用するＲＡＭ容量を削減することができる。
また、本実施形態によれば、各地点間の最小評価値経路を計算する際に経路データを残しておくことにより、この経路データを参照することで巡回経路を構成することができるので、経路構成のために探索処理を実施しなくてすむため、巡回経路選出時間を短縮することができる。
【０１５４】
また、上記第１〜第５の巡回経路選出方法の説明では、深さ優先探索方法を例に採り上げて、最適な巡回経路を求めるようにしていた。しかし、深さ優先探索方法だけでなく、シュミレーテッドアニーリング法（いわゆるＳＡ法）、遺伝アルゴリズム（いわゆるＧＡ法）またはニューラルネット法等、従来から知られている方法に、上記各巡回経路選出方法を適用しても良い。
【０１５５】
なお、第１および第２の実施形態において、各機能ブロックは、ハードウェアによって構成されても良いし、マイクロコンピュータのマルチタスクなどのプログラム処理の結果として構成されても良い。
また、本発明は、プログラムによって実現し、これをフロッピーディスク等の記録媒体に記録して移送することにより、独立した他のコンピュータ・システムで容易に実施することができる。この場合、記録媒体は、フロッピーディスクに限らず、光ディスク、ＩＣカード、ＲＯＭカセット等、プログラムを記録できるものであれば、同様に実施することができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施形態に係るカーナビゲーションシステムの構成を示すブロック図である。
【図２】  本発明の第２の実施形態に係る配送車両管理システムの構成を示すブロック図である。
【図３】  第１の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図４】  図３の地点間経路計算処理（ステップＳ３０３）の詳細な手順を示すフローチャートである。
【図５】  コストマトリクスの一例を示している。
【図６】  図３の巡回順序決定処理（ステップＳ３０４）の詳細な手順を示すフローチャートである。
【図７】  リスト構造を有する管理情報の一例を示している。
【図８】  図６の巡回再帰処理（ステップＳ６０４）の詳細な手順を示すフローチャートである。
【図９】  巡回経路の３つの例を示している。
【図１０】  巡回地点Ｎ１〜Ｎ５が選択された場合に構成されるコストマトリクスを示している。
【図１１】  図８の巡回再帰処理の過程における管理情報の状態遷移を示している。
【図１２】  図８の巡回再帰処理の過程において算出される総巡回コストＹ１および巡回経路ＴＲ２について処理が打ち切られる様子を示している。
【図１３】  図８の巡回再帰処理の過程における管理情報の状態遷移を示している。
【図１４】  網掛けされた観光区域α内に、丸印で表された観光地点ＳＰが予め決められた地点の一例として示されている。
【図１５】  第２の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図１６】  図１５の端地点追加処理（ステップＳ１００４）の詳細な手順を示すフローチャートである。
【図１７】  図１５の出入口地点選択処理（ステップＳ１００６）の詳細な手順を示すフローチャートである。
【図１８】  第３の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図１９】図１８の地点間経路選出処理（ステップＳ１３０８）の詳細な手順を示すフローチャートである。
【図２０】  第４の巡回経路選出方法に係る巡回順序決定処理の詳細な手順を示すフローチャートである。
【図２１】図２０の再帰グループ化処理（ステップＳ１５０２）の詳細な手順を示すフローチャートである。
【図２２】  図２０の再帰グループ化処理によりグループ化された巡回地点Ｎの１例を示している。
【図２３】  図２０の階層的巡回順序決定処理（ステップＳ１５０３）の詳細な手順を示すフローチャートである。
【図２４】  図２３の階層的巡回順序決定処理により求められた最上位階層のグループ間の巡回経路の１例を示している。
【図２５】  図２３の階層的巡回順序決定処理により求められた巡回経路の１例を示している。
【図２６】  第４の巡回経路選出方法の処理手順を示すメインフローチャートである。
【図２７】  図２６の地点間経路計算処理（ステップＳ２６０３）の詳細な手順を示すフローチャートである。
【図２８】  図２７の階層内探索処理（ステップＳ２７０２）の詳細な手順を示すフローチャートである。
【図２９】  図２７の接続判定処理（ステップＳ２７０３）の詳細な手順を示すフローチャートである。
【図３０】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ１→Ｎ２の経路を求める処理を説明するための図である。
【図３１】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ１→Ｎ３の経路を求める処理を説明するための図である。
【図３２】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ２→Ｎ３の経路を求める処理を説明するための図である。
【図３３】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ２→Ｎ１の経路を求める処理を説明するための図である。
【図３４】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ３→Ｎ１の経路を求める処理を説明するための図である。
【図３５】  ２地点間探索の繰り返しにおいて、巡回地点Ｎ３→Ｎ２の経路を求める処理を説明するための図である。
【図３６】  第４の巡回経路選出方法で、巡回地点Ｎ１〜Ｎ３の２地点間の経路を求める処理を説明するための図である。
【図３７】  従来の巡回経路探索方法の処理手順を示すフローチャートである。
【図３８】  従来の他の巡回経路探索方法の処理手順を示すフローチャートである。
【符号の説明】
１０１  ロケーター
１０２  データ記憶部
１０３  操作部
１０４  ナビゲーション装置
１０５  情報提示部
２０１  無線装置
２０２  データ記憶部
２０３  操作部
２０４  コンピュータ
２０５  情報提示部
【図１】
0004421052.tif 000002
【図２】
0004421052.tif 000003
【図３】
0004421052.tif 000004
【図４】
0004421052.tif 000005
【図５】
0004421052.tif 000006
【図６】
0004421052.tif 000007
【図７】
0004421052.tif 000008
【図８】
0004421052.tif 000009
【図９】
0004421052.tif 000010
【図１０】
0004421052.tif 000011
【図１１】
0004421052.tif 000012
【図１２】
0004421052.tif 000013
【図１３】
0004421052.tif 000014
【図１４】
0004421052.tif 000015
【図１５】
0004421052.tif 000016
【図１６】
0004421052.tif 000017
【図１７】
0004421052.tif 000018
【図１８】
0004421052.tif 000019
【図１９】
0004421052.tif 000020
【図２０】
0004421052.tif 000021
【図２１】
0004421052.tif 000022
【図２２】
0004421052.tif 000023
【図２３】
0004421052.tif 000024
【図２４】
0004421052.tif 000025
【図２５】
0004421052.tif 000026
【図２６】
0004421052.tif 000027
【図２７】
0004421052.tif 000028
【図２８】
0004421052.tif 000029
【図２９】
0004421052.tif 000030
【図３０】
0004421052.tif 000031
【図３１】
0004421052.tif 000032
【図３２】
0004421052.tif 000033
【図３３】
0004421052.tif 000034
【図３４】
0004421052.tif 000035
【図３５】
0004421052.tif 000036
【図３６】
0004421052.tif 000037
【図３７】
0004421052.tif 000038
【図３８】
0004421052.tif 000039