特許
J-GLOBAL ID：201103081679342227
経由最小コスト経路探索装置及び経由最小コスト経路探索方法
発明者：
,
出願人/特許権者：
,
代理人 (1件)：
笹島 富二雄
公報種別：公開公報
出願番号（国際出願番号）：特願2009-234275
公開番号（公開出願番号）：特開2011-080899
出願日： 2009年10月08日
公開日（公表日）： 2011年04月21日
要約：
【課題】重複経路なしに、始点から経由点を通り終点に至る経由最小コスト経路の探索時間を短縮する。【解決手段】コストを設定したアークと複数のノードからなる経路探索ネットワークで、出発点ノードから経由点ノードまでの第1区間と経由点ノードから到着点ノードまでの第2区間の各最小コスト経路を探索して結合し(S1〜S3)、結合経路に重複ノードが存在する時、第1区間の最小コスト経路の経由点ノードに最も近い重複ノードへ入るアークをカットして第1アークカット経路探索ネットワークを構築し、第2区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカットして第2アークカット経路探索ネットワークを構築し、第1及び第2アークカット経路探索ネットワークそれぞれで、重複ノードのない結合経路を探索して経由最小コスト経路候補とし(S4〜S6、S1〜S3)、複数の候補の中でコストが最小のものを経由最小コスト経路として選択する(S7〜S9)。【選択図】図2
請求項（抜粋）：
経路探索ネットワークを用いて、始点から指定した経由点を通り終点に至る経由経路の中でコストが最小となる経由最小コスト経路を探索する経由最小コスト経路探索装置であって、
複数のノードをアークで接続し、各アークにコストを設定した本来の経路探索ネットワークを構築するネットワークデータを格納するデータ格納部と、
前記始点、終点及び経由点の各ノード情報を入力する入力部と、
前記本来の経路探索ネットワークに基づいて、入力された始点ノードから経由点ノードまでの第1区間の最小コスト経路と前記経由点ノードから終点ノードまでの第2区間の最小コスト経路を探索して結合し当該結合経路で重複するノードが存在する時、前記本来の経路探索ネットワークにおいて前記第1区間の最小コスト経路で経由点ノードに最も近い前記重複ノードへ入るアークをカット処理して構築した第1アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成すると共に、前記本来の経路探索ネットワークにおいて前記第2区間の最小コスト経路の経由ノードに最も近い重複ノードから出るアークをカット処理して構築した第2アークカット経路探索ネットワークに基づいて、ノードが重複しない結合経路を経由最小コスト経路候補として生成する経由最小コスト経路候補生成部と、
該経由最小コスト経路候補生成部で生成した経由最小コスト経路候補を記憶する経由最小コスト経路候補記憶部と、
該経由最小コスト経路候補記憶部に記憶されたコストが最小の経由最小コスト経路候補を経由最小コスト経路情報として出力する出力部と、
を備えて構成したことを特徴とする経由最小コスト経路探索装置。
IPC (1件)：
FI (1件)：
Fターム (3件)：
2F129AA02
, 2F129DD03
, 2F129DD62
