輸送問題 (Transportation Problem)

6月 4, 2024

輸送問題 (Transportation Problem)

最適化問題の例として、輸送問題 (Transportation Problem) を考えます。

この問題は、複数の供給地から複数の需要地に商品を輸送する際の輸送コストを最小化する問題です。

以下は簡単な輸送問題の例です。

問題設定:

供給地A、B、Cがあり、それぞれの供給量は次の通りです:
- A: 20
- B: 30
- C: 25
需要地1、2、3があり、それぞれの需要量は次の通りです:
- 1: 30
- 2: 35
- 3: 10
各供給地から各需要地への輸送コストは次のように設定されています:

	1	2	3
A	8	6	10
B	9	12	13
C	14	9	16

この輸送問題を PuLP で解いてみましょう。

import pulp

# 供給量
supply = {'A': 20, 'B': 30, 'C': 25}

# 需要量
demand = {1: 30, 2: 35, 3: 10}

# 輸送コスト
cost = {'A': {1: 8, 2: 6, 3: 10},
        'B': {1: 9, 2: 12, 3: 13},
        'C': {1: 14, 2: 9, 3: 16}}

# 問題の定義
prob = pulp.LpProblem("Transportation_Problem", pulp.LpMinimize)

# 変数の定義
routes = [(i,j) for i in supply for j in demand]
vars = pulp.LpVariable.dicts("Route", (supply, demand), lowBound=0, cat='Continuous')

# 目的関数
prob += pulp.lpSum([vars[i][j] * cost[i][j] for (i, j) in routes])

# 制約条件
# 各供給地から出る供給量がその供給地の供給量に等しい
for i in supply:
    prob += pulp.lpSum([vars[i][j] for j in demand]) == supply[i]

# 各需要地に入る供給量がその需要地の需要量に等しい
for j in demand:
    prob += pulp.lpSum([vars[i][j] for i in supply]) == demand[j]

# 最適化の実行
prob.solve()

# 結果の表示
print("Status:", pulp.LpStatus[prob.status])
print("Total Cost:", pulp.value(prob.objective))
for v in prob.variables():
    print(v.name, "=", v.varValue)

このコードでは、供給地と需要地の間の輸送量を決定し、全体の輸送コストを最小化するように最適化しています。

最適化の結果に基づいて、どの供給地からどの需要地にいくらの商品を輸送すればコストが最小になるかを表示します。

[実行結果]

Status: Optimal
Total Cost: 655.0
Route_A_1 = 0.0
Route_A_2 = 10.0
Route_A_3 = 10.0
Route_B_1 = 30.0
Route_B_2 = 0.0
Route_B_3 = 0.0
Route_C_1 = 0.0
Route_C_2 = 25.0
Route_C_3 = 0.0

ソースコード解説

ソースコードを詳しく解説します。

1. 概要

このプログラムは、Pulpライブラリを使用して輸送問題を最適化する例です。

輸送問題は、供給地から需要地へ物資を輸送する際のコストを最小化するために、各ルートに割り当てる物資の量を決定する問題です。

2. 必要なライブラリのインポート

1	import pulp

Pulpは、線形計画問題（LP）や整数計画問題（ILP）を解くためのPythonライブラリです。

3. データの定義

# 供給量
supply = {'A': 20, 'B': 30, 'C': 25}

# 需要量
demand = {1: 30, 2: 35, 3: 10}

# 輸送コスト
cost = {'A': {1: 8, 2: 6, 3: 10},
        'B': {1: 9, 2: 12, 3: 13},
        'C': {1: 14, 2: 9, 3: 16}}

供給量: 各供給地の供給量を表します。
需要量: 各需要地の需要量を表します。
輸送コスト: 各供給地から需要地への輸送コストを表します。

4. 問題の定義

1	prob = pulp.LpProblem("Transportation_Problem", pulp.LpMinimize)

輸送問題を最小化問題として定義します。ここでは、輸送コストを最小化することが目的です。

5. 変数の定義

1 2	routes = [(i,j) for i in supply for j in demand] vars = pulp.LpVariable.dicts("Route", (supply, demand), lowBound=0, cat='Continuous')

routes: 全ての供給地と需要地の組み合わせをリストにします。
vars: 各ルートにおける輸送量を表す変数を定義します。ここでは、連続変数として定義しています。

6. 目的関数の定義

1	prob += pulp.lpSum([vars[i][j] * cost[i][j] for (i, j) in routes])

目的関数は、全てのルートにおける輸送コストの総和を最小化することです。

7. 制約条件の定義

# 各供給地から出る供給量がその供給地の供給量に等しい
for i in supply:
    prob += pulp.lpSum([vars[i][j] for j in demand]) == supply[i]

# 各需要地に入る供給量がその需要地の需要量に等しい
for j in demand:
    prob += pulp.lpSum([vars[i][j] for i in supply]) == demand[j]

供給制約: 各供給地から出る供給量が、その供給地の供給量に等しくなるようにします。
需要制約: 各需要地に入る供給量が、その需要地の需要量に等しくなるようにします。

8. 最適化の実行

1	prob.solve()

Pulpのsolveメソッドを使用して、定義した問題を解きます。

9. 結果の表示

print("Status:", pulp.LpStatus[prob.status])
print("Total Cost:", pulp.value(prob.objective))
for v in prob.variables():
    print(v.name, "=", v.varValue)

最適化のステータス（成功・失敗）を表示します。
最小化された総輸送コストを表示します。
各ルートにおける最適な輸送量を表示します。

結果解説

この実行結果を詳しく解説します。

[実行結果]

Status: Optimal
Total Cost: 655.0
Route_A_1 = 0.0
Route_A_2 = 10.0
Route_A_3 = 10.0
Route_B_1 = 30.0
Route_B_2 = 0.0
Route_B_3 = 0.0
Route_C_1 = 0.0
Route_C_2 = 25.0
Route_C_3 = 0.0

結果:

最適化ステータス: Optimal
- この結果は、PuLPが問題に対して最適な解を見つけたことを示しています。
総輸送コスト: 655.0
- この値は、最適な輸送計画に基づいて計算された最小の総コストです。

各供給地から各需要地への輸送量:

Route_A_1 = 0.0
- 供給地Aから需要地1への輸送量は 0 です。
Route_A_2 = 10.0
- 供給地Aから需要地2への輸送量は 10 です。
Route_A_3 = 10.0
- 供給地Aから需要地3への輸送量は 10 です。
Route_B_1 = 30.0
- 供給地Bから需要地1への輸送量は 30 です。
Route_B_2 = 0.0
- 供給地Bから需要地2への輸送量は 0 です。
Route_B_3 = 0.0
- 供給地Bから需要地3への輸送量は 0 です。
Route_C_1 = 0.0
- 供給地Cから需要地1への輸送量は 0 です。
Route_C_2 = 25.0
- 供給地Cから需要地2への輸送量は 25 です。
Route_C_3 = 0.0
- 供給地Cから需要地3への輸送量は 0 です。

解釈

この結果から、以下の輸送プランがコストを最小化するために用いられます。

供給地A:
- 需要地2に 10 単位を輸送します。 (コスト: $(6 \times 10 = 60)$)
- 需要地3に 10 単位を輸送します。 (コスト: $(10 \times 10 = 100)$)
供給地B:
- 需要地1に 30 単位を輸送します。 (コスト: $(9 \times 30 = 270)$)
供給地C:
- 需要地2に 25 単位を輸送します。 (コスト: $(9 \times 25 = 225)$)

総コストの計算

上記の輸送プランに基づいた輸送コストは次のように計算できます。

供給地Aのコスト: $(60 + 100 = 160)$
供給地Bのコスト: $(270)$
供給地Cのコスト: $(225)$

したがって、合計の輸送コストは下記のようになります。
$$
160 + 270 + 225 = 655
$$