(57)【特許請求の範囲】
【請求項１】
経路探索ネットワークを用いて、始点から指定した経由点を通り終点に至る経由経路の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索装置であって、
複数のノードをアークで接続し、各アークにコストを設定した本来の経路探索ネットワークを構築するネットワークデータを格納するデータ格納部と、
前記始点、終点及び経由点の各ノード情報を入力する入力部と、
前記本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第１区間の最小コスト経路と前記経由点ノードから終点ノードまでの第２区間の最小コスト経路を探索して結合し当該結合経路で重複するノードが存在する時、前記本来の経路探索ネットワークにおいて前記第１区間の最小コスト経路で経由点ノードに最も近い前記重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、前記本来の経路探索ネットワークにおいて前記第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する経由最小コスト経路候補生成部と、
該経由最小コスト経路候補生成部で生成した経由最小コスト経路候補を記憶する経由最小コスト経路候補記憶部と、
該経由最小コスト経路候補記憶部に記憶されたコストが最小の経由最小コスト経路候補を経由最小コスト経路情報として出力する出力部と、
を備えて構成したことを特徴とする経由最小コスト経路探索装置。
【請求項２】
前記経由最小コスト経路候補生成部は、
前記入力部で始点、終点及び経由点の各ノード情報が入力されると、前記データ格納部のネットワークデータを基に前記本来の経路探索ネットワークを構築し、前記本来の経路探索ネットワークを基に前記第１区間の最小コスト経路と、前記第２区間の最小コスト経路とをそれぞれ探索すると共に、前記アークカット処理によって構築される前記第１及び第２アークカット経路探索ネットワークに基づいて、前記第１及び第２区間の最小コスト経路をそれぞれ探索する区間最小コスト経路探索手段と、
前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とを結合して前記結合経路を生成する最小コスト経路結合手段と、
前記結合経路に重複するノードが存在するか否かを探索する重複ノード探索手段と、
重複ノードが存在する時に、前記本来の経路探索ネットワークにおいて、前記第１区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークをカット処理し、前記第２区間の最小コスト経路の経由点ノードに最も近い重複ノードから出るアークをカット処理するアークカット処理手段と、
を備え、
前記重複ノード探索手段の探索結果に基づいて、ノードが重複しない結合経路が生成されたときに当該結合経路を前記経由最小コスト経路候補として生成する構成である請求項１に記載の経由最小コスト経路探索装置。
【請求項３】
前記アークカット処理手段は、前記本来の経路探索ネットワークを構築するネットワークデータからカット対象のアークデータを削除して前記第１及び第２アークカット経路探索ネットワークを構築する請求項２に記載の経由最小コスト経路探索装置。
【請求項４】
前記アークカット処理手段は、前記本来の経路探索ネットワークを構築するネットワークデータにおけるカット対象のアークのコストデータを、最小コスト経路探索動作で当該アークを通る経路が選択されないよう大きい値に設定して前記第１及び第２アークカット経路探索ネットワークを構築する請求項２に記載の経由最小コスト経路探索装置。
【請求項５】
前記経由最小コスト経路候補記憶部に、前記経由最小コスト経路候補生成部で生成した全ての経由最小コスト経路候補を記憶し、前記経由最小コスト経路候補記憶部に記憶された全ての経由最小コスト経路候補の中でコストが最小の経由最小コスト経路候補を前記経由最小コスト経路として選択する経由最小コスト経路選択部を設け、該経由最小コスト経路選択部で選択した経由最小コスト経路情報を前記出力部から出力する構成とした請求項１〜４のいずれか１つに記載の経由最小コスト経路探索装置。
【請求項６】
前記経由最小コスト経路候補生成部で経由最小コスト経路候補が生成されたとき、当該生成された経由最小コスト経路候補のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとを比較しコストの小さい経由最小コスト経路候補のみを前記経由最小コスト経路候補記憶部に記憶すると共に、前記経由最小コスト経路候補生成部で生成される前記結合経路のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとの比較結果に基づいて、前記経由最小コスト経路候補よりコストの小さい結合経路が存在しないとき、前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補を前記経由最小コスト経路情報として前記出力部により出力する構成とした請求項１〜４のいずれか１つに記載の経由最小コスト経路探索装置。
【請求項７】
経路探索ネットワークを用いて、始点から指定した経由点を通り終点に至る経由経路の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索方法であって、
前記始点、終点及び経由点の各ノード情報を入力する入力ステップと、
予め格納されたネットワークデータに基づいて構築される、複数のノードをアークで接続し、各アークにコストを設定した本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第１区間の最小コスト経路と前記経由点ノードから終点ノードまでの第２区間の最小コスト経路を結合し当該結合経路で重複するノードが存在する時、前記本来の経路探索ネットワークにおいて前記第１区間の最小コスト経路で経由点ノードに最も近い前記重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、前記本来の経路探索ネットワークにおいて前記第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する経由最小コスト経路候補生成ステップと、
該経由最小コスト経路候補生成ステップで生成した経由最小コスト経路候補を記憶する経由最小コスト経路候補記憶ステップと、
該経由最小コスト経路候補記憶ステップで記憶したコストが最小の経由最小コスト経路候補を経由最小コスト経路情報として出力する出力ステップと、
を備えて構成したことを特徴とする経由最小コスト経路探索方法。
【請求項８】
前記経由最小コスト経路候補生成ステップは、
前記入力ステップで始点、終点及び経由点の各ノード情報が入力されると、前記本来の経路探索ネットワークに基づいて、前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とをそれぞれ探索すると共に、前記アークカット処理によって構築される前記第１及び第２アークカット経路探索ネットワークに基づいて、前記第１及び第２区間の最小コスト経路をそれぞれ探索する区間最小コスト経路探索ステップと、
前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とを結合して前記結合経路を生成する最小コスト経路結合ステップと、
前記結合経路に重複するノードが存在するか否かを探索する重複ノード探索ステップと、
重複ノードが存在する時に、前記第１区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークをカット処理し、前記第２区間の最小コスト経路の経由点ノードに最も近い重複ノードから出るアークをカット処理するアークカット処理ステップと、
を備え、
前記重複ノード探索ステップの探索結果に基づいて、ノードが重複しない結合経路が生成されたときに当該結合経路を前記経由最小コスト経路候補として生成する構成である請求項７に記載の経由最小コスト経路探索方法。
【請求項９】
前記経由最小コスト経路候補記憶ステップは、前記経由最小コスト経路候補生成ステップで生成した全ての経由最小コスト経路候補を記憶し、経由最小コスト経路候補記憶ステップで記憶された全ての経由最小コスト経路候補の中でコストが最小の経由最小コスト経路候補を前記経由最小コスト経路として選択する経由最小コスト経路選択ステップを設け、該経由最小コスト経路選択ステップで選択した経由最小コスト経路情報を前記出力ステップで出力する構成とした請求項７又は８に記載の経由最小コスト経路探索方法。
【請求項１０】
前記経由最小コスト経路候補記憶ステップは、前記経由最小コスト経路候補生成ステップで経由最小コスト経路候補が生成される度に、当該生成された経由最小コスト経路候補のコストと既に記憶されている経由最小コスト経路候補のコストとを比較してコストの小さい経由最小コスト経路候補のみを記憶する構成であり、前記出力ステップは、前記経由最小コスト経路候補生成部で生成される前記結合経路のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとの比較結果に基づいて前記経由最小コスト経路候補よりコストの小さい結合経路が存在しないとき、前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補を前記経由最小コスト経路情報として出力する構成である請求項７又は８に記載の経由最小コスト経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードをアークで接続し各アークにコストを設定した経路探索ネットワークを用いて、経路を重複せずに、始点から指定した経由点を通り終点に至る経路（以下、経由経路とする）の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索装置及び経由最小コスト経路探索方法に関する。
【背景技術】
【０００２】
この種の経由最小コスト経路探索の一例としては、例えば、乗継駅を指定して出発駅と到着駅間の鉄道運賃を計算する鉄道運賃計算がある。鉄道運賃計算は、例えば、駅をノード、駅間を結ぶ線路をアーク、アークのコストを距離とした経路探索ネットワークを用い、出発駅を始点ノード、到着駅を終点ノード、乗継駅を経由点ノードとして設定し、始点ノードと終点ノード間で経路を重複することなく経由点ノードを通る経由経路の中でコストが最小となる経路を探索し、探索した経由経路の距離を運賃に換算して運賃を算出する。このような重複経路なしに指定した経由点ノードを通り且つコストが最小となる経由最小コスト経路を探索する従来手法としては、例えば特許文献１に記載されたものがある。
【０００３】
特許文献１に記載された手法は、始点ノードと終点ノード間を、始点ノードと経由点ノードまでの区間と経由点ノードと終点ノードまでの区間に分割し、各区間で最小コスト経路を探索する。次に、各区間の探索経路を結合し、結合経路に重複する経路が存在する場合に、始点ノードから経由点ノードまでの区間と経由点ノードから終点ノードまでの区間についてそれぞれ複数の経路を算出し、各区間毎に算出した複数の経路同士を重複経路がないように組合わせて始点ノードから経由点ノードを通り終点ノードに至る経由経路を生成し、生成した複数の経由経路の中でコストが最小となる経路を経由最小コスト経路として選択するようにしている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−５４２３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載された従来手法では、経由最小コスト経路として最終的に選択した経由経路が、確実にコスト最小の経由経路であるという保証が得られるのは、分割したそれぞれの区間において２つのノード間に存在する経路を全て算出する場合である。しかも、各区間で算出した全経路同士を、重複する経路がないよう組み合わせなければならない。このため、各区間の２つのノード間に存在する経路数が多い場合には、最終的な経由最小コスト経路を探索するには処理時間がかかるという問題がある。
【０００６】
本発明は上記問題点に着目してなされたもので、経路の重複なしに始点から指定した経由点を通り終点に至る最小コストの経由経路の探索処理時間を大幅に短縮できる経由最小コスト経路探索装置及び経由最小コスト経路探索方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
このため、請求項１に記載の発明は、経路探索ネットワークを用いて、始点から指定した経由点を通り終点に至る経由経路の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索装置であって、複数のノードをアークで接続し、各アークにコストを設定した本来の経路探索ネットワークを構築するネットワークデータを格納するデータ格納部と、前記始点、終点及び経由点の各ノード情報を入力する入力部と、前記本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第１区間の最小コスト経路と前記経由点ノードから終点ノードまでの第２区間の最小コスト経路を探索して結合し当該結合経路で重複するノードが存在する時、前記本来の経路探索ネットワークにおいて前記第１区間の最小コスト経路で経由点ノードに最も近い前記重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、前記本来の経路探索ネットワークにおいて前記第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する経由最小コスト経路候補生成部と、該経由最小コスト経路候補生成部で生成した経由最小コスト経路候補を記憶する経由最小コスト経路候補記憶部と、該経由最小コスト経路候補記憶部に記憶されたコストが最小の経由最小コスト経路候補を経由最小コスト経路情報として出力する出力部と、を備えて構成したことを特徴とする。
【０００８】
かかる構成では、入力部で始点、終点及び経由点の各ノード情報を入力すると、経由最小コスト経路候補生成部は、データ格納部に格納されたネットワークデータを用いて構築される本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第１区間の最小コスト経路と経由点ノードから終点ノードまでの第２区間の最小コスト経路を探索して結合し、この結合経路で重複するノードが存在する時、本来の経路探索ネットワークにおいて第１区間の最小コスト経路で経由点ノードに最も近い重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、本来の経路探索ネットワークにおいて第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する。経由最小コスト経路候補生成部で生成した経由最小コスト経路候補は、経由最小コスト経路候補記憶部で記憶し、出力部から経由最小コスト経路候補記憶部で記憶されたコストが最小の経由最小コスト経路候補を経由最小コスト経路として出力する。
【０００９】
前記経由最小コスト経路候補生成部は、具体的には、請求項２のように、前記入力部で始点、終点及び経由点の各ノード情報が入力されると、前記データ格納部のネットワークデータを基に前記本来の経路探索ネットワークを構築し、前記本来の経路探索ネットワークを基に前記第１区間の最小コスト経路と、前記第２区間の最小コスト経路とをそれぞれ探索すると共に、前記アークカット処理によって構築される前記第１及び第２アークカット経路探索ネットワークに基づいて、前記第１及び第２区間の最小コスト経路をそれぞれ探索する区間最小コスト経路探索手段と、前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とを結合して前記結合経路を生成する最小コスト経路結合手段と、前記結合経路に重複するノードが存在するか否かを探索する重複ノード探索手段と、重複ノードが存在する時に、前記本来の経路探索ネットワークにおいて、前記第１区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークをカット処理し、前記第２区間の最小コスト経路の経由点ノードに最も近い重複ノードから出るアークをカット処理するアークカット処理手段と、を備え、前記重複ノード探索手段の探索結果に基づいて、ノードが重複しない結合経路が生成されたときに当該結合経路を前記経由最小コスト経路候補として生成する構成とするとよい。
【００１０】
前記アークカット処理手段は、請求項３のように、前記本来の経路探索ネットワークを構築するネットワークデータからカット対象のアークデータを削除して前記第１及び第２アークカット経路探索ネットワークを構築する構成でもよく、請求項４のように、前記本来の経路探索ネットワークを構築するネットワークデータにおけるカット対象のアークのコストデータを、最小コスト経路探索動作で当該アークを通る経路が選択されないよう大きい値に設定して前記第１及び第２アークカット経路探索ネットワークを構築する構成でもよい。
【００１１】
請求項５のように、前記経由最小コスト経路候補記憶部に、前記経由最小コスト経路候補生成部で生成した全ての経由最小コスト経路候補を記憶し、前記経由最小コスト経路候補記憶部に記憶された全ての経由最小コスト経路候補の中でコストが最小の経由最小コスト経路候補を前記経由最小コスト経路として選択する経由最小コスト経路選択部を設け、該経由最小コスト経路選択部で選択した経由最小コスト経路情報を前記出力部から出力する構成とするとよい。
【００１２】
また、請求項６のように、前記経由最小コスト経路候補生成部で経由最小コスト経路候補が生成されたとき、当該生成された経由最小コスト経路候補のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとを比較しコストの小さい経由最小コスト経路候補のみを前記経由最小コスト経路候補記憶部に記憶すると共に、前記経由最小コスト経路候補生成部で生成される前記結合経路のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとの比較結果に基づいて、前記経由最小コスト経路候補よりコストの小さい結合経路が存在しないとき、前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補を前記経由最小コスト経路情報として前記出力部により出力する構成とするとよい。
【００１３】
請求項７に記載の発明は、経路探索ネットワークを用いて、始点から指定した経由点を通り終点に至る経由経路の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索方法であって、前記始点、終点及び経由点の各ノード情報を入力する入力ステップと、予め格納されたネットワークデータに基づいて構築される、複数のノードをアークで接続し、各アークにコストを設定した本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第１区間の最小コスト経路と前記経由点ノードから終点ノードまでの第２区間の最小コスト経路を結合し当該結合経路で重複するノードが存在する時、前記本来の経路探索ネットワークにおいて前記第１区間の最小コスト経路で経由点ノードに最も近い前記重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、前記本来の経路探索ネットワークにおいて前記第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する経由最小コスト経路候補生成ステップと、該経由最小コスト経路候補生成ステップで生成した経由最小コスト経路候補を記憶する経由最小コスト経路候補記憶ステップと、該経由最小コスト経路候補記憶ステップで記憶したコストが最小の経由最小コスト経路候補を経由最小コスト経路情報として出力する出力ステップと、を備えて構成したことを特徴とする。
【００１４】
前記経由最小コスト経路候補生成ステップは、具体的には請求項８のように、前記入力ステップで始点、終点及び経由点の各ノード情報が入力されると、前記本来の経路探索ネットワークに基づいて、前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とをそれぞれ探索すると共に、前記アークカット処理によって構築される前記第１及び第２アークカット経路探索ネットワークに基づいて、前記第１及び第２区間の最小コスト経路をそれぞれ探索する区間最小コスト経路探索ステップと、前記第１区間の最小コスト経路と前記第２区間の最小コスト経路とを結合して前記結合経路を生成する最小コスト経路結合ステップと、前記結合経路に重複するノードが存在するか否かを探索する重複ノード探索ステップと、重複ノードが存在する時に、前記第１区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークをカット処理し、前記第２区間の最小コスト経路の経由点ノードに最も近い重複ノードから出るアークをカット処理するアークカット処理ステップと、を備え、前記重複ノード探索ステップの探索結果に基づいて、ノードが重複しない結合経路が生成されたときに当該結合経路を前記経由最小コスト経路候補として生成する構成とするとよい。
【００１５】
請求項９のように、前記経由最小コスト経路候補記憶ステップは、前記経由最小コスト経路候補生成ステップで生成した全ての経由最小コスト経路候補を記憶し、経由最小コスト経路候補記憶ステップで記憶された全ての経由最小コスト経路候補の中でコストが最小の経由最小コスト経路候補を前記経由最小コスト経路として選択する経由最小コスト経路選択ステップを設け、該経由最小コスト経路選択ステップで選択した経由最小コスト経路情報を前記出力ステップで出力する構成とするとよい。
【００１６】
請求項１０のように、前記経由最小コスト経路候補記憶ステップは、前記経由最小コスト経路候補生成ステップで経由最小コスト経路候補が生成される度に、当該生成された経由最小コスト経路候補のコストと既に記憶されている経由最小コスト経路候補のコストとを比較してコストの小さい経由最小コスト経路候補のみを記憶する構成であり、前記出力ステップは、前記経由最小コスト経路候補生成部で生成される前記結合経路のコストと前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補のコストとの比較結果に基づいて前記経由最小コスト経路候補よりコストの小さい結合経路が存在しないとき、前記経由最小コスト経路候補記憶部に記憶されている経由最小コスト経路候補を前記経由最小コスト経路情報として出力する構成とするとよい。
【発明の効果】
【００１７】
本発明によれば、始点から終点までを、始点から経由点までの区間（第１区間）と経由点から終点までの区間（第２区間）に分割し、それぞれの区間で最小コスト経路を探索して結合し、結合した経路において重複経路が存在する場合に、重複経路のない経由経路が求まるまで、重複経路を除外するように予め定めたアークカット条件に従って所定のアークのカット処理を繰返し行うことにより、重複経路のない経由最小コスト経路を探索する構成としたので、従来の経由最小コスト経路探索装置に比べて、重複経路のない経由最小コスト経路の探索処理時間を短縮することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明に係る経由最小コスト経路探索装置の一実施形態の構成を示すブロック図。
【図２】経由最小コスト経路探索動作を説明するフローチャート。
【図３】本来の経路探索ネットワークの一例を示す図。
【図４】図３の経路探索ネットワークから求めたノードの重複を考慮しない経由最小コスト経路を示す図。
【図５】第１アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図６】第２アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図７】本来の経路探索ネットワークの別の例を示す図。
【図８】図７の経路探索ネットワークから求めたノードの重複を考慮しない経由最小コスト経路を示す図。
【図９】第１アークカット経路探索ネットワークから求めた経由最小コスト経路を示す図。
【図１０】第２アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図１１】図９の経路ネットワークに基づく第１アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図１２】図９の経路ネットワークに基づく第２アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図１３】本来の経路探索ネットワークの更に別の例を示す図。
【図１４】図１３の経路探索ネットワークから求めたノードの重複を考慮しない経由最小コスト経路を示す図。
【図１５】アークカット処理後の第１アークカット経路探索ネットワークを示す図。
【図１６】アークカット処理後の第２アークカット経路探索ネットワークを示す図。
【図１７】本来の経路探索ネットワークの更に別の例を示す図。
【図１８】図１７の経路探索ネットワークから求めたノードの重複を考慮しない経由最小コスト経路を示す図。
【図１９】アークカット処理後の第１アークカット経路探索ネットワークを示す図。
【図２０】第２アークカット経路探索ネットワークから求めた重複ノードのない経由最小コスト経路候補を示す図。
【図２１】本発明に係る経由最小コスト経路探索装置の別の実施形態の構成を示すブロック図。
【図２２】図２１の実施形態装置の経由最小コスト経路探索動作を説明するフローチャート。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面に基づいて説明する。
図１は、本発明に係る経由最小コスト経路探索装置の一実施形態の構成を示すブロック図である。
【００２０】
図１において、本実施形態の経由最小コスト経路探索装置１は、入力部２と、データストレージ装置３と、経由経路データ生成部４と、経由最小コスト経路データ選択部５と、出力部６と、を備えて構成される。ここで、経由最小コスト経路探索装置１は、例えばコンピュータで構成され、前記経由経路データ生成部４及び経由最小コスト経路データ選択部５の機能はソフトウエア的に備えられるものである。
【００２１】
前記入力部２は、始点となる出発点、終点となる到着点及び経由点等のノード情報を入力するものである。
【００２２】
前記データストレージ装置３は、複数のノードをアークで接続し、各アークにコスト（例えば距離、運賃等）を設定した本来の経路探索ネットワークを構築するためのネットワークデータを格納するネットワークデータ格納部３Ａと、後述するカット対象アークデータ生成手段４Ｄによって生成されるカット対象のアークデータを格納するアークデータ格納部３Ｂと、経由経路データ生成部４において生成される経由最小コスト経路候補の経由経路データを格納する経由経路データ格納部３Ｃとを備える。ここで、前記ネットワークデータ格納部３Ａがデータ格納部に相当し、経由経路データ格納部３Ｃが経由最小コスト経路候補記憶部に相当する。
【００２３】
前記経由経路データ生成部４は、データストレージ装置３内のネットワークデータ格納部３Ａに格納されたネットワークデータにより構築される本来の経路探索ネットワークに基づいて、入力された出発点ノードから経由点ノードまでの第１区間の最小コスト経路と経由点ノードから到着点ノードまでの第２区間の最小コスト経路を探索して結合し当該結合経路で重複するノードが存在する時、本来の経路探索ネットワークにおいて第１区間の最小コスト経路で経由点ノードに最も近い重複ノードへ入るアークをカット処理して構築した第１アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、本来の経路探索ネットワークにおいて第２区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第２アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成するもので、２ノード間最小コスト経路データ生成手段４Ａと、最小コスト経路データ結合手段４Ｂと、重複ノード探索手段４Ｃと、カット対象アークデータ生成手段４Ｄと、アークカット手段４Ｅとを備える。ここで、経由経路データ生成部４が経由最小コスト経路候補生成部に相当する。
【００２４】
前記２ノード間最小コスト経路データ生成手段４Ａは、入力部２で出発点、到着点及び経由点の各ノード情報が入力されると、ネットワークデータ格納部３Ａのネットワークデータを基に本来の経路探索ネットワークを構築し、この本来の経路探索ネットワークを基に第１区間の最小コスト経路と、第２区間の最小コスト経路とをそれぞれ探索して各区間の最小コスト経路データを生成すると共に、アークカット処理によって構築される第１及び第２アークカット経路探索ネットワークに基づいて、第１及び第２区間の最小コスト経路をそれぞれ探索してアークカット処理後の各区間における最小コスト経路データを生成するもので、区間最小コスト経路探索手段に相当する。各区間における最小コスト経路の算出方法は、例えばダイクストラ法等の最短経路探索アルゴリズムを用いることができる。
【００２５】
前記最小コスト経路データ結合手段４Ｂは、２ノード間最小コスト経路データ生成手段４Ａで生成される第１区間の最小コスト経路データと第２区間の最小コスト経路データとを結合して結合経路データを生成するもので、最小コスト経路結合手段に相当する。
【００２６】
前記重複ノード探索手段４Ｃは、最小コスト経路データ結合手段４Ｂの結合経路データに重複するノードが存在するか否かを探索するものである。
【００２７】
カット対象アークデータ生成手段４Ｄは、重複ノード探索手段４Ｃの探索処理において重複ノードが存在する時に、本来の経路探索ネットワークにおいて、第１区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークと、第２区間の最小コスト経路の経由点ノードに最も近い重複ノードから出るアークとを、それぞれカット対象のアークデータとして生成するものである。
【００２８】
前記アークカット手段４Ｅは、前記カット対象アークデータ生成手段４Ｄによって生成されたカット対象アークデータに基づいて、本来の経路探索ネットワークにおいてカット対象のアークをカットして第１及び第２アークカット経路探索ネットワークを構築するためのネットワークデータとするものである。アークカット手段４Ｅによるアークカット方法としては、例えば、本来の経路探索ネットワーク構築用データにおいて、カット対象のアークデータを削除して第１及び第２アークカット経路探索ネットワーク構築用データとしてもよく、また、カット対象のアークのコストデータを、最小コスト経路探索動作でカット対象のアークを通る経路が選択されないよう極端に大きい値に設定して第１及び第２アークカット経路探索ネットワーク構築用データとするようにしてもよい。ここで、前記カット対象アークデータ生成手段４Ｄとアークカット手段４Ｅとでアークカット処理手段が構成される。
【００２９】
前記経由最小コスト経路データ選択部５は、経由経路データ格納部３Ｃに記憶された重複ノードの存在しない複数の経由最小コスト経路候補の中でコストが最小の経由最小コスト経路候補を経由最小コスト経路として選択するもので、経由最小コスト経路選択部に相当する。尚、経由経路データ格納部３Ｃに記憶された重複ノードの存在しない経由最小コスト経路候補が１つの場合は、その経由最小コスト経路候補を経由最小コスト経路として選択する。また、経由経路データ格納部３Ｃに記憶された重複ノードの存在しない経由最小コスト経路候補がない場合には、選択する経由最小コスト経路なしとする。
【００３０】
前記出力部６は、経由最小コスト経路データ選択部５で選択された経由最小コスト経路のデータ（ノード、アーク及びコスト等のデータ）を出力するものである。尚、経由最小コスト経路データ選択部５で選択される経由最小コスト経路が存在しないときには、例えば、出力部６からは、該当経由最小コスト経路なしの情報を出力するか、或いは、既に探索済みの重複ノードを考慮しない経由最小コスト経路の情報を出力するようにする。
【００３１】
次に、本実施形態の経由最小コスト経路探索装置１による経由最小コスト経路探索動作を、図２のフローチャートと図３に示す経路探索ネットワークを参照して説明する。
【００３２】
ステップＳ１で、入力部２において、出発点、到着点及び経由点の各データを入力する。このステップＳ１が入力ステップに相当する。
ステップＳ２では、ネットワークデータ格納部３Ａ内のネットワークデータで構築される図３に示す本来の経路探索ネットワークに基づいて、経由経路データ生成部４の２ノード間最小コスト経路データ生成部４Ａにより、出発点ノードｓから経由点ノードｖまでの第１区間及び経由点ノードｖから到着点ノードｔまでの第２区間における最小コスト経路をそれぞれ探索する。探索の結果、前記第１区間における最小コスト経路はノードｓ→ノード２→ノードｖの経路でコストは３であり、前記第２区間における最小コスト経路はノードｖ→ノード２→ノードｔの経路でコストは３である。
【００３３】
ステップＳ３では、最小コスト経路データ結合手段４Ｂにより、ステップＳ２で探索された各区間の最小コスト経路を結合する。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図４に点線矢印で示すノードｓ→ノード２→ノードｖ→ノード２→ノードｔという結合経路が得られる。
【００３４】
ステップＳ４で、重複ノード探索手段４Ｃにより、ステップＳ３で生成された結合経路ノードｓ→ノード２→ノードｖ→ノード２→ノードｔに重複するノードが存在するか否かを探索する。この場合、前記結合経路ノードｓ→ノード２→ノードｖ→ノード２→ノードｔではノード２が重複しており、重複ノードありとしてステップＳ５に進む。尚、図３の経路探索ネットワークの例では、ステップＳ２で得られる最小コスト経路は各区間でそれぞれ１つであるが、経路探索ネットワークによっては各区間で複数得られる場合がある。この場合、ステップＳ３で得られる結合経路が複数存在し、結合経路が複数存在する場合、ステップＳ４では、重複ノードを含まない結合経路が少なくとも１つ存在する場合に重複ノードなしと判定し後述するステップＳ７に進み、全ての結合経路が重複ノードを含む場合に重複ノードありと判定しステップＳ５に進む。
【００３５】
ステップＳ５では、カット対象アークデータ生成手段４Ｄにより、カットするアークデータを生成する。ここで、アークのカット条件としては、下記に示すＡ）とＢ）の２つの条件とする。
Ａ）始点ノードから経由点ノードまで（第１区間）の最小コスト経路を構成するアーク
の中で、経由点ノードに一番近い重複ノードへ入るアーク。
Ｂ）経由点ノードから終点ノードまで（第２区間）の最小コスト経路を構成するアーク
の中で、経由点ノードに一番近い重複ノードから出るアーク。
条件Ａ）から、図４の結合経路における重複ノード２に入るアークをカット対象アークデータとして生成し、条件Ｂ）から、図４の結合経路における重複ノード２から出るアークをカット対象アークデータとして生成する。これら生成したカット対象のアークデータをアークデータ格納部３Ｂに格納する。
【００３６】
ステップＳ６では、アークカット手段４Ｅにより、アークデータ格納部３Ｂのカット対象アークデータに従ってこれらアークのカット処理を行う。具体的には、例えば、第１区間のカット対象アークを本来の経路探索ネットワークから取除いて図５に示すような第１アークカット経路探索ネットワークを構築するためのネットワークデータとすると共に、第２区間のカット対象アークを本来の経路探索ネットワークから取除いて図６に示すような第２アークカット経路探索ネットワークを構築するためのネットワークデータとする。図５及び図６において、カット対象のアークを点線で示してある。この点線で示したアークは、実際にはネットワーク上では存在しない。
【００３７】
尚、アークのカット処理手法として、例えば、カット対象のアークのコストを極端に大きい値に設定することにより、最小コスト経路探索動作でカット対象のアークを通る経路が選択されないようにしてもよい。
【００３８】
次に、ステップＳ２に戻り、図５の第１アークカット経路探索ネットワークと図６の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する。探索の結果、図５の第１アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路はノードｓ→ノード１→ノード４→ノード５→ノードｖでコスト７の経路が得られ、第２区間の最小コスト経路は前述した本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｖ→ノード２→ノードｔ）でコスト３の経路が得られる。また、図６の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路は前述した本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｓ→ノード２→ノードｖ）でコスト３の経路が得られ、第２区間の最小コスト経路はノードｖ→ノード５→ノード７→ノード３→ノードｔの経路でコスト８の経路が得られる。
【００３９】
次に、ステップＳ３で、前述と同様に、最小コスト経路データ結合手段４Ｂにより、ステップＳ２で探索された各区間の最小コスト経路を結合する。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図５の第１アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１→ノード４→ノード５→ノードｖ→ノード２→ノードｔでコスト１０の結合経路が得られる。また、図６の第２アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード２→ノードｖ→ノード５→ノード７→ノード３→ノードｔでコスト１１の結合経路が得られる。
【００４０】
次に、ステップＳ４で、ステップＳ３で得られた結合経路に重複するノードが存在するか否かをそれぞれ探索する。この場合、結合経路ノードｓ→ノード１→ノード４→ノード５→ノードｖ→ノード２→ノードｔと結合経路ノードｓ→ノード２→ノードｖ→ノード５→ノード７→ノード３→ノードｔのいずれにも重複ノードが存在しない。従って、このように重複ノードが存在しない結合経路が探索された場合、重複ノードなしとしてステップＳ７に進む。
【００４１】
このように、重複経路のない経由経路が求まるまで、予め定めたアークカット条件に従って所定のアークのカット処理を繰返し行って重複経路のない経由最小コスト経路候補を求めることで、無駄のない経由最小コスト経路の探索を行う。
【００４２】
ステップＳ７では、これら両結合経路を経由最小コスト経路候補として経由経路データ格納部３Ｃに格納する。このステップＳ７が経由最小コスト経路候補記憶ステップに相当する。
【００４３】
ステップＳ８では、重複ノードを含む結合経路の有無を判定し、重複ノードを含む結合経路が１つでもあれば判定が経路有りとなりステップＳ５に進み、重複ノードを含む結合経路が存在しなければステップＳ９に進む。図５及び図６の例では、両結合経路がどちらも重複ノードを含んでいないため、ステップＳ８の判定が経路無しとなりステップＳ９に進むことになる。従って、前述のステップＳ２〜ステップＳ６とステップＳ８が経由最小コスト経路候補生成ステップに相当する。
【００４４】
ステップＳ９では、経路最小コスト経路データ選択部５により、経由経路データ格納部３Ｃに格納された経由最小コスト経路候補の中でコスト最小のものを経由最小コスト経路として選択する。この場合、ノードｓ→ノード１→ノード４→ノード５→ノードｖ→ノード２→ノードｔの経路のコストは１０であり、結合経路ノードｓ→ノード２→ノードｖ→ノード５→ノード７→ノード３→ノードｔのコストは１１である。従って、経由最小コスト経路として図５の経路ノードｓ→ノード１→ノード４→ノード５→ノードｖ→ノード２→ノードｔが選択される。このステップＳ９が経由最小コスト経路選択ステップに相当する。
【００４５】
ステップＳ１０では、選択した経由最小コスト経路ノードｓ→ノード１→ノード４→ノード５→ノードｖ→ノード２→ノードｔの経路データ（コスト１０のコストデータも含む）を出力部６から出力する。このステップＳ１０が出力ステップに相当する。
【００４６】
次に、図７に示す別の経路探索ネットワークを用いて、アークカット処理後の結合経路でも重複経路が存在する場合の経由最小コスト経路探索動作について図２のフローチャートを参照して説明する。
【００４７】
図７に示す本来の経路探索ネットワークに基づいて、出発点ノードｓから経由点ノードｖまでの第１区間及び経由点ノードｖから到着点ノードｔまでの第２区間における最小コスト経路をそれぞれ探索する（ステップＳ２）。探索の結果、前記第１区間における最小コスト経路はノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖの経路でコストは７であり、前記第２区間における最小コスト経路はノードｖ→ノード４→ノード１→ノード２→ノードｔの経路でコストは４である。
【００４８】
次に、上記の第１区間と第２区間のそれぞれの最小コスト経路を結合する（ステップＳ３）。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図８に点線で示すノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード４→ノード１→ノード２→ノードｔという結合経路が得られる。
【００４９】
次に、生成された結合経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード４→ノード１→ノード２→ノードｔに重複するノードが存在するか否かを探索する（ステップＳ４）。この場合、ノード４とノード１が重複する。
【００５０】
前述のアークカット条件Ａ）により、図８の結合経路における経由点ノードｖに一番近い重複ノード４に入るアークをカット対象アークデータとして生成する。また、アークカット条件Ｂ）により、図８の結合経路における経由点ノードｖに一番近い重複ノード４から出るアークをカット対象アークデータとして生成し、アークデータ格納部３Ｂに格納する（ステップＳ５）。
【００５１】
次に、アークデータ格納部３Ｂのカット対象アークデータに従ってアークのカット処理を行う。例えば、第１区間のカット対象アークを本来の経路探索ネットワークから取除いて図９に示すような第１アークカット経路探索ネットワークを構築するためのネットワークデータとすると共に、第２区間のカット対象アークを本来の経路探索ネットワークから取除いて図１０に示すような第２アークカット経路探索ネットワークを構築するためのネットワークデータとする（ステップＳ６）。図９及び図１０において、カット対象のアークを点線で示してある。この点線で示したアークは、実際にはネットワーク上では存在しない。
【００５２】
次に、図９の第１アークカット経路探索ネットワークと図１０の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する（ステップＳ２）。探索の結果、図９の第１アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路はノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖでコスト８の経路が得られる。また、第２区間の最小コスト経路は前述した本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｖ→ノード４→ノード１→ノード２→ノードｔ）でコスト４の経路が得られる。また、図１０の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路は前述した本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ）でコスト７の経路が得られ、第２区間の最小コスト経路はノードｖ→ノード８→ノード５→ノード２→ノードｔの経路でコスト５の経路が得られる。
【００５３】
次に、第１及び第２アークカット経路探索ネットワーク上で探索された各区間の最小コスト経路を結合する（ステップＳ３）。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図９の第１アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード４→ノード１→ノード２→ノードｔでコスト１２の結合経路が得られる。また、図１０の第２アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔでコスト１２の結合経路が得られる。
【００５４】
次に、それぞれの結合経路について重複するノードが存在するか否かを探索する（ステップＳ４）。ここで、図１０の第２アークカット経路探索ネットワーク上で得られた結合経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔは重複するノードが存在しない。従って、経由最小コスト経路候補としてその経由経路データを経由経路データ格納部３Ｃに格納する（ステップＳ７）。一方、図９の第１アークカット経路探索ネットワーク上で得られた結合経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード４→ノード１→ノード２→ノードｔでは、ノード２が重複している。従って、ステップ８の判定が経路有りとなり、この結合経路について、再度、アークカット処理を行う（ステップＳ５，６）。
【００５５】
アークカット条件Ａ）により、図９の結合経路における重複ノード２に入るアークをカット対象アークデータとして生成し、アークカット条件Ｂ）により、図９の結合経路における重複ノード２から出るアークをカット対象アークデータとして生成し、アークデータ格納部３Ｂに格納する（ステップＳ５）。
【００５６】
次に、アークデータ格納部３Ｂのカット対象アークデータに従って、図９の第１アークカット経路探索ネットワークにおいて重複ノード２に入るアークを取除いて図１１に示すような第１アークカット経路探索ネットワークを構築するためのネットワークデータを生成すると共に、重複ノード２から出るアークを取除いて図１２に示すような第２アークカット経路探索ネットワークを構築するためのネットワークデータとする（ステップＳ６）。
【００５７】
次に、図１１の第１アークカット経路探索ネットワークと図１２の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する（ステップＳ２）。探索の結果、図１１の第１アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路はノードｓ→ノード３→ノード７→ノードｖでコスト９の経路が得られ、第２区間の最小コスト経路は前述した本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｖ→ノード４→ノード１→ノード２→ノードｔ）でコスト４の経路が得られる。また、図１２の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路は図１１の第１アークカット経路探索ネットワークと同じ経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖでコスト８の経路が得られ、第２区間の最小コスト経路はノードｖ→ノード１５→ノード１６→ノード１７→ノード９→ノード６→ノードｔの経路でコスト１０の経路が得られる。
【００５８】
次に、図１１と図１２の第１及び第２アークカット経路探索ネットワーク上で探索された各区間の最小コスト経路を結合する（ステップＳ３）。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図１１の第１アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード３→ノード７→ノードｖ→ノード４→ノード１→ノード２→ノードｔでコスト１３の結合経路が得られる。また、図１２の第２アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード１５→ノード１６→ノード１７→ノード９→ノード６→ノードｔでコスト１８の結合経路が得られる。
【００５９】
それぞれの結合経路について、再度、重複する経路が存在するか否かを探索する（ステップＳ４）。ここで、いずれの経由経路も重複するノードがないことから、これら経由経路を経由最小コスト経路候補としてその経由経路データを経由経路データ格納部３Ｃに格納する（ステップＳ７）。
【００６０】
そして、これ以上重複ノードが存在する経由経路が存在しないことからステップＳ８で判定が経路無しとなり、これまでに経由経路データ格納部３Ｃに格納された経由最小コスト経路候補の中から最小コストの経由経路を選択する（ステップＳ９）。この例では、経由経路データ格納部３Ｃには３つの経由最小コスト経路候補が格納されている。即ち、図１０に点線矢印で示した経由経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔと、図１１に点線矢印で示した経由経路ノードｓ→ノード３→ノード７→ノードｖ→ノード４→ノード１→ノード２→ノードｔと、図１２に点線矢印で示した経由経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード１５→ノード１６→ノード１７→ノード９→ノード６→ノードｔである。そして、これら３つの経由経路の中でコストが最小のものを経由最小コスト経路として選択する。図１０に示した経由経路のコストは１２であり、図１１に示した経由経路のコストは１３であり、図１２に示した経由経路のコストは１８である。従って、経由最小コスト経路として図１０の経由経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔを選択し、この経由経路データを出力部６から出力することになる（ステップＳ１０）。
【００６１】
上記の各実施形態は、第１及び第２アークカット経路探索ネットワークにおいて、ノードの重複しない経由最小コスト経路候補がそれぞれ存在する例を示したが、必ずしも第１及び第２アークカット経路探索ネットワーク上に経由最小コスト経路候補が存在するとは限らない。以下にそのような例について説明する。
【００６２】
図１３に示す経路探索ネットワークを用いて、第１及び第２アークカット経路探索ネットワークのいずれにも経由最小コスト経路候補が存在しない場合の例について図２のフローチャートを参照して説明する。
【００６３】
図１３に示す本来の経路探索ネットワークに基づいて、出発点ノードｓから経由点ノードｖまでの第１区間及び経由点ノードｖから到着点ノードｔまでの第２区間における最小コスト経路をそれぞれ探索し（ステップＳ２）、探索したそれぞれの最小コスト経路を結合すると（ステップＳ３）、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図１４に点線で示すノードｓ→ノード４→ノードｖ→ノード４→ノードｔという結合経路が得られる。
【００６４】
生成された結合経路ノードｓ→ノード４→ノードｖ→ノード４→ノードｔには、重複ノードとしてノード４が存在するのでステップＳ４の判定が重複ノードありとなり、前述と同様にしてアークカット処理を実行し、アークカット条件Ａ）から第１アークカット経路探索ネットワークデータを生成し、アークカット条件Ｂ）から第２アークカット経路探索ネットワークデータを生成する（ステップＳ５、Ｓ６）。生成されたネットワークデータから得られる第１アークカット経路探索ネットワークを図１５に示し、第２アークカット経路探索ネットワークを図１６に示す。尚、カット対象のアークを図中に点線で示してある。この点線で示したアークは、実際にはネットワーク上では存在しない。
【００６５】
図１５の第１アークカット経路探索ネットワークと図１６の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する（ステップＳ２）。探索の結果、図１５の第１アークカット経路探索ネットワークでは出発点ノードｓから経由点ノードｖに至る経路が存在しない。また、図１６の第２アークカット経路探索ネットワークでは経由点ノードｖから到着点ノードｔに至る経路が存在しない。このため、第１及び第２アークカット経路探索ネットワークそれぞれにおいて第１区間と第２区間の最小コスト経路の結合経路として得られる、重複ノードの存在しない経由最小コスト経路候補は、第１及び第２アークカット経路探索ネットワークのいずれにも存在しない。
【００６６】
尚、この場合、経由経路データ格納部３Ｃに記憶される経由最小コスト経路候補の経路データがないので、経由最小コスト経路データ選択部５では経由最小コスト経路存在なしと判断し、例えば、出力部６からは、該当経由最小コスト経路なしの情報を出力するか、或いは、既に探索済みの重複ノードを考慮しない経由最小コスト経路の情報を出力するようにする（ステップＳ１０）。
【００６７】
次に、図１７に示す経路探索ネットワークを用いて、経由最小コスト経路候補が１つしか存在しない場合の例について説明する。
【００６８】
図１７に示す本来の経路探索ネットワークに基づいて、出発点ノードｓから経由点ノードｖまでの第１区間及び経由点ノードｖから到着点ノードｔまでの第２区間における最小コスト経路をそれぞれ探索し（ステップＳ２）、探索したそれぞれの最小コスト経路を結合すると（ステップＳ３）、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図１８に点線で示すノードｓ→ノード４→ノードｖ→ノード４→ノードｔという結合経路が得られる。
【００６９】
生成された結合経路ノードｓ→ノード４→ノードｖ→ノード４→ノードｔには、重複ノードとしてノード４が存在するのでステップＳ４の判定が重複ノードありとなり、前述と同様にしてアークカット処理を実行し、アークカット条件Ａ）から第１アークカット経路探索ネットワークデータを生成し、アークカット条件Ｂ）から第２アークカット経路探索ネットワークデータを生成する（ステップＳ５、Ｓ６）。生成されたネットワークデータから得られる第１アークカット経路探索ネットワークを図１９に示し、第２アークカット経路探索ネットワークを図２０に示す。尚、カット対象のアークを図中に点線で示してある。この点線で示したアークは、実際にはネットワーク上では存在しない。
【００７０】
図１９の第１アークカット経路探索ネットワークと図２０の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する（ステップＳ２）。探索の結果、図１９の第１アークカット経路探索ネットワークでは出発点ノードｓから経由点ノードｖに至る経路が存在しない。一方、図２０の第２アークカット経路探索ネットワークでは、第１区間の最小コスト経路は本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｓ→ノード４→ノードｖ）の経路が得られ、経由点ノードｖから到着点ノードｔに至る第２区間の最小コスト経路としてノードｖ→ノード６→ノードｔの経路が得られる。
【００７１】
これにより、出発点ｓから経由点ｖを通り到着点ｔに至る経由最小コスト経路として、図２０の第２アークカット経路探索ネットワークにおいて、図中点線矢印で示す経路ノードｓ→ノード４→ノードｖ→ノード６→ノードｔの結合経路が経由最小コスト経路候補として１つだけ存在する（ステップＳ３、Ｓ４）。従って、この経路データが経由経路データ格納部３Ｃに記憶され（ステップＳ７）、経由最小コスト経路データ選択部５によって選択され（ステップＳ９）、出力部６から経由最小コスト経路情報として出力される（ステップＳ１０）。
【００７２】
かかる構成によれば、始点から終点までを、始点から経由点までの区間（第１区間）と経由点から終点までの区間（第２区間）に分割し、それぞれの区間で最小コスト経路を探索して結合し、結合した経路において重複経路が存在する場合に、重複経路のない経由経路が求まるまで、重複経路を除外するように予め定めたアークカット条件に従って所定のアークのカット処理を繰返し行うことにより、重複経路のない経由最小コスト経路を探索する構成としたので、従来の経由最小コスト経路探索装置に比べて、重複経路のない経由最小コスト経路の探索処理時間を短縮することができる。
【００７３】
図２１は、本発明に係る経由最小コスト経路探索装置の別の実施形態の構成を示すブロック図である。尚、図１の実施形態と同一要素には同一符号を付して説明を省略する。
図２１に示す経由最小コスト経路探索装置１は、より効率的に経由最小コスト経路を求めるもので、その構成は経由最小コスト経路選択部５がない点が図１の実施形態と異なり、その他の構成は同じである。本実施形態の経由最小コスト経路探索装置１では、経由経路データ格納部３Ｃに格納する経由最小コスト経路候補は常に１つとし、複数の候補の中から１つの経路を選択する必要がないため、経由最小コスト経路選択部５を必要としない。そして、経由最小コスト経路記憶部５に格納されている経由最小コスト経路候補のコストより小さいコストの結合経路が生成されなくなったとき、経由最小コスト経路記憶部５に格納されている経由最小コスト経路候補を経由最小コスト経路情報として出力部６から出力する構成である。
【００７４】
次に、図７に示す経路探索ネットワークを用いて、図２１の経由最小コスト経路探索装置１による経由最小コスト経路探索動作を、図２２のフローチャートを参照しながら説明する。
【００７５】
ステップＳ２１〜Ｓ２３の動作は、図２のフローチャートと同様である。
ステップＳ２１において、入力部２から出発点、到着点及び経由点の各データを入力し、ステップＳ２２において、出発点ノードｓから経由点ノードｖまでの第１区間及び経由点ノードｖから到着点ノードｔまでの第２区間における最小コスト経路をそれぞれ探索する。探索の結果、第１区間における最小コスト経路はノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖの経路でコストは７であり、第２区間における最小コスト経路はノードｖ→ノード４→ノード１→ノード２→ノードｔの経路でコストは４である。ステップＳ２３において、上記の第１区間と第２区間のそれぞれの最小コスト経路を結合する。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図８に点線で示すノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード４→ノード１→ノード２→ノードｔというコスト１１の結合経路が得られる。
【００７６】
ステップＳ２４において、ステップＳ２３で得られた結合経路のコストと、経由経路データ格納部３Ｃ内の経由最小コスト経路候補のコストとを比較し、コストの小さい結合経路があるか否かを判定する。経由経路データ格納部３Ｃ内の経由最小コスト経路候補よりコストの小さい結合経路が有れば判定が経路有りとなってステップＳ２５に進む。経由経路データ格納部３Ｃ内の経由最小コスト経路候補よりコストの小さい結合経路が無ければ判定が経路無しとなって後述するステップＳ３１に進む。尚、経路探索動作開始初期は、経由経路データ格納部３Ｃ内に経由最小コスト経路候補が格納されていない。そのため、経由経路データ格納部３Ｃ内に経由最小コスト経路候補が格納されていない探索動作開示時の比較用コストデータとして極端に大きな値に設定したコストデータを予め経由経路データ格納部３Ｃ内に格納しておく。こうすることにより、初回では必ず結合経路のコストの方が小さくなるため、ステップＳ２４の判定は経路有りとなりステップＳ２５に進むことになる。
【００７７】
ステップＳ２５において、重複ノード探索手段４Ｃにより、生成された結合経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード４→ノード１→ノード２→ノードｔに重複するノードが存在するか否かを探索する。この場合、ノード４とノード１が重複し、ステップＳ２５の判定は重複ノードありとなりステップＳ２６に進む。
【００７８】
ステップＳ２６において、重複ノードが存在する結合経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード４→ノード１→ノード２→ノードｔのコストが経由経路データ格納部３Ｃ内の経由最小コスト経路候補のコストより小さいか否かを判定する。経由経路データ格納部３Ｃ内の経由最小コスト経路候補よりコストの小さい結合経路が有れば判定が経路有りとなってステップＳ２７に進み、経由経路データ格納部３Ｃ内の経由最小コスト経路候補よりコストの小さい結合経路が無ければ判定が経路無しとなってステップＳ３１に進む。前述したように経路探索動作開始初期は、経由経路データ格納部３Ｃ内に経由最小コスト経路候補は格納されていないので、ステップＳ２６についても、初回は極端に大きな値に設定した比較用コストデータと比較することになり、必ずステップＳ２６の判定が経路有りとなりステップＳ２７に進むことになる。
【００７９】
ステップＳ２７において、前述のアークカット条件Ａ）により、図８の結合経路における経由点ノードｖに一番近い重複ノード４に入るアークをカット対象アークデータとして生成する。また、アークカット条件Ｂ）により、図８の結合経路における経由点ノードｖに一番近い重複ノード４から出るアークをカット対象アークデータとして生成し、アークデータ格納部３Ｂに格納する。
【００８０】
ステップＳ２８において、アークデータ格納部３Ｂのカット対象アークデータに従ってアークのカット処理を行う。例えば、第１区間のカット対象アークを本来の経路探索ネットワークから取除いて図９に示すような第１アークカット経路探索ネットワークを構築するためのネットワークデータとすると共に、第２区間のカット対象アークを本来の経路探索ネットワークから取除いて図１０に示すような第２アークカット経路探索ネットワークを構築するためのネットワークデータとする。図９及び図１０において、点線で示したカット対象のアークは、実際にはネットワーク上では存在しない。
【００８１】
ステップＳ２２に戻り、図９の第１アークカット経路探索ネットワークと図１０の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路と第２区間の最小コスト経路をそれぞれ探索する。探索の結果、図９の第１アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路はノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖでコスト８の経路が得られる。また、第２区間の最小コスト経路は本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｖ→ノード４→ノード１→ノード２→ノードｔ）でコスト４の経路が得られる。また、図１０の第２アークカット経路探索ネットワークにおいて、第１区間の最小コスト経路は本来の経路探索ネットワーク上で得られた経路と同じ経路（ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ）でコスト７の経路が得られ、第２区間の最小コスト経路はノードｖ→ノード８→ノード５→ノード２→ノードｔの経路でコスト５の経路が得られる。
【００８２】
ステップＳ２３において、第１及び第２アークカット経路探索ネットワーク上で探索された各区間の最小コスト経路を結合する。これにより、出発点ｓから経由点ｖを通り到着点ｔまでの経由最小コスト経路として、図９の第１アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード４→ノード１→ノード２→ノードｔでコスト１２の結合経路が得られる。また、図１０の第２アークカット経路探索ネットワークにおいては、点線矢印で示す経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔでコスト１２の結合経路が得られる。
【００８３】
ステップＳ２４において、ステップＳ２３で得られたそれぞれの結合経路のコストが、経由経路データ格納部３Ｃ内の経由最小コスト経路候補のコストより小さいか否かを判定する。この場合も、経由経路データ格納部３Ｃ内には経由最小コスト経路候補は格納されておらず、コストが極端に大きな値に設定したコストデータとの比較となり、判定は経路有りとなりステップＳ２５に進むことになる。
【００８４】
ステップＳ２５において、それぞれの結合経路について重複するノードが存在するか否かを探索する。ここで、図１０の第２アークカット経路探索ネットワーク上で得られた結合経路ノードｓ→ノード１０→ノード１１→ノード１→ノード４→ノードｖ→ノード８→ノード５→ノード２→ノードｔは重複するノードが存在しない。従って、ステップＳ２９に進み、経由最小コスト経路候補としてその経由経路データを経由経路データ格納部３Ｃに格納する。一方、図９の第１アークカット経路探索ネットワーク上で得られた結合経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード４→ノード１→ノード２→ノードｔでは、ノード２が重複している。従って、ステップＳ３０の判定が経路有りとなってステップＳ２６に進む。
【００８５】
ステップＳ２６において、重複ノードが存在する図９の結合経路ノードｓ→ノード１０→ノード１１→ノード１２→ノード２→ノード５→ノード８→ノードｖ→ノード４→ノード１→ノード２→ノードｔのコストが経由経路データ格納部３Ｃ内の経由最小コスト経路候補のコストより小さいか否かを判定する。この場合、重複ノードが存在する図９の結合経路のコストは１２であり、経由経路データ格納部３Ｃに格納されている経由最小コスト経路候補のコストも１２である。このため、判定は経路無しとなりステップＳ３１に進む。
【００８６】
ステップＳ３１において、経由経路データ格納部３Ｃに格納されている図１０の経由最小コスト経路候補を経由最小コスト経路データとして出力部６から出力する。
【００８７】
かかる実施形態装置によれば、経由経路データ格納部３Ｃに格納される経由最小コスト経路は常に１つであるので、複数の経由最小コスト経路から選択する必要がなく、経由最小コスト経路選択部５が不要となる。また、経由経路データ格納部３Ｃに格納されている経由最小コスト経路候補のコストよりコストの大きい結合経路についてはアークカット処理を省略でき、その後の経路探索処理も省略できるので、経由最小コスト経路の探索動作の効率を向上できる。
【符号の説明】
【００８８】
１    経由最小コスト経路探索装置
２    入力部
３    データストレージ装置
３Ａ    ネットワークデータ格納部
３Ｂ    アークデータ格納部
３Ｃ    経由経路データ格納部
４    経由経路データ生成部
４Ａ    ２ノード間最小コスト経路データ生成手段
４Ｂ    最小コスト経路データ結合手段
４Ｃ    重複ノード探索手段
４Ｄ    カット対象アークデータ生成手段
４Ｅ    アークカット手段
５    経由最小コスト経路データ選択部
６    出力部
【図１】
0005413894.tif 000002
【図２】
0005413894.tif 000003
【図３】
0005413894.tif 000004
【図４】
0005413894.tif 000005
【図５】
0005413894.tif 000006
【図６】
0005413894.tif 000007
【図７】
0005413894.tif 000008
【図８】
0005413894.tif 000009
【図９】
0005413894.tif 000010
【図１０】
0005413894.tif 000011
【図１１】
0005413894.tif 000012
【図１２】
0005413894.tif 000013
【図１３】
0005413894.tif 000014
【図１４】
0005413894.tif 000015
【図１５】
0005413894.tif 000016
【図１６】
0005413894.tif 000017
【図１７】
0005413894.tif 000018
【図１８】
0005413894.tif 000019
【図１９】
0005413894.tif 000020
【図２０】
0005413894.tif 000021
【図２１】
0005413894.tif 000022
【図２２】
0005413894.tif 000023