非分割フローを考慮した容量制約をもつネットワーク設計問題

(1)

1

《論　文》

非分割フローを考慮した容量制約をもつネットワーク設計問題

片　山　直　登

1 　はじめに

ネットワーク設計問題は，ネットワーク上の施設・設備であるアークにかかる固定的な費用とものの移動にかかる変動的な費用を考慮して，施設・設備などに対応するアークやノードを適切に選択することによりネットワークを形成し，かつ異なる始点と終点をもつ複数の荷物，商品やデータなどの移動経路であるパスを決める問題である．この問題は，輸送，ロジスティクス，通信や生産システムなどに幅広い応用分野をもつネットワークの構造を設計する問題であり，一般的なネットワーク設計問題は NP- 困難な問題であることが知られている（Magnanti and Wong 1984）.

容量制約をもつネットワーク設計問題はアークまたはノードに容量をもつ問題であり，ネットワーク設計問題の中でも最適解や良い近似解を求めることが困難な問題である．容量制約をもつネットワーク設計問題に関しては，今日まで数多くの研究が行われている．ネットワーク設計問題とその関連問題に関するサーベイとして，Magnanti and Wong（1984），Wong（1984, 1985），Minoux（1989），Balakrishnan et al.（1997），

Gendron et al.（1997），Crainic（2003），Costa （2005），片山直登（2008）および Yaghini and Rahbar （2012）などがある．

通信ネットワーク上では，同一の始点と終点をもつパケットなどのフローは必ずしも単一の経路上で送信されるとは限らず，トラフィックの状態に応じて複数の経路上で分割されて送信されることが一般的である．一方，ロジスティクスやサプライチェーンのネットワーク上では，同一の発地と着地をもつ荷物が複数に分割され，別々の経路で輸送されることはなく，単一の経路上で輸送されるのが一般的である．このような分割されないフローを非分割フローとよび，この非分割フローを考慮した問題を非分割フローを考慮した容量制約をもつネットワーク設計問題（UCND：Unsplittable Capacitated

(2)

2

Network Design Problem）とよぶ．この問題では，アークのデザイン変数のみならず，

パスやアークフロー変数も0-1 離散変数となり，すべての変数が離散変数である困難な組合せ最適化問題となる．ネットワーク設計問題においてデザイン変数を固定した問題は，分割フローを許す問題では多品種フロー問題，すなわち線形計画問題となるため，

比較的容易に解くことができる．一方，非分割フローを考慮した問題では，デザイン変数を固定した問題でさえ 0-1 変数をもつ組合せ最適化問題となるため，最適に解くことが困難となる．

非分割フローを考慮した容量制約をもつネットワーク設計問題に対する研究は最近始まったばかりであり，それほど多くはない．従来の研究としては，Yaghiniand Kazemzadeh（2012）のシミュレーテッドアニーリング法を用いた研究，Hewitt et al.

（2012）の IP 探索法および分枝価格法とガイドつき探索法を用いた研究がある．

本研究では，非分割フローを考慮した容量制約をもつ設計問題に対して，容量スケーリング法と局所探索法およびパス再結合法を組合せた近似解法を提案する．

2 　問題の定式化

はじめに，UCNDの前提条件，使用する記号および UCNDの定義を示す．続いて，

アークフローによる定式化，およびパスフローによる定式化を示す．

2 ． 1 　前提条件，記号および問題の定義 UCNDの前提条件を示す．

• ノード集合が与えられている．

• 向きをもつアーク集合が与えられている．

• アークには，非負のデザイン費用が与えられている．

• 複数の品種からなる品種集合が与えられている．

• アークには，品種ごとの全需要に対する非負のフロー費用が与えられている．

• アークには，単位期間当たりの処理量の上限であるアーク容量が与えられている．

• 各品種ごとの需要が与えられている．

• 各品種の需要は，始点から終点までの 1 つのパス上を移動する．

UCNDの定式化で使用する記号の定義を示す．

• N：ノード集合

• A：アーク集合

• K：品種集合

• N⁺n：ノード n を終点とするアークの終点であるノード集合

• N⁻n：ノード n を始点とするアークの始点であるノード集合

(3)

3

• P^k：品種 k の取り得るパス集合

• c^kij：アーク（i, j）上における品種 k の全需要に対する非負のフロー費用

• fij：アーク（i, j）の非負のデザイン費用

• Cij：アーク（i, j）のアーク容量

• d^k：品種 k の需要

• δ^pij：パス p にアーク（i, j）が含まれるとき 1 ，そうでないとき 0 を表す定数

• O^k：品種 k の始点

• D^k：品種 k の終点

• x^kij：品種 k のフローがアーク（i, j）上に含まれるとき 1 ，そうでないとき 0 であるアークフロー変数；0–1 変数

• z^kp：品種 k のフローがパス p 上を移動するとき 1 ，そうでないとき 0 であるパスフロー変数；0–1 変数

• yij：アーク（i, j）を選択するとき 1 ，そうでないとき 0 であるデザイン変数；0–1変数次に，UCNDの定義を示す．

定義 2 ． 1 （UCND）デザイン費用 f ，フロー費用 c ，アーク容量 C をもつ向きをもつアーク集合 A が与えられ，ノード集合 N および品種の需要 d をもつ品種集合 K が与えられている．このとき，フロー費用とデザイン費用の合計を最小にするアーク集合 A′

（⊆ A），およびアーク容量を満足する非分割アークフロー x または非分割パスフロー z を求めよ．

2 ． 2 　アークフローによる定式化

UCND のアークフローによる定式化を UCNDA とする．UCNDA は，次のようになる．

• AɿΞ ʔ Ϋ ू ߹

• Kɿ඼ छ ू ߹

• N_n⁺ɿϊʔ υnΛऴ ఺ ͱ ͢ Δ Ξ ʔ Ϋ ͷ ऴ ఺ Ͱ ͋ Δ ϊ ʔ υ ू ߹

• N_n⁻ɿϊʔ υnΛ࢝ ఺ ͱ ͢ Δ Ξ ʔ Ϋ ͷ ࢝ ఺ Ͱ ͋ Δ ϊ ʔ υ ू ߹

• P^kɿ඼छkͷ औ Γ ಘ Δ ύ ε ू ߹

• c^k_ijɿΞʔ Ϋ(i, j)্ ʹ ͓ ͚ Δ ඼ छkͷશ ध ཁ ʹ ର ͢ Δ ඇ ෛ ͷ ϑ ϩ ʔ අ ༻

• fijɿΞʔ Ϋ(i, j)ͷ ඇ ෛ ͷ σ β Π ϯ අ ༻

• C_ijɿΞ ʔ Ϋ(i, j)ͷ Ξ ʔ Ϋ ༰ ྔ

• d^kɿ඼छkͷ ध ཁ

• δ_ij^pɿύ εpʹΞ ʔ Ϋ(i, j)͕ ؚ · Ε Δ ͱ ͖1ɼͦ ͏ Ͱ ͳ ͍ ͱ ͖0Λ ද ͢ ఆ ਺

• O^kɿ඼ छkͷ࢝ ఺

• D^kɿ඼ छkͷ ऴ ఺

• x^k_ijɿ඼ छkͷ ϑ ϩ ʔ ͕ Ξ ʔ Ϋ(i, j)্ ʹ ؚ · Ε Δ ͱ ͖1ɼͦ ͏ Ͱ ͳ ͍ ͱ ͖0Ͱ

͋Δ Ξ ʔ Ϋ ϑ ϩ ʔ ม ਺ʀ0–1ม ਺

• z^k_pɿ඼ छkͷ ϑ ϩ ʔ ͕ ύ εp্ Λ Ҡ ಈ ͢ Δ ͱ ͖1ɼͦ ͏ Ͱ ͳ ͍ ͱ ͖0Ͱ ͋ Δ ύ εϑ ϩ ʔ ม ਺ʀ0–1ม਺

• y_ijɿΞ ʔ Ϋ(i, j)Λ બ ୒ ͢ Δ ͱ ͖1ɼͦ ͏ Ͱ ͳ ͍ ͱ ͖0Ͱ ͋ Δ σ β Π ϯ ม ਺ʀ 0–1ม਺

࣍ ʹ ɼU CN Dͷ ఆ ٛ Λ ࣔ ͢ɽ

ఆٛ2.1 (U CN D) σ β Π ϯ අ ༻fɼϑ ϩ ʔ අ ༻cɼΞ ʔ Ϋ ༰ ྔCΛ ΋ ͭ ޲ ͖ Λ ΋

ͭ Ξ ʔ Ϋ ू ߹A͕ ༩ ͑ Β Ε ɼϊ ʔ υ ू ߹N͓ Α ͼ ඼ छ ͷ ध ཁdΛ ΋ ͭ ඼ छ ू ߹ K͕ ༩ ͑ Β Ε ͯ ͍ Δ ɽ͜ ͷ ͱ ͖ ɼϑ ϩ ʔ අ ༻ ͱ σ β Π ϯ අ ༻ ͷ ߹ ܭ Λ ࠷ খ ʹ ͢ Δ Ξʔ Ϋ ू ߹A^′(⊆A)ɼ͓Α ͼ Ξ ʔ Ϋ ༰ ྔ Λ ຬ ଍ ͢ Δ ඇ ෼ ׂ Ξ ʔ Ϋ ϑ ϩ ʔx·ͨ ͸ ඇ

෼ׂ ύ ε ϑ ϩ ʔzΛٻ Ί Α ɽ

2.2 ΞʔΫϑϩʔʹΑΔఆࣜԽ

U CN Dͷ Ξ ʔ Ϋ ϑ ϩ ʔ ʹ Α Δ ఆ ࣜ Խ ΛU CN DAͱ ͢ Δ ɽU CN DA͸ ɼ࣍ͷ Α ͏ ʹͳ Δ ɽ

(U CN DA)

min ∑

(i,j)∈A

∑

k∈K

c^k_ijx^k_ij+ ∑

(i,j)∈A

f_ijy_ij (1)

subject to 3

∑

i∈Nn⁺

x^k_in− ∑

j∈Nn⁻

x^k_nj=









−1 if n=O^k 1 if n=D^k 0 otherwise

∀n∈N, k∈K (2)

∑

k∈K

d^kx^k_ij≤Cijyij ∀(i, j)∈A (3)

x^k_ij≤y_ij ∀k∈K,(i, j)∈A (4)

x^k_ij∈ {0,1} ∀k∈K,(i, j)∈A (5)

y_ij∈ {0,1} ∀(i, j)∈A (6)

(1)ࣜ ͸ ໨ త ؔ ਺ Ͱ ͋ Γɼϑ ϩ ʔ අ ༻ ͱ σ β Π ϯ අ ༻ ͷ ૯ ࿨ Λ ࠷ খ Խ ͢ Δ ɽ(2)

ࣜ ͸ ϑ ϩ ʔ อ ଘ ࣜ Ͱ ͋ Γɼϊ ʔ υ ʹ ྲྀ ೖ ͢ Δ ϑ ϩ ʔ ͱ ྲྀ ग़ ͢ Δ ϑ ϩ ʔ ม ਺ ஋ ͷ ࠩ

͕ɼ඼छkͷ࢝ ఺ Ͱ ͋ Ε ͹−1ɼऴ఺ Ͱ ͋ Ε ͹1ɼͦͷ ଞ ͷ ϊ ʔ υ Ͱ ͋ Ε ͹0Ͱ͋ Δ

͜ ͱ Λ ද ͢ɽ͜ ͷ ࣜ ͸ ɼ֤ ඼ छ ʹ ͭ ͍ ͯ ɼඞ ͣ ࢝ ఺ ͔ Β ऴ ఺ · Ͱ ध ཁ ͕ Ҡ ಈ ͢ Δ

͜ͱ Λ อ ূ ͢ Δ ɽ(3)ࣜ ͸ ɼ༰ྔ ੍ ໿ ࣜ Ͱ ͋ Δ ɽΞʔ Ϋ(i, j)͕ બ ୒ ͞ Ε Δ ͱ ͖ ɼࠨ ล ͸ Ξ ʔ Ϋ ্ Λ Ҡ ಈ ͢ Δ ϑ ϩ ʔ ྔ ͷ ߹ ܭ Ͱ ͋ Γɼ͜ Ε ͕ ӈ ล ͷ Ξ ʔ Ϋ ༰ ྔ Ҏ Լ Ͱ

͋ Δ ͜ ͱ Λ ද ͢ɽ· ͨ ɼΞ ʔ Ϋ ͕ બ ୒ ͞ Ε ͳ ͍ ͱ ͖ ͸ ϑ ϩ ʔ ྔ ͷ ߹ ܭ ͕0Ͱ ͋ Δ

͜ ͱ Λ ද ͢ɽ(4)ࣜ ͸ ɼΞ ʔ Ϋ(i, j)ʹ ͓ ͚ Δ ඼ छkʹ ؔ ͢ Δ ڧ ੍ ੍ ໿ ࣜ Ͱ ͋ Δ ɽ͜

ͷ ࣜ ͸ ɼΞ ʔ Ϋ(i, j)͕ બ ୒ ͞ Ε Δ ͱ ͖ ʹ ͸ ඼ छkͷ Ξ ʔ Ϋ ϑ ϩ ʔ ม ਺ ஋ ͕ ࠷ େ Ͱ 1ͱ ͳ ΓɼΞ ʔ Ϋ(i, j)͕ બ ୒ ͞ Ε ͳ ͍ ͱ ͖ ʹ ͸0ͱ ͳ Δ ͜ ͱ Λ ද ͢ɽ(5)ࣜ ͸ Ξ ʔ Ϋϑ ϩ ʔ ม ਺ ͷ0–1৚ ݅ ɼ(6)ࣜ͸ σ β Π ϯ ม ਺ ͷ0–1৚ ݅ Ͱ ͋ Δ ɽ

U CN DA͸ ɼ|A||K|ݸ ͷ Ξ ʔ Ϋ ϑ ϩ ʔ ม ਺ ɼ|A|ݸ ͷ σ β Π ϯ ม ਺ ɼ͓ Α ͼ

|N||K|+|A|+|A||K|ຊ ͷ ੍ ໿ ࣜ Λ ΋ ͭ ໰ ୊ ͱ ͳ Δ ɽ

2.3 ύεϑϩʔʹΑΔఆࣜԽ

U CN Dͷ ύ ε ϑ ϩ ʔ ʹ Α Δ ఆ ࣜ ԽU CN DPΛ ࣔ ͢ɽ (U CN DP)

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ^p_ijz_p^k+ ∑

(i,j)∈A

f_ijy_ij (7)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (8)

4

(4)

4 subject to

∑

i∈Nn⁺

x^k_in− ∑

j∈Nn⁻

x^k_nj=









∀n∈N, k∈K (2)

∑

k∈K

d^kx^k_ij≤Cijyij ∀(i, j)∈A (3)

x^k_ij≤y_ij ∀k∈K,(i, j)∈A (4)

x^k_ij∈ {0,1} ∀k∈K,(i, j)∈A (5)

y_ij∈ {0,1} ∀(i, j)∈A (6)

|N||K|+|A|+|A||K|ຊ ͷ ੍ ໿ ࣜ Λ ΋ ͭ ໰ ୊ ͱ ͳ Δ ɽ

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ_ij^pz_p^k+ ∑

(i,j)∈A

f_ijy_ij (7)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (8)

4

⑴式は目的関数であり，フロー費用とデザイン費用の総和を最小化する．⑵式はフロー保存式であり，ノードに流入するフロー変数値と流出するフロー変数値の差が，品種 k の始点であれば−1，終点であれば 1 ，その他のノードであれば 0 であることを表す．この式は，各品種について，必ず始点から終点まで需要が移動することを保証する．

⑶式は，容量制約式である．アーク（i, j）が選択されるとき，左辺はアーク上を移動するフロー量の合計であり，これが右辺のアーク容量以下であることを表す．また，アークが選択されないときはフロー量の合計が 0 であることを表す．⑷式は，アーク（i, j）

における品種 k に関する強制制約式である．この式は，アーク（i, j）が選択されるときには品種 k のアークフロー変数値が最大で 1 となり，アーク（i, j）が選択されないときには 0 となることを表す．⑸式はアークフロー変数の 0–1 条件，⑹式はデザイン変数の

0–1 条件である．

UCNDAは，︱A︱︱K︱個のアークフロー変数，︱A︱個のデザイン変数，および

︱N︱︱K︱+︱A︱+︱A︱︱K︱本の制約式をもつ問題となる．

2 ． 3 　パスフローによる定式化

UCND のパスフローによる定式化 UCNDP を示す．

subject to

∑

i∈Nn⁺

x^k_in− ∑

j∈Nn⁻

x^k_nj=









∀n∈N, k∈K (2)

∑

k∈K

d^kx^k_ij≤C_ijy_ij ∀(i, j)∈A (3)

x^k_ij≤yij ∀k∈K,(i, j)∈A (4)

x^k_ij∈ {0,1} ∀k∈K,(i, j)∈A (5)

yij∈ {0,1} ∀(i, j)∈A (6)

|N||K|+|A|+|A||K|ຊ ͷ ੍ ໿ ࣜ Λ ΋ ͭ ໰ ୊ ͱ ͳ Δ ɽ

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ_ij^pz_p^k+ ∑

(i,j)∈A

fijyij (7)

subject to

∑

p∈P^k

z_p^k= 1 ∀k∈K (8)

∑ 4

k∈K

∑

p∈P^k

δ_ij^pd^kz^k_p≤C_ijy_ij ∀(i, j)∈A (9)

∑

p∈P^k

δ^p_ijz_p^k≤yij ∀k∈K,(i, j)∈A (10)

z_p^k∈ {0,1} ∀p∈P^k, k∈K (11)

yij∈ {0,1} ∀(i, j)∈A (12)

(7)ࣜ ͸ ໨ త ؔ ਺ Ͱ ͋ Γɼϑ ϩ ʔ අ ༻ ͱ σ β Π ϯ අ ༻ ͷ ૯ ࿨ Λ ࠷ খ Խ ͢ Δ ɽ͜ ͜ Ͱɼ∑

p∈P^kδ^p_ijz^k_p͸x^k_ijʹ Ұ க ͢ Δ ɽ(8)ࣜ͸ ɼ඼छkͷύ ε ϑ ϩ ʔ ม ਺ ஋ ͷ ߹ ܭ ͕1ɼ

͢ͳ Θ ͪ ୯ Ұ ͷ ύ ε ্ ͷ Έ ʹ ϑ ϩ ʔ ͕ ྲྀ Ε Δ ͜ ͱ Λ ද ͢ɽ(9)ࣜ ͸ ɼΞʔ Ϋ(i, j)͕ બ ୒ ͞ Ε Δ ͱ ͖ ͸ Ξ ʔ Ϋ ্ Λ Ҡ ಈ ͢ Δ ϑ ϩ ʔ ม ਺ ஋ ͷ ߹ ܭ ͕ Ξ ʔ Ϋ ༰ ྔ Ҏ Լ Ͱ ͋ ΓɼΞ ʔ Ϋ ͕ બ ୒ ͞ Ε ͳ ͍ ͱ ͖ ͸0Ͱ ͋ Δ ͜ ͱ Λ ද ͢ ༰ ྔ ੍ ໿ ࣜ Ͱ ͋ Δ ɽ(10)ࣜ

͸ ɼΞ ʔ Ϋ(i, j)ʹ ͓ ͚ Δ ඼ छkʹ ؔ ͢ Δ ڧ ੍ ੍ ໿ ࣜ Ͱ ͋ Δ ɽ(11)ࣜ ͸ ύ ε ϑ ϩ ʔ ม਺ ͷ0–1৚ ݅ ɼ(12)ࣜ ͸ σ β Π ϯ ม ਺ ͷ0–1৚ ݅ Ͱ ͋ Δ ɽ

U CN DP͸ ɼ∑

k∈K|P^k|ݸ Ͱ ͋ Δ ࢦ ਺ ݸ ͷ ύ ε ϑ ϩ ʔ ม ਺ ɼ|A|ݸ ͷ σ β Π ϯ ม

਺ͱ|K|+|A|+|A||K|ຊͷ ੍ ໿ ࣜ Λ ΋ ͭ ໰ ୊ ͱ ͳ Δ ɽ0-1ม ਺ ͕ ࢦ ਺ ݸ ͱ ๲ େ ͳ ΋ ͷͱ ͳ Δ ͷ Ͱ ɼখ ن ໛ ͳ ໰ ୊ Ͱ ͋ͬͯ ΋ ͜ ͷ ఆ ࣜ Խ Λ ௚ ઀ ղ ͘ ͜ ͱ ͸ ࠔ ೉ Ͱ ͋ Δ ɽ

࣮ ࡍ ʹ ͸ ɼஞ ࣍ ɼඞ ཁ ͳ ύ ε ϑ ϩ ʔ ม ਺ Λ ੜ ੒ ͠ ͯ ໰ ୊ Λ ղ ͘ ྻ ੜ ੒ ๏ ͕ ༻ ͍ Β Ε Δ ɽ͜ ͷ ྻ ੜ ੒ ๏ Λ ͏ · ͘ ద ༻ ͢ Ε ͹ ɼΞ ʔ Ϋ ϑ ϩ ʔ ʹ Α Δ ఆ ࣜ Խ ͷ ৔ ߹ Α Γ

΋ɼཅ త ʹ ࢖ ༻ ͢ Δ ม ਺ ͷ ਺ Λ ཈ ͑ Δ ͜ ͱ ͕ Ͱ ͖ Δ ɽ

Ξ ʔ Ϋ ϑ ϩ ʔ ม ਺ ͓ Α ͼ ύ ε ϑ ϩ ʔ ม ਺ ͕0-1ม ਺ Ͱ ͋ Δ ͜ ͱ Ҏ ֎ ɼج ຊ త ʹ

͸ ༰ ྔ ੍ ໿ Λ ΋ ͭ ωοτ ϫ ʔ Ϋ ઃ ܭ ໰ ୊ ͱ ಉ Ұ Ͱ ͋ Δ ɽͦ ͜ Ͱ ɼ༰ ྔ ੍ ໿ Λ ΋ ͭ ωοτ ϫ ʔ Ϋ ઃ ܭ ໰ ୊ ʹ ର ͢ Δ ۙ ࣅ ղ ๏ Ͱ ͋ Δ ༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͱ ύ ε ࠶ ݁ ߹

๏Λ ద ༻ ͠ ɼ͞ Β ʹ ہ ॴ ෼ ࢬ ๏ Λ ซ ༻ ͢ Δ ɽ

3 ^{༰ྔεέʔϦϯά๏}

3.1 ઢܗ؇࿨໰୊ͱ༰ྔεέʔϦϯά

༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͸ ɼઢ ܗ ؇ ࿨ ໰ ୊ ͷ ղ Λ ΋ ͱ ʹ ɼΞ ʔ Ϋ ༰ ྔ Λ ม ߋ ͠ ͯ ܁ Γ ฦ ͠ ઢ ܗ ؇ ࿨ ໰ ୊ Λ ղ ͖ ɼ0–1ม ਺ ղ Λ ಋ ͘ ۙ ࣅ ղ ๏ Ͱ ͋ Δ ɽྻ ੜ ੒ ๏ ͸ ݶ ఆ ओ ໰ ୊ Λ ղ ͖ ɼద ࣌ ɼඃ ໿ අ ༻ ͕ ෛ ͱ ͳ Δ ม ਺ Λ ੜ ੒ ͢ Δ ํ ๏ Ͱ ͋ Δ ɽ· ͨ ɼߦ ੜ ੒ ๏ ͸ ɼྻ ੜ ੒ ๏ ʹ Α Γ ੜ ੒ ͞ Ε ͨ ม ਺ ʹ ର ͢ Δ ༗ ޮ ͳ ੍ ໿ ࣜ Λ ஞ ࣍ ௥ Ճ ͢ Δ

ํ ๏ Ͱ ͋ Δ ɽ͜ Ε Β ͷ ํ ๏ ʹ ͭ ͍ ͯ ͸ ɼ༰ ྔ ੍ ໿ Λ ΋ ͭ ωοτ ϫ ʔ Ϋ ઃ ܭ ໰ ୊ ʹ ର ͢ Δ ย ࢁ ௚ ొ(2010)ʹ ৄ ࡉ ͕ ه ࡌ ͞ Ε ͯ ͓ ΓɼΞ ʔ Ϋ ϑ ϩ ʔ ม ਺ ͓ Α ͼ ύ ε ϑ ϩʔ ม ਺ ͕0-1ม਺ Ͱ ͋ Δ ͜ ͱ Λ আ ͚ ͸ ಉ Ұ ͷ ղ ๏ Ͱ ͋ Δ ɽ

U CN DPʹ ͓ ͍ ͯ ɼσ β Π ϯ ม ਺ ͓ Α ͼ ύ ε ϑ ϩ ʔ ม ਺ ͷ0-1৚ ݅ Λ0͔ Β1ͷ

࿈ଓ ਺ ʹ ؇ ࿨ ͠ ͨ ઢ ܗ ؇ ࿨ ໰ ୊LRΛ ߟ ͑ Δ ɽ

(5)

5

⑺式は目的関数であり，フロー費用とデザイン費用の総和を最小化する．ここで，

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz^k_p≤C_ijy_ij ∀(i, j)∈A (9)

∑

p∈P^k

δ_ij^pz_p^k≤y_ij ∀k∈K,(i, j)∈A (10)

z^k_p∈ {0,1} ∀p∈P^k, k∈K (11)

yij∈ {0,1} ∀(i, j)∈A (12)

p∈P^kδ_ij^pz_p^k͸x^k_ijʹ Ұ க ͢ Δ ɽ(8)ࣜ͸ ɼ඼छkͷύ ε ϑ ϩ ʔ ม ਺ ஋ ͷ ߹ ܭ ͕1ɼ

U CN DP͸ ɼ∑

΋ɼཅ త ʹ ࢖ ༻ ͢ Δ ม ਺ ͷ ਺ Λ ཈ ͑ Δ ͜ ͱ ͕ Ͱ ͖ Δ ɽ

๏Λ ద ༻ ͠ ɼ͞ Β ʹ ہ ॴ ෼ ࢬ ๏ Λ ซ ༻ ͢ Δ ɽ

3 ^{༰ྔεέʔϦϯά๏}

࿈ଓ ਺ ʹ ؇ ࿨ ͠ ͨ ઢ ܗ ؇ ࿨ ໰ ୊LRΛ ߟ ͑ Δ ɽ 5 は

∑

k∈K

∑

p∈P^k

∑

p∈P^k

δ_ij^pz_p^k≤yij ∀k∈K,(i, j)∈A (10)

z^k_p∈ {0,1} ∀p∈P^k, k∈K (11)

yij∈ {0,1} ∀(i, j)∈A (12)

p∈P^kδ_ij^pz_p^k͸x^k_ijʹ Ұ க ͢ Δ ɽ(8)ࣜ͸ ɼ඼छkͷύ ε ϑ ϩ ʔ ม ਺ ஋ ͷ ߹ ܭ ͕1ɼ

U CN DP͸ ɼ∑

΋ɼཅ త ʹ ࢖ ༻ ͢ Δ ม ਺ ͷ ਺ Λ ཈ ͑ Δ ͜ ͱ ͕ Ͱ ͖ Δ ɽ

๏Λ ద ༻ ͠ ɼ͞ Β ʹ ہ ॴ ෼ ࢬ ๏ Λ ซ ༻ ͢ Δ ɽ

3 ^{༰ྔεέʔϦϯά๏}

࿈ଓ ਺ ʹ ؇ ࿨ ͠ ͨ ઢ ܗ ؇ ࿨ ໰ ୊LRΛ ߟ ͑ Δ ɽ 5

に一致する．⑻式は，品種 k のパスフロー変数値の合計が 1 ，すなわち単一のパス上のみにフローが流れることを表す．⑼式は，アーク（i, j）が選択されるときはアーク上を移動するフロー量の合計がアーク容量以下であり，アークが選択されないときは 0 であることを表す容量制約式である．⑽式は，アーク（i, j）における品種 k に関する強制制約式である．⑾式はパスフロー変数の 0–1 条件，⑿式はデザイン変数の 0–1 条件である．

UCNDP は，

∑

k∈K

∑

p∈P^k

∑

p∈P^k

z_p^k∈ {0,1} ∀p∈P^k, k∈K (11)

yij∈ {0,1} ∀(i, j)∈A (12)

p∈P^kδ^p_ijz_p^k͸x^k_ijʹ Ұ க ͢ Δ ɽ(8)ࣜ͸ ɼ඼छkͷύ ε ϑ ϩ ʔ ม ਺ ஋ ͷ ߹ ܭ ͕1ɼ

U CN DP͸ ɼ∑

΋ɼཅ త ʹ ࢖ ༻ ͢ Δ ม ਺ ͷ ਺ Λ ཈ ͑ Δ ͜ ͱ ͕ Ͱ ͖ Δ ɽ

๏Λ ద ༻ ͠ ɼ͞ Β ʹ ہ ॴ ෼ ࢬ ๏ Λ ซ ༻ ͢ Δ ɽ

3 ^{༰ྔεέʔϦϯά๏}

࿈ଓ ਺ ʹ ؇ ࿨ ͠ ͨ ઢ ܗ ؇ ࿨ ໰ ୊LRΛ ߟ ͑ Δ ɽ 5

個である指数個のパスフロー変数，︱A︱個のデザイン変数と

︱K︱+︱A︱+︱A︱︱K︱本の制約式をもつ問題となる．0–1 変数が指数個と膨大なものとなるので，小規模な問題であってもこの定式化を直接解くことは困難である．実際には，

逐次，必要なパスフロー変数を生成して問題を解く列生成法が用いられる．この列生成法をうまく適用すれば，アークフローによる定式化の場合よりも，陽的に使用する変数の数を抑えることができる．

アークフロー変数およびパスフロー変数が 0-1 変数であること以外，基本的には容量制約をもつネットワーク設計問題と同一である．そこで，容量制約をもつネットワーク設計問題に対する近似解法である容量スケーリング法と局所分枝法を適用し，さらにパス再結合法を併用する．

3 　容量スケーリング法

3 ． 1 　線形緩和問題と容量スケーリング

容量スケーリング法は，線形緩和問題の解をもとに，アーク容量を変更して繰り返し線形緩和問題を解き，0–1 変数解を導く近似解法である．列生成法は限定主問題を解き，

適時，被約費用が負となる変数を生成する方法である．また，行生成法は，列生成法により生成された変数に対する有効な制約式を逐次追加する方法である．これらの方法については，容量制約をもつネットワーク設計問題に対する片山直登（2010）の研究に詳細が記載されており，アークフロー変数およびパスフロー変数が 0-1 変数であることを除けば同一の解法である．

UCNDP において，デザイン変数およびパスフロー変数の 0-1 条件を 0 から 1 の連続数に緩和した線形緩和問題 LR を考える．

(LR)

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ^p_ijz_p^k+ ∑

(i,j)∈A

f_ijy_ij (13)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (14)

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz_p^k≤Cijyij ∀(i, j)∈A (15)

∑

p∈P^k

0≤z^k_p≤1 ∀p∈P^k, k∈K (17)

0≤y_ij≤1 ∀(i, j)∈A (18)

LRʹ ͓ ͍ ͯ ɼ܁ Γ ฦ ͠ ճ ਺lͷ ͱ ͖ ͷ Ξ ʔ Ϋ(i, j)্ ͷ Ξ ʔ Ϋ ༰ ྔ ΛC_ij^l ͱ ͠ ͨ

໰ ୊ ΛLR(C^l)ͱ ͠ ɼ܁ Γ ฦ ͠ ຖ ʹ Ξ ʔ Ϋ ༰ ྔ Λ ม Խ ͞ ͤ Δ ɽLRͷlճ ໨ ͷ ܁ Γ ฦ͠ ʹ ͓ ͚ ΔLR(C^l)͸ ɼ࣍ ͷ Α ͏ ʹ ͳ Δ ɽ

(L(C^l))

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ^p_ijz_p^k+ ∑

(i,j)∈A

f_ijy_ij (19)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (20)

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz_p^k≤C_ij^ly_ij ∀(i, j)∈A (21)

∑

p∈P^k

0≤z^k_p≤1 ∀p∈P^k, k∈K (23)

0≤y_ij≤C_ij

C_ij^l ∀(i, j)∈A (24)

(6)

6 (LR)

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ^p_ijz^k_p+ ∑

(i,j)∈A

f_ijy_ij (13)

subject to

∑

p∈P^k

z_p^k= 1 ∀k∈K (14)

∑

k∈K

∑

p∈P^k

∑

p∈P^k

0≤z^k_p≤1 ∀p∈P^k, k∈K (17)

0≤yij≤1 ∀(i, j)∈A (18) LRʹ ͓ ͍ ͯ ɼ܁ Γ ฦ ͠ ճ ਺lͷ ͱ ͖ ͷ Ξ ʔ Ϋ(i, j)্ ͷ Ξ ʔ Ϋ ༰ ྔ ΛC_ij^l ͱ ͠ ͨ

(L(C^l))

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ^p_ijz^k_p+ ∑

(i,j)∈A

f_ijy_ij (19)

subject to

∑

p∈P^k

z_p^k= 1 ∀k∈K (20)

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz^k_p≤C_ij^ly_ij ∀(i, j)∈A (21)

∑

p∈P^k

0≤z^k_p≤1 ∀p∈P^k, k∈K (23)

0≤yij≤Cij

C_ij^l ∀(i, j)∈A (24)

6

LR において，繰り返し回数 l のときのアーク（i, j）上のアーク容量を Cij^lとした問題を LR（C^l）とし，繰り返し毎にアーク容量を変化させる．LR の l 回目の繰り返しにおける LR（C^l）は，次のようになる．

(LR)

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ_ij^pz_p^k+ ∑

(i,j)∈A

f_ijy_ij (13)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (14)

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz_p^k≤Cijyij ∀(i, j)∈A (15)

∑

p∈P^k

δ_ij^pz^k_p≤yij ∀k∈K,(i, j)∈A (16)

0≤z^k_p≤1 ∀p∈P^k, k∈K (17)

0≤y_ij≤1 ∀(i, j)∈A (18)

LRʹ ͓ ͍ ͯ ɼ܁ Γ ฦ ͠ ճ ਺lͷ ͱ ͖ ͷ Ξ ʔ Ϋ(i, j)্ ͷ Ξ ʔ Ϋ ༰ ྔ ΛC_ij^l ͱ ͠ ͨ

(L(C^l))

min ∑

(i,j)∈A

∑

k∈K

c^k_ij ∑

p∈P^k

δ_ij^pz_p^k+ ∑

(i,j)∈A

fijyij (19)

subject to

∑

p∈P^k

z^k_p= 1 ∀k∈K (20)

∑

k∈K

∑

p∈P^k

δ^p_ijd^kz_p^k≤C_ij^ly_ij ∀(i, j)∈A (21)

∑

p∈P^k

δ_ij^pz^k_p≤y_ij ∀k∈K,(i, j)∈A (22)

0≤z^k_p≤1 ∀p∈P^k, k∈K (23)

0≤y_ij≤C_ij

C_ij^l ∀(i, j)∈A (24)

ここでは，デザイン変数の上限値である 1 を変更し，6

͜ ͜ Ͱ ͸ ɼσ β Π ϯ ม ਺ ͷ ্ ݶ ஋ Ͱ ͋ Δ1Λ ม ߋ ͠ ɼy^s_ij≤C_ij/C_ij^l ʹ ม ߋ ͠ ͯ

͍Δ ɽ

ύ ϥ ϝ ʔ λλ(0< λ <1)ɼLR(C^l−1)ʹ ͓ ͚ Δ Ξ ʔ Ϋ(i, j)্ ͷ ૯ ϑ ϩ ʔ ྔX˜ij͓ Α ͼ Ξ ʔ Ϋ(i, j)ͷ Ξ ʔ Ϋ ༰ ྔC_ij^l−1Λ ༻ ͍ ͯ ɼLR(C^l)ʹ ͓ ͚ Δ Ξ ʔ Ϋ ༰ ྔ Λ ࣍ ͷ Α͏ ʹ ߋ ৽ ͢ Δ ɽ

C_ij^l :=λX˜ij+ (1−λ)C_ij^l−1 ∀(i, j)∈A (25)

͜ ͜ Ͱ ɼLR(C^l−1)ʹ ͓ ͚ Δ ࣮ ߦ Մ ೳ ͳ ύ ε ϑ ϩ ʔ ม ਺ Λz˜ͱ ͢ Δ ͱ ɼX˜_ij͸ ࣍ ࣜ ͱͳ Δ ɽ

X˜ij= ∑

k∈K

∑

p∈P¯^k

δ_ij^pd^kz˜_p^k ∀(i, j)∈A (26)

Ұ ํ ɼ(16)ࣜ ͕ ͋ Δ ͨ Ί ʹ ɼ࠷ ద ղ ʹ ͓ ͍ ͯ ඞ ͣ ͠ ΋y˜_ij= ˜X_ij/C_ij^l ͕ ੒ Γ ཱ ͨ

ͣɼC_ij^ly˜ij≥X˜ijͱ ͳ ΓɼC_ij^ly˜ij͸X˜ijͷ ্ ݶ ஋ ͱ ͳ Δ ɽͦ͜ Ͱ ɼLR(C^l−1)ʹ͓ ͚ Δ Ξ ʔ Ϋ(i, j)্ ͷ σ β Π ϯ ม ਺y˜ijΛ ༻ ͍ ͯ ɼLR(C^l)ʹ ͓ ͚ Δ Ξ ʔ Ϋ ༰ ྔ Λ ࣍ ͷ Α

͏ʹ ߋ ৽ ͢ Δ ͜ ͱ ΋ Ͱ ͖ Δ ɽ

C_ij^l :=λC_ij^l−1y˜_ij+ (1−λ)C_ij^l−1={1−λ(1−y˜_ij)}C_ij^l−1 ∀(i, j)∈A (27)

༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ Ξ ϧ ΰ Ϧ ζ Ϝ ΛAlgorithm1ʹ ࣔ ͢ɽ͜ ͜ Ͱ ɼIT Emin͸

༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ ࠷ খ ܁ Γ ฦ ͠ ճ ਺ ɼIT Emax͸ ༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ ࠷ େ

܁ Γ ฦ ͠ ճ ਺ Ͱ ͋ ΓɼUB͸ ্ ք ஋ Ͱ ͋ Δ ɽ͜ ͜ Ͱ ɼColumn Generation and Row Generation͸ ྻ ੜ ੒ ͱ ߦ ੜ ੒ ๏ ɼRestricted Branch and Bound͸ ݶ ఆ ෼ ࢬ ݶ ఆ ๏ ɼ Path Relinking͸ ύ ε ࠶ ݁ ߹ ๏ Ͱ ͋ ΓɼLocal Branching͸ہ ॴ ෼ ࢬ ๏ Ͱ ͋ Δ ɽ

3.2 ^{ݶఆओ໰୊}

LR(C^l)ʹ ͸ ඇ ৗ ʹ ଟ ͘ ͷ ύ ε ϑ ϩ ʔ ม ਺ ͕ ؚ · Ε Δ ͨ Ί ɼ௚ ઀ ղ ͘ ͜ ͱ ͸ ࠔ ೉ Ͱ ͋ Δ ɽͦ ͜ Ͱ ɼ͋ Β ͔ ͡ Ί ͢ ΂ ͯ ͷ ύ ε ϑ ϩ ʔ ม ਺ Λ ؚ Ή ໰ ୊ Λ ର ৅ ͱ ͢ Δ ͷ Ͱ͸ ͳ ͘ɼஞ࣍ ɼඞཁ ͳ ύ ε ϑ ϩ ʔ ม ਺ Λ ੜ ੒ ͠ ɼ໰୊ ʹ ௥ Ճ ͠ ͯ ͍ ͘ɽੜ੒ ͢ Δ ύ ε ϑ ϩ ʔ ม ਺ ͕ ୯ ମ ๏ ͷ ྻ ʹ ૬ ౰ ͢ Δ ͜ ͱ ͔ Β ɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ྻ ੜ ੒ ๏ ͱ ΑͿ ɽ

Ұ ํ ɼLR(C^l)ʹ ͸ ɼඇ ৗ ʹ ଟ ͘ ͷ ڧ ੍ ੍ ໿ ࣜ Ͱ ͋ Δ(22)ࣜ ͕ ؚ · Ε ͯ ͍ Δ ɽ͠

͔ ͠ ɼྻ ੜ ੒ ʹ Α Γ ੜ ੒ ͞ Ε ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ؚ · Ε Δ ڧ ੍ ੍ ໿ ࣜ ͸ ͦ Ε ΄ Ͳ ଟ ͘ ͳ ͘ɼੜ ੒ ͞ Ε ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ࠨ ล ʹ ؚ · Ε ͯ ͍ ͳ ͍ ڧ ੍ ੍ ໿ ࣜ ͸ ෆ ཁ ͳ ΋ ͷ ͱ ͳ Δ ɽͦ ͜ Ͱ ɼੜ ੒ ͠ ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ॳ Ί ͯ ࠨ ล ʹ ؚ · Ε Δ ڧ ੍ ੍

໿ ࣜ Λ ஞ ࣍ ੜ ੒ ͠ ɼ໰ ୊ ʹ ௥ Ճ ͢ Δ ɽੜ ੒ ͢ Δ ੍ ໿ ࣜ ͕ ୯ ମ ๏ ͷ ߦ ʹ ૬ ౰ ͢ Δ ͜ ͱ ͔ Β ɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ߦ ੜ ੒ ๏ ͱ Α Ϳ ɽͳ ͓ ɼద ࣌ ɼઢ ܗ ؇ ࿨ ղ Λ আ ֎ ͢ Δ Α ͏ ͳ ༗ ޮ ͳ ڧ ੍ ੍ ໿ ࣜ ͷ Έ Λ Ճ ͑ Δ ͜ ͱ ΋ Մ ೳ Ͱ ͋ Γɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ੾ আ ฏ໘ ๏ Λ Α Ϳ ɽ

に変更している．

パラメータλ（0 < λ < 1），LR（C^{l −1}）におけるアーク（i, j）上の総フロー量

͜ ͜ Ͱ ͸ ɼσ β Π ϯ ม ਺ ͷ ্ ݶ ஋ Ͱ ͋ Δ1Λ ม ߋ ͠ ɼy^s_ij ≤Cij/C_ij^l ʹ ม ߋ ͠ ͯ

͍Δ ɽ

ύ ϥ ϝ ʔ λλ(0< λ <1)ɼLR(C^l−1)ʹ ͓ ͚ Δ Ξ ʔ Ϋ(i, j)্ ͷ ૯ ϑ ϩ ʔ ྔX˜_ij͓ Α ͼ Ξ ʔ Ϋ(i, j)ͷ Ξ ʔ Ϋ ༰ ྔC^l−1_ij Λ ༻ ͍ ͯ ɼLR(C^l)ʹ ͓ ͚ Δ Ξ ʔ Ϋ ༰ ྔ Λ ࣍ ͷ Α͏ ʹ ߋ ৽ ͢ Δ ɽ

C_ij^l :=λX˜ij+ (1−λ)C_ij^l−1 ∀(i, j)∈A (25)

͜ ͜ Ͱ ɼLR(C^l−1)ʹ ͓ ͚ Δ ࣮ ߦ Մ ೳ ͳ ύ ε ϑ ϩ ʔ ม ਺ Λ˜zͱ ͢ Δ ͱ ɼX˜_ij͸ ࣍ ࣜ ͱͳ Δ ɽ

X˜ij=∑

k∈K

∑

p∈P¯^k

δ^p_ijd^kz˜_p^k ∀(i, j)∈A (26)

Ұ ํ ɼ(16)ࣜ ͕ ͋ Δ ͨ Ί ʹ ɼ࠷ ద ղ ʹ ͓ ͍ ͯ ඞ ͣ ͠ ΋y˜_ij= ˜X_ij/C_ij^l ͕ ੒ Γ ཱ ͨ

ͣɼC_ij^ly˜ij≥X˜ijͱ ͳ ΓɼC_ij^ly˜ij͸X˜ijͷ ্ ݶ ஋ ͱ ͳ Δ ɽͦ͜ Ͱ ɼLR(C^l−1)ʹ͓ ͚ Δ Ξ ʔ Ϋ(i, j)্ ͷ σ β Π ϯ ม ਺y˜ijΛ ༻ ͍ ͯ ɼLR(C^l)ʹ ͓ ͚ Δ Ξ ʔ Ϋ ༰ ྔ Λ ࣍ ͷ Α

͏ʹ ߋ ৽ ͢ Δ ͜ ͱ ΋ Ͱ ͖ Δ ɽ

C_ij^l :=λC_ij^l−1y˜_ij+ (1−λ)C_ij^l−1={1−λ(1−y˜_ij)}C_ij^l−1 ∀(i, j)∈A (27)

༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ Ξ ϧ ΰ Ϧ ζ Ϝ ΛAlgorithm1ʹ ࣔ ͢ɽ͜ ͜ Ͱ ɼIT Emin͸

༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ ࠷ খ ܁ Γ ฦ ͠ ճ ਺ ɼIT E_max͸ ༰ ྔ ε έ ʔ Ϧ ϯ ά ๏ ͷ ࠷ େ

܁ Γ ฦ ͠ ճ ਺ Ͱ ͋ ΓɼUB͸ ্ ք ஋ Ͱ ͋ Δ ɽ͜ ͜ Ͱ ɼColumn Generation and Row Generation͸ ྻ ੜ ੒ ͱ ߦ ੜ ੒ ๏ ɼRestricted Branch and Bound͸ ݶ ఆ ෼ ࢬ ݶ ఆ ๏ ɼ Path Relinking͸ ύ ε ࠶ ݁ ߹ ๏ Ͱ ͋ ΓɼLocal Branching͸ہ ॴ ෼ ࢬ ๏ Ͱ ͋ Δ ɽ

3.2 ݶఆओ໰୊

LR(C^l)ʹ ͸ ඇ ৗ ʹ ଟ ͘ ͷ ύ ε ϑ ϩ ʔ ม ਺ ͕ ؚ · Ε Δ ͨ Ί ɼ௚ ઀ ղ ͘ ͜ ͱ ͸ ࠔ ೉ Ͱ ͋ Δ ɽͦ ͜ Ͱ ɼ͋ Β ͔ ͡ Ί ͢ ΂ ͯ ͷ ύ ε ϑ ϩ ʔ ม ਺ Λ ؚ Ή ໰ ୊ Λ ର ৅ ͱ ͢ Δ ͷ Ͱ͸ ͳ ͘ɼஞ࣍ ɼඞཁ ͳ ύ ε ϑ ϩ ʔ ม ਺ Λ ੜ ੒ ͠ ɼ໰୊ ʹ ௥ Ճ ͠ ͯ ͍ ͘ɽੜ੒ ͢ Δ ύ ε ϑ ϩ ʔ ม ਺ ͕ ୯ ମ ๏ ͷ ྻ ʹ ૬ ౰ ͢ Δ ͜ ͱ ͔ Β ɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ྻ ੜ ੒ ๏ ͱ ΑͿ ɽ

Ұ ํ ɼLR(C^l)ʹ ͸ ɼඇ ৗ ʹ ଟ ͘ ͷ ڧ ੍ ੍ ໿ ࣜ Ͱ ͋ Δ(22)ࣜ ͕ ؚ · Ε ͯ ͍ Δ ɽ͠

͔ ͠ ɼྻ ੜ ੒ ʹ Α Γ ੜ ੒ ͞ Ε ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ؚ · Ε Δ ڧ ੍ ੍ ໿ ࣜ ͸ ͦ Ε ΄ Ͳ ଟ ͘ ͳ ͘ɼੜ ੒ ͞ Ε ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ࠨ ล ʹ ؚ · Ε ͯ ͍ ͳ ͍ ڧ ੍ ੍ ໿ ࣜ ͸ ෆ ཁ ͳ ΋ ͷ ͱ ͳ Δ ɽͦ ͜ Ͱ ɼੜ ੒ ͠ ͨ ύ ε ϑ ϩ ʔ ม ਺ ͕ ॳ Ί ͯ ࠨ ล ʹ ؚ · Ε Δ ڧ ੍ ੍

໿ ࣜ Λ ஞ ࣍ ੜ ੒ ͠ ɼ໰ ୊ ʹ ௥ Ճ ͢ Δ ɽੜ ੒ ͢ Δ ੍ ໿ ࣜ ͕ ୯ ମ ๏ ͷ ߦ ʹ ૬ ౰ ͢ Δ ͜ ͱ ͔ Β ɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ߦ ੜ ੒ ๏ ͱ Α Ϳ ɽͳ ͓ ɼద ࣌ ɼઢ ܗ ؇ ࿨ ղ Λ আ ֎ ͢ Δ Α ͏ ͳ ༗ ޮ ͳ ڧ ੍ ੍ ໿ ࣜ ͷ Έ Λ Ճ ͑ Δ ͜ ͱ ΋ Մ ೳ Ͱ ͋ Γɼ͜ ͷ Α ͏ ͳ ํ ๏ Λ ੾ আ ฏ໘ ๏ Λ Α Ϳ ɽ

およびアーク（i, j）のアーク容量 Cij^l−1を用いて，LR（C^l）におけるアーク容量を次のように更新する．

非分割フローを考慮した容量制約をもつネットワーク設計問題

非分割フローを考慮した容量制約をもつネットワーク設計問題

片 山 直 登

1 はじめに

2 問題の定式化

3 ༰ྔεέʔϦϯά๏

3 ༰ྔεέʔϦϯά๏

3 ༰ྔεέʔϦϯά๏

3 ༰ྔεέʔϦϯά๏

3 容量スケーリング法

片　山　直　登

1 　はじめに

2 　問題の定式化

3 ^{༰ྔεέʔϦϯά๏}

3 ^{༰ྔεέʔϦϯά๏}

3 ^{༰ྔεέʔϦϯά๏}

3 ^{༰ྔεέʔϦϯά๏}

3 　容量スケーリング法