数理解析研究所講究録 1297 巻 2002 年 89-95

89
施設配置を考慮したネットワーク・デザイン問題について
早稲田大学・商学部

毛利裕昭 (Hiroaki Mohri)

School of Colnmerce,Waseda University.
mohri@waseda jp, mohri@me1nber.ams.org

1

はじめに

ネットワーク・デザイン問題は, あるグラフ上にネットワークをどう構築する
力 , つまり主としてアークの敷設場所を論じる問題である. そのバリエーションはネットワーク上を流れるフローを含めた最適化をはじめ数多くある. 工学的応用も,$\mathrm{a}$コンピュータや通信ネットワーク, 交通網ネットワー久 ロジステイクスネットワー

久ガス・電カネットワー久 航空ネットワークと枚挙に暇がない.
ベーシックなネットワーク・デザイン問題については, Wynants [6] が 2001 年に刊行した著作にこれまでの研究動向がまとめられている. ここでは, アークの配置,フローの制御といったベーシツクな条件を考慮だけでなく, 特殊な性質をもつノードへの施設配置とその設置コストを考慮した問題を考える. つまり, ネットワーク.
デザイン問題に施設配置問題で考えられている条件を組み入れた問題である.
施設配置問題については, 数多くの研究がなされ現在では学部向けの離散数学やオペレーションズ. リサーチの教科書で取り上げてられておりここでは多くを説明問題もしくは p-median
しない. ここで基礎として考える施設配置問題は,$\mathrm{I}\succ \mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}$問題およひ能力制約なし施設配置問題と一般的に呼ばれているものにイメージとしては近い.
これら 2 つの問題は, 独立のレベルの違う問題として取り上げられてきたという経緯がある. 近年, 日本でサプライ・チェーン. マネジメント ( CM) において焦点になるのは 「全体最適化」 というキーワードである. しかし, ロジステイク$\mathrm{S}$ス工学の観点からは最適化に関して 3 つの階層 (レイヤー) で論じられてきた, そして, その階層化は適切であると考える. その理由は以下による.
・戦略的意思決定階層 : 長期の意思決定を行うレベル : 原価償却が長期間のものが主な対象

・戦術的意思決定階層 : 中期の意思決定を行うレベル : 原価償却が中期間のものが主な対象

・作戦的意思決定階層 : 短期の意思決定を行うレベル : 原価償却が短期間のもの
が主な対象

大きな工場や{?}.庫といったものは, 原価償却が長期間にわたる.

よって, その配置や移転に関する意思決定は戦略的意思決定階層のものと考えるのが一 ff 的である.

施設配置問題はこのレベルと考えるべきものである.

また, 大型トラツクで配90
送拠点間輸送を行う際, 高速道路を利用する定期便スケジュールの計画期間は, 数年といった長期間でなく季節的な問題を考えて数 t 月といった期間で定期的に見直すべきものである. これは, 戦術的意思決定階層の問題である. さらに, 本論文との関わりはないが, 配送拠点からの最終顧客までの配送を考える配送経路問題は作戦的意思決定階層の問題である.
こうして考えると,CM に関しては, 少なくとも日本のように地価や建設費用が高い国では, これらの 3 つの階層を同時に考慮するのは不適切である. 本論では, 上位 2 階層が問題となるが, それらを同時に取り扱うことが不適切と考えられることは言うまでもない.
$\mathrm{S}$

しかし, ネットワーク・デザイン問題に関してロジスティクスと並んでアプリケーションとして考えられる通信ネットワークに目を向けてみる. 通信ネットワー
クにおいては, コンピュータ・サイエンスの著しい発達が原動力になり, 様々なハードウェアが高性能小型化し安価になってきている. ハードウェアの能力や低価格化が著しく進む現象は万人の認めるところであろう. ここで, 通信ネットワークにおいて, かつて巨大であったハードウエアの例を考えてみる. それらには, 交換機, 集線装置といったものがあげられよう. こうしたハードウェアは, その巨大さゆえに場所と大きさを占める上に高額なものであった. しかし, かつてはビルのワンフロアを占めたようなこれらのハードウェアが現在は小型化した上に安価になっている.
しかも, インターネット普及の影響を受けその設置はきわめて柔軟に行われなければならない社会状況である.
通信ネットワークを取り巻くこういった環境により, 通信ネットワークにおける施設配置の問題は, そのハードウェアの原価償却期間も長期レベルでなく中期レベルで考えるべき状況となっている. そこで, 本論では施設配置を考慮したネットワークデザイン問題を施設配置問題とネットワークデザイン問題を併せた離散最適化問題として定式化を行 , その解法について論じる. また, 計算量の理論の観点からは, この問題はネットワーク・デザイン問題の拡張になっているので, NP-hardな問題である [2].
$\mathrm{A}\mathrm{a}$既存研究は, ネットワーク・デザイン問題と施設配置問題の両者を同時考慮したモデルとして Melkote and Daskin $[4, 5]$ の研究がある. 彼らの研究は, 施設配置問題を主としネットワーク・デザイン問題を従とした数学モデルの研究である. これは, 主としてロジスティクスへの応用を意識している. 上記の論文の中には, このモデルに関わる実際問題についての記述がある. それは, 米国という広大な土地があり, 地価力相本と比べて (都市部を除き) 平均すればかなり安いという状況が背景にあるからであると想像できる. また, 工場や倉庫ではその容量が重要な条件となってくる. これに比べて, 通信ネットワークで, 施設の容量条件がないわけではないが, 3 次元の物体を取り扱うロジスティクスの問題に比べれば, ほぼ無視できるものと本論では想定している.

91
2記号

く集合等 $>$
ノード集合
アーク集合

$N$
$A$

$G(N, A)$

グラフ

$M$

$(M\subseteq N)$
施設候補集合品種集合, $K\subseteq N\cross N$$K$

く定数 $>$$\ovalbox{\tt\small REJECT}$$F_{ij}$$L_{i}$

アーク $(i,j)$ に品種$k$が 1 単位流される時のルーテイング (フロー) 費用

アーク ( , 力のデザイン (敷設) 費用
$i$

施設$i$

が, 作られたときの固定費用

ネットワーク上で敷設すべき施設の数 (所与とする)$l$

く決定変数 $>$
$f_{ij}^{k}$$y_{ij}$$z_{i}$のフロー量変数
アーク $(i,j)$ のデザイン (敷設) 変数
施設 の設置変数
アーク $(i,j)$ における品種

$k$

$i$

3

定式化

3.1

アークフロー定式化
ここでは,解釈のし易いアークフロー定式化を記述する.
(1)$\min\sum_{(i,j)\in A}\sum_{k\in K}d_{ij}^{k}f_{ij}^{k}+\sum_{(i,j)\in A}F_{ij}y_{ij}+\sum_{i\in M}L_{i}z_{i}$subject to$\sum_{j\in N-\{i\}}f_{ij}^{k}-\sum_{j\in N-\{i\}}f_{ji}^{k}=\{$$i=O(k)$1$\forall i\in N-\{O(k), D(k)\}\forall k\in K$0-1 $i=D(k)$$\forall(i,j)\in A$$\sum_{k\in K}f_{ij}^{k}\leq|K|y_{ij}$

(2)

(3)
(4)

$\sum_{i\in M}z_{i}=l$$f_{ij}^{k}\geq 0$$y_{ij}\leq z_{i}$$\ovalbox{\tt\small REJECT}_{i}\leq z_{i}$$\forall(i,j)\in A,\forall k\in K$(5)$\forall i\in M$$\forall j\in N$(6)$\forall i\in M$$\forall j\in N$

(7)

92
$y_{ij}\in\{0,1\}$$\forall(i,j)\in A$(8)$\forall i\in M$(9)$z_{i}\in\{0,1\}$(2) は, ネットワーク問題で典型的に現れるフロー保存則の制約式群である. (3) は,アーク上のフロー量が, 使用するアークの容量以下であること示す. (4) は, 施設数制約である. (6),(7) は, アークと施設の関係制約である.

3.2

パスフロ–定式化

アークフロー定式化は, 定式化は直感的にはわかり易いという利点をもつ.
方, 以下に示すパスフロー定式化は, 解釈さえ理解できればシンプルである.

–記号は, アークフロー定式化で利用している記号を用いるが以下のように読みかえる.

<集合等 $>$$P^{k}$

品種$k$の取りうるパスの集合

く定数 $>$$d_{k}^{\mathrm{p}}$

パス $p$ に品種 $k$ が 1 単位流される時のルーティング (フロー)アーク$e$

L。 アーク$e$$F_{e}$

費用のデザイン (敷設) 費用の終点 (始点でも可) に施設が, 作られたときの固定費用<決定変数 $>$$f_{p}^{k}$y。
z。

パス $p$ における品種 $k$ のフロー量変数のデザイン (敷設) 変数
基準化された, アーク の終点 (始点でも可) 設置変数
アーク$e$$e$z。が基準化されているとは, を用いて施設の配置を表現するためには,施設配置ノードを複数のアークが終点 (始点) となる場合を考えなければならない.
ここで,$e$

そこでの多重カウントを防ぐための処理である.

$\min\sum_{k\in K}\sum_{p\in P^{k}}d_{p}^{k}f_{p}^{k}+\sum_{e\in A}F_{e}y_{e}+\sum_{\mathrm{e}\in A}L_{e}z_{e}$(10)subject to$\forall k\in K$$\sum_{p\in P^{k}}f_{p}^{k}=1$(11)$\sum_{k\in K,p\ni e}\sum_{p\in P^{k}}f_{p}^{k}\leq y_{e}$(12)$\sum_{e\in A}\sim e\vee=l$(13)$\forall e\in A$$y_{e}\leq z_{e}$$\forall e\in A$

(14)

93
$f_{p}^{k}.\geq 0$$\forall p\in P^{k},\forall k\in K$(15)$y_{e}\in\{0,1\}$$\forall e\in A$(16)$\sim e7\in\{0,1\}$$\forall e\in A$

(17)

4

解法の方針

4.1

アルゴリズムの基本的方針

厳密解法としては, 基本的に分枝限定法を利用することになるが,・多面体論の観点から Cutting Plane としてどのようなものがあり, それをどの程度利用するか・いずれかの制約式を Lagrange 緩和してそこでを得られた下界をどのように利用するかということが焦点になる. ここでは, 筆者が本稿を記述時点で認識している CuttingPlane となりうるアークフロー定式化における妥当不等式とパスフロー定式化における Lagrange 緩和を紹介する.

4.2

アークフロー定式化における妥当不等式

命題 1 以下に示す. 制約不等式はこの最適化問題の妥当不等式である.
$\mathrm{f}_{\mathrm{N}}^{\mathrm{k}}\leq \mathrm{y}_{\mathrm{i}\mathrm{i}}$$\forall(\mathrm{i},\mathrm{j})\in \mathrm{A},\forall \mathrm{k}\in \mathrm{K}$(18)

妥当不等式であるのは, 明らかである. さらに, この制約不等式 (18) は, forcing
constraint になっている. つまり, 一般にいわれる妥当不等式より強い性質を備えている. アークがなければ, そこにフローはありえないというのが, この制約不当式の意味である.
命題 2 さらに,次に示す制約不等式もこの最適化問題の妥当不等式である.
$\mathrm{f}_{\ddot{\mathrm{u}}}^{\mathrm{k}}+\mathrm{f}_{\mathrm{j}\mathrm{i}}^{\mathrm{k}}\leq \mathrm{y}_{\mathrm{N}}$$\forall(\mathrm{i},\mathrm{j})\in \mathrm{A},\forall \mathrm{k}\in \mathrm{K}$(19)

妥当不等式であるのは, 明らかである. この制約不等式 (19) も, forcing constraintになっている. この制約不等式の意味は, 「アーク上で (そのアークが存在すれば)同じ品種のフローが逆流することはない」 ということである.

以上が現時点で認識されている妥当不等式である. ただ, グラフが完全グラフで規模が大きいとこれらの制約式は $O(|K||N|^{2})$ 個であるので, 分枝カットとしてこれらの制約不等式を用いる際には, すべての分枝した問題においてこれを入れるべきかどうかは議論の余地がある.

94
4.3

Lagrange 緩和問題の性質

パスフロー定式化における (12) を Lagrange 緩和する問題を考える. Lagrange 乗数を \mu 。とすると以下のようになる.

$\min\sum_{k\in K}\sum_{p\in P^{k}}d_{p}^{k}f_{p}^{k}+\sum_{e\in A}F_{e}y_{e}+\sum_{e\in A}L_{e}z_{e}+\sum_{e\in A}\mu_{e}(\sum_{k\in Kp\in}\sum_{P^{k},p\ni e}f_{p}^{k}-y_{e})$(20)subject to(11),(13)\sim (17)となる.

目的関数である. (20) を整理しなおすと,$\sum_{e\in A}$と$\sum_{k\in K}$

で 2 分割できる. 制

約式まで含めて考察してみるとこの問題は 2 つの問題に分解可能である. 前者の問題を LFDI, 後者の問題を LFD2 とする.
が小さい数であれば z。を 0,1 に固定して, greedy な解法で分に関しては, 単純な計画法の問題であ解問題の解を得ることが可能である.
る. ただし,に関しては劣勾配法により最終的に調整しなければならない. それによって下界値が求められる.

LFDI に関しては,$l$$\mathrm{L}\mathrm{F}\mathrm{D}2$$\mu_{e}$ここでの難点は, 予め全て品種のパスのフロー費用を最短経路問題を解いて得ておかねばならないことである. 全てを求めておくのではなく, 必要な品種のパスのフロー費用だけを得る生成法を工夫する必要がある.

5

まとめと研究の指針
本稿では, 施設配置を考慮したネットワーク・デザイン問題ついてその定式化と厳密解を得る手法の要素である妥当不等式と Lagrange 緩和について考察をおこなった.

ここで取り上げた最適化問題については, 本稿では数値実験結果を示していな

ネットワーク・デザイン問題で過去に提供されている数値事件問題例は殆どロジスティクスに関するものである. また, 施設配置に関しては, 先に述べたように現在のコンピュータ・サイエンスの発達にともない施設配置費用が, 他の費用に比べてどの程度のオーダーであるか本稿記述時点では情報を得ることができなかった.
まずは, 問題意識にもとづく系統的なデータ生成方法を考えることが第一の研究目標である. また, 実験データについての指針が立った後, 分枝限定法を行うにあたっては, 妥当不等式や Lagrange 緩和による下界を利用することをすべての分枝ノードで行うのは非効率であると予測されるためその検討も必要である. 多面体論的考
察からは, 適切な制約式を生み出すさらに深めた研究が必要と考える. 一方, メタヒューリスティクスの解法については, ネットワーク・デザイン問題で提案されている解法を元にして考え実験する余地がある.
い.

95
本稿を作成にあたり,発表の機会いただいた研究代表者の数理統計研究所

隆先生, ネットワークデザイン問題に関して様々な情報をいただいた流通経済大学 片山直登先生, および発表の際に貴重なコメントいただいた東京商船大
土屋学久保幹雄先生に心より感謝いたします.

●本研究発表は早稲田大学特定課題研究助成費 2002A-063 の成果の一部である.

参考文献

and—-

Models of Network Des
ntegra\mbox{\boldmath $\tau$}eo lVlooelS[1]J.
J. Bhadury et al.. , Computational Complexity of lIntegrated
Isuue 1, pp.30Mathematics,
AppliedL\={o}cation Southwest Journal of Pure andFacility Location
43, 2000.
Guide to the Theory of. Garey and D.S.Johnson (1979) Computers and Intmctability:[2]$NP$ -Completeness, Freeman.
$\mathrm{i}\mathrm{g}\mathrm{n}$$\mathrm{a}1$$\mathrm{O}\mathrm{I}1\tau \mathrm{e}\mathrm{b}\mathrm{W}\mathrm{U}\mathrm{I}^{-}\mathrm{K}1J\mathrm{e}\mathrm{b}.\mathrm{l}\mathrm{g}11^{\cdot}\mathrm{d}11\mathrm{U}$$\mathrm{C}^{1}\mathrm{o}\mathrm{m}\mathrm{p}1\mathrm{e}\mathrm{x}\overline{1}\mathrm{t}\mathrm{y}\mathrm{o}1$$,$$\mathrm{V}\mathrm{o}\mathrm{l}.43,$$A$$\mathrm{M}.\mathrm{R}$編集) : ネットワークデザイン問題,[3]

片山直登, z 用数理計画ハンドブツク (久保. 田村, 松井
朝倉書店, 2002.

[4]. Daskin, Capacitated facility
S. Melkote and, pp.481-495, 2001.
Research,
Operational
Journal ofdesign problems, European$\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}/\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}$$\mathrm{M}.\mathrm{S}$$\mathrm{V}\mathrm{o}\mathrm{l}.129$[5]. Daskin, An integrated model of facility location and transportation
S. Melkote andPP.515-538, 2001.
$\pianspo\hslash
ation$ Research $Pa\hslash A,$
network design,$\mathrm{M}.\mathrm{S}$$\mathrm{V}\mathrm{o}\mathrm{l}.35,$[6]

C. Wynants, Network Synthesis Problems, Kluwer Academic, 2001.