ネットワーク設計装置及び方法並びにネットワーク設計プログラム
【課題】 数理計画法における問題を効率的に解くことで、ネットワークへの配置用品を決定する。
【解決手段】 ネットワーク設計装置１００は、ネットワーク内の線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す情報、伝送装置の候補の夫々の配置コスト、及び線形区間における所定の区間における伝送装置の配置コストの和の夫々を取得する情報取得手段１２１と、線形区間に配置する伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段１２２と、数理計画法における問題を、伝送装置の候補のうち少なくとも一つについて解き、線形区間に配置する伝送装置の候補の組み合わせを決定する装置選択手段１２３とを備える。装置選択手段は、伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に数理計画法における問題を解く伝送装置の候補を決定する。
【解決手段】 ネットワーク設計装置１００は、ネットワーク内の線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す情報、伝送装置の候補の夫々の配置コスト、及び線形区間における所定の区間における伝送装置の配置コストの和の夫々を取得する情報取得手段１２１と、線形区間に配置する伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段１２２と、数理計画法における問題を、伝送装置の候補のうち少なくとも一つについて解き、線形区間に配置する伝送装置の候補の組み合わせを決定する装置選択手段１２３とを備える。装置選択手段は、伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に数理計画法における問題を解く伝送装置の候補を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークへの用品配置を決定するためのネットワーク設計装置及び方法の技術分野に関する。
【背景技術】
【０００２】
移動通信システム等において利用されるこの種のネットワークでは、ネットワーク上のトラヒックを処理するために最低限必要とされる装置構成がある。ネットワーク上の装置構成とは、例えば、信号の中継局など、所謂信号の伝送に係る装置である。
【０００３】
一般に、ネットワーク上に配置されるこれらの信号伝送装置のコストと、これらの信号伝送装置上を経由する信号の伝送品質とはトレードオフの関係にある。すなわちコストの高い信号伝送装置が配置されると信号の伝送品質が向上する。これによりネットワーク上の信号の伝送路上において必要とされる信号伝送装置の数が減少する。他方で、コストが低い信号伝送装置の配置数を増やすと全体としての装置の配置数が増加する。
【０００４】
また、ネットワークの性質上、上述したネットワーク上のトラヒックを処理するために求められるコストを大きく下回るネットワークは許容されない。
【０００５】
上述した性質を考慮して、ネットワークの設計においては、トラヒックより決定される目標コストに対して、信号伝送装置のコストの総和、言い換えればネットワークを敷設する際の所要コストを可能な限り近付けることが好ましい。このようなネットワークの設計のために、整数計画法を用いてネットワークを設計する手法が提案されている。
【０００６】
下記に示される先行技術文献には、基板に部品を装着する際の割り振り方法を混合整数計画問題としてモデル化し、該問題を解くことにより割り振り方法を決定する方法について説明されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−３８０８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ネットワークの設計においても、数理計画法における整数計画問題又は混合整数計画問題等の問題を用いて、ネットワーク上に設置される装置のコストの総和と目標コストとの差分が最小となる配置を決定することで、好適なネットワーク設計が可能となる。
【０００９】
しかしながら、数理計画法における問題を解くことによるネットワーク上の装置の配置決定は、装置数が増えることにより解法に係る処理量が増大するという技術的な問題がある。
【００１０】
例えば、あるネットワークについて、現在考えられている配置から装置を一つ変更することを考える場合、装置交換後の目的関数を再計算することが要求される。また、かかる変更がネットワーク設計において適しているか否かを判定するためには、変更候補の装置全てについて目的関数を計算し直す必要がある。
【００１１】
本発明は、上述した問題点に鑑み為されたものであり、数理計画法における問題を用いるネットワークの設計方法において、要求される処理量を低減し得るネットワークの設計装置及び方法を提供することを課題とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、開示のネットワーク設計装置は、情報取得手段と、問題生成手段と、装置選択手段とを備える。
【００１３】
情報取得手段は、線形区間を含むネットワークにおいて、該線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、伝送装置の候補の夫々の配置コスト、及び線形区間における一又は複数の配置点を含む所定の区間における伝送装置の配置コストの和である目標コストの夫々を取得する。
【００１４】
問題生成手段は、装置候補情報、配置コスト、及び目標コストに基づいて、線形区間に配置する伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する。
【００１５】
装置選択手段は、生成された数理計画法における問題を、伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、線形区間に配置する伝送装置の候補の組み合わせを決定する。尚、装置選択手段は、伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に数理計画法における問題を解く伝送装置の候補を決定する。
【００１６】
上記課題を解決するために、開示のネットワーク設計方法は、情報取得工程と、問題生成工程と、装置選択工程とを備える。情報取得工程では、上述した情報取得手段と同様の処理が実施される。問題生成工程では、上述した問題生成手段と同様の処理が実施される。装置選択工程では、上述した装置選択手段と同様の処理が実施される。
【発明の効果】
【００１７】
開示のネットワーク設計装置によれば、配置される伝送装置の組み合わせの候補について算出した被約費用に基づいて、次に目的関数を算出するために数理計画法における問題を解くための伝送装置の組み合わせの候補が選択される。このため、好適に目的関数の改善の可能性がある伝送装置の組み合わせについて、目的関数の検証が可能となるため、計算量を低減することが出来る。
【図面の簡単な説明】
【００１８】
【図１】設計対象となるネットワークを示す図である。
【図２】ネットワーク設計装置のハードウェア構成及び機能部構成を示す図である。
【図３】ネットワーク設計装置に入力されるネットワークについての情報を示す図である。
【図４】ネットワーク設計装置の動作例における動作の流れを示すフローチャートである。
【図５】動作例における配置候補の用品について、コスト及び目標コストを示す図である。
【図６】被約費用の算出の具体例を示す図である。
【図７】目的関数費用の算出の具体例を示す図である。
【図８】ネットワーク設計装置の動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【図９】ネットワーク設計装置の第１変形動作例における動作の流れを示すフローチャートである。
【図１０】ネットワーク設計装置の第１変形動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【図１１】ネットワーク設計装置の第２変形動作例における動作の流れを示すフローチャートである。
【図１２】ネットワーク設計装置の第２変形動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００２０】
（１）構成例
図１に、開示のネットワーク設計装置による設計の対象となるネットワークの一例を示す。図１に示されるネットワーク２００は、移動通信システム等を構成するネットワークの一部を示すものである。ネットワーク２００では、信号分岐装置又は信号中継装置等のノード装置１乃至６が配置される線形区間について示している。尚、ネットワーク２００は、所謂メッシュ型のネットワークにおける或る線形区間について示しているが、例えば、ネットワーク２００はその他の態様のネットワークの一部であってもよい。
【００２１】
線形区間は２つ以上のノード装置が縦続接続されることにより形成される区間である。例えば、図１の例では、ノード装置１の出力がノード装置２の入力に、ノード装置２の出力がノード装置３の入力に、ノード装置３の出力がノード装置４の入力に、ノード装置４の出力がノード装置５の入力に、ノード装置５の出力がノード装置６の入力に、夫々接続されている。尚、接続端子の向きは逆向きであっても、双方向であってもよい。また、線形区間においては、ノード装置間の接続は、物理的に直線である必要はなく、曲線的に接続されていてもよい。
【００２２】
開示のネットワーク設計装置は、ネットワーク２００における線形区間において、該線形区間に配置されるノード装置の組み合わせを決定する。以降、ノード装置について「用品」と記載し、ノード装置の配置の組み合わせについて「用品配置」と記載して説明することがある。
【００２３】
ネットワーク２００上に配置される用品は、夫々トラヒックを処理するためのコストを有している。コストの高い用品が配置されると、ネットワーク２００における該用品を経由する信号の伝送品質が大きく向上する。他方で、コストの低い用品が配置されると、伝送品質の大きな向上は生じない。
【００２４】
ネットワーク２００上では、所定の区間ごとにトラヒック処理のための目標コストが設定される。かかる目標コストは、ネットワーク２００上において、シミュレーションや統計処理等により得られる予測トラヒック量を処理するために必要とされるコストである。区間ごとの該目標コストに対して、多少の変動幅は許容されるものの、該区間に配置される用品のコスト総和と目標コストとの差分が可能な限り近付くよう、ネットワーク２００が設計されることが好ましい。
【００２５】
以下に説明するように、ネットワーク設計装置１００は、ネットワーク２００において区間ごとに設定される目標コストに対して、より近いコスト総和を有する用品配置の決定を行う。
【００２６】
図２を参照して、ネットワーク設計装置１００の構成について説明する。図２は、ネットワーク設計装置１００の基本的な構成を示すブロック図である。
【００２７】
図２に示されるように、ネットワーク設計装置１００は、入出力インタフェース１１０と、ＣＰＵ１２０と、メモリ１３０とを備える。
【００２８】
入出力インタフェース１１０は、例えば、外部のネットワークノード装置や、コンピュータ等との間でデータの入出力を行うためのインタフェースであって、入力部１１１及び出力部１１２の機能部を有する。
【００２９】
入力部１１１は、外部からのデータを入力するための機能部であって、設計対象となるネットワークトポロジー情報、該ネットワーク２００におけるトラヒック情報（言い換えれば、ネットワーク上の各区間における配置用品の目標コスト）及び該ネットワーク２００上に配置される用品についてのデータ等の入力を受け、ＣＰＵ１２０に出力する。用品についてのデータとは、例えば、ネットワークトポロジーにおける或る区間における配置候補となり得る各用品についてコストを示したものである。
【００３０】
出力部１１２は、ＣＰＵ１２０において算出された用品配置情報を外部に出力する。
【００３１】
ＣＰＵ１２０は、ネットワーク設計装置１００における各部の動作の制御を行うための演算装置であり、また入力された情報を処理することで、用品配置情報の算出を行う。ＣＰＵ１２０は、用品候補選択部１２１、問題生成部１２２及び用品選択部１２３の機能部を有する。
【００３２】
用品候補選択部１２１は、入力部１１１より入力される用品のデータに基づいて、ネットワーク２００上の用品配置情報の算出を行うための用品候補データの生成を行う。また、用品候補選択部１２１は、生成した用品候補データについて、メモリ１３０内部にデータベースとして格納してもよい。
【００３３】
問題生成部１２２は、入力部１１１より入力されるネットワークトポロジー情報及びトラヒック情報に基づいて、用品配置情報の算出を行うための数理計画法における整数計画問題又は混合整数計画問題等の問題の生成を行う。また、問題生成部１２２は、入力されるネットワークトポロジー情報及びトラヒック情報、並びに生成した数理計画法における問題をメモリ１３０内部に格納してもよい。
【００３４】
用品選択部１２３は、用品候補選択部１２１において生成される用品候補データと、問題生成部１２２において生成される数理計画法における問題とに基づいて、ネットワーク２００上への用品配置情報の算出を行う。用品選択部１２３は、例えば、数理計画法における問題を、用品候補データについて解くことによって、用品配置情報の算出を行う。
【００３５】
メモリ１３０は、ＣＰＵ１２０を動作させるためのソフトウェアや、ネットワーク設計装置１００の動作の上での各種情報等を格納するための記憶装置である。
【００３６】
図３に、問題生成部１２２が生成する数理計画法における問題をネットワークトポロジー図として示す。図３は、図１に示されるネットワーク２００における線形区間についてネットワークトポロジー図として示すものである。
【００３７】
図３に示されるように、問題生成部１２２は、入力部１１１より入力されるネットワークトポロジー情報及びトラヒック情報に基づいて、用品が配置される区間を指定するネットワークトポロジー図を生成する。図３の例では、問題生成部１２２は、図１のネットワーク２００をノード装置１が配置される区間１’と、ノード装置２が配置される区間２’と、ノード装置３が配置される区間３’と、ノード装置４が配置される区間４’と、ノード装置５が配置される区間５’と、ノード装置６が配置される区間６’とに分割する。
【００３８】
また、問題生成部１２２は、トラヒック情報に基づいて、ネットワークトポロジーにおける区間毎の目標コストを設定する。図３の例では、区間１’、２’、３’における用品コストの総和が１５、区間３’、４’、５’における用品コストの総和が２０、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０に夫々設定される。
【００３９】
用品候補選択部１２１は、用品候補データを参照して、区間毎に配置される用品の識別番号とコストとを用品選択部１２３に通知する。図３の例では、区間１’に配置される用品の候補としてｘ１（１）、ｘ２（２）及びｘ３（３）が挙げられている。区間２’に配置される用品の候補としてｘ４（７）、ｘ５（８）及びｘ６（９）が挙げられている。区間３’に配置される用品の候補としてｘ７（４）、ｘ８（５）及びｘ９（６）が挙げられている。区間４’に配置される用品の候補としてｘ１０（１１）、ｘ１１（１２）及びｘ１２（１３）が挙げられている。区間５’に配置される用品の候補としてｘ１３（２）及びｘ１４（３）が挙げられている。区間６’に配置される用品の候補としてｘ１５（９）、ｘ１６（１０）、ｘ１７（１１）及びｘ１８（１２）が挙げられている。尚、カッコ内の数字は各用品のコストを示す。
【００４０】
問題生成部１２２は、用品候補選択部１２１から入力される区間毎の配置用品とそのコスト、並びにネットワークトポロジーに示されるネットワーク２００上の区間及び目標コストを参照し、下記の式（１）乃至（３）に示される整数計画問題を生成する。
【００４１】
上述した整数計画問題又は混合整数計画問題を解くことにより、適切な用品配置の決定を行う数理計画法では、上述したように区間毎に設定される配置用品の候補より、複数の区間を跨いで設定される目標コスト等に基づいて、各区間に配置される用品が決定される。また、図３に示されるネットワークトポロジーの例においては、各区間に一つずつ用品が配置される。このように、区間毎に配置される用品の数、及び目標コストを条件として、問題生成部１２２は、用品の配置を決定するための制約式を生成する。
【００４２】
用品選択部１２３は、このような制約式により示される条件の下、数理計画法に基づいて算出する対象である目的関数（objective function）を最適な値（例えば、最大値又は最小値）となるよう整数計画問題を解くことで、好適な用品の配置を決定する。
【００４３】
以下に示す例では、用品選択部１２３は、ネットワーク２００の区間毎に配置される用品の目標コストと配置される用品のコストの和との差分を目的関数に設定する。そして、ネットワーク２００の区間毎に配置される用品のコストの和を可能な限り目標コストに近付けるよう、用品選択部１２３は、このような目的関数を制約式により示される条件下で最小とする最適解を算出することで用品の配置を決定する。
【００４４】
（２）動作例
以下、本実施例で用いる整数計画問題及びその解法について説明する。
【００４５】
問題生成部１２２は、上述のように生成されたネットワークトポロジーに基づいて、数理計画法における問題を生成する。
【００４６】
問題生成部１２２は、例えば、入力情報として、ネットワーク２００における区間情報及びトラフィック情報、各区間において配置可能な用品の候補、各用品のコスト、並びに各トラフィックに基づく所定の区間毎の目標コスト等の入力を受ける。そして、問題生成部１２２は、ネットワーク２００における各区間において、トラフィックに基づいて決定される目標コストに対して、配置される用品のコストの総和が最適となるよう、各区間に配置可能な用品候補から夫々１つの用品を選択することを目標とする問題を生成する。
【００４７】
数理計画法における問題は、例えば、整数計画問題又は混合整数計画問題に係る目的関数と制約式との集合となる。以下に示される式（１）式は、問題生成部１２２により生成される数理計画法における問題に基づき、上述した用品選択部１２３が解く整数計画問題における目的関数を表現する数式である。
【００４８】
【数１】
式（１）において、ｐｅ（ｔ）及びｎｅ（ｔ）は、配置される用品のコストの和と、目標コストとの差分、つまり誤差を示す成分である。尚、ｐｅ（ｔ）は、正の誤差について、ｎｅ（ｔ）は負の誤差について夫々示す成分であり、ｐｅ（ｔ）＋ｎｅ（ｔ）により誤差の絶対量を示す。変数ｔは、ネットワーク２００上におけるトラヒックが生じる所定の経路（トラヒック経路）を示す。関数ｗ（ｔ）は、或る経路ｔにおける配置用品のコストと目標コストとの誤差に重みづけを行うための係数である。かかる係数を設定することにより、ネットワーク２００における特定の箇所をトラヒック毎に決定し、優先的に用品の配置決定を行うことが出来る。重みづけ係数ｗ（ｔ）は、用品候補選択部１２１、問題生成部１２２又は用品交換部１２３等において設定される。尚、その他の態様で、用品配置の決定に係る優先度を別途指定してもよい。
【００４９】
式（１）に示した目的関数に係る制約条件を示す制約式を以下の式（２）及び式（３）に示す。
【００５０】
【数２】
【００５１】
【数３】
式（２）は、ネットワーク２００に配置される用品について、各区間（つまり、図３における区間１’乃至６’のいずれか）の用品の候補より１つずつ選択するという条件を示す制約式である。式（２）において、ｘ（ｃ）は、区間（segment）ｓにおける用品ｃについての存在又は非存在を示す関数である。ｘ（ｃ）＝１である場合、用品ｃが配置され、ｘ（ｃ）＝０である場合、用品ｃが配置されていないことを夫々示す。つまり、式（２）によれば、或る区間ｓにおいて配置される用品は、該区間に配置される用品候補（ｃａｎｄｉｄａｔｅ ｃ ｏｎ ｓ）のうち、１つが選択されることを示している。
【００５２】
式（３）は、ネットワーク２００に配置される用品について、コストの総和と、所定の１又は複数の区間毎に設定される目標コストとの誤差を決定する制約式である。式（３）において、ｉｄｅａｌ＿ｃｏｓｔ（ｔ）は、所定の経路ｔについて算出された目標コストを示す。ｃｏｓｔ（ｃ）は、所定の経路ｔ中の区間ｃに配置される用品のコストを示す。用品のコストｃｏｓｔ（ｃ）と、配置される用品ｘ（ｃ）との積ｃｏｓｔ（ｃ）・ｘ（ｃ）は、所定のトラヒック経路ｔにおける区間ｃに配置される用品のコストを示す。また、トラヒック経路ｔ中の区間ｃのコストの総和は、Σｃｏｓｔ（ｃ）・ｘ（ｃ）により表される。
従って、式（３）によれば、所定のトラヒック経路ｔにおける各区間に配置される用品のコストの総和と該トラヒック経路における目標コストとの差分が誤差成分ｐｅ（ｔ）＋ｎｅ（ｔ）により表される。
【００５３】
上記のように設定された整数計画問題について、用品選択部１２３は、最適解の算出を行う。以下に、用品選択部１２３が行う算出処理の流れについて、図４を参照して説明する。
【００５４】
図４は、最適解の算出処理に係る用品選択部１２３の動作の流れを示すフローチャートである。図５は、図３に示されるネットワーク２００における区間毎の用品候補のコストと、被約費用（Reduced Cost）とを含むデータを示すテーブルである。
【００５５】
図５には、図３に示されるように、区間１’、２’、３’における用品コストの総和が１５、区間３’、４’、５’における用品コストの総和が２０、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０に夫々設定される場合についての用品の配置に係るデータが示される。以降の説明においては、区間毎の目標コストについて、区間１’、２’、３’における用品コストの総和が１５となる条件を条件１と記載して説明する。また、区間３’、４’、５’における用品コストの総和が２０となる条件を条件２と記載して説明する。また、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０となる条件を条件３と記載して説明する。
【００５６】
図５のテーブルの第１行には、各用品についての用品番号ｘｎ及び誤差成分が記載される。誤差成分の内、ｎｅ１及びｐｅ１は、条件１における誤差成分、ｎｅ２及びｐｅ２は、条件２における誤差成分、ｎｅ３及びｐｅ３は、条件３における誤差成分を夫々示す。
【００５７】
図５のテーブル第２行には、各用品及び誤差成分についての存在又は非存在を示すベクトルｃが記述される。
【００５８】
図５のテーブル第３行から第１２行までには、ネットワーク２００に対する各用品の配置状態及びコスト、並びに誤差成分の状態を示す行列Ａが記述される。
【００５９】
図５のテーブル第１３行には、各用品候補ｘｎについて、夫々の被約費用ｃ＾が記述される。被約費用ｃ＾は、例えば、行列Ａについて、条件１、条件２又は条件３について連立方程式を生成することで算出可能である。
【００６０】
以下の説明では、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置されたネットワーク２００において、より効率的な（つまり、目標コストと配置される用品コストの総和との誤差が最小となる）用品の配置を決定する際の動作について説明する。
【００６１】
図４に示されるように、先ず用品選択部１２３は、上述のように生成された整数計画問題における目的関数及び制約式に基づいて、各区間の用品の候補についての被約費用の算出を行う（ステップＳ１００）。
【００６２】
図６を参照して、被約費用の具体的な算出動作について説明する。
【００６３】
被約費用ｃ＾は、以下に示す式（４）により表される。
【００６４】
【数４】
ここに、Ｎは、非基底成分の（言い換えれば、選択されていない）変数（つまり、各用品ｘｎ並びに誤差成分ｐｅ及びｎｅを含む変数）に対応する行列である。具体的には、図５に示す行列Ａにおいて、非基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列の集合が行列Ｎにあたる。また、ｃＮは、行列ｃの非基底成分を示す行列である。具体的には、図５に示す行列ｃにおいて、非基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列（値）の集合がｃＮにあたる。尚、πは以下の式（５）により表される。
【００６５】
【数５】
ここに、Ｂは基底成分の（言い換えれば、ネットワーク２００に仮に配置されている）用品候補を示す行列である。具体的には、図５に示す行列Ａにおいて、基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列の集合が行列Ｂにあたる。また、ｃＢは、行列ｃの基底成分を示す行列である。具体的には、図５に示す行列ｃにおいて、基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列（値）の集合がｃＢにあたる。図３及び図５の例に基づく行列Ｂ及びｃＢは、図６（１）に示されるものとなる。また、行列Ｂの逆行列Ｂ−１は、図６（２）に示されるものとなる。
【００６６】
尚、π＝ｃＢＢ−１は、図６（３）に示されるものとなる。
【００６７】
以上、示した式を用いることで、現在ネットワーク２００に配置されていない用品（つまり、非基底成分Ｎ）の被約費用ｃ＾は、以下の式（６）より求められる。
【００６８】
【数６】
尚、図５に示される例では、ｃＢは、誤差成分以外の用品については０となるため、被約費用ｃ＾＝−ｃＢＢ−１Ｎとなる。なお、ここでは誤差成分に関する被約費用は省略している。
【００６９】
目的関数を最小化することを目的とする、所謂最小化問題においては、被約費用ｃ＾成分が負であり、且つ絶対量の大きい（言い換えれば、最小の）被基底変数を新たに基底変数として、現在基底変数に選択されている変数と交換することで、目的関数が改善される可能性がある。用品選択部１２３は、算出された被約費用を参照して、被約費用が負である配置候補の用品が存在するか否かを確認する（ステップＳ１０１）。
【００７０】
被約費用が負である配置候補の用品が存在する場合（ステップＳ１０１：Ｙｅｓ）、用品選択部１２３は、図５のテーブルのように示される配置用品の候補から、被約費用が負であり、且つ最小のものを選択する（ステップＳ１０２）。用品選択部１２３は、現在ネットワーク２００に配置される用品を、該選択された配置候補の用品に配置を変更した場合の目的関数の算出を行う（ステップＳ１０３）。
【００７１】
目的関数の算出の態様について、図７に例を示して説明する。初回の算出時には、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態であるため、図７は、これらの用品を配置した際の目的関数の算出の態様について示している。このように配置される用品の組み合わせによれば、条件１に該当する区間１’、２’、３’におけるコスト総和は１＋７＋４＝１２となり、目標コスト１５とのコスト差分は３となる。また、条件２に該当する区間３’、４’、５’におけるコスト総和は４＋１１＋２＝１７となり、目標コスト２０とのコスト差分は３となる。また、条件３に該当する区間１’、２’、３’、４’、５’、６’におけるコスト総和は１＋７＋４＋１１＋２＋９＝３４となり、目標コスト４０とのコスト差分は６となる。以上のことから、条件１乃至３を同時に満たすよう設定される目的関数は、コスト差分の和３＋３＋６＝１２となる。
【００７２】
用品選択部１２３は、用品の配置変更後の目的関数と、変更前の目的関数とを比較して、変更前に比べて目的関数が改善しているか（つまり、変更前より値が小さくなっているか）否かの判定を行う（ステップＳ１０４）。
【００７３】
用品選択部１２３は、用品の配置の変更により、目的関数が改善されると判断される場合（ステップＳ１０５：Ｙｅｓ）、該選択された配置候補の用品を配置用品として設定する（ステップＳ１０６）。その後、用品選択部１２３は、選択された配置用品について被約費用の算出を行い、ステップＳ１００乃至Ｓ１０５の処理を繰り返す。
【００７４】
他方で、用品の配置の変更により、目的関数が改善されない、又は悪化すると判断される場合（ステップＳ１０５：Ｎｏ）、該選択された配置候補の用品を配置用品としては不適であると判断する（ステップＳ１０７）。その後、用品選択部１２３は、ステップＳ１００において算出された被約費用のうち、不適とされた配置候補の用品を除いて、被約費用が負である配置候補の用品が存在するか否かの確認を行い、ステップＳ１０１乃至Ｓ１０５の処理を繰り返す。
【００７５】
用品選択部１２３は、目的関数が改善しない、又は悪化することから不適と判断された用品を除いて、被約費用が負である用品が存在しない場合（ステップＳ１０１：Ｎｏ）、現在設定される配置用品の組み合わせを、配置用品情報として決定する（ステップＳ１０８）。
【００７６】
上述した動作の流れにおける用品の選択及び目的関数の算出の態様について、図８を参照して説明する。図８は、図３及び図５に示される例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。なお、以降の例では、記載を省略するが、各区間の誤差成分ｐｅ、ｎｅのうち、いずれか一方の誤差量が正となる成分が基底として選択されているものとする。また、誤差量が０の場合はｎｅが基底として選択される。
【００７７】
図８（１）に示されるように、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態のネットワーク２００において、用品選択部１２３は、配置候補として、被約費用が負であり、且つ絶対量が最大の用品を選択する。用品選択部１２３は、図８（１）の例では、被約費用が−６の用品ｘ９を配置候補として選択する。次に、用品選択部１２３は、用品ｘ９が配置される区間３’において、現在仮に配置される用品ｘ７をｘ９に変更した場合について、目的関数の算出を行う。
【００７８】
用品選択部１２３は、図５に示されるものと同様の手順で、用品ｘ１、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置される場合の目的関数の算出を行う。図８（２）に示されるように、変更後の目的関数は６となり、変更前と比較して改善が見られる。このため、用品選択部１２３は、区間３’において配置される用品をｘ９に決定する。尚、配置される用品をｘ７からｘ９に変更することにより、各用品の被約費用が変化する。用品選択部１２３は、ネットワーク２００における他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。
【００７９】
用品ｘ１、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、次の配置候補として用品ｘ３、ｘ６及びｘ１２を検出する。以下の説明では、便宜上、用品ｘ３、ｘ６、ｘ１２のように順番で配置変更後の目的関数の算出と判定を行うものとする。
【００８０】
用品ｘ３が配置される区間１’において、用品ｘ１を用品ｘ３に変更する場合、目的関数は、図８（３）に示されるように、４となり、更に改善が見られる。このため、用品選択部１２３は、区間１’において配置される用品をｘ３に決定する。
【００８１】
用品ｘ３、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。用品選択部１２３は、図８（３）に示されるように算出される用品の被約費用から、次の配置候補として、被約費用が−４である用品ｘ１２を選択する。用品ｘ１２が配置される区間４’において、用品ｘ１０を用品ｘ１２に変更する場合、目的関数は、図８（４）に示されるように、２となり、更に改善が見られる。このため、用品選択部１２３は、区間４’において配置される用品をｘ１２に決定する。
【００８２】
用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。用品選択部１２３は、図８（４）に示されるように算出される用品の被約費用から、次の配置候補として、被約費用が−３である用品ｘ１８を選択する。用品ｘ１８が配置される区間６’において、用品ｘ１５を用品ｘ１８に変更する場合、目的関数は、図８（５）に示されるように、５となり、却って悪化する。このため、用品選択部１２３は、区間６’において配置される用品がｘ１８では不適であると判断する。用品選択部１２３は、図８（５）に示される用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１８が配置された状態のネットワーク２００において、被約費用が負であり最も小さい用品ｘ１５を配置候補として選択し、目的関数の算出を行う。
【００８３】
用品ｘ１８を用品ｘ１５に交換することで、図８（６）に示されるように、目的関数及び各用品の被約費用は、図８（４）と同様の状態となる。用品選択部１２３は、不適であると判断した用品ｘ１８を除いて、被約費用が次に小さい（且つ、負である）用品である配置候補として、用品ｘ７及び用品ｘ１７を選択する。尚、配置される用品を用品ｘ７及び用品ｘ１７に変更する場合、目的関数はいずれも４となり悪化するため、用品選択部１２３は、これらの用品ｘ７及び用品ｘ１７についても配置候補としては不適であると判断する。
【００８４】
用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、不適であるとして除外された用品ｘ７、用品ｘ１７及び用品１８に次いで被約費用が小さい用品ｘ８を配置候補として選択する。
【００８５】
用品ｘ８が配置される区間３’において、用品ｘ９を用品ｘ８に変更する場合、目的関数は、図８（７）に示されるように、１となり、更に改善が見られる。このため、用品選択部１２３は、区間３’において配置される用品をｘ８に決定する。
【００８６】
用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、被約費用が小さい用品について、配置候補として選択して目的関数の算出を更に行う。用品選択部１２３は、図８（７）に示されるよう、被約費用が小さい用品ｘ６、ｘ９、ｘ１８、ｘ１４、ｘ１７、ｘ１６の順で各用品に配置を変更した場合の目的関数の算出を行う。尚、用品ｘ６に配置を変更する場合、目的関数は３となり悪化する。用品ｘ９に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１８に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１４に配置を変更する場合、目的関数は１となり改善が見られない。用品ｘ１７に配置を変更する場合、目的関数は１となり改善が見られない。
【００８７】
用品ｘ１６に配置を変更する場合、図８（８）に示されるように、目的関数が０となり改善が見られるため、用品選択部１２３は、用品ｘ１５の代わりに用品ｘ１６を配置するよう決定する。
【００８８】
用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１６が配置された状態のネットワーク２００において、用品選択部１２３は、被約費用が小さい用品について、配置候補として選択して目的関数の算出を更に行う。用品選択部１２３は、図８（８）に示されるよう、被約費用が小さい用品ｘ６、ｘ９、ｘ５、ｘ１４、ｘ１８、ｘ１７の順で各用品に配置を変更した場合の目的関数の算出を行う。尚、用品ｘ６に配置を変更する場合、目的関数は４となり悪化する。用品ｘ９に配置を変更する場合、目的関数は３となり悪化する。用品ｘ１４に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１８に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１７に配置を変更する場合、目的関数は１となり悪化する。以上のように、被約費用が負である用品で、目的関数が改善するものがないため、用品選択部１２３は、以降の処理を終了する。
【００８９】
用品選択部１２３は、用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１６が配置される場合に目的関数が最小値となることから、これらの用品を配置するよう用品配置情報を決定する。
【００９０】
以上、説明した一連の動作によれば、全ての配置候補の用品について、目的関数を算出することなく、好適な配置用品を決定することが出来る。用品毎の被約費用は、該用品に配置を変更する場合の目的関数に与える影響の大小を示す指標である。特に、目的関数を最小化する数理計画法における問題においては、被約費用が負となる用品を次の配置候補として選択することにより、好適に、目的関数を改善する可能性のある用品を選択することが出来る。このため、被約費用を比較することで、目的関数を改善する可能性のない（例えば、被約費用が正又は０の）用品を配置候補から除外することが出来る。
【００９１】
従って、全ての配置候補の用品について、目的関数の算出を行うことなく、目的関数の改善の可能性がある用品を選択可能となる。
【００９２】
上述した数理計画法における問題は、整数計画問題又は混合整数計画問題等の問題としてモデル化が可能である。しかしながら、整数計画問題又は混合整数計画問題を用いて台規模問題を解く場合、計算量が増大することにより、短時間で最適解を算出することは困難な場合が多い。例えば、上述した動作例によらない（言い換えれば、従来の）最適解の算出法においては、用品についてのある組み合わせから次に配置を変更する用品を決定する場合、各用品について配置した場合の目的関数を算出していた。しかしながら、目的関数の算出には、行列演算が生じるため、計算負荷が多く、算出に多くの時間が必要とされる。
【００９３】
他方で、上述した動作例によれば、ある用品を配置用品として決定した場合の途中解から、次に目的関数が改善される可能性のある用品についての実行可能解に至る計算量を低減し、効率的に遷移を行うことが可能となる。このため、最適解の算出に係る計算量を低減し、より短時間で算出することが可能となる。
【００９４】
尚、例えば、目的関数を最大化するような数理計画法における問題を設定する場合、被約費用が正となる用品の内、最大のものから順番に目的関数を算出することで、同様の効果を得ることが出来る。従って、上述した例以外の数理計画法における問題についても、上述した一連の動作及びその効果が適用可能である。
【００９５】
（３）第１変形動作例
図９及び図１０を参照して、ネットワーク設計装置１００の第１変形動作例について説明する。図９は、第１変形動作例における配置用品の選択動作の流れを示すフローチャートである。図１０は、第１変形動作例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。
【００９６】
第１変形動作例においては、ネットワーク設計装置１００の用品選択部１２３は、被約費用が負であり最小である用品の代わりに、被約費用が負であり最小である用品が存在する区間において、現在配置されている用品からコストが最も近いものを次の配置候補として選択する。
【００９７】
以下に、具体的な動作の流れを説明する。
【００９８】
用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態において、用品選択部１２３は、各用品についての被約費用を算出する（ステップＳ２００）。用品選択部１２３は、被約費用が負である用品が存在するか否かの確認を行う（ステップＳ２０１）。
【００９９】
被約費用が負である用品が存在する場合（ステップＳ２０１：Ｙｅｓ）、用品選択部１２３は、被約費用が負であり且つ最小の用品を検出し、該用品が存在する区間を選択する（ステップＳ２０２）。そして、用品選択部１２３は、該区間において、被約費用が負であり、現在の配置用品からコストが最も近い用品を選択する（ステップＳ２０３）。
【０１００】
図１０（１）の例では、用品選択部１２３は、被約費用が負であり且つ最小の用品として用品ｘ９を選択する。そして、用品ｘ９が存在する区間３’において、被約費用が負であり、且つ現在配置される用品ｘ７からコストが最も近い用品ｘ８を選択する。
【０１０１】
用品選択部１２３は、選択された用品ｘ８を用品ｘ７に換えて配置した場合の目的関数を算出する（ステップＳ２０４）。図１０（２）に示されるように、算出される目的関数は、９となる。
【０１０２】
用品選択部１２３は、算出した目的関数と、用品変更前の目的関数とを比較して（ステップＳ２０５）、目的関数が改善したか否かの判定を行う（ステップＳ２０６）。図１０（１）及び（２）に示される例では、目的関数が１２から９になり、改善が見られる。
【０１０３】
そこで、用品選択部１２３は、用品ｘ８を配置用品として選択する（ステップＳ２０７）。その後、ステップＳ２０１乃至Ｓ２０６の処理を繰り返す。
【０１０４】
図１０（２）に示されるように、用品ｘ１、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ２を配置候補として選択する。図１０（３）に示されるように、用品ｘ１を用品ｘ２に変更する場合の目的関数は７となり、図１０（２）に示される目的関数９より改善が見られるため、用品選択部１２３は、用品ｘ２を配置用品として選択する。
【０１０５】
図１０（３）に示されるように、用品ｘ２、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ５を配置候補として選択する。図１０（４）に示されるように、用品ｘ４を用品ｘ５に変更する場合の目的関数は５となり、図１０（３）に示される目的関数７より改善が見られるため、用品選択部１２３は、用品ｘ５を配置用品として選択する。
【０１０６】
図１０（４）に示されるように、用品ｘ２、ｘ５、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１１を配置候補として選択する。図１０（５）に示されるように、用品ｘ１０を用品ｘ１１に変更する場合の目的関数は３となり、図１０（４）に示される目的関数５より改善が見られるため、用品選択部１２３は、用品ｘ１１を配置用品として選択する。
【０１０７】
図１０（５）に示されるように、用品ｘ２、ｘ５、ｘ８、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ９を配置候補として選択する。図１０（６）に示されるように、用品ｘ８を用品ｘ９に変更する場合の目的関数は２となり、図１０（５）に示される目的関数３より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１０８】
図１０（６）に示されるように、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１６を配置候補として選択する。図１０（７）に示されるように、用品ｘ１５を用品ｘ１６に変更する場合の目的関数は１となり、図１０（６）に示される目的関数２より改善が見られるため、用品選択部１２３は、用品ｘ１６を配置用品として選択する。
【０１０９】
図１０（７）に示されるように、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１６が配置された状態では、用品選択部１２３は、用品ｘ１２、ｘ１４、ｘ１７、ｘ１８の順で配置候補を選択するが、いずれの用品を配置した場合でも、目的関数に改善が見られない。そこで、用品選択部１２３は、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１６が配置される状態を配置用品情報として決定し（ステップＳ２０９）、処理を終了する。
【０１１０】
上述した、第１変形動作例においても、ネットワーク設計装置１００の動作例と同様に、一の途中解から次の実行可能解への遷移において、被約費用に基づくことで、目的関数の改善の可能性がある用品を好適に選択することが出来る。従って、最適な用品の配置を決定するための数理計画法における問題を解く際の計算量を低減した上で、好適な解を算出することが出来る。
【０１１１】
（４）第２変形動作例
図１１及び図１２を参照して、ネットワーク設計装置１００の第２変形動作例について説明する。図１１は、第２変形動作例における配置用品の選択動作の流れを示すフローチャートである。図１２は、第２変形動作例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。
【０１１２】
第２変形動作例においては、ネットワーク設計装置１００の用品選択部１２３は、現在配置されている用品からコストが最も近い用品群から順に、被約費用が負であり且つ最小である用品を次の配置候補として選択する。
【０１１３】
以下に、具体的な動作の流れを説明する。
【０１１４】
用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態において、用品選択部１２３は、各用品についての被約費用を算出する（ステップＳ３００）。用品選択部１２３は、被約費用が負である用品が存在するか否かの確認を行う（ステップＳ３０１）。
【０１１５】
被約費用が負である用品が存在する場合（ステップＳ３０１：Ｙｅｓ）、用品選択部１２３は、現在の配置用品からコストが最も近い用品を一又は複数選択する（ステップＳ３０２）。そして、用品選択部１２３は、選択された用品の内、被約費用が負であり且つ最小の用品を配置候補として選択する（ステップＳ３０３）。
【０１１６】
図１２（１）の例では、用品選択部１２３は、現在配置される用品群ｘ２、ｘ５、ｘ８、ｘ１１、ｘ１４、ｘ１６のうち，被約費用が最小のい用品ｘ８を選択する。
【０１１７】
用品選択部１２３は、選択された用品ｘ８を用品ｘ７に換えて配置した場合の目的関数を算出する（ステップＳ３０４）。図１２（２）に示されるように、算出される目的関数は、９となる。
【０１１８】
用品選択部１２３は、算出した目的関数と、用品変更前の目的関数とを比較して（ステップＳ３０５）、目的関数が改善したか否かの判定を行う（ステップＳ３０６）。図１２（１）及び（２）に示される例では、目的関数が１２から９になり、改善が見られる。
【０１１９】
そこで、用品選択部１２３は、用品ｘ８を配置用品として選択する（ステップＳ３０７）。その後、ステップＳ３０１乃至Ｓ３０６の処理を繰り返す。
【０１２０】
図１２（２）に示されるように、用品ｘ１、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ９を配置候補として選択する。図１２（３）に示されるように、用品ｘ８を用品ｘ９に変更する場合の目的関数は６となり、図１２（２）に示される目的関数９より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１２１】
図１２（３）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ２を配置候補として選択する。図１２（４）に示されるように、用品ｘ１を用品ｘ２に変更する場合の目的関数は４となり、図１２（３）に示される目的関数６より改善が見られるため、用品選択部１２３は、用品ｘ２を配置用品として選択する。
【０１２２】
図１２（４）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１１を配置候補として選択する。図１２（５）に示されるように、用品ｘ１０を用品ｘ１１に変更する場合の目的関数は２となり、図１２（４）に示される目的関数４より改善が見られるため、用品選択部１２３は、用品ｘ１１を配置用品として選択する。
【０１２３】
図１２（５）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１７を配置候補として選択する。図１２（６）に示されるように、用品ｘ１５を用品ｘ１７に変更する場合の目的関数は０となり、図１２（５）に示される目的関数２より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１２４】
図１２（６）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１７が配置された状態では、目的関数が０となるため、用品選択部１２３は、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１７が配置される状態を配置用品情報として決定し（ステップＳ３０９）、処理を終了する。
【０１２５】
上述した、第２変形動作例においても、ネットワーク設計装置１００の動作例と同様に、一の途中解から次の実行可能解への遷移において、被約費用に基づくことで、目的関数の改善の可能性がある用品を好適に選択することが出来る。従って、最適な用品の配置を決定するための数理計画法における問題を解く際の計算量を低減した上で、好適な解を算出することが出来る。
【０１２６】
以上説明した実施形態に関して、更に以下の付記を開示する。
【０１２７】
（付記１）
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
を備え、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計装置。
【０１２８】
（付記２）
前記装置選択手段は、（１）前記伝送装置の候補から第１の組み合わせを選択し、（２）該第１の組み合わせについて前記数理計画法における問題の目的関数及び被約費用を算出し、（３）算出された前記被約費用に基づいて、前記伝送装置の候補から前記第１の組み合わせとは異なる第２の組み合わせを選択し、（４）該第２の組み合わせについて算出した、前記数理計画法における問題の目的関数と、前記第１の組み合わせについて算出した、前記数理計画法における問題の目的関数とを比較し、（５）目的関数が前記数理計画法における問題の目標値により近い組み合わせを前記線形区間に配置する前記伝送装置の候補の組み合わせとして決定することを特徴とする付記１に記載のネットワーク設計装置。
【０１２９】
（付記３）
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３０】
（付記４）
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３１】
（付記５）
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記伝送装置の候補の組み合わせに含まれる前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３２】
（付記６）
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記第１の組み合わせに含まれている前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３３】
（付記７）
前記装置選択手段は、前記伝送装置の候補の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記伝送装置の候補の組み合わせに含まれない前記伝送装置のうち、該伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３４】
（付記８）
前記装置選択手段は、前記第１の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記第１の組み合わせに含まれない前記伝送装置のうち、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３５】
（付記９）
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得工程と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成工程と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択工程
とを備え、
前記装置選択工程は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計方法。
【０１３６】
（付記１０）
コンピュータを、
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
して機能させ、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計プログラム。
【０１３７】
本発明は、上述した実施例に限られるものではなく、請求の範囲及び明細書全体から読み取れる発明の要旨又は思想に反しない範囲で適宜変更可能であり、そのような変更を伴うネットワーク設計装置及び方法などもまた本発明の技術的範囲に含まれるものである。
【符号の説明】
【０１３８】
１００ ネットワーク設計装置、
１１０ 入出力インタフェース、
１１１ 入力部、
１１２ 出力部、
１２０ ＣＰＵ、
１２１ 用品候補選択部、
１２２ 問題生成部、
１２３ 用品選択部、
１３０ メモリ。
【技術分野】
【０００１】
本発明は、ネットワークへの用品配置を決定するためのネットワーク設計装置及び方法の技術分野に関する。
【背景技術】
【０００２】
移動通信システム等において利用されるこの種のネットワークでは、ネットワーク上のトラヒックを処理するために最低限必要とされる装置構成がある。ネットワーク上の装置構成とは、例えば、信号の中継局など、所謂信号の伝送に係る装置である。
【０００３】
一般に、ネットワーク上に配置されるこれらの信号伝送装置のコストと、これらの信号伝送装置上を経由する信号の伝送品質とはトレードオフの関係にある。すなわちコストの高い信号伝送装置が配置されると信号の伝送品質が向上する。これによりネットワーク上の信号の伝送路上において必要とされる信号伝送装置の数が減少する。他方で、コストが低い信号伝送装置の配置数を増やすと全体としての装置の配置数が増加する。
【０００４】
また、ネットワークの性質上、上述したネットワーク上のトラヒックを処理するために求められるコストを大きく下回るネットワークは許容されない。
【０００５】
上述した性質を考慮して、ネットワークの設計においては、トラヒックより決定される目標コストに対して、信号伝送装置のコストの総和、言い換えればネットワークを敷設する際の所要コストを可能な限り近付けることが好ましい。このようなネットワークの設計のために、整数計画法を用いてネットワークを設計する手法が提案されている。
【０００６】
下記に示される先行技術文献には、基板に部品を装着する際の割り振り方法を混合整数計画問題としてモデル化し、該問題を解くことにより割り振り方法を決定する方法について説明されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−３８０８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ネットワークの設計においても、数理計画法における整数計画問題又は混合整数計画問題等の問題を用いて、ネットワーク上に設置される装置のコストの総和と目標コストとの差分が最小となる配置を決定することで、好適なネットワーク設計が可能となる。
【０００９】
しかしながら、数理計画法における問題を解くことによるネットワーク上の装置の配置決定は、装置数が増えることにより解法に係る処理量が増大するという技術的な問題がある。
【００１０】
例えば、あるネットワークについて、現在考えられている配置から装置を一つ変更することを考える場合、装置交換後の目的関数を再計算することが要求される。また、かかる変更がネットワーク設計において適しているか否かを判定するためには、変更候補の装置全てについて目的関数を計算し直す必要がある。
【００１１】
本発明は、上述した問題点に鑑み為されたものであり、数理計画法における問題を用いるネットワークの設計方法において、要求される処理量を低減し得るネットワークの設計装置及び方法を提供することを課題とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、開示のネットワーク設計装置は、情報取得手段と、問題生成手段と、装置選択手段とを備える。
【００１３】
情報取得手段は、線形区間を含むネットワークにおいて、該線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、伝送装置の候補の夫々の配置コスト、及び線形区間における一又は複数の配置点を含む所定の区間における伝送装置の配置コストの和である目標コストの夫々を取得する。
【００１４】
問題生成手段は、装置候補情報、配置コスト、及び目標コストに基づいて、線形区間に配置する伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する。
【００１５】
装置選択手段は、生成された数理計画法における問題を、伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、線形区間に配置する伝送装置の候補の組み合わせを決定する。尚、装置選択手段は、伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に数理計画法における問題を解く伝送装置の候補を決定する。
【００１６】
上記課題を解決するために、開示のネットワーク設計方法は、情報取得工程と、問題生成工程と、装置選択工程とを備える。情報取得工程では、上述した情報取得手段と同様の処理が実施される。問題生成工程では、上述した問題生成手段と同様の処理が実施される。装置選択工程では、上述した装置選択手段と同様の処理が実施される。
【発明の効果】
【００１７】
開示のネットワーク設計装置によれば、配置される伝送装置の組み合わせの候補について算出した被約費用に基づいて、次に目的関数を算出するために数理計画法における問題を解くための伝送装置の組み合わせの候補が選択される。このため、好適に目的関数の改善の可能性がある伝送装置の組み合わせについて、目的関数の検証が可能となるため、計算量を低減することが出来る。
【図面の簡単な説明】
【００１８】
【図１】設計対象となるネットワークを示す図である。
【図２】ネットワーク設計装置のハードウェア構成及び機能部構成を示す図である。
【図３】ネットワーク設計装置に入力されるネットワークについての情報を示す図である。
【図４】ネットワーク設計装置の動作例における動作の流れを示すフローチャートである。
【図５】動作例における配置候補の用品について、コスト及び目標コストを示す図である。
【図６】被約費用の算出の具体例を示す図である。
【図７】目的関数費用の算出の具体例を示す図である。
【図８】ネットワーク設計装置の動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【図９】ネットワーク設計装置の第１変形動作例における動作の流れを示すフローチャートである。
【図１０】ネットワーク設計装置の第１変形動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【図１１】ネットワーク設計装置の第２変形動作例における動作の流れを示すフローチャートである。
【図１２】ネットワーク設計装置の第２変形動作例における目的関数及び被約費用の推移の様子を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００２０】
（１）構成例
図１に、開示のネットワーク設計装置による設計の対象となるネットワークの一例を示す。図１に示されるネットワーク２００は、移動通信システム等を構成するネットワークの一部を示すものである。ネットワーク２００では、信号分岐装置又は信号中継装置等のノード装置１乃至６が配置される線形区間について示している。尚、ネットワーク２００は、所謂メッシュ型のネットワークにおける或る線形区間について示しているが、例えば、ネットワーク２００はその他の態様のネットワークの一部であってもよい。
【００２１】
線形区間は２つ以上のノード装置が縦続接続されることにより形成される区間である。例えば、図１の例では、ノード装置１の出力がノード装置２の入力に、ノード装置２の出力がノード装置３の入力に、ノード装置３の出力がノード装置４の入力に、ノード装置４の出力がノード装置５の入力に、ノード装置５の出力がノード装置６の入力に、夫々接続されている。尚、接続端子の向きは逆向きであっても、双方向であってもよい。また、線形区間においては、ノード装置間の接続は、物理的に直線である必要はなく、曲線的に接続されていてもよい。
【００２２】
開示のネットワーク設計装置は、ネットワーク２００における線形区間において、該線形区間に配置されるノード装置の組み合わせを決定する。以降、ノード装置について「用品」と記載し、ノード装置の配置の組み合わせについて「用品配置」と記載して説明することがある。
【００２３】
ネットワーク２００上に配置される用品は、夫々トラヒックを処理するためのコストを有している。コストの高い用品が配置されると、ネットワーク２００における該用品を経由する信号の伝送品質が大きく向上する。他方で、コストの低い用品が配置されると、伝送品質の大きな向上は生じない。
【００２４】
ネットワーク２００上では、所定の区間ごとにトラヒック処理のための目標コストが設定される。かかる目標コストは、ネットワーク２００上において、シミュレーションや統計処理等により得られる予測トラヒック量を処理するために必要とされるコストである。区間ごとの該目標コストに対して、多少の変動幅は許容されるものの、該区間に配置される用品のコスト総和と目標コストとの差分が可能な限り近付くよう、ネットワーク２００が設計されることが好ましい。
【００２５】
以下に説明するように、ネットワーク設計装置１００は、ネットワーク２００において区間ごとに設定される目標コストに対して、より近いコスト総和を有する用品配置の決定を行う。
【００２６】
図２を参照して、ネットワーク設計装置１００の構成について説明する。図２は、ネットワーク設計装置１００の基本的な構成を示すブロック図である。
【００２７】
図２に示されるように、ネットワーク設計装置１００は、入出力インタフェース１１０と、ＣＰＵ１２０と、メモリ１３０とを備える。
【００２８】
入出力インタフェース１１０は、例えば、外部のネットワークノード装置や、コンピュータ等との間でデータの入出力を行うためのインタフェースであって、入力部１１１及び出力部１１２の機能部を有する。
【００２９】
入力部１１１は、外部からのデータを入力するための機能部であって、設計対象となるネットワークトポロジー情報、該ネットワーク２００におけるトラヒック情報（言い換えれば、ネットワーク上の各区間における配置用品の目標コスト）及び該ネットワーク２００上に配置される用品についてのデータ等の入力を受け、ＣＰＵ１２０に出力する。用品についてのデータとは、例えば、ネットワークトポロジーにおける或る区間における配置候補となり得る各用品についてコストを示したものである。
【００３０】
出力部１１２は、ＣＰＵ１２０において算出された用品配置情報を外部に出力する。
【００３１】
ＣＰＵ１２０は、ネットワーク設計装置１００における各部の動作の制御を行うための演算装置であり、また入力された情報を処理することで、用品配置情報の算出を行う。ＣＰＵ１２０は、用品候補選択部１２１、問題生成部１２２及び用品選択部１２３の機能部を有する。
【００３２】
用品候補選択部１２１は、入力部１１１より入力される用品のデータに基づいて、ネットワーク２００上の用品配置情報の算出を行うための用品候補データの生成を行う。また、用品候補選択部１２１は、生成した用品候補データについて、メモリ１３０内部にデータベースとして格納してもよい。
【００３３】
問題生成部１２２は、入力部１１１より入力されるネットワークトポロジー情報及びトラヒック情報に基づいて、用品配置情報の算出を行うための数理計画法における整数計画問題又は混合整数計画問題等の問題の生成を行う。また、問題生成部１２２は、入力されるネットワークトポロジー情報及びトラヒック情報、並びに生成した数理計画法における問題をメモリ１３０内部に格納してもよい。
【００３４】
用品選択部１２３は、用品候補選択部１２１において生成される用品候補データと、問題生成部１２２において生成される数理計画法における問題とに基づいて、ネットワーク２００上への用品配置情報の算出を行う。用品選択部１２３は、例えば、数理計画法における問題を、用品候補データについて解くことによって、用品配置情報の算出を行う。
【００３５】
メモリ１３０は、ＣＰＵ１２０を動作させるためのソフトウェアや、ネットワーク設計装置１００の動作の上での各種情報等を格納するための記憶装置である。
【００３６】
図３に、問題生成部１２２が生成する数理計画法における問題をネットワークトポロジー図として示す。図３は、図１に示されるネットワーク２００における線形区間についてネットワークトポロジー図として示すものである。
【００３７】
図３に示されるように、問題生成部１２２は、入力部１１１より入力されるネットワークトポロジー情報及びトラヒック情報に基づいて、用品が配置される区間を指定するネットワークトポロジー図を生成する。図３の例では、問題生成部１２２は、図１のネットワーク２００をノード装置１が配置される区間１’と、ノード装置２が配置される区間２’と、ノード装置３が配置される区間３’と、ノード装置４が配置される区間４’と、ノード装置５が配置される区間５’と、ノード装置６が配置される区間６’とに分割する。
【００３８】
また、問題生成部１２２は、トラヒック情報に基づいて、ネットワークトポロジーにおける区間毎の目標コストを設定する。図３の例では、区間１’、２’、３’における用品コストの総和が１５、区間３’、４’、５’における用品コストの総和が２０、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０に夫々設定される。
【００３９】
用品候補選択部１２１は、用品候補データを参照して、区間毎に配置される用品の識別番号とコストとを用品選択部１２３に通知する。図３の例では、区間１’に配置される用品の候補としてｘ１（１）、ｘ２（２）及びｘ３（３）が挙げられている。区間２’に配置される用品の候補としてｘ４（７）、ｘ５（８）及びｘ６（９）が挙げられている。区間３’に配置される用品の候補としてｘ７（４）、ｘ８（５）及びｘ９（６）が挙げられている。区間４’に配置される用品の候補としてｘ１０（１１）、ｘ１１（１２）及びｘ１２（１３）が挙げられている。区間５’に配置される用品の候補としてｘ１３（２）及びｘ１４（３）が挙げられている。区間６’に配置される用品の候補としてｘ１５（９）、ｘ１６（１０）、ｘ１７（１１）及びｘ１８（１２）が挙げられている。尚、カッコ内の数字は各用品のコストを示す。
【００４０】
問題生成部１２２は、用品候補選択部１２１から入力される区間毎の配置用品とそのコスト、並びにネットワークトポロジーに示されるネットワーク２００上の区間及び目標コストを参照し、下記の式（１）乃至（３）に示される整数計画問題を生成する。
【００４１】
上述した整数計画問題又は混合整数計画問題を解くことにより、適切な用品配置の決定を行う数理計画法では、上述したように区間毎に設定される配置用品の候補より、複数の区間を跨いで設定される目標コスト等に基づいて、各区間に配置される用品が決定される。また、図３に示されるネットワークトポロジーの例においては、各区間に一つずつ用品が配置される。このように、区間毎に配置される用品の数、及び目標コストを条件として、問題生成部１２２は、用品の配置を決定するための制約式を生成する。
【００４２】
用品選択部１２３は、このような制約式により示される条件の下、数理計画法に基づいて算出する対象である目的関数（objective function）を最適な値（例えば、最大値又は最小値）となるよう整数計画問題を解くことで、好適な用品の配置を決定する。
【００４３】
以下に示す例では、用品選択部１２３は、ネットワーク２００の区間毎に配置される用品の目標コストと配置される用品のコストの和との差分を目的関数に設定する。そして、ネットワーク２００の区間毎に配置される用品のコストの和を可能な限り目標コストに近付けるよう、用品選択部１２３は、このような目的関数を制約式により示される条件下で最小とする最適解を算出することで用品の配置を決定する。
【００４４】
（２）動作例
以下、本実施例で用いる整数計画問題及びその解法について説明する。
【００４５】
問題生成部１２２は、上述のように生成されたネットワークトポロジーに基づいて、数理計画法における問題を生成する。
【００４６】
問題生成部１２２は、例えば、入力情報として、ネットワーク２００における区間情報及びトラフィック情報、各区間において配置可能な用品の候補、各用品のコスト、並びに各トラフィックに基づく所定の区間毎の目標コスト等の入力を受ける。そして、問題生成部１２２は、ネットワーク２００における各区間において、トラフィックに基づいて決定される目標コストに対して、配置される用品のコストの総和が最適となるよう、各区間に配置可能な用品候補から夫々１つの用品を選択することを目標とする問題を生成する。
【００４７】
数理計画法における問題は、例えば、整数計画問題又は混合整数計画問題に係る目的関数と制約式との集合となる。以下に示される式（１）式は、問題生成部１２２により生成される数理計画法における問題に基づき、上述した用品選択部１２３が解く整数計画問題における目的関数を表現する数式である。
【００４８】
【数１】
式（１）において、ｐｅ（ｔ）及びｎｅ（ｔ）は、配置される用品のコストの和と、目標コストとの差分、つまり誤差を示す成分である。尚、ｐｅ（ｔ）は、正の誤差について、ｎｅ（ｔ）は負の誤差について夫々示す成分であり、ｐｅ（ｔ）＋ｎｅ（ｔ）により誤差の絶対量を示す。変数ｔは、ネットワーク２００上におけるトラヒックが生じる所定の経路（トラヒック経路）を示す。関数ｗ（ｔ）は、或る経路ｔにおける配置用品のコストと目標コストとの誤差に重みづけを行うための係数である。かかる係数を設定することにより、ネットワーク２００における特定の箇所をトラヒック毎に決定し、優先的に用品の配置決定を行うことが出来る。重みづけ係数ｗ（ｔ）は、用品候補選択部１２１、問題生成部１２２又は用品交換部１２３等において設定される。尚、その他の態様で、用品配置の決定に係る優先度を別途指定してもよい。
【００４９】
式（１）に示した目的関数に係る制約条件を示す制約式を以下の式（２）及び式（３）に示す。
【００５０】
【数２】
【００５１】
【数３】
式（２）は、ネットワーク２００に配置される用品について、各区間（つまり、図３における区間１’乃至６’のいずれか）の用品の候補より１つずつ選択するという条件を示す制約式である。式（２）において、ｘ（ｃ）は、区間（segment）ｓにおける用品ｃについての存在又は非存在を示す関数である。ｘ（ｃ）＝１である場合、用品ｃが配置され、ｘ（ｃ）＝０である場合、用品ｃが配置されていないことを夫々示す。つまり、式（２）によれば、或る区間ｓにおいて配置される用品は、該区間に配置される用品候補（ｃａｎｄｉｄａｔｅ ｃ ｏｎ ｓ）のうち、１つが選択されることを示している。
【００５２】
式（３）は、ネットワーク２００に配置される用品について、コストの総和と、所定の１又は複数の区間毎に設定される目標コストとの誤差を決定する制約式である。式（３）において、ｉｄｅａｌ＿ｃｏｓｔ（ｔ）は、所定の経路ｔについて算出された目標コストを示す。ｃｏｓｔ（ｃ）は、所定の経路ｔ中の区間ｃに配置される用品のコストを示す。用品のコストｃｏｓｔ（ｃ）と、配置される用品ｘ（ｃ）との積ｃｏｓｔ（ｃ）・ｘ（ｃ）は、所定のトラヒック経路ｔにおける区間ｃに配置される用品のコストを示す。また、トラヒック経路ｔ中の区間ｃのコストの総和は、Σｃｏｓｔ（ｃ）・ｘ（ｃ）により表される。
従って、式（３）によれば、所定のトラヒック経路ｔにおける各区間に配置される用品のコストの総和と該トラヒック経路における目標コストとの差分が誤差成分ｐｅ（ｔ）＋ｎｅ（ｔ）により表される。
【００５３】
上記のように設定された整数計画問題について、用品選択部１２３は、最適解の算出を行う。以下に、用品選択部１２３が行う算出処理の流れについて、図４を参照して説明する。
【００５４】
図４は、最適解の算出処理に係る用品選択部１２３の動作の流れを示すフローチャートである。図５は、図３に示されるネットワーク２００における区間毎の用品候補のコストと、被約費用（Reduced Cost）とを含むデータを示すテーブルである。
【００５５】
図５には、図３に示されるように、区間１’、２’、３’における用品コストの総和が１５、区間３’、４’、５’における用品コストの総和が２０、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０に夫々設定される場合についての用品の配置に係るデータが示される。以降の説明においては、区間毎の目標コストについて、区間１’、２’、３’における用品コストの総和が１５となる条件を条件１と記載して説明する。また、区間３’、４’、５’における用品コストの総和が２０となる条件を条件２と記載して説明する。また、区間１’、２’、３’、４’、５’、６’における用品コストの総和が４０となる条件を条件３と記載して説明する。
【００５６】
図５のテーブルの第１行には、各用品についての用品番号ｘｎ及び誤差成分が記載される。誤差成分の内、ｎｅ１及びｐｅ１は、条件１における誤差成分、ｎｅ２及びｐｅ２は、条件２における誤差成分、ｎｅ３及びｐｅ３は、条件３における誤差成分を夫々示す。
【００５７】
図５のテーブル第２行には、各用品及び誤差成分についての存在又は非存在を示すベクトルｃが記述される。
【００５８】
図５のテーブル第３行から第１２行までには、ネットワーク２００に対する各用品の配置状態及びコスト、並びに誤差成分の状態を示す行列Ａが記述される。
【００５９】
図５のテーブル第１３行には、各用品候補ｘｎについて、夫々の被約費用ｃ＾が記述される。被約費用ｃ＾は、例えば、行列Ａについて、条件１、条件２又は条件３について連立方程式を生成することで算出可能である。
【００６０】
以下の説明では、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置されたネットワーク２００において、より効率的な（つまり、目標コストと配置される用品コストの総和との誤差が最小となる）用品の配置を決定する際の動作について説明する。
【００６１】
図４に示されるように、先ず用品選択部１２３は、上述のように生成された整数計画問題における目的関数及び制約式に基づいて、各区間の用品の候補についての被約費用の算出を行う（ステップＳ１００）。
【００６２】
図６を参照して、被約費用の具体的な算出動作について説明する。
【００６３】
被約費用ｃ＾は、以下に示す式（４）により表される。
【００６４】
【数４】
ここに、Ｎは、非基底成分の（言い換えれば、選択されていない）変数（つまり、各用品ｘｎ並びに誤差成分ｐｅ及びｎｅを含む変数）に対応する行列である。具体的には、図５に示す行列Ａにおいて、非基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列の集合が行列Ｎにあたる。また、ｃＮは、行列ｃの非基底成分を示す行列である。具体的には、図５に示す行列ｃにおいて、非基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列（値）の集合がｃＮにあたる。尚、πは以下の式（５）により表される。
【００６５】
【数５】
ここに、Ｂは基底成分の（言い換えれば、ネットワーク２００に仮に配置されている）用品候補を示す行列である。具体的には、図５に示す行列Ａにおいて、基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列の集合が行列Ｂにあたる。また、ｃＢは、行列ｃの基底成分を示す行列である。具体的には、図５に示す行列ｃにおいて、基底成分である用品ｘｎ、誤差成分ｐｅ、ｎｅについての列（値）の集合がｃＢにあたる。図３及び図５の例に基づく行列Ｂ及びｃＢは、図６（１）に示されるものとなる。また、行列Ｂの逆行列Ｂ−１は、図６（２）に示されるものとなる。
【００６６】
尚、π＝ｃＢＢ−１は、図６（３）に示されるものとなる。
【００６７】
以上、示した式を用いることで、現在ネットワーク２００に配置されていない用品（つまり、非基底成分Ｎ）の被約費用ｃ＾は、以下の式（６）より求められる。
【００６８】
【数６】
尚、図５に示される例では、ｃＢは、誤差成分以外の用品については０となるため、被約費用ｃ＾＝−ｃＢＢ−１Ｎとなる。なお、ここでは誤差成分に関する被約費用は省略している。
【００６９】
目的関数を最小化することを目的とする、所謂最小化問題においては、被約費用ｃ＾成分が負であり、且つ絶対量の大きい（言い換えれば、最小の）被基底変数を新たに基底変数として、現在基底変数に選択されている変数と交換することで、目的関数が改善される可能性がある。用品選択部１２３は、算出された被約費用を参照して、被約費用が負である配置候補の用品が存在するか否かを確認する（ステップＳ１０１）。
【００７０】
被約費用が負である配置候補の用品が存在する場合（ステップＳ１０１：Ｙｅｓ）、用品選択部１２３は、図５のテーブルのように示される配置用品の候補から、被約費用が負であり、且つ最小のものを選択する（ステップＳ１０２）。用品選択部１２３は、現在ネットワーク２００に配置される用品を、該選択された配置候補の用品に配置を変更した場合の目的関数の算出を行う（ステップＳ１０３）。
【００７１】
目的関数の算出の態様について、図７に例を示して説明する。初回の算出時には、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態であるため、図７は、これらの用品を配置した際の目的関数の算出の態様について示している。このように配置される用品の組み合わせによれば、条件１に該当する区間１’、２’、３’におけるコスト総和は１＋７＋４＝１２となり、目標コスト１５とのコスト差分は３となる。また、条件２に該当する区間３’、４’、５’におけるコスト総和は４＋１１＋２＝１７となり、目標コスト２０とのコスト差分は３となる。また、条件３に該当する区間１’、２’、３’、４’、５’、６’におけるコスト総和は１＋７＋４＋１１＋２＋９＝３４となり、目標コスト４０とのコスト差分は６となる。以上のことから、条件１乃至３を同時に満たすよう設定される目的関数は、コスト差分の和３＋３＋６＝１２となる。
【００７２】
用品選択部１２３は、用品の配置変更後の目的関数と、変更前の目的関数とを比較して、変更前に比べて目的関数が改善しているか（つまり、変更前より値が小さくなっているか）否かの判定を行う（ステップＳ１０４）。
【００７３】
用品選択部１２３は、用品の配置の変更により、目的関数が改善されると判断される場合（ステップＳ１０５：Ｙｅｓ）、該選択された配置候補の用品を配置用品として設定する（ステップＳ１０６）。その後、用品選択部１２３は、選択された配置用品について被約費用の算出を行い、ステップＳ１００乃至Ｓ１０５の処理を繰り返す。
【００７４】
他方で、用品の配置の変更により、目的関数が改善されない、又は悪化すると判断される場合（ステップＳ１０５：Ｎｏ）、該選択された配置候補の用品を配置用品としては不適であると判断する（ステップＳ１０７）。その後、用品選択部１２３は、ステップＳ１００において算出された被約費用のうち、不適とされた配置候補の用品を除いて、被約費用が負である配置候補の用品が存在するか否かの確認を行い、ステップＳ１０１乃至Ｓ１０５の処理を繰り返す。
【００７５】
用品選択部１２３は、目的関数が改善しない、又は悪化することから不適と判断された用品を除いて、被約費用が負である用品が存在しない場合（ステップＳ１０１：Ｎｏ）、現在設定される配置用品の組み合わせを、配置用品情報として決定する（ステップＳ１０８）。
【００７６】
上述した動作の流れにおける用品の選択及び目的関数の算出の態様について、図８を参照して説明する。図８は、図３及び図５に示される例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。なお、以降の例では、記載を省略するが、各区間の誤差成分ｐｅ、ｎｅのうち、いずれか一方の誤差量が正となる成分が基底として選択されているものとする。また、誤差量が０の場合はｎｅが基底として選択される。
【００７７】
図８（１）に示されるように、用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態のネットワーク２００において、用品選択部１２３は、配置候補として、被約費用が負であり、且つ絶対量が最大の用品を選択する。用品選択部１２３は、図８（１）の例では、被約費用が−６の用品ｘ９を配置候補として選択する。次に、用品選択部１２３は、用品ｘ９が配置される区間３’において、現在仮に配置される用品ｘ７をｘ９に変更した場合について、目的関数の算出を行う。
【００７８】
用品選択部１２３は、図５に示されるものと同様の手順で、用品ｘ１、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置される場合の目的関数の算出を行う。図８（２）に示されるように、変更後の目的関数は６となり、変更前と比較して改善が見られる。このため、用品選択部１２３は、区間３’において配置される用品をｘ９に決定する。尚、配置される用品をｘ７からｘ９に変更することにより、各用品の被約費用が変化する。用品選択部１２３は、ネットワーク２００における他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。
【００７９】
用品ｘ１、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、次の配置候補として用品ｘ３、ｘ６及びｘ１２を検出する。以下の説明では、便宜上、用品ｘ３、ｘ６、ｘ１２のように順番で配置変更後の目的関数の算出と判定を行うものとする。
【００８０】
用品ｘ３が配置される区間１’において、用品ｘ１を用品ｘ３に変更する場合、目的関数は、図８（３）に示されるように、４となり、更に改善が見られる。このため、用品選択部１２３は、区間１’において配置される用品をｘ３に決定する。
【００８１】
用品ｘ３、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。用品選択部１２３は、図８（３）に示されるように算出される用品の被約費用から、次の配置候補として、被約費用が−４である用品ｘ１２を選択する。用品ｘ１２が配置される区間４’において、用品ｘ１０を用品ｘ１２に変更する場合、目的関数は、図８（４）に示されるように、２となり、更に改善が見られる。このため、用品選択部１２３は、区間４’において配置される用品をｘ１２に決定する。
【００８２】
用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、他の区間についての配置用品を選択するために、被約費用の算出を行い、図４に示される動作の流れを繰り返す。用品選択部１２３は、図８（４）に示されるように算出される用品の被約費用から、次の配置候補として、被約費用が−３である用品ｘ１８を選択する。用品ｘ１８が配置される区間６’において、用品ｘ１５を用品ｘ１８に変更する場合、目的関数は、図８（５）に示されるように、５となり、却って悪化する。このため、用品選択部１２３は、区間６’において配置される用品がｘ１８では不適であると判断する。用品選択部１２３は、図８（５）に示される用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１８が配置された状態のネットワーク２００において、被約費用が負であり最も小さい用品ｘ１５を配置候補として選択し、目的関数の算出を行う。
【００８３】
用品ｘ１８を用品ｘ１５に交換することで、図８（６）に示されるように、目的関数及び各用品の被約費用は、図８（４）と同様の状態となる。用品選択部１２３は、不適であると判断した用品ｘ１８を除いて、被約費用が次に小さい（且つ、負である）用品である配置候補として、用品ｘ７及び用品ｘ１７を選択する。尚、配置される用品を用品ｘ７及び用品ｘ１７に変更する場合、目的関数はいずれも４となり悪化するため、用品選択部１２３は、これらの用品ｘ７及び用品ｘ１７についても配置候補としては不適であると判断する。
【００８４】
用品ｘ３、ｘ４、ｘ９、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、不適であるとして除外された用品ｘ７、用品ｘ１７及び用品１８に次いで被約費用が小さい用品ｘ８を配置候補として選択する。
【００８５】
用品ｘ８が配置される区間３’において、用品ｘ９を用品ｘ８に変更する場合、目的関数は、図８（７）に示されるように、１となり、更に改善が見られる。このため、用品選択部１２３は、区間３’において配置される用品をｘ８に決定する。
【００８６】
用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１５が配置された状態のネットワーク２００において、用品選択部１２３は、被約費用が小さい用品について、配置候補として選択して目的関数の算出を更に行う。用品選択部１２３は、図８（７）に示されるよう、被約費用が小さい用品ｘ６、ｘ９、ｘ１８、ｘ１４、ｘ１７、ｘ１６の順で各用品に配置を変更した場合の目的関数の算出を行う。尚、用品ｘ６に配置を変更する場合、目的関数は３となり悪化する。用品ｘ９に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１８に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１４に配置を変更する場合、目的関数は１となり改善が見られない。用品ｘ１７に配置を変更する場合、目的関数は１となり改善が見られない。
【００８７】
用品ｘ１６に配置を変更する場合、図８（８）に示されるように、目的関数が０となり改善が見られるため、用品選択部１２３は、用品ｘ１５の代わりに用品ｘ１６を配置するよう決定する。
【００８８】
用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１６が配置された状態のネットワーク２００において、用品選択部１２３は、被約費用が小さい用品について、配置候補として選択して目的関数の算出を更に行う。用品選択部１２３は、図８（８）に示されるよう、被約費用が小さい用品ｘ６、ｘ９、ｘ５、ｘ１４、ｘ１８、ｘ１７の順で各用品に配置を変更した場合の目的関数の算出を行う。尚、用品ｘ６に配置を変更する場合、目的関数は４となり悪化する。用品ｘ９に配置を変更する場合、目的関数は３となり悪化する。用品ｘ１４に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１８に配置を変更する場合、目的関数は２となり悪化する。用品ｘ１７に配置を変更する場合、目的関数は１となり悪化する。以上のように、被約費用が負である用品で、目的関数が改善するものがないため、用品選択部１２３は、以降の処理を終了する。
【００８９】
用品選択部１２３は、用品ｘ３、ｘ４、ｘ８、ｘ１２、ｘ１３及びｘ１６が配置される場合に目的関数が最小値となることから、これらの用品を配置するよう用品配置情報を決定する。
【００９０】
以上、説明した一連の動作によれば、全ての配置候補の用品について、目的関数を算出することなく、好適な配置用品を決定することが出来る。用品毎の被約費用は、該用品に配置を変更する場合の目的関数に与える影響の大小を示す指標である。特に、目的関数を最小化する数理計画法における問題においては、被約費用が負となる用品を次の配置候補として選択することにより、好適に、目的関数を改善する可能性のある用品を選択することが出来る。このため、被約費用を比較することで、目的関数を改善する可能性のない（例えば、被約費用が正又は０の）用品を配置候補から除外することが出来る。
【００９１】
従って、全ての配置候補の用品について、目的関数の算出を行うことなく、目的関数の改善の可能性がある用品を選択可能となる。
【００９２】
上述した数理計画法における問題は、整数計画問題又は混合整数計画問題等の問題としてモデル化が可能である。しかしながら、整数計画問題又は混合整数計画問題を用いて台規模問題を解く場合、計算量が増大することにより、短時間で最適解を算出することは困難な場合が多い。例えば、上述した動作例によらない（言い換えれば、従来の）最適解の算出法においては、用品についてのある組み合わせから次に配置を変更する用品を決定する場合、各用品について配置した場合の目的関数を算出していた。しかしながら、目的関数の算出には、行列演算が生じるため、計算負荷が多く、算出に多くの時間が必要とされる。
【００９３】
他方で、上述した動作例によれば、ある用品を配置用品として決定した場合の途中解から、次に目的関数が改善される可能性のある用品についての実行可能解に至る計算量を低減し、効率的に遷移を行うことが可能となる。このため、最適解の算出に係る計算量を低減し、より短時間で算出することが可能となる。
【００９４】
尚、例えば、目的関数を最大化するような数理計画法における問題を設定する場合、被約費用が正となる用品の内、最大のものから順番に目的関数を算出することで、同様の効果を得ることが出来る。従って、上述した例以外の数理計画法における問題についても、上述した一連の動作及びその効果が適用可能である。
【００９５】
（３）第１変形動作例
図９及び図１０を参照して、ネットワーク設計装置１００の第１変形動作例について説明する。図９は、第１変形動作例における配置用品の選択動作の流れを示すフローチャートである。図１０は、第１変形動作例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。
【００９６】
第１変形動作例においては、ネットワーク設計装置１００の用品選択部１２３は、被約費用が負であり最小である用品の代わりに、被約費用が負であり最小である用品が存在する区間において、現在配置されている用品からコストが最も近いものを次の配置候補として選択する。
【００９７】
以下に、具体的な動作の流れを説明する。
【００９８】
用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態において、用品選択部１２３は、各用品についての被約費用を算出する（ステップＳ２００）。用品選択部１２３は、被約費用が負である用品が存在するか否かの確認を行う（ステップＳ２０１）。
【００９９】
被約費用が負である用品が存在する場合（ステップＳ２０１：Ｙｅｓ）、用品選択部１２３は、被約費用が負であり且つ最小の用品を検出し、該用品が存在する区間を選択する（ステップＳ２０２）。そして、用品選択部１２３は、該区間において、被約費用が負であり、現在の配置用品からコストが最も近い用品を選択する（ステップＳ２０３）。
【０１００】
図１０（１）の例では、用品選択部１２３は、被約費用が負であり且つ最小の用品として用品ｘ９を選択する。そして、用品ｘ９が存在する区間３’において、被約費用が負であり、且つ現在配置される用品ｘ７からコストが最も近い用品ｘ８を選択する。
【０１０１】
用品選択部１２３は、選択された用品ｘ８を用品ｘ７に換えて配置した場合の目的関数を算出する（ステップＳ２０４）。図１０（２）に示されるように、算出される目的関数は、９となる。
【０１０２】
用品選択部１２３は、算出した目的関数と、用品変更前の目的関数とを比較して（ステップＳ２０５）、目的関数が改善したか否かの判定を行う（ステップＳ２０６）。図１０（１）及び（２）に示される例では、目的関数が１２から９になり、改善が見られる。
【０１０３】
そこで、用品選択部１２３は、用品ｘ８を配置用品として選択する（ステップＳ２０７）。その後、ステップＳ２０１乃至Ｓ２０６の処理を繰り返す。
【０１０４】
図１０（２）に示されるように、用品ｘ１、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ２を配置候補として選択する。図１０（３）に示されるように、用品ｘ１を用品ｘ２に変更する場合の目的関数は７となり、図１０（２）に示される目的関数９より改善が見られるため、用品選択部１２３は、用品ｘ２を配置用品として選択する。
【０１０５】
図１０（３）に示されるように、用品ｘ２、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ５を配置候補として選択する。図１０（４）に示されるように、用品ｘ４を用品ｘ５に変更する場合の目的関数は５となり、図１０（３）に示される目的関数７より改善が見られるため、用品選択部１２３は、用品ｘ５を配置用品として選択する。
【０１０６】
図１０（４）に示されるように、用品ｘ２、ｘ５、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１１を配置候補として選択する。図１０（５）に示されるように、用品ｘ１０を用品ｘ１１に変更する場合の目的関数は３となり、図１０（４）に示される目的関数５より改善が見られるため、用品選択部１２３は、用品ｘ１１を配置用品として選択する。
【０１０７】
図１０（５）に示されるように、用品ｘ２、ｘ５、ｘ８、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ９を配置候補として選択する。図１０（６）に示されるように、用品ｘ８を用品ｘ９に変更する場合の目的関数は２となり、図１０（５）に示される目的関数３より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１０８】
図１０（６）に示されるように、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１６を配置候補として選択する。図１０（７）に示されるように、用品ｘ１５を用品ｘ１６に変更する場合の目的関数は１となり、図１０（６）に示される目的関数２より改善が見られるため、用品選択部１２３は、用品ｘ１６を配置用品として選択する。
【０１０９】
図１０（７）に示されるように、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１６が配置された状態では、用品選択部１２３は、用品ｘ１２、ｘ１４、ｘ１７、ｘ１８の順で配置候補を選択するが、いずれの用品を配置した場合でも、目的関数に改善が見られない。そこで、用品選択部１２３は、用品ｘ２、ｘ５、ｘ９、ｘ１１、ｘ１３及びｘ１６が配置される状態を配置用品情報として決定し（ステップＳ２０９）、処理を終了する。
【０１１０】
上述した、第１変形動作例においても、ネットワーク設計装置１００の動作例と同様に、一の途中解から次の実行可能解への遷移において、被約費用に基づくことで、目的関数の改善の可能性がある用品を好適に選択することが出来る。従って、最適な用品の配置を決定するための数理計画法における問題を解く際の計算量を低減した上で、好適な解を算出することが出来る。
【０１１１】
（４）第２変形動作例
図１１及び図１２を参照して、ネットワーク設計装置１００の第２変形動作例について説明する。図１１は、第２変形動作例における配置用品の選択動作の流れを示すフローチャートである。図１２は、第２変形動作例における被約費用に基づく用品の選択と、選択された用品を配置した場合の目的関数の算出の態様について示すテーブルの集合である。
【０１１２】
第２変形動作例においては、ネットワーク設計装置１００の用品選択部１２３は、現在配置されている用品からコストが最も近い用品群から順に、被約費用が負であり且つ最小である用品を次の配置候補として選択する。
【０１１３】
以下に、具体的な動作の流れを説明する。
【０１１４】
用品ｘ１、ｘ４、ｘ７、ｘ１０、ｘ１３及びｘ１５が仮に配置された状態において、用品選択部１２３は、各用品についての被約費用を算出する（ステップＳ３００）。用品選択部１２３は、被約費用が負である用品が存在するか否かの確認を行う（ステップＳ３０１）。
【０１１５】
被約費用が負である用品が存在する場合（ステップＳ３０１：Ｙｅｓ）、用品選択部１２３は、現在の配置用品からコストが最も近い用品を一又は複数選択する（ステップＳ３０２）。そして、用品選択部１２３は、選択された用品の内、被約費用が負であり且つ最小の用品を配置候補として選択する（ステップＳ３０３）。
【０１１６】
図１２（１）の例では、用品選択部１２３は、現在配置される用品群ｘ２、ｘ５、ｘ８、ｘ１１、ｘ１４、ｘ１６のうち，被約費用が最小のい用品ｘ８を選択する。
【０１１７】
用品選択部１２３は、選択された用品ｘ８を用品ｘ７に換えて配置した場合の目的関数を算出する（ステップＳ３０４）。図１２（２）に示されるように、算出される目的関数は、９となる。
【０１１８】
用品選択部１２３は、算出した目的関数と、用品変更前の目的関数とを比較して（ステップＳ３０５）、目的関数が改善したか否かの判定を行う（ステップＳ３０６）。図１２（１）及び（２）に示される例では、目的関数が１２から９になり、改善が見られる。
【０１１９】
そこで、用品選択部１２３は、用品ｘ８を配置用品として選択する（ステップＳ３０７）。その後、ステップＳ３０１乃至Ｓ３０６の処理を繰り返す。
【０１２０】
図１２（２）に示されるように、用品ｘ１、ｘ４、ｘ８、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ９を配置候補として選択する。図１２（３）に示されるように、用品ｘ８を用品ｘ９に変更する場合の目的関数は６となり、図１２（２）に示される目的関数９より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１２１】
図１２（３）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ２を配置候補として選択する。図１２（４）に示されるように、用品ｘ１を用品ｘ２に変更する場合の目的関数は４となり、図１２（３）に示される目的関数６より改善が見られるため、用品選択部１２３は、用品ｘ２を配置用品として選択する。
【０１２２】
図１２（４）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１０、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１１を配置候補として選択する。図１２（５）に示されるように、用品ｘ１０を用品ｘ１１に変更する場合の目的関数は２となり、図１２（４）に示される目的関数４より改善が見られるため、用品選択部１２３は、用品ｘ１１を配置用品として選択する。
【０１２３】
図１２（５）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１５が配置された状態では、用品選択部１２３は、次に用品ｘ１７を配置候補として選択する。図１２（６）に示されるように、用品ｘ１５を用品ｘ１７に変更する場合の目的関数は０となり、図１２（５）に示される目的関数２より改善が見られるため、用品選択部１２３は、用品ｘ９を配置用品として選択する。
【０１２４】
図１２（６）に示されるように、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１７が配置された状態では、目的関数が０となるため、用品選択部１２３は、用品ｘ２、ｘ４、ｘ９、ｘ１１、ｘ１３及びｘ１７が配置される状態を配置用品情報として決定し（ステップＳ３０９）、処理を終了する。
【０１２５】
上述した、第２変形動作例においても、ネットワーク設計装置１００の動作例と同様に、一の途中解から次の実行可能解への遷移において、被約費用に基づくことで、目的関数の改善の可能性がある用品を好適に選択することが出来る。従って、最適な用品の配置を決定するための数理計画法における問題を解く際の計算量を低減した上で、好適な解を算出することが出来る。
【０１２６】
以上説明した実施形態に関して、更に以下の付記を開示する。
【０１２７】
（付記１）
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
を備え、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計装置。
【０１２８】
（付記２）
前記装置選択手段は、（１）前記伝送装置の候補から第１の組み合わせを選択し、（２）該第１の組み合わせについて前記数理計画法における問題の目的関数及び被約費用を算出し、（３）算出された前記被約費用に基づいて、前記伝送装置の候補から前記第１の組み合わせとは異なる第２の組み合わせを選択し、（４）該第２の組み合わせについて算出した、前記数理計画法における問題の目的関数と、前記第１の組み合わせについて算出した、前記数理計画法における問題の目的関数とを比較し、（５）目的関数が前記数理計画法における問題の目標値により近い組み合わせを前記線形区間に配置する前記伝送装置の候補の組み合わせとして決定することを特徴とする付記１に記載のネットワーク設計装置。
【０１２９】
（付記３）
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３０】
（付記４）
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３１】
（付記５）
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記伝送装置の候補の組み合わせに含まれる前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３２】
（付記６）
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記第１の組み合わせに含まれている前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３３】
（付記７）
前記装置選択手段は、前記伝送装置の候補の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記伝送装置の候補の組み合わせに含まれない前記伝送装置のうち、該伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする付記１又は２に記載のネットワーク設計装置。
【０１３４】
（付記８）
前記装置選択手段は、前記第１の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記第１の組み合わせに含まれない前記伝送装置のうち、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする付記２に記載のネットワーク設計装置。
【０１３５】
（付記９）
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得工程と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成工程と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択工程
とを備え、
前記装置選択工程は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計方法。
【０１３６】
（付記１０）
コンピュータを、
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
して機能させ、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計プログラム。
【０１３７】
本発明は、上述した実施例に限られるものではなく、請求の範囲及び明細書全体から読み取れる発明の要旨又は思想に反しない範囲で適宜変更可能であり、そのような変更を伴うネットワーク設計装置及び方法などもまた本発明の技術的範囲に含まれるものである。
【符号の説明】
【０１３８】
１００ ネットワーク設計装置、
１１０ 入出力インタフェース、
１１１ 入力部、
１１２ 出力部、
１２０ ＣＰＵ、
１２１ 用品候補選択部、
１２２ 問題生成部、
１２３ 用品選択部、
１３０ メモリ。
【特許請求の範囲】
【請求項１】
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
を備え、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計装置。
【請求項２】
前記装置選択手段は、（１）前記伝送装置の候補から第１の組み合わせを選択し、（２）該第１の組み合わせについて前記数理計画法における問題の目的関数及び被約費用を算出し、（３）算出された前記被約費用に基づいて、前記伝送装置の候補から前記第１の組み合わせとは異なる第２の組み合わせを選択し、（４）該第２の組み合わせについて算出した、前記数理計画法における問題の目的関数と、前記第１の組み合わせについて算出した、前記数理計画法における問題の目的関数とを比較し、（５）目的関数が前記数理計画法における問題の目標値により近い組み合わせを前記線形区間に配置する前記伝送装置の候補の組み合わせとして決定することを特徴とする請求項１に記載のネットワーク設計装置。
【請求項３】
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項４】
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項５】
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記伝送装置の候補の組み合わせに含まれる前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項６】
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記第１の組み合わせに含まれている前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項７】
前記装置選択手段は、前記伝送装置の候補の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記伝送装置の候補の組み合わせに含まれない前記伝送装置のうち、該伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項８】
前記装置選択手段は、前記第１の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記第１の組み合わせに含まれない前記伝送装置のうち、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項９】
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得工程と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成工程と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択工程
とを備え、
前記装置選択工程は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計方法。
【請求項１０】
コンピュータを、
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
して機能させ、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計プログラム。
【請求項１】
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
を備え、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計装置。
【請求項２】
前記装置選択手段は、（１）前記伝送装置の候補から第１の組み合わせを選択し、（２）該第１の組み合わせについて前記数理計画法における問題の目的関数及び被約費用を算出し、（３）算出された前記被約費用に基づいて、前記伝送装置の候補から前記第１の組み合わせとは異なる第２の組み合わせを選択し、（４）該第２の組み合わせについて算出した、前記数理計画法における問題の目的関数と、前記第１の組み合わせについて算出した、前記数理計画法における問題の目的関数とを比較し、（５）目的関数が前記数理計画法における問題の目標値により近い組み合わせを前記線形区間に配置する前記伝送装置の候補の組み合わせとして決定することを特徴とする請求項１に記載のネットワーク設計装置。
【請求項３】
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項４】
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項５】
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記伝送装置の候補の組み合わせに含まれる前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項６】
前記装置選択手段は、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置と同一の前記配置点に配置される前記伝送装置のうち、被約費用が負であり、前記同一の配置点に配置されるものとして前記第１の組み合わせに含まれている前記伝送装置と最も配置コストが近い前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項７】
前記装置選択手段は、前記伝送装置の候補の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記伝送装置の候補の組み合わせに含まれない前記伝送装置のうち、該伝送装置の候補の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記伝送装置の候補として決定することを特徴とする請求項１又は２に記載のネットワーク設計装置。
【請求項８】
前記装置選択手段は、前記第１の組み合わせに含まれる一つの前記伝送装置と最も配置コストが近く且つ前記第１の組み合わせに含まれない前記伝送装置のうち、前記第１の組み合わせについて算出した被約費用が負であり且つ最小の前記伝送装置を、次に前記数理計画法における問題を解く前記第２の組み合わせに含めることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項９】
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得工程と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成工程と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択工程
とを備え、
前記装置選択工程は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計方法。
【請求項１０】
コンピュータを、
線形区間を含むネットワークにおいて、前記線形区間内に含まれる複数の配置点に配置される伝送装置の候補を示す装置候補情報、前記伝送装置の候補の夫々の配置コスト、及び前記線形区間における一又は複数の前記配置点を含む所定の区間における前記伝送装置の配置コストの和である目標コストの夫々を取得する情報取得手段と、
前記装置候補情報、前記配置コスト、及び前記目標コストに基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定するための数理計画法における問題を生成する問題生成手段と、
前記数理計画法における問題を、前記伝送装置の候補のうち少なくとも一つについて解き、得られた目的関数に基づいて、前記線形区間に配置する前記伝送装置の候補の組み合わせを決定する装置選択手段と
して機能させ、
前記装置選択手段は、前記伝送装置の候補の組み合わせについて算出した被約費用に基づいて、次に前記数理計画法における問題を解く前記伝送装置の候補を決定することを特徴とするネットワーク設計プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−７３７０５（Ｐ２０１２−７３７０５Ａ）
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願番号】特願２０１０−２１６４１２（Ｐ２０１０−２１６４１２）
【出願日】平成２２年９月２８日（２０１０．９．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願日】平成２２年９月２８日（２０１０．９．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]