(57)【特許請求の範囲】
【請求項１】
ノードとブランチとで経路を表現したグラフにおいて、予め設定された始点ノードと終点ノードに対して各ブランチが経路と成り得るか否かを示す各ブランチの感度を算出して感度を持つブランチのみを抽出するブランチ感度算出手段と、このブランチ感度算出手段で抽出されたグラフに含まれるループ構成を探索し、探索したループ構成を切断して前記グラフを放射状構成とするための切断対象となるブランチの組み合わせを作成する放射状構成作成手段と、この放射状構成作成手段により切断対象となるブランチを切断して作成された放射状構成のグラフに基づいて始点ノードから終点ノードに至る経路の候補を全て探索する全経路探索手段とを備えたことを特徴とする経路探索装置。
【請求項２】
前記全経路探索手段で探索される経路の内から、ブランチの進行方向の制約を満たす経路の候補を探索する進行方向制約付経路探索手段を有することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
始点ノードから終点ノードに至る途中に指定された中継点ノードを経由する経路の候補を全て探索する中継点経由経路探索手段を有することを特徴とする請求項１または請求項２に記載の経路探索装置。
【請求項４】
前記全経路探索手段で探索される経路の内から、最小コストとなる経路を探索する最小コスト経路探索手段を有することを特徴とする請求項１ないし請求項３のいずれか１項に記載の経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ノードとブランチとで経路を表現したグラフにおいて、始点ノードから終点ノードに至る経路を探索する経路探索装置に関する。
【０００２】
【従来の技術】
従来、ノードとブランチとで経路を表現したグラフにおいて、始点ノードから終点ノードに至る全経路を探索する装置として、たとえば、特開平０７−０１５４６９号公報に記載されたものがある。
【０００３】
この全経路探索装置は、いわゆる総当たり方式によって全経路を探索するものであり、この総当たり方式について図１３を参照して説明する。
【０００４】
図１３において、始点ノードをＡ点、終点ノードをＢ点としたとき、まず、始点ノードＡから伸びる全中継路について接続先ノードを調べ、それが終点ノードＢであったならば、その経路を格納する。接続先ノードが終点ノードＢでなかったならば、さらにその接続先ノードから伸びる全ての中継路について接続先ノードが終点ノードＢか否かを調べていき、最終的に終点ノードＢに到達すれば、その経路を格納する。
【０００５】
このように、従来の装置では、全ての接続先ノードから伸びる全ての中継路について経路を調べていくことで始点ノードＡから終点ノードＢへの全経路を探索している。
【０００６】
【発明が解決しようとする課題】
従来の経路探索装置は、上記のように構成されているため、ノード数やブランチ数が増加するのに伴って経路探索の組み合わせ数が増大し、経路探索に時間を要する。
【０００７】
また、最短経路探索に関しては、従来より、Ｋｕｒｓｋａｌの算法や、ダイクストラム法などの手法がある。しかし、従来の上記手法では、目的関数の設定の仕方（マイナスの評価のブランチがある場合など）によっては、局所最適解にはまって全体的な最適経路を探索できない場合が発生するなどの問題が生じる。
【０００８】
本発明は、上述の問題を解決するためになされたもので、始点ノードから終点ノードまでの経路探索を確実かつ短時間の内に行うことができる経路探索装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明は、上記の目的を達成するために、次の構成を採用している。
すなわち、請求項１記載の発明に係る経路探索装置は、ノードとブランチとで経路を表現したグラフにおいて、予め設定された始点ノードと終点ノードに対して各ブランチが経路と成り得るか否かを示す各ブランチの感度を算出して感度を持つブランチのみを抽出するブランチ感度算出手段と、このブランチ感度算出手段で抽出されたグラフに含まれるループ構成を探索し、探索したループ構成を切断して前記グラフを放射状構成とするための切断対象となるブランチの組み合わせを作成する放射状構成作成手段と、この放射状構成作成手段により切断対象となるブランチを切断して作成された放射状構成のグラフに基づいて始点ノードから終点ノードに至る経路の候補を全て探索する全経路探索手段と、を備えることを特徴としている。
【００１０】
請求項２記載の発明に係る経路探索装置は、請求項１に記載の発明の構成において、前記全経路探索手段で探索される経路の内から、ブランチの進行方向の制約を満たす経路の候補を探索する進行方向制約付経路探索手段を有することを特徴としている。
【００１１】
請求項３記載の発明に係る経路探索装置は、請求項１または請求項２に記載の発明の構成において、始点ノードから終点ノードに至る途中に指定された中継点ノードを経由する経路の候補を全て探索する中継点経由経路探索手段を有することを特徴としている。
【００１２】
請求項４記載の発明に係る経路探索装置は、請求項１ないし請求項３のいずれか１項に記載の発明の構成において、前記全経路探索手段で探索される経路の内から、最小コストとなる経路を探索する最小コスト経路探索手段を有することを特徴としている。
【００１３】
【発明の実施の形態】
実施の形態１．
図１は本発明の実施の形態１に係る経路探索装置の構成を示すブロック図である。
この経路探索装置１は、ハードディスクなどで構成される探索データ格納部１１と、マイクロコンピュータなどで構成される探索処理部１２とからなる。
【００１４】
探索データ格納部１１は、ノードブランチ接続情報格納装置５１を有している。このノードブランチ接続情報格納装置５１には、ブランチ数、ノード数、始点ノード番号、終点ノード番号などのノードブランチ接続情報が予め格納されている。
【００１５】
探索処理部１２は、ノードブランチ接続情報格納装置５１に格納されているノードブランチ接続情報に基づいて経路探索を行うもので、ブランチ感度算出手段６１、放射状構成作成手段６２、および全経路探索手段６３を含む。なお、探索処理部１２の探索処理結果は、図示しないディスプレイやプリンタ等の出力装置に出力されるようになっている。
【００１６】
ブランチ感度算出手段６１は、探索データ格納部１１のノードブランチ接続情報格納装置５１から生成されたノードブランチ接続情報に基づき、ノードとブランチとで経路を表現したグラフにおいて、予め設定された始点ノードと終点ノードに対して各ブランチが経路と成り得るか否かを示す各ブランチの感度を算出して感度を持つブランチのみを抽出するものである。
【００１７】
また、放射状構成作成手段６２は、ブランチ感度算出手段６１で抽出されたグラフに含まれるループ構成を探索し、探索したループ構成を切断してグラフを放射状構成とするための切断対象となるブランチの組み合わせを作成するものである。
【００１８】
さらに、全経路探索手段６３は、放射状構成作成手段６２により切断対象となるブランチを切断して作成された放射状構成のグラフに基づいて始点ノードから終点ノードに至る経路の候補を全て探索するものである。
【００１９】
次に、上記構成を有する経路探索装置１における全経路探索処理動作について、図２に示すフローチャート、および図３ないし図７に示す説明図を参照して説明する。なお、符号Ｓは各処理ステップを意味する。
【００２０】
まず、ブランチ感度算出手段６１は、ノードブランチ接続情報格納装置５１に予め格納されているノードブランチ接続情報を読み込み（Ｓ１）、予め設定された始点ノードと終点ノードに対する各ブランチが経路と成り得るか否かを示す各ブランチの感度を算出し、感度を持つブランチのみを抽出する（Ｓ２）。
【００２１】
たとえば、図３に示すようなノードとブランチとで経路を表現したグラフがあるとした場合に、始点ノードを番号２のノード、終点ノードを番号６のノードとし、始点ノードを送電側と考えて電源発生地点であるスラックノードとして定義し、また、終点ノードを受電側と考えて負荷量１ＭＷの負荷ノードとして定義したとする。このとき、各ブランチにランダムなインピーダンスを設定して潮流計算を実行すると、潮流が流れるブランチと潮流が流れないブランチとが存在することになる。図３では、潮流が流れるブランチは、番号２，３，４，５，６，７のブランチで、潮流が流れないブランチは番号１，８，９，１０，１１である。この内、潮流が流れないブランチは、始点ノードと終点ノードに関して無関係、すなわち感度は無くて０と考えることができる。
【００２２】
このように、始点ノードと終点ノードに複数のブランチが接続している場合に、複数のブランチの内で経路の候補となるブランチは０以外の数値をもち、始点ノードと終点ノードに関して無関係なブランチは感度が０となる。そこで、感度が０のブランチは、始点ノードと終点ノードを結ぶ経路には無関係であるので、このようなブランチを切断して削除する（Ｓ３）。また、感度が０のブランチを削除することにより、接続するブランチが全て切断されていて、いずれのノードとも接続されない状態となった浮きノードについても、経路探索には無関係となるため削除する。
【００２３】
こうして、図３において始点ノードと終点ノードに関して不要なノードおよびブランチを削除すると、探索対象となるノードとブランチは図４に示すようになる。したがって、経路探索を行う上で探索対象となるノード数とブランチ数とが減少されるため、経路探索処理の効率化を図ることができる。
【００２４】
次に、放射状構成作成手段６２は、ブランチ感度算出手段６１で抽出されたグラフ（たとえば図４）についてループ構成を探索してループ構成のある部分を抽出する（Ｓ４）。この場合のループ構成の抽出は、たとえば次のアルゴリズムによって行われる。
【００２５】
▲１▼  全てのノードを最初は未チェックとする。
▲２▼  始点ノードをチェック済みとする。
▲３▼  ある一つのブランチに着目する。
▲４▼  この着目したブランチの両端にあるノードについて、ａ）両端ノードのいずれか一方がチェック済みであれば、チェック済みでない方のノードをチェック済みとした後、次のブランチに着目する。ｂ）両端ノードが何れも未チェックであれば、次のブランチに着目する。ｃ）両端ノードが何れもチェック済みであれば、このブランチはループに所属しているため、このブランチをループ構成のブランチとして登録した後、次のブランチに着目する。
▲５▼  上記の▲４▼の処理をチェック済みのノード数が変化しなくなるまで繰り返す。
これにより、たとえば図４におけるグラフでは、図５（ａ），（ｂ）に示すように２つのループ構成１，２が抽出されることになる。
【００２６】
続いて、放射状構成作成手段６２は、ステップ４で抽出した各ループ構成について、各ループごとに切断するブランチを一つ選択し、グラフを非ループ構成とするための切断対象となるブランチの組み合わせを作成する（Ｓ５）。以下、非ループ構成のブランチのことを放射状構成のブランチと称する。
【００２７】
たとえば、図５に示した２つのループ構成１，２に対して、図６（ａ）では切断対象としてブランチ３，２の組み合わせが、図６（ｂ）ではブランチ４，５の組み合わせが、図６（ｃ）ではブランチ４，４の組み合わせがそれぞれ作成されている。図６では、切断対象となるブランチの組み合わせとして３つの例を示しているが、図５における２つのループ構成１，２に対する切断対象となるブランチの組み合わせは、図７に示すように９個の組み合わせがある。
【００２８】
このように、放射状構成作成手段６２は、グラフに含まれるループ構成を抽出した後、各ループごとに一つのブランチを切断してグラフを放射状構成とするための切断対象となるブランチの組み合わせを作成するが、このような処理を行うのは、次の理由による。
【００２９】
始点ノードから終点ノードまでの一つの経路を探索することは、始点ノードから終点ノードまでを一筆書きで放射状構成を作成するこを意味する。また、グラフをこのような放射状構成とするためには、ループを構成している少なくとも１つのブランチを切断することが必要である。このため、グラフに含まれるループ構成の部分に着目し、そのループ構成のブランチを切断して非ループとなるブランチを作成することが、放射状構成を作成する上で最も効率がよいことになる。
【００３０】
次に、全経路探索手段６３は、放射状構成作成手段６２によって切断対象となるブランチの組み合わせに従ってブランチを切断したことにより得られたグラフが放射状構成となっているか否かを判断する（Ｓ６）。ここで、グラフが放射状構成となる条件は、浮きノードがないときには、『ノード数＝ブランチ数＋１』の関係があるので、この関係に基づいてグラフが放射状構成となっているか否かを判断する。
【００３１】
たとえば、図６（ａ）に示すようにループ構成１についてはブランチ３を、ループ構成２についてはブランチ２をそれぞれ切断すると、切断後のグラフは同図（ａ）右端に示すようになるが、このとき、ノード数３でブランチ数２となるため、グラフは放射状構成である。また、図６（ｂ）に示すようにループ構成１についてはブランチ４を、ループ構成２についてはブランチ５をそれぞれ切断すると、切断後のグラフは同図（ｂ）右端に示すようになるが、このとき、ノード数４でブランチ数３となるためグラフは放射状構成である。さらに、図６（ｃ）に示すようにループ構成１についてはブランチ４を、ループ構成２についてはブランチ４をそれぞれ切断すると、切断後のグラフは同図（ｃ）右端に示すようになるが、このとき、ループ構成１とループ構成２で切断するブランチが重複しているのでノード数４に対しブランチ数４となり、したがってグラフは放射状構成にならない。
【００３２】
次いで、全経路探索手段６３は、放射状構成とならない場合には、この組み合わせを無効としてステップ８に処理を移す。また、放射状構成となる場合は、続いて、終点ノードから始点ノードへ順に辿ったブランチを一つの経路として格納する（Ｓ７）。
【００３３】
引き続いて、全経路探索手段６３は、ループ構成を切断してグラフを放射状構成とするための切断対象となるブランチの組み合わせを全て実施したかを判定する（Ｓ８）。このとき、全ての組み合わせについて処理が終了していない場合は、ステップ５に処理を移し、全ての組み合わせについて処理が終了するまでステップ５〜ステップ８を繰り返す。このようにして、たとえば、図４のグラフにおいて、このグラフを放射状構成とするための切断対象となる全てのブランチの組み合わせ結果を示すと図７に示すようになる。
【００３４】
全経路探索手段６３は、上記のステップ８で全ての組み合わせについて処理が終了したならば、次に、探索した経路について重複する経路の組み合わせが存在するか否かを判定する（Ｓ９）。そして、重複する経路の組み合わせが存在する場合には、作成された放射状構成の経路について、重複する経路の組み合わせを統一する（Ｓ１０）。
【００３５】
たとえば、図７に示すようにして探索された９個の経路の組み合わせの内で重複した経路については、一つの経路に統一すると、以下の３通りとなる。なお、数字はブランチ番号である。
経路１：４→７
経路２：２→５→７
経路３：３→６→７
【００３６】
従来の場合、全経路探索を実施する場合には、経路探索の対象となる組み合わせ数は２ｎ（ｎ：ブランチ数）であったのに対して、この実施の形態１のように、ループ構成のみに着目すると、経路探索の対象となる組み合わせ数は、ＲＢ１×ＲＢ２×…（ＲＢ１、ＲＢ２、…は、各ループ内のブランチ数）となる。図３に示す例の場合、従来の方法で全探索で実施したときには２11＝２０４８通りの組み合わせになるのに対して、この実施の形態１のようにループ構成のみに着目すると経路探索の対象となる組み合わせ数は、３×３＝９通りの組み合わせ数となる。このように、経路探索を行う上での除外対象とするブランチをループを構成しているブランチに限定することにより、経路探索の効率化を図ることができ、全経路探索に要する時間を短縮化することが可能になる。
【００３７】
実施の形態２．
図８は本発明の実施の形態２に係る経路探索装置の構成を示すブロック図であり、図１に示した実施の形態１における経路探索装置と対応する構成部分には同一の符号を付す。
【００３８】
この実施の形態２の経路探索装置２において、探索データ格納部２１には、ノードブランチ接続情報格納装置５１に加えて、ブランチ進行方向制約格納装置５２が設けられている。そして、このブランチ進行方向制約格納装置５２には、始点ノードから終点ノードに至るまでに経由する各ブランチにおける時間的制約、費用的制約、方向的制約、エネルギー的制約などといったブランチ進行方向の制約条件となる情報が予め格納されている。
【００３９】
また、探索処理部２２には、ブランチ感度算出手段６１、放射状構成作成手段６２、および全経路探索手段６３に加えて、進行方向制約付経路探索手段６４が設けられている。この進行方向制約付経路探索手段６４は、全経路探索手段６３で探索される経路の内から、ブランチ進行方向制約格納装置５２に格納されているブランチの進行方向の制約条件を満たす経路の候補を探索するものである。
その他の構成は実施の形態１と同様であるから、ここでは詳しい説明は省略する。
【００４０】
次に、この実施の形態２の経路探索装置２における経路探索処理動作について、特に、進行方向制約付経路探索手段６４の動作を主体に説明する。
【００４１】
たとえば、図９に示すように、全経路探索手段６３によって探索された経路の組み合わせが、次の３通りであったとする。数字はブランチ番号である。
経路１：４→７
経路２：２→５→７
経路３：３→６→７
【００４２】
ここで、たとえば電力会社間の電力融通の経路について考えると、各ノードを電力会社とし、始点ノード２が送電側の電力会社、終点ノード６が受電側電力会社、各ブランチを電力会社間の連系設備とし、送電側電力会社２は、融通電力を受電側電力会社６に融通するものとする。
【００４３】
このとき、経路３の途中にある電力会社（ノード）４と電力会社（ノード）５の間の連系設備（ブランチ）６が設備容量の限度超過などの理由によって電力会社４から電力会社５への融通ができない状況にあるとすると、経路３を電力融通経路として採用することができない。したがって、進行方向制約付経路探索手段６４は、経路１，２のみが電力会社間の電力融通の可能な経路（つまり、進行方向の制約を満たす経路）として採用する。
【００４４】
このように、この実施の形態２では、各連系設備（ブランチ）に対して融通電力上限値のように、経路の進行方向の制約となる条件を指定することによって進行方向の制約を満たす経路を探索することができる。
【００４５】
実施の形態３．
図１０は本発明の実施の形態３に係る経路探索装置の構成を示すブロック図であり、図１に示した実施の形態１における経路探索装置と対応する構成部分には同一の符号を付す。
【００４６】
この実施の形態３の経路探索装置３において、探索データ格納部３１には、ノードブランチ接続情報格納装置５１に加えて、中継点指定データ格納装置５３が設けられている。そして、この中継点指定データ格納装置５３には、始点ノードから終点ノードに至るまでに経由すべき各中継点を指定するための情報が予め格納されている。
【００４７】
また、探索処理部３２には、ブランチ感度算出手段６１、放射状構成作成手段６２、および全経路探索手段６３に加えて、中継点経由経路探索手段６５が設けられている。この中継点経由経路探索手段６５は、中継点指定データ格納装置５３に格納されている中継点ノードに基づいて、始点ノードから終点ノードに至る途中に指定された中継点ノードを経由する経路の候補を全て探索するものである。
その他の構成は実施の形態１と同様であるから、ここでは詳しい説明は省略する。
【００４８】
次に、この実施の形態３の経路探索装置３における経路探索処理動作について、特に、中継点経由経路探索手段６５の動作を主体に説明する。
【００４９】
たとえば、図３に示したグラフにおいて、ノードブランチ接続情報格納装置５１の情報によって始点ノードはノード番号２、終点ノードはノード番号６に指定され、また、中継点指定データ格納装置５３の情報によって中継点ノードとしてノード番号３が指定されているものとする。
【００５０】
このとき、まず、実施の形態１の場合と同様に、ブランチ感度算出手段６１、放射状構成作成手段６２、および全経路探索手段６３によって全経路探索を行い、検索された全経路の組み合わせが、次の３通りであったとする。数字はノード番号である。
経路１：２→３→５→６
経路２：２→５→６
経路３：２→４→５→６
【００５１】
ここで、中継点経由経路探索手段６５は、中継点指定データ格納装置５３に格納されている中継点ノードが含まれる経路を採用し、中継点ノードが含まない経路は採用しない。したがって、図３に示したグラフの例では、
経路１：２→３→５→６（数字はノード番号）
が指定された中継点ノードが含まれる経路として得られる。
【００５２】
なお、複数の中継点ノードが指定されている場合には、中継点経由経路探索手段６５は上記の要領によってすべての中継点ノードが含まれる経路のみを採用する。
【００５３】
実施の形態４．
図１１は本発明の実施の形態４に係る経路探索装置の構成を示すブロック図であり、図１に示した実施の形態１における経路探索装置と対応する構成部分には同一の符号を付す。
【００５４】
この実施の形態４の経路探索装置４において、探索データ格納部４１には、ノードブランチ接続情報格納装置５１に加えて、ブランチコストデータ格納装置５４が設けられている。そして、このブランチコストデータ格納装置５４には、各ブランチのコスト情報が予め格納されている。
【００５５】
また、探索処理部４２には、ブランチ感度算出手段６１、放射状構成作成手段６２、および全経路探索手段６３に加えて、最小コスト経路探索手段６６が設けられている。この最小コスト経路探索手段６６は、ブランチコストデータ格納装置５４に格納されている情報に基づいて、全経路探索手段６３で探索される経路の内から、最小コストとなる経路を探索するものである。
その他の構成は実施の形態１と同様であるから、ここでは詳しい説明は省略する。
【００５６】
次に、この実施の形態４の経路探索装置４における経路探索処理動作について、特に、最小コスト経路探索手段６６の動作を主体に説明する。
【００５７】
たとえば、図１２に示すように、全経路探索手段６３によって探索された経路の組み合わせが、次の３通りであったとする。数字はブランチ番号である。
経路１：４→７
経路２：２→５→７
経路３：３→６→７
【００５８】
ここで、たとえば最も送電ロスが少ない電力会社間の融通経路を決定することを考えると、始点ノード２を送電側電力会社、終点ノード６を受電側電力会社としたとき、最小コスト経路探索手段６６は、全経路探索手段６３によって探索された全経路について送電ロスの計算を行う。
【００５９】
この場合の送電ロスの計算は、各電力会社の受給口に対して送電設備などのインピーダンスより決まる損失率を用いて行うことができる。たとえば、図１２において、電力会社（ノード）２から電力会社（ノード）３に送電するときの損失率は３％、電力会社（ノード）３から電力会社（ノード）５に送電するときの損失率は２％のようになっている。
【００６０】
このとき、送電側電力会社から受電側電力会社への経路は前述のように経路１：４→７、経路２：２→５→７、経路３：３→６→７であり、送電会社から１ＭＷの融通電力が送電されるとすると、各経路による受電会社までの送電ロスは以下のように算出される。
【００６１】
経路１の送電ロス：
１−（１−０．０６）×（１−０．０１）×１ＭＷ＝０．０６９４ＭＷ
経路２の送電ロス：
１−（１−０．０３）×（１−０．０２）×（１−０．０１）×１ＭＷ＝０．０５８９ＭＷ
経路３の送電ロス：
１−（１−０．０４）×（１−０．０４）×（１−０．０１）×１ＭＷ＝０．０８７６ＭＷ
したがって、最小コスト経路探索手段６６は、最小送電ロスの経路として経路２を選択する。
【００６２】
なお、上記の実施の形態２〜４では、進行方向制約付経路探索手段６４、中継点経由経路探索手段６５、最小コスト経路探索手段６６をそれぞれ単独に設けた場合について説明したが、本発明はこれに限定されるものではなく、必要に応じてこれらの各手段６４，６５，６６を適宜組み合わせた構成とすることが可能である。
【００６３】
また、上記の実施の形態１〜４では、ノード・ブランチで表現されるグラフとして送電経路を一例にとって説明したが、本発明はこのような送電経路に限定されるものではなく、経路を経由して通過する人、物、金銭、エネルギー、通信、情報などの各種の分野について本発明を適用することができる。たとえば、カーナビゲーションの最短経路探索として、出発地と目的地の最短時間の経路を探索することができる。この場合の進行方向制約条件としては、一方通行や混雑経路回避などの制約がある。また、ネットワークの通信経路探索として、ネットワーク回線故障時の迂回経路を探索することができる。この場合の進行方向制約条件としては、ルータのルーティングやトラフィックなどの制約がある。
【００６４】
【発明の効果】
本発明によれば、次の効果を奏する。
請求項１記載に係る発明の経路探索装置は、従来の手法に比べて始点ノードから終点ノードまでの経路探索の組み合わせ数を減少させることができるため、始点ノードから終点ノードに至るまでの全経路探索を短時間の内に効率良く行うことができる。
【００６５】
請求項２記載に係る発明の経路探索装置は、請求項１記載の発明の効果に加えて、始点ノードから終点ノードの間の経路に進行方向の制約がある場合にも、この条件を満たす経路の候補を全て探索することができる。
【００６６】
請求項３記載に係る発明の経路探索装置は、請求項１または請求項２記載の発明の効果に加えて、始点ノードから終点ノードの間の経路に所定の中継点を経由すべき制約がある場合にも、この条件を満たす経路の候補を全て探索することができる。
【００６７】
請求項４記載の発明に係る経路探索装置は、請求項１ないし請求項３記載のいずれかの発明の効果に加えて、始点ノードから終点ノードに至るまでに最小コストが必要であるという制約がある場合にも、この最小コストの条件を満たす経路の候補を全て探索することができる。
【図面の簡単な説明】
【図１】  本発明の実施の形態１に係る経路探索装置の構成を示すブロック図である。
【図２】  図１の経路探索装置における全経路探索処理動作の説明に供するフローチャートである。
【図３】  経路探索処理対象となるグラフの一例を示す説明図である。
【図４】  ブランチ感度算出手段によりブランチ感度を算出する場合の一例を示す説明図である。
【図５】  放射状構成作成手段によりループ構成を抽出する場合の一例を示す説明図である。
【図６】  放射状構成作成手段により放射状構成を作成する場合の一例を示す説明図である。
【図７】  全経路探索手段による全経路探索結果の一例を表にして示す説明図である。
【図８】  本発明の実施の形態２に係る経路探索装置の構成を示すブロック図である。
【図９】  進行方向制約付経路探索手段により進行方向制約を満たす経路を探索する場合の一例を示す説明図である。
【図１０】  本発明の実施の形態３に係る経路探索装置の構成を示すブロック図である。
【図１１】  本発明の実施の形態４に係る経路探索装置の構成を示すブロック図である。
【図１２】  最小コスト経路探索手段により最小コスト（最小送電ロス）の経路を探索する場合の一例を示す説明図である。
【図１３】  従来の全経路探索装置による全経路探索処理対象となるグラフの一例を示す説明図である。
【符号の説明】
１，２，３，４  経路探索装置、１１，２１，３１，４１  探索データ格納部、１２，２２，３２，４２  探索処理部、６１  ブランチ感度算出手段、６２  放射状構成作成手段、６３  全経路探索手段、６４  進行方向制約付経路探索手段、６５  中継点経由経路探索手段、６６  最小コスト経路探索手段。
【図１】
0003676713.tif 000002
【図２】
0003676713.tif 000003
【図３】
0003676713.tif 000004
【図４】
0003676713.tif 000005
【図５】
0003676713.tif 000006
【図６】
0003676713.tif 000007
【図７】
0003676713.tif 000008
【図８】
0003676713.tif 000009
【図９】
0003676713.tif 000010
【図１０】
0003676713.tif 000011
【図１１】
0003676713.tif 000012
【図１２】
0003676713.tif 000013
【図１３】
0003676713.tif 000014