敷設可能経路を考慮したケーブル敷設設計用のプログラム、装置及びシステム
【課題】伝送ケーブルの敷設経路の設計に対して、その伝送ケーブルの工事区間の総延長に対する準最適解を与えることができるケーブル敷設設計用のプログラム等を提供する。
【解決手段】伝送ケーブルを敷設可能な経路について、物理的なノードの位置情報ｖと、それらノードを結ぶエッジｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと、ノードＶの部分集合Ｔに、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースとを有する。そして、全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、Ｇ'上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップとしてコンピュータを実行させる。
【解決手段】伝送ケーブルを敷設可能な経路について、物理的なノードの位置情報ｖと、それらノードを結ぶエッジｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと、ノードＶの部分集合Ｔに、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースとを有する。そして、全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、Ｇ'上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップとしてコンピュータを実行させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信局間を結ぶケーブルの敷設経路の設計を支援する装置の技術に関する。
【背景技術】
【０００２】
通信局間を、有線の伝送ケーブルで接続する場合、その敷設経路（ルート）を設計する必要がある。近年では、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルについて、その敷設経路を設計する需要も多い。このネットワーク構成は、収容局から伸びる１本の光ファイバの途中に、光スプリッタ（分岐装置）を挿入し、その複数の光ファイバケーブルを加入者宅に引き込むものである。
【０００３】
図１は、ＰＯＮのシステム構成図である。
【０００４】
図１のシステムによれば、１つの収容局２に、光ファイバケーブルを介して複数の光スプリッタ３が接続されている。収容局２と光スプリッタ３との間を接続する光ファイバネットワークは、一般に「ＯＤＮ」と称される。また、光スプリッタ３は、収容局２に接続する１本の光ファイバケーブルを、光加入者ユニット（ＯＮＵ(Optical Network Unit)）４に接続する複数の光ファイバケーブルに分岐する。光スプリッタ３と光加入者ユニット４との間の光ファイバケーブルは、一般に「ドロップケーブル」と称される。図１のシステムにおける光スプリッタ３は、スターカプラのような電気装置を必要としない受動的な素子を用いており、「Passive」と称される。
【０００５】
通信事業者によって敷設される通信局間のケーブルの敷設経路は、熟練技術者に依存して、以下のような２つのステップによって設計されていた。例えばＰＯＮの場合、少なくとも１つの収容局の位置は、予め与えられている。
（ステップ１）最初に、光スプリッタの配置位置が決定される。この位置は、光ファイバケーブルの敷設可能な経路だけでなく、トラヒックの需要予測や、加入者端局の分布密度、等の情報に基づいて決定される。
（ステップ２）次に、収容局に対して全ての光スプリッタを結ぶように、光ファイバケーブルの敷設経路が決定される。ここで、以下の２つが考慮される。
「敷設される伝送ケーブルの総延長」
「伝送ケーブルの敷設工事区間の総延長」
しかしながら、熟練技術者に依存するために、ケーブルの敷設経路の設計には、膨大な手間と時間を要することとなる。
【０００６】
従来、ＰＯＮにおける光ファイバケーブルの敷設コストを最小化するための技術がある（例えば非特許文献１及び２参照）。この技術によれば、収容局を中心とした円形のエリア内に、加入者宅内の光加入者ユニットが一様に分布していることを前提とする。
【０００７】
また、ＯＤＮとして敷設される光ファイバケーブルの総延長を、準最適解となるように設計する技術もある（例えば特許文献１及び２参照）。この技術によれば、前述したステップ１における収容局及び光スプリッタの配置位置を、自動的且つ最適に決定する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−２０４７８０号公報
【特許文献２】特願２００９−２１８１９５号公報
【非特許文献】
【０００９】
【非特許文献１】宇田川大輔、松本隆男、「多段分岐光アクセスネットワークの最小光ファイバ長に関する検討」、電子情報通信学会総合大会、B-8-29、2003年
【非特許文献２】宇田川大輔、松本隆男、「多段分岐アクセスネットワークのコスト最小化条件に関する検討」、電子情報通信学会総合大会、B-8-11、2004年
【非特許文献３】S. Dreyfus, R. Wagner, “\lochThe Steiner problem in graphs,”\loch Networks 1, pp.195-207, (1972).
【非特許文献４】Xianlong Hong, et al., “\lochTIGER: An Effcient Timing-Driven Global Router for Gate Arrayand Standard Cell Layout Design,”\loch IEEE Trans. On Computer-aided Design of Integrated Circuits andSystems, Vol. 16, No. 11, Nov., pp. 1323-1331, (1997).
【発明の概要】
【発明が解決しようとする課題】
【００１０】
一般的に、単位長さあたりで比較すると、光ファイバケーブルの敷設工事コストは、光ファイバケーブルの材料コストよりも、大幅に高価である。このため、ＯＤＮ構築コストを低減するためには、「伝送ケーブルの敷設工事区間の総延長」に対する準最適解を導出する必要がある。しかしながら、熟練技術者に依存した場合、ＯＤＮが、敷設コストに対する準最適解となっているか否かを確認することは不可能であった。
【００１１】
図２は、伝送ケーブルの総延長と敷設工事区間の総延長との関係を表す説明図である。
【００１２】
図２によれば、例えば、１つの収容局と、３つの光スプリッタと、収容局及び光スプリッタ以外の２つのノード（例えば道路の交差点や、送電線の設備点（電柱））とが配置されており、ケーブルの敷設候補（図２（ａ）参照）が表されている。Ｌ１〜Ｌ９は、距離を表す。
［敷設１］（図２（ｂ）参照）ケーブルの総延長を最短にした場合（Ｌ１，Ｌ２＋Ｌ３＋Ｌ８，Ｌ５）、工事区間の総延長は、Ｌ１＋Ｌ２＋Ｌ３＋Ｌ５＋Ｌ８となる。
［敷設２］（図２（ｃ）参照）一方で、工事区間の総延長を最短にした場合（Ｌ２＋Ｌ３＋Ｌ８，Ｌ６，Ｌ４）、ケーブルの総延長は、３×Ｌ２＋２×Ｌ３＋Ｌ４＋Ｌ６＋Ｌ８となる。
ここで、敷設工事コストをできる限り低額で抑えるためには、工事区間の総延長を最短にするべく［敷設２］を選択すべきである。
【００１３】
また、前述した非特許文献１及び２に記載された技術によれば、以下の２つの点を前提としている。
（前提１）前提として、収容局を中心とした円形のエリア内に、ＰＯＮの加入希望者宅が一様に分布している。
（現実１）現実的には、加入希望者宅が非一様に分布しおらず、また、収容局がカバーするエリアの形状も円形でない。
【００１４】
（前提２）前提として、光ファイバケーブルは、任意の場所に、敷設可能である。即ち、エリアでは、光ファイバケーブルを自由に敷設することができる。
（現実２）現実的には、光ファイバケーブルは、架空送電線網や道路網に沿って敷設する必要がある。
【００１５】
前述したステップ１（光スプリッタ設置位置の決定）のみであれば、準最適解が得られる。しかしながら、前述したステップ２（ＯＤＮの設計）では、光ファイバケーブルの総延長に対する準最適解を得るにすぎず、光ファイバケーブル工事区間の総延長は、全く考慮されていない。
【００１６】
そこで、本発明は、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができるケーブル敷設設計用のプログラム、装置及びシステムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計用のプログラムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと
を有し、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップと
してコンピュータを実行させることを特徴とする。
【００１８】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第１のステップは、最小シュタイナー木(Minimum Steiner Tree)を導出するアルゴリズムを用いることも好ましい。
【００１９】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第１のステップは、
ノードＶ（＝｛ｖ1,ｖ2,・・・,ｖn｝）の部分集合Ｔに、収容局及び分岐局の位置情報ｔを含める第１１のステップと、
部分集合Ｔに含まれるノードｔの任意の２点の組み合わせ毎に、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となるパスを探索する第１２のステップと、
第１２のステップによって探索されたパス上に存在するノードｖを、ツリー状グラフＧ'（Ｖ',Ｅ'）に追加する第１３のステップと、
第１２のステップによって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する第１４のステップと
を有し、ツリー状グラフＧ'が連結するまで、第１２〜第１４のステップを繰り返すことも好ましい。
【００２０】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第２のステップの最短経路探索アルゴリズムは、部分集合Ｔに含まれる２点のノード同士の総当たりに対するダイクストラ(Dijkstra)法を用いることも好ましい。
【００２１】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
敷設コストｗは、ケーブルの敷設費用に基づく数値、又は、ケーブルの線路長に基づく数値であることも好ましい。
【００２２】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
伝送ケーブルは、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルであり、
分岐局は、光スプリッタであり、
収容局及び分岐局以外のノードは、物理的な敷設設備である
ことも好ましい。
【００２３】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計装置であって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有することを特徴とする。
【００２４】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するケーブル敷設設計システムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
位置情報データベース及び敷設可能経路情報データベースとネットワークを介して接続された敷設経路設計装置と
を有し、
敷設経路設計装置は、
収容局及び分岐局毎の位置情報ｔと敷設可能経路情報Ｇ（Ｖ,Ｅ）とを用いて、Ｔに含まれる全てのノードを閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有する
ことを特徴とする。
【発明の効果】
【００２５】
本発明のケーブル敷設設計用のプログラム、装置及びシステムによれば、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができる。
【図面の簡単な説明】
【００２６】
【図１】ＰＯＮのシステム構成図である。
【図２】伝送ケーブルの総延長と敷設工事区間の総延長との関係を表す説明図である。
【図３】伝送ケーブルを敷設可能なグラフ状の経路を表す説明図である。
【図４】本発明における敷設経路設計装置の機能構成図である。
【図５】本発明における第１の実施形態のフローチャートである。
【図６】最短経路探索アルゴリズムを説明するグラフである。
【図７】本発明における第２の実施形態のフローチャートである。
【図８】具体的な敷設経路の第１の設計過程を表す説明図である。
【図９】具体的な敷設経路の第２の設計過程を表す説明図である。
【図１０】具体的な敷設経路の第３の設計過程を表す説明図である。
【図１１】具体的な敷設経路の第４の設計過程を表す説明図である。
【図１２】本発明におけるシステム構成図である。
【発明を実施するための形態】
【００２７】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２８】
図３は、伝送ケーブルを敷設可能なグラフ状の経路を表す説明図である。
【００２９】
図３の経路によれば、収容局２と複数の光スプリッタ（分岐局）３との間の伝送ケーブルは、グラフ状に敷設可能となっている。ここで、以下のように定義する。
収容局の位置：Ｃ
光スプリッタの位置：ＳＰＬi（i=1,2,…,N）
ノードｖi（i=1,2,…,K1）、ノードの集合Ｖ＝｛ｖ1,ｖ2,・・・,ｖK1｝
エッジｅj（j=1,2,…,K2）、エッジの集合Ｅ＝｛ｅ1,ｅ2,・・・,ｖK2｝
エッジｅjの重みｗj（j=1,2,…,K2）
【００３０】
ノード（節点）ｖは、物理的な位置情報であって、収容局及び光スプリッタの位置情報も含むものとする。
エッジ（枝）ｅは、ノードｖ同士を結ぶ。
例えば、敷設可能経路として道路網を想定する場合、以下のように対応付けられる。
ノードｖ：例えば道路の交差点や、送電線の設備点（電柱）の位置情報
（収容局及び光スプリッタの位置情報を含む）
エッジｅ：道路の交差点同士や送電線の設備点同士の間を結ぶ、道路や送電線
重みｗ ：道路や送電線ｅの長さ（敷設コストにつながる）
【００３１】
図４は、本発明における敷設経路設計装置の機能構成図である。
【００３２】
敷設経路設計装置１は、伝送ケーブル（例えば光ファイバケーブル）の敷設可能経路網Ｇ（Ｖ,Ｅ）上に、収容局及び光スプリッタの全ての通信局を結ぶ敷設経路を決定する。敷設経路設計装置１は、敷設可能経路情報データベース１０１と、位置情報データベース１０２と、パラメータ記憶部１０３と、ツリー状グラフ生成部１１１と、２点間経路決定部１１２と、設計結果出力部１１３とを有する。敷設経路設計装置１は、例えばパーソナルコンピュータやサーバのようなものであって、その装置１に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００３３】
［敷設可能経路情報データベース１０１］
敷設可能経路情報データベース１０１は、敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶する。敷設可能経路情報Ｇは、伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとを用いて表現したものである。また、各エッジｅには、敷設コストｗも付与される。
【００３４】
［位置情報データベース１０２］
位置情報データベース１０２は、ノードＶの部分集合Ｔとして、収容局Ｃ及び光スプリッタＳＰＬi毎の位置情報ｔを記憶する。即ち、物理的なノード（節点）の位置情報ｖは、収容局及び分岐局の位置情報も含んでいる。
【００３５】
［パラメータ記憶部１０３］
パラメータ記憶部１０３は、ノードｖの部分集合Ｔとなるツリー状グラフＧ'（Ｖ',Ｅ'）を、算出過程の中で一時的に記憶する。
【００３６】
［ツリー状グラフ生成部１１１］
ツリー状グラフ生成部１１１は、全てのノード間について、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する。ここで、ツリー状グラフＧ'を生成するために、２つの実施形態がある。
（第１の実施形態）最小シュタイナー木を導出するアルゴリズムを用いる
（比較的演算量が多い）
（第２の実施形態）最小シュタイナー木に準ずる木を導出するアルゴリズムを用いる
（比較的演算量が少ない）
【００３７】
［２点間経路決定部１１２］
２点間経路決定部１１２は、ツリー状ネットワークＧ'（Ｖ',Ｅ'）について、敷設コストが最小となるべき、収容局から各分岐装置を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する。最短経路探索アルゴリズムとしては、例えばダイクストラ(Dijkstra)法を用いることができる。
【００３８】
［設計結果出力部１１３］
設計結果出力部１１３は、最終的にパラメータ記憶部１０３に記憶された設計結果を、オペレータに明示するべくディスプレイへ出力する。これによって、オペレータは、伝送ケーブルの敷設経路を認識することができる。
【００３９】
図５は、本発明における第１の実施形態のフローチャートである。
【００４０】
（Ｓ５１）最初に、位置情報データベース１０２に記憶された収容局Ｃ及び光スプリッタＳＰＬi全ての位置情報を、ノードＶの部分集合Ｔとする。
【００４１】
（Ｓ５２）次に、最小シュタイナー木を導出するアルゴリズムを用いて、収容局Ｃ及び光スプリッタＳＰＬi全てを含む最小シュタイナー木を算出する。この木は、敷設可能経路情報データベース１０１に記憶されたノードｖ及びエッジｅを用いて算出される。
【００４２】
第１の実施形態によれば、「シュタイナー木(Steiner Tree)」を生成する。「シュタイナー木」とは、グラフＧに対して、ノードＶの部分集合Ｔ（T={t1,t2,…,tk}, k≦K1）が与えられた場合、部分集合Ｔに含まれる全てのノードを含む木をいう。この木は、閉路を持たない連結グラフである。
【００４３】
ここで、本発明によれば、特に「最小シュタイナー木(Minimum Steiner Tree)」を生成する。「最小シュタイナー木」問題とは、エッジｅjに重みｗjが付与されたグラフＧにおけるノードＶの部分集合Ｔについて、エッジｅの重みの総和ｗが最も小さくなるシュタイナー木を算出することをいう。最小シュタイナー木問題は、ＮＰ(Non-deterministic Polynomial time)困難であることが周知となっている。最小シュタイナー木を導出するアルゴリズムとしては、例えば非特許文献３及び非特許文献４に記載の技術がある。
【００４４】
パラメータ記憶部１０３は、最小シュタイナー木について、ノードｖ'i（i=1,2,…,K'1）及びエッジｅ'j（j=1,2,…,K'2）によって構成されるグラフＧ’＝（Ｖ',Ｅ'）を記憶する。尚、最小シュタイナー木Ｇ’は、グラフＧの一部（Ｇ'⊆Ｇ）であるため、K'1≦K1、K'2≦K2であることは明らかである。
【００４５】
（Ｓ５３）最小シュタイナー木のグラフＧ'＝（Ｖ',Ｅ'）上で、各光スプリッタＳＰＬi（i=1,2,…,N）から収容局Ｃまでの経路を、最短経路探索アルゴリズム（２点間経路決定部において実施）を用いて算出する。
【００４６】
図６は、最短経路探索アルゴリズムを説明するグラフである。
【００４７】
ここでは、最短経路探索アルゴリズムとして、ダイクストラ(Dijkstra)法を用いる。図６のグラフは、□で表された交差点（ノード）と、線で表された道路（エッジ）とからなる。また、各エッジには、例えばエッジの長さ（道路の長さ）に対応する重みｗが付与されている。グラフには、起点及び終点が予め指定されており、ダイクストラ法によって、起点及び終点を結ぶ最短経路（＝重みの総和が最小となる経路）が導出される。
【００４８】
この方法は、各第ｉ次ノードについて、隣接する第（ｉ＋１）次ノードを見出す。そして、各第（ｉ＋１）次ノードについて、以下の３つを記憶する。
（１）１ホップ前の第ｉ次ノードを経由する起点からの累積距離
（２）起点までのホップ数
（３）１ホップ前のノードのノード番号
最終的に、終点に到達した際に、順次、０次ノード（起点）まで辿ることによって、起点と終点とを結ぶ経路を作成する。この経路が、起点と終点を結ぶ最短の経路となる。
ｍ次ノード -> （ｍ−１）次ノード -> （ｍ−２）次ノード・・・
【００４９】
（Ｓ６１）起点を０次ノードとして、当該０次ノードからエッジに沿って隣接する１次ノードＡ1〜Ａ2を探索する。そして、１次ノードＡ1，Ａ2それぞれは、以下の情報を記憶する。
Ａ1 -> 起点−Ａ1間の累計距離Ａｄ1
起点までのホップ数：１
１ホップ前のノード：起点
Ａ2 -> 起点−Ａ2間の累計距離Ａｄ2
起点までのホップ数：１
１ホップ前のノード：起点
【００５０】
（Ｓ６２）次いで、各１次ノードＡ1及びＡ2について、２次ノードＢijを探索する。
１次ノードＡ1については、３つの２次ノードＢ11，Ｂ12，Ｂ13を見出す。２次ノードＢ11，Ｂ12，Ｂ13に対して、以下の情報を登録する。
Ｂ11 -> 起点−Ａ1−Ｂ11間の累計距離Ｂｄ11
起点までのホップ数：２
１ホップ前のノード：Ａ1
Ｂ12 -> 起点−Ａ1−Ｂ12間の累計距離Ｂｄ12
起点までのホップ数：２
１ホップ前のノード：Ａ1
Ｂ13 -> 起点−Ａ1−Ｂ13間の累計距離Ｂｄ13
起点までのホップ数：２
１ホップ前のノード：Ａ1
【００５１】
同様に、１次ノードＡ2については、２つの２次ノードＢ21，Ｂ22を見出す。２次ノードＢ21，Ｂ22に対して、以下の情報を登録する。
Ｂ21 -> 起点−Ａ2−Ｂ21間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
Ｂ22 -> 起点−Ａ2−Ｂ22間の累計距離Ｂｄ22
起点までのホップ数：２
１ホップ前のノード：Ａ2
【００５２】
ここで、ノードＢ13及びＢ21は、同一ノードである。このように、重複した１つのノードに対して、異なる経路の累積距離のデータが記憶される場合がある。この場合、起点からの累積距離Ｂｄ13とＢｄ21との大小関係を比較し、大きい方のデータを破棄し、小さい方のデータのみを記憶する。例えば、Ｂｄ13＞Ｂｄ21であれば、ノードＢ13（＝Ｂ21）には、累計距離Ｂｄ21と対応する１ホップ前のノードＡ2の番号が最終的に記憶される。
［Ｂｄ13＞Ｂｄ21］
Ｂ13 -> 起点−Ａ1−Ｂ13間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
Ｂ21 -> 起点−Ａ2−Ｂ21間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
【００５３】
（Ｓ６３）以降、同様に、各２次ノードＢijについて、隣接する３次ノードＣijを探索する。これを繰り返すことによって、探索が、終点に到達する。
【００５４】
例えば、２次ノードB12及びB13（B21）は、３次ノードとしての終点を探索する。ここで、以下の２つの経路が検出される。
起点−Ａ1−Ｂ12−終点 ：累計距離（短い）
起点−Ａ2−Ｂ13（Ｂ21）−終点 ：累計距離（長い）
終点に到達した場合、累計距離が短い方の経路が、最短経路として決定される。例えば、図６によれば、起点−Ａ1−Ｂ12−終点が、最短経路として決定される。
【００５５】
図７は、本発明における第２の実施形態のフローチャートである。
【００５６】
図５で前述した第１の実施形態のフローチャートによれば、「最小シュタイナー木」のアルゴリズムを用いた。「最小シュタイナー木」は、グラフＧと、Ｖの部分集合（＝全光スプリッタ及び収容局の位置を含む）（T={t1,t2,…,tk}, k≦K1）に基づいて、Ｔに含まれるノード全てを含む木を導出する。この最小シュタイナー木によれば、エッジの重みの総和が最小となる。
【００５７】
しかしながら、このような最小シュタイナー木アルゴリズムの計算量のオーダは、３のＴの要素数乗（Ｏ(3k)）であることが分かっている。このため、Ｔの要素数が増加すると、計算量が爆発的に増加するという課題がある。
【００５８】
そこで、図７の第２の実施形態によれば、エッジの重みの総和が望ましい程度に小さいシュタイナー木（つまり、「最小シュタイナー木に準ずる木」）を導出する技術を用いる。この技術によれば、エッジの重みの総和が確実に最小となるまで算出しないために、短時間で、ツリー状グラフの木を導出することができる。
【００５９】
（Ｓ７１）最初に、位置情報データベース１０２に記憶された収容局Ｃ及び光スプリッタＳＰＬi全ての位置情報を、ノードＶ（={ｖ1,ｖ2,・・・,ｖn}）の部分集合Ｔとする。
【００６０】
（Ｓ７２）次に、パラメータ記憶部１０３に対して、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）の保存用に割り当てられている記憶領域を初期化する。Ｖ'及びＥ'を共に、空集合とする。
【００６１】
（Ｓ７３）次に、部分集合Ｔに含まれるノードｔの任意の２点（ti,tj（i≠j））の組み合わせ毎に、光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）上におけるti−tj間の最短経路を探索する。即ち、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となる経路を探索する。その結果は、パラメータ記憶部１０３に保存される。
【００６２】
（Ｓ７４）パラメータ記憶部１０３に保存された全ての経路について、重み（長さ）の総和がゼロでない経路を抽出する。その中で、重みの総和が最小の経路tp−tqを検索する。
【００６３】
（Ｓ７５）当該経路について、両端ノードであるtp、tqを含め、当該経路を構成するノードｖ及びエッジｅの集合を、シュタイナー木Ｇ'に追加する。
【００６４】
（Ｓ７６）また、Ｓ７５によって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する。即ち、光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）について、Ｇ'に追加された経路を構成するエッジの重みｗの値をゼロ（０）に変更する。
【００６５】
（Ｓ７７）最後に、シュタイナー木Ｇ'を構成するノードの集合Ｖ'が、Ｔを全て含み（Ｔ⊆Ｖ'）、且つ、連結グラフかどうかを確認する。この条件を満たす場合、Ｓ７８へ移行し、満たさない場合、Ｓ７３へ移行する。
【００６６】
（Ｓ７８）最小シュタイナー木のグラフＧ'＝（Ｖ',Ｅ'）上で、各光スプリッタＳＰＬi（i=1,2,…,N）から収容局Ｃまでの経路を、最短経路探索アルゴリズム（２点間経路決定部において実施）を用いて算出する。前述した図５のＳ５３の処理と全く同様である。
【００６７】
ここで、第２の実施形態における計算量のオーダについて検討する。ダイクストラ法の計算量のオーダは、グラフＧに含まれるノード数の二乗であることが知られている。第２の実施形態によれば、ダイクストラ法による演算が、Ｔに含まれるノード間の全組合せについて実施されるために、全体の計算量のオーダは、K12×k2に比例する（Ｏ(K12×k2)）。このため、光スプリッタ数の多い（kが大きい）場合では、第２の実施形態によって、大幅に計算量を削減（＝設計処理の高速化）することができる。
【００６８】
最後に、第２の実施形態における具体的な敷設経路の設計について説明する。
【００６９】
図８は、具体的な敷設経路の第１の設計過程を表す説明図である。
【００７０】
簡単化のために、ここでは、敷設可能経路網情報データベースに保存されている光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）は、以下の要素から構成されているとする。
１１個のノード（Ｖ＝{ｖ1,…,ｖ11}）
１６本のエッジ（Ｅ＝{e1,…,e16}）
各エッジｅは、初期状態ではエッジの長さで重み付けされているものとする。また、位置情報データベースには、３個の光スプリッタ及び収容局の位置情報が保存されているものとする。
【００７１】
図９は、具体的な敷設経路の第２の設計過程を表す説明図である。
【００７２】
最初に、Ｓ７１について、光スプリッタ及び収容局を、Ｖの部分集合Ｔ＝{t1,t2,t3,t4}とする。ここで、t1=v7, t2=v4, t3=v10, t4=v8であるものとする。
次に、Ｓ７２について、シュタイナー木Ｇ'を初期化する。
【００７３】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t1−t3が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ'＝{t1,t2,t3,t4}， Ｅ'＝{e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではｅ14）の重みを、ゼロとおく。
この時点では、Ｖ'に含まれないＴの要素がある（Ｔ⊆Ｖ'でない）ため、Ｓ７３へ戻る。
【００７４】
図１０は、具体的な敷設経路の第３の設計過程を表す説明図である。
【００７５】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t2−t4が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ’＝{t1,t2,t3,t4,v5}， Ｅ'＝{e4,e7,e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではe4,e7）の重みを、ゼロとおく。
この時点では、ＴはＶ'に含まれる（Ｔ⊆Ｖ'）ものの、Ｇ'は、連結グラフでないため、Ｓ７３へ戻る。
【００７６】
図１１は、具体的な敷設経路の第４の設計過程を表す説明図である。
【００７７】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t1−t2が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ'＝{t1,t2,t3,t4,v5,v6}， Ｅ'＝{e4,e6,e7,e11,e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではe4,e6,e11）の重みを、ゼロとおく。
この時点では、ＴはＶ'に含まれ（Ｔ⊆Ｖ'）、且つ、Ｇ'は連結グラフとなるために、Ｓ７８へ移行する。
【００７８】
最後に、Ｇ'＝（Ｖ'，Ｅ'）上で、それぞれの光スプリッタＳＰＬi（i=1,2,3）に対して、収容局Ｃまでの経路を、最短経路探索アルゴリズムを用いて算出する。最終的に、図１１のような経路が、最短経路として算出される。
【００７９】
図１２は、本発明におけるシステム構成図である。
【００８０】
図１２のシステムによれば、図４と比較して、敷設可能経路情報データベース１０１及び位置情報データベース１０２と、敷設経路設計装置１とが、ネットワークを介して接続されている。例えば敷設経路設計装置１がパーソナルコンピュータであってもよく、ネットワークに接続されたデータベースから情報を取得することによって、敷設経路を設計することができる。
【００８１】
前述したように、本発明のケーブル敷設設計用のプログラム、装置及びシステムによれば、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができる。
【００８２】
例えばＰＯＮの光ファイバケーブルにおける敷設経路を設計する場合、複数の光スプリッタの位置と収容局の位置が与えられていても、光ファイバケーブルの敷設可能経路に対して制約条件が存在する。ここで、光スプリッタの全てを収容局に収容する場合、本発明によれば、光ファイバケーブル工事区間の総延長に対して準最適となるＯＤＮを自動的に設計することができる。また、本発明によって設計されたＯＤＮ構築コストは、従来法（熟練した技術者による手作業や、特許文献１及び２に記載の手法）で設計されたコストよりも低くなる。更に、本発明の第２の実施形態によってＯＤＮを設計した場合、少ない演算量で、短時間に設計することができる。本発明によれば、特に、ＰＯＮサービスを展開する通信事業者における、ＦＴＴＨネットワークの設計に適する。
【００８３】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００８４】
１ 敷設経路設計装置
１０１ 敷設可能経路情報データベース
１０２ 位置情報データベース
１０３ パラメータ記憶部
１１１ ツリー状グラフ生成部
１１２ ２点間経路決定部
１１３ 設計結果出力部
【技術分野】
【０００１】
本発明は、通信局間を結ぶケーブルの敷設経路の設計を支援する装置の技術に関する。
【背景技術】
【０００２】
通信局間を、有線の伝送ケーブルで接続する場合、その敷設経路（ルート）を設計する必要がある。近年では、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルについて、その敷設経路を設計する需要も多い。このネットワーク構成は、収容局から伸びる１本の光ファイバの途中に、光スプリッタ（分岐装置）を挿入し、その複数の光ファイバケーブルを加入者宅に引き込むものである。
【０００３】
図１は、ＰＯＮのシステム構成図である。
【０００４】
図１のシステムによれば、１つの収容局２に、光ファイバケーブルを介して複数の光スプリッタ３が接続されている。収容局２と光スプリッタ３との間を接続する光ファイバネットワークは、一般に「ＯＤＮ」と称される。また、光スプリッタ３は、収容局２に接続する１本の光ファイバケーブルを、光加入者ユニット（ＯＮＵ(Optical Network Unit)）４に接続する複数の光ファイバケーブルに分岐する。光スプリッタ３と光加入者ユニット４との間の光ファイバケーブルは、一般に「ドロップケーブル」と称される。図１のシステムにおける光スプリッタ３は、スターカプラのような電気装置を必要としない受動的な素子を用いており、「Passive」と称される。
【０００５】
通信事業者によって敷設される通信局間のケーブルの敷設経路は、熟練技術者に依存して、以下のような２つのステップによって設計されていた。例えばＰＯＮの場合、少なくとも１つの収容局の位置は、予め与えられている。
（ステップ１）最初に、光スプリッタの配置位置が決定される。この位置は、光ファイバケーブルの敷設可能な経路だけでなく、トラヒックの需要予測や、加入者端局の分布密度、等の情報に基づいて決定される。
（ステップ２）次に、収容局に対して全ての光スプリッタを結ぶように、光ファイバケーブルの敷設経路が決定される。ここで、以下の２つが考慮される。
「敷設される伝送ケーブルの総延長」
「伝送ケーブルの敷設工事区間の総延長」
しかしながら、熟練技術者に依存するために、ケーブルの敷設経路の設計には、膨大な手間と時間を要することとなる。
【０００６】
従来、ＰＯＮにおける光ファイバケーブルの敷設コストを最小化するための技術がある（例えば非特許文献１及び２参照）。この技術によれば、収容局を中心とした円形のエリア内に、加入者宅内の光加入者ユニットが一様に分布していることを前提とする。
【０００７】
また、ＯＤＮとして敷設される光ファイバケーブルの総延長を、準最適解となるように設計する技術もある（例えば特許文献１及び２参照）。この技術によれば、前述したステップ１における収容局及び光スプリッタの配置位置を、自動的且つ最適に決定する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−２０４７８０号公報
【特許文献２】特願２００９−２１８１９５号公報
【非特許文献】
【０００９】
【非特許文献１】宇田川大輔、松本隆男、「多段分岐光アクセスネットワークの最小光ファイバ長に関する検討」、電子情報通信学会総合大会、B-8-29、2003年
【非特許文献２】宇田川大輔、松本隆男、「多段分岐アクセスネットワークのコスト最小化条件に関する検討」、電子情報通信学会総合大会、B-8-11、2004年
【非特許文献３】S. Dreyfus, R. Wagner, “\lochThe Steiner problem in graphs,”\loch Networks 1, pp.195-207, (1972).
【非特許文献４】Xianlong Hong, et al., “\lochTIGER: An Effcient Timing-Driven Global Router for Gate Arrayand Standard Cell Layout Design,”\loch IEEE Trans. On Computer-aided Design of Integrated Circuits andSystems, Vol. 16, No. 11, Nov., pp. 1323-1331, (1997).
【発明の概要】
【発明が解決しようとする課題】
【００１０】
一般的に、単位長さあたりで比較すると、光ファイバケーブルの敷設工事コストは、光ファイバケーブルの材料コストよりも、大幅に高価である。このため、ＯＤＮ構築コストを低減するためには、「伝送ケーブルの敷設工事区間の総延長」に対する準最適解を導出する必要がある。しかしながら、熟練技術者に依存した場合、ＯＤＮが、敷設コストに対する準最適解となっているか否かを確認することは不可能であった。
【００１１】
図２は、伝送ケーブルの総延長と敷設工事区間の総延長との関係を表す説明図である。
【００１２】
図２によれば、例えば、１つの収容局と、３つの光スプリッタと、収容局及び光スプリッタ以外の２つのノード（例えば道路の交差点や、送電線の設備点（電柱））とが配置されており、ケーブルの敷設候補（図２（ａ）参照）が表されている。Ｌ１〜Ｌ９は、距離を表す。
［敷設１］（図２（ｂ）参照）ケーブルの総延長を最短にした場合（Ｌ１，Ｌ２＋Ｌ３＋Ｌ８，Ｌ５）、工事区間の総延長は、Ｌ１＋Ｌ２＋Ｌ３＋Ｌ５＋Ｌ８となる。
［敷設２］（図２（ｃ）参照）一方で、工事区間の総延長を最短にした場合（Ｌ２＋Ｌ３＋Ｌ８，Ｌ６，Ｌ４）、ケーブルの総延長は、３×Ｌ２＋２×Ｌ３＋Ｌ４＋Ｌ６＋Ｌ８となる。
ここで、敷設工事コストをできる限り低額で抑えるためには、工事区間の総延長を最短にするべく［敷設２］を選択すべきである。
【００１３】
また、前述した非特許文献１及び２に記載された技術によれば、以下の２つの点を前提としている。
（前提１）前提として、収容局を中心とした円形のエリア内に、ＰＯＮの加入希望者宅が一様に分布している。
（現実１）現実的には、加入希望者宅が非一様に分布しおらず、また、収容局がカバーするエリアの形状も円形でない。
【００１４】
（前提２）前提として、光ファイバケーブルは、任意の場所に、敷設可能である。即ち、エリアでは、光ファイバケーブルを自由に敷設することができる。
（現実２）現実的には、光ファイバケーブルは、架空送電線網や道路網に沿って敷設する必要がある。
【００１５】
前述したステップ１（光スプリッタ設置位置の決定）のみであれば、準最適解が得られる。しかしながら、前述したステップ２（ＯＤＮの設計）では、光ファイバケーブルの総延長に対する準最適解を得るにすぎず、光ファイバケーブル工事区間の総延長は、全く考慮されていない。
【００１６】
そこで、本発明は、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができるケーブル敷設設計用のプログラム、装置及びシステムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計用のプログラムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと
を有し、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップと
してコンピュータを実行させることを特徴とする。
【００１８】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第１のステップは、最小シュタイナー木(Minimum Steiner Tree)を導出するアルゴリズムを用いることも好ましい。
【００１９】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第１のステップは、
ノードＶ（＝｛ｖ1,ｖ2,・・・,ｖn｝）の部分集合Ｔに、収容局及び分岐局の位置情報ｔを含める第１１のステップと、
部分集合Ｔに含まれるノードｔの任意の２点の組み合わせ毎に、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となるパスを探索する第１２のステップと、
第１２のステップによって探索されたパス上に存在するノードｖを、ツリー状グラフＧ'（Ｖ',Ｅ'）に追加する第１３のステップと、
第１２のステップによって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する第１４のステップと
を有し、ツリー状グラフＧ'が連結するまで、第１２〜第１４のステップを繰り返すことも好ましい。
【００２０】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
第２のステップの最短経路探索アルゴリズムは、部分集合Ｔに含まれる２点のノード同士の総当たりに対するダイクストラ(Dijkstra)法を用いることも好ましい。
【００２１】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
敷設コストｗは、ケーブルの敷設費用に基づく数値、又は、ケーブルの線路長に基づく数値であることも好ましい。
【００２２】
本発明のケーブル敷設設計用のプログラムにおける他の実施形態によれば、
伝送ケーブルは、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルであり、
分岐局は、光スプリッタであり、
収容局及び分岐局以外のノードは、物理的な敷設設備である
ことも好ましい。
【００２３】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計装置であって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有することを特徴とする。
【００２４】
本発明によれば、伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するケーブル敷設設計システムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
位置情報データベース及び敷設可能経路情報データベースとネットワークを介して接続された敷設経路設計装置と
を有し、
敷設経路設計装置は、
収容局及び分岐局毎の位置情報ｔと敷設可能経路情報Ｇ（Ｖ,Ｅ）とを用いて、Ｔに含まれる全てのノードを閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
ツリー状グラフＧ'（Ｖ',Ｅ'）上について、敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有する
ことを特徴とする。
【発明の効果】
【００２５】
本発明のケーブル敷設設計用のプログラム、装置及びシステムによれば、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができる。
【図面の簡単な説明】
【００２６】
【図１】ＰＯＮのシステム構成図である。
【図２】伝送ケーブルの総延長と敷設工事区間の総延長との関係を表す説明図である。
【図３】伝送ケーブルを敷設可能なグラフ状の経路を表す説明図である。
【図４】本発明における敷設経路設計装置の機能構成図である。
【図５】本発明における第１の実施形態のフローチャートである。
【図６】最短経路探索アルゴリズムを説明するグラフである。
【図７】本発明における第２の実施形態のフローチャートである。
【図８】具体的な敷設経路の第１の設計過程を表す説明図である。
【図９】具体的な敷設経路の第２の設計過程を表す説明図である。
【図１０】具体的な敷設経路の第３の設計過程を表す説明図である。
【図１１】具体的な敷設経路の第４の設計過程を表す説明図である。
【図１２】本発明におけるシステム構成図である。
【発明を実施するための形態】
【００２７】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２８】
図３は、伝送ケーブルを敷設可能なグラフ状の経路を表す説明図である。
【００２９】
図３の経路によれば、収容局２と複数の光スプリッタ（分岐局）３との間の伝送ケーブルは、グラフ状に敷設可能となっている。ここで、以下のように定義する。
収容局の位置：Ｃ
光スプリッタの位置：ＳＰＬi（i=1,2,…,N）
ノードｖi（i=1,2,…,K1）、ノードの集合Ｖ＝｛ｖ1,ｖ2,・・・,ｖK1｝
エッジｅj（j=1,2,…,K2）、エッジの集合Ｅ＝｛ｅ1,ｅ2,・・・,ｖK2｝
エッジｅjの重みｗj（j=1,2,…,K2）
【００３０】
ノード（節点）ｖは、物理的な位置情報であって、収容局及び光スプリッタの位置情報も含むものとする。
エッジ（枝）ｅは、ノードｖ同士を結ぶ。
例えば、敷設可能経路として道路網を想定する場合、以下のように対応付けられる。
ノードｖ：例えば道路の交差点や、送電線の設備点（電柱）の位置情報
（収容局及び光スプリッタの位置情報を含む）
エッジｅ：道路の交差点同士や送電線の設備点同士の間を結ぶ、道路や送電線
重みｗ ：道路や送電線ｅの長さ（敷設コストにつながる）
【００３１】
図４は、本発明における敷設経路設計装置の機能構成図である。
【００３２】
敷設経路設計装置１は、伝送ケーブル（例えば光ファイバケーブル）の敷設可能経路網Ｇ（Ｖ,Ｅ）上に、収容局及び光スプリッタの全ての通信局を結ぶ敷設経路を決定する。敷設経路設計装置１は、敷設可能経路情報データベース１０１と、位置情報データベース１０２と、パラメータ記憶部１０３と、ツリー状グラフ生成部１１１と、２点間経路決定部１１２と、設計結果出力部１１３とを有する。敷設経路設計装置１は、例えばパーソナルコンピュータやサーバのようなものであって、その装置１に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００３３】
［敷設可能経路情報データベース１０１］
敷設可能経路情報データベース１０１は、敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶する。敷設可能経路情報Ｇは、伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとを用いて表現したものである。また、各エッジｅには、敷設コストｗも付与される。
【００３４】
［位置情報データベース１０２］
位置情報データベース１０２は、ノードＶの部分集合Ｔとして、収容局Ｃ及び光スプリッタＳＰＬi毎の位置情報ｔを記憶する。即ち、物理的なノード（節点）の位置情報ｖは、収容局及び分岐局の位置情報も含んでいる。
【００３５】
［パラメータ記憶部１０３］
パラメータ記憶部１０３は、ノードｖの部分集合Ｔとなるツリー状グラフＧ'（Ｖ',Ｅ'）を、算出過程の中で一時的に記憶する。
【００３６】
［ツリー状グラフ生成部１１１］
ツリー状グラフ生成部１１１は、全てのノード間について、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する。ここで、ツリー状グラフＧ'を生成するために、２つの実施形態がある。
（第１の実施形態）最小シュタイナー木を導出するアルゴリズムを用いる
（比較的演算量が多い）
（第２の実施形態）最小シュタイナー木に準ずる木を導出するアルゴリズムを用いる
（比較的演算量が少ない）
【００３７】
［２点間経路決定部１１２］
２点間経路決定部１１２は、ツリー状ネットワークＧ'（Ｖ',Ｅ'）について、敷設コストが最小となるべき、収容局から各分岐装置を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する。最短経路探索アルゴリズムとしては、例えばダイクストラ(Dijkstra)法を用いることができる。
【００３８】
［設計結果出力部１１３］
設計結果出力部１１３は、最終的にパラメータ記憶部１０３に記憶された設計結果を、オペレータに明示するべくディスプレイへ出力する。これによって、オペレータは、伝送ケーブルの敷設経路を認識することができる。
【００３９】
図５は、本発明における第１の実施形態のフローチャートである。
【００４０】
（Ｓ５１）最初に、位置情報データベース１０２に記憶された収容局Ｃ及び光スプリッタＳＰＬi全ての位置情報を、ノードＶの部分集合Ｔとする。
【００４１】
（Ｓ５２）次に、最小シュタイナー木を導出するアルゴリズムを用いて、収容局Ｃ及び光スプリッタＳＰＬi全てを含む最小シュタイナー木を算出する。この木は、敷設可能経路情報データベース１０１に記憶されたノードｖ及びエッジｅを用いて算出される。
【００４２】
第１の実施形態によれば、「シュタイナー木(Steiner Tree)」を生成する。「シュタイナー木」とは、グラフＧに対して、ノードＶの部分集合Ｔ（T={t1,t2,…,tk}, k≦K1）が与えられた場合、部分集合Ｔに含まれる全てのノードを含む木をいう。この木は、閉路を持たない連結グラフである。
【００４３】
ここで、本発明によれば、特に「最小シュタイナー木(Minimum Steiner Tree)」を生成する。「最小シュタイナー木」問題とは、エッジｅjに重みｗjが付与されたグラフＧにおけるノードＶの部分集合Ｔについて、エッジｅの重みの総和ｗが最も小さくなるシュタイナー木を算出することをいう。最小シュタイナー木問題は、ＮＰ(Non-deterministic Polynomial time)困難であることが周知となっている。最小シュタイナー木を導出するアルゴリズムとしては、例えば非特許文献３及び非特許文献４に記載の技術がある。
【００４４】
パラメータ記憶部１０３は、最小シュタイナー木について、ノードｖ'i（i=1,2,…,K'1）及びエッジｅ'j（j=1,2,…,K'2）によって構成されるグラフＧ’＝（Ｖ',Ｅ'）を記憶する。尚、最小シュタイナー木Ｇ’は、グラフＧの一部（Ｇ'⊆Ｇ）であるため、K'1≦K1、K'2≦K2であることは明らかである。
【００４５】
（Ｓ５３）最小シュタイナー木のグラフＧ'＝（Ｖ',Ｅ'）上で、各光スプリッタＳＰＬi（i=1,2,…,N）から収容局Ｃまでの経路を、最短経路探索アルゴリズム（２点間経路決定部において実施）を用いて算出する。
【００４６】
図６は、最短経路探索アルゴリズムを説明するグラフである。
【００４７】
ここでは、最短経路探索アルゴリズムとして、ダイクストラ(Dijkstra)法を用いる。図６のグラフは、□で表された交差点（ノード）と、線で表された道路（エッジ）とからなる。また、各エッジには、例えばエッジの長さ（道路の長さ）に対応する重みｗが付与されている。グラフには、起点及び終点が予め指定されており、ダイクストラ法によって、起点及び終点を結ぶ最短経路（＝重みの総和が最小となる経路）が導出される。
【００４８】
この方法は、各第ｉ次ノードについて、隣接する第（ｉ＋１）次ノードを見出す。そして、各第（ｉ＋１）次ノードについて、以下の３つを記憶する。
（１）１ホップ前の第ｉ次ノードを経由する起点からの累積距離
（２）起点までのホップ数
（３）１ホップ前のノードのノード番号
最終的に、終点に到達した際に、順次、０次ノード（起点）まで辿ることによって、起点と終点とを結ぶ経路を作成する。この経路が、起点と終点を結ぶ最短の経路となる。
ｍ次ノード -> （ｍ−１）次ノード -> （ｍ−２）次ノード・・・
【００４９】
（Ｓ６１）起点を０次ノードとして、当該０次ノードからエッジに沿って隣接する１次ノードＡ1〜Ａ2を探索する。そして、１次ノードＡ1，Ａ2それぞれは、以下の情報を記憶する。
Ａ1 -> 起点−Ａ1間の累計距離Ａｄ1
起点までのホップ数：１
１ホップ前のノード：起点
Ａ2 -> 起点−Ａ2間の累計距離Ａｄ2
起点までのホップ数：１
１ホップ前のノード：起点
【００５０】
（Ｓ６２）次いで、各１次ノードＡ1及びＡ2について、２次ノードＢijを探索する。
１次ノードＡ1については、３つの２次ノードＢ11，Ｂ12，Ｂ13を見出す。２次ノードＢ11，Ｂ12，Ｂ13に対して、以下の情報を登録する。
Ｂ11 -> 起点−Ａ1−Ｂ11間の累計距離Ｂｄ11
起点までのホップ数：２
１ホップ前のノード：Ａ1
Ｂ12 -> 起点−Ａ1−Ｂ12間の累計距離Ｂｄ12
起点までのホップ数：２
１ホップ前のノード：Ａ1
Ｂ13 -> 起点−Ａ1−Ｂ13間の累計距離Ｂｄ13
起点までのホップ数：２
１ホップ前のノード：Ａ1
【００５１】
同様に、１次ノードＡ2については、２つの２次ノードＢ21，Ｂ22を見出す。２次ノードＢ21，Ｂ22に対して、以下の情報を登録する。
Ｂ21 -> 起点−Ａ2−Ｂ21間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
Ｂ22 -> 起点−Ａ2−Ｂ22間の累計距離Ｂｄ22
起点までのホップ数：２
１ホップ前のノード：Ａ2
【００５２】
ここで、ノードＢ13及びＢ21は、同一ノードである。このように、重複した１つのノードに対して、異なる経路の累積距離のデータが記憶される場合がある。この場合、起点からの累積距離Ｂｄ13とＢｄ21との大小関係を比較し、大きい方のデータを破棄し、小さい方のデータのみを記憶する。例えば、Ｂｄ13＞Ｂｄ21であれば、ノードＢ13（＝Ｂ21）には、累計距離Ｂｄ21と対応する１ホップ前のノードＡ2の番号が最終的に記憶される。
［Ｂｄ13＞Ｂｄ21］
Ｂ13 -> 起点−Ａ1−Ｂ13間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
Ｂ21 -> 起点−Ａ2−Ｂ21間の累計距離Ｂｄ21
起点までのホップ数：２
１ホップ前のノード：Ａ2
【００５３】
（Ｓ６３）以降、同様に、各２次ノードＢijについて、隣接する３次ノードＣijを探索する。これを繰り返すことによって、探索が、終点に到達する。
【００５４】
例えば、２次ノードB12及びB13（B21）は、３次ノードとしての終点を探索する。ここで、以下の２つの経路が検出される。
起点−Ａ1−Ｂ12−終点 ：累計距離（短い）
起点−Ａ2−Ｂ13（Ｂ21）−終点 ：累計距離（長い）
終点に到達した場合、累計距離が短い方の経路が、最短経路として決定される。例えば、図６によれば、起点−Ａ1−Ｂ12−終点が、最短経路として決定される。
【００５５】
図７は、本発明における第２の実施形態のフローチャートである。
【００５６】
図５で前述した第１の実施形態のフローチャートによれば、「最小シュタイナー木」のアルゴリズムを用いた。「最小シュタイナー木」は、グラフＧと、Ｖの部分集合（＝全光スプリッタ及び収容局の位置を含む）（T={t1,t2,…,tk}, k≦K1）に基づいて、Ｔに含まれるノード全てを含む木を導出する。この最小シュタイナー木によれば、エッジの重みの総和が最小となる。
【００５７】
しかしながら、このような最小シュタイナー木アルゴリズムの計算量のオーダは、３のＴの要素数乗（Ｏ(3k)）であることが分かっている。このため、Ｔの要素数が増加すると、計算量が爆発的に増加するという課題がある。
【００５８】
そこで、図７の第２の実施形態によれば、エッジの重みの総和が望ましい程度に小さいシュタイナー木（つまり、「最小シュタイナー木に準ずる木」）を導出する技術を用いる。この技術によれば、エッジの重みの総和が確実に最小となるまで算出しないために、短時間で、ツリー状グラフの木を導出することができる。
【００５９】
（Ｓ７１）最初に、位置情報データベース１０２に記憶された収容局Ｃ及び光スプリッタＳＰＬi全ての位置情報を、ノードＶ（={ｖ1,ｖ2,・・・,ｖn}）の部分集合Ｔとする。
【００６０】
（Ｓ７２）次に、パラメータ記憶部１０３に対して、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）の保存用に割り当てられている記憶領域を初期化する。Ｖ'及びＥ'を共に、空集合とする。
【００６１】
（Ｓ７３）次に、部分集合Ｔに含まれるノードｔの任意の２点（ti,tj（i≠j））の組み合わせ毎に、光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）上におけるti−tj間の最短経路を探索する。即ち、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となる経路を探索する。その結果は、パラメータ記憶部１０３に保存される。
【００６２】
（Ｓ７４）パラメータ記憶部１０３に保存された全ての経路について、重み（長さ）の総和がゼロでない経路を抽出する。その中で、重みの総和が最小の経路tp−tqを検索する。
【００６３】
（Ｓ７５）当該経路について、両端ノードであるtp、tqを含め、当該経路を構成するノードｖ及びエッジｅの集合を、シュタイナー木Ｇ'に追加する。
【００６４】
（Ｓ７６）また、Ｓ７５によって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する。即ち、光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）について、Ｇ'に追加された経路を構成するエッジの重みｗの値をゼロ（０）に変更する。
【００６５】
（Ｓ７７）最後に、シュタイナー木Ｇ'を構成するノードの集合Ｖ'が、Ｔを全て含み（Ｔ⊆Ｖ'）、且つ、連結グラフかどうかを確認する。この条件を満たす場合、Ｓ７８へ移行し、満たさない場合、Ｓ７３へ移行する。
【００６６】
（Ｓ７８）最小シュタイナー木のグラフＧ'＝（Ｖ',Ｅ'）上で、各光スプリッタＳＰＬi（i=1,2,…,N）から収容局Ｃまでの経路を、最短経路探索アルゴリズム（２点間経路決定部において実施）を用いて算出する。前述した図５のＳ５３の処理と全く同様である。
【００６７】
ここで、第２の実施形態における計算量のオーダについて検討する。ダイクストラ法の計算量のオーダは、グラフＧに含まれるノード数の二乗であることが知られている。第２の実施形態によれば、ダイクストラ法による演算が、Ｔに含まれるノード間の全組合せについて実施されるために、全体の計算量のオーダは、K12×k2に比例する（Ｏ(K12×k2)）。このため、光スプリッタ数の多い（kが大きい）場合では、第２の実施形態によって、大幅に計算量を削減（＝設計処理の高速化）することができる。
【００６８】
最後に、第２の実施形態における具体的な敷設経路の設計について説明する。
【００６９】
図８は、具体的な敷設経路の第１の設計過程を表す説明図である。
【００７０】
簡単化のために、ここでは、敷設可能経路網情報データベースに保存されている光ファイバ敷設可能経路網Ｇ（Ｖ，Ｅ）は、以下の要素から構成されているとする。
１１個のノード（Ｖ＝{ｖ1,…,ｖ11}）
１６本のエッジ（Ｅ＝{e1,…,e16}）
各エッジｅは、初期状態ではエッジの長さで重み付けされているものとする。また、位置情報データベースには、３個の光スプリッタ及び収容局の位置情報が保存されているものとする。
【００７１】
図９は、具体的な敷設経路の第２の設計過程を表す説明図である。
【００７２】
最初に、Ｓ７１について、光スプリッタ及び収容局を、Ｖの部分集合Ｔ＝{t1,t2,t3,t4}とする。ここで、t1=v7, t2=v4, t3=v10, t4=v8であるものとする。
次に、Ｓ７２について、シュタイナー木Ｇ'を初期化する。
【００７３】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t1−t3が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ'＝{t1,t2,t3,t4}， Ｅ'＝{e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではｅ14）の重みを、ゼロとおく。
この時点では、Ｖ'に含まれないＴの要素がある（Ｔ⊆Ｖ'でない）ため、Ｓ７３へ戻る。
【００７４】
図１０は、具体的な敷設経路の第３の設計過程を表す説明図である。
【００７５】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t2−t4が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ’＝{t1,t2,t3,t4,v5}， Ｅ'＝{e4,e7,e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではe4,e7）の重みを、ゼロとおく。
この時点では、ＴはＶ'に含まれる（Ｔ⊆Ｖ'）ものの、Ｇ'は、連結グラフでないため、Ｓ７３へ戻る。
【００７６】
図１１は、具体的な敷設経路の第４の設計過程を表す説明図である。
【００７７】
次に、Ｓ７３及びＳ７４について、Ｔに含まれるノード同士の中で、Ｇ上で当該２つのノードを結ぶパスの重みの総和が最小となるノード同士を探索する。ここでは、経路t1−t2が見出されたとする。
次に、Ｓ７５について、当該経路を構成するノード及びエッジを、シュタイナー木Ｇ'＝（Ｖ'，Ｅ'）に追加する。
Ｖ'＝{t1,t2,t3,t4,v5,v6}， Ｅ'＝{e4,e6,e7,e11,e14}
次に、Ｓ７６について、Ｇ上で、当該経路に含まれるエッジ全て（ここではe4,e6,e11）の重みを、ゼロとおく。
この時点では、ＴはＶ'に含まれ（Ｔ⊆Ｖ'）、且つ、Ｇ'は連結グラフとなるために、Ｓ７８へ移行する。
【００７８】
最後に、Ｇ'＝（Ｖ'，Ｅ'）上で、それぞれの光スプリッタＳＰＬi（i=1,2,3）に対して、収容局Ｃまでの経路を、最短経路探索アルゴリズムを用いて算出する。最終的に、図１１のような経路が、最短経路として算出される。
【００７９】
図１２は、本発明におけるシステム構成図である。
【００８０】
図１２のシステムによれば、図４と比較して、敷設可能経路情報データベース１０１及び位置情報データベース１０２と、敷設経路設計装置１とが、ネットワークを介して接続されている。例えば敷設経路設計装置１がパーソナルコンピュータであってもよく、ネットワークに接続されたデータベースから情報を取得することによって、敷設経路を設計することができる。
【００８１】
前述したように、本発明のケーブル敷設設計用のプログラム、装置及びシステムによれば、伝送ケーブルの工事区間の総延長に対する準最適解を得ることができる。
【００８２】
例えばＰＯＮの光ファイバケーブルにおける敷設経路を設計する場合、複数の光スプリッタの位置と収容局の位置が与えられていても、光ファイバケーブルの敷設可能経路に対して制約条件が存在する。ここで、光スプリッタの全てを収容局に収容する場合、本発明によれば、光ファイバケーブル工事区間の総延長に対して準最適となるＯＤＮを自動的に設計することができる。また、本発明によって設計されたＯＤＮ構築コストは、従来法（熟練した技術者による手作業や、特許文献１及び２に記載の手法）で設計されたコストよりも低くなる。更に、本発明の第２の実施形態によってＯＤＮを設計した場合、少ない演算量で、短時間に設計することができる。本発明によれば、特に、ＰＯＮサービスを展開する通信事業者における、ＦＴＴＨネットワークの設計に適する。
【００８３】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００８４】
１ 敷設経路設計装置
１０１ 敷設可能経路情報データベース
１０２ 位置情報データベース
１０３ パラメータ記憶部
１１１ ツリー状グラフ生成部
１１２ ２点間経路決定部
１１３ 設計結果出力部
【特許請求の範囲】
【請求項１】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計用のプログラムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと
を有し、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップと
してコンピュータを実行させることを特徴とするケーブル敷設設計用のプログラム。
【請求項２】
第１のステップは、最小シュタイナー木(Minimum Steiner Tree)を導出するアルゴリズムを用いることを特徴とするケーブル敷設設計用のプログラム。
【請求項３】
第１のステップは、
ノードＶ（＝｛ｖ1,ｖ2,・・・,ｖn｝）の部分集合Ｔに、収容局及び分岐局の位置情報ｔを含める第１１のステップと、
部分集合Ｔに含まれるノードｔの任意の２点の組み合わせ毎に、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となるパスを探索する第１２のステップと、
第１２のステップによって探索されたパス上に存在するノードｖを、ツリー状グラフＧ'（Ｖ',Ｅ'）に追加する第１３のステップと、
第１２のステップによって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する第１４のステップと
を有し、前記ツリー状グラフＧ'が連結するまで、第１２〜第１４のステップを繰り返すことを特徴とする請求項１に記載のケーブル敷設設計用のプログラム。
【請求項４】
第２のステップの最短経路探索アルゴリズムは、部分集合Ｔに含まれる２点のノード同士の総当たりに対するダイクストラ(Dijkstra)法を用いることを特徴とする請求項１から３のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項５】
前記敷設コストｗは、ケーブルの敷設費用に基づく数値、又は、ケーブルの線路長に基づく数値であることを特徴とする請求項１から４のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項６】
前記伝送ケーブルは、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルであり、
前記分岐局は、光スプリッタであり、
収容局及び分岐局以外のノードは、物理的な敷設設備である
ことを特徴とする請求項１から５のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項７】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計装置であって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有することを特徴とするケーブル敷設設計装置。
【請求項８】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するケーブル敷設設計システムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
前記位置情報データベース及び前記敷設可能経路情報データベースとネットワークを介して接続された敷設経路設計装置と
を有し、
前記敷設経路設計装置は、
収容局及び分岐局毎の位置情報ｔと敷設可能経路情報Ｇ（Ｖ,Ｅ）とを用いて、Ｔに含まれる全てのノードを閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有する
ことを特徴とするケーブル敷設設計システム。
【請求項１】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計用のプログラムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストｗを記憶する敷設可能経路情報データベースと
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと
を有し、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成する第１のステップと、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する第２のステップと
してコンピュータを実行させることを特徴とするケーブル敷設設計用のプログラム。
【請求項２】
第１のステップは、最小シュタイナー木(Minimum Steiner Tree)を導出するアルゴリズムを用いることを特徴とするケーブル敷設設計用のプログラム。
【請求項３】
第１のステップは、
ノードＶ（＝｛ｖ1,ｖ2,・・・,ｖn｝）の部分集合Ｔに、収容局及び分岐局の位置情報ｔを含める第１１のステップと、
部分集合Ｔに含まれるノードｔの任意の２点の組み合わせ毎に、両ノードを結ぶパス（経路）上に存在するエッジｅに付与された敷設コストｗの総和が最小となるパスを探索する第１２のステップと、
第１２のステップによって探索されたパス上に存在するノードｖを、ツリー状グラフＧ'（Ｖ',Ｅ'）に追加する第１３のステップと、
第１２のステップによって探索されたパス上に存在するエッジｅについて、付与された敷設コストｗを０に設定する第１４のステップと
を有し、前記ツリー状グラフＧ'が連結するまで、第１２〜第１４のステップを繰り返すことを特徴とする請求項１に記載のケーブル敷設設計用のプログラム。
【請求項４】
第２のステップの最短経路探索アルゴリズムは、部分集合Ｔに含まれる２点のノード同士の総当たりに対するダイクストラ(Dijkstra)法を用いることを特徴とする請求項１から３のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項５】
前記敷設コストｗは、ケーブルの敷設費用に基づく数値、又は、ケーブルの線路長に基づく数値であることを特徴とする請求項１から４のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項６】
前記伝送ケーブルは、ＰＯＮ(Passive Optical Network)用のＯＤＮ(Optical Distribution Network)における光ファイバケーブルであり、
前記分岐局は、光スプリッタであり、
収容局及び分岐局以外のノードは、物理的な敷設設備である
ことを特徴とする請求項１から５のいずれか１項に記載のケーブル敷設設計用のプログラム。
【請求項７】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するように、装置に搭載されたコンピュータを機能させるケーブル敷設設計装置であって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
全ての収容局及び分岐局Ｔを、閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有することを特徴とするケーブル敷設設計装置。
【請求項８】
伝送ケーブルを敷設可能なグラフ状の経路上で、収容局と複数の分岐局との間（ノード間）における伝送ケーブルの敷設経路を決定するケーブル敷設設計システムであって、
伝送ケーブルを敷設可能な経路について、物理的なノード（節点）の位置情報ｖ（収容局及び分岐局の位置情報を含む）と、それらノードを結ぶエッジ（枝）ｅとによって表現した敷設可能経路情報Ｇ（Ｖ,Ｅ）を記憶すると共に、各エッジｅに付与された敷設コストを記憶する敷設可能経路情報データベースと、
ノードＶの部分集合Ｔとして、収容局及び分岐局毎の位置情報ｔを記憶する位置情報データベースと、
前記位置情報データベース及び前記敷設可能経路情報データベースとネットワークを介して接続された敷設経路設計装置と
を有し、
前記敷設経路設計装置は、
収容局及び分岐局毎の位置情報ｔと敷設可能経路情報Ｇ（Ｖ,Ｅ）とを用いて、Ｔに含まれる全てのノードを閉路のない連結グラフで結んだツリー状グラフＧ'（Ｖ',Ｅ'）を生成するツリー状グラフ生成手段と、
前記ツリー状グラフＧ'（Ｖ',Ｅ'）上について、前記敷設コストの総和が最小となるべき、収容局から各分岐局を結ぶ２点間経路を、最短経路探索アルゴリズムによって探索する２点間経路決定手段と
を有する
ことを特徴とするケーブル敷設設計システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１３−３８７６（Ｐ２０１３−３８７６Ａ）
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１１−１３４８２２（Ｐ２０１１−１３４８２２）
【出願日】平成２３年６月１７日（２０１１．６．１７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２３年６月１７日（２０１１．６．１７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]