輸送問題とそのバリエーション

transportation problem(輸送問題)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} \\ &\text{subject to} && \sum_{j=1}^{m} x_{ij}= S_i \\ & && \sum_{i=1}^{n} x_{ij}= D_j \\ & && x_{ij} \geq 0 \end{aligned}

n箇所の工場からm箇所の倉庫へ荷物を運ぶことを考えます.工場iは {S_{i}}個の荷物があり,倉庫jは {D_{j}}個の荷物を受け取る必要があります.工場iと倉庫jを結ぶ経路 {x_{ij}}は1つ荷物送るごとに {c_{ij}}のコストがかかります.工場から倉庫にすべての荷物を送るのにかかる最小のコストを求める問題です.

fixed charge transportation problem(FCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{n} \sum_{j=1}^{m} (c_{ij} x_{ij} + d_{ij} y_{ij}) \\ &\text{subject to} && \sum_{j=1}^{m} x_{ij}= S_i \\ & && \sum_{i=1}^{n} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

fixed charge transportation problemは輸送問題に加えて枝に固定のコストが追加されたものです.
枝(i, j)を使うと流量 {x_{ij}}に関係なく {d_{ij}}が固定コストとしてかかります.
工場から倉庫へ荷物を送るときに,経路を使えるようにするための契約料金がかかる場合です.

pure fixed charge transportation problem(PFCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{n} \sum_{j=1}^{m} d_{ij} y_{ij} \\ &\text{subject to} && \sum_{j=1}^{m} x_{ij}= S_i \\ & && \sum_{i=1}^{n} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

pure fixed charge transportation problemはfixed charge transportation problemから流量にかかるコストが取り除かれたものです.
工場から倉庫へ荷物を送るときに,経路を定額利用できる場合です.
プログラミングコンテストチャレンジブックの最小費用流のコラムに,「流量×コストの和を最小化ではなく、流量が正である辺のコストの和を最小化したい場合」とありますが,たぶんこの問題です(正確にはこの問題に容量制約がついたもの).

pure constant fixed charge transportation problem(PC-FCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{n} \sum_{j=1}^{m} d y_{ij} \\ &\text{subject to} && \sum_{j=1}^{m} x_{ij}= S_i \\ & && \sum_{i=1}^{n} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

pure constant fixed charge transportation problemはpure fixed charge transportation problemの固定コストがすべて同じ値のものです.
 {d}を1とすれば,SupplyからDemandにものを送る際に使う枝の数を最小化する問題になります.
工場から倉庫へ荷物を送るときに,経路を定額利用でき,どの経路も同じコストの場合にあたります.

PC-FCTPをPulpで解く

PC-FCTPはNP-Hardなのですが,小規模なら厳密解が求められます.
試しにpulpで解いてみます.

結果

Status: Optimal
Total Cost:13.0
Assignment:
Left:0 -> Right:7(8.0)
Left:1 -> Right:8(6.0)
Left:2 -> Right:3(7.0)
Left:3 -> Right:4(10.0)
Left:3 -> Right:7(1.0)
Left:4 -> Right:0(11.0)
Left:5 -> Right:6(13.0)
Left:6 -> Right:8(6.0)
Left:7 -> Right:6(13.0)
Left:8 -> Right:5(11.0)
Left:8 -> Right:9(9.0)
Left:9 -> Right:1(11.0)
Left:9 -> Right:2(10.0)
2sec

参考