(57)【要約】【課題】通信ケーブルの敷設工事コストを低減することが可能で、かつ、冗長性を持つリング形状の網の設計を支援するネットワーク設計支援システムを提供する。【解決手段】ネットワーク設計支援システムは、加入者位置情報に基づいて複数の加入者を複数のクラスタに分割し、電柱等の通信ケーブルを保持する頂点の位置情報に基づいて、クラスタの中心に近い頂点を中継ノードの敷設位置として決定し、中継ノードの敷設位置と、複数の頂点の位置情報とに基づいて、同一の頂点を２度以上通過しないように、複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する。【選択図】図１Ｅ
2014123849.tif 000002
【特許請求の範囲】
【請求項１】
リング状のネットワークを設計するネットワーク設計支援システムであって、
複数の加入者のそれぞれ位置を示す加入者位置情報と、通信ケーブルを敷設可能な複数の頂点の位置を示す敷設可能位置情報と、前記複数の頂点間に通信ケーブルを敷設する際のコストを示す敷設コスト情報とを記憶した記憶手段と、
前記加入者位置情報に基づいて前記複数の加入者を複数のクラスタに分割するクラスタリング手段と、
前記敷設可能位置情報に基づいて、前記複数のクラスタの中心に近い頂点を中継ノードの敷設位置として決定する敷設位置決定手段と、
前記中継ノードの敷設位置と、前記複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、前記複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する閉路決定手段と
を有することを特徴とするネットワーク設計支援システム。
【請求項２】
前記閉路の全長が所定長を超えているか、または、前記閉路に含まれる中継ノードの数が所定数を超えているときに、前記閉路を複数の閉路に分割する分割手段をさらに有し、
前記分割手段は、分割後の複数の閉路のそれぞれの全長が前記所定長を超えず、かつ、当該分割後の複数の閉路のそれぞれに含まれる中継ノードの数が所定数を超えないように、前記閉路を複数の閉路に分割する分割点を決定することを特徴とする請求項１に記載のネットワーク設計支援システム。
【請求項３】
前記閉路決定手段は、前記閉路を収容する収容局から前記分割点までの経路を決定する際に、前記収容局から前記分割点までの経路を、前記分割後の複数の閉路にとって重複した経路として決定することを特徴とする請求項２に記載のネットワーク設計支援システム。
【請求項４】
前記閉路決定手段は、前記閉路が通過する複数の頂点のうち重複して通過する頂点を特定し、前記重複して通過する頂点について前記閉路が通過する順番を他の頂点と入れ替えることで、前記閉路の全長を短縮することを特徴とする請求項１ないし３のいずれか１項に記載のネットワーク設計支援システム。
【請求項５】
前記分割手段は、前記閉路を構成する複数の中継ノードをそれぞれ分割点の候補として選択し、その分割点により分割して得られる複数の分割経路の総距離を求め、総距離が最短となる中継ノードを決定することを特徴とする請求項２に記載のネットワーク設計支援システム。
【請求項６】
前記複数の分割経路のそれぞれについて前記敷設コスト情報に基づいてケーブルの敷設コストが最も小さくなるように、各分割経路におけるケーブル敷設経路を決定する経路導出部をさらに備えることを特徴とする請求項５に記載のネットワーク設計支援システム。
【請求項７】
前記複数のクラスタのそれぞれについて、そのクラスタの中継ノードからそのクラスタを構成する加入者までのケーブル敷設経路を、前記敷設コスト情報に基づいてケーブルの敷設コストが最も小さくなるように、決定する網設計部をさらに備えることを特徴とする請求項１ないし６のいずれか１項に記載のネットワーク設計支援システム。
【請求項８】
１つのクラスタを構成する１つの中継ノードと複数の加入者について、当該中継ノードに対して前記複数の加入者のそれぞれを接続する経路を部分グラフとし、複数の部分グラフを新たな複数の頂点とし、当該新たな複数の頂点を結ぶ経路の敷設コストを求める経路網再構成手段をさらに備え、
前記閉路決定手段は、当該敷設コストの合計が最小となるように、当該新たな複数の頂点間を通る閉路を決定することを特徴とする請求項１に記載のネットワーク設計支援システム。
【請求項９】
コンピュータに、
複数の加入者のそれぞれ位置を示す加入者位置情報と、通信ケーブルを敷設可能な複数の頂点の位置を示す敷設可能位置情報と、前記複数の頂点間に通信ケーブルを敷設する際のコストを示す敷設コスト情報とを記憶した記憶手段と、
前記加入者位置情報に基づいて前記複数の加入者を複数のクラスタに配分するクラスタリング手段と、
前記敷設可能位置情報に基づいて、前記複数のクラスタの中心に近い頂点を中継ノードの敷設位置として決定する敷設位置決定手段と、
前記中継ノードの敷設位置と、前記複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、前記複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する閉路決定手段と
して機能させることを特徴とするコンピュータプログラム。
【請求項１０】
リング状のネットワークを設計する方法であって、
記憶手段が、複数の加入者のそれぞれ位置を示す加入者位置情報と、通信ケーブルを敷設可能な複数の頂点の位置を示す敷設可能位置情報と、前記複数の頂点間に通信ケーブルを敷設する際のコストを示す敷設コスト情報とを記憶するステップと、
クラスタリング手段が、前記加入者位置情報に基づいて前記複数の加入者を複数のクラスタに分割するステップと、
敷設位置決定手段が、前記敷設可能位置情報に基づいて、前記複数のクラスタの中心に近い頂点を中継ノードの敷設位置として決定するステップと、
閉路決定手段が、前記中継ノードの敷設位置と、前記複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、前記複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定するステップと
を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、リング形状の通信網設備の設計を支援する、ネットワーク設計支援システムに関するものである。
【背景技術】
【０００２】
一般に、光通信ネットワークは、通信事業者の複数の拠点間を結ぶ拠点間ネットワークと、加入者と収容局とを結ぶアクセス網とに分類される。従来は、拠点間ネットワークとしてリング状の網設備が採用され、アクセス網としてはツリー状の網が採用されていた。リング状の網設備は冗長経路を持つネットワークを容易に構築できるという特徴を有している。そのため、リング状の網設備は、通信事業者の複数の拠点間を結ぶためなどに広く用いられている。一方で、リング状の網はツリー状の網と比較して敷設コストが高いため、収容局から加入者装置（以下、単に加入者と呼ぶ。）までのネットワークであるアクセス網においてはあまり用いられてはいない。つまり、アクセス網においては敷設コストで有利なツリー状の網が主流となっている。
【０００３】
しかし、将来においては、加入者と収容局の間の網設備に冗長経路が必要とされるケースが増えるものと予想される。したがって、将来は、アクセス網にもリング状の網設備が普及するであろう。冗長性の増加と敷設コストの増加の抑制とを同時に達成するために、加入者と収容局の間に複数の中継ノードを設置し、加入者と中継ノードとの間をツリー状の網設備で接続し、中継ノードと収容局の間をリング状の網設備で接続する形態が考えられる。
【０００４】
これまでのところ、リング状の網を自動設計する設計支援システムが提案されていない。このため、このような網構成を採用する場合には、熟練した技術者が手作業で網設計を行う必要がある。リング状の網設備は、通常、設備仕様により、単一リング網に収容可能な中継ノードの数と、単一リング網の最大経路長が制限される。そのため、通常は加入者数に応じて複数のリング網を設計する必要がある。この問題は、時間枠・容量制約付き配送計画問題とみなすことができ、いわゆるＮＰ困難であることが示されている。
【０００５】
配送計画問題は、１か所の倉庫から、複数台の輸送車によりあらかじめ指定されたすべての客のもとへ荷物を配送し、各輸送車が倉庫に戻るまでの経路を求める問題である。時間枠・容量制約付き配送計画問題は、前記問題に、倉庫に戻るまでの時間制約と、単一の輸送車が配送を行うことができる客数の上限の制約とが付加されたものである。時間枠制約を単一リング網の経路長の制約とみなし、容量制約を単一リング網が収容可能な中継ノード数の制約とみなすことで、網設計問題を時間枠・容量制約付き配送計画問題とみなすことができる。
【０００６】
時間枠・容量制約付き配送計画問題はＮＰ困難であるため、厳密に最短経路となる解を求めるためには客数の指数関数時間以上の計算時間が必要であると考えられている。しかし、容量制約の値が小さい場合において、任意に高精度な近似解を客数の多項式時間で求める手法が提案されている。
【０００７】
非特許文献１には、すべての頂点を通過する閉路のうち、閉路長がほぼ最小となる設計手法が記載されている。
【０００８】
非特許文献２には、単一リング網で収容可能な中継ノード数が十分小さい場合において、経路長がほぼ最小となる配送計画問題の解法が記載されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Sanjeev Arora, "Polynomial time approximation for Euclidian traveling salesman and other geometric problems,'' Journal of the ACM, Vol. 45, No. 5, pp. 753 - 782, 1998
【非特許文献２】Aparna Das, et al., "A quasi-polynomial time approximation fir Euclidian capacitated vehicle routing,'' Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
【発明の概要】
【発明が解決しようとする課題】
【００１０】
アクセス網において通信ケーブルは電柱や地下坑道などに敷設される。一般的に、単位長さあたりの通信ケーブル敷設工事コストは、通信ケーブルの材料コストよりも大きい。したがって、アクセス網設備の構築コストを低減するためには、通信ケーブル敷設工事を行う経路長を最小化する設計を行う必要がある。しかし、通信ケーブル敷設工事コストを最小化するリング網の設計アルゴリズムは確立されておらず、熟練した技術者が手作業で網設計を行う必要がある。
【００１１】
リング網の設計問題は、時間枠・容量制約付き配送計画問題に帰着することができる。平面中に頂点が存在する時間枠・容量制約付き配送計画問題に対し、頂点数の多項式時間で近似解を求める手法は、上述したようにすでに提案されている。
【００１２】
しかし、上記の手法はいずれも任意の２点間に直線状に通信ケーブルが敷設可能であるという点を前提としている。一方、実際の網設計作業では架空送電線網や道路網などに沿って通信ケーブルを敷設する必要がある。通信ケーブル敷設可能経路の制約がない場合、加入者数を頂点数とした時間枠・容量制約付き配送計画問題に帰着することが可能であるが、上記の制約がある場合、加入者数に等しい数の頂点に加えて、通信ケーブル敷設可能経路網の中の頂点も考慮する必要がある。また、それらの頂点を通過することは必須ではないため、考慮すべきパターンが増加し、問題規模が急激に大きくなる。また、これらの手法は通信ケーブル敷設工事長ではなく通信ケーブル長を最小化することを目的としているため、必ずしも敷設コスト低減に有効ではない。
【００１３】
また、リング網では全ての加入者が２方向で収容局と接続されているという特徴がある。このため、任意の１か所で回線障害が発生した場合においても、すべての加入者は少なくとも一方向で収容局と接続されており、収容局との通信を継続できる。一方で、リング網が同じ経路を複数回通過する場合、そのような回線障害に対する耐性を失うため、設計の際にはリング網が同じ経路を通過しないよう配慮する必要がある。任意の２点間に直線状に通信ケーブルが敷設可能であれば、異なる頂点を結ぶ経路は異なることが保証されるが、経路網に制約がある場合は異なる頂点を結ぶ経路の一部が重複する可能性がある。リング網を設計する際には経路が重複しないように配慮する必要がある。よって、熟練した技術者の手作業では、作業に膨大な手間と時間を要するという課題がある。
【００１４】
上述した非特許文献１の手法は、平面上の点をすべて通過する閉路のうち、最短閉路長を持つものの近似解を多項式時間で求めるものである。この手法は、通信ケーブル材料コストを最適化することが可能であるが、経路長を十分短くするためには膨大な計算量が必要となるという課題がある。また、この手法は、任意の２点間が最短距離で接続可能であることを前提としている。このため、通信ケーブルが架空送電線網や道路網に沿ってのみ設置可能である実際の環境下では適用できないという課題がある。
【００１５】
非特許文献２の手法は、容量制約付きの配送計画問題に対し、近似解を多項式時間で求めるものである。この手法は、時間枠の制約を考慮しておらず、単一リング網の最大経路長の制約条件を満たす網を設計することはできない。
【００１６】
そこで、本発明は、通信ケーブルの敷設工事コストを低減することが可能で、かつ、冗長性を持つリング形状の網の設計を支援するネットワーク設計支援システムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明は、たとえば、リング状のネットワークを設計するネットワーク設計支援システムであって、
複数の加入者のそれぞれ位置を示す加入者位置情報と、通信ケーブルを敷設可能な複数の頂点の位置を示す敷設可能位置情報と、前記複数の頂点間に通信ケーブルを敷設する際のコストを示す敷設コスト情報とを記憶した記憶手段と、
前記加入者位置情報に基づいて前記複数の加入者を複数のクラスタに分割するクラスタリング手段と、
前記敷設可能位置情報に基づいて、前記複数のクラスタの中心に近い頂点を中継ノードの敷設位置として決定する敷設位置決定手段と、
前記中継ノードの敷設位置と、前記複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、前記複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する閉路決定手段と
を有することを特徴とする。
【発明の効果】
【００１８】
本発明によれば、中継ノードの敷設位置と、複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定するため、通信ケーブルの敷設工事コストを低減することができる。また、設計されたネットワークは閉路であるため、冗長性を有する。
【図面の簡単な説明】
【００１９】
【図１Ａ】収容局と複数の加入者の位置関係の一例を示す図
【図１Ｂ】クラスタリングの一例を示す図
【図１Ｃ】すべてのクラスタを通過する閉路設計の一例を示す図
【図１Ｄ】閉路の分割を説明するための図
【図１Ｅ】ネットワーク設計支援方法の各工程を示すフローチャート
【図２】実施例１の概略構成図
【図３】実施例１におけるネットワーク設計支援システムの閉路構築処理手順の一例を示す図
【図４】実施例１における閉路構築処理手順の一例を示す図
【図５】実施例１における閉路構築処理手順の一例を示す図
【図６】実施例１における閉路構築処理手順の一例を示す図
【図７】実施例１における閉路修正処理手順を示すフローチャート
【図８】実施例１における閉路修正処理手順の一例を示す図
【図９】実施例１における閉路分割処理手順を示すフローチャート
【図１０】実施例１における閉路分割処理手順の一例を示す図
【図１１】実施例２におけるネットワーク設計支援システムの概略構成図
【図１２】実施例２における経路網再構成処理を示すフローチャート
【図１３】実施例２における経路網再構成処理の一例を示す図
【図１４】実施例２における経路網再構成処理の一例を示す図
【図１５】実施例２における経路網再構成処理の一例を示す図
【図１６】実施例３の概略構成図
【発明を実施するための形態】
【００２０】
本実施形態は、複数の加入者の位置情報と、通信ケーブルを敷設可能な経路網の情報とから中継ノードの位置を決定する機能と、前記機能により生成された複数の中継ノードの位置情報と、１つの収容局の位置情報と、前記経路網の情報と、リング網の最大中継ノード数と最大距離の情報とから敷設工事コスト低減したリング形状の網設備を設計する機能とを有するものである。
【００２１】
＜実施形態の概要＞
図１Ａないし図１Ｄを用いて、ネットワーク設計支援システムが実行するアルゴリズムの概要を説明する。図１Ａが示すように、収容局１００の周囲には複数の加入者１０１ａないし１０１ｋが配置されているものと仮定する。加入者１０１ａないし１０１ｋは、加入者宅に配置されている加入者装置の略称である。ここで、加入者１０１ａないし１０１ｋの位置情報（緯度、経度）と収容局１００の位置情報（緯度、経度）は予めデータベースに格納されているものとする。
【００２２】
図１Ｂが示すように、加入者１０１ａないし１０１ｋに対してクラスタリングを行う。ここでは、１つのノードに収容可能な加入者数と、各加入者の位置情報とを元に、クラスタリングが実行される。図１Ｂでは、１つのクラスタには最大で３つの加入者を収容（配分ないしは分配）できると仮定している。第１のクラスタ１０２ａには、距離が相対的に近い３つの加入者１０１ａ、１０１ｂ、１０１ｃが割り当てられている。第２のクラスタ１０２ｂには、距離が相対的に近い２つの加入者１０１ｄ、１０１ｅが割り当てられている。第３のクラスタ１０２ｃには、距離が相対的に近い３つの加入者１０１ｆ、１０１ｇ、１０１ｈが割り当てられている。第４のクラスタ１０２ｅには、距離が相対的に近い３つの加入者１０１ｉ、１０１ｊ、１０１ｋが割り当てられている。そして、各クラスタの中心には１つのノードが割り当てられる。第１のクラスタ１０２ａの中心近くには、第１のノード１０３ａが配置される。第２のクラスタ１０２ｂの中心近くには、第１のノード１０３ｂが配置される。第３のクラスタ１０２ｃの中心近くには、第３のノード１０３ｃが配置される。第４のクラスタ１０２ｄの中心近くには、第４のノード１０３ｄが配置される。なお、ノードの位置は、ノードを配置可能な電柱などの位置によって決まるため、クラスタの中心近くに位置する電柱の位置がノードの位置として決定される。電柱などの経路の情報も予めデータベース化しておくものとする。
【００２３】
図１Ｃでは、ノードと基地局を結ぶ経路１０４を決定するとともに、ノード１０３ａないしノード１０３ｄと収容局１００と結ぶリング１０５を決定する。ノードと基地局を結ぶ経路は、敷設コストが最低となるように、たとえば、経路を構成する電柱間の距離の和が最短となるように決定する。同様に、ノード１０３ａないしノード１０３ｄと収容局１００と結ぶリング１０５の経路も、経路を構成する電柱間の距離の和が最短となるように決定する。リング１０５に含まれているノードの数が、１つのノードに収容可能な最大ノード数を超えていたり、リング１０５の経路が所定の最大長を超えていたりした場合には、図１Ｄで示すようなリングの分割処理が必要となる。
【００２４】
図１Ｄでは、リング１０５の分割するためのコストが最低となるように、分割点１０７を決定する。たとえば、リング１０５の任意の場所を分割点１０７として選択し、分割点１０７によって分割される２つのリング１０６ａ、１０６ｂに含まれるノード数が最大ノード数を超えず、かつ、２つのリング１０６ａ、１０６ｂの各経路長が最大長を超えず、かつ、収容局１００から分割点１０７までの経路の敷設コストが最低となるように、分割点１０７を決定する。ただし、敷設工事コストを削減するために、２つのリング１０６ａ、１０６ｂにおいて経路の重複を許容してもよい。図１Ｄにおいて、収容局１００から分割点１０７までの経路が、２つのリング１０６ａ、１０６ｂに対して重複している。一方で、回線障害に対するプロテクションを実現するための経路の冗長性を確保するために、各リングにおいては経路の重複を認めないこととする。
【００２５】
以上のように決定することで、敷設工事コストを削減しつつ、回線障害に対するプロテクションを有したリング形のアクセス網を提供できるようになる。
【００２６】
次に、図２および図３を用いてネットワーク設計支援システムの詳細について説明する。
【００２７】
図１Ｅは、ネットワーク設計支援システムのプロセッサが実行するネットワーク設計支援プログラムの手順を示すフローチャートである。
【００２８】
Ｓ１１で、プロセッサは、１つのノードに収容可能な加入者数（上限加入者数）と、各加入者の位置情報とを元に、クラスタリングを実行する。プロセッサは、地理的な位置が近い加入者を上限加入者数に達するまで順番に選択することで、クラスタリングを実行する。なお、地理的な距離が所定の閾値を超える場合、プロセッサは、１つのクラスタに属する加入者数を上限加入者数未満としてもよい。
【００２９】
Ｓ１２で、プロセッサは、中継ノードの位置を決定する。上述したように、プロセッサは、クラスタの中心位置に近い頂点（電柱など、中継ノードや通信ケーブルを敷設可能な位置）をデータベースから抽出し、中継ノードの位置に決定する。
【００３０】
Ｓ１３で、プロセッサは、中継ノードから加入者までの通信ケーブルの敷設経路を決定する。たとえば、プロセッサは、敷設工事コストを削減するために、各加入者までの通信ケーブルの距離（敷設経路の距離）の合計が最短となるように、敷設経路を決定する。なお、中継ノードから加入者までのネットワークはツリー状のネットワークとなる。
【００３１】
Ｓ１４で、プロセッサは、リングを構成する経路を決定する。プロセッサは、各クラスタの中継ノードをリング状に接続するように、中継ノードの位置、収容局の位置および頂点の位置に基づいて、リングネットワークを構成する経路を決定する。
【００３２】
Ｓ１５で、プロセッサは、必要に応じてリングの経路を修正する。たとえば、リングの冗長性を考慮すると、同一の頂点を２度以上通過することは望ましくない。そこで、プロセッサは、リングの経路として選択された各頂点について一度だけ通過するように、経路を修正する。たとえば、プロセッサは、２度以上通過することになってしまった頂点について通過する順番を他の頂点と入れ替えたりすることで、各頂点を一度だけ通過するように経路を修正する。
【００３３】
Ｓ１６で、プロセッサは、リングの分割が必要かどうかを判定する。たとえば、リングの経路の全長が所定の最大長を超えることは設備の制約上、許されない。また、１つのリングに収容可能なノード数にも上限値が存在する。よって、プロセッサは、リングの経路の全長を求め最大長と比較し、全長が最大長を超えていれば、リングの分割が必要と判断する。また、プロセッサは、リングに含まれている中継ノードの総数を求め、総数と上限数とを比較し、総数が上限数を超えていれば、リングの分割が必要と判断する。リングの分割が不要であれば本処理を終了するが、リングの分割が必要であればＳ１７に進む。
【００３４】
Ｓ１７で、プロセッサは、リングの分割を実行する。たとえば、プロセッサは、リングを分割して形成される各サブリングの数が最小となるように、リングを分割する頂点（分割点）を決定する。たとえば、プロセッサは、各サブリングに含まれるノードの総数とサブリングの全長とが上述した制約に違反しないように、分割点を決定する。プロセッサは、リングに含まれる１つの頂点を任意に選択し、その頂点でリングを分割して形成される各サブリングが制約に反しないかどうかを判定する。制約に反すれば、次の頂点を選択し、同様の判定を実行する。すべての頂点について判定しても制約を満たす頂点がなければ、分割点を１つ増やして、同様の判定処理を実行する。なお、各サブリングのそれぞれについては同一の頂点を２度通ることは禁止するが、複数の異なるサブリングが同一の頂点を経路に含むことは許容する。これは、回線障害に対するプロテクションを実現するためである。
【００３５】
＜実施例１＞
ネットワーク設計支援システムは、本実施例にかかる手順を含むコンピュータプログラムをコンピュータに実行させることで実現できる。コンピュータは、よく知られているように、プログラムを実行するＣＰＵ、プログラムを記憶したりワークエリアとして機能したりするＲＯＭ、ＲＡＭ、ハードディスクドライブなどの記憶装置、情報を入力する入力装置および情報を表示する表示装置を有している。
【００３６】
図２に即して、第１の実施例による処理内容を説明する。パラメータ記憶部２０１は、ネットワーク設計支援に関与する各種のパラメータを記憶する記憶装置（メモリやハードディスクドライブ装置など）である。たとえば、パラメータ記憶部２０１は、入力装置２０８から入力された網設計の対象となるエリア情報を記憶する。ＣＰＵ２００は、各部を統括的に制御する制御ユニットである。ＣＰＵ２００がプログラムを実行することで実現する機能としては、たとえば、加入者クラスタリング・加入者‐中継ノード間網設計部２０２と、分割処理・閉路設計部２０３などがある。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、パラメータ記憶部２０１と、加入者位置情報データベース２０４と、敷設可能経路網情報データベース２０５とから情報を取得し、加入者‐中継ノード間の網設計を行い、設計結果をパラメータ記憶部２０１に記憶する。分割処理・閉路設計部２０３は、パラメータ記憶部２０１と敷設可能経路網情報データベース２０５と収容局設備情報データベース２０６から情報を取得し、すべての中継ノードがいずれかのリングを通過するように複数のリング網を設計し、設計結果をパラメータ記憶部２０１に記憶する。ＣＰＵ２００は、パラメータ記憶部２０１から読み出した設計結果を表示装置２０７に出力する。以下で、各部における具体的な処理内容を説明する。
【００３７】
［加入者位置情報データベース］
加入者位置情報データベース２０４は、複数の加入者のそれぞれ位置を示す加入者位置情報を記憶した記憶手段として機能する。加入者位置情報データベース２０４は、たとえば、サービス加入者または今後加入が見込まれるサービス加入予定者の位置情報ｓｉ  （ｉ＝１，２，...，Ｎｓ）の集合Ｓを保持する。
【００３８】
［敷設可能経路情報データベース］
敷設可能経路網情報データベース２０５は、通信ケーブルを敷設可能な複数の頂点（電柱など）の位置を示す敷設可能位置情報を記憶した記憶手段として機能する。敷設可能経路網情報データベース２０５は、たとえば、光ファイバケーブルなどの通信ケーブルを敷設可能な経路の情報を、頂点集合Ｖと辺集合Ｅにより定義されるグラフＧ＝（Ｖ，Ｅ）の形式で保持する。頂点集合Ｖは各頂点の位置情報を保持する頂点ｖｉ  （ｉ＝１，２，...，ｎｖ）で構成される。辺集合Ｅは各辺の重みを表す辺ｅｉｊ  （ｉ，ｊ＝１，２，...，ｎｖ）で構成される。たとえば、敷設可能経路網として架空送電線網を想定する場合、頂点ｖｉは電柱の位置を表し、辺の重みｅｉｊは頂点ｖｉの電柱と頂点ｖｊの電柱の間の距離を表す。頂点ｖｉの電柱と頂点ｖｊの電柱の間に通信ケーブルの敷設が不可能な場合は、ｅｉｊ＝∞（または、十分大きな値）とするか、またはｅｉｊを保持しない。
【００３９】
［収容局設備情報データベース］
収容局設備情報データベース２０６は、複数の頂点間に通信ケーブルを敷設する際のコストを示す敷設コスト情報を記憶した記憶手段として機能する。収容局設備情報データベース２０６は、たとえば、収容局の位置情報Ｃと、収容局の設備の制約条件である単一のリング網あたりの収容可能中継ノード数Ｎｍａｘ，ｎと、単一リング網の最大長Ｌｍａｘとを保持する。
【００４０】
［加入者クラスタリング・加入者‐中継ノード間網設計部］
加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、加入者位置情報に基づいて複数の加入者を複数のクラスタに分割するクラスタリング手段と、敷設可能位置情報に基づいて、複数のクラスタの中心に近い頂点を中継ノードの敷設位置として決定する敷設位置決定手段として機能する。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、たとえば、網設計を行うエリア情報をパラメータ記憶部２０１から取得する。エリア情報としては、地理的エリア（Ａ県Ｂ市Ｃ区Ｄ町など）の識別情報（郵便番号など）などが含まれている。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、エリア情報で指定されるエリアに含まれる加入者の位置情報Ｓを加入者位置情報データベース２０４から取得する。加入者の位置情報Ｓはエリアの識別情報と対応付けて加入者位置情報データベース２０４に記憶されている。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、各加入者を、各加入者間の距離を非類似度としてＮ＿ｎ個にクラスタ分割する。このクラスタリングには、ｋ−ｍｅｄｏｉｄｓ法などを用いることができる。そして、クラスタの中心付近に存在する頂点を中継ノードの位置とする。たとえば、ｋ−ｍｅｄｏｉｄｓ法においてクラスタリングに利用するセントロイドと呼ばれる頂点を中継ノードの位置とすることができる。
【００４１】
加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、各クラスタについて、中継ノードとそのクラスタに所属する加入者とを接続する網を設計する。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、設計対象の加入者と中継ノードとを結ぶすべての潜在的にあり得る経路網のうち、網に用いられる辺の重みの和が最小となる最小シュタイナー木を設計する。これは、通信ケーブル敷設工事コストを低減するためである。まず、加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、同一クラスタに属するすべての頂点を含む矩形の領域を設定する。これは、計算量を抑えるためである。そして、加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、設定した領域内に存在する複数の頂点および複数の辺を抽出し、部分グラフＧ＿ｓ＝（Ｖ＿ｓ，Ｅ＿ｓ）を決定する。加入者クラスタリング・加入者‐中継ノード間網設計部２０２は、この部分グラフＧ＿ｓにＤｒｅｙｆｕｓ−Ｗａｇｎｅｒ法を適用することで、最小シュタイナー木を設計する。
【００４２】
［分割処理・閉路設計部］
分割処理・閉路設計部２０３は、中継ノードの敷設位置と、複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する閉路決定手段と、閉路の全長が所定長を超えているか、または、閉路に含まれる中継ノードの数が所定数を超えているときに、閉路を複数の閉路に分割する分割手段として機能する。分割処理・閉路設計部２０３は、たとえば、収容局とすべての中継ノードを結ぶリング網を設計する閉路設計処理と、リング網の経路長を短縮する閉路修正処理と、リング網が単一リング網あたりの収容可能中継ノード数Ｎｍａｘ，ｎと単一リング網の最大長Ｌｍａｘの制約を満たすようリング網を分割する閉路分割処理とを順番に実行する。以下、図３から図１０を用いて分割処理・閉路設計部２０３が実行する具体的な処理内容を説明する。
【００４３】
［閉路構築処理］
閉路構築の代表的な手法として、最近隣接法がある。この手法は始点から近い点を順に接続し、すべての点を通る経路を求める。その後、最後に通過した点と始点を接続することで閉路を構築する手法である。しかし、この手法は通信ケーブルの敷設可能経路情報を考慮しないため、単一リング内において経路が重複（単一のリングを構成する経路が同一の通信ケーブルを２度以上にわたって通過すること）し、冗長性を確保できない可能性がある。そこで、本実施形態は、この手法に経路重複を避ける処理を加える。以下で、本実施形態における閉路構築処理の処理内容を具体的に説明する。
【００４４】
図３、図４、図５および図６を用いて閉路構築処理の処理内容を説明する。分割処理・閉路設計部２０３は、パラメータ記憶部２０１から中継ノードの位置情報を取得する。中継ノードは経路上の任意の位置に設置可能であるが、ここではいずれかの頂点ｖｉ上に設置されるものとする。頂点ｖｉは、電柱等に対応しているため、頂点ｖｉであれば中継ノードを安価に敷設できるからである。図３、図４、図５および図６中では、収容局はｖ１の位置にあり、ｖ０，ｖ４，ｖ６，ｖ１１上に中継ノードが設置されている。また、図３、図４、図５および図６中の各辺の長さは全て１と仮定する。
【００４５】
次に、分割処理・閉路設計部２０３は、収容局ｖ１からの経路長が最短となる中継ノードと、当該中継ノードへ至る最短経路を求める。図３中では、ｖ０またはｖ４が収容局ｖ０からの経路長が最小となる中継ノードである。経路長が最小となる中継ノードが複数存在する場合は、他のパラメータを考慮してもよいし、乱数処理でいずれか１つを選択してもよい。今回はｖ４を選択するものとする。ｖｉとｖｊの最短経路をＰｉｊで表すと、その最短経路はＰ１４＝｛ｅ１４｝である。ｖｉとｖｊが隣接していない場合、この最短経路は、一般にダイクストラ（Ｄｉｊｋｓｔｒａ）法やベルマン‐フォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）法などにより求めることができる。
【００４６】
上述したように、リング網が同じ経路を複数回通過して構成されている場合、リング網の冗長性は確保されない。複数の中継ノード間の移動が直線的に行われる場合、このような可能性を考慮する必要性は小さいが、通信ケーブル敷設可能経路が限られている実際の環境を想定して閉路を設計する際には、閉路中に同じ辺が複数回含まれないようにする必要がある。このため、分割処理・閉路設計部２０３は、一度最短経路に含まれた辺の重みを大きい値に変更する。図４中では、ｅ１４＝∞に変更することで、経路が重複して選択されることを防止できる。ただし、プログラム処理上は辺の重みを十分大きい値に変更すれば、ｅ１４＝∞にしたのと同様に、その経路は実質的に重複して選択されなくなる。
【００４７】
次に、分割処理・閉路設計部２０３は、追加した中継ノードｖ４からの経路長が最小となる中継ノードと、ｖ４から当該中継ノードへ至る最短経路を、再び前記手法を用いて求める。
【００４８】
図５中では、ｖ４からの経路が最短経路となる中継ノードはｖ０、ｖ６であるが、ここでは中継ノードｖ０に着目する。ｖ４からｖ０に至る最短経路は２通りあるが、Ｐ１４は敷設不可能な経路となっている。そのため、最短経路はＰ４０＝｛ｅ３４，ｅ０３｝である。
【００４９】
再び、最短経路Ｐ４０に含まれている辺の重みを変更するか、または削除する。同様の手順を繰り返し、図５にあるようにＰ０６＝｛ｅ０１，ｅ１３，ｅ３６｝、を求め、次に、Ｐ６ １１＝｛ｅ６９，ｅ９１０，ｅ１０１１｝を求める。
【００５０】
前記手順によりすべての中継ノードへの経路を設計した後、分割処理・閉路設計部２０３は、最後に到達した中継ノードｖ１１から収容局までの最短経路を求める。求められた最短経路は図６に示すように、Ｐ１１ １＝｛ｅ１１ ８，ｅ８５，ｅ５２，ｅ２１｝となる。分割処理・閉路設計部２０３は、Ｐ１１ １を上記の手順までに作成された経路に追加することにより、閉路Ｃ＝｛Ｐ１４，Ｐ４０，Ｐ０６，Ｐ６ １１，Ｐ１１ １｝を構築し、閉路構築処理を終了する。
【００５１】
［閉路修正処理］
上述した閉路構築手法は、閉路Ｃが同じ辺を複数回通過することはないが、同じ頂点を複数回通過することがある。この場合、閉路が中継ノードを通過する順番を入れ替えることで頂点の重複をなくし、閉路長を短縮できる可能性がある。そこで、次に、分割処理・閉路設計部２０３は、閉路修正処理を行い、頂点の重複回数を減少させる。閉路修正処理の代表的な手法として、閉路の交叉を解消する２−ｏｐｔ法がある。
【００５２】
２−ｏｐｔ法により、分割処理・閉路設計部２０３は、閉路中のある２辺ｅｉｊ，ｅｋｌを選択する。そして、ｅｉｊ，ｅｋｌをｅｉｋ，ｅｊｌに置き換えた場合に総閉路長が短縮される場合、辺の置き換えを行う。
【００５３】
しかし、この手法は任意の２点間が直線的に接続可能であるということを前提としている。敷設可能経路制約のある実際の環境下においては、実際にｅｉｋ，ｅｊｌが敷設可能であるという保証がないため、この手法を適用することはできないという課題があった。そこで、本実施形態では、２−ｏｐｔ法に経路重複を避ける処理を追加する。以下、図７および図８に即して閉路修正処理の具体的な処理内容を説明する。
【００５４】
Ｓ１０１で、分割処理・閉路設計部２０３は、探索済みの経路の組み合わせを保存するリストを作成する。
【００５５】
Ｓ１０２で、分割処理・閉路設計部２０３は、閉路中の、中継ノードを結ぶ２経路Ｐｉｊ，Ｐｋｌを選択する。
【００５６】
Ｓ１０３で、分割処理・閉路設計部２０３は、この組み合わせ（Ｐｉｊ，Ｐｋｌ）をリストに追加する。たとえば、図８中において、Ｐ４０，Ｐ１１ １を選択するものとする。ここで、分割処理・閉路設計部２０３は、ｖ０，ｖ１に隣接する経路に含まれる辺の重みを再度計算し、グラフＧ＝（Ｖ，Ｅ）に計算した重みの値を反映する。この手順により、ｅ４５，ｅ５８，ｅ８ １１が再び敷設可能経路となる。分割処理・閉路設計部２０３は、最短経路計算法を用いてＰ４ １１＝｛ｅ４５，ｅ５８，ｅ８ １１｝を計算し、Ｐ４ １１に用いられた辺の重みを、敷設不可能を表す値に変更する。さらに、分割処理・閉路設計部２０３は、Ｐ０１を同様に求める。
【００５７】
Ｓ１０４で、分割処理・閉路設計部２０３は、経路の置換前後のコスト比較を行う。置換後のコストが置換前のコストよりも低下していれば、より効率のよい経路が見つかったことになる。そこで、この場合は、Ｓ１０６に進む。
【００５８】
Ｓ１０６で、分割処理・閉路設計部２０３は、経路（Ｐｉｊ，Ｐｋｌ）をＰｉｋ，Ｐｊｌに置換する。Ｓ１０７で、分割処理・閉路設計部２０３は、リストを削除する。その後、Ｓ１０１に戻る。
【００５９】
たとえば、図８では、｜Ｐ０１｜＝１であるため、Ｐ４０，Ｐ１１ １をＰ４ １１，Ｐ０１に置換する。この場合、閉路からＰ４６，Ｐ１１ ０を削除し、Ｐ４ １１，Ｐ６０を閉路に追加し、ｖ０とｖ１１の間に頂点が存在すれば、それらの頂点を通過する順番を逆にする（Ｓ１０６）。経路の置き換えを行った場合、それにより他の頂点間の最短経路も変化する可能性がある。したがって、探索済み経路組み合わせリストの項目を削除する（Ｓ１０７）。Ｓ１０４で条件を満たさない場合は、Ｓ１０５に進む。
【００６０】
Ｓ１０５で、分割処理・閉路設計部２０３は、すべての経路の組み合わせが探索済み経路組み合わせリストに登録されたかどうかを判定する。すべての経路の組み合わせが探索済み経路組み合わせリストに登録された場合、分割処理・閉路設計部２０３は、閉路修正処理を終了する。一方で、すべての経路の組み合わせが探索済み経路組み合わせリストに登録されていなければ、分割処理・閉路設計部２０３は、経路の置換を行わずに、再び新たな２経路を選択するために、Ｓ１０２に戻る。
【００６１】
分割処理・閉路設計部２０３は、修正後の閉路をパラメータ記憶部２０１に記憶し、閉路修正処理を終了する。
【００６２】
［閉路分割処理］
閉路分割処理は、すべての中継ノードを通過するリング網を複数のリング網に分割する処理である。閉路分割処理では、分割処理・閉路設計部２０３が、最小分割数を決定し、分割数に応じて分割点を決定し、分割点と収容局を結ぶ経路を決定する。分割点は、分割点から定まる目的関数の極小値を求めることで決定される。以下、図９および図１０に即して閉路分割処理の具体的な処理内容を説明する。
【００６３】
Ｓ２０１で、分割処理・閉路設計部２０３は、最小分割数Ｎｒを決定する。最小分割数Ｎｒは、たとえば、次式により算出可能である。
Ｎｒ＝ｍａｘ（［Ｎｎ／Ｎｒ，ｍａｘ］，［Ｌ／（Ｌｍａｘ−δ）］）
ここで、Ｎｎは、修正後の閉路Ｃに含まれている中継ノードの総数である。Ｎｒ，ｍａｘは、単一リング網に収容可能な中継ノード数である。Ｌは、閉路長である。Ｌｍａｘは、単一リング網の最大長である。δは各中継ノードと収容局との距離から定まるパラメータであり、分割によって追加される経路長の目安を表す。たとえば、δを収容局から各中継ノードへの最短経路長の平均値とすると、図１０ではδ＝２である。また、Ｎｎ＝４、Ｎｒ，ｍａｘ＝２、Ｌｍａｘ＝８、Ｌ＝１０とする。このとき、Ｎｒ＝ｍａｘ（２，１０／６）＝２である。
【００６４】
Ｓ２０２で、分割処理・閉路設計部２０３は、分割数Ｎｒに応じて分割点ｕ＝｛ｕ１，ｕ２，...ｕＮｒ，ｍａｘ−１｝を決定する。各分割点は、閉路中の任意の頂点を選択することができる。分割点の初期値はランダムに決定するか、あるいは、中継ノード数と閉路長の制約条件を満たすものの中からランダムに決定する。図１０において、初期値としてｕ１＝ｖ９を選択したものとする。
【００６５】
Ｓ２０３で、分割処理・閉路設計部２０３は、初期値として選択したｕに対して目的関数ｆ（ｕ）を求める。目的関数は評価値ｃ（ｕ）とペナルティ関数φ（ｕ）とにより構成される。まず、分割処理・閉路設計部２０３は、評価値ｃ（ｕ）を求める。たとえば、収容局ｖ０から各分割点までの最短経路長の総和を評価値とすると、図８ではｃ（ｕ）＝｜Ｐ１９｜＝３である。ただし、冗長性を確保するため、分割処理・閉路設計部２０３は、閉路Ｃに用いた辺を除外して、この最短経路を決定する。
【００６６】
また、分割により得られた各リング網が中継ノード数や閉路長の制約を満たさない場合は、それに応じたペナルティ関数φ（ｕ）を加えることで、制約条件を反映させる。たとえば、ペナルティ関数φ（ｕ）を、超過した閉路長と超過したノード数の和と定義する。図８では、ｖ４とｖ１１を含む閉路について、Ｌ＝｜Ｐ１４｜＋｜Ｐ４ １１｜＋｜Ｐ１１ ９｜＋｜Ｐ９１｜＝９であるから、Ｌ−Ｌｍａｘ＝１をペナルティ関数φ（ｕ）に加算する。中継ノード数は、Ｎｒ，ｍａｘ以下となっているため、この制約を満たしている。他方のリングは閉路長、中継ノード数ともに制約を満たしているので、φ（ｕ）＝１となる。したがって、ｆ（ｕ）＝ｃ（ｕ）＋φ（ｕ）＝４がｕ＝｛ｖ９｝の目的関数となる。
【００６７】
Ｓ２０４で、分割処理・閉路設計部２０３は、この分割点ｕをより目的関数ｆ（ｕ）が小さくなる方向へ変化させる。分割処理・閉路設計部２０３は分割点ｕから一つの頂点ｖｉを選択する。選択した頂点ｖｉを隣接する頂点ｖｊに変更した分割点ｕｉｊの目的関数ｆ（ｕｉｊ）を計算する。隣接する頂点ｖｊは各ｖｉに対して２つずつ存在するため、各ｖｉに対して２回ずつ目的関数の計算を行う。図８では、分割点ｖ９を隣接した頂点ｖ６、ｖ１０に変更した場合の目的関数の変化量を計算する。ｖ６に変更した場合、評価値ｃ（ｕ９６）は３であるため、ｖ９の評価値から変化しない。ただし、ｖ４とｖ１１を含む閉路長が長くなるため、ペナルティ関数がφ（ｕ９６）＝Ｌ−Ｌｍａｘ＝２となる。したがって、目的関数ｆ（ｕ）の変化量Δｆ（ｕ９６）は＋１である。一方、分割点をｖ９からｖ１０に変更した場合、やはり評価値ｃ（ｕ９ １０）＝３となり、ｖ９の評価値から変化しない。しかし、ペナルティの制約を満たすため、φ（ｕ９ １０）が０となる。よって、目的関数ｆ（ｕ）の変化量はΔｆ（ｕ９ １０）＝−１である。分割処理・閉路設計部２０３は、目的関数ｆ（ｕ）の変化量Δｆをすべてのｕｉｊに対して求め、目的関数ｆ（ｕ）を最も減少させるｕｉｊを採用する。図８では、ｕ９ １０を採用し、分割点ｖ９をｖ１０に変更する。
【００６８】
上記の手順を繰り返し、分割点を変更しても目的関数の値が減少しなくなった場合、そのときの分割ｕが局所最適解であると判断し、分割処理・閉路設計部２０３は、目的関数と変化量Δｆの計算を終了する。
【００６９】
図８では、閉路に用いた辺を用いずにｖ１１に到達する経路が存在しないため、分割処理・閉路設計部２０３は、Δｆ（ｕ１０ １１）＝∞と判断する。また、上記の手順から明らかなように、Δｆ（ｕ１０ ９）＝＋１である。したがって、目的関数の値を減少させることはできないため、分割処理・閉路設計部２０３は、ｕ＝｛ｖ１０｝を局所最適解と判断し、計算を終了する。
【００７０】
＜複数の異なる初期分割点を用いた分割点の決定＞
上記の手順による分割点ｕの局所最適解は、初期値に大きく依存する。たとえば、図８において、ｕ＝｛ｖ３｝が初期値であった場合、ｖ３をｖ０またはｖ６のいずれに変更した場合も目的関数を減少させることができず、ｕ＝｛ｖ３｝が制約を満たしていないにもかかわらず局所最適解として決定されてしまう。このような解が得られることを避けるため、分割処理・閉路設計部２０３は、２つ以上の異なる初期値（初期分割点ｕ）をランダムに選択し、上記のＳ２０１ないしＳ２０４を実行して、各初期値についての最適な分割点を決定し、決定された２つ以上の分割点のうちで目的関数の値が最小となる分割点を最終的な分割点として選択してもよい。
【００７１】
＜分割数の変更を伴う分割点の決定＞
また、加入者の分布によっては、分割数Ｎｒでは制約条件が満たせないことがある。そこで、分割処理・閉路設計部２０３は、初期値を変えた複数回の計算によって得られた最適分割点における目的関数値を事前に設定したしきい値Ｔｈと比較してもよい。算出された目的関数値がしきい値Ｔｈを上回る場合、分割処理・閉路設計部２０３は、分割数を増やして、目的関数の再計算（Ｓ２０１〜Ｓ２０４）を実行する。また、分割処理・閉路設計部２０３は、目的関数値がしきい値Ｔｈ以下になったときの最適分割点を、最終的な分割点として決定する。上記の手順を繰り返すことで、制約条件を満たす分割点ｕを求めることができる。なお、しきい値Ｔｈは経験的に決定するものとする。
【００７２】
＜収容局から分割点までの経路設計＞
Ｓ２０５で、分割処理・閉路設計部２０３は、分割点と収容局ｖ１を結ぶ経路を設計する。この経路は上述した最短経路の設計法により求める。その後、分割処理・閉路設計部２０３は、設計結果をパラメータ記憶部２０１に記憶し、リングの分割処理を終了する。
【００７３】
上記の手順により、制約条件を満たす複数のリング網が得られる。このリング網を辺集合Ｅの部分集合Ｅ'、または頂点集合Ｖの部分集合Ｖ'と辺集合Ｅの部分集合Ｅ'からなるグラフＧ＝（Ｖ，Ｅ）の部分グラフＧ'＝（Ｖ'，Ｅ'）の形式でパラメータ記憶部２０１に記憶する。
【００７４】
本実施例によれば、ネットワーク設計支援システムは、中継ノードの敷設位置と、複数の頂点の敷設可能位置情報とに基づいて、同一の頂点を２度以上通過しないように、複数のクラスタのそれぞれの中継ノードを結ぶ閉路を決定する。そのため、通信ケーブルの敷設工事コストを低減することができる。また、設計されたネットワークは閉路であるため、冗長性を有する。
【００７５】
また、ネットワーク設計支援システムのＣＰＵ２００は、閉路の全長が所定長Ｌｍａｘを超えているか、または、閉路に含まれる中継ノードの数が所定数Ｎｍａｘ，ｒを超えているときに、閉路を複数の閉路に分割する分割手段として機能する。とりわけ、ＣＰＵ２００の分割処理・閉路設計部２０３は、分割後の複数の閉路のそれぞれの全長が所定長を超えず、かつ、当該分割後の複数の閉路のそれぞれに含まれる中継ノードの数が所定数を超えないように、閉路を複数の閉路に分割する分割点を決定する。これにより、設備の制約を満足した複数のリングネットワークを設計できる。
【００７６】
また、分割処理・閉路設計部２０３は、図１Ｄに示したように、閉路を収容する収容局から分割点までの経路を決定する際に、収容局から分割点までの経路を、分割後の複数の閉路にとって重複した経路として決定してもよい。ただし、分割後の複数の閉路のそれぞれについては経路の重複を認めない。これにより、分割後の複数の閉路のそれぞれに冗長性を持たせることができ、回線障害に対するプロテクションを提供できるようになる。
【００７７】
図７を用いて説明したように、分割処理・閉路設計部２０３は、閉路が通過する複数の頂点のうち重複して通過する頂点（中継ノードが配置される頂点）を特定し、重複して通過する頂点について閉路が通過する順番を他の頂点と入れ替えることで、閉路の全長を短縮することができる。
【００７８】
＜実施例２＞
実施例２では、実施例１に経路網再構成部を追加する。これにより、敷設可能経路制約のある網を敷設可能経路制約が少ない、頂点数の少ない網に置換する。また、実施例２では、置換後の網に対してすべての頂点を通過する閉路を設計するため、一般的な巡回セールスマン問題の解法を適用できる。以下、図１１を用いて実施例２による具体的な処理の内容を説明する。なお、実施例１と共通する事項については説明を省略する。たとえば、加入者位置情報データベース２０４、敷設可能経路網情報データベース２０５および収容局設備情報データベース２０６に関しては実施例１で説明したとおりであるため、これらの説明を省略する。
【００７９】
［加入者‐中継ノード間網設計部］
実施例２でも実施例１と同じ手法で網設計を行う。ただし、実施例２では、中継ノードの位置決定を省略する。
【００８０】
［経路網再構成部］
加入者‐中継ノード間網設計部２０２は、一つの中継ノードと複数の加入者とを接続する経路を部分グラフＧｓ，ｉ＝（Ｖｓ，ｉ，Ｅｓ，ｉ）（ｉ＝１，２，...，Ｎｎ）の形で出力する。Ｖｓ，ｉは、頂点の位置を示す情報（頂点位置情報）である。Ｅｓ，ｉは、頂点間に通信ケーブルを敷設工事する際にかかるコストを示す情報（敷設コスト情報）である。経路網再構成部２０９は、この部分グラフＧｓ，ｉを一つの頂点とみなし、各部分グラフ間の距離（敷設コスト）を求めることで経路網を単純化し、閉路設計を容易にする。以下、図１２、図１３および図１４に即して経路網再構成部の具体的な処理内容を説明する。
【００８１】
Ｓ３０１で、経路網再構成部２０９は、２つの加入者‐中継ノード間網Ｇｓ，ｉ，Ｇｓ，ｊをパラメータ記憶部２０１から取得し、Ｅｓ，ｉまたはＥｓ，ｊに含まれる辺の重み（敷設コスト）を０に変更する。
【００８２】
Ｓ３０２で、経路網再構成部２０９は、Ｇｓ，ｉからＧｓ，ｊに至る最短経路を求める。たとえば、経路網再構成部２０９は、Ｇｓ，ｉの一つの頂点を始点として選択し、その点からＶｓ，ｊに含まれるいずれかの頂点までの最短距離を求める。
【００８３】
図１３において、ｉ行ｊ列目の頂点をｖｉｊと呼ぶことにする。ここでは、部分グラフＧｓ，１から部分グラフＧｓ，２への距離を、ｖ３４を始点として求めると仮定する。経路網再構成部２０９は、最短経路を順番に探索していく。その結果、経路網再構成部２０９は、Ｇｓ，２に属する頂点のうちｖ３６への経路は２つの辺を経由する経路が最短ルートであると決定し、その重みを２として求める。図１４が示すように、この経路を、Ｇｓ，１とＧｓ，２の間の経路ｐ（Ｇｓ，１，Ｇｓ，２）として保持する。
【００８４】
次に、経路網再構成部２０９は、Ｇｓ，１とＧｓ，３の間の最短経路を求める。ただし、リング網の冗長性を確保するため、ｐ（Ｇｓ，１，Ｇｓ，２）に用いた経路については重みを無限大とする。Ｅｓ，１に属する辺は重みが０であるため、ｐ（Ｇｓ，１，Ｇｓ，３）＝｛ｖ３４，ｖ２４，ｖ２３，ｖ２２，ｖ２１，ｖ３１，ｖ４１，ｖ５１｝であるが、その重み｜ｐ（Ｇｓ，１，Ｇｓ，３）｜は２である。引き続き、同様にすべての部分グラフ間においてその最短経路を求める。
【００８５】
さらに、経路網再構成部２０９は、部分グラフＧｓ，１とＧｓ，４との間の最短経路を求める。図１４に示すｐ（Ｇｓ，１，Ｇｓ，４）が最短経路であり、その重み｜ｐ（Ｇｓ，１，Ｇｓ，４）｜は４である。
【００８６】
経路網再構成部２０９は、すべてのＧｓ，ｉとＧｓ，ｊの組み合わせに対して最短経路を求めることによって、任意の２点間に辺が存在する、頂点数Ｎｎのグラフに経路網を再構成することができる。図１５は、再構成によって頂点数が削減された経路網を示している。このように頂点数を削減できれば、閉路を計算しやすくなる。
【００８７】
なお、図１３において、収容局ｖ１１はＧｓ，１に含まれているが、収容局が部分グラフに含まれない場合は、収容局ｖ１１をひとつの部分グラフとみなすことで同様の処理が可能である。図１３のグラフは図１４のように再構成される。経路網再構成部２０９は、再構成した経路網をパラメータ記憶部２０１に記憶し、処理を終了する。
【００８８】
このように、経路網再構成部２０９は、１つのクラスタを構成する１つの中継ノードと複数の加入者について、当該中継ノードに対して複数の加入者のそれぞれを接続する経路を部分グラフとし、複数の部分グラフを新たな複数の頂点とし、当該新たな複数の頂点を結ぶ経路の敷設コストを求める経路網再構成手段として機能する。
【００８９】
［分割処理・閉路設計部］
経路網再構成部２０９によって再構成された経路網から閉路を計算する問題は、三角不等式の成立しない巡回セールスマン問題に帰着する。この問題には、近似精度が保証された多項式時間解法が存在しないといわれている。しかし、頂点数を大幅に減らすことができたので、分割処理・閉路設計部２０３は、分枝限定法などの厳密解法を用いて経路長の短い閉路を設計することができる。
【００９０】
Ｓ３０３で、分割処理・閉路設計部２０３は、パラメータ記憶部２０１からｐ（Ｇｓ，１，Ｇｓ，２、ｐ（Ｇｓ，２，Ｇｓ，４）、ｐ（Ｇｓ，４，Ｇｓ，３）、ｐ（Ｇｓ，３，Ｇｓ，１）を読み出し、敷設コスト（辺の重み）の合計が最小となるように閉路を設計する。図１５に示した事例では、Ｇｓ，１→Ｇｓ，２→Ｇｓ，４→Ｇｓ，３→Ｇｓ，１と巡回することで最短の閉路が得られる。これにより、通信ケーブルの敷設可能経路網制約を満たした閉路を設計することができる。
【００９１】
このように本実施例によれば、経路網再構成部２０９は、１つのクラスタを構成する１つの中継ノードと複数の加入者について、当該中継ノードに対して複数の加入者のそれぞれを接続する経路を部分グラフとし、複数の部分グラフを新たな複数の頂点とし、当該新たな複数の頂点を結ぶ経路の敷設コストを求める。さらに、分割処理・閉路設計部２０３は、敷設コストの合計が最小となるように、当該新たな複数の頂点間を通る閉路を決定する。このように、頂点数を減らすことで解くべき問題の規模を縮小できるため、効率良く、閉路を設計できるようになる。
【００９２】
上述した実施例では、光通信ネットワークにおけるリング状のアクセス網を設計することを前提として説明した。しかし、通信ケーブルは光ファイバではなく、銅線などの通信ケーブルであってもよいし、無線回線であってもよい。また、加入者装置に代えて、無線基地局などが採用されてもよい。
【００９３】
＜実施例３＞
第３の実施例では、まず中継ノードの位置を決定する。次に、決定されたすべての中継ノードを通過する１つの閉路を構築する。閉路を構築する手順には、各中継ノードと収容局の通過順序を決定する手順と、通過順序を実際の敷設可能経路情報に当てはめ、ケーブル敷設経路を決定する手順とが含まれる。最後に中継ノードと加入者を接続する網を設計する。
【００９４】
以下、図１６に即して実施例３の具体的な処理手順を述べる。なお、実施例１、２と共通する部分には同一の参照符号を付与することで説明の簡明化を図ることにする。たとえば、加入者位置情報データベース２０４、敷設可能経路情報データベース２０５および収容局設備情報データベース２０６などは、実施例１ないし２において基本的に共通している。
【００９５】
実施例３における中継ノード位置決定部３０２は、加入者位置情報を加入者位置情報データベース２０４から取得し、加入者位置情報に基づいて中継ノードの位置を決定する。中継ノード位置決定部３０２は、実施例１の加入者クラスタリング・加入者‐中継ノード間網設計部２０２が実行した処理と同様の加入者クラスタリング処理を行い、そこから中継ノードの位置のみを抽出することで中継ノードの位置を決定する。中継ノード位置決定部３０２は、決定した中継ノードの位置をパラメータ記憶部２０１に記憶する。
【００９６】
分割処理・閉路設計部３０３は、パラメータ記憶部２０１から中継ノードの位置を取得し、取得した中継ノードの位置に基づいてすべての中継ノードを通過する１つの閉路Ｔを設計する。この閉路設計法としては、たとえば、最近隣接法、最近挿入法、またはＣｈｒｉｓｔｏｆｉｄｅｓのアルゴリズムなどの既知の近似解法や、総当たりにより最も距離が短くなる閉路を求める厳密解法が利用できる。
【００９７】
続いて、分割処理・閉路設計部３０３は、閉路Ｔに含まれる中継ノード数Ｎｎをカウントする。分割処理・閉路設計部３０３は、閉路Ｔが、１閉路に収容可能な中継ノード数Ｎｒ，ｍａｘを超えるＮｎ個の中継ノードを収容しているかどうかを判定する。ＮｎがＮｒ，ｍａｘを超えていなければ閉路Ｔの分割は不要である。一方で、ＮｎがＮｒ，ｍａｘを超えていれば閉路Ｔの分割が必要となるため、分割処理・閉路設計部３０３は、閉路Ｔを２つ以上の閉路に分割する。分割処理・閉路設計部３０３は、閉路Ｔの中から１つの中継ノードを選び、それをｔ０とする。中継ノードｔ０の選択方法は、ランダムに選択してもよいし、収容局１００に最も近いものを選択してもよいし、収容局１００から閉路Ｔを左回りに回って中継ノードに到達したときの距離と右回りに回って中継ノードに到達したときの距離とがほぼ一致するような位置にある中継ノードを選択してもよい。収容局１００から中継ノードｔ０に向かい、中継ノードｔ０から閉路Ｔに沿って他の中継ノードを回る。そして、ｔ１、ｔ２、…ｔ（Ｎｒ，ｍａｘ−１）といったＮｒ，ｍａｘ個の他の中継ノードを周ったのちに収容局１００に戻る。ただし、このときの軌跡を一つの分割閉路とする。続いて、次の中継ノードｔ（Ｎｒ，ｍａｘ）から再びＮｒ，ｍａｘ個の中継ノードを回り、一つの分割閉路を構成する。この手順を繰り返し、ｔ（Ｎｎ）までのすべての中継ノードを分割閉路に含めたのち、収容局１００に戻り、閉路構築を完了する。分割処理・閉路設計部３０３は、このときの閉路長を｜Ｒ（ｔ０）｜としてパラメータ記憶部２０１に記憶する。
【００９８】
分割処理・閉路設計部３０３は、収容局１００から最初に訪問する中継ノードｔ０（分割点の候補）を閉路Ｔ内の他の中継ノードに代え、同じ手順を実行する。このように、分割処理・閉路設計部３０３は、すべての中継ノードをｔ０として複数の分割閉路（分割閉路群）を決定する。中継ノードがＮｎ個の場合は、Ｎｎ個の分割閉路群が決定される。分割処理・閉路設計部３０３は、各分割閉路群について、その分割閉路群に含まれる複数の分割閉路それぞれの一周の距離を求め、求めた距離の和をその分割閉路群の総距離（全長）として求める。そして、分割処理・閉路設計部３０３は、Ｎｎ個の分割閉路群について総距離を比較し、総距離が最も短くなる分割閉路群を決定し、それをパラメータ記憶部２０１に記憶し、閉路分割処理を終了する。パラメータ記憶部２０１には、総距離が最も短くなる分割閉路群を特定する情報としては、たとえば、通過順序Ｒ＝｛ｃ，ｔ０，ｔ１，…ｔ（Ｎｎ−１），ｃ｝が記憶される。ｃは、収容局１００を示し、ｔｉ（ｉ＝０〜Ｎｎ−１）は、中継ノードを示す。なお、全長が最も短くなる分割閉路群を決定することで、閉路Ｔの分割点となる中継ノードｔ０も決定される。
【００９９】
上述した手順により、収容局１００（ここではｃで表す）と中継ノードを回る順番（通過順序）が決定されたことになる。この順番をＲ＝｛ｃ，ｔ０，ｔ１，…ｔ（Ｎｎ），ｃ｝とする。
【０１００】
最短経路導出部３０４は、Ｒをパラメータ記憶部２０１から取得し、グラフＧ上における分割閉路、つまり実際のケーブル敷設経路Ｒ’（Ｇ）を計算する。この処理は以下のように行われる。
【０１０１】
まず、最短経路導出部３０４は、Ｒから順番に２つの頂点を取り出す。上の例では、ｃ、ｔ０が該当する。次に、最短経路導出部３０４は、Ｄｉｊｋｓｔｒａ法などを用いてこの２点間の最短経路を求め、この最短経路をＲ’（Ｇ）に追加する。続いて、最短経路導出部３０４は、閉路内の経路重複を避けるため、この最短経路に用いられた辺のコストを∞に設定する。続いて、最短経路導出部３０４は、次の中継ノードｔ１を取り出し、同様にｔ０とｔ１の間の最短経路をＲ’（Ｇ）に追加し、辺のコストを∞に設定する。辺のコストを∞に設定することで、その辺は考慮の対象外となる。最短経路導出部３０４は、この処理を繰り返すことで、順次、実際のケーブル敷設経路Ｒ’（Ｇ）を決定する。なお、ケーブル敷設経路Ｒ’（Ｇ）を最短とすることで、通信ケーブルの敷設コストが最も小さくなる。
【０１０２】
上述した処理の中で、異なる閉路が同じ辺を通過することは、回線障害耐性の観点からは問題とならない。これは、２つの閉路に共通している辺（ケーブル敷設経路）に回線障害が発生しても、その辺を迂回した経路を形成できるからである。なお、１つの閉路において１つの辺を２回通る場合、その辺に回線障害が発生すると、閉路全体に回線障害が波及してしまう。このように、異なる閉路が同じ辺を通過することは、回線障害耐性の観点からは問題とならない。したがって、最短経路導出部３０４は、Ｎｒ，ｍａｘ個の中継ノードを通過する一つの閉路をＲ’（Ｇ）に追加した後、Ｒ’（Ｇ）に含まれている辺のコストを∞から初期値に戻す。辺のコストが初期値に戻されたため、その辺は他の分割閉路の辺としても選択可能となる。
【０１０３】
最短経路導出部３０４は、Ｒに含まれるすべての閉路について実際のケーブル敷設経路Ｒ’（Ｇ）を確定したら、パラメータ記憶部２０１にＲ’（Ｇ）を記憶し、最短経路導出処理を終了する。
【０１０４】
加入者‐中継ノード間網設計部３０５は、分割閉路のケーブル敷設経路Ｒ’（Ｇ）をパラメータ記憶部２０１から取得し、これに基づいて中継ノードと加入者間のケーブル敷設経路Ｄを決定する。このとき、加入者‐中継ノード間網設計部３０５は、敷設コストを低減するため、ケーブル敷設工事長を短縮するアルゴリズムに基づいて設計を行う。この処理手順は以下の通りである。
【０１０５】
まず、加入者‐中継ノード間網設計部３０５は、敷設可能経路網情報データベース２０５の敷設コスト情報Ｅに含まれる辺のうち、Ｒ’（Ｇ）に含まれるもののコストをｒ倍する。ここで、加入者‐中継ノード間網設計部３０５は、ｒは単位長さあたりのケーブル敷設コストに対するケーブル材料コストの割合を表す係数である。続いて、加入者‐中継ノード間網設計部３０５は、すべての加入者位置情報を未確定加入者位置情報ＵＳに追加する。加入者‐中継ノード間網設計部３０５は、未確定加入者位置情報ＵＳの各要素に対してＤｉｊｋｓｔｒａ法を適用し、加入者から最も低コストで到達できる中継ノードまでの経路をそれぞれ計算する。ただし、中継ノードと加入者の間のケーブル長に上限が設けられている場合、加入者‐中継ノード間網設計部３０５は、その上限を満たすものの中から最も低コストのものを計算する。このように、Ｒ’（Ｇ）に含まれる辺のコストを小さい値に変更したため、加入者‐中継ノード間網設計部３０５は、辺を選択する際にすでにＲ’（Ｇ）で使用されている辺を優先的に選択する。これにより、敷設工事コストを下げることができる。
【０１０６】
加入者‐中継ノード間網設計部３０５は、すべての加入者における最小コストの経路のうち、最もコストの小さい経路を一つ選択し、これに含まれる辺のコストが初期値から変更されていなければ、それをｒ倍した上でその辺をケーブル敷設経路Ｄに追加する。これにより、今後最短経路を求める加入者はいま選択された経路に含まれる辺も優先的に使用するようになり、敷設工事コストの低減に貢献する。その後、加入者‐中継ノード間網設計部３０５は、当該加入者をＵＳから削除し、未確定加入者位置情報ＵＳに含まれている別の加入者について同様の処理を繰り返し、一つずつ加入者と中継ノード間の経路を確定する。
【０１０７】
加入者‐中継ノード間網設計部３０５は、未確定加入者位置情報ＵＳが空になった時点ですべての加入者が中継ノードと接続されたと判定し、設計処理を終了する。各加入者は最も低コストで到達できる中継ノードを選択したため、接続される加入者が０である中継ノード、または上限値を超える中継ノードが存在することがある。０である中継ノードを消去し、上限値を超えるものについては同一地点に必要な中継ノード数をＲ’（Ｇ）に記録して、Ｒ’（Ｇ）とケーブル敷設経路Ｄをパラメータ記憶部２０１に記憶して処理を終了する。
【０１０８】
このように実施例３によれば、中継ノード位置決定部３０２が中継ノードの位置を決定し、分割処理・閉路設計部３０３は、決定されたすべての中継ノードを通過する１つの閉路を構築する。ここで、分割処理・閉路設計部３０３は、各中継ノードと収容局の通過順序を決定する。さらに、最短経路導出部３０４は、分割処理・閉路設計部３０３が決定した通過順序を実際の敷設可能経路情報に当てはめ、ケーブル敷設経路を決定する。最後に、加入者‐中継ノード間網設計部３０５が、中継ノードと加入者を接続する網を設計する。とりわけ、実施例３によれば、中継ノードの敷設位置と、複数の頂点の敷設可能位置情報とに基づいて、分割閉路の総距離が最も短くなるように、複数の分割閉路を決定する。さらに、１つの分割閉路が同一の辺を２度以上通過せず（ただし、異なる分割閉路であれば同一の辺を２度以上通過してもよい）、かつ、分割閉路のケーブル敷設経路Ｒ’（Ｇ）が最短となるように、分割閉路のケーブル敷設経路Ｒ’（Ｇ）を決定する。その結果、実施例３によれば、通信ケーブルの敷設工事コストを低減しつつ、ネットワークの冗長性を確保できるようになる。
【図１Ａ】
2014123849.tif 000003
【図１Ｂ】
2014123849.tif 000004
【図１Ｃ】
2014123849.tif 000005
【図１Ｄ】
2014123849.tif 000006
【図１Ｅ】
2014123849.tif 000007
【図２】
2014123849.tif 000008
【図３】
2014123849.tif 000009
【図４】
2014123849.tif 000010
【図５】
2014123849.tif 000011
【図６】
2014123849.tif 000012
【図７】
2014123849.tif 000013
【図８】
2014123849.tif 000014
【図９】
2014123849.tif 000015
【図１０】
2014123849.tif 000016
【図１１】
2014123849.tif 000017
【図１２】
2014123849.tif 000018
【図１３】
2014123849.tif 000019
【図１４】
2014123849.tif 000020
【図１５】
2014123849.tif 000021
【図１６】
2014123849.tif 000022