製造業分野の最適化問題：輸送コストの最小化（混合整数計画法）

問題の概要

製造業での物流コストは企業の収益に直接影響を及ぼす重要な要素です。このコストを管理するためには、複数の工場から複数の小売店へ製品を効率良く輸送することが求められます。具体的には、工場の生産能力、小売店の需要、および輸送コストを考慮して、最も経済的な輸送方法を計画する必要があります。この計画を立てる際には、パレット数が整数であることを条件とする混合整数計画問題（MILP）を用います。この問題を解決することで、製造業者は効率的な物流ネットワークを築き、輸送コストを削減することが可能です。

製品輸送コストの最小化（具体例）

ある製造業者が、3つの工場から4つの小売店へ製品を輸送するケースを考えます。各工場が供給できるパレット数、各小売店の必要パレット数、そして輸送コストは下記の表に示されています。

工場 \ 小売店	A	B	C	D	供給量
1	1,000円	800円	1,500円	1,200円	20
2	1,200円	1,000円	900円	700円	30
3	800円	1,200円	1,000円	900円	25
需要量	10	15	20	30

目標は、すべての小売店の需要を満たしながら、総輸送コストを最小化することです。ただし、輸送されるパレット数は整数でなければならないという条件があります。

問題の定式化

パラメータ

パラメータ	説明	値
\(m\)	工場の数	3
\(n\)	小売店の数	4
\(s_i\)	工場 \(i\) の供給可能パレット数	\(s_1=20, s_2=30, s_3=25\)
\(d_j\)	小売店 \(j\) の需要パレット数	\(d_1=10, d_2=15, d_3=20, d_4=30\)
\(c_{ij}\)	工場 \(i\) から小売店 \(j\) への輸送コスト（円/パレット）	上記の表の値

決定変数

変数	説明	範囲
\(x_{ij}\)	工場 \(i\) から小売店 \(j\) へ輸送するパレット数	非負整数

目的関数

目的	式
総輸送コストの最小化	\(\text{minimize} \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}\)

総輸送コストは、各工場から各小売店への輸送コストと輸送パレット数の積の総和です。この値を最小化することが目的です。

制約条件

制約	式	説明
供給制約	\(\sum_{j=1}^n x_{ij} \leq s_i, \quad \forall i\)	各工場からの総輸送パレット数は、その工場の供給可能パレット数以下でなければならない
需要制約	\(\sum_{i=1}^m x_{ij} \geq d_j, \quad \forall j\)	各小売店への総輸送パレット数は、その小売店の需要パレット数以上でなければならない
非負整数制約	\(x_{ij} \geq 0, \quad x_{ij} \in \mathbb{Z}, \quad \forall i,j\)	輸送パレット数は非負の整数でなければならない

これらの制約により、すべての小売店の需要を満たしつつ、各工場の供給量を超えないような輸送計画が求められます。また、輸送パレット数は整数であるという条件も満たされます。

コード例

以下に、この問題を nAG Library for Python の混合整数計画問題専用ソルバー関数 handle_solve_milp を用いて解くコード例を示します。今回の問題は整数制約を含むため、handle_solve_milp のような汎用的な MILP ソルバーを選択しました。

import numpy as np
from naginterfaces.base import utils
from naginterfaces.library import opt
from naginterfaces.library import mip

# 輸送問題のデータを設定
supplies = [20, 30, 25]
demands = [10, 15, 20, 30]
costs = np.array([
    [1000, 800, 1500, 1200],
    [1200, 1000, 900, 700],
    [800, 1200, 1000, 900]
])
m = len(supplies) # 工場の数
n = len(demands) # 小売店の数

# 問題のサイズ
num_vars = m * n
num_constraints = m + n

# ハンドルの作成
handle = opt.handle_init(nvar=num_vars)

# 変数の上限と下限の設定
xl = np.zeros(num_vars)
xu = np.full(num_vars, np.inf)
opt.handle_set_simplebounds(handle, xl, xu)

# 目的関数の設定
c = costs.flatten()
opt.handle_set_linobj(handle, c)

# 制約式の設定
rows, cols, vals = [], [], []
# 供給制約
for i in range(m):
    for j in range(n):
        rows.append(i + 1)
        cols.append(i * n + j + 1)
        vals.append(1.0)
bl_supplies = supplies
bu_supplies = supplies
# 需要制約
for j in range(n):
    for i in range(m):
        rows.append(m + j + 1)
        cols.append(i * n + j + 1)
        vals.append(1.0)
bl_demands = demands
bu_demands = demands

# 制約式の下限と上限を結合
bl_combined = np.concatenate([bl_supplies, bl_demands])
bu_combined = np.concatenate([bu_supplies, bu_demands])

# 線形制約を問題のハンドルに追加
opt.handle_set_linconstr(handle, bl_combined, bu_combined, rows, cols, vals)

# ソルバーのオプション設定
opt.handle_opt_set(handle, "Print Level = 0")

# すべての変数を整数として設定
opt.handle_set_property(handle, ptype='INT', idx=list(range(1, num_vars + 1)))

# 問題を解く
res = mip.handle_solve_milp(handle)

# 結果の取得
x = res.x.reshape((m, n))
print("輸送コストの最小値: {:,}円".format(int(res.rinfo[0])))
print("各工場から各小売店への最適輸送パレット数:")
print(np.round(x).astype(int))

# ハンドルの破棄
opt.handle_free(handle)

結果例

コードを実行すると、以下の結果が得られます。

輸送コストの最小値: 62,000円
各工場から各小売店への最適輸送パレット数:
[[ 5 15  0  0]
 [ 0  0  0 30]
 [ 5  0 20  0]]

この結果は、次のことを示しています。

工場1から小売店Aに5パレット、小売店Bに15パレット輸送し、小売店CとDへの輸送はありません。
工場2からは小売店Dに30パレット輸送し、他の小売店への輸送はありません。
工場3から小売店Aに5パレット、小売店Cに20パレット輸送し、小売店BとDへの輸送はありません。

この輸送計画により、総輸送コストは62,000円となり、与えられた制約条件の下で最小の輸送コストを達成しています。また、輸送パレット数はすべて整数値となっています。

まとめ

ここでは、製造業における輸送コスト最小化問題を混合整数計画法（MILP）を用いて解き、具体的な数値例を用いて効率的な輸送計画を得る例を示しました。この基本モデルに対して、輸送キャパシティの制約を追加したり、製品ごとの需要と輸送コストを考慮して複数の製品を同時に輸送することを考慮したり、各拠点でのフローバランス制約を追加したりするなど、より現実的な応用も可能です。