(57)【特許請求の範囲】
【請求項１】
第１のネットワークの経路を探索する現用パス探索手段と、
前記現用パス探索手段で探索された現用パスに使われているリンクを双方向とも取り除く処理を行うことで迂回パス探索用の第２のネットワークを作成する迂回パス探索用ネットワーク作成手段と、
前記迂回パス探索用ネットワーク作成手段で作成された前記第２のネットワーク上で迂回パスの経路探索を行う迂回パス探索手段と、前記迂回パス探索手段で前記迂回パスが見つからなかった時に前記第１のネットワークを変形する現用パス探索用ネットワーク作成手段とを有し、
前記現用パス探索用ネットワーク作成手段は、前記迂回パス探索手段で到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記現用パス探索手段に渡すことで前記現用パス探索手段と前記迂回パス探索用ネットワーク作成手段と前記迂回パス探索手段と前記現用パス探索用ネットワーク作成手段とによる処理を繰返し行うようにしたことを特徴とする迂回パス設計装置。
【請求項２】
第１のネットワークの経路を探索する現用パス探索手段と、
前記現用パス探索手段で探索された現用パスに使われているリンクを双方向とも取り除く処理と、始点及び終点を除く前記現用パス上のノードから出ている向きのリンクを片方向だけ取り除く処理とを行うことで迂回パス探索用の第２のネットワークを作成する迂回パス探索用ネットワーク作成手段と、
前記迂回パス探索用ネットワーク作成手段で作成された前記第２のネットワーク上で迂回パスの経路探索を行う迂回パス探索手段と、前記迂回パス探索手段で前記迂回パスが見つからなかった時に前記第１のネットワークを変形する現用パス探索用ネットワーク作成手段とを有し、
前記現用パス探索用ネットワーク作成手段は、前記迂回パス探索手段で到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記現用パス探索手段に渡すことで前記現用パス探索手段と前記迂回パス探索用ネットワーク作成手段と前記迂回パス探索手段と前記現用パス探索用ネットワーク作成手段とによる処理を繰返し行うようにしたことを特徴とする迂回パス設計装置。
【請求項３】
第１のネットワークの経路を探索する第１のステップと、
前記第１のステップで探索された現用パスに使われているリンクを双方向ともに取り除く処理を行うことで迂回パス探索用の第２のネットワークを作成する第２のステップと、
この作成された第２のネットワーク上で迂回パスの経路探索を行う第３のステップと、前記迂回パスが見つからなかった時に前記第１のネットワークを変形する第４のステップとを有し、
前記第４のステップは、前記第３のステップで到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記第１のステップに渡すことで前記第１のステップから前記第４のステップまでの探索処理を繰返し行うようにしたことを特徴とする迂回パス設計方法。
【請求項４】
第１のネットワークの経路を探索する第１のステップと、
前記第１のステップで探索された現用パスに使われているリンクを双方向ともに取り除く処理と、始点及び終点を除く前記現用パス上のノードから出ている向きのリンクを片方向だけ取り除く処理とを行うことで迂回パス探索用の第２のネットワークを作成する第２のステップと、
この作成された第２のネットワーク上で迂回パスの経路探索を行う第３のステップと、前記迂回パスが見つからなかった時に前記第１のネットワークを変形する第４のステップとを有し、
前記第４のステップは、前記第３のステップで到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記第１のステップに渡すことで前記第１のステップから前記第４のステップまでの探索処理を繰返し行うようにしたことを特徴とする迂回パス設計方法。
【請求項５】
コンピュータに、第１のネットワークの経路を探索する第１の処理と、
前記第１の処理で探索された現用パスに使われているリンクを双方向ともに取り除く処理を行うことで迂回パス探索用の第２のネットワークを作成する第２の処理と、
この作成された第２のネットワーク上で迂回パスの経路探索を行う第３の処理と、
前記迂回パスが見つからなかった時に前記第１のネットワークを変形する第４の処理とを実行させ、
前記第４の処理において、前記第３の処理で到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第５の処理を行わせ、前記第５の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行わせることで前記第１のネットワークを変形する第６の処理を行わせ、
前記第６の処理で得られたネットワークを前記第１の処理に渡すことで前記第１の処理から前記第４の処理までの探索処理を繰返し行わせるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は迂回パス設計装置及びそれに用いる迂回パス設計方法並びにそのプログラムに関し、特にネットワークに障害が発生した時に現用パスから迂回パスに切替える障害切替えにおける迂回パスの設計に関する。
【０００２】
【従来の技術】
ネットワークに障害が発生した時に、現用パスから迂回パスに切替える障害切替えにおいて、障害が発生した時に障害地点を迂回するように迂回パスを設計する方法と、障害が発生する前から迂回パスを設計しておく方法とがある。
【０００３】
後者の方法において、現用パス上の任意の地点の障害に対応することができるように、迂回パスは現用パスが用いたノード、リンクを全く通らないような経路を設計する必要がある。
【０００４】
このような従来の迂回パス設計方法の一例が、特開平７−２５０３５６号公報の段落「００３３」に記載されている。この例では、まず現用パスを先に最短経路探索にて探索する。次に、光伝送路に充分大きな距離を付与することで迂回パスの最短経路探索において現用パスに利用された光伝送路が利用されないようにした上で迂回経路用に最短経路探索を行う。
【０００５】
このようにして、現用パスに利用された光伝送路を利用しない迂回パスを設計している。この迂回パス設計装置の構成を図１４に示す。この迂回パス設計装置２では、まず現用パス探索部２１で現用パスが探索され、迂回パス探索用ネットワーク作成部２２で現用パスに利用された光伝送路に充分大きな距離が付与される。続いて、迂回パス探索部２３で迂回パスを最短経路探索にて探索する。
【０００６】
このように，現用パスを決定した後に迂回パスを探索する場合、現用パスの取り方によっては迂回パスを探索することができない場合が出てくる。その例を図３に示す。図３において、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｚがノードで、リンクで結ばれているリンクに添えている数字がリンクの距離を表すものとし、始点（ノードＡ）から終点（ノードＺ）までの現用パス及び予備パスを設計するものとする。図２において、始点（ノードＡ）から終点（ノードＺ）までの最短パスを現用パスにすると、その現用パスはＡ−Ｂ−Ｃ−Ｚとなる。
【０００７】
【発明が解決しようとする課題】
上述した従来の迂回パスの設計方法では、先に決定した現用パスが迂回パスを取り得ないパスである場合、図４に示すように、現用パス（Ａ−Ｂ−Ｃ−Ｚ）の迂回パスを探索するためにＡ−Ｂ間リンク（双方向）、Ｂ−Ｃ間リンク（双方向）、Ｃ−Ｚ間リンク（双方向）を除いたネットワークであれば、始点（ノードＡ）から終点（ノードＺ）までの経路を探索しようとしても、このネットワークでは、始点（ノードＡ）から終点（ノードＺ）まで到達する経路が存在しておらず、迂回パスの探索に失敗してしまう。
【０００８】
そこで、本発明の目的は上記の問題点を解消し、迂回パスが存在するネットワークにおける迂回パスの探索の失敗を防ぐことができる迂回パス設計装置及びそれに用いる迂回パス設計方法並びにそのプログラムを提供することにある。
【０００９】
【課題を解決するための手段】
本発明による迂回パス設計装置は、第１のネットワークの経路を探索する現用パス探索手段と、前記現用パス探索手段の結果を基に迂回パス探索用の第２のネットワークを作成する迂回パス探索用ネットワーク作成手段と、前記迂回パス探索用ネットワーク作成手段で作成された前記第２のネットワーク上で迂回パスの経路探索を行う迂回パス探索手段と、前記迂回パス探索手段で前記迂回パスが見つからなかった時に前記第１のネットワークを変形する現用パス探索用ネットワーク作成手段とを有し、
前記現用パス探索用ネットワーク作成手段は、前記迂回パス探索手段で到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記現用パス探索手段に渡すことで前記現用パス探索手段と前記迂回パス探索用ネットワーク作成手段と前記迂回パス探索手段と前記現用パス探索用ネットワーク作成手段とによる処理を繰返し行っている。
【００１０】
本発明による迂回パス設計方法は、第１のネットワークの経路を探索する第１のステップと、その探索結果を基に迂回パス探索用の第２のネットワークを作成する第２のステップと、この作成された第２のネットワーク上で迂回パスの経路探索を行う第３のステップと、前記迂回パスが見つからなかった時に前記第１のネットワークを変形する第４のステップとを有し、
前記第４のステップは、前記第３のステップで到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第１の処理を行い、前記第１の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行うことで前記第１のネットワークを変形する第２の処理を行い、
前記第２の処理で得られたネットワークを前記第１のステップに渡すことで前記第１のステップから前記第４のステップまでの探索処理を繰返し行っている。
【００１１】
本発明による迂回パス設計方法のプログラムは、コンピュータに、第１のネットワークの経路を探索する第１の処理と、その探索結果を基に迂回パス探索用の第２のネットワークを作成する第２の処理と、この作成された第２のネットワーク上で迂回パスの経路探索を行う第３の処理と、前記迂回パスが見つからなかった時に前記第１のネットワークを変形する第４の処理とを実行させ、
前記第４の処理において、前記第３の処理で到達したノードの中で現用パスに現れる最も始点から遠いノードを見つける第５の処理を行わせ、前記第５の処理で得られたノードと現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く処理を行わせることで前記第１のネットワークを変形する第６の処理を行わせ、
前記第６の処理で得られたネットワークを前記第１の処理に渡すことで前記第１の処理から前記第４の処理までの探索処理を繰返し行わせている。
【００１２】
すなわち、本発明の迂回パス設計装置は、上記の問題点を解決するために、上記のようなネットワークにおいても迂回パスを設計することができる仕組みを提供するものである。
【００１３】
より具体的に説明すると、本発明の迂回パス設計装置では、現用パス探索部で経路を探索し、迂回パス探索用ネットワーク作成部で迂回パス探索用のネットワークを作成し、そのネットワーク上で迂回パス探索部が経路探索を行っている。この迂回パス探索部で迂回パスが見つからなかった場合、現用パス探索用ネットワーク作成部でネットワークを変形した上で現用パス探索部に戻り、探索を繰返す。
【００１４】
上記のように、先に求めた現用パスに対応する迂回パスが見つからなかった場合に、ネットワークを変形して再び現用パスから探索を繰返す仕組みを取り入れることで、迂回パスが存在するネットワークにおいて迂回パスの探索に失敗することがなくなる。
【００１５】
【発明の実施の形態】
次に、本発明の実施例について図面を参照して説明する。図１は本発明の一実施例による迂回パス設計装置の構成を示すブロック図である。図１において、迂回パス設計装置１は現用パス探索部１１と、迂回パス探索用ネットワーク作成部１２と、迂回パス探索部１３と、現用パス探索用ネットワーク作成部１４と、各部で実行されるプログラムを格納する記録媒体１５とから構成されている。つまり、迂回パス設計装置１の各部は記録媒体１５のプログラムをコンピュータ（図示せず）が実行することで実現される。
【００１６】
図２は本発明の一実施例による設計動作を示すフローチャートであり、図３〜図６は本発明の一実施例による設計動作を説明するための図である。図３〜図６において、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｚがノードで、リンクで結ばれているリンクに添えている数字がリンクの距離を表すものとし、始点（ノードＡ）から終点（ノードＺ）までの現用パス及び予備パスを設計するものとする。
【００１７】
これら図１〜図６を参照して、上記のネットワークで始点（ノードＡ）から終点（ノードＺ）までの現用パス、予備パスを設計する場面について説明する。現用パス探索部１１及び迂回パス探索部１３は最短距離、最小ホップ数等の任意の基準で経路探索可能であり、以下の例では最短距離の経路探索を使ってその動作について説明する。尚、図２に示す処理は迂回パス設計装置１のコンピュータが記録媒体１５に格納されたプログラムを実行することで実現される。
【００１８】
まず、現用パス探索部１１は図３に示すネットワークをそのまま用いて始点（ノードＡ）から終点（ノードＺ）までの最短経路探索を行うと（図２ステップＳ１）、その現用パスはＡ−Ｂ−Ｃ−Ｚとなる。
【００１９】
次に、迂回パス探索用ネットワーク作成部１２は迂回パス探索用のネットワークを作成する（図２ステップＳ２）。すなわち、迂回パス探索用ネットワーク作成部１２は現用パスに使われたリンクを双方向とも取り除く（図２ステップＳ２−１）。今回の処理では、図３から現用パスに使われたＡ−Ｂ間リンク（双方向）、Ｂ−Ｃ間リンク（双方向）、Ｃ−Ｚ間リンク（双方向）を取り除くので、図４に示すようになる。
【００２０】
図４において、迂回パス探索部１３が迂回パス用に始点（ノードＡ）から終点（ノードＺ）を含む全てのノードまでの最短経路探索を行うと（図２ステップＳ３）、ノードＥ、ノードＣまでしか到達することができず、終点（ノードＺ）までの経路を探索することができないので（図２ステップＳ４）、現用パス探索用ネットワーク作成部１４の処理に進む。
【００２１】
現用パス探索用ネットワーク作成部１４では、現用パス探索部１１で得られた現用パス（Ａ−Ｂ−Ｃ−Ｚ）と、迂回パス探索部１３で得られたパス（Ａ−Ｅ−Ｃ）とからネットワークを作成する（図２ステップＳ５）。
【００２２】
すなわち、現用パス探索用ネットワーク作成部１４は迂回パス探索部１３で到達したノードの中で現用パスに現れる最も始点（ノードＡ）から遠いノードを見つける（図２ステップＳ５−１）。今回の処理では、ノードＣが最も始点（ノードＡ）から遠いノードとなる。
【００２３】
現用パス探索用ネットワーク作成部１４は上記の処理で得られたノードと、現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く（図２ステップＳ５−２）。今回の処理では図２からＢ−Ｃ間リンクを双方向とも取り除くことになり、図５に示すようになる。
【００２４】
図５のネットワークを用いて、再び現用パス探索部１１が始点（ノードＡ）から終点（ノードＺ）まで最短経路探索を行うと（図２ステップＳ１）、その現用パスはＡ−Ｂ−Ｄ−Ｚとなる。
【００２５】
次に、迂回パス探索用ネットワーク作成部１２は迂回パス探索用のネットワークを作成する（図２ステップＳ２）。すなわち、迂回パス探索用ネットワーク作成部１２は、前回の処理と同様に、現用パスに使われたリンクを双方向とも取り除く（図２ステップＳ２−１）。今回の処理では、図５から現用パスに使われたＡ−Ｂ間リンク（双方向）、Ｂ−Ｄ間リンク（双方向）、Ｄ−Ｚ間リンク（双方向）を取り除いて図６に示すようになる。
【００２６】
そこで、迂回パス探索部１３が図６で始点（ノードＡ）から終点（ノードＺ）を含む全てのノードまでの最短経路探索を行うと（図２ステップＳ３）、終点（ノードＺ）まで到達し（図２ステップＳ４）、そのパスはＡ−Ｅ−Ｃ−Ｚとなるので、現用パスをパス（Ａ−Ｂ−Ｄ−Ｚ）、迂回パスをパス（Ａ−Ｅ−Ｃ−Ｚ）として（図２ステップＳ４）、迂回パスの探索を終了する。上記のようにして、現用パスで使われたリンクを通らない迂回パスを設計することができる。
【００２７】
このように、迂回パスが存在しない現用パスを選択したとしても、迂回パス設計失敗の原因となるリンクを取り除いて現用パスを再設計するため、迂回パスが存在する任意のネットワークにおいて迂回パスを設計することができる。
【００２８】
次に、本発明の他の実施例について図面を参照して詳細に説明する。上述した本発明の一実施例では現用パスと同じリンクを通らない迂回パスを設計する方法を示しているが、本発明の他の実施例として、現用パスとは同じリンク及び同じノードも通らない迂回パスを設計する方法について説明する。差分は迂回パス探索用ネットワーク設計部１２の動作のみであり、本発明の他の実施例による迂回パス設計装置の構成は図１に示す本発明の一実施例の構成と同様である。
【００２９】
図７は本発明の他の実施例による設計動作を示すフローチャートであり、図８〜図１３は本発明の他の実施例による設計動作を説明するための図である。これら図１及び図７〜図１３を参照して、図７に示すネットワークで始点（ノードＡ）から終点（ノードＺ）までの現用パス、予備パスを設計する場面について説明する。尚、図７に示す処理は迂回パス設計装置１のコンピュータが記録媒体１５に格納されたプログラムを実行することで実現される。
【００３０】
まず、現用パス探索部１１が図８に示すネットワークをそのまま用いて始点（ノードＡ）から終点（ノードＺ）まで最短経路探索を行うと（図７ステップＳ１１）、その現用パスはＡ−Ｂ−Ｃ−Ｚとなる。
【００３１】
次に、迂回パス探索用ネットワーク作成部１２は迂回パス探索用のネットワークを図８から作成する（図７ステップＳ１２）。すなわち、迂回パス探索用ネットワーク作成部１２は現用パスに使われたリンクを双方向とも取り除く（図７ステップＳ１２−１）。今回の処理では現用パスに使われたＡ−Ｂ間リンク（双方向）、Ｂ−Ｃ間リンク（双方向）、Ｃ−Ｚ間リンク（双方向）を取り除く。
【００３２】
続いて、迂回パス探索用ネットワーク作成部１２は始点、終点を除く現用パス上のノードから出ている向きのリンクを片方向だけ取り除く（図７ステップＳ１２−２）。今回の処理では、Ｂ→Ｄ間リンク、Ｃ→Ｄ間リンク、Ｃ→Ｅ間リンクを取り除き、Ｄ→Ｂ間リンク、Ｄ→Ｃ間リンク、Ｅ→Ｃ間リンクを残しておく。このように、図８を上述した迂回パス探索用ネットワーク作成部１２による処理で変形すると、そのネットワークは図９に示すようになる。
【００３３】
図９において、迂回パス探索部１３が迂回パス用に始点（ノードＡ）から終点（ノードＺ）を含む全てのノードまでの最短経路探索を行うと（図７ステップＳ１３）、ノードＥ、ノードＣまでしか到達することができず、終点（ノードＺ）までの経路を探索することができないので（図７ステップＳ１４）、現用パス探索用ネットワーク作成部１４の処理に進む。
【００３４】
現用パス探索用ネットワーク作成部１４では、現用パス探索部１１で得られた現用パスＡ−Ｂ−Ｃ−Ｚと、迂回パス探索部１３で到達したノードＥ、ノードＣからネットワークを作成する（図７ステップＳ１５）。
【００３５】
すなわち、現用パス探索用ネットワーク作成部１４は迂回パス探索部１３で到達したノードの中で現用パスに現れる最も始点（ノードＡ）から遠いノードを見つける（図７ステップＳ１５−１）。今回の処理では、ノードＣが最も始点（ノードＡ）から遠いノードとなる。
【００３６】
現用パス探索用ネットワーク作成部１４は上記の処理で得られたノードと、現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く（図７ステップＳ１５−２）。今回の処理では、図８からＢ−Ｃ間リンクを双方向とも取り除いて図１０に示すようになり、これが現用パス探索用ネットワーク作成部１４の出力となる。
【００３７】
図１０に示すネットワークを用いて、再び現用パス探索部１１が始点（ノードＡ）から終点（ノードＺ）まで最短経路探索を行うと（図７ステップＳ１１）、その現用パスはＡ−Ｂ−Ｄ−Ｃ−Ｚとなる。
【００３８】
次に、迂回パス探索用ネットワーク作成部１２は迂回パス探索用のネットワークを図１０から作成する（図７ステップＳ１２）。すなわち、迂回パス探索用ネットワーク作成部１２は現用パスに使われたリンクを双方向とも取り除く（図７ステップＳ１２−１）。今回の処理では、現用パスに使われたＡ−Ｂ間リンク（双方向）、Ｂ−Ｄ間リンク（双方向）、Ｄ−Ｃ間リンク（双方向）、Ｃ−Ｚ間リンク（双方向）を取り除く。
【００３９】
続いて、迂回パス探索用ネットワーク作成部１２は始点、終点を除く現用パス上のノードから出ている向きのリンクを片方向だけ取り除く（図７ステップＳ１２−２）。今回の処理では、Ｃ→Ｅ間リンク、Ｄ→Ｚ間リンクを取り除き、Ｅ→Ｃ間リンク、Ｚ→Ｄ間リンクを残しておく。このように、図１０を上述した迂回パス探索用ネットワーク作成部１２による処理で変形すると、そのネットワークは図１１に示すようになる。
【００４０】
図１１上で、再び迂回パス探索部１３が迂回パス用に始点（ノードＡ）から終点（ノードＺ）を含む全てのノードまでの最短経路探索を行うと（図７ステップＳ１３）、ノードＥ、ノードＣまでしか到達することができず、終点（ノードＺ）までの経路を探索することができないので（図７ステップＳ１４）、現用パス探索用ネットワーク作成部１４の処理に進む。
【００４１】
現用パス探索用ネットワーク作成部１４では、現用パス探索部１１で得られた現用パス（Ａ−Ｂ−Ｄ−Ｃ−Ｚ）と、迂回パス探索部１３で到達したノードＥ、ノードＣからネットワークを作成する（図７ステップＳ１５）。
【００４２】
すなわち、現用パス探索用ネットワーク作成部１４は迂回パス探索部１３で到達したノードの中で現用パスに現れる最も始点（ノードＡ）から遠いノードを見つける（図７ステップＳ１５−１）。今回の処理では、ノードＣが最も始点（ノードＡ）から遠いノードである。
【００４３】
続いて、現用パス探索用ネットワーク作成部１４は上記の処理で得られたノードと、現用パス上でのその直前のノードとの間のリンクを双方向とも取り除く（図７ステップＳ１５−２）。今回の処理では、図１０からＤ−Ｃ間リンクを双方向とも取り除いて図１２に示すようになり、これが現用パス探索用ネットワーク作成部１４の出力となる。
【００４４】
図１２のネットワークを用いて、現用パス探索部１１は始点（ノードＡ）から終点（ノードＺ）まで三度目の最短経路探索を行うと（図７ステップＳ１１）、その現用パスはＡ−Ｂ−Ｄ−Ｚとなる。
【００４５】
次に、迂回パス探索用ネットワーク作成部１２は迂回パス探索用のネットワークを図１２から作成する（図７ステップＳ１２）。すなわち、迂回パス探索用ネットワーク作成部１２は現用パスに使われたリンクを双方向とも取り除く（図７ステップＳ１２−１）。今回の処理では、現用パスに使われたＡ−Ｂ間リンク（双方向）、Ｂ−Ｄ間リンク（双方向）、Ｄ−Ｚ間リンク（双方向）を取り除く。
【００４６】
続いて、迂回パス探索用ネットワーク作成部１２は始点、終点を除く現用パス上のノードから出ている向きのリンクを片方向だけ取り除く（図７ステップＳ１２−２）。今回の処理では、取り除くリンクが存在しない。このように、図１２を上述した迂回パス探索用ネットワーク作成部１２の処理で変形すると、そのネットワークは図１３に示すようになる。
【００４７】
そこで、迂回パス探索部１３が図１３で始点（ノードＡ）から終点（ノードＺ）を含む全てのノードまでの最短経路探索を行うと（図７ステップＳ１３）、終点（ノードＺ）まで到達するので（図７ステップＳ１４）、そのパスはＡ−Ｅ−Ｃ−Ｚとなり、現用パスをパス（Ａ−Ｂ−Ｄ−Ｚ）、迂回パスをパス（Ａ−Ｅ−Ｃ−Ｚ）として（図７ステップＳ１６）、迂回パスの探索を終了する。上述したようにして、現用パスで使われたリンク及びノードを通らない迂回パスを設計することができる。
【００４８】
【発明の効果】
以上説明したように本発明は、ネットワークの経路を探索し、その探索結果を基に迂回パス探索用のネットワークを作成し、この作成されたネットワーク上で迂回パスの経路探索を行い、迂回パスが見つからなかった時にネットワークを変形するという処理を繰返し行うことによって、迂回パスが存在するネットワークにおける迂回パスの探索の失敗を防ぐことができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施例による迂回パス設計装置の構成を示すブロック図である。
【図２】本発明の一実施例による設計動作を示すフローチャートである。
【図３】本発明の一実施例による設計動作を説明するための図である。
【図４】本発明の一実施例による設計動作を説明するための図である。
【図５】本発明の一実施例による設計動作を説明するための図である。
【図６】本発明の一実施例による設計動作を説明するための図である。
【図７】本発明の他の実施例による設計動作を示すフローチャートである。
【図８】本発明の他の実施例による設計動作を説明するための図である。
【図９】本発明の他の実施例による設計動作を説明するための図である。
【図１０】本発明の他の実施例による設計動作を説明するための図である。
【図１１】本発明の他の実施例による設計動作を説明するための図である。
【図１２】本発明の他の実施例による設計動作を説明するための図である。
【図１３】本発明の他の実施例による設計動作を説明するための図である。
【図１４】従来例による迂回パス設計装置の構成を示すブロック図である。
【符号の説明】
１  迂回パス設計装置
１１  現用パス探索部
１２  迂回パス探索用ネットワーク作成部
１３  迂回パス探索部
１４  現用パス探索用ネットワーク作成部
１５  記録媒体
【図１】
0003707427.tif 000002
【図２】
0003707427.tif 000003
【図３】
0003707427.tif 000004
【図４】
0003707427.tif 000005
【図５】
0003707427.tif 000006
【図６】
0003707427.tif 000007
【図７】
0003707427.tif 000008
【図８】
0003707427.tif 000009
【図９】
0003707427.tif 000010
【図１０】
0003707427.tif 000011
【図１１】
0003707427.tif 000012
【図１２】
0003707427.tif 000013
【図１３】
0003707427.tif 000014
【図１４】
0003707427.tif 000015