アルゴリズムクイックリファレンス 第2版

8.7

 輸送

■

275

E

は

(w

＋

1)*(m

＋

n)

＋

m

*

n

＋

w

個の辺を持つ

積み替え問題から辺を構築するプロセスは、コードリポジトリ内のクラ

ス

Transshipment

に示されている。

人工的に加えたソース節点が

m

供給節点にコスト

0

で供給容量

sup(s

i

)

に等し

い容量で連結される。この

m

個の供給節点はそれぞれ

n

個の需要節点にコストが

d (i, j)

に等しく無限容量で連結される。

n

個の需要節点は新たな人工的ターゲット

節点にコスト

0

で容量が

dem (t

j

)

に等しく連結される。

w

個の倉庫節点があり、それ

ぞれ

m

個の供給節点とコストが

ts (i, k)

、容量が供給容量

sup(s

i

)

で連結される。こ

れらの倉庫節点は、

n

個の需要節点ともコストが

ts (k, j)

で容量が需要容量

dem (t

j

)

に等しい容量で連結される。最後に、倉庫間の辺は、倉庫の限界とコストに基づい

た容量とコストを持つ。

最小コスト解が得られれば

、

f (u, v)

＞

0

の辺

(u, v)

∈

E

を見つけることによって、

積み替えスケジュールが構築される。これらの辺についての

f (u, v)*d (u, v)

の総和

がスケジュールのコストとなる。

8.7

 輸送

輸送問題では、中間の倉庫節点がないので、積み替え問題よりも単純になる。入

力は次の通り。

●

商品を

sup(s

i

)

ユニット生成できる供給基地

s

i

が

m

個

●

商品を

dem (t

j

)

ユニット消費する需要基地

s

i

が

n

個

辺

(i, j)

で

1

ユニット輸送するのに固定コスト

d (i, j)

≧

0

がかかる。 ...