費用効果及び信頼性の高いユーティリティ配給ネットワーク
【課題】 費用効果及び信頼性の高いユーティリティ配給ネットワークを提供する。
【解決手段】 費用効果及び信頼性の高いユーティリティの配給ネットワークを設計するための方法、システム、及びコンピュータ・プログラム製品が例示的な実施形態において提供される。複数のクラスタを形成するように、ユーティリティの消費者のセットをユーティリティの供給者のセットと接続するグラフが簡約化される。複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークが改良され、この改良することは、第１のネットワークにおける所定数の障害後に消費者のサブセットへのユーティリティの供給を継続するように、第１の接続を第１のネットワークに加えることである。供給者のセットを消費者のセットに接続する第２のネットワークについての設計が生成され、第２のネットワークは改良後の第１のネットワークを含んでおり、第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有する。
【解決手段】 費用効果及び信頼性の高いユーティリティの配給ネットワークを設計するための方法、システム、及びコンピュータ・プログラム製品が例示的な実施形態において提供される。複数のクラスタを形成するように、ユーティリティの消費者のセットをユーティリティの供給者のセットと接続するグラフが簡約化される。複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークが改良され、この改良することは、第１のネットワークにおける所定数の障害後に消費者のサブセットへのユーティリティの供給を継続するように、第１の接続を第１のネットワークに加えることである。供給者のセットを消費者のセットに接続する第２のネットワークについての設計が生成され、第２のネットワークは改良後の第１のネットワークを含んでおり、第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ユーティリティ配給ネットワークを生成又は修正するための方法、システム、及びコンピュータ・プログラム製品に関する。より具体的には、本発明は、ネットワークが費用効果が高く信頼できるものとなるようにユーティリティ配給ネットワークを生成又は修正するための方法、システム、及びコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
電気、水及びガスといったユーティリティは、種々の供給者から種々の消費者に供給される。ユーティリティの配給は、これらのユーティリティの好適な搬送装置のネットワークを通して行われる。例えば、電気は、電気ケーブル及びグリッドのネットワークを通して配給され、水及びガスは、パイプラインのネットワーク上で配給される。
【０００３】
新しいユーティリティ配給ネットワーク（ネットワーク）は、例えば、新しい都市又は区画が計画されるときに設計される。既存のネットワークは、例えば、新しい供給者が表れた場合、古い供給者が事業を止めた場合、又は、消費者若しくは需要のパターンが変化した場合のように、配給に変更が必要であるときに修正される。
【０００４】
ユーティリティ配給ネットワークは、高価なインフラストラクチャである。その構築には、大きな設備投資が必要である。ネットワークの維持管理には、多くの時間及び出費が必要である。既存のネットワークの修正は複雑であり、費用、時間、及びユーティリティ・サービスのダウン時間が関係する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ユーティリティ配給ネットワークは、信頼できるものでなければならない。例えば、ネットワークにおける障害がユーティリティの供給を中断しないものであることが望ましい。
【課題を解決するための手段】
【０００６】
例示的な実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワーク（ネットワーク）のための方法、システム、及びコンピュータ・プログラム製品を提供する。実施形態は、複数のクラスタを形成するように、ユーティリティの消費者のセットをユーティリティの供給者のセットと接続するグラフを簡約化する。本実施形態は、複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良し、この改良することは、第１のネットワークにおける所定数の障害後に、消費者のサブセットへのユーティリティの供給を継続するように、第１の接続を第１のネットワークに加えることである。本実施形態は、供給者のセットを消費者のセットに接続する第２のネットワークについての設計を生成し、第２のネットワークは改良後の第１のネットワークを含んでおり、第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有する。
【図面の簡単な説明】
【０００７】
【図１】例示的な実施形態を実装することができる電気配給ネットワークの例の図を示す。
【図２】例示的な実施形態を実装することができるデータ処理システムのブロック図を示す。
【図３】例示的な実施形態による費用効果の高いネットワークを設計するためのグラフ簡約化プロセスを示す。
【図４】例示的な実施形態による信頼性のための単純化されたループ・グラフを示す。
【図５】例示的な実施形態によるユーティリティ配給ネットワークにおいて信頼性を向上させる第２の形態を示す。
【図６】例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するプロセスのフローチャートを示す。
【図７】例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークをさらに最適化する例示的なプロセスのフローチャートを示す。
【発明を実施するための形態】
【０００８】
本発明の特徴であると考えられる新規な構成が、特許請求の範囲に記載される。しかしながら、本発明自体、並びに、本発明の好ましい使用形態、さらなる目的及び利点は、図面と併せて読んだときに、例示的な実施形態の以下の詳細な説明を参照することによって、最も良く理解される。
【０００９】
本発明によって、ユーティリティ配給ネットワークは、構築するのに費用効果が高く、動作が信頼できるものでなければならないことが分かる。例えば、ネットワークを構築するためのより単純化された１つの手法は、ユーティリティの各消費者（消費者）をユーティリティの供給者（供給者）に接続するものである。しかしながら、そのようなより単純化された手法は、サービスを消費者に第１の供給者から提供する場合と第２の供給者から提供する場合のネットワーク構築における比較費用を考慮していない。例えば、消費者のより近くにある第１の供給者から供給することは、第１の供給者から遠くにある第２の供給者から消費者に供給することと比較すると、第１の供給者の方が必要な導線又はケーブルの長さが短いため、より費用効果が高い。
【００１０】
そのようなより単純化された手法はまた、サービスの継続性についての信頼性が低い。例えば、第１の供給者がユーティリティを供給できないとき又は第１の供給者と消費者との間のネットワークが機能しなくなったときには、ユーティリティを消費者に提供することができない。
【００１１】
若干の信頼性を伴ってネットワークを構築するより単純化された別の手法は、２つ又はそれ以上の供給者から任意に消費者にサービスを提供することである。ここでも、そのような手法は、異なる供給者から消費者にサービスを提供するネットワークを構築する比較費用を考慮していない。
【００１２】
消費者と供給者の間のような２点間の最短距離を選択するための幾つかの最短経路アルゴリズムが知られている。本発明によって、単に消費者と供給者との間の距離が最短であるというだけの理由で消費者と供給者とを対にすることは、費用効果及び信頼性の点から十分な解決策ではないことが分かる。例えば、消費者に最も近い供給者は、風力エネルギーを電気に変換する供給者のような散在する供給者であることがある。
【００１３】
信頼性は、例えばネットワークにおける導線を二重にすることによって、実現することができる。しかしながら、こうした法は、導線長といったネットワーク資源を無駄にするものであるため、そのような信頼性は費用効果が低い。
【００１４】
本発明によって、ネットワークが、費用効果及び信頼性の観点から所与の消費者のセット及び所与の供給者のセットのために設計された場合であっても、そのような設計プロセスは、自動化プロセスの結果ではなく、従って容易に複製できるものではないことが分かる。特定の供給者及び消費者のための特定のネットワーク設計は、費用効果及び信頼性が高い場合があるが、通常、可能なネットワーク化の選択枝について試行錯誤による網羅的な調査が必要である。
【００１５】
本発明を説明するのに用いられる例示的な実施形態は、一般に、ユーティリティ配給ネットワーク設計に関する上述の問題に対処し、解決するものである。例示的な実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するための方法、システム及びコンピュータ・プログラム製品を提供する。
【００１６】
本発明及びその種々の実施形態は、本明細書においては、単に本開示を明確にするために、主として、限られた数の消費者とユーティリティの例すなわち電気の供給者との間の単純化された関係に関して、説明される。ユーティリティ配給ネットワークの設計に関して本明細書において説明される概念、方法、製品、システム、動作、作用、構成、又は操作は、限定することなく、他のタイプのユーティリティ配給ネットワーク並びに任意の数の消費者及び供給者にも同様に適用可能である。
【００１７】
例示的な実施形態は、単なる例として特定のアルゴリズム及びツールを用いて説明され、例示的な実施形態に限定されない。例示的な実施形態は、本発明の範囲内で、他の類似の又は同様な目的のアルゴリズム及びツールと共に用いることができる。例示的な実施形態は、ハードウェア、ソフトウェア、又はそれらの組み合わせで実装することができる。
【００１８】
本明細書に挙げられるいずれの利点も、単なる例であり、例示的な実施形態に限定することを意図するものではない。付加的な又は異なる利点は、特定の例示的な実施形態によって実現することができる。さらに、特定の例示的な実施形態は、上で挙げられた利点の幾つか又はすべてをもつことも、どれももたないこともある。
【００１９】
図面、特に図１及び図２を参照すると、これらの図面は、例示的な実施形態を実装することができるデータ処理環境の例示的な図である。図１及び図２は、単なる例であり、異なる実施形態を実装することができる環境に関してどのような限定も主張又は意味することを意図するものではない。特定の実装形態は、以下の説明に基づいて、示される環境に対して多くの修正を行うことができる。
【００２０】
図１は、例示的な実施形態を実装することができる電気配給ネットワークの例の図を示す。電気配給ネットワーク１００は、例としての供給者１０２及び１０４を含む。供給者１０２は、一例として、石炭、油又は原子力を用いて電気を生成する供給者とすることができる。供給者１０４は、一例として、風力又は太陽エネルギーから電気を生成するような、信頼性がより低い供給者１０４とすることができる。
【００２１】
ネットワーク１００は、消費者１０６及び１０８をさらに含む。導線１１０は、供給者１０２及び１０４から消費者１０６及び１０８に例としての電気ユーティリティを配送するネットワーク１００のインフラストラクチャの一部である。導線／グリッド１１２は、種々の供給者から種々の消費者に電気供給をもたらす、例としてのグリッドの一部とすることができる。典型的な電気配給ネットワークのスイッチング回路、変圧器、及びその他の構成要素は、例示を明確にするために、図から省いてある。
【００２２】
ネットワークの導線１１０、１１２及びその他の省かれた構成要素は、費用をかけて構築される。ネットワーク１００の２つの設計が、同程度の信頼性で、共通の供給者のセットから共通の消費者のセットに電気を配送できるものと仮定する。導線１１０及び１１２の閾値導線長より短い導線長を用いて供給者のセットから消費者のセットに電気を配給できるネットワーク１００の１つの設計は、閾値導線長より長い導線長を用いるネットワーク１００の別の設計より高い費用効果で電気を配給する。
【００２３】
図２を参照すると、この図は、例示的な実施形態を実装することができるデータ処理システムのブロック図を示す。データ処理システム２００は、実施形態による方法、実施形態によるコンピュータ使用可能プログラム製品又は実施形態によるシステムを実装するのに用いることができる、例としてのコンピュータである。
【００２４】
示される例において、データ処理システム２００は、ノースブリッジ及びメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２と、サウスブリッジ及び入力／出力（Ｉ／Ｏ）コントローラ・ハブ（ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを採用する。処理ユニット２０６と、メイン・メモリ２０８と、グラフィックス・プロセッサ２１０とは、ノースブリッジ及びメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２に結合される。処理ユニット２０６は、１つ又は複数のプロセッサを含むことができ、１つ又は複数の異種プロセッサ・システムを用いて実装することができる。特定の実装形態において、グラフィックス・プロセッサ２１０は、アクセラレイティッド・グラフィックス・ポート（ＡＧＰ）を通してＮＢ／ＭＣＨに結合することができる。
【００２５】
示される例において、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２は、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合される。オーディオ・アダプタ２１６、キーボード及びマウス・アダプタ２２０、モデム２２２、読み取り専用メモリ（ＲＯＭ）２２４、ユニバーサル・シリアル・バス（ＵＳＢ）及びその他のポート２３２、並びにＰＣＩ／ＰＣＩｅデバイス２３４は、バス２３８を通して、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合される。ハードディスク・ドライブ（ＨＤＤ）２２６及びＣＤ−ＲＯＭ２３０は、バス２４０を通して、サウスブリッジ及びＩ／Ｏコントローラ・ハブ２０４に結合される。ＰＣＩ／ＰＣＩｅデバイスは、例えば、イーサネット・アダプタ、アドイン・カード、及びノートブック・コンピュータのためのＰＣカードを含むことができる。ＰＣＩはカード・バス・コントローラを用いるが、ＰＣＩｅはこれを用いない。ＲＯＭ２２４は、例えば、フラッシュ・バイナリ入力／出力システム（ＢＩＯＳ）とすることができる。ハードディスク・ドライブ２２６及びＣＤ−ＲＯＭ２３０は、例えば、インテグレーテッド・ドライブ・エレクトロニクス（ＩＤＥ）又はシリアル・アドバンスド・テクノロジー・アタッチメント（ＳＡＴＡ）インターフェースを用いることができる。スーパーＩ／Ｏ（ＳＩＯ）デバイス２３６は、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合することができる。
【００２６】
オペレーティング・システムは、処理ユニット２０６上で作動する。オペレーティング・システムは、図２におけるデータ処理システム２００内の種々のコンポーネントを連携させ、制御する。オペレーティング・システムは、Ｍｉｃｒｏｓｏｆｔ（商標）Ｗｉｎｄｏｗｓ（商標）（Ｍｉｃｒｏｓｏｆｔ及びＷｉｎｄｏｗｓは、米国、その他の国々又はその両方におけるマイクロソフト・コーポレーションの商標である）、又はＬｉｎｕｘ（商標）（Ｌｉｎｕｘは米国、その他の国々又は両方におけるＬｉｎｕｓ Ｔｏｒｖａｌｄｓの商標である）といった、市販のオペレーティング・システムとすることができる。Ｊａｖａ（商標）プログラミング・システムのようなオブジェクト志向型プログラミング・システムは、オペレーティング・システムと共に作動することができ、データ処理システム２００上で実行されるＪａｖａ（商標）プログラム又はアプリケーションからオペレーティング・システムにコールを与える（Ｊａｖａ及びすべてのＪａｖａベースの商標並びにロゴは、Ｏｒａｃｌｅ及び／又はその関連会社の商標又は登録商標である）。
【００２７】
オペレーティング・システムのためのプログラム命令、オブジェクト志向型プログラミング・システム、例示的な実施形態のプロセス、及びアプリケーション又はプログラムは、ハードディスク・ドライブ２２６のようなストレージ・デバイス上に置かれ、処理ユニット２０６による実行のために、例えば、メイン・メモリ２０８、読み取り専用メモリ２２４、又は、１つ又は複数の周辺装置といったメモリ内に、ロードすることができる。プログラム命令はまた、不揮発性メモリ内に永続的に格納し、そこからロードしても、所定の場所で実行してもよい。例えば、実施形態による合成プログラムは、不揮発性メモリ内に格納し、そこからＤＲＡＭ内にロードすることができる。
【００２８】
図１−図２におけるハードウェアは、実装形態に応じて変更することができる。図１−図２に示されるハードウェアに加えて、又はこれらの代わりに、フラシュメモリ、等価な不揮発性メモリ、若しくは光学ディスクドライブなどのような、他の内部ハードウェア又は周辺機器を用いることができる。さらに、例示的な実施形態のプロセスは、マルチプロセッサ・データ処理システムに適用することができる。
【００２９】
幾つかの実施例においては、データ処理システム２００は、オペレーティング・システムのファイル及び／又はユーザ生成データを格納するための不揮発性メモリとなるフラッシュ・メモリを用いて一般に構成される携帯情報端末（ＰＤＡ）とすることができる。バス・システムは、システム・バス、Ｉ／Ｏバス、及びＰＣＩバスのような１つ又は複数のバスを含むことができる。当然のことながら、バス・システムは、通信ファブリック又はアーキテクチャに取り付けられた異なるコンポーネント又はデバイス間でデータの転送を提供する、いずれかのタイプの通信ファブリック又はアーキテクチャを用いて実装することができる。
【００３０】
通信ユニットは、モデム又はネットワーク・アダプタのような、データの送受信に用いられる１つ又は複数のデバイスを含むことができる。メモリは、例えば、メイン・メモリ２０８、又は、ノースブリッジ及びメモリ・コントローラ・ハブ２０２にあるキャッシュのようなキャッシュとすることができる。処理ユニットは、１つ又は複数のプロセッサ又はＣＰＵを含むことができる。
【００３１】
図１−図２に示される例及び上述の例は、アーキテクチャ上の限定を示すことを意味するものではない。例えば、データ処理システム２００は、ＰＤＡの形を取ることに加えて、タブレット・コンピュータ、ラップトップ・コンピュータ、又は電話デバイスとすることもできる。
【００３２】
図３を参照すると、この図は、例示的な実施形態による費用効果の高いネットワークを設計するためのグラフ簡約化プロセスを示す。最初の設計のグラフ３００において、供給者３０２、３０４及び３０６は、図１における供給者１０２及び１０４と同様な任意の数の供給者である。供給者３０２−３０６は、合わせて、合計供給能力３０８を有する。
【００３３】
合計需要３１０は、消費者３１２、３１４、３１６及び３１８の需要を含む。消費者３１２−３１８は、図１における消費者１０６及び１０８と同様な任意の数の消費者とすることができる。
【００３４】
図３の設計プロセスにおける第１のステップとして、各供給者３０２−３０６は、図示されるような接続３２０と同様の接続を用いて、各消費者３１２−３１８と接続される。接続３２０は、供給者３０２−３０６と消費者３１２−３１８との間の実際の導線接続ではなく、設計プロセスのための概念的な接続に過ぎないことに留意されたい。
【００３５】
接続３２０の各々はさらに、最大能力制約を伴って構成される。例えば、供給者３０２と消費者３１８との間の接続３２０は、１００キロワットの電力しか運べないように制約される場合がある。
【００３６】
設計のグラフ３５０において、それぞれ、供給者３５２、３５４及び３５６は、供給者３０２、３０４及び３０６と同じであり、能力３５８は能力３０８と同じであり、需要３６０は需要３１０と同じであり、消費者３６２、３６４、３６６及び３６８は、消費者３１２、３１４、３１６及び３１８と同じである。
【００３７】
設計プロセスのグラフ３５０において、接続３２０の幾つかは除去され、他は維持される。接続３７０は残っている接続であり、接続３７２は除去された接続である。接続３７２は、最小費用最大フロー・アルゴリズムを用いてグラフ３５０から除去される。最小費用最大フロー・アルゴリズムは、集積回路設計のような他の領域において適用される公知のアルゴリズムであり、消費者ノードの需要を満たす接続に対する制約に反することなく、消費者ノードの需要を供給者ノードから満たそうとするものである。
【００３８】
アルゴリズムはさらに、接続３７２のような特定の接続を除去することができるように、ある接続上のフローをその接続の制約まで最大化しようとする。アルゴリズムはさらに、供給者３５２のような供給者を閾値能力まで利用できるような供給者と消費者の対を生成しようとする。
【００３９】
例えば、供給者３５２が、１００メガワットの生産能力を有し、アルゴリズムによって、そのうちの８０パーセントである閾値供給能力を消費者に割り当てることができるものと仮定する。アルゴリズムは、供給者３５２が閾値供給能力を上限としてこれを超えることなく供給するように、消費者３６２−３６８のサブセットを供給者３５２と対にする。
【００４０】
従って、グラフ３５０は、利用可能な供給者の周りに消費者をクラスタ化する最低費用のネットワークである。最小費用最大フロー・アルゴリズムは、グラフ３５０から接続３７２を除去する。グラフ３５０においては、グラフ３００と比較すると、消費者３６２−３６８のサブセットを供給者３５２−３５６のうちの１つを用いてクラスタ化することによって、除去された接続３７２の導線長が節約されている。グラフ３５０は、接続３７２の導線長を節約する一方で、接続３７０の制約、供給者３５２−３５６の閾値供給能力を維持し、消費者３６４−３６８の需要を満たす。
【００４１】
図４を参照すると、この図は、例示的な実施形態による信頼性のための単純化されたループ・グラフを示す。「Ｓ１」と表示される供給者４０２は、図３における供給者３５２と同様である。「Ｃ１」と表示される消費者４０４及び「Ｃ２」と表示される消費者４０６は、図３における消費者３６２−３６８のサブセットである。
【００４２】
ネットワークのループ構造は、一点の障害を有するネットワークを確実に動作させるための最低費用ネットワークである。図４に示されるように、供給者４０２は、接続４０８を介して消費者４０４に供給し、接続４１０を介して消費者４０６に供給することができる。しかしながら、接続４０８の障害は、消費者４０４への供給を中断させ、接続４１０の障害は、消費者４０６への供給を中断させる。接続４１２によって形成されるループは、消費者４０４及び４０６の各々に供給するための２つの経路を与える。
【００４３】
実施形態によるループ・ネットワークを用いることによって、この方法においてどのような数の消費者が与えられても、ネットワークの信頼性を増強して、サービスを中断することなく一点の障害に耐えることができる。費用、例えば導線長を最小にするために、ループ内で、ノード、例えば供給者と消費者のサブセットとを順序付けることは、ハミルトン・サイクル問題として知られている。
【００４４】
任意サイズのノードの集合の場合には、ハミルトン・サイクル問題は、ＮＰ完全問題である。しかしながら、実施形態は、有限ノードの定められたセット、すなわち、図３に関して説明されたクラスタ化において選択された、定められた供給者及び定められた消費者のサブセットに適用される。従って、ユーティリティ配給ネットワークの最適化問題について、実施形態は、限られた時間で最低費用ループ・ネットワークの解を見出すことができる。例えば、実施形態は、単に、所与の供給者及び消費者のサブセットを通して、すべての可能なループを列挙し、それらの費用を評価し、費用を比較し、最低費用ループを選択することができる。
【００４５】
最低費用のループ、例えば電気配給ネットワークにおける最短導線長のループをこのように選択することで、実施形態は、図３における除去された接続３７２によって実現された導線長の削減のために費用効果の高いネットワークを提供し、費用効果の高いネットワークはまた、図４に従って計算されたループのために、単一の障害に対して信頼性が向上する。
【００４６】
図４は、３つのノード、すなわち１つの供給者と２つの消費者のみで示されるが、これは例示であることを明確にするために過ぎず、実施形態に対する限定ではないことに留意されたい。１つの供給者といずれかのサイズの消費者のサブセットとを用いることによって形成されるような、いずれかのサイズのノード集合を同様に用いて、単一の障害に対する信頼性を向上するループ・ネットワークを計算することができる。さらに、ノードの集合が特定のサイズを超えるときには、特定の既知の発見的方法を採用して、閾値費用より低い費用のループを実現することができる。
【００４７】
さらに、図４に示され、本明細書において説明されるループは、単なる例としてループにおける単一の障害に対する信頼性を向上させる。当業者は、本開示を用いて、ループにおける二つ、三つ又はそれ以上の障害に耐えて、中断することなくユーティリティの配給を継続することが可能なループ・ネットワークを計算することができる。そのようなループは、例示的な実施形態の範囲内で想定される。
【００４８】
図５を参照すると、この図は、例示的な実施形態によるユーティリティ配給ネットワークにおいて信頼性を向上させる第２の形態を示す。ループ４５２、４５４及び４５６の各々は、図４に関して説明されたような１つの供給者と消費者のサブセットとについて計算されたループである。
【００４９】
例えば、ループ４５２は、供給者Ｓ１と消費者Ｃ１及びＣ２との間の費用効果の高いネットワークを表しており、このネットワークは、ループ４５２における１つの障害を伴うユーティリティの連続供給について、信頼性が高いものである。同様に、ループ４５４は、供給者Ｓ２と消費者Ｃ３及びＣ４との間の費用効果の高い信頼性のあるネットワークを表わす。ループ４５６は、供給者Ｓ３と消費者Ｃ５及びＣ６との間の費用効果の高い信頼性のあるネットワークを表わす。
【００５０】
ループ構造を組み込むことによってネットワークの信頼性を向上させることに加えて、実施形態は、ユーティリティ配給ネットワークに供給者の冗長性を付与することによって、信頼性をさらに向上することができる。図５に示されるように、ループ４５２、４５４及び４５６は、接続４５８、４６０及び４６２を介して互いにさらに接続される。
【００５１】
例えば、接続４５８は、ループ４５４における供給者Ｓ２が供給を中止した場合に、ループ４５２における供給者Ｓ１から、ループ４５４における消費者Ｃ３及びＣ４に供給するように機能する。接続４５８は、供給者Ｓ１がユーティリティ供給を提供できないときに、同様に、供給者Ｓ２から消費者Ｃ１及びＣ２に供給するように機能する。
【００５２】
接続４６０及び４６２は、それぞれ、ループ４５４と４６５の間、ループ４５６と４５２の間で、同様に動作する。従って、実施形態によると、図５に示されるネットワークは、費用効果が高く（図３の導線長削減のために）、単一の障害に対して信頼性があり（図４のループ構造のために）、供給者の冗長性があるためにさらに信頼性がある（図５におけるようなループ間の相互接続のために）。
【００５３】
既存のネットワークは、実施形態の組み合わせを用いて同様に再構成できることに留意されたい。例えば、既存のネットワークは、図３におけるグラフ３５０の方法で特定の接続を除去し、それによってネットワークの維持管理費用を削減するように再構成することができる。別の例として、既存のネットワークは、信頼性を向上させるために、図４に関して説明される実施形態の方法でループを含むように再構成することができる。別の例として、既存のネットワークは、供給者の冗長性を与えることによって信頼性を向上させるように、図５に関して説明される実施形態の方法で再構成することができる。
【００５４】
別の例として、既存のネットワークは、図３、図４及び図５に関して説明された１つ又は複数の実施形態に従って、同様の方法で拡張することができる。従って、実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワークの設計を、新しい供給区域が計画されたときのような白紙の状態から支援するだけでなく、既存の供給区域が拡張されたとき又は新しい建物若しくは区画が想定されるときのような、既存のネットワークを改善又は拡張するときにも、支援することができる。
【００５５】
図６を参照すると、この図は、例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するプロセスのフローチャートを示す。プロセス５００は、図２におけるデータ処理システム２００のようなコンピュータ上で実行することができるコンピュータ使用可能コードを含むソフトウェア・アプリケーションに実装することができる。
【００５６】
プロセス５００は、供給者のセットを受信することによって開始する（ステップ５０２）。プロセス５００は、消費者のセットを受信する（５０４）。
【００５７】
プロセス５００は、図３におけるグラフ３００のように、各消費者を各供給者に接続する（ステップ５０６）。プロセス５００は、図３におけるグラフ３５０のように、最小費用最大フロー・アルゴリズムを用いて、接続の数を減らす（ステップ５０８）。
【００５８】
プロセス５００は、ステップ５０８の簡約化グラフにおいて、ネットワークを形成する１つ又は複数の供給者−消費者クラスタを識別する（ステップ５１０）。プロセス５００は、クラスタのループ・トポロジを計算することによって、１つ又は複数の識別されたクラスタのロバスト性（信頼性）を向上させる（ステップ５１２）。必要に応じて、プロセス５００は、ステップ５１２において、図５に関して説明されたような供給者の冗長性のための接続を計算することによって、クラスタのロバスト性をさらに向上することができる。プロセス５００は、その後終了するか、又は、「Ａ」で示される出口点を介して、図７におけるプロセス６００に合流するように進むことができる。
【００５９】
図７を参照すると、この図は、例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークをさらに最適化するプロセスの例のフローチャートを示す。プロセス６００は、図６におけるプロセス５００の実装形態と同様にソフトウェア・アプリケーションに実装することができる。
【００６０】
本明細書に説明されるように、供給者の冗長性を伴って又はそれを伴わずに、費用効果及び信頼性の高いネットワークが計算されると、ネットワークは、さらなる費用削減、供給効率、維持管理の削減、及びその他の有形及び無形の利点のためにさらに最適化することができる。例えば、供給者のセット及び消費者のセットが与えられる場合には、ハミルトン・サイクルの下限によって定められる接続数を有するネットワークを上述のように実現することができる。信頼性の向上のために各消費者への二重の供給経路が必要な場合には、接続数の上限は、ネットワークのグラフのシュタイナー・ツリー長の２倍に設定することができる。
【００６１】
さらに、図３のグラフ３５０のようなクラスタ形成段階の際に、費用削減における１つの考慮事項は、供給者と消費者との間の距離であった。例えば、その考慮事項に加えて、実施形態による最適化プロセスは、図４のループ計算に備えて、クラスタ内の消費者間の距離を閾値より下の限度内に留めることなどによって、消費者間の距離をさらに考慮してクラスタを計算する。
【００６２】
別の例として、既存のネットワークについて、実施形態では、拡張のためのネットワーク計算を最適化するに当たって既存の供給者と消費者との接続費用を考慮する。別の例として、実施形態は、特定の消費者を特定の供給者又は特定の他の消費者と共に配置することなどによって、以前のグラフ簡約化の反復からクラスタ形成を変更し、簡約化グラフを再計算することができる。そのようなクラスタの操作によって、２つ又はそれ以上のクラスタを合体させてより大きいクラスタにすることができ、これにより、特定の状況下で、増大した導線長の節約をもたらすことができる。
【００６３】
別の例として、実施形態は、ループに基づく信頼性の向上と冗長供給者に基づく信頼性の向上との間の費用を比較して、より良好な費用節約のために、両方ではなくいずれか一方を選択する。図７におけるプロセス６００は、実施形態によるこれらの最適化ステップの幾つかを行うプロセスの例である。
【００６４】
プロセス６００は、クラスタを選択することによって開始する（ステップ６０２）。図６におけるプロセス５００のような別のプロセスが、「Ａ」で示される入口点においてプロセス６００に入り、ステップ６０２に進むことができる。
【００６５】
プロセス６００は、クラスタ費用を削減するために、消費者を１つのクラスタから別のクラスタに移動させる（ステップ６０４）。例えば、消費者が１つのネットワークから除去されたときには、そのクラスタ内でその消費者に供給するための導線長を除去することができ、従って、クラスタ費用を削減することができる。そのような移動は、例えばクラスタ内の供給者が閾値供給能力を上回った状態で使用されているときに、有益である。
【００６６】
代替的に、又はステップ６０４と併せて、プロセス６００は、１つのクラスタを別のクラスタと合体させる（ステップ６０６）。２つ又はそれ以上のクラスタを共に合体させることによって、組み合わされたグラフにおける合計導線長を減らし、従って、組み合わされたクラスタの費用を削減することができる。
【００６７】
プロセス６００は、ステップ６０４、６０６又はその両方の結果によって生じたクラスタの費用を再計算する（ステップ６０８）。プロセス６００は、解、すなわちグラフ又は結果として生じたクラスタ若しくはネットワークが、特定の限度を満たすかどうかを判定する（ステップ６１０）。例えば、単一障害の信頼性について上述されたように、解の上限は、クラスタ内の供給者及び消費者のノードを用いて可能となるシュタイナー・ツリーにおけるシュタイナー・ツリー長の２倍に設定することができる。
【００６８】
解の費用が、上述の例における２×シュタイナー・ツリー長によって定められる閾値を超えるときなどのように、解の費用が限度内にない場合（ステップ６１０の「いいえ」の経路）には、プロセス６００は、ステップ６０４、６０６、又はその両方の別の反復を行うために戻る。解の費用が、限度内にある場合（ステップ６１０の「はい」の経路）には、プロセス６００は、ステップ６１２に進む。当然のことながら、例示的な実施形態の範囲内で、あらゆる適切な条件をステップ６１０において特定することができる。
【００６９】
プロセス６００は、本明細書に説明される特定の条件が満たされるまで、ステップ６０４、６０６、６０８及び６１０を反復して行う。そのような反復においては、プロセス６００は、ステップ６０４、６０６又はその両方を行うことによって得られる可能な解を列挙し、ステップ６０８において、列挙された解を評価し、ステップ６０８の計算に基づいて望ましい解を選択し、ステップ６１０において、特定された条件が満たされていない場合には、ステップ６０４、６０６及び６０８を繰り返す。
【００７０】
プロセス６００は、解、すなわち提案される費用効果及び信頼性の高いネットワークを出力する（ステップ６１２）。プロセス６００は、その後終了する。
【００７１】
図におけるフローチャート及びブロック図は、本発明の種々の実施形態によるシステム、方法、及びコンピュータ・プログラム製品の可能な実装形態のアーキテクチャ、機能、及び操作を示す。この点に関して、フローチャート又はブロック図の中の各ブロックは、特定の１つ又は複数の論理機能を実装するための１つ又は複数の実行可能命令を含むコードのモジュール、セグメント、又は一部を表すことができる。幾つかの代替的な実装形態においては、ブロックに記載された機能が図に示される順序通りに行われない場合があることにも留意すべきである。例えば、連続して示される２つのブロックは、関与する機能に応じて、実際には、実質的に同時に実行されることがあり、ブロックが逆順に実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及び、ブロック図及び／又はフローチャート図におけるブロックの組み合わせは、特定の機能若しくは動作を行う専用ハードウェア・ベースのシステムによって、又は、専用ハードウェアとコンピュータ命令との組み合わせによって、実装できることにも留意されたい。
【００７２】
このようにして、費用効果及び信頼性の高いユーティリティ配給ネットワークを生成又は修正するためのコンピュータ実装方法、システム及びコンピュータ・プログラム製品が例示的な実施形態において提供される。本発明の実施形態を用いることによって、ネットワークにおける導線長又は導管長などの費用を削減するように、新しい又は既存のネットワークを設計することができる。特定の実施形態が、費用関数としてノード間の距離に関して説明されたが、そのような費用関数は、例として用いられるに過ぎず、本発明を限定するものとして用いられるものではない。導線又は導管のタイプ、特定の供給者又は接続に関する負荷平衡の費用、クラスタ費用に関する上限又は下限のような、他の費用関数も、本発明の範囲内で、実施形態と併せて同様に用いることができる。
【００７３】
実施形態は、散発する供給者及び将来の成長要求に信頼性をもって対応するネットワークを設計するのに用いることができる。実施形態は、設計時には費用の基準を満たし、さらに、成長時には、ネットワークの設計における成長経路がネットワークの信頼性又はロバスト性を維持することを可能にする、ネットワークを生成する。
【００７４】
当業者であれば分かるように、本発明の態様は、システム、方法、又はコンピュータ・プログラム製品として具体化することができる。従って、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、又は、ソフトウェア及びハードウェアの態様を組み合わせた実施形態の形を取ることができ、本明細書ではその全てを一般的に「回路」、「デバイス」、「モジュール」、又は「システム」と呼ぶことがある。さらにまた、本発明の態様は、コンピュータ可読プログラム・コードが組み込まれた１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体において具体化された、コンピュータ・プログラム製品の形を取ることができる。
【００７５】
１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体のいずれの組み合わせも用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ・デバイスは、例えば、電子、磁気、光学、電磁気、赤外線、若しくは半導体のシステム、装置若しくはデバイス又は上記のいずれかの適切な組み合わせとすることができるが、これらに限定されるものではない。コンピュータ可読ストレージ・デバイスのより具体的な例（非網羅的なリスト）として、１つ又は複数の導線を有する電気接続、携帯可能コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、携帯可能コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光ストレージ・デバイス、磁気ストレージ・デバイス、又は上記のいずれかの適切な組み合わせが挙げられる。本明細書の文脈において、コンピュータ可読ストレージ・デバイスは、命令実行システム、装置、若しくはデバイスによって、又はこれらと共に、用いるためのプログラムを含むか又は格納することができるいずれかの有形のデバイス又は媒体とすることができる。
【００７６】
コンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体上に具体化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は上記のいずれかの好適な組み合わせ含むがこれらに限定されないいずれかの適切な媒体を用いて、伝送することができる。
【００７７】
本発明の態様の操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（商標）、ＳｍａｌｌＴａｌｋ（商標）、Ｃ＋＋などのようなオブジェクト指向型プログラミング言語と、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語とを含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで書くことができる。プログラム・コードは、完全にユーザのコンピュータ上で実行するか、スタンドアロンのソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行するか、部分的にユーザのコンピュータ上で実行し、部分的にリモート・コンピュータ上で実行するか、又は、完全にリモート・コンピュータ若しくはサーバ上で実行することができる。後者の場合には、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続することができ、又は、（例えば、インターネット・サービス・プロバイダを用いてインターネットを通じて）外部コンピュータに接続することもできる。
【００７８】
本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して、本明細書に説明される。フローチャート図及び／又はブロック図の各ブロック、及び、フローチャート図及び／又はブロック図におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実装できることが理解されるであろう。これらのコンピュータ・プログラム命令を１つ又は複数の汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置の１つ又は複数のプロセッサに与えてマシンを生成し、それにより、コンピュータ又は他のプログラム可能データ処理装置の１つ又は複数のプロセッサによって実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装するための手段を生成するようにしてもよい。
【００７９】
また、これらのコンピュータ命令を、特定の方法で機能するように、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイスを向けることができる１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体に格納し、それにより、その１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体に格納された命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装する命令を含む製品を作るようにしてもよい。
【００８０】
また、コンピュータ・プログラム命令を、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイスにロードし、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイス上で一連の操作ステップを行わせて、コンピュータ実装プロセスを生成し、それにより、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイス上で実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実行するためのプロセスを提供するようにしてもよい。
【００８１】
本明細書において用いられる用語は、特定の実施形態を説明する目的だけのためのものであり、本発明を限定することを意図したものではない。本明細書において用いられる場合、文脈から明らかにそうでないことが示されていない限り、単数形「ａ」「ａｎ」、及び「ｔｈｅ」は、複数形も同様に含むことが意図される。「含む（ｃｏｍｐｒｉｓｅｓ）」及び／又は「含んでいる（ｃｏｍｐｒｉｓｉｎｇ）」という用語は、この明細書において使用される場合、言明された特徴、整数、ステップ、動作、要素、及び／又はコンポーネントの存在を特定するものではあるが、１つ又は複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、及び／又はそれらの群の存在又は追加を排除するものではないことが、さらに理解されるであろう。
【００８２】
特許請求の範囲における全ての「手段又はステップと機能との組合せ（ミーンズ又はステップ・プラス・ファンクション）」要素の対応する構造、材料、行為及び均等物は、その機能を、明確に特許請求されているように他の特許請求された要素と組み合わせて実行するための、いかなる構造、材料又は行為をも含むことが意図される。本発明の説明は、例示及び説明の目的で提示されたものであるが、網羅的であることを意図するものではなく、本発明を開示された形態に限定することを意図するものでもない。本発明の範囲及び趣旨から逸脱することのない多くの変更及び変形が、当業者には明らかである。実施形態は、本発明の原理及び実際の用途を最も良く説明するため、及び、当業者が本発明を種々の変更を有する種々の実施形態について企図される特定の使用に適したものとして理解することを可能にするために、選択及び記載された。
【符号の説明】
【００８３】
１００：電気配給ネットワーク
１１０：導線
１１２：導線／グリッド
２００：データ処理システム
３００、３５０：グラフ
３０２、３０４、３０６、３５２、３５４、３５６、Ｓ１、Ｓ２、Ｓ３：供給者
３１２、３１４、３１６、３１８、３６２、３６４、３６６、３６８、Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６：消費者
４０８、４１０、４１２、４５８、４６０、４６２：接続
４５２、４５４、４５６：ループ
５００、６００：プロセス
【技術分野】
【０００１】
本発明は、一般に、ユーティリティ配給ネットワークを生成又は修正するための方法、システム、及びコンピュータ・プログラム製品に関する。より具体的には、本発明は、ネットワークが費用効果が高く信頼できるものとなるようにユーティリティ配給ネットワークを生成又は修正するための方法、システム、及びコンピュータ・プログラム製品に関する。
【背景技術】
【０００２】
電気、水及びガスといったユーティリティは、種々の供給者から種々の消費者に供給される。ユーティリティの配給は、これらのユーティリティの好適な搬送装置のネットワークを通して行われる。例えば、電気は、電気ケーブル及びグリッドのネットワークを通して配給され、水及びガスは、パイプラインのネットワーク上で配給される。
【０００３】
新しいユーティリティ配給ネットワーク（ネットワーク）は、例えば、新しい都市又は区画が計画されるときに設計される。既存のネットワークは、例えば、新しい供給者が表れた場合、古い供給者が事業を止めた場合、又は、消費者若しくは需要のパターンが変化した場合のように、配給に変更が必要であるときに修正される。
【０００４】
ユーティリティ配給ネットワークは、高価なインフラストラクチャである。その構築には、大きな設備投資が必要である。ネットワークの維持管理には、多くの時間及び出費が必要である。既存のネットワークの修正は複雑であり、費用、時間、及びユーティリティ・サービスのダウン時間が関係する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ユーティリティ配給ネットワークは、信頼できるものでなければならない。例えば、ネットワークにおける障害がユーティリティの供給を中断しないものであることが望ましい。
【課題を解決するための手段】
【０００６】
例示的な実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワーク（ネットワーク）のための方法、システム、及びコンピュータ・プログラム製品を提供する。実施形態は、複数のクラスタを形成するように、ユーティリティの消費者のセットをユーティリティの供給者のセットと接続するグラフを簡約化する。本実施形態は、複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良し、この改良することは、第１のネットワークにおける所定数の障害後に、消費者のサブセットへのユーティリティの供給を継続するように、第１の接続を第１のネットワークに加えることである。本実施形態は、供給者のセットを消費者のセットに接続する第２のネットワークについての設計を生成し、第２のネットワークは改良後の第１のネットワークを含んでおり、第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有する。
【図面の簡単な説明】
【０００７】
【図１】例示的な実施形態を実装することができる電気配給ネットワークの例の図を示す。
【図２】例示的な実施形態を実装することができるデータ処理システムのブロック図を示す。
【図３】例示的な実施形態による費用効果の高いネットワークを設計するためのグラフ簡約化プロセスを示す。
【図４】例示的な実施形態による信頼性のための単純化されたループ・グラフを示す。
【図５】例示的な実施形態によるユーティリティ配給ネットワークにおいて信頼性を向上させる第２の形態を示す。
【図６】例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するプロセスのフローチャートを示す。
【図７】例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークをさらに最適化する例示的なプロセスのフローチャートを示す。
【発明を実施するための形態】
【０００８】
本発明の特徴であると考えられる新規な構成が、特許請求の範囲に記載される。しかしながら、本発明自体、並びに、本発明の好ましい使用形態、さらなる目的及び利点は、図面と併せて読んだときに、例示的な実施形態の以下の詳細な説明を参照することによって、最も良く理解される。
【０００９】
本発明によって、ユーティリティ配給ネットワークは、構築するのに費用効果が高く、動作が信頼できるものでなければならないことが分かる。例えば、ネットワークを構築するためのより単純化された１つの手法は、ユーティリティの各消費者（消費者）をユーティリティの供給者（供給者）に接続するものである。しかしながら、そのようなより単純化された手法は、サービスを消費者に第１の供給者から提供する場合と第２の供給者から提供する場合のネットワーク構築における比較費用を考慮していない。例えば、消費者のより近くにある第１の供給者から供給することは、第１の供給者から遠くにある第２の供給者から消費者に供給することと比較すると、第１の供給者の方が必要な導線又はケーブルの長さが短いため、より費用効果が高い。
【００１０】
そのようなより単純化された手法はまた、サービスの継続性についての信頼性が低い。例えば、第１の供給者がユーティリティを供給できないとき又は第１の供給者と消費者との間のネットワークが機能しなくなったときには、ユーティリティを消費者に提供することができない。
【００１１】
若干の信頼性を伴ってネットワークを構築するより単純化された別の手法は、２つ又はそれ以上の供給者から任意に消費者にサービスを提供することである。ここでも、そのような手法は、異なる供給者から消費者にサービスを提供するネットワークを構築する比較費用を考慮していない。
【００１２】
消費者と供給者の間のような２点間の最短距離を選択するための幾つかの最短経路アルゴリズムが知られている。本発明によって、単に消費者と供給者との間の距離が最短であるというだけの理由で消費者と供給者とを対にすることは、費用効果及び信頼性の点から十分な解決策ではないことが分かる。例えば、消費者に最も近い供給者は、風力エネルギーを電気に変換する供給者のような散在する供給者であることがある。
【００１３】
信頼性は、例えばネットワークにおける導線を二重にすることによって、実現することができる。しかしながら、こうした法は、導線長といったネットワーク資源を無駄にするものであるため、そのような信頼性は費用効果が低い。
【００１４】
本発明によって、ネットワークが、費用効果及び信頼性の観点から所与の消費者のセット及び所与の供給者のセットのために設計された場合であっても、そのような設計プロセスは、自動化プロセスの結果ではなく、従って容易に複製できるものではないことが分かる。特定の供給者及び消費者のための特定のネットワーク設計は、費用効果及び信頼性が高い場合があるが、通常、可能なネットワーク化の選択枝について試行錯誤による網羅的な調査が必要である。
【００１５】
本発明を説明するのに用いられる例示的な実施形態は、一般に、ユーティリティ配給ネットワーク設計に関する上述の問題に対処し、解決するものである。例示的な実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するための方法、システム及びコンピュータ・プログラム製品を提供する。
【００１６】
本発明及びその種々の実施形態は、本明細書においては、単に本開示を明確にするために、主として、限られた数の消費者とユーティリティの例すなわち電気の供給者との間の単純化された関係に関して、説明される。ユーティリティ配給ネットワークの設計に関して本明細書において説明される概念、方法、製品、システム、動作、作用、構成、又は操作は、限定することなく、他のタイプのユーティリティ配給ネットワーク並びに任意の数の消費者及び供給者にも同様に適用可能である。
【００１７】
例示的な実施形態は、単なる例として特定のアルゴリズム及びツールを用いて説明され、例示的な実施形態に限定されない。例示的な実施形態は、本発明の範囲内で、他の類似の又は同様な目的のアルゴリズム及びツールと共に用いることができる。例示的な実施形態は、ハードウェア、ソフトウェア、又はそれらの組み合わせで実装することができる。
【００１８】
本明細書に挙げられるいずれの利点も、単なる例であり、例示的な実施形態に限定することを意図するものではない。付加的な又は異なる利点は、特定の例示的な実施形態によって実現することができる。さらに、特定の例示的な実施形態は、上で挙げられた利点の幾つか又はすべてをもつことも、どれももたないこともある。
【００１９】
図面、特に図１及び図２を参照すると、これらの図面は、例示的な実施形態を実装することができるデータ処理環境の例示的な図である。図１及び図２は、単なる例であり、異なる実施形態を実装することができる環境に関してどのような限定も主張又は意味することを意図するものではない。特定の実装形態は、以下の説明に基づいて、示される環境に対して多くの修正を行うことができる。
【００２０】
図１は、例示的な実施形態を実装することができる電気配給ネットワークの例の図を示す。電気配給ネットワーク１００は、例としての供給者１０２及び１０４を含む。供給者１０２は、一例として、石炭、油又は原子力を用いて電気を生成する供給者とすることができる。供給者１０４は、一例として、風力又は太陽エネルギーから電気を生成するような、信頼性がより低い供給者１０４とすることができる。
【００２１】
ネットワーク１００は、消費者１０６及び１０８をさらに含む。導線１１０は、供給者１０２及び１０４から消費者１０６及び１０８に例としての電気ユーティリティを配送するネットワーク１００のインフラストラクチャの一部である。導線／グリッド１１２は、種々の供給者から種々の消費者に電気供給をもたらす、例としてのグリッドの一部とすることができる。典型的な電気配給ネットワークのスイッチング回路、変圧器、及びその他の構成要素は、例示を明確にするために、図から省いてある。
【００２２】
ネットワークの導線１１０、１１２及びその他の省かれた構成要素は、費用をかけて構築される。ネットワーク１００の２つの設計が、同程度の信頼性で、共通の供給者のセットから共通の消費者のセットに電気を配送できるものと仮定する。導線１１０及び１１２の閾値導線長より短い導線長を用いて供給者のセットから消費者のセットに電気を配給できるネットワーク１００の１つの設計は、閾値導線長より長い導線長を用いるネットワーク１００の別の設計より高い費用効果で電気を配給する。
【００２３】
図２を参照すると、この図は、例示的な実施形態を実装することができるデータ処理システムのブロック図を示す。データ処理システム２００は、実施形態による方法、実施形態によるコンピュータ使用可能プログラム製品又は実施形態によるシステムを実装するのに用いることができる、例としてのコンピュータである。
【００２４】
示される例において、データ処理システム２００は、ノースブリッジ及びメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２と、サウスブリッジ及び入力／出力（Ｉ／Ｏ）コントローラ・ハブ（ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを採用する。処理ユニット２０６と、メイン・メモリ２０８と、グラフィックス・プロセッサ２１０とは、ノースブリッジ及びメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２に結合される。処理ユニット２０６は、１つ又は複数のプロセッサを含むことができ、１つ又は複数の異種プロセッサ・システムを用いて実装することができる。特定の実装形態において、グラフィックス・プロセッサ２１０は、アクセラレイティッド・グラフィックス・ポート（ＡＧＰ）を通してＮＢ／ＭＣＨに結合することができる。
【００２５】
示される例において、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２は、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合される。オーディオ・アダプタ２１６、キーボード及びマウス・アダプタ２２０、モデム２２２、読み取り専用メモリ（ＲＯＭ）２２４、ユニバーサル・シリアル・バス（ＵＳＢ）及びその他のポート２３２、並びにＰＣＩ／ＰＣＩｅデバイス２３４は、バス２３８を通して、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合される。ハードディスク・ドライブ（ＨＤＤ）２２６及びＣＤ−ＲＯＭ２３０は、バス２４０を通して、サウスブリッジ及びＩ／Ｏコントローラ・ハブ２０４に結合される。ＰＣＩ／ＰＣＩｅデバイスは、例えば、イーサネット・アダプタ、アドイン・カード、及びノートブック・コンピュータのためのＰＣカードを含むことができる。ＰＣＩはカード・バス・コントローラを用いるが、ＰＣＩｅはこれを用いない。ＲＯＭ２２４は、例えば、フラッシュ・バイナリ入力／出力システム（ＢＩＯＳ）とすることができる。ハードディスク・ドライブ２２６及びＣＤ−ＲＯＭ２３０は、例えば、インテグレーテッド・ドライブ・エレクトロニクス（ＩＤＥ）又はシリアル・アドバンスド・テクノロジー・アタッチメント（ＳＡＴＡ）インターフェースを用いることができる。スーパーＩ／Ｏ（ＳＩＯ）デバイス２３６は、サウスブリッジ及びＩ／Ｏコントローラ・ハブ（ＳＢ／ＩＣＨ）２０４に結合することができる。
【００２６】
オペレーティング・システムは、処理ユニット２０６上で作動する。オペレーティング・システムは、図２におけるデータ処理システム２００内の種々のコンポーネントを連携させ、制御する。オペレーティング・システムは、Ｍｉｃｒｏｓｏｆｔ（商標）Ｗｉｎｄｏｗｓ（商標）（Ｍｉｃｒｏｓｏｆｔ及びＷｉｎｄｏｗｓは、米国、その他の国々又はその両方におけるマイクロソフト・コーポレーションの商標である）、又はＬｉｎｕｘ（商標）（Ｌｉｎｕｘは米国、その他の国々又は両方におけるＬｉｎｕｓ Ｔｏｒｖａｌｄｓの商標である）といった、市販のオペレーティング・システムとすることができる。Ｊａｖａ（商標）プログラミング・システムのようなオブジェクト志向型プログラミング・システムは、オペレーティング・システムと共に作動することができ、データ処理システム２００上で実行されるＪａｖａ（商標）プログラム又はアプリケーションからオペレーティング・システムにコールを与える（Ｊａｖａ及びすべてのＪａｖａベースの商標並びにロゴは、Ｏｒａｃｌｅ及び／又はその関連会社の商標又は登録商標である）。
【００２７】
オペレーティング・システムのためのプログラム命令、オブジェクト志向型プログラミング・システム、例示的な実施形態のプロセス、及びアプリケーション又はプログラムは、ハードディスク・ドライブ２２６のようなストレージ・デバイス上に置かれ、処理ユニット２０６による実行のために、例えば、メイン・メモリ２０８、読み取り専用メモリ２２４、又は、１つ又は複数の周辺装置といったメモリ内に、ロードすることができる。プログラム命令はまた、不揮発性メモリ内に永続的に格納し、そこからロードしても、所定の場所で実行してもよい。例えば、実施形態による合成プログラムは、不揮発性メモリ内に格納し、そこからＤＲＡＭ内にロードすることができる。
【００２８】
図１−図２におけるハードウェアは、実装形態に応じて変更することができる。図１−図２に示されるハードウェアに加えて、又はこれらの代わりに、フラシュメモリ、等価な不揮発性メモリ、若しくは光学ディスクドライブなどのような、他の内部ハードウェア又は周辺機器を用いることができる。さらに、例示的な実施形態のプロセスは、マルチプロセッサ・データ処理システムに適用することができる。
【００２９】
幾つかの実施例においては、データ処理システム２００は、オペレーティング・システムのファイル及び／又はユーザ生成データを格納するための不揮発性メモリとなるフラッシュ・メモリを用いて一般に構成される携帯情報端末（ＰＤＡ）とすることができる。バス・システムは、システム・バス、Ｉ／Ｏバス、及びＰＣＩバスのような１つ又は複数のバスを含むことができる。当然のことながら、バス・システムは、通信ファブリック又はアーキテクチャに取り付けられた異なるコンポーネント又はデバイス間でデータの転送を提供する、いずれかのタイプの通信ファブリック又はアーキテクチャを用いて実装することができる。
【００３０】
通信ユニットは、モデム又はネットワーク・アダプタのような、データの送受信に用いられる１つ又は複数のデバイスを含むことができる。メモリは、例えば、メイン・メモリ２０８、又は、ノースブリッジ及びメモリ・コントローラ・ハブ２０２にあるキャッシュのようなキャッシュとすることができる。処理ユニットは、１つ又は複数のプロセッサ又はＣＰＵを含むことができる。
【００３１】
図１−図２に示される例及び上述の例は、アーキテクチャ上の限定を示すことを意味するものではない。例えば、データ処理システム２００は、ＰＤＡの形を取ることに加えて、タブレット・コンピュータ、ラップトップ・コンピュータ、又は電話デバイスとすることもできる。
【００３２】
図３を参照すると、この図は、例示的な実施形態による費用効果の高いネットワークを設計するためのグラフ簡約化プロセスを示す。最初の設計のグラフ３００において、供給者３０２、３０４及び３０６は、図１における供給者１０２及び１０４と同様な任意の数の供給者である。供給者３０２−３０６は、合わせて、合計供給能力３０８を有する。
【００３３】
合計需要３１０は、消費者３１２、３１４、３１６及び３１８の需要を含む。消費者３１２−３１８は、図１における消費者１０６及び１０８と同様な任意の数の消費者とすることができる。
【００３４】
図３の設計プロセスにおける第１のステップとして、各供給者３０２−３０６は、図示されるような接続３２０と同様の接続を用いて、各消費者３１２−３１８と接続される。接続３２０は、供給者３０２−３０６と消費者３１２−３１８との間の実際の導線接続ではなく、設計プロセスのための概念的な接続に過ぎないことに留意されたい。
【００３５】
接続３２０の各々はさらに、最大能力制約を伴って構成される。例えば、供給者３０２と消費者３１８との間の接続３２０は、１００キロワットの電力しか運べないように制約される場合がある。
【００３６】
設計のグラフ３５０において、それぞれ、供給者３５２、３５４及び３５６は、供給者３０２、３０４及び３０６と同じであり、能力３５８は能力３０８と同じであり、需要３６０は需要３１０と同じであり、消費者３６２、３６４、３６６及び３６８は、消費者３１２、３１４、３１６及び３１８と同じである。
【００３７】
設計プロセスのグラフ３５０において、接続３２０の幾つかは除去され、他は維持される。接続３７０は残っている接続であり、接続３７２は除去された接続である。接続３７２は、最小費用最大フロー・アルゴリズムを用いてグラフ３５０から除去される。最小費用最大フロー・アルゴリズムは、集積回路設計のような他の領域において適用される公知のアルゴリズムであり、消費者ノードの需要を満たす接続に対する制約に反することなく、消費者ノードの需要を供給者ノードから満たそうとするものである。
【００３８】
アルゴリズムはさらに、接続３７２のような特定の接続を除去することができるように、ある接続上のフローをその接続の制約まで最大化しようとする。アルゴリズムはさらに、供給者３５２のような供給者を閾値能力まで利用できるような供給者と消費者の対を生成しようとする。
【００３９】
例えば、供給者３５２が、１００メガワットの生産能力を有し、アルゴリズムによって、そのうちの８０パーセントである閾値供給能力を消費者に割り当てることができるものと仮定する。アルゴリズムは、供給者３５２が閾値供給能力を上限としてこれを超えることなく供給するように、消費者３６２−３６８のサブセットを供給者３５２と対にする。
【００４０】
従って、グラフ３５０は、利用可能な供給者の周りに消費者をクラスタ化する最低費用のネットワークである。最小費用最大フロー・アルゴリズムは、グラフ３５０から接続３７２を除去する。グラフ３５０においては、グラフ３００と比較すると、消費者３６２−３６８のサブセットを供給者３５２−３５６のうちの１つを用いてクラスタ化することによって、除去された接続３７２の導線長が節約されている。グラフ３５０は、接続３７２の導線長を節約する一方で、接続３７０の制約、供給者３５２−３５６の閾値供給能力を維持し、消費者３６４−３６８の需要を満たす。
【００４１】
図４を参照すると、この図は、例示的な実施形態による信頼性のための単純化されたループ・グラフを示す。「Ｓ１」と表示される供給者４０２は、図３における供給者３５２と同様である。「Ｃ１」と表示される消費者４０４及び「Ｃ２」と表示される消費者４０６は、図３における消費者３６２−３６８のサブセットである。
【００４２】
ネットワークのループ構造は、一点の障害を有するネットワークを確実に動作させるための最低費用ネットワークである。図４に示されるように、供給者４０２は、接続４０８を介して消費者４０４に供給し、接続４１０を介して消費者４０６に供給することができる。しかしながら、接続４０８の障害は、消費者４０４への供給を中断させ、接続４１０の障害は、消費者４０６への供給を中断させる。接続４１２によって形成されるループは、消費者４０４及び４０６の各々に供給するための２つの経路を与える。
【００４３】
実施形態によるループ・ネットワークを用いることによって、この方法においてどのような数の消費者が与えられても、ネットワークの信頼性を増強して、サービスを中断することなく一点の障害に耐えることができる。費用、例えば導線長を最小にするために、ループ内で、ノード、例えば供給者と消費者のサブセットとを順序付けることは、ハミルトン・サイクル問題として知られている。
【００４４】
任意サイズのノードの集合の場合には、ハミルトン・サイクル問題は、ＮＰ完全問題である。しかしながら、実施形態は、有限ノードの定められたセット、すなわち、図３に関して説明されたクラスタ化において選択された、定められた供給者及び定められた消費者のサブセットに適用される。従って、ユーティリティ配給ネットワークの最適化問題について、実施形態は、限られた時間で最低費用ループ・ネットワークの解を見出すことができる。例えば、実施形態は、単に、所与の供給者及び消費者のサブセットを通して、すべての可能なループを列挙し、それらの費用を評価し、費用を比較し、最低費用ループを選択することができる。
【００４５】
最低費用のループ、例えば電気配給ネットワークにおける最短導線長のループをこのように選択することで、実施形態は、図３における除去された接続３７２によって実現された導線長の削減のために費用効果の高いネットワークを提供し、費用効果の高いネットワークはまた、図４に従って計算されたループのために、単一の障害に対して信頼性が向上する。
【００４６】
図４は、３つのノード、すなわち１つの供給者と２つの消費者のみで示されるが、これは例示であることを明確にするために過ぎず、実施形態に対する限定ではないことに留意されたい。１つの供給者といずれかのサイズの消費者のサブセットとを用いることによって形成されるような、いずれかのサイズのノード集合を同様に用いて、単一の障害に対する信頼性を向上するループ・ネットワークを計算することができる。さらに、ノードの集合が特定のサイズを超えるときには、特定の既知の発見的方法を採用して、閾値費用より低い費用のループを実現することができる。
【００４７】
さらに、図４に示され、本明細書において説明されるループは、単なる例としてループにおける単一の障害に対する信頼性を向上させる。当業者は、本開示を用いて、ループにおける二つ、三つ又はそれ以上の障害に耐えて、中断することなくユーティリティの配給を継続することが可能なループ・ネットワークを計算することができる。そのようなループは、例示的な実施形態の範囲内で想定される。
【００４８】
図５を参照すると、この図は、例示的な実施形態によるユーティリティ配給ネットワークにおいて信頼性を向上させる第２の形態を示す。ループ４５２、４５４及び４５６の各々は、図４に関して説明されたような１つの供給者と消費者のサブセットとについて計算されたループである。
【００４９】
例えば、ループ４５２は、供給者Ｓ１と消費者Ｃ１及びＣ２との間の費用効果の高いネットワークを表しており、このネットワークは、ループ４５２における１つの障害を伴うユーティリティの連続供給について、信頼性が高いものである。同様に、ループ４５４は、供給者Ｓ２と消費者Ｃ３及びＣ４との間の費用効果の高い信頼性のあるネットワークを表わす。ループ４５６は、供給者Ｓ３と消費者Ｃ５及びＣ６との間の費用効果の高い信頼性のあるネットワークを表わす。
【００５０】
ループ構造を組み込むことによってネットワークの信頼性を向上させることに加えて、実施形態は、ユーティリティ配給ネットワークに供給者の冗長性を付与することによって、信頼性をさらに向上することができる。図５に示されるように、ループ４５２、４５４及び４５６は、接続４５８、４６０及び４６２を介して互いにさらに接続される。
【００５１】
例えば、接続４５８は、ループ４５４における供給者Ｓ２が供給を中止した場合に、ループ４５２における供給者Ｓ１から、ループ４５４における消費者Ｃ３及びＣ４に供給するように機能する。接続４５８は、供給者Ｓ１がユーティリティ供給を提供できないときに、同様に、供給者Ｓ２から消費者Ｃ１及びＣ２に供給するように機能する。
【００５２】
接続４６０及び４６２は、それぞれ、ループ４５４と４６５の間、ループ４５６と４５２の間で、同様に動作する。従って、実施形態によると、図５に示されるネットワークは、費用効果が高く（図３の導線長削減のために）、単一の障害に対して信頼性があり（図４のループ構造のために）、供給者の冗長性があるためにさらに信頼性がある（図５におけるようなループ間の相互接続のために）。
【００５３】
既存のネットワークは、実施形態の組み合わせを用いて同様に再構成できることに留意されたい。例えば、既存のネットワークは、図３におけるグラフ３５０の方法で特定の接続を除去し、それによってネットワークの維持管理費用を削減するように再構成することができる。別の例として、既存のネットワークは、信頼性を向上させるために、図４に関して説明される実施形態の方法でループを含むように再構成することができる。別の例として、既存のネットワークは、供給者の冗長性を与えることによって信頼性を向上させるように、図５に関して説明される実施形態の方法で再構成することができる。
【００５４】
別の例として、既存のネットワークは、図３、図４及び図５に関して説明された１つ又は複数の実施形態に従って、同様の方法で拡張することができる。従って、実施形態は、費用効果及び信頼性の高いユーティリティ配給ネットワークの設計を、新しい供給区域が計画されたときのような白紙の状態から支援するだけでなく、既存の供給区域が拡張されたとき又は新しい建物若しくは区画が想定されるときのような、既存のネットワークを改善又は拡張するときにも、支援することができる。
【００５５】
図６を参照すると、この図は、例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークを設計するプロセスのフローチャートを示す。プロセス５００は、図２におけるデータ処理システム２００のようなコンピュータ上で実行することができるコンピュータ使用可能コードを含むソフトウェア・アプリケーションに実装することができる。
【００５６】
プロセス５００は、供給者のセットを受信することによって開始する（ステップ５０２）。プロセス５００は、消費者のセットを受信する（５０４）。
【００５７】
プロセス５００は、図３におけるグラフ３００のように、各消費者を各供給者に接続する（ステップ５０６）。プロセス５００は、図３におけるグラフ３５０のように、最小費用最大フロー・アルゴリズムを用いて、接続の数を減らす（ステップ５０８）。
【００５８】
プロセス５００は、ステップ５０８の簡約化グラフにおいて、ネットワークを形成する１つ又は複数の供給者−消費者クラスタを識別する（ステップ５１０）。プロセス５００は、クラスタのループ・トポロジを計算することによって、１つ又は複数の識別されたクラスタのロバスト性（信頼性）を向上させる（ステップ５１２）。必要に応じて、プロセス５００は、ステップ５１２において、図５に関して説明されたような供給者の冗長性のための接続を計算することによって、クラスタのロバスト性をさらに向上することができる。プロセス５００は、その後終了するか、又は、「Ａ」で示される出口点を介して、図７におけるプロセス６００に合流するように進むことができる。
【００５９】
図７を参照すると、この図は、例示的な実施形態による費用効果及び信頼性の高いユーティリティ配給ネットワークをさらに最適化するプロセスの例のフローチャートを示す。プロセス６００は、図６におけるプロセス５００の実装形態と同様にソフトウェア・アプリケーションに実装することができる。
【００６０】
本明細書に説明されるように、供給者の冗長性を伴って又はそれを伴わずに、費用効果及び信頼性の高いネットワークが計算されると、ネットワークは、さらなる費用削減、供給効率、維持管理の削減、及びその他の有形及び無形の利点のためにさらに最適化することができる。例えば、供給者のセット及び消費者のセットが与えられる場合には、ハミルトン・サイクルの下限によって定められる接続数を有するネットワークを上述のように実現することができる。信頼性の向上のために各消費者への二重の供給経路が必要な場合には、接続数の上限は、ネットワークのグラフのシュタイナー・ツリー長の２倍に設定することができる。
【００６１】
さらに、図３のグラフ３５０のようなクラスタ形成段階の際に、費用削減における１つの考慮事項は、供給者と消費者との間の距離であった。例えば、その考慮事項に加えて、実施形態による最適化プロセスは、図４のループ計算に備えて、クラスタ内の消費者間の距離を閾値より下の限度内に留めることなどによって、消費者間の距離をさらに考慮してクラスタを計算する。
【００６２】
別の例として、既存のネットワークについて、実施形態では、拡張のためのネットワーク計算を最適化するに当たって既存の供給者と消費者との接続費用を考慮する。別の例として、実施形態は、特定の消費者を特定の供給者又は特定の他の消費者と共に配置することなどによって、以前のグラフ簡約化の反復からクラスタ形成を変更し、簡約化グラフを再計算することができる。そのようなクラスタの操作によって、２つ又はそれ以上のクラスタを合体させてより大きいクラスタにすることができ、これにより、特定の状況下で、増大した導線長の節約をもたらすことができる。
【００６３】
別の例として、実施形態は、ループに基づく信頼性の向上と冗長供給者に基づく信頼性の向上との間の費用を比較して、より良好な費用節約のために、両方ではなくいずれか一方を選択する。図７におけるプロセス６００は、実施形態によるこれらの最適化ステップの幾つかを行うプロセスの例である。
【００６４】
プロセス６００は、クラスタを選択することによって開始する（ステップ６０２）。図６におけるプロセス５００のような別のプロセスが、「Ａ」で示される入口点においてプロセス６００に入り、ステップ６０２に進むことができる。
【００６５】
プロセス６００は、クラスタ費用を削減するために、消費者を１つのクラスタから別のクラスタに移動させる（ステップ６０４）。例えば、消費者が１つのネットワークから除去されたときには、そのクラスタ内でその消費者に供給するための導線長を除去することができ、従って、クラスタ費用を削減することができる。そのような移動は、例えばクラスタ内の供給者が閾値供給能力を上回った状態で使用されているときに、有益である。
【００６６】
代替的に、又はステップ６０４と併せて、プロセス６００は、１つのクラスタを別のクラスタと合体させる（ステップ６０６）。２つ又はそれ以上のクラスタを共に合体させることによって、組み合わされたグラフにおける合計導線長を減らし、従って、組み合わされたクラスタの費用を削減することができる。
【００６７】
プロセス６００は、ステップ６０４、６０６又はその両方の結果によって生じたクラスタの費用を再計算する（ステップ６０８）。プロセス６００は、解、すなわちグラフ又は結果として生じたクラスタ若しくはネットワークが、特定の限度を満たすかどうかを判定する（ステップ６１０）。例えば、単一障害の信頼性について上述されたように、解の上限は、クラスタ内の供給者及び消費者のノードを用いて可能となるシュタイナー・ツリーにおけるシュタイナー・ツリー長の２倍に設定することができる。
【００６８】
解の費用が、上述の例における２×シュタイナー・ツリー長によって定められる閾値を超えるときなどのように、解の費用が限度内にない場合（ステップ６１０の「いいえ」の経路）には、プロセス６００は、ステップ６０４、６０６、又はその両方の別の反復を行うために戻る。解の費用が、限度内にある場合（ステップ６１０の「はい」の経路）には、プロセス６００は、ステップ６１２に進む。当然のことながら、例示的な実施形態の範囲内で、あらゆる適切な条件をステップ６１０において特定することができる。
【００６９】
プロセス６００は、本明細書に説明される特定の条件が満たされるまで、ステップ６０４、６０６、６０８及び６１０を反復して行う。そのような反復においては、プロセス６００は、ステップ６０４、６０６又はその両方を行うことによって得られる可能な解を列挙し、ステップ６０８において、列挙された解を評価し、ステップ６０８の計算に基づいて望ましい解を選択し、ステップ６１０において、特定された条件が満たされていない場合には、ステップ６０４、６０６及び６０８を繰り返す。
【００７０】
プロセス６００は、解、すなわち提案される費用効果及び信頼性の高いネットワークを出力する（ステップ６１２）。プロセス６００は、その後終了する。
【００７１】
図におけるフローチャート及びブロック図は、本発明の種々の実施形態によるシステム、方法、及びコンピュータ・プログラム製品の可能な実装形態のアーキテクチャ、機能、及び操作を示す。この点に関して、フローチャート又はブロック図の中の各ブロックは、特定の１つ又は複数の論理機能を実装するための１つ又は複数の実行可能命令を含むコードのモジュール、セグメント、又は一部を表すことができる。幾つかの代替的な実装形態においては、ブロックに記載された機能が図に示される順序通りに行われない場合があることにも留意すべきである。例えば、連続して示される２つのブロックは、関与する機能に応じて、実際には、実質的に同時に実行されることがあり、ブロックが逆順に実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及び、ブロック図及び／又はフローチャート図におけるブロックの組み合わせは、特定の機能若しくは動作を行う専用ハードウェア・ベースのシステムによって、又は、専用ハードウェアとコンピュータ命令との組み合わせによって、実装できることにも留意されたい。
【００７２】
このようにして、費用効果及び信頼性の高いユーティリティ配給ネットワークを生成又は修正するためのコンピュータ実装方法、システム及びコンピュータ・プログラム製品が例示的な実施形態において提供される。本発明の実施形態を用いることによって、ネットワークにおける導線長又は導管長などの費用を削減するように、新しい又は既存のネットワークを設計することができる。特定の実施形態が、費用関数としてノード間の距離に関して説明されたが、そのような費用関数は、例として用いられるに過ぎず、本発明を限定するものとして用いられるものではない。導線又は導管のタイプ、特定の供給者又は接続に関する負荷平衡の費用、クラスタ費用に関する上限又は下限のような、他の費用関数も、本発明の範囲内で、実施形態と併せて同様に用いることができる。
【００７３】
実施形態は、散発する供給者及び将来の成長要求に信頼性をもって対応するネットワークを設計するのに用いることができる。実施形態は、設計時には費用の基準を満たし、さらに、成長時には、ネットワークの設計における成長経路がネットワークの信頼性又はロバスト性を維持することを可能にする、ネットワークを生成する。
【００７４】
当業者であれば分かるように、本発明の態様は、システム、方法、又はコンピュータ・プログラム製品として具体化することができる。従って、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、又は、ソフトウェア及びハードウェアの態様を組み合わせた実施形態の形を取ることができ、本明細書ではその全てを一般的に「回路」、「デバイス」、「モジュール」、又は「システム」と呼ぶことがある。さらにまた、本発明の態様は、コンピュータ可読プログラム・コードが組み込まれた１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体において具体化された、コンピュータ・プログラム製品の形を取ることができる。
【００７５】
１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体のいずれの組み合わせも用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読ストレージ媒体とすることができる。コンピュータ可読ストレージ・デバイスは、例えば、電子、磁気、光学、電磁気、赤外線、若しくは半導体のシステム、装置若しくはデバイス又は上記のいずれかの適切な組み合わせとすることができるが、これらに限定されるものではない。コンピュータ可読ストレージ・デバイスのより具体的な例（非網羅的なリスト）として、１つ又は複数の導線を有する電気接続、携帯可能コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、携帯可能コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光ストレージ・デバイス、磁気ストレージ・デバイス、又は上記のいずれかの適切な組み合わせが挙げられる。本明細書の文脈において、コンピュータ可読ストレージ・デバイスは、命令実行システム、装置、若しくはデバイスによって、又はこれらと共に、用いるためのプログラムを含むか又は格納することができるいずれかの有形のデバイス又は媒体とすることができる。
【００７６】
コンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体上に具体化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は上記のいずれかの好適な組み合わせ含むがこれらに限定されないいずれかの適切な媒体を用いて、伝送することができる。
【００７７】
本発明の態様の操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（商標）、ＳｍａｌｌＴａｌｋ（商標）、Ｃ＋＋などのようなオブジェクト指向型プログラミング言語と、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語とを含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで書くことができる。プログラム・コードは、完全にユーザのコンピュータ上で実行するか、スタンドアロンのソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行するか、部分的にユーザのコンピュータ上で実行し、部分的にリモート・コンピュータ上で実行するか、又は、完全にリモート・コンピュータ若しくはサーバ上で実行することができる。後者の場合には、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続することができ、又は、（例えば、インターネット・サービス・プロバイダを用いてインターネットを通じて）外部コンピュータに接続することもできる。
【００７８】
本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して、本明細書に説明される。フローチャート図及び／又はブロック図の各ブロック、及び、フローチャート図及び／又はブロック図におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実装できることが理解されるであろう。これらのコンピュータ・プログラム命令を１つ又は複数の汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置の１つ又は複数のプロセッサに与えてマシンを生成し、それにより、コンピュータ又は他のプログラム可能データ処理装置の１つ又は複数のプロセッサによって実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装するための手段を生成するようにしてもよい。
【００７９】
また、これらのコンピュータ命令を、特定の方法で機能するように、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイスを向けることができる１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体に格納し、それにより、その１つ又は複数のコンピュータ可読ストレージ・デバイス又はコンピュータ可読媒体に格納された命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装する命令を含む製品を作るようにしてもよい。
【００８０】
また、コンピュータ・プログラム命令を、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイスにロードし、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイス上で一連の操作ステップを行わせて、コンピュータ実装プロセスを生成し、それにより、１つ又は複数のコンピュータ、１つ又は複数の他のプログラム可能データ処理装置、又は、１つ又は複数の他のデバイス上で実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実行するためのプロセスを提供するようにしてもよい。
【００８１】
本明細書において用いられる用語は、特定の実施形態を説明する目的だけのためのものであり、本発明を限定することを意図したものではない。本明細書において用いられる場合、文脈から明らかにそうでないことが示されていない限り、単数形「ａ」「ａｎ」、及び「ｔｈｅ」は、複数形も同様に含むことが意図される。「含む（ｃｏｍｐｒｉｓｅｓ）」及び／又は「含んでいる（ｃｏｍｐｒｉｓｉｎｇ）」という用語は、この明細書において使用される場合、言明された特徴、整数、ステップ、動作、要素、及び／又はコンポーネントの存在を特定するものではあるが、１つ又は複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、及び／又はそれらの群の存在又は追加を排除するものではないことが、さらに理解されるであろう。
【００８２】
特許請求の範囲における全ての「手段又はステップと機能との組合せ（ミーンズ又はステップ・プラス・ファンクション）」要素の対応する構造、材料、行為及び均等物は、その機能を、明確に特許請求されているように他の特許請求された要素と組み合わせて実行するための、いかなる構造、材料又は行為をも含むことが意図される。本発明の説明は、例示及び説明の目的で提示されたものであるが、網羅的であることを意図するものではなく、本発明を開示された形態に限定することを意図するものでもない。本発明の範囲及び趣旨から逸脱することのない多くの変更及び変形が、当業者には明らかである。実施形態は、本発明の原理及び実際の用途を最も良く説明するため、及び、当業者が本発明を種々の変更を有する種々の実施形態について企図される特定の使用に適したものとして理解することを可能にするために、選択及び記載された。
【符号の説明】
【００８３】
１００：電気配給ネットワーク
１１０：導線
１１２：導線／グリッド
２００：データ処理システム
３００、３５０：グラフ
３０２、３０４、３０６、３５２、３５４、３５６、Ｓ１、Ｓ２、Ｓ３：供給者
３１２、３１４、３１６、３１８、３６２、３６４、３６６、３６８、Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６：消費者
４０８、４１０、４１２、４５８、４６０、４６２：接続
４５２、４５４、４５６：ループ
５００、６００：プロセス
【特許請求の範囲】
【請求項１】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのコンピュータ実装方法であって、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化することと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良することであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良することと、
前記供給者のセットを前記消費者のセットに接続する第２のネットワークについての設計を生成することであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成することと、
を含む、コンピュータ実装方法。
【請求項２】
前記接続を前記ネットワークに加えることは、前記クラスタ内の前記消費者のサブセットにおける各消費者に二重の供給経路を与えるループを前記ネットワークに形成することである、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第１のネットワークから第３のネットワークへの第２の接続を加えることによって、前記第１のネットワークをさらに改良することであって、前記第３のネットワークは、前記複数のクラスタ内の第２のクラスタにおける第２の供給者と第２の消費者のサブセットとの間に形成され、前記第２の接続は、前記第１及び第３のネットワークに供給者の冗長性を与えるものである、改良することをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項４】
前記複数のクラスタ内で、消費者を前記第１のクラスタから前記第２のクラスタに移動させることであって、前記移動は前記第１のクラスタの費用を削減するものである、移動させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記第１のクラスタを前記第２のクラスタと合体させることであって、前記合体は前記第１及び第２のクラスタの合計費用を削減するものである、合体させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記第１のクラスタを前記第２のクラスタと合体させることであって、前記合体は前記第１及び第２のクラスタに供給者の冗長性を与えるものである、合体させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記第２のネットワークは、前記所定数の障害後に前記ユーティリティの供給を継続する信頼性を有するものである、請求項１に記載のコンピュータ実装方法。
【請求項８】
前記第２のネットワークの前記費用は、前記第２のネットワークにおけるすべての接続の全長である、請求項１に記載のコンピュータ実装方法。
【請求項９】
前記第２のネットワークの前記費用についての前記下方閾値は、前記消費者のセットにおける各消費者を前記供給者のセットにおける供給者と接続するために形成されるハミルトン・サイクルの全長であり、前記第２のネットワークの前記費用についての前記上方閾値は、前記消費者のセットにおける各消費者を前記供給者のセットにおける供給者と接続するために形成されるシュタイナー・ツリーの全長の倍数である、請求項１に記載のコンピュータ実装方法。
【請求項１０】
前記倍数の値は２であり、前記倍数値２は、単一の障害に対して前記第２のネットワークの信頼性をもたらすものである、請求項９に記載のコンピュータ実装方法。
【請求項１１】
前記ネットワークにおける前記障害は、前記ネットワークにおける接続の障害である、請求項１に記載のコンピュータ実装方法。
【請求項１２】
前記グラフにおける接続が能力制約を有し、前記供給者のセットにおける供給者が閾値供給能力を有し、前記簡約化することは、前記能力制約及び前記閾値供給能力に反しないものである、請求項１に記載のコンピュータ実装方法。
【請求項１３】
前記簡約化することは、前記グラフを簡約化するために最小費用最大フロー・アルゴリズムを用いる、請求項１に記載のコンピュータ実装方法。
【請求項１４】
前記ユーティリティは電気であり、前記ユーティリティのための前記配給ネットワークは電気配給ネットワークである、請求項１に記載のコンピュータ実装方法。
【請求項１５】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのコンピュータ使用可能コードを含むコンピュータ使用可能プログラムであって、前記コンピュータ使用可能コードは、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化するためのコンピュータ使用可能コードと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良するためのコンピュータ使用可能コードであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良するためのコンピュータ使用可能コードと、
前記供給者のセットを前記消費者のセットに接続する第２のネットワークについての設計を生成するためのコンピュータ使用可能コードであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成するためのコンピュータ使用可能コードと、
を含む、コンピュータ使用可能プログラム。
【請求項１６】
前記接続を前記ネットワークに加えることは、前記クラスタ内の前記消費者のサブセットにおける各消費者に二重の供給経路を与えるループを前記ネットワークに形成することである、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１７】
前記第１のネットワークから第３のネットワークへの第２の接続を加えることによって、前記第１のネットワークをさらに改良するためのコンピュータ使用可能コードであって、前記第３のネットワークは、前記複数のクラスタ内の第２のクラスタにおける第２の供給者と第２の消費者のサブセットとの間に形成され、前記第２の接続は、前記第１及び第３のネットワークに供給者の冗長性を与えるものである、さらに改良するためのコンピュータ使用可能コードをさらに含む、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１８】
前記コンピュータ使用可能コードは、データ処理システムにおけるコンピュータ可読ストレージ媒体内に格納され、前記コンピュータ使用可能コードは、遠隔データ処理システムからネットワーク上で伝送される、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１９】
前記コンピュータ使用可能コードは、サーバ・データ処理システムにおけるコンピュータ可読ストレージ媒体内に格納され、前記コンピュータ使用可能コードは、遠隔データ処理システムと関連付けられたコンピュータ可読ストレージ媒体において用いるために、ネットワーク上で前記遠隔データ処理システムにダウンロードされる、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項２０】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのデータ処理システムであって、
コンピュータ使用可能プログラム・コードを格納する、ストレージ媒体を含むストレージ・デバイスと、
前記コンピュータ使用可能プログラム・コードを実行するプロセッサと、
を含み、前記コンピュータ使用可能プログラム・コードは、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化するためのコンピュータ使用可能コードと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良するためのコンピュータ使用可能コードであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良するためのコンピュータ使用可能コードと、
前記供給者のセットを前記消費者のセットと接続する第２のネットワークについての設計を生成するためのコンピュータ使用可能コードであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成するためのコンピュータ使用可能コードと、
を含む、
データ処理システム。
【請求項１】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのコンピュータ実装方法であって、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化することと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良することであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良することと、
前記供給者のセットを前記消費者のセットに接続する第２のネットワークについての設計を生成することであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成することと、
を含む、コンピュータ実装方法。
【請求項２】
前記接続を前記ネットワークに加えることは、前記クラスタ内の前記消費者のサブセットにおける各消費者に二重の供給経路を与えるループを前記ネットワークに形成することである、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第１のネットワークから第３のネットワークへの第２の接続を加えることによって、前記第１のネットワークをさらに改良することであって、前記第３のネットワークは、前記複数のクラスタ内の第２のクラスタにおける第２の供給者と第２の消費者のサブセットとの間に形成され、前記第２の接続は、前記第１及び第３のネットワークに供給者の冗長性を与えるものである、改良することをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項４】
前記複数のクラスタ内で、消費者を前記第１のクラスタから前記第２のクラスタに移動させることであって、前記移動は前記第１のクラスタの費用を削減するものである、移動させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記第１のクラスタを前記第２のクラスタと合体させることであって、前記合体は前記第１及び第２のクラスタの合計費用を削減するものである、合体させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記第１のクラスタを前記第２のクラスタと合体させることであって、前記合体は前記第１及び第２のクラスタに供給者の冗長性を与えるものである、合体させることをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記第２のネットワークは、前記所定数の障害後に前記ユーティリティの供給を継続する信頼性を有するものである、請求項１に記載のコンピュータ実装方法。
【請求項８】
前記第２のネットワークの前記費用は、前記第２のネットワークにおけるすべての接続の全長である、請求項１に記載のコンピュータ実装方法。
【請求項９】
前記第２のネットワークの前記費用についての前記下方閾値は、前記消費者のセットにおける各消費者を前記供給者のセットにおける供給者と接続するために形成されるハミルトン・サイクルの全長であり、前記第２のネットワークの前記費用についての前記上方閾値は、前記消費者のセットにおける各消費者を前記供給者のセットにおける供給者と接続するために形成されるシュタイナー・ツリーの全長の倍数である、請求項１に記載のコンピュータ実装方法。
【請求項１０】
前記倍数の値は２であり、前記倍数値２は、単一の障害に対して前記第２のネットワークの信頼性をもたらすものである、請求項９に記載のコンピュータ実装方法。
【請求項１１】
前記ネットワークにおける前記障害は、前記ネットワークにおける接続の障害である、請求項１に記載のコンピュータ実装方法。
【請求項１２】
前記グラフにおける接続が能力制約を有し、前記供給者のセットにおける供給者が閾値供給能力を有し、前記簡約化することは、前記能力制約及び前記閾値供給能力に反しないものである、請求項１に記載のコンピュータ実装方法。
【請求項１３】
前記簡約化することは、前記グラフを簡約化するために最小費用最大フロー・アルゴリズムを用いる、請求項１に記載のコンピュータ実装方法。
【請求項１４】
前記ユーティリティは電気であり、前記ユーティリティのための前記配給ネットワークは電気配給ネットワークである、請求項１に記載のコンピュータ実装方法。
【請求項１５】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのコンピュータ使用可能コードを含むコンピュータ使用可能プログラムであって、前記コンピュータ使用可能コードは、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化するためのコンピュータ使用可能コードと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良するためのコンピュータ使用可能コードであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良するためのコンピュータ使用可能コードと、
前記供給者のセットを前記消費者のセットに接続する第２のネットワークについての設計を生成するためのコンピュータ使用可能コードであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成するためのコンピュータ使用可能コードと、
を含む、コンピュータ使用可能プログラム。
【請求項１６】
前記接続を前記ネットワークに加えることは、前記クラスタ内の前記消費者のサブセットにおける各消費者に二重の供給経路を与えるループを前記ネットワークに形成することである、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１７】
前記第１のネットワークから第３のネットワークへの第２の接続を加えることによって、前記第１のネットワークをさらに改良するためのコンピュータ使用可能コードであって、前記第３のネットワークは、前記複数のクラスタ内の第２のクラスタにおける第２の供給者と第２の消費者のサブセットとの間に形成され、前記第２の接続は、前記第１及び第３のネットワークに供給者の冗長性を与えるものである、さらに改良するためのコンピュータ使用可能コードをさらに含む、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１８】
前記コンピュータ使用可能コードは、データ処理システムにおけるコンピュータ可読ストレージ媒体内に格納され、前記コンピュータ使用可能コードは、遠隔データ処理システムからネットワーク上で伝送される、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項１９】
前記コンピュータ使用可能コードは、サーバ・データ処理システムにおけるコンピュータ可読ストレージ媒体内に格納され、前記コンピュータ使用可能コードは、遠隔データ処理システムと関連付けられたコンピュータ可読ストレージ媒体において用いるために、ネットワーク上で前記遠隔データ処理システムにダウンロードされる、請求項１５に記載のコンピュータ使用可能プログラム。
【請求項２０】
費用効果及び信頼性の高いユーティリティの配給ネットワーク（ネットワーク）を設計するためのデータ処理システムであって、
コンピュータ使用可能プログラム・コードを格納する、ストレージ媒体を含むストレージ・デバイスと、
前記コンピュータ使用可能プログラム・コードを実行するプロセッサと、
を含み、前記コンピュータ使用可能プログラム・コードは、
複数のクラスタを形成するように、前記ユーティリティの消費者のセットを前記ユーティリティの供給者のセットと接続するグラフを簡約化するためのコンピュータ使用可能コードと、
前記複数のクラスタ内の第１のクラスタにおける供給者と消費者のサブセットとの間の第１のネットワークを改良するためのコンピュータ使用可能コードであって、前記改良することは、前記第１のネットワークにおける所定数の障害後に前記消費者のサブセットへの前記ユーティリティの供給を継続するように、第１の接続を前記第１のネットワークに加えることである、改良するためのコンピュータ使用可能コードと、
前記供給者のセットを前記消費者のセットと接続する第２のネットワークについての設計を生成するためのコンピュータ使用可能コードであって、前記第２のネットワークは前記改良後の前記第１のネットワークを含んでおり、前記第２のネットワークは下方閾値から上方閾値までの範囲内の費用を有するものである、生成するためのコンピュータ使用可能コードと、
を含む、
データ処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−８９２３２（Ｐ２０１３−８９２３２Ａ）
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願番号】特願２０１２−２０６０２５（Ｐ２０１２−２０６０２５）
【出願日】平成２４年９月１９日（２０１２．９．１９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願日】平成２４年９月１９日（２０１２．９．１９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
[ Back to top ]