(57)【特許請求の範囲】
【請求項１】
主分配ノードに供給されるテリトリに在住する全てのユーザを接続するネットワーク、特に、電気通信ネットワーク、給水ネットワーク、地域暖房または電力ネットワークを生成する方法であって、
Ａ）以下のプロセス段階、すなわち、
Ｉ）エッジ（１４）およびノード（１５）からなる幹線ネットワークを表すグラフ（Ｇ）を生成する段階からなり、該グラフ（Ｇ）のエッジはネットワーク内の全ての伝送経路を表しており、該エッジの長さと方向が、街路のセグメントの実際のトポグラフィと該ネットワークにより供給を受けるテリトリの指定可能なケーブル経路とから得られ、そして該ノードが、該街路間、ケーブル経路間又は該街路と該ケーブル経路との間の交差点を表わすものであり、さらに、
II）該グラフ（Ｇ）に該ユーザ（３）を割り当てる段階からなり、各ユーザ（３）が、サービスエッジ（１４）により、該グラフ（Ｇ）の最も近いエッジ（１４）または最も近いノード（１５）に接続されており、さらに、
III）該グラフ（Ｇ）から不必要なエッジ（１４）を除去することにより木構造（Ｂａ）を生成する段階からなり、前記生成する段階は、該木構造（Ｂａ）の該サービスエッジ（１６）とエッジ（１４）とノード（１５）からなる１つの接続部のみが、該主分配ノード（７）と各ユーザ（３）の間に存在するような方法で行われるものであり、さらに、
IV）該各ユーザ（３）に対して指定されたニーズおよび要件に依存して、該木構造（Ｂａ）の該エッジ（１４）の負荷を決定する段階、
を使用してネットワーク計画を生成する段階と、
Ｂ）概略的に生成した該計画により該ネットワークを生成する段階からなることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、後続の第５のプロセス段階Ｖを用いて、プロセス段階Ｉ−IVで計算した該エッジ（１４）の負荷（２１）に基づいて、エリアの境界を定め、そして該木構造（Ｂａ）の各エッジ（１４）とサービスエッジ（１６）とノード（１５）に対して使用する（特に、敷設するケーブルまたはラインに関する）技術を画定し選択することを特徴とする方法。
【請求項３】
請求項２に記載の方法において、プロセス段階IIを用いて、最も近い該エッジ（１４）と該サービスエッジ（１６）との間の接合において、グラフ（Ｇ）における該最も近いエッジ（１４）を２つのエッジ（１４ａ）に分割し、該接合は新しいノード（１５ａ）を形成することを特徴とする方法。
【請求項４】
請求項１乃至３のいずれか１項に記載の方法において、該プロセス段階IIIにおいて、
ａ）該グラフ（Ｇ）に沿った該主分配ノード（７）への伝送経路が他のユーザと比して最も供給コストが安いユーザ（３）を決定し、位置するユーザ（３）と伝送経路を形成する該エッジ（１４）と該ノード（１５）とにマークを付ける段階と、
ｂ）次に、該主分配ノードへの伝送経路が最も経済的である未だマークされていない多くのユーザ（３）からユーザ（３）を選択し、以前にマークされた伝送経路の以前にマークされた該エッジ（１４）と該ノード（１５）とを考慮して、このユーザ（３）とこの伝送経路を形成する該エッジ（１４）とノード（１５）とにマークを付ける段階と、、
ｃ）全てのユーザ（３）にマークが付くまで、段階ｂ）を反復して行う段階と、そして、
ｄ）該グラフ（Ｇ）でまだマークが付いていない全てのエッジ（１４）およびノード（１５）を該グラフ（Ｇ）から除去する段階と、
により該木構造（Ｂａ）を生成することを特徴とする方法。
【請求項５】
請求項１乃至４のいずれか１項に記載の方法において、該ネットワークにより供給を受ける該テリトリ（１）の街路セグメントと指定可能なケーブル経路（５）との実際のトポグラフィのデータが第１のデータ・ベースに記憶され、該ユーザ（３）のデータが第２のデータ・ベースに記憶され、該第２のデータ・ベースは、特に、各ユーザ（３）に対するネットワークによりカバーされるアドレスと接合部座標と要件（４）とを記憶することを特徴とする方法。
【請求項６】
請求項５に記載の方法において、該木構造（Ｂａ）の前にある該グラフ（Ｇ）が、両方のデータ・ベースから生成されることを特徴とする方法。
【請求項７】
請求項１乃至６のいずれか１項に記載のネットワーク、特に電気通信ネットワークを生成および最適化する方法において、該テリトリの各街路が、グラフ（Ｇ）が生成されている間に、２つのエッジ、特に平行なエッジ（１４）によってプロセス段階Ｉにおいて描写され、各エッジ（１４）が街路の一方の側を表わすことを特徴とする方法。
【請求項８】
請求項７に記載の方法において、該ユーザ（３）を、銅線、銅線対（ＣｕＤＡ）またはガラス・ファイバのような異なる型式の伝送線により該主分配ノード（７）に接続することができ、該接続が、その伝送容量と最大範囲により他のものと区別され、該ケーブルがこの目的に対して提供されるべき異なる数の導線対又はガラス・ファイバを有しており、一人のユーザ（３）が必要とする電話機の数および／またはデータ伝送線の数が、一人のユーザ（３）を通過するケーブル（ＶｚＫ）から出て、他のユーザ（３）に到達するような方法で、複数のユーザ（３）にケーブル（ＶｚＫ）が供給されることを特徴とする方法。
【請求項９】
請求項７または８に記載の方法において、エリアの境界決定と各エッジ（１４）に対して使用される（特に、敷設されるケーブルまたはラインに関する）技術の画定と選択が、
ａ）該ケーブル分配装置（ＫＶｚ）の容量および／またはケーブル分配エリア用に使用される該伝送装置の範囲を指定する段階からなり、前記容量が、特に、該ケーブル分配装置用に使用される装置からのものであり、さらに、
ｂ）他の１つのエッジ（１４）だけに接続しているノード（１５）にそのサービスエッジ（１６）が接続しているユーザ（２２）に行く段階と、
ｃ）該段階ｂ）において選択したユーザ（３）からスタートして、該段階ａ）で指定したケーブル分配装置またはケーブル分配エリアの容量および／または範囲をその負荷（２１）が超えているエッジ（２５）に接続しているノード（１５）に境界を接するエッジ（以下制限エッジ（Ｇｋ）と称する）に到達するまで、該交換機（７）の方向に、該木構造（Ｂａ）のサービスエッジ
（１６）、エッジ（１４）およびノード（１５）を辿る段階と、
ｄ）該制限エッジ（Ｇｋ）により該交換機（７）に接続している全てのユーザ（３）にマークを付け、それらユーザをケーブル分配サブエリア（２３）に割り当てる段階と、
ｅ）全てのユーザ（３）がケーブル分配サブエリア（２３）に割り当てられるまで、段階（ｂ）からｄ）までを反復して行う段階と、
に分割されることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、プロセス段階ｅ）の後で、各ケーブル分配エリア（２６）の負荷（３０）が段階ａ）で指定された該ケーブル分配装置の容量を超えないように、全てのケーブル分配サブエリア（２３）をケーブル分配エリア（２６）に結合するために再帰的な方法が用いられるプロセス段階が行われ、各ユーザ（３）が１つのケーブル分配エリア（２６）に割り当てられることを特徴とする方法。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の方法において、より小さなまたは等しい負荷を持ち、そのためにより大きなケーブル分配サブエリア２３を形成する、隣接するケーブル分配サブエリア２４と結合することができない該ケーブル分配サブエリア２３が、プロセス段階Ｖ（ｆ）において該木構造（Ｂａ）から選択されることを特徴とする方法。
【請求項１２】
請求項９または請求項１０に記載の方法において、相互に直接隣接するこれらケーブル分配サブエリア（２３）だけが、ケーブル分配エリア
（２６）に結合されることを特徴とする方法。
【請求項１３】
請求項１０乃至１２のいずれか１項に記載の方法において、プロセス段階ｅ）の後で、下記のプロセス、すなわち、
ｆ）より小さいかまたは等しい負荷を有し、制限エッジ（Ｇｋ）が同じノード（２８）上で境界を接する直接隣接するケーブル分配エリア（２３）の負荷と結合した負荷が、該ケーブル分配装置のプロセス段階ａ）で指定された容量より大きい全てのケーブル分配サブエリア（２３）に対する該木構造
（Ｂａ）をまず検索する段階と、
ｇ）木構造（Ｂａ）に位置する、この型式の任意のケーブル分配サブエリア（２３）を、最も小さいケーブル分配サブエリア（２３）を除いて、ケーブル分配エリア（２６）に結合し、ケーブル分配エリア（２６）に対してプロセス段階ｈ）およびｉ）を実行する段階と、
ｈ）該木構造（Ｂａ）からプロセス段階ｇ）において形成された該ケーブル分配エリア（２６）を除去し、該制限エッジ（Ｇｋ）により該交換機（７）に接続している全てのユーザ（３）、サービスエッジ（１６）、エッジ（１４）、およびノード（１５）が、該木構造（Ｂａ）から分離するように、または残りのケーブル分配エリア（２６）を生成している間、無視されるように、残りのケーブル分配エリア（２６）を生成中に、それらケーブル分配エリア
（２６）を無視する段階と、それらを該交換機（７）に接続している全てのエッジ（１４）の割り当て負荷（２１）から、分離されたケーブル分配エリア（２７）の負荷（３０）を差し引く段階と、
ｉ）その後、追加のケーブル分配サブエリア（２３）の任意の他の制限エッジ（Ｇｋ）が、該分離されたケーブル分配エリア（２７）で該交換機（７）と境界を接しているかどうかをチェックする段階と、追加の制限エッジ（Ｇｋ）が存在しない場合には、該接続ノード（２８）、および他の制限エッジ（Ｇｋ）が境界を接している次のノード（２９）に接続している該エッジ（１４）およびノード（１５）を除去する段階と、
が行われる方法。
【請求項１４】
請求項１３に記載の方法において、追加のケーブル分配エリア（２６）が、下記プロセス段階、すなわち、
ｊ）１つのエッジ（１４）だけに、また少なくとも１つの制限エッジ（Ｇｋ）に接続しているノード（２８）を探す段階であって、該エッジ（１４）の負荷（２１）が、該木構造（Ｂａ）に未だ存在するか、または含まれる全ての他のエッジ（１４）より大きいものであり、さらに、
ｋ）位置が発見されたノード（２８）に隣接する全てのケーブル分配サブエリア（２３）の負荷の合計が該ケーブル分配装置の容量より小さいかまたは等しいときには、これら全てのケーブル分配サブエリア（２３）を、該結合ケーブル分配サブエリア（２３）の個々の負荷の合計に等しい負荷を有する新しいケーブル分配サブエリア（２３）に結合し、その後、段階ｌ）を続行する段階と、
位置が発見されたノード（２８）に隣接する全てのケーブル分配サブエリア（２３）の負荷の合計が該ケーブル分配装置の容量より大きいときには、個々の負荷の合計は最も大きいが該ケーブル分配装置よりは小さい容量を有する隣接するケーブル分配サブエリア（２３）を結合して、新しいケーブル分配エリア（２６）を形成する段階と、
該木構造（Ｂａ）からこのケーブル分配サブエリア（２３）か該新しいケーブル分配エリア（２６）を除去し、ケーブル分配エリア（２６）を生成中にこれを無視する段階と、その後、該除去したケーブル分配エリア（２７）の負荷（３１）を、このケーブル分配エリア（２６）を該交換機（７）に接続している全てのエッジ（１４）の割り当て負荷から差し引く段階と、任意のケーブル分配サブエリア（２３）が該木構造（Ｂａ）に依然として接続しているときには、段階ｆ）に進み、そうでない場合には段階ｐ）に進む段階と、
ｌ）該位置が発見されたノードを該交換機（７）に接続しているエッジ（１４）が、該新しいケーブル分配サブエリア（２３）の該制限エッジ（Ｇｋ）である段階と、
ｍ）この制限エッジ（Ｇｋ）が、他の制限エッジ（Ｇｋ）が境界を接していないノード（１５）に隣接しているときには、該制限エッジ（Ｇｋ）からスタートし、該交換機（７）の方向に移動しながら、他の制限エッジ（Ｇｋ）が境界を接している次のノード（２９）を探す段階と、
ｎ）この型式のノード（２９）が段階ｍ）で発見できないときには、該ケーブル分配サブエリア（２３）がケーブル分配エリア（２６）になる段階と、その場合には段階ｐ）に進む段階と、この型式のノード（２９）が発見された場合には、この方法を引続き適用するために段階ｏ）に進む段階と、
ｏ）該ケーブル分配サブエリア（２３）の該制限エッジ（Ｇｋ）を段階ｍ）で位置が発見された該ノード（２９）に接続する段階と、段階ｎ）が段階ｐ）に分岐するまで、段階ｆ）からｎ）までを反復して実行する段階と、
ｐ）これにより、該ケーブル分配エリア（２６）の生成プロセスを終了する段階と、
により、更なるケーブル分配エリア（２６）を生成することを特徴とする方法。
【請求項１５】
請求項１０乃至１４のいずれか１項に記載の方法において、該ケーブル分配エリアを生成する手順の後に、下記のプロセス段階、すなわち、
ｑ）該ケーブル分配エリアに割り当てられた、各ユーザの位置および要件に関する各ケーブル分配エリアの分配の中心を決定する段階であって、該ケーブル分配エリアにおける１つのノードが、該分配の中心を形成すると同時に、該ケーブル分配エリアと設定される該電気通信ネットワークとの間に接合部を形成するものであり、さらに
ｒ）該ケーブル分配エリアの負荷を各分配の中心に割り当てる段階と、
ｓ）新しい木構造を生成し、該交換機（７）へのノードとして指定された該分配の中心に接続する、プロセス段階IIにおいて形成された元の木構造の全てのノードおよびエッジにマークを付し、その後、該木構造から全てのまだマークが付けられていないユーザ、サービスエッジ、ノードおよびエッジを除去するか、または以降のプロセス段階を実行するときにそれらを無視する段階とを実行することを特徴とする方法。
【請求項１６】
請求項１３乃至１５のいずれか１項に記載の方法において、段階Ｖ（ａ）において設定された、該ケーブル分配装置の容量よりその要件（４）が大きい全てのユーザ（３）が、それぞれ、プロセス段階Ｖ（ｆ）を終了する前に、１つのケーブル分配エリア（２６）として指定されるものであり、これらユーザに、それぞれ、特定のユーザの要件をカバーするのに十分な技術が割り当てられ、この型式のユーザ（３）の制限エッジ（Ｇｋ）が境界を接しているノード（１５）に、段階Ｖ（ａ）で指定する容量の倍数である、プロセス段階Ｖ（ｓ）において生成される新しい木構造（Ｂａ）に対する要件が割り当てられ、それ故、このユーザの要件を丁度カバーし、続いて、ノードがユーザ（３）に割り当てられたケーブル分配装置の分配の中心または位置を形成する状態で、木構造（Ｂａ）からこのユーザ（３）を除去することを特徴とする方法。
【請求項１７】
請求項１乃至１６のいずれか１項に記載の、該木構造（Ｂａ）において該エッジ（１４）の負荷を決定する方法（プロセス段階IV）において、該木構造（Ｂａ）の全てのエッジ（１４）に、最初「０」（ゼロ）の負荷が割り当てられ、該交換機（７）の方向に該エッジ（１４）および該ノード（１５）に沿ってあるユーザ（３）から次のユーザに移動し、各ユーザの要件（４）が移動した各エッジ（１４）に追加されることを特徴とする方法。
【請求項１８】
請求項９乃至１７のいずれか１項に記載の、プロセス段階Ｖにおいて形成された該ケーブル分配エリア（２６）に対する該伝送装置およびケーブルを必要な大きさにするための方法において、下記プロセス段階、すなわち、
ｕ）「０」（ゼロ）の負荷を該木構造（Ｂａ）の全てのエッジ（１４）に割り当てる段階と、
ｖ）該エッジ（１４）およびノード（１５）に沿って、各ユーザ（３）から、該ユーザ（３）に属する該ケーブル分配エリア（２６）の該ケーブル分配装置に移動し、該ユーザの要件（４）を通過した各エッジ（１４）に追加する段階と、
ｗ）その容量が特定のエッジ（１４）の負荷を丁度カバーするケーブルを各エッジ（１４）に割り当てる段階と、
ｘ）該特定のノード（１５）の負荷を丁度カバーする一台の伝送装置を各ノード（１５）に割り当てる段階とを順次終了する方法。
【請求項１９】
請求項１８に記載の方法において、プロセス段階IV、およびＶ（ａ）から、Ｖ（ｓ）、および段階（ｕ）から（ｘ）が、段階Ｖ（ａ）において、該新しい木レベル上に生成される該新しいケーブル分配エリア（２６）に対して、異なる容量および範囲を指定するプロセス段階Ｖ（ｓ）に続いて、該新しい木構造（３３）に適用されることを特徴とする方法。
【請求項２０】
データ処理プログラムによる請求項１乃至１８のいずれか１項に記載の方法の適用。
【発明の詳細な説明】
本発明は、ネットワークに関し、特に電気通信ネットワーク、給水ネットワーク、地域暖房ネットワーク、または電力ネットワークを形成し最適化するための方法に関する。
供給ネットワーク、電気通信ネットワークおよび、例えば、コンピュータ・ネットワークは、ある大きさ以上に成長した場合、一個人が手作業で設定するのは非常に困難である。それ故、ネットワークを設定する場合、最も重要な考慮事項はその利便性である。ネットワークが設定された場合、それを最適化できるのはいくつかの地点に限定される。ほとんどの場合、後になってからでは重大なエラーを修正することはできない。
ネットワークの型式およびレイアウトにより、非常に種々様々な技術を使用することができる。ネットワークの立案者は、通常、特定のネットワークの問題を解決するために、自分が自由に使用することができる複数の構成部分を持つ。電気通信ネットワークの場合には、とりわけ、立案者は特定の接続のために銅のケーブルを使用するか、または光ファイバを使用するのかを決定しなければならない。立案者は、また、非常に種々様々な型式の銅のケーブル、および光ファイバのケーブルの中から選択を行わなければならない。これらすべてのケーブルは、その容量、すなわち、伝送速度、一本のケーブル内のラインの数、および可能な最大伝送範囲が異なる。
現在に至るまで、特定のテリトリをカバーできる電気通信ネットワークの種々の計画は、ほとんど常に、経験を積んだネットワーク立案者により手書きで行われてきた。すでに説明したとおり、そのような計画を立案する場合、ネットワークの利便性は最も重要な問題である。技術的に最適化され、コスト・パーフォーマンスの最もよいレイアウトを持つネットワークは、現在周知のネットワーク生成方法では設定することができない。
電気通信ネットワークの従来の設定方法について以下に説明するが、その説明は最も重要な原理だけに限定する。図１は、１つの交換機（ＨＶＫ）７から供給を受ける個々の市ブロック２を含むテリトリ１である。ブロック２は、その電話ライン要件４が表示されている個々のユーザ３を含む。説明を簡単にするために、この例のユーザ３は、電話線以外のいかなるサービスも必要としないことにする。ブロック２は、街路５および街路交差点６により、相互に分離されている。図２に示すように、ネットワーク立案者は、上記テリトリ１を、自分自身のキャリヤと豊かな経験により、過去に確立された立案規則に基づいて、エリアＡからＥに分割する。この場合、Ａ１およびＡ２のような複数の市ブロックは、通常は１つのエリアに結合される。下記の説明においては、これらエリアをケーブル分配エリアまたはＫＶｚ（Kabeiverwzweigung）エリアと呼ぶ。テリトリは、使用する技術、および個々の国で規定されているケーブルの型式に基づいて、ケーブル分配エリアに分割される。上記技術により、個々のケーブル分配エリアの最大の大きさおよび最適の大きさが決まる。この例の場合には、ネットワーク立案者は、銅のケーブルを選択したので、そのため、一本の銅のケーブルは、１０組、２０組、５０組、７５組、１００組、１５０組または２００組のような異なる銅線の組（ＣｕＤＡ）を含むことができる。銅のケーブルの通信範囲は、すべてのユーザにとって十分なものであり、１つのケーブル分配装置８の容量は、１００組の銅線を収容することができる。ネットワーク立案者は、その後、ケーブル分配装置８（ＫＶｚA−ＫＶｚE）の位置を確立し、上記ケーブル分配装置から、電話線を含むケーブル（ＶｚＫ）が、図３に示すように、可能な経路、すなわち、歩道およびその下の交差点１１に沿って、個々のユーザ３のところまで引かれる。束ねられて主要なケーブル（Ｈｋ）９になる特定のエリアの電話線は、そのエリアのケーブル分配装置８から、直接交換機７へ接続される。可能な場合には、ケーブル９は、ケーブルの敷設コストを安くするために、他のエリアの現存のケーブル経路に沿って敷設される。
図２に示すように、エリアＡは、少なくとも６８本の電話線の供給を受けなければならないし、エリアＢは、少なくとも７２本の電話線の供給を受けなければならないし、エリアＣは、少なくとも７８本の電話線の供給を受けなければならないし、エリアＤは、少なくとも５７本の電話線の供給を受けなければならないし、エリアＥは、少なくとも４９本の電話線の供給を受けなければならない。このことは、その利用度が、必要な銅線の組（ＣｕＤＡ）の数により、またケーブルの型式により異なる複数の分配ケーブル（Ｃｕ−ＶｚＫ）を個々のエリア内に敷設しなければならないことを意味する。例えば、市ブロックＡ１の１つの側に対しては２０のＣｕＤＡ銅分配ケーブルが必要になり、同じブロックの他方の側に対しては５０のＣｕＤＡ銅分配ケーブルが必要になる。この方法の場合、ケーブル分配エリアは分割されるので、このことは、銅分配ケーブルは異なる充填比を持つことを意味する。
この方法により形成されたケーブル分配エリアは、主要ケーブル（Ｈｋ）９を通して、交換機（ＨＶＫ）７に接続しなければならない。例えば、ケーブル分配エリアＥに供給を行うには、４９本の銅線の組を収容することができる正味の容量を持つ主要ケーブルが必要になる。このことは、使用をお奨めする、次に本数の多い５０の銅線の組を含む主要ケーブルは、９８％の割合で使用されることを意味する。ネットワーク立案者は、交換機７に対する、エリアＥの主要ケーブルを敷設するのに２つの選択肢を持つことになる。ネットワーク立案者は、エリアＥの主要ケーブルを、他のエリアの主要ケーブルと一緒に、より大きな容量を持つ主要ケーブル、または光ファイバのような異なる技術の主要ケーブルに接続するために、交換機により近い場所に位置するエリアＡまたはＤ内のケーブル分配装置までの経路に沿って主要ケーブルを敷設することができる。ネットワーク立案者は、エリアＥの主要ケーブルをエリアＤまたはＡのケーブル分配装置へ敷設することができる。第１のケースの場合、交換機７からエリアＤのケーブル分配装置への主要ケーブルは、最低でも１０６本の銅線の組を持たなければならないし、（エリアＥにおいては４９本のＣｕＤＡ、およびエリアＤにおいては５７本のＣｕＤＡを持たなければならない。）第２のケースの場合には、交換機７からエリアＡのケーブル分配装置への主要ケーブルは、最低でも１１７の銅線の組を持たなければならないし、（エリアＥにおいては４９本のＣｕＤＡ、およびエリアＤにおいては６８本のＣｕＤＡを持たなければならない。）しかし、１１７本または１０９本の銅線の組を収容することができる容量を持つ銅のケーブルは市販されていないので、次に容量の大きい、すなわち、１５０の銅線の組を収容することができる銅のケーブルを選択しなければならない。１５０本のＣｕＤＡ銅ケーブルを使用した場合、主要ケーブルの容量の利用度は、第１のケースの場合７０．６７％であり、第２のケースの場合７８％である。最適なネットワーク・バージョンを選択するために、両方の選択肢のコストを計算しなければならない。すべてのケーブル分配エリアに対してこの手順が反復して行われる。
エリアを区画し主要ケーブルを敷設する場合、最適なネットワーク設計を行うために、すべての可能な組合せを考慮の対象にしなければならないことは明らかである。ネットワーク立案の初期の段階で、ケーブル分配エリアに対して好ましくないエッジ（「枝」又は「辺」）を選択すると、後でエラーが発生しても、後からそれを修正することができない。
また、大きなネットワークを手書きで完成するには、数週間掛かかるが、ネットワークは非常に短時間の間に設定しなければならないので、エリアを決定する際に他の解決方法を使用することは通常不可能である。それ故、効率的なネットワーク利用度および最低のコストという立場から見た場合、ネットワークは最適化されていないことになる。
その結果、上記の方法を使用した場合、ネットワーク立案者が、最もコスト・パーフォーマンスが高く、利益を上げることができるネットワークのバージョンを立案することができる可能性は低い。
それ故、本発明の目的は、最短時間で、容量利用度が高く、手数が最も掛からない、非常に利便性が高く、コストも安いネットワークを生成するための方法を提供することである。
本発明によれば、上記目的は、第１のプロセス・ステップにおいて、技術的に実行可能なおよび／または指定可能なネットワーク伝送経路を含み、上記エッジの長さおよび方向が、街路のセグメントの実際のトポグラフィ、およびネットワークにより供給を受けるテリトリの指定可能なケーブル経路により決まり、上記ノードが、エッジまたは街路および／またはケーブル経路の間に交点を形成する場合に、エッジとノードからなるグラフを生成することにより；また、第２のプロセス・ステップにおいて、各ユーザが追加のサービスエッジにより、上記グラフの最も近いエッジ、または最も近いノードに接続されるような方法で、上記テリトリ内のユーザを上記グラフに割り当てることにより；また、第３のプロセス・ステップにおいて、木構造のエッジおよびノードによる、主分配ノードと各ユーザとの間の接続が１つだけになるように、グラフから不必要なエッジを除去することにより、最もコスト・パーフォーマンスの高い木構造を生成することにより；また、第四のプロセス・ステップにおいて、ユーザのニーズおよび要件により、上記木構造のエッジが負担する負荷を決定することにより；また、その後の第５のプロセス・ステップにおいて、プロセス・ステップＩからIVで計算したエッジの負荷に基づいて、上記木構造の各エッジ、サービスエッジ、およびノードに対して使用する技術を決定し、選択することにより達成される。
本発明の方法は、材料のコストおよびケーブル敷設コストが安いために、特に経済的に生成することができる、長さが特に短く、特にネットワーク容量の利用度が高く、キャリヤのコストを低く維持するネットワークを有利に生成するために、有利に使用することができる。この方法は、特に、電気通信ネットワーク、給水ネットワーク、地域暖房ネットワークおよび電力ネットワークに対して使用することができる。この方法をデータ処理システム上で実行することができるコンピュータ・プログラムに変換することにより、生成したネットワークを手作業により、後で容易に最適化することができる。何故なら、この方法を、例えば、電気通信装置、特に上記伝送経路に沿ったケーブルに対して転送を行うネットワークを生成するために使用することにより、上記グラフに対していくつかの伝送経路を永久的に指定することができるからである。
種々のレベルに対して使用する種々の技術により、異なるネットワーク・レベルに何回もこの方法を適用して、完全なネットワーク計画を非常に迅速に作成することができる。コンピュータを使用する場合には、この方法の使用を終了した直後に、例えば、電気通信ネットワークに対する敷設ケーブル型式およびその長さおよび組合せを、各ノードに対して必要な相互接続と一緒に、直ちにデータ・ベースから入手することができる。これにより、コストおよび材料のリストを非常に迅速に作成することができる。ネットワーク構造および維持の地図も、生成したネットワーク計画データから作成することができる。
給水ネットワークの場合には、直径および勾配、必要なポンプおよびその位置等と一緒に、必要なパイプの型式を直ちに決定することができる。
本発明の１つの利点は、コンピュータ・プログラムを使用して、すべてのプロセス・ステップを容易に、迅速に、都合よく終了することができ、それにより比較的短時間で、テリトリに対する、任意の数のネットワーク計画を生成することができる。指定の街路および経路のレイアウトのパラメータ、および特定のネットワーク・レベルに対して使用する材料コスト、敷設ケーブル・コストおよび技術を若干修正することにより、最適なネットワーク計画を作成することができる。しかし、これらのパラメータは、また、バッチ・プログラム、または、例えば、一般アルゴリズムまたは進化戦術を使用して、ネットワーク計画を作成する際の各ステップに対して、指定または選択することができる。コンピュータを使用することにより、それ以後手作業を何も行わなくても、ネットワーク計画を最適化することができる。
電気通信ネットワークを生成するための実施形態を示す図面を参照しながら、本発明の方法の個々のプロセス・ステップを以下に詳細に説明する。
図１は、街路に沿って配置されている個々のユーザ３を含むテリトリ１である。
図２は、従来の方法により、ネットワーク立案者が、手書きでエリアＡ−Ｅに分割したテリトリ１である。
図３は、従来の方法により、ネットワーク立案者が、手書きで作成したテリトリ１に対するネットワーク計画である。
図４−図８は、本発明の方法を示す。
図４は、各街路の各側に沿って、グラフＧに対するエッジ１４が供給されている、本発明の方法により、テリトリ１内に挿入されたグラフＧである。
図４ａは、本発明の方法により、サービスエッジ１６を通して、グラフＧにユーザ３を接続している、図４のテリトリ１の一部である。
図４ｂは、ユーザ３をすでに生成済みの木構造の一部に、徐々に接続することにより、作成中の木構造Ｂａを含むテリトリ１の一部である。
図４ｃは、本発明の方法により、テリトリ１に対して生成された木構造、およびエッジ１４に割り当てられた負荷２１である。
図５は、以下に説明するプロセス・ステップ（Ｖａ）から（Ｖｅ）中に生成したケーブル分配サブエリアを含むテリトリ１である。
図５ａは、ケーブル分配エリア２６を形成するために結合中の２つのケーブル分配サブエリアを含むテリトリ１の一部である。
図５ｂは、２つの制限エッジＧｋにより、木構造から分離されているケーブル分配エリア２６を含む図５ａの一部である。
図５ｃは、（不法の）要件を含む最も近いノード２９に接続しているケーブル分配サブエリアの制限エッジを含む上記図５ａの一部である。
図６は、生成されたケーブル分配エリア２６、およびその分配の中心に配列されているケーブル分配装置ＫＶｚ2からＫＶｚ4を含むテリトリ１である。
図７は、以下に説明するプロセス・ステップ（Ｖｑ）から（Ｖｓ）中に生成された新しい木構造３３を示す。
図８は、個々のエッジ１４または街路・セグメントに割り当て中の銅線の組３５を含むケーブル分配エリア２６である。
その上にユーザ３、および街路、および指定のケーブル経路５、およびその交差点６がランダムに配列されている市ブロック２からなる図１のテリトリ１の場合、テリトリ１を交換機７に接続する電気通信ネットワークが、図４−図８に示すように本発明の方法により形成される。図面を簡単にするために、電話線のような同じ型式のサービスを必要とするこれらユーザ３だけを表示する。
本発明の方法は、しかし、必要な回数だけ、技術により決定した特定のレベルに適用することができるので、交換機７を分配ノード８のように処理することができる。
図４は、プロセス・ステップＩ中に作成された街路図である。この図の場合、街路だけが存在し、指定ケーブル経路は存在しないものと仮定する。グラフＧのエッジ１４は、街路の各側に割り当てられる。そうすることにより、街路の交差点６のところに四つのノード１５が形成されるが、四つの街路交差点１１からなる１つのグループが個々のエッジ１４を形成する。
図４ａのプロセス・ステップIIにおいて、ユーザ３はサービスエッジ１６により、グラフＧに接続される。そうするために、特定のユーザ３の接合からグラフＧへの最も短い経路を選択しなければならないか、またはサービスエッジ１６を、特定の予め定めたパラメータに従って、特定の経路に沿って敷設しなければならないが、それにより、サービスエッジ１６の長さが定まる。サービスエッジ１６がグラフＧのエッジ１４と合流する場合には、このエッジ１４は新しいノード１５ａになる。それ故、エッジ１４ａはエッジ１４に対応する。
プロセスIIの終わりで、すべてのユーザ３はグラフＧに接続される。図４ｂおよび図４ｃに示すように、木構造Ｂａはプロセス・ステップIIIで生成される。この場合、各ユーザ３は、サービス・ブランチ１６、エッジ１４およびノード１５からなる個々の接続部を通して交換機７に接続される。この目的のために、交換機７に対する最も接続コストが安いユーザ１７を発見するために、街路図の検索が行われる。上記接続コストは、例えば、使用したケーブル技術および掘削コストを含むケーブル敷設コストにより決まる。ユーザ１７、エッジ１４および後で交換機７に接続するノード１５は、その後、マークが付けられ、マーク付き伝送経路１８を形成する（プロセス・ステップ１ａ）。次に、（プロセス・ステップ１ｂにおいて）、前にマークが付けられたエッジ１４、および／またはノード１５を考慮に入れて、前のマーク付き伝送経路１８へのその接続コストが、まだマークされていないすべてのユーザ３の接続コストより安いユーザ１９が、何時でも最初に交換機７に接続されるように、すべてのユーザ３が、次々と交換機７に接続される。位置が発見された伝送経路は、そのユーザと一緒にマークされる。プロセス・ステップ１ａおよび１ｂは、簡単な検索アルゴリズムからだけからなるので、コンピュータ・プログラムの形で容易に適用することができる。
すべてのユーザ３にマークが付けられると、すなわち、生成された木構造Ｂａに接続されると、グラフＧのすべてのマークされていないエッジ１４およびノード１５は除去される。エッジ１４およびノード１５を除去する代わりに、残りのプロセス・ステップに対して、マーク付きのエッジ１４およびノード１５だけを使用することができる。プログラミングの立場から見た場合、後者の方法の方が明らかに好ましい。
生成された木構造Ｂａは、指定された可能な経路およびケーブル・レイアウト５に対する接続コスト（材料およびケーブル敷設コスト）が最小になるように設計される。
コンピュータ・プログラムを設計するとき、プロセス・ステップIVにおいて、木構造Ｂａの残りのエッジ１４に負荷２１を割り当てる方が都合がよい場合がある。以下に１つの可能なアルゴリズムについて説明する。しかし、本発明の方法を実行する場合には、異なるアルゴリズムを使用しても、エッジ１４の負荷２１をプロセス・ステップＶで決定してもまったく同じことである。
上記の可能なアルゴリズムは、木構造Ｂａのすべてのエッジ１４に、最初「０」（ゼロ）の負荷を割り当て、エッジ１４およびノード１５に沿って、各ユーザ３から交換機７へ連続的に移動して、上記手順が移動した各エッジ１４に、上記手順が最後にスタートしたユーザ３の要件４を追加する。
上記プロセス・ステップにより、経路グラフの最適化した木構造の作成が行われたので、木構造Ｂａに接続されたユーザ３が、ケーブル分配エリア２６に結合される方法について以下に説明する（図５および図６）。この場合、できるだけ効率的な装置を使用することによりできるだけ少ないケーブル分配エリア２６を生成することによってグラフを最適化するために、上記方法が継続して使用される。
ケーブル分配エリア２６を生成するために、個々のケーブル分配エリアに供給を行う個々のケーブル分配装置の容量が最初に指定される（プロセス・ステップＶａ）。この容量は、使用するケーブル分配装置の技術により異なる。上記容量により、ケーブル分配エリアが使用することができる銅線の組、ガラス・ファイバ等の数が決定される。ケーブル分配エリア２６で使用される伝送装置の最大範囲も指定しなければならない。それにより、プロセス・ステップＶｂ中に、ケーブル分配サブエリア２３の大きさが制限される。
自分の要件４に従って、個々のユーザ３は、１つのケーブル分配サブエリア２３、または個々のケーブル分配エリア２６を形成することができる。その場合、上記要件は、プロセス・ステップＶａで指定した容量より大きくてもかまわない。その要件４が、ステップＶａで指定されたケーブル分配装置の容量より大きい上記ユーザ３を１つのケーブル分配エリア２６として指定するほうが得策である。この場合、この型式のユーザ３の制限エッジＧｋに隣接するノード１５には、ユーザ３の要件を丁度カバーするプロセス・ステップＶで生成される新しい木構造３３に対してステップＶａで指定された容量の倍数に対応する要件が割り当てられるように、これら各ユーザ３には、ユーザの要件をカバーするのに十分な伝送装置が割り当てられ、木構造Ｂａからこのユーザ３が除去され、その場合、上記ノードは、ユーザ３に割り当てられたケーブル分配装置の分配の中心または位置を形成する。
マークがすでに設定されている場合には、その後、すべてのマークがユーザ３から除去される。
その後、木構造Ｂａのブランチの端部に位置する、まだマークが付いていないユーザ２２を求めて、木構造Ｂａが検索される。このユーザ２２は、自分のサービスエッジ１６と一緒に、その上において１つのエッジ１４だけが境界を接しているノードに隣接するという事実により識別される。このユーザ２２からスタートして、ネットワーク立案者は、制限エッジＧｋに到着するまで、交換機７の方向へサービスエッジ１６、エッジ１４およびノード１５に沿って移動する。制限エッジＧｋは、その負荷２１が、プロセス・ステップＶａ）中に指定された負荷より大きい、エッジ２５上において境界を接しているノード１５に、自らが接続しているという事実により識別される。しかし、エッジ１４は、制限エッジＧｋがその容量により、ケーブル分配サブエリア２３に属しているように見える場合でも、（同様に、プロセス・ステップＶａで指定される）、このケーブル分配エリア２６に対して使用される伝送装置の、ユーザ２２から始まる範囲を超えた場合、直ちに、ケーブル分配サブエリア２３の制限エッジＧｋになることができる。
図５は、上記方法で生成されるすべてのケーブル分配サブエリア２３を示す。ケーブル分配サブエリア２３へのこの分割は、一意のもので、再現することができることに留意されたい。
以降のプロセス・ステップＶｆからＶｐにより、ケーブル分配サブエリア２３は、できれば、徐々にケーブル分配エリア２６に結合または変換され、結合されたケーブル分配エリア２６の負荷３０は、ケーブル分配装置８の最大容量を確実に超えないようにする。これらプロセス・ステップの終わりに、各ユーザ３は、はっきりとケーブル分配エリア２６に割り当てられる。
ケーブル分配エリア２６を生成する時にも、同様に、隣接するケーブル分配サブエリア２３を結合することができることに留意されたい。何故なら、そうでない場合、上記エリアは結合力を持っていないからである。これにより、それ以降、キャリヤは保守およびエラー分析を行うことがほとんど不可能になる。何故なら、故障の場合、発生するエラーの原因についての結論を出すことができないからである。エリアが同じノード１５上で隣接していて、時計方向および反時計方向に相互に直接重なっている場合には、エリアは隣接している。
以下に、図５および図６を参照しながら、プロセス・ステップＶｆ）からＶｐ）についてさらに詳細に説明する。この場合、図５および図６は、プロセス・ステップＶｆ）にその基礎を置く最初の状況を示し、図６は、プロセス・ステップＶｐ）終了後の終了結果を示す。
プロセス・ステップＶｆ）においては、より大きいケーブル分配サブエリア２３を形成するために、より小さいか、等しい負荷を持つ任意の隣接するケーブル分配サブエリア２４と結合することができない木構造Ｂａのこれらケーブル分配サブエリア２３が、最初に選択される。何故なら、両方の隣接するケーブル分配サブエリアの全負荷が、ケーブル分配装置の容量を超えるからである。ケーブル分配サブエリア２３は、ケーブル分配エリア２６に変換され、プロセス・ステップＶｈ）およびプロセス・ステップＶｉ）中に、木構造から除去される。この場合、この新しいケーブル分配エリア２６の要件が、後者を交換機７に接続しているすべてのエッジ１４から差し引かれ、他のケーブル分配エリア２６を生成する際には、上記要件は無視される。プロセス・ステップＶｈ）およびＶｉの詳細な説明については請求の範囲を参照されたい。
ケーブル分配サブエリア２３を、より大きなケーブル分配サブエリア２３に、結合する方法について以下に説明する。図５に示すように、３つのケーブル分配サブエリア２４が、同じノード２８に隣接している。上記３つのケーブル分配サブエリア２４の中のどれも、前のプロセス・ステップの影響を受けていない。何故なら、これらの要件は、ケーブル分配装置の容量またはそれら容量の合計を超えていないし、または隣接するケーブル分配サブエリアの容量が、ケーブル分配装置の容量を超えていないからである。それ故、１つのケーブル分配サブエリア２４の要件は、その制限エッジ（Ｇｋ）により直接定まる。例えば、ノード２８上で境界を接している３つのケーブル分配サブエリア２３は、要件９、７７および２０を持つ。隣接するケーブル分配サブエリア２３の合計は、８６または９７である。以降のプロセス・ステップにおいて、ケーブル分配サブエリア２４は、その合計が最も大きいケーブル分配エリア２６、すなわち、全要件が９７である２つのケーブル分配サブエリアに結合される。このケーブル分配サブエリア２６は、木構造から分離または除去され、および／または残りのプロセス・ステップに対して無視される（図５ｂ）。もっと多くのケーブル分配サブエリア２４をノード２８に接続する場合には、それらケーブル分配サブエリアも同様に結合することができる。しかし、ネットワークの結合力を確保することに留意しなければならない。この例の場合には、ノード２８には、１つのケーブル分配サブエリア２４が接続される。このケーブル分配サブエリアの、その向きがケーブル分配サブエリア２３から逸れているその端部が、他のケーブル分配サブエリア２３が接続している次のノード２９に合流するまで、制限エッジＧｋは、交換機７の方向に延びる。この次のノード２９からスタートして、前に除去されたケーブル分配エリア２６の負荷が、交換機の方向のエッジ１４から差し引かれる（図５ｃ）。ケーブル分配サブエリア２３は、木構造Ｂａに接続しているケーブル分配サブエリアが全部無くなるまで、引続き結合状態のままでいる。ケーブル分配サブエリア２３をケーブル分配エリア２６に結合する正確な方法については、請求の範囲（プロセス請求項Ｖｊ）からＶｐ））に記載する。図６に示すように、本発明の方法は、テリトリを四つのケーブル分配エリア２６に分割するために使用される。
ユーザ３に、生成したケーブル分配エリア２６が割り当てられた後で、ユーザ３に割り当てられたケーブル分配装置に接続している、個々の分配ケーブル（ＶｚＫ）の大きさを決定することができる。この目的のための、プロセス・ステップＶｕ）からＶｗ）が終了する。プロセス・ステップＶｕ）は、必要な大きさにするための第１のステップである。プロセス・ステップＶｕ）は、初期化ステップであり、負荷０（ゼロ）を木構造Ｂａのすべてのエッジ１４、３７に割り当てる。その後、各ユーザの要求４がステップＶ）において追加され、エッジ１４に沿ってユーザ３から移動し、ノード１５に沿ってユーザ３に属するケーブル分配エリア２６のケーブル分配装置へ移動する。これをする際には、可能であればケーブル分配装置をケーブル分配エリアの分配の中心に位置させなければならないが、その場合、追加のノードが、ネットワークに生成されるのを防止するために、上記分配の中心が次のノードにマップされる。上記分配の中心は、移動する中心の収益性により決定され、例えば、ユーザ３およびその要件４を分配することにより計算することができる。分配の中心またはケーブル分配装置の位置を決定するための種々のアルゴリズムは周知であり、それらのアルゴリズムも、本発明の方法で使用することができる。
ステップＶｗ）において、分配ケーブルＶｚＫに対応し、その容量がエッジ１４の負荷を丁度カバーする１つの銅線の組が、その後、各エッジ１４、３７に割り当てられる。これにより、個々のケーブル分配エリアに対するネットワーク計画（図６）が作成され、この計画を見れば、そのケーブルに接続しているユーザに正しい供給を行うために敷設するケーブル３４に対してどの技術を使用すべきか、またはどの銅線の組２５を使用すべきであるかがすぐに分かる。
これにより、個々のケーブル分配エリア２６の必要な大きさが分かる。
次に、ケーブル分配エリア２６のケーブル分配装置を交換機に接続しなければならない。しかし、テリトリ１が広い場合には、最初に生成したケーブル分配エリア２６のケーブル分配装置に供給を行い、分配エリアを新しいネットワーク・レベルに結合するために、追加の分配ノードを供給しなければならない場合もでてくる。両方の場合、個々のユーザ３の要件を表示しないで、木構造に接続しているケーブル分配装置により、選択的に表示される前のネットワーク・レベルのケーブル分配エリア２６の要件を表示して、プロセス・ステップＶを図７に示す木構造に適用することができる。ここでも、エッジの負荷３１を決定することができ、ケーブル分配サブエリアおよびケーブル分配エリアが、新しいネットワーク・レベル上に形成される。この方法は、このネットワーク・レベルに引続き適用することができる。
この方法を少し修正したものも、ユーザの異なる要件により一台の装置を使用して、次のより高い、またはより低いネットワーク・レベル上の、交換機に接続している装置により、あるネットワーク・レベル上に複数の装置を並べて設置しなければならないようなネットワークに適用することができる。ケーブル分配サブエリア２３およびケーブル分配エリア２６の境界を決定する際には、このことも考慮に入れられる。
当業者なら、本発明の上記方法を、地域暖房ネットワーク、または給水ネットワークのような他のネットワーク・システムに容易に適用することができる。このようなネットワークの場合には、パイプも、街路の交差点のところで結合または分岐する経路または街路に沿って敷設される。上記方法によれば、これら接合部はノード１５として定義され、パイプ経路はエッジ１４として定義される。交換機７の代わりに、個々の暖房ネットワークの主分配ノードが使用される。要件は方法で抽象番号を表わし、個々のユーザの個々の暖房要件も１つの番号で表わすことができるので、この方法の場合、例えば、この方法を地域暖房ネットワークに適用するために、この点を変更する必要はない。
＜参照番号のリスト＞
１    供給テリトリ
２    市ブロック
３    ユーザ
４    ユーザ要件
５    街路または指定ケーブル経路
６    街路またはケーブル交差点
７    主分配ノード（ＨＶＫ）または交換機（Ｖｓｔ）
８    分配ノード（ＫＶｚA−ＫＶｚE＝エリアＡ−Ｅに対するケーブル分配装置）
９    データ・ラインを含むケーブル
１０  ユーザへの送電線
１１  地下ケーブルと街路との交差点
１２  主分配ノードへのケーブル経路
１３  エリアＤ用のケーブルの一部と一緒に、ケーブル・ピットに敷設されたエリアＥ用のケーブル
１４  街路の一方の側を表わすエッジ
１５  ノード、エッジ（１４）に対する接合
１６  ユーザへのサービスエッジ
１７  交換機（ＨＶＫ、７）への接続コストが最も安いユーザ
１８  交換機（７）からユーザ（１７）へのマーク付き伝送経路
１９  マーク付き伝送経路１８への接続コストが最も安いユーザ
２０  本発明の方法により、すでにマーク付きのエッジ（１４）およびノード（１５）に、後で接続されるユーザ
２１  エッジ（１４）上の負荷
２２  プロセス・ステップＶｂ）のユーザ
２３  ケーブル分配サブエリア
２４  その制限エッジ（Ｇｋ）が、同じノードに接続している、ケーブル分配サブエリア（２３）
２５  プロセス・ステップＶｃ）中のエッジ
２６  プロセス・ステップＶｇ中のケーブル分配エリア
２７  除去ケーブル分配エリア、プロセス・ステップＶｈ）
２８  複数のケーブル分配サブエリア（２３）の、制限エッジ（Ｇｋ）と境界を接するノード
２９  最も近いノード；プロセス・ステップＶｉ）
３０  ケーブル分配エリア（２６）の要件
３１  エッジ（２３）の負荷
３２  プロセス・ステップＶｓ）中に生成された新しい木構造（３３）のエッジ
３３  プロセス・ステップＶｓ）中に生成された新しい木構造
３４  分配ケーブル（ＶｚＫ）
３５  分配ケーブル（３４）の組
３６  その内部で、両方のケーブル分配エリアの分配ケーブルが、平行に走っている２つのケーブル分配エリア２および４により共有されるノード
３７  エッジ
Ａ−Ｅ          供給テリトリ（１）内のエリア
Ｂａ            木構造
ＣｕＤＡ        銅線の組
Ｃｕ−ＶｚＫ    銅の分配ケーブル
Ｇｋ            ケーブル分配サブエリア（２３）の制限エッジ
Ｈｋ            主ケーブル
ＨＶＫ          交換機（７）
ＫＶｚ          ケーブル分配エリアの分配ケーブル用のターミナル
ＫＶｚエリア    ケーブル分配エリア
ＶｚＫ          分配ケーブル（３４）
【図１】
0004087458.tif 000002
【図２】
0004087458.tif 000003
【図３】
0004087458.tif 000004
【図４】
0004087458.tif 000005
【図４ａ】
0004087458.tif 000006
【図４ｂ】
0004087458.tif 000007
【図４ｃ】
0004087458.tif 000008
【図５】
0004087458.tif 000009
【図５ａ】
0004087458.tif 000010
【図５ｂ】
0004087458.tif 000011
【図５ｃ】
0004087458.tif 000012
【図６】
0004087458.tif 000013
【図７】
0004087458.tif 000014
【図８】
0004087458.tif 000015