利用者:斎藤四郎
線形ネットワーク流量解析モデル
[編集]現在のネットワーク最大流量問題解析手法は、多項式アルゴリズムで行なわれている。また、自然現象におけるネットワーク流量現象においても、線形だけでは表すことは出来ないと考える。 しかしネットワーク内流量が微量であった場合、経路（アーク）容量に比例した流量が発生することは誰もが想定できる。 容量に比例した流量が経路内に発生すると考えれば、最小カット面も発生しないし解析も非常に簡単なものとなる。ここで自然現象から考えると、交通量が増大した道路ネットワークにおいて、特定の経路で車の速度減少が見られる。この流体減速にネットワーク流量解析に大きなヒントがある。 ここで理想ネットワーク構成について考察してみる。理想ネットワーク構成では、ネットワーク内全てのノードで総入力容量と総出力容量が等しい。このとき最小カット面の存在はない。開始ノード総出力容量がネットワーク最大流量となる。 ネットワーク流量計算するために経路有効容量を想定する。即ち特定経路内流速減少に大して有効容量を想定する。この有効流量を使って線形ネットワーク流量計算をおこなう。
ネットワーク流量形態について
[編集]ネットワーク流量が増大するにあたって以下の３種類のネットワーク流量フェーズを考える。 ①第一フェーズ：ネットワーク流量が微小で、経路容量に比例した流量が流れる流量状態。 ②第二フェーズ：ボトルネックノードが発生し、そのボトルネックノードを迂回し流量が流れるネットワーク流量状態。 ③第三フェーズ：ネットワーク内に全てのボトルネックが出尽くし、最小カット面が形成され最小カット面を上流域にさかのぼる流量が抑止され、最小カット面が確定される。このフェーズで全ての経路内流量は、必ずしも経路容量に比例しない。ここで有効容量を使用し線形流量計算を行なう。有効容量の決定を理想ネットワーク構成でのノード毎の総入力容量と総出力容量が等しいという条件から行なう。 この有効容量という考えかたを導入すれば、多項式アルゴリズムを使用せずに線形モデルでネットワーク解析が可能となる。また、市販PCで１００ノード構成ネットワーク流量解析が３０秒前後で解析可能となることを確認した。また、ネットワーク構成改善についての数値解析も可能となる。旧来の解析手法は、数学的側面から行なわれている。しかし物理的側面からネットワーク流量解析を行なえば、簡単な数式で流量解析が可能となる。なお全ての経路流量が確定されると、ネットワーク内全流量ルートが検索出来る。このルート検索結果で最小コストルート、最短路等の解析も可能となった。