(57)【要約】【課題】制約条件やネットワーク条件が経時的に変化しても所望の設計結果を得ること。【解決手段】ステップＳ１０１，Ｓ１０２では、複数の時期毎のネットワーク条件があらかじめ入力される。ステップＳ１０３，Ｓ１０４では、複数の時期における各コストに関する制約条件を受け付ける。ステップＳ１０５〜Ｓ１１５では、ステップＳ１０１，Ｓ１０２によって入力されたネットワーク条件において、ステップＳ１０３，Ｓ１０４によって受け付けられた制約条件を満たすネットワークを設計する。ステップＳ１１６では、ステップＳ１０５〜Ｓ１１５の設計結果を出力する。【選択図】図１
2010147653.tif 000002
【特許請求の範囲】
【請求項１】
複数の時期毎のネットワーク条件があらかじめ入力される入力工程と、
前記複数の時期における各コストに関する制約条件を受け付ける受付工程と、
前記入力工程によって入力されたネットワーク条件において、前記受付工程によって受け付けられた制約条件を満たすネットワークを設計する設計工程と、
前記設計工程の設計結果を出力する出力工程と、
を含むことを特徴とするネットワーク設計方法。
【請求項２】
前記入力工程では、前記複数の時期毎に異なるデマンドが前記ネットワーク条件として入力されることを特徴とする請求項１に記載のネットワーク設計方法。
【請求項３】
前記設計工程では、前記複数の時期毎に異なるデマンドに基づいてサイトのルーティングを行い、ルーティングを行った各サイトのサイトタイプを、前記制約条件を満たすように変更することを特徴とする請求項２に記載のネットワーク設計方法。
【請求項４】
複数の時期毎のネットワーク条件があらかじめ入力される入力工程と、
前記入力工程によって入力されたネットワーク条件をメモリに記憶する第１記憶工程と、
前記複数の時期における各コストに関する制約条件を受け付ける受付工程と、
前記受付工程によって受け付けられた制約条件をメモリに記憶する第２記憶工程と、
前記第１記憶工程によって記憶されたネットワーク条件および前記第２記憶工程によって記憶された制約条件をメモリから読み出す第１読出工程と、
前記第１読出工程によって読み出されたネットワーク条件において、前記第１読出工程によって読み出された制約条件を満たすネットワークを設計する設計工程と、
前記設計工程の設計結果をメモリに記憶する第３記憶工程と、
前記第３記憶工程によって記憶された設計結果をメモリから読み出す第２読出工程と、
前記第２読出工程によって読み出された設計結果を出力する出力工程と、
を含むことを特徴とするネットワーク設計方法。
【請求項５】
複数の時期毎のネットワーク条件があらかじめ入力される入力手段と、
前記複数の時期における各コストに関する制約条件を受け付ける受付手段と、
前記入力手段によって入力されたネットワーク条件において、前記受付手段によって受け付けられた制約条件を満たすネットワークを設計する設計手段と、
前記設計手段の設計結果を出力する出力手段と、
を備えることを特徴とするネットワーク設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ネットワーク設計を行うネットワーク設計方法およびネットワーク設計装置に関する。
【背景技術】
【０００２】
ＷＤＭ（Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ：波長分割多重）装置を用いる通信システムの設計を行うネットワーク設計装置は、ファイバ条件とデマンドの入力にしたがい、デマンド経路（ルーティング）と各サイトに設置する用品を決定する。たとえば、ネットワーク設計装置は、初年度のコストが最適になるように、デマンド経路と用品を決定する（たとえば、下記特許文献１〜３参照。）。
【０００３】
【特許文献１】米国特許第６７５７４９４号明細書
【特許文献２】米国特許第７０９６１７６号明細書
【特許文献３】米国特許第７１７１１２４号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した従来技術では、ネットワーク投資コストの制約条件やネットワーク条件が経時的に変化した場合に、ネットワーク設計が最適でなくなる場合がある。このため、ネットワークの運用者は、時期毎（たとえば年度毎）の投資方針を反映したネットワーク設計を行うことができないという問題がある。
【０００５】
たとえば、初年度は安価な構成となるが、将来の増設コストが膨大になってトータルコストが増大し、将来的には膨大な投資が必要となる場合がある。また、最終年度に最適化したネットワーク設計を行うと、初年度はＷＤＭ敷設による投資額が大きいため、年度毎の投資額がアンバランスになる場合がある。
【０００６】
また、ネットワーク条件の経時的な変化が考慮されていないため、ネットワークの運用開始後（たとえば設置２年目）においてネットワーク条件が部分的に変更された場合は、既に敷設した用品を含めて再度全体設計を行わなければならない。このため、２年目において、初年度に既に敷設されている用品の交換が必要になることがある。
【０００７】
開示のネットワーク設計方法およびネットワーク設計装置は、上述した問題点を解消するものであり、制約条件やネットワーク条件が経時的に変化しても所望の設計結果を得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、開示技術は、複数の時期毎のネットワーク条件があらかじめ入力され、前記複数の時期における各コストに関する制約条件を受け付け、入力されたネットワーク条件において、受け付けられた制約条件を満たすネットワークを設計し、設計結果を出力することを要件とする。
【０００９】
上記構成によれば、複数の時期毎のネットワーク条件および複数の時期における各コストに関する制約条件を用いることで、制約条件やネットワーク条件の経時的な変化を設計結果に反映させることができる。
【発明の効果】
【００１０】
このネットワーク設計方法およびネットワーク設計装置によれば、制約条件やネットワーク条件が経時的に変化しても所望の設計結果を得ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１１】
以下に添付図面を参照して、このネットワーク設計方法およびネットワーク設計装置の好適な実施の形態を詳細に説明する。このネットワーク設計方法およびネットワーク設計装置は、複数の時期毎のネットワーク条件および複数の時期における各コストに関する制約条件を入力パラメータとして用いる。これにより、制約条件やネットワーク条件の経時的な変化を設計結果に反映させることができる。
【００１２】
（実施の形態）
図１は、実施の形態にかかるネットワーク設計方法の一例を示すフローチャートである。図１に示すように、実施の形態にかかるネットワーク設計装置は、まず、ネットワーク条件（図２参照）の入力要求をユーザに対して表示する（ステップＳ１０１）。つぎに、ユーザからネットワーク条件が入力されたか否かを判断し（ステップＳ１０２）、ネットワーク条件が入力されるまで待つ（ステップＳ１０２：Ｎｏのループ）。
【００１３】
ステップＳ１０２において、ネットワーク条件が入力されると（ステップＳ１０２：Ｙｅｓ）、制約条件（図３参照）の入力要求をユーザに対して表示する（ステップＳ１０３）。これに対して、ネットワーク設計装置のユーザは、制約条件として「初年度コスト最小」、「全年度コスト閾値以下」および「全年度累計コスト最小」のうちのいずれかを選択してネットワーク設計装置へ入力できるとする。
【００１４】
つぎに、ユーザから制約条件が入力されたか否かを判断し（ステップＳ１０４）、制約条件が入力されるまで待つ（ステップＳ１０４：Ｎｏのループ）。制約条件が入力されると（ステップＳ１０４：Ｙｅｓ）、ステップＳ１０４によって入力された制約条件が「初年度コスト最小」であるか否かを判断する（ステップＳ１０５）。
【００１５】
ステップＳ１０５において、入力された制約条件が「初年度コスト最小」である場合（ステップＳ１０５：Ｙｅｓ）は、所定の手順によりコア設計を行い（ステップＳ１０６）、コア設計の結果に基づいてＲＥＧ配置を行う（ステップＳ１０７）。つぎに、ステップＳ１０６によるコア設計およびステップＳ１０７によるＲＥＧ配置によって初年度のコストが最小となったか否かを判断する（ステップＳ１０８）。
【００１６】
ステップＳ１０８において、初年度のコストが最小となっていない場合（ステップＳ１０８：Ｎｏ）はステップＳ１０６へ戻って処理を続行する。初年度のコストが最小となった場合（ステップＳ１０８：Ｙｅｓ）はステップＳ１１６へ移行して処理を続行する。
【００１７】
ステップＳ１０５において、入力された制約条件が「初年度コスト最小」でない場合（ステップＳ１０５：Ｎｏ）は、ステップＳ１０４によって入力された制約条件が「全年度コスト閾値以下」であるか否かを判断する（ステップＳ１０９）。
【００１８】
ステップＳ１０９において、入力された制約条件が「全年度コスト閾値以下」である場合（ステップＳ１０９：Ｙｅｓ）は、所定の手順によりコア設計を行い（ステップＳ１１０）、コア設計の結果に基づいてＲＥＧ配置を行う（ステップＳ１１１）。つぎに、ステップＳ１１０によるコア設計およびステップＳ１１１によるＲＥＧ配置によって全年度のコストが閾値以下になったか否かを判断する（ステップＳ１１２）。
【００１９】
全年度のコストが閾値以下となっていない場合（ステップＳ１１２：Ｎｏ）はステップＳ１１０へ戻って処理を続行する。全年度のコストが閾値以下となった場合（ステップＳ１１２：Ｙｅｓ）はステップＳ１１６へ移行して処理を続行する。
【００２０】
ステップＳ１０９において、入力された制約条件が「全年度コスト閾値以下」でない場合（ステップＳ１０９：Ｎｏ）は、所定の手順によりコア設計を行い（ステップＳ１１３）、コア設計の結果に基づいてＲＥＧ配置を行う（ステップＳ１１４）。つぎに、ステップＳ１１３によるコア設計およびステップＳ１１４によるＲＥＧ配置によって全年度の累計コストが最小になったか否かを判断する（ステップＳ１１５）。
【００２１】
全年度の累計コストが最小となっていない場合（ステップＳ１１５：Ｎｏ）はステップＳ１１３へ戻って処理を続行する。全年度の累計コストが最小となった場合（ステップＳ１１５：Ｙｅｓ）はステップＳ１１６へ移行して処理を続行する。つぎに、設計結果をユーザに対して出力し（ステップＳ１１６）、一連の処理を終了する。
【００２２】
なお、ステップＳ１１６によって設計結果をユーザに対して出力した後に、制約条件を再度選択して入力すべき旨のメッセージをユーザに対して表示し、ステップＳ１０４へ戻って処理を続行してもよい。これにより、ユーザは、まだ選択していない制約条件をネットワーク設計装置へ入力して、複数の制約条件の設計結果を簡単に得ることができる。
【００２３】
図２は、ネットワーク条件の一例を示す図である。図１に示したステップＳ１０１において、ネットワーク設計装置は、たとえばテーブル２００の項目２１０および必須情報２２０と、項目２１０および必須情報２２０について入力すべき旨のメッセージと、をユーザに対して表示する。また、ユーザが任意に入力可能なオプション情報２３０がある場合は、オプション情報２３０と、オプション情報２３０も入力可能である旨のメッセージをユーザに対して表示してもよい。
【００２４】
項目２１０に示すように、ネットワーク条件としては、たとえばファイバ情報、サイト情報、デマンド情報などが用いられる。ファイバ情報とは、サイト間を接続する光ファイバに関する情報である。ファイバ情報には、必須情報２２０としてファイバ種、距離、スパンロス、分散値、ＰＭＤ（Ｐｏｌａｒｉｚａｔｉｏｎ  Ｍｏｄｅ  Ｄｉｓｐｅｒｓｉｏｎ：偏波モード分散）値などが含まれている。
【００２５】
サイト情報は、局舎（ノード）として設けられるサイトに関する情報である。サイト情報には、必須情報２２０としてツール（ネットワーク設計装置）による算出の有り／無しの指定情報が含まれている。また、サイト情報に関しては、オプション情報２３０として指定したいサイトタイプ、許容するサイトタイプ、禁止サイトタイプが含まれている。
【００２６】
デマンド情報は、要求されるネットワークパスに関する情報である。デマンド情報には、必須情報２２０としてＦＲＯＭ／ＴＯ（始点／終点）サイト、収容サービス種、プロテクションの有無が含まれている。また、デマンド情報に関しては、オプション情報２３０として使用したい用品、指定したいルート、指定したい使用波長などが含まれている。
【００２７】
また、これらのネットワーク条件には、時期によって異なるものが含まれている。時期によって異なるネットワーク条件は、複数の時期毎に図１に示したステップＳ１０１においてあらかじめ入力される。複数の時期とは、複数の日（たとえば１１日〜１３日）や、複数の月（たとえば４月〜５月）や、複数の年度（１年度〜３年度）などである。たとえば、サイト情報やデマンド情報は、顧客の増減やトラフィック量などに応じて年度によって異なるネットワーク条件である。
【００２８】
図３は、制約条件の一例を示す図である。図１で説明したように、ここでは、制約条件としてテーブル３００に示す「初年度コスト最小」、「全年度コスト閾値以下」および「全年度累計コスト最小」のうちのいずれかをユーザが選択してネットワーク設計装置へ入力できるようにする。「初年度コスト最小」とは、初年度（１年目）のネットワーク設計に基づく投資コストが最小となる制約条件である。また、初年度に限らず、複数の時期のうちのユーザによって指定された特定の時期のネットワーク設計に基づく投資コストが最小となる制約条件としてもよい。
【００２９】
「全年度コスト閾値以下」とは、各区年度のネットワーク設計に基づく各投資コストがすべて閾値以下となる制約条件である。「全年度累計コスト最小」とは、各区年度のネットワーク設計に基づく各投資コストの合計が最小となる制約条件である。この他にも、制約条件として、「各年度のトータルコストの変化量最小」など、複数の時期における各コストに関する制約条件を用いることができる。
【００３０】
図４は、設計結果の一例を示す図である。図１に示したステップＳ１０３においては、ネットワーク設計装置は、たとえばテーブル４００に示すような設計結果をユーザに対して出力する。テーブル４００に示す設計結果は、項目４１０と、項目４１０毎に対応する出力情報４２０と、を含んでいる。
【００３１】
項目４１０には、サイト毎のサイトタイプ（ＯＡＤＭ、ＥＸＰＲＥＳＳ、ＩＬＡ、Ｂｙｐａｓｓなど）、サイト毎の設置用品（図番、価格、消費電力など）、サイト毎の用品構成図（ラック搭載図やケーブリング図など）、デマンドルーティング、デマンド毎の光特性（ＯＳＮＲ、分散マップ、パワーレベルなど）、リーチャビリティ（各サイトから他サイトへの光到達性、到達可能区間の光特性など）が含まれている。
【００３２】
つぎに、図１に示したステップＳ１０８，Ｓ１１２，Ｓ１１５において用いるコストの評価方法について説明する。時期ｔにおけるサイトｎ１からサイトｎ２までのデマンドｋをＤｌ（ｎ１，ｎ２，ｔ）とする。Ｄｌ（ｎ１，ｎ２，ｔ）＝１の場合は、時期ｔにおけるサイトｎ１からサイトｎ２までのデマンドｋが存在することを示す。Ｄｌ（ｎ１，ｎ２，ｔ）＝０の場合は、時期ｔにおけるサイトｎ１からサイトｎ２までのデマンドｋが存在しないことを示す。
【００３３】
デマンドｋの最大値をＫとすると１≦ｋ≦Ｋとなる。Ｋは、すべての時期ｔのデマンドｋの合計である。任意の時期ｔにおけるネットワーク全体の総デマンド数をΣＤｋ（ｎ１，ｎ２，ｔ）とする。ｄΣＤｌ／ｄｔは総デマンド数の微分変化量を示す。
【００３４】
サイトはＩｉ（ｔ）で示す。Ｉｉ（ｔ）＝１の場合はサイトｉが時期ｔに存在することを示す。Ｉｉ（ｔ）＝１０の場合はサイトｉが時期ｔに存在しないことを示す。リンクはＬｋ（Ｉｉ，Ｉｊ，ｔ）で示す。Ｌｋ（Ｉｉ，Ｉｊ，ｔ）＝１の場合はサイトｉからサイトｊへのリンクが時期ｔに存在することを示す。Ｌｋ（Ｉｉ，Ｉｊ，ｔ）＝０の場合はサイトｉからサイトｊへのリンクが時期ｔに存在しないことを示す。
【００３５】
サイトＩとリンクＬの間にはつぎの関係が成り立つ。まず、サイトあるいはリンクがないところにデマンドの経路を割り当てることはできない。つぎに、サイトがないところにサイトタイプを割り当てることはできない。すなわち、サイトＩとリンクＬの間の関係は、ネットワーク設計に対する物理的制約をもたらす。
【００３６】
サイトの入出力情報は、ＳｉｔｅＴｙｐｅｉｎ（Ｎｉ，ｔ）およびＳｉｔｅＴｙｐｅｏｕｔ（Ｎｉ，ｔ）によって示す。具体的には、サイトｉの時期ｔにおける入力時のサイトタイプはＳｉｔｅＴｙｐｅｉｎ（Ｎｉ，ｔ）で示す。ＳｉｔｅＴｙｐｅｉｎ（Ｎｉ，ｔ）には、ＯＡＤＭ、ＥＸＰＲＥＳＳ、ＩＬＡなどの選択可能なサイトタイプが設定される。
【００３７】
サイトｉの時期ｔにおける出力時のサイトタイプはＳｉｔｅＴｙｐｅｏｕｔ（Ｎｉ，ｔ）で示す。ＳｉｔｅＴｙｐｅｉｎ（Ｎｉ，ｔ）およびＳｉｔｅＴｙｐｅｏｕｔ（Ｎｉ，ｔ）によってサイトコストが決まる。したがって、サイトコストは時期ｔの関数になる。
【００３８】
デマンド数とネットワークの関係はａＤｋ，ｌ（ｔ）によって示す。ａＤｋ，ｌ（ｔ）＝１の場合はデマンドＤｋがリンクＩを通過することを示す。ａＤｋ，ｌ（ｔ）＝０の場合はデマンドＤｋがリンクＩを通過しないことを示す。デマンドＤｋ（ｉ，ｊ，ｔ）に対して通過するリンクに対応するリストＬｉｓｔ｛ａ  ｄ、Ｉ（ｔ）｝によってデマンドの経路を表現する。また、デマンドの経路に対するデマンド数をパラメータＤＰｌ（ｉ，ｊ，ｔ）によって示す。
【００３９】
また、デマンド数に対するリーチャビリティ数をＮＬｐｉｊ＝ｆ（Ｎｃｉｊｋ）によって示す。デマンドＤｋ（ｉ，ｊ，ｔ）に対して割り当てたデマンド経路のリーチャビリティ数を計算し、デマンドを構成するリーチャビリティ数（ライトパス数）を示す。たとえば、あるデマンドが３つのリーチャビリティから構成される場合は２Ｒｅｇを意味する。
【００４０】
また、デマンドＤｋ（ｉ，ｊ，ｔ）を構成するリーチャビリティをＲｔｙｐｅＤｋｌ（ｔ）ｌによって示す。あるデマンドに経路が割り当てられた場合にその経路を構成するリーチャビリティに順番を付与するとｌ（ｌ＝１〜ｍ）番目のタイプが何であるかを表現する。ｉが異なる箇所にはＲｅｇが割り当てられるが、Ｒｔｙｐｅが異なることがあるかどうかはＲｅｇがサポートしているかどうかによって決まる。
【００４１】
図１のステップＳ１０８，Ｓ１１２，Ｓ１１５においては、評価関数のパラメータとしてＣｃｏｒｅｉｊとＣｒｅｇｉｊを用いる。Ｃｃｏｒｅｉｊは、サイトｉとサイトｊの間の区間のコアコストである。Ｃｃｏｒｅｉｊ＝ｆｃｏｒｅ（Ｎｃｉｊｋ）とすると、ｆｃｏｒｅ（Ｎｃｉｊｋ）＝ΣＣｌ×Ｃｃｏｓｔｌとなる。Ｃｌはサイトタイプｌの数であり、Ｃｃｏｓｔｌはサイトタイプｌの単価である。
【００４２】
デマンドコストＣｒｅｇｔｏｔａｌ（ｔ）は、各デマンドを構成するデマンドリーチャビリティタイプにより決まる。デマンドリーチャビリティが同一である場合には、Ｃｒｅｇｔｏｔａｌ＝ΣｉｊＣｒｅｇ  ＤＰ（Ｉｊ）（ＮＬＰｉｊ−１）となる。最終的な評価関数としてはＣｃｏｒｅｉｊとＣｒｅｇｔｏｔａｌの合計（トータルコスト）を用いる。
【００４３】
このように、実施の形態にかかるネットワーク設計装置は、複数の時期毎のネットワーク条件があらかじめ入力され、複数の時期における各コストに関する制約条件を受け付ける。そして、ネットワーク設計装置は、入力されたネットワーク条件において、受け付けられた制約条件を満たすネットワークを設計し、設計結果を出力する。
【００４４】
これにより、制約条件やネットワーク条件の経時的な変化を設計結果に反映させることができる。このため、制約条件やネットワーク条件が経時的に変化しても所望の設計結果を得ることができる。また、各コストに関する制約条件を含む複数の制約条件のうちの少なくともいずれかの選択を受け付けるようにすることで、ネットワークの運用者は、時期毎の投資方針に応じたネットワーク設計を容易に行うことができる。つぎに、図５〜図２４を用いて、ネットワーク設計の具体例を説明する。
【００４５】
図５は、ネットワーク条件（サイト条件）の一例を示す図である。図５の符号５１０（初期状態）に示すように、１６個のサイトＡ〜Ｄ，５１１〜５１４，５２１〜５２４，５３１〜５３４を含むリニアネットワークを設計するものとする。サイトＡ，Ｂ，Ｃ，Ｄのそれぞれは、光信号のＡｄｄ／Ｄｒｏｐが可能なＯＡＤＭノードである。
【００４６】
サイトＡ−Ｂ間にはサイト５１１〜５１４が接続されている。サイトＢ−Ｃ間にはサイト５２１〜５２４が接続されている。サイトＣ−Ｄ間にはサイト５３１〜５３４が接続されている。サイト５１３，５２３，５３３のそれぞれは、ＥＸＰＲＥＳＳ（図では「ＥＸＰ」と表記。以下同様。）となっている。ＥＸＰＲＥＳＳとは、ＲＥＧ（光−電気−光の再生ユニット）が収容可能なＯＡＤＭである。
【００４７】
ＥＸＰＲＥＳＳはコストが高い一方、雑音劣化を最小に抑えることができる。このため、ＥＸＰＲＥＳＳを配置した場合はデマンドあたりのＲＥＧの必要数を少なくすることができる。「＊」を付したサイト５１１，５１２，５１４，５２１，５２２，５２４，５３１，５３２，５３４のそれぞれには、ＩＬＡおよびＥＸＰＲＥＳＳのいずれかを選択して配置可能である。ＩＬＡは、コストが低い一方、雑音劣化が大きくなるアンプである。
【００４８】
つぎに、各サイトに配置するサイトタイプ毎のコスト条件について説明する。サイトにＯＡＤＭを配置した場合のコストを７とする。サイトにＥＸＰＲＥＳＳを配置した場合のコストを５とする。サイトにＩＬＡを配置した場合のコストを１とする。また、ＥＸＰＲＥＳＳなどにＲＥＧを１つ収容した場合のコストを１とする。
【００４９】
図６は、ネットワーク条件（性能条件）の一例を示す図である。図６に示すテーブル６００は、ネットワーク条件に含まれる性能条件として、デマンド毎のＲＥＧの必要数を示している。テーブル６００においては、任意のデマンドが経由するＩＬＡの数６１０に対するＲＥＧの必要数を、デマンドが経由するＯＡＤＭ区間数６２０毎に示している。
【００５０】
たとえば、デマンドがサイトＡ〜Ｂを経由し（ＯＡＤＭ区間数１）、サイトＡ−Ｂ間のＩＬＡが３つである場合は、ＲＥＧの必要数は１個になる。また、デマンドがサイトＢ〜Ｄを経由し（ＯＡＤＭ区間数２）、サイトＢ−Ｄ間のＩＬＡが４つである場合は、ＲＥＧの必要数は２個になる。また、デマンドがサイトＡ〜Ｄを経由し（ＯＡＤＭ区間数３）、サイトＡ−Ｄ間のＩＬＡが８つである場合は、ＲＥＧの必要数は５個になる。
【００５１】
図７は、ネットワーク条件（デマンド条件）の一例を示す図である。図７に示すテーブル７００は、ネットワーク条件に含まれるデマンド条件として、ＯＡＤＭ区間毎のデマンド数を示している。テーブル７００においては、ＯＡＤＭ区間毎のデマンド数を、年度ｔ＝１，２，３（１年目〜３年目）毎に示している。たとえばサイトＡ−Ｂ間のデマンド数は、１年目においては１０、２年目においては１５、３年目においては２０である。
【００５２】
図８は、デマンド条件に基づくルーティングを示す図である。ルーティングにおいては、少なくとも図７に示したデマンド条件を満たすように隣接する各ＯＡＤＭ区間のデマンド数を決定する（テーブル８００）。サイトＡ−Ｂ間、サイトＢ−Ｃ間、サイトＣ−Ｄ間、サイトＡ−Ｃ間の１〜３年目と、サイトＢ−Ｄ間の１，２年目と、サイトＡ−Ｄ間の１年目は、図７に示したデマンド条件をちょうど満たすようにデマンド数を配置している。
【００５３】
また、サイトＢ−Ｄ間の３年目は、デマンド条件の９に対してデマンド数１５を配置している。また、サイトＡ−Ｄ間の２年目は、デマンド条件の０に対してデマンド数１０を配置している。また、サイトＡ−Ｄ間の３年目は、デマンド条件の１０に対してデマンド数１５を配置している。「Ｔｏｔａｌ」は、１〜３年目のそれぞれにおけるデマンド数の合計を、隣接するＯＡＤＭ区間毎に示している。
【００５４】
「Ｔｏｔａｌ」に示すように、１年目のデマンド数の合計は１６であり、１年目においてはサイトＡ−Ｂ間にデマンド数１０、サイトＢ−Ｃ間にデマンド数１、サイトＣ−Ｄ間にデマンド数５が割り当てられている。また、２年目のデマンド数の合計は５４であり、２年目においてはサイトＡ−Ｂ間にデマンド数３８、サイトＢ−Ｃ間にデマンド数３４、サイトＣ−Ｄ間にデマンド数１６が割り当てられている。また、３年目のデマンド数の合計は８１であり、サイトＡ−Ｂ間にデマンド数４８、サイトＢ−Ｃ間にデマンド数５６、サイトＣ−Ｄ間にデマンド数３５が割り当てられている。
【００５５】
図９は、サイトタイプ選択の一例を示す図（その１）である。図９において、図５に示した構成と同様の構成については同一の符号を付して説明を省略する。図９の符号９１０に示すように、サイトタイプ選択においては、まず、コアコストが最小となるように「＊」を付した各サイト（サイト５１１，５１２，５１４，５２１，５２２，５２４，５３１，５３２，５３４）のすべてに対してＩＬＡを割り当てる仮決めを行う。
【００５６】
図１０は、図９に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。図１０のテーブル１０００は、図６に示したデマンド毎のＲＥＧの必要数と、図９に示したサイトタイプの仮決めに基づいて算出したデマンドあたりのＲＥＧ数を示している。ここでは、各ＯＡＤＭ区間のうちのサイトＡ−Ｂ間、サイトＡ−Ｃ間およびサイトＡ−Ｄ間のＲＥＧ数について説明する。
【００５７】
テーブル１０００に示すように、サイトＡ−Ｂ間は、ＯＡＤＭ区間数が１でありＩＬＡ数が３であるため、デマンドあたりに必要なＲＥＧ数は１である（図６参照）。また、サイトＡ−Ｂ間の１年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｂ間における１年目に必要なＲＥＧ数は１×１０＝１０である。
【００５８】
また、サイトＡ−Ｂ間の２年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｂ間における２年目に必要なＲＥＧ数は１×１５＝１５である。また、サイトＡ−Ｂ間の３年目のデマンド数は２０である（図８参照）ため、サイトＡ−Ｂ間における３年目に必要なＲＥＧ数は１×２０＝２０である。
【００５９】
また、テーブル１０００に示すように、サイトＡ−Ｃ間は、ＯＡＤＭ区間数が２でありＩＬＡ数が６であるため、デマンドあたりに必要なＲＥＧ数は３である（図６参照）。また、サイトＡ−Ｃ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｃ間における１年目に必要なＲＥＧ数は３×０＝０である。
【００６０】
また、サイトＡ−Ｃ間の２年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における２年目に必要なＲＥＧ数は３×１３＝３９である。また、サイトＡ−Ｃ間の３年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における３年目に必要なＲＥＧ数は３×１３＝３９である。
【００６１】
また、テーブル１０００に示すように、サイトＡ−Ｄ間は、ＯＡＤＭ区間数が３でありＩＬＡ数が９であるため、デマンドあたりに必要なＲＥＧ数は５である（図６参照）。また、サイトＡ−Ｄ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｄ間における１年目に必要なＲＥＧ数は５×０＝０である。
【００６２】
また、サイトＡ−Ｄ間の２年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｄ間における２年目に必要なＲＥＧ数は５×１０＝５０である。また、サイトＡ−Ｄ間の３年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｄ間における３年目に必要なＲＥＧ数は５×１５＝７５である。
【００６３】
図１１は、図９に示した設計におけるトータルコストを示す図である。図１１のテーブル１１００は、図９に示したサイトタイプの仮決めと、図１０に示したＯＡＤＭ区間毎に必要なＲＥＧ数と、に基づいて算出したトータルコストを示している。
【００６４】
１年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が３個、ＩＬＡ（コスト１）が９個、ＲＥＧ（コスト１）が３２個配置される。したがって、１年目のトータルコストは７×４＋５×３＋１×９＋１×３２＝８４になる。１年目（初年度）の前年度は存在しないため、１年目の前年度とのトータルコストの差は８４とする。また、１年目のトータルコスト差の変化量は０とする。
【００６５】
２年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が３個、ＩＬＡ（コスト１）が９個、ＲＥＧ（コスト１）が１７６個配置される。したがって、２年目のトータルコストは７×４＋５×３＋１×９＋１×１７６＝２２８になる。２年目の前年度（１年目）とのトータルコストの差は２２８−８４＝１４４である。
【００６６】
また、１年目の前年度とのトータルコストの差は８４であり、２年目の前年度（１年目）とのトータルコストの差は１４４であるため、１年目から２年目のトータルコスト差の変化量は１４４−８４＝６０である。
【００６７】
３年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が３個、ＩＬＡ（コスト１）が９個、ＲＥＧ（コスト１）が２７８個配置される。したがって、３年目のトータルコストは７×４＋５×３＋１×９＋１×２７８＝３３０になる。３年目の前年度（２年目）とのトータルコストの差は３３０−２２８＝１０２である。
【００６８】
また、２年目の前年度（１年目）とのトータルコストの差は１４４であり、３年目の前年度（２年目）とのトータルコストの差は１０２であるため、２年目から３年目のトータルコスト差の変化量は１０２−１４４＝−４２である。したがって、各年度におけるトータルコスト差の変化量（絶対値）の最大値は、｜６０｜＞｜−４２｜のため６０となる。
【００６９】
図１２は、サイトタイプ選択の一例を示す図（その２）である。図９に示した状態から、各ＯＡＤＭ区間のうちの、１年目のデマンド数が最も多いＯＡＤＭ区間に対して、リーチャビリティ（たとえばＯＳＮＲ）が向上するようにサイトの選択を変更する。ここでは、Ａ−Ｂ間のデマンド数が１０で最も多い（図７参照）ため、符号１２１０に示すように、Ａ−Ｂ間のサイト５１１をＩＬＡからＥＸＰＲＥＳＳに変更する。
【００７０】
図１３は、図１２に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。図１３のテーブル１３００は、図６に示したデマンド毎のＲＥＧの必要数と、図１２に示したサイトタイプの仮決めに基づいて算出したデマンドあたりのＲＥＧ数を示している。ここでは、各ＯＡＤＭ区間のうちのサイトＡ−Ｂ間、サイトＡ−Ｃ間およびサイトＡ−Ｄ間のＲＥＧ数について説明する。
【００７１】
テーブル１３００に示すように、サイトＡ−Ｂ間は、ＯＡＤＭ区間数が１でありＩＬＡ数が２であるため、デマンドあたりに必要なＲＥＧ数は０である（図６参照）。また、サイトＡ−Ｂ間の１年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｂ間における１年目に必要なＲＥＧ数は０×１０＝０である。
【００７２】
また、サイトＡ−Ｂ間の２年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｂ間における２年目に必要なＲＥＧ数は０×１５＝０である。また、サイトＡ−Ｂ間の３年目のデマンド数は２０である（図８参照）ため、サイトＡ−Ｂ間における３年目に必要なＲＥＧ数は０×２０＝０である。
【００７３】
また、テーブル１３００に示すように、サイトＡ−Ｃ間は、ＯＡＤＭ区間数が２でありＩＬＡ数が５であるため、デマンドあたりに必要なＲＥＧ数は２である（図６参照）。また、サイトＡ−Ｃ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｃ間における１年目に必要なＲＥＧ数は２×０＝０である。
【００７４】
また、サイトＡ−Ｃ間の２年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における２年目に必要なＲＥＧ数は２×１３＝２６である。また、サイトＡ−Ｃ間の３年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における３年目に必要なＲＥＧ数は２×１３＝２６である。
【００７５】
また、テーブル１３００に示すように、サイトＡ−Ｄ間は、ＯＡＤＭ区間数が３でありＩＬＡ数が８であるため、デマンドあたりに必要なＲＥＧ数は５である（図６参照）。また、サイトＡ−Ｄ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｄ間における１年目に必要なＲＥＧ数は５×０＝０である。
【００７６】
また、サイトＡ−Ｄ間の２年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｄ間における２年目に必要なＲＥＧ数は５×１０＝５０である。また、サイトＡ−Ｄ間の３年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｄ間における３年目に必要なＲＥＧ数は５×１５＝７５である。
【００７７】
図１４は、図１２に示した設計におけるトータルコストを示す図である。図１４のテーブル１４００は、図１２に示したサイトタイプの仮決めと、図１３に示したＯＡＤＭ区間毎に必要なＲＥＧ数と、に基づいて算出したトータルコストを示している。
【００７８】
１年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が４個、ＩＬＡ（コスト１）が８個、ＲＥＧ（コスト１）が２２個配置される。したがって、１年目のトータルコストは７×４＋５×４＋１×８＋１×２２＝７８になる。１年目（初年度）の前年度は存在しないため、１年目の前年度とのトータルコストの差（年度間コスト差）は７８とする。また、１年目のトータルコスト差の変化量は０とする。
【００７９】
２年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が４個、ＩＬＡ（コスト１）が８個、ＲＥＧ（コスト１）が１４８個配置される。したがって、２年目のトータルコストは７×４＋５×４＋１×８＋１×１４８＝２０４になる。２年目の前年度（１年目）とのトータルコストの差は２０４−７８＝１２６である。
【００８０】
また、１年目の前年度とのトータルコストの差は７８であり、２年目の前年度（１年目）とのトータルコストの差は１２６であるため、１年目から２年目のトータルコスト差の変化量は１２６−７８＝４８である。
【００８１】
３年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が４個、ＩＬＡ（コスト１）が８個、ＲＥＧ（コスト１）が２４５個配置される。したがって、３年目のトータルコストは７×４＋５×４＋１×８＋１×２４５＝３０１になる。３年目の前年度（２年目）とのトータルコストの差は３０１−２０４＝９７である。
【００８２】
また、２年目の前年度（１年目）とのトータルコストの差は１２６であり、３年目の前年度（２年目）とのトータルコストの差は９７であるため、２年目から３年目のトータルコスト差の変化量は９７−１２６＝−２９である。したがって、各年度におけるトータルコスト差の変化量（絶対値）の最大値は、｜４８｜＞｜−２９｜のため４８となる。
【００８３】
図１５は、各年度のトータルコスト差の変化量の比較を示す図（その１）である。図１５に示すテーブル１５００は、図１１に示したトータルコスト差の変化量と、図１４に示したトータルコスト差の変化量と、を比較するテーブルである。ネットワーク設計装置は、各トータルコスト差の変化量（絶対値）の最大値を比較する。
【００８４】
そして、ネットワーク設計装置は、最新の設計におけるトータルコスト差の変化量（符号１５２０）の最大値が、前回の設計におけるトータルコスト差の変化量（符号１５１０）の最大値よりも減少していれば、最新の設計を新たな仮決め設計として採用する。ここでは、符号１５２０に示すトータルコスト差の変化量の最大値４８が、符号１５１０に示すトータルコスト差の変化量１５１０の最大値６０よりも減少しているため、ネットワーク設計装置は、図１２に示した設計を新たな仮決め設計として採用する。
【００８５】
図１６は、サイトタイプ選択の一例を示す図（その３）である。ネットワーク設計装置は、図１２〜図１５に示した動作を、サイトタイプを未決定の各ＯＡＤＭ区間において行う。まず、符号１６１０に示すように、サイトＢ−Ｃ間のサイト５２１をＩＬＡからＥＸＰＲＥＳＳに変更する。つぎに、符号１６２０に示すように、サイトＣ−Ｄ間のサイト５３１をＩＬＡからＥＸＰＲＥＳＳに変更する。
【００８６】
つぎに、符号１６３０に示すように、サイトＡ−Ｂ間のサイト５１２をＩＬＡからＥＸＰＲＥＳＳに変更する。つぎに、符号１６４０に示すように、サイトＢ−Ｃ間のサイト５２２をＩＬＡからＥＸＰＲＥＳＳに変更する。つぎに、符号１６５０に示すように、サイトＣ−Ｄ間のサイト５３２をＩＬＡからＥＸＰＲＥＳＳに変更する。
【００８７】
つぎに、符号１６６０に示すように、サイトＡ−Ｂ間のサイト５１４をＩＬＡからＥＸＰＲＥＳＳに変更する。つぎに、符号１６７０に示すように、サイトＢ−Ｃ間のサイト５２４をＩＬＡからＥＸＰＲＥＳＳに変更する。つぎに、符号１６８０に示すように、サイトＣ−Ｄ間のサイト５３４をＩＬＡからＥＸＰＲＥＳＳに変更する。
【００８８】
また、ネットワーク設計装置は、サイトをＩＬＡからＥＸＰＲＥＳＳに変更するたびに、最新の設計におけるトータルコスト差の変化量の最大値と、前回の設計におけるトータルコスト差の変化量の最大値とを比較する。そして、ネットワーク設計装置は、最新の設計におけるトータルコスト差の変化量の最大値が前回の設計におけるトータルコスト差の変化量の最大値よりも減少していない場合は、前回の設計を設計結果として確定させる。
【００８９】
図１７は、各年度のトータルコスト差の変化量の比較を示す図（その２）である。図１７において、図１５に示した部分と同様の部分については同一の符号を付して説明を省略する。図１７のテーブル１７００は、図１６の符号９１０，１２１０，１６１０，１６２０，１６３０，１６４０，１６５０，１６６０，１６７０，１６８０の各状態におけるトータルコスト差の変化量をそれぞれ年度毎に示している（符号１５１０，１５２０，１７１０，１７２０，１７３０，１７４０，１７５０，１７６０，１７７０，１７８０）。
【００９０】
図１６の符号１６１０に示した状態においては、最新のトータルコスト差の変化量（符号１７１０）の最大値３１が、前回のトータルコスト差の変化量１５２０の最大値４８よりも減少している。このため、図１６の符号１６１０に示した設計を新たな仮決め設計として採用する。つぎに、図１６の符号１６２０に示した状態へ移行する。
【００９１】
図１６の符号１６２０に示した状態においては、最新のトータルコスト差の変化量（符号１７２０）の最大値２６が、前回のトータルコスト差の変化量１７１０の最大値３１よりも減少している。このため、図１６の符号１６２０に示した設計を新たな仮決め設計として採用する。つぎに、図１６の符号１６３０に示した状態へ移行する。
【００９２】
図１６の符号１６３０に示した状態においては、最新のトータルコスト差の変化量（符号１７３０）の最大値１３が、前回のトータルコスト差の変化量１７２０の最大値２６よりも減少している。このため、図１６の符号１６３０に示した設計を新たな仮決め設計として採用する。つぎに、図１６の符号１６４０に示した状態へ移行する。
【００９３】
図１６の符号１６４０に示した状態においては、最新のトータルコスト差の変化量（符号１７４０）の最大値２１が、前回のトータルコスト差の変化量１７３０の最大値１３よりも増加している。このため、図１６の符号１６３０に示した設計を設計結果として確定させ、設計結果をユーザへ出力する。
【００９４】
図１８は、図１６の符号１６３０に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。図１８のテーブル１８００は、図６に示したデマンド毎のＲＥＧの必要数と、図１６の符号１６３０に示したサイトタイプの仮決めに基づいて算出したデマンドあたりのＲＥＧ数を示している。ここでは、各ＯＡＤＭ区間のうちのサイトＡ−Ｂ間、サイトＡ−Ｃ間およびサイトＡ−Ｄ間のＲＥＧ数について説明する。
【００９５】
テーブル１８００に示すように、サイトＡ−Ｂ間は、ＯＡＤＭ区間数が１でありＩＬＡ数が１であるため、デマンドあたりに必要なＲＥＧ数は０である（図６参照）。また、サイトＡ−Ｂ間の１年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｂ間における１年目に必要なＲＥＧ数は０×１０＝０である。
【００９６】
また、サイトＡ−Ｂ間の２年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｂ間における２年目に必要なＲＥＧ数は０×１５＝０である。また、サイトＡ−Ｂ間の３年目のデマンド数は２０である（図８参照）ため、サイトＡ−Ｂ間における３年目に必要なＲＥＧ数は０×２０＝０である。
【００９７】
また、テーブル１８００に示すように、サイトＡ−Ｃ間は、ＯＡＤＭ区間数が２でありＩＬＡ数が３であるため、デマンドあたりに必要なＲＥＧ数は１である（図６参照）。また、サイトＡ−Ｃ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｃ間における１年目に必要なＲＥＧ数は１×０＝０である。
【００９８】
また、サイトＡ−Ｃ間の２年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における２年目に必要なＲＥＧ数は１×１３＝１３である。また、サイトＡ−Ｃ間の３年目のデマンド数は１３である（図８参照）ため、サイトＡ−Ｃ間における３年目に必要なＲＥＧ数は１×１３＝１３である。
【００９９】
また、テーブル１８００に示すように、サイトＡ−Ｄ間は、ＯＡＤＭ区間数が３でありＩＬＡ数が５であるため、デマンドあたりに必要なＲＥＧ数は３である（図６参照）。また、サイトＡ−Ｄ間の１年目のデマンド数は０である（図８参照）ため、サイトＡ−Ｄ間における１年目に必要なＲＥＧ数は３×０＝０である。
【０１００】
また、サイトＡ−Ｄ間の２年目のデマンド数は１０である（図８参照）ため、サイトＡ−Ｄ間における２年目に必要なＲＥＧ数は３×１０＝３０である。また、サイトＡ−Ｄ間の３年目のデマンド数は１５である（図８参照）ため、サイトＡ−Ｄ間における３年目に必要なＲＥＧ数は３×１５＝４５である。
【０１０１】
図１９は、図１６の符号１６３０に示した設計におけるトータルコストを示す図である。図１９のテーブル１９００は、図１６の符号１６３０に示した設計におけるサイトタイプの仮決めと、図１８に示したＯＡＤＭ区間毎に必要なＲＥＧ数と、に基づいて算出したトータルコストを示している。
【０１０２】
１年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が７個、ＩＬＡ（コスト１）が５個、ＲＥＧ（コスト１）が１６個配置される。したがって、１年目のトータルコストは７×４＋５×７＋１×５＋１×１６＝８４になる。１年目（初年度）の前年度は存在しないため、１年目の前年度とのトータルコストの差は８４とする。また、１年目のトータルコスト差の変化量は０とする。
【０１０３】
２年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が７個、ＩＬＡ（コスト１）が５個、ＲＥＧ（コスト１）が９９個配置される。したがって、２年目のトータルコストは７×４＋５×７＋１×５＋１×９９＝１６７になる。２年目の前年度（１年目）とのトータルコストの差は１６７−８４＝８３である。
【０１０４】
また、１年目の前年度とのトータルコストの差は８４であり、２年目の前年度（１年目）とのトータルコストの差は８３であるため、１年目から２年目のトータルコスト差の変化量は８３−８４＝−１である。
【０１０５】
３年目においては、ＯＡＤＭ（コスト７）が４個、ＥＸＰＲＥＳＳ（コスト５）が７個、ＩＬＡ（コスト１）が５個、ＲＥＧ（コスト１）が１６９個配置される。したがって、３年目のトータルコストは７×４＋５×７＋１×５＋１×１６９＝２３７になる。３年目の前年度（２年目）とのトータルコストの差は２３７−１６７＝７０である。
【０１０６】
また、２年目の前年度（１年目）とのトータルコストの差は８３であり、３年目の前年度（２年目）とのトータルコストの差は７０であるため、２年目から３年目のトータルコスト差の変化量は７０−８３＝−１３である。したがって、各年度におけるトータルコスト差の変化量（絶対値）の最大値は、｜−１｜＞｜−１３｜のため１３となる。
【０１０７】
このように、複数の時期の各トータルコストの変化量を最小にする制約条件を用いることで、複数の時期の各トータルコストを平準化することができる。これにより、各時期における投資コストがアンバランスになることを回避することができる。
【０１０８】
図２０は、ネットワーク設計装置の動作の一例（初年度コスト最小）を示すフローチャートである。図１のステップＳ１０４において、制約条件として「初年度コスト最小」が選択された場合は、ネットワーク設計装置は、まず、デマンド条件に基づいてルーティングを行う（ステップＳ２００１）。ステップＳ２００１においては、たとえば図８に示したルーティングと同様のルーティングを行う。
【０１０９】
つぎに、サイトタイプが確定していないＯＡＤＭ区間の中から、デマンド数が最も多いＯＡＤＭ区間を検索する（ステップＳ２００２）。ステップＳ２００２においては、たとえば、図８に示した例の場合は最初にサイトＡ−Ｂ間が検索される。サイトＡ−Ｂ間のサイトタイプが確定した後の場合はサイトＣ−Ｄ間が検索される。サイトＣ−Ｄ間のサイトタイプが確定した後の場合はサイトＢ−Ｃ間が検索される。
【０１１０】
つぎに、ステップＳ２００２によって検索されたＯＡＤＭ区間のサイトタイプを変更する（ステップＳ２００３）。ステップＳ２００３においては、たとえば、リーチャビリティが向上するように、ＯＡＤＭ区間のいずれかのサイトのサイトタイプをＩＬＡからＥＸＰＲＥＳＳに変更する（図９、図１２、図１６参照）。
【０１１１】
つぎに、ステップＳ２００３によってサイトタイプを変更した場合の、初年度におけるトータルコストを算出する（ステップＳ２００４）。ステップＳ２００４においては、たとえば図１１、図１４、図１９において説明したトータルコストの算出方法（ただし初年度におけるトータルコストのみでよい）と同様の方法でトータルコストを算出する。
【０１１２】
つぎに、ステップＳ２００４によって算出された初年度におけるトータルコストが、１ループ前のステップＳ２００４によって算出されたトータルコストよりも減少したか否かを判断する（ステップＳ２００５）。ただし、１ループ目のステップＳ２００５においては、トータルコストが減少していないと判断する。
【０１１３】
ステップＳ２００５においてトータルコストが減少していない場合（ステップＳ２００５：Ｎｏ）は、サイトタイプの変更によりトータルコストが減少する可能性があるか否かを判断する（ステップＳ２００６）。具体的には、ステップＳ２００５において検索されたＯＡＤＭ区間のいずれかのサイトのサイトタイプを、トータルコストが減少し得るように変更（たとえばＩＬＡからＥＸＰＲＥＳＳへ変更）することが可能か否かを判断する。
【０１１４】
ステップＳ２００６において、トータルコストが減少する可能性がない場合（ステップＳ２００６：Ｎｏ）は、ステップＳ２００８へ移行して処理を続行する。トータルコストが減少する可能性がある場合（ステップＳ２００６：Ｙｅｓ）は、ステップＳ２００２において検索されたＯＡＤＭ区間のいずれかのサイトのサイトタイプを変更し（ステップＳ２００７）、ステップＳ２００４へ戻って処理を続行する。
【０１１５】
ステップＳ２００５において、トータルコストが減少している場合（ステップＳ２００５：Ｙｅｓ）は、サイトタイプが未確定のＯＡＤＭ区間があるか否かを判断する（ステップＳ２００８）。サイトタイプが未確定のＯＡＤＭ区間がある場合（ステップＳ２００８：Ｙｅｓ）は、ステップＳ２００２へ戻って処理を続行する。サイトタイプが未確定のＯＡＤＭ区間がない場合（ステップＳ２００８：Ｎｏ）は、設計結果を出力し（ステップＳ２００９）、一連の処理を終了する。
【０１１６】
図２１は、図２０に示した動作による設計結果の一例を示す図である。図２１のテーブル２１００は、図５〜図７に示した各条件のもので図２０に示した動作によって得られた設計結果を示している。図２０に示した動作によって得られた設計結果においては、初年度（１年目）におけるトータルコスト（符号２１１０）が最小となる設計となる。
【０１１７】
ここでは初年度におけるトータルコストを最小にする設計について説明したが、対象年度は初年度に限らない。たとえば、対象年度をユーザによって指定させ、指定された年度におけるトータルコストを最小にする設計を行ってもよい。このように、図２０，図２１に示した動作によれば、特定の時期のネットワーク設計に基づく投資コストを最小にすることができる。これにより、ネットワーク設計の柔軟性を向上させることができる。
【０１１８】
図２２は、ネットワーク設計装置の動作の一例（全年度累計コスト最小）を示すフローチャートである。図１のステップＳ１０４において、制約条件として「全年度累計コスト最小」が選択された場合は、ネットワーク設計装置は、まず、入力された各年度のデマンド条件の合計を算出する（ステップＳ２２０１）。つぎに、ステップＳ２２０１によって算出されたデマンド条件の合計に基づいてルーティングを行う（ステップＳ２２０２）。
【０１１９】
図２２に示すステップＳ２２０３〜Ｓ２２０９は、図２０に示したステップＳ２００２〜Ｓ２００８と同様であるため説明を省略する。ただし、ステップＳ２２０５においては、ステップＳ２２０４によってサイトタイプを変更した場合の、各年度における累計のトータルコストを算出する（ステップＳ２２０５）。
【０１２０】
ステップＳ２２０９において、サイトタイプが未確定のＯＡＤＭ区間がない場合（ステップＳ２２０９：Ｎｏ）は、現在の設計経路がデマンドの存在しない区間を通過しているか否かを判断する（ステップＳ２２１０）。デマンドの存在しない区間を通過している場合（ステップＳ２２１０：Ｙｅｓ）は、設計経路を、デマンドの存在しない区間を避けた最短経路に変更する（ステップＳ２２１１）。
【０１２１】
つぎに、ステップＳ２２１１によって変更された設計経路にＲＥＧを割り当て（ステップＳ２２１２）、ステップＳ２２１３へ移行する。ステップＳ２２１０においてデマンドの存在しない区間を通過していない場合（ステップＳ２２１０：Ｎｏ）は、設計結果を出力し（ステップＳ２２１３）、一連の処理を終了する。
【０１２２】
図２３は、図２２に示した動作による設計結果の一例を示す図である。図２３のテーブル２３００は、図５〜図７に示した各条件のもので図２２に示した動作によって得られた設計結果を示している。図２２に示した動作によって得られた設計結果においては、全年度における各トータルコストの累計（符号２３１０）が最小となる設計となる。このため、制約条件やネットワーク条件が経時的に変化する場合であっても、最終的な投資コストを最小に抑えることができる。
【０１２３】
図２４は、ネットワーク設計装置の動作の一例（コスト変化量最小）を示すフローチャートである。図１のステップＳ１０４において、制約条件として「コスト変化量最小」（図１では不図示）が選択された場合のネットワーク設計装置の動作について説明する。図２４に示すステップＳ２４０１〜Ｓ２４０３は、図２０に示したステップＳ２００１〜Ｓ２００３と同様であるため説明を省略する。
【０１２４】
ステップＳ２４０３によってＯＡＤＭ区間のサイトタイプを変更した後、ネットワーク設計装置は、ステップＳ２４０３によってサイトタイプを変更した場合における、各年度のトータルコストをそれぞれ算出する（ステップＳ２４０４）。ステップＳ２４０４においては、たとえば、図１１、図１４、図１９において説明したトータルコストの算出方法と同様の方法でトータルコストを算出する。
【０１２５】
つぎに、ステップＳ２４０４によって算出された各年度のトータルコストの変化量の最大値（たとえば図１１に示した例では６０）が、１ループ前のステップＳ２４０４によって算出された各年度のトータルコストの変化量の最大値よりも減少したか否かを判断する（ステップＳ２４０５）。ただし、１ループ目のステップＳ２４０５においては、各年度のトータルコストの変化量の最大値が減少していないと判断する。
【０１２６】
ステップＳ２４０５においてトータルコストの変化量の最大値が減少していない場合（ステップＳ２４０５：Ｎｏ）は、トータルコストの変化量が最大の年度（たとえば図１１に示した例では２年目）のコスト変化が最大のデマンドを検索する（ステップＳ２４０６）。つぎに、ステップＳ２４０６によって検索されたデマンドにＲＥＧがあり、そのＲＥＧを減らせる可能性があるか否かを判断する（ステップＳ２４０７）。
【０１２７】
ステップＳ２４０７においては、具体的には、サイトタイプの変更によりＲＥＧを減らすことが可能か否かを判断する。ＲＥＧを減らせる可能性がある場合（ステップＳ２４０７：Ｙｅｓ）は、サイトタイプを変更し（ステップＳ２４０８）、ステップＳ２４０４へ戻って処理を続行する。ＲＥＧを減らせる可能性がない場合（ステップＳ２４０７：Ｎｏ）は、トータルコストの変化量が最小の年度（たとえば図１１に示した例では３年目）のコスト変化が最小のデマンドを検索する（ステップＳ２４０９）。
【０１２８】
つぎに、ステップＳ２４０９によって検索されたデマンドのＲＥＧを増やせる可能性があるか否かを判断する（ステップＳ２４１０）。ＲＥＧを増やせる可能性がある場合（ステップＳ２４１０：Ｙｅｓ）はステップＳ２４０８へ移行して処理を続行する。
【０１２９】
ＲＥＧを増やせる可能性がない場合（ステップＳ２４１０：Ｎｏ）は、ステップＳ２４１１へ移行して処理を続行する。ステップＳ２４０５においてトータルコストの変化量の最大値が減少している場合（ステップＳ２４０５：Ｙｅｓ）は、設計結果を出力し（ステップＳ２４１１）、一連の処理を終了する。図２４に示した動作によれば、図５〜図１９に示した例と同様に、複数の時期の各トータルコストを平準化することができる。
【０１３０】
図２５は、実施の形態にかかるネットワーク設計装置のハードウェア構成の一例を示すブロック図である。図２５において、ネットワーク設計装置２５００は、ＣＰＵ２５０１と、ＲＯＭ２５０２と、ＲＡＭ２５０３と、ＨＤＤ（ハードディスクドライブ）２５０４と、ＨＤ（ハードディスク）２５０５と、ＦＤＤ（フレキシブルディスクドライブ）２５０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）２５０７と、ディスプレイ２５０８と、Ｉ／Ｆ（インターフェース）２５０９と、キーボード２５１０と、マウス２５１１と、スキャナ２５１２と、プリンタ２５１３と、を備えている。また、各構成部はバス２５２０によってそれぞれ接続されている。
【０１３１】
ここで、ＣＰＵ２５０１は、ネットワーク設計装置２５００の全体の制御を司る。ＲＯＭ２５０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２５０３は、ＣＰＵ２５０１のワークエリアとして使用される。ＨＤＤ２５０４は、ＣＰＵ２５０１の制御にしたがってＨＤ２５０５に対するデータのリード／ライトを制御する。ＨＤ２５０５は、ＨＤＤ２５０４の制御で書き込まれたデータを記憶する。
【０１３２】
ＦＤＤ２５０６は、ＣＰＵ２５０１の制御にしたがってＦＤ２５０７に対するデータのリード／ライトを制御する。ＦＤ２５０７は、ＦＤＤ２５０６の制御で書き込まれたデータを記憶したり、ＦＤ２５０７に記憶されたデータをネットワーク設計装置２５００に読み取らせたりする。
【０１３３】
また、着脱可能な記録媒体として、ＦＤ２５０７の他、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、メモリーカードなどであってもよい。ディスプレイ２５０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ２５０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【０１３４】
Ｉ／Ｆ２５０９は、通信回線を通じてインターネットなどのネットワーク２５１４（ＮＥＴ）に接続され、このネットワーク２５１４を介して他の装置に接続される。そして、Ｉ／Ｆ２５０９は、ネットワーク２５１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２５０９には、たとえばモデムやＬＡＮアダプタなどを用いることができる。
【０１３５】
キーボード２５１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス２５１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【０１３６】
スキャナ２５１２は、画像を光学的に読み取り、ネットワーク設計装置２５００内に画像データを取り込む。なお、スキャナ２５１２は、ＯＣＲ機能を持たせてもよい。また、プリンタ２５１３は、画像データや文書データを印刷する。プリンタ２５１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【０１３７】
図１のステップＳ１０１，Ｓ１０３によるユーザへの表示は、たとえば、ＣＰＵ２５０１がディスプレイ２５０８やプリンタ２５１３を制御することによって行う。また、図１のステップＳ１０２は、たとえば、キーボード２５１０、マウス２５１１またはスキャナ２５１２などによるユーザからの入力をＣＰＵ２５０１が取得することによって行われる。これにより、複数の時期毎のネットワーク条件があらかじめ入力される（入力工程）。そして、入力工程によって入力されたネットワーク条件は、ＲＡＭ２５０３やＨＤ２５０５などのメモリに記憶される（第１記憶工程）。
【０１３８】
つぎに、図１のステップＳ１０４は、たとえば、キーボード２５１０、マウス２５１１またはスキャナ２５１２などによるユーザからの入力をＣＰＵ２５０１が取得することによって行われる。これにより、複数の時期における各コストに関する制約条件を受け付ける（受付工程）。そして、受付工程によって入力された制約条件は、ＲＡＭ２５０３やＨＤ２５０５などのメモリに記憶される（第２記憶工程）。
【０１３９】
つぎに、図１のステップＳ１０５〜Ｓ１１５においては、ＣＰＵ２５０１が、ＲＡＭ２５０３やＨＤ２５０５などのメモリに記憶されたネットワーク条件および制約条件をメモリから読み出す（第１読出工程）。そして、ＣＰＵ２５０１が、ＲＡＭ２５０３をワークエリアとして使用しながら演算を行うことで、読み出したネットワーク条件において、読み出された制約条件を満たすネットワークを設計する（設計工程）。
【０１４０】
そして、設計工程の設計結果は、ＲＡＭ２５０３やＨＤ２５０５などのメモリに記憶される（第３記憶工程）。つぎに、図１のステップＳ１１６においては、ＣＰＵ２５０１が、ＲＡＭ２５０３やＨＤ２５０５などのメモリに記憶された設計結果をメモリから読み出す（第２読出工程）。そして、ＣＰＵ２５０１が、読み出した設計結果をディスプレイ２５０８やプリンタ２５１３を制御することによって出力する。
【０１４１】
また、図１のステップＳ１０２，Ｓ１０４においては、ネットワーク２５１４上の他のコンピュータから送信された入力情報をＩ／Ｆ２５０９を介して受け付けてもよい。また、図１のステップＳ１１６においては、ＣＰＵ２５０１がＨＤ２５０５やＦＤ２５０７に設計結果を書き込んだり、Ｉ／Ｆ２５０９を介してネットワーク２５１４上の他のコンピュータへ設計結果を送信したりすることによって設計結果を出力してもよい。
【０１４２】
以上説明したように、開示のネットワーク設計方法およびネットワーク設計装置によれば、制約条件やネットワーク条件が経時的に変化しても所望の設計結果を得ることができる。なお、上述した実施の形態においては、サイトＡ〜Ｄ，５１１〜５１４，５２１〜５２４，５３１〜５３４を含むリニアネットワークの設計について説明したが、ネットワークの形態はこれに限らず、各種形態のネットワークの設計に適用することができる。
【０１４３】
また、上述したコア設計の手順に限らず、コアコストが少ないことを優先した設計や、発生雑音が少ないことを優先した設計など種々の手順を用いることができる。また、これらの手順は、線形計画法や整数計画法によって実現することも可能である。上述した実施の形態に関し、さらに以下の付記を開示する。
【０１４４】
（付記１）複数の時期毎のネットワーク条件があらかじめ入力される入力工程と、
前記複数の時期における各コストに関する制約条件を受け付ける受付工程と、
前記入力工程によって入力されたネットワーク条件において、前記受付工程によって受け付けられた制約条件を満たすネットワークを設計する設計工程と、
前記設計工程の設計結果を出力する出力工程と、
を含むことを特徴とするネットワーク設計方法。
【０１４５】
（付記２）前記受付工程では、前記各コストに関する制約条件を含む複数の制約条件のうちの少なくともいずれかの選択を受け付けることを特徴とする付記１に記載のネットワーク設計方法。
【０１４６】
（付記３）前記複数の制約条件は、前記複数の時期のうちの特定の時期の投資コストを最小にする制約条件を含むことを特徴とする付記２に記載のネットワーク設計方法。
【０１４７】
（付記４）前記複数の制約条件は、前記複数の時期の各投資コストをすべて閾値以下にする制約条件を含むことを特徴とする付記２または３に記載のネットワーク設計方法。
【０１４８】
（付記５）前記複数の制約条件は、前記複数の時期の各投資コストの合計を最小にする制約条件を含むことを特徴とする付記２〜４のいずれか一つに記載のネットワーク設計方法。
【０１４９】
（付記６）前記複数の制約条件は、前記複数の時期の各投資コストの変化量を最小にする制約条件を含むことを特徴とする付記２〜５のいずれか一つに記載のネットワーク設計方法。
【０１５０】
（付記７）前記入力工程では、前記複数の時期毎に異なるデマンドが前記ネットワーク条件として入力されることを特徴とする付記１〜６のいずれか一つに記載のネットワーク設計方法。
【０１５１】
（付記８）前記設計工程では、前記複数の時期毎に異なるデマンドに基づいてサイトのルーティングを行い、ルーティングを行った各サイトのサイトタイプを、前記制約条件を満たすように変更することを特徴とする付記７に記載のネットワーク設計方法。
【０１５２】
（付記９）複数の時期毎のネットワーク条件があらかじめ入力される入力工程と、
前記入力工程によって入力されたネットワーク条件をメモリに記憶する第１記憶工程と、
前記複数の時期における各コストに関する制約条件を受け付ける受付工程と、
前記受付工程によって受け付けられた制約条件をメモリに記憶する第２記憶工程と、
前記第１記憶工程によって記憶されたネットワーク条件および前記第２記憶工程によって記憶された制約条件をメモリから読み出す第１読出工程と、
前記第１読出工程によって読み出されたネットワーク条件において、前記第１読出工程によって読み出された制約条件を満たすネットワークを設計する設計工程と、
前記設計工程の設計結果をメモリに記憶する第３記憶工程と、
前記第３記憶工程によって記憶された設計結果をメモリから読み出す第２読出工程と、
前記第２読出工程によって読み出された設計結果を出力する出力工程と、
を含むことを特徴とするネットワーク設計方法。
【０１５３】
（付記１０）複数の時期毎のネットワーク条件があらかじめ入力される入力手段と、
前記複数の時期における各コストに関する制約条件を受け付ける受付手段と、
前記入力手段によって入力されたネットワーク条件において、前記受付手段によって受け付けられた制約条件を満たすネットワークを設計する設計手段と、
前記設計手段の設計結果を出力する出力手段と、
を備えることを特徴とするネットワーク設計装置。
【０１５４】
（付記１１）複数の時期毎のネットワーク条件があらかじめ入力される入力手段と、
前記入力手段によって入力されたネットワーク条件をメモリに記憶する第１記憶手段と、
前記複数の時期における各コストに関する制約条件を受け付ける受付手段と、
前記受付手段によって受け付けられた制約条件をメモリに記憶する第２記憶手段と、
前記第１記憶手段によって記憶されたネットワーク条件および前記第２記憶手段によって記憶された制約条件をメモリから読み出す第１読出手段と、
前記第１読出手段によって読み出されたネットワーク条件において、前記第１読出手段によって読み出された制約条件を満たすネットワークを設計する設計手段と、
前記設計手段の設計結果をメモリに記憶する第３記憶手段と、
前記第３記憶手段によって記憶された設計結果をメモリから読み出す第２読出手段と、
前記第２読出手段によって読み出された設計結果を出力する出力手段と、
を備えることを特徴とするネットワーク設計装置。
【図面の簡単な説明】
【０１５５】
【図１】実施の形態にかかるネットワーク設計方法の一例を示すフローチャートである。
【図２】ネットワーク条件の一例を示す図である。
【図３】制約条件の一例を示す図である。
【図４】設計結果の一例を示す図である。
【図５】ネットワーク条件（サイト条件）の一例を示す図である。
【図６】ネットワーク条件（性能条件）の一例を示す図である。
【図７】ネットワーク条件（デマンド条件）の一例を示す図である。
【図８】デマンド条件に基づくルーティングを示す図である。
【図９】サイトタイプ選択の一例を示す図（その１）である。
【図１０】図９に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。
【図１１】図９に示した設計におけるトータルコストを示す図である。
【図１２】サイトタイプ選択の一例を示す図（その２）である。
【図１３】図１２に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。
【図１４】図１２に示した設計におけるトータルコストを示す図である。
【図１５】各年度のトータルコスト差の変化量の比較を示す図（その１）である。
【図１６】サイトタイプ選択の一例を示す図（その３）である。
【図１７】各年度のトータルコスト差の変化量の比較を示す図（その２）である。
【図１８】図１６の符号１６３０に示した設計におけるデマンドあたりのＲＥＧ数を示す図である。
【図１９】図１６の符号１６３０に示した設計におけるトータルコストを示す図である。
【図２０】ネットワーク設計装置の動作の一例（初年度コスト最小）を示すフローチャートである。
【図２１】図２０に示した動作による設計結果の一例を示す図である。
【図２２】ネットワーク設計装置の動作の一例（全年度累計コスト最小）を示すフローチャートである。
【図２３】図２２に示した動作による設計結果の一例を示す図である。
【図２４】ネットワーク設計装置の動作の一例（コスト変化量最小）を示すフローチャートである。
【図２５】実施の形態にかかるネットワーク設計装置のハードウェア構成の一例を示すブロック図である。
【符号の説明】
【０１５６】
４２０  出力情報
５１１〜５１４，５２１〜５２４，５３１〜５３４  サイト
【図１】
2010147653.tif 000003
【図２】
2010147653.tif 000004
【図３】
2010147653.tif 000005
【図４】
2010147653.tif 000006
【図５】
2010147653.tif 000007
【図６】
2010147653.tif 000008
【図７】
2010147653.tif 000009
【図８】
2010147653.tif 000010
【図９】
2010147653.tif 000011
【図１０】
2010147653.tif 000012
【図１１】
2010147653.tif 000013
【図１２】
2010147653.tif 000014
【図１３】
2010147653.tif 000015
【図１４】
2010147653.tif 000016
【図１５】
2010147653.tif 000017
【図１６】
2010147653.tif 000018
【図１７】
2010147653.tif 000019
【図１８】
2010147653.tif 000020
【図１９】
2010147653.tif 000021
【図２０】
2010147653.tif 000022
【図２１】
2010147653.tif 000023
【図２２】
2010147653.tif 000024
【図２３】
2010147653.tif 000025
【図２４】
2010147653.tif 000026
【図２５】
2010147653.tif 000027