【世の中で使える最適化の数学を紹介してみた】運送に必要なトラックの台数を数学を使って求めてみた

はじめに

こんにちは！しゅんです！

いきなりですが皆さんはいま運送会社の従業員で、荷物の配送方法について考えています。

運送したい荷物がたくさんあるのでトラックを何台か使って運送するんですけど、トラックをたくさん使うほど燃料代や人件費がかかってしまいます。

この記事ではなるべく使うトラックの台数を少なくしつつ、全ての荷物を積むためには何台必要なのかを数学を使って求めてみたいと思います！

組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！

もっとみる

このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。

このブログについて

このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！

ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。

そもそも経営工学とは何なのでしょうか。Wikipediaによると

経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。

引用元 : 経営工学 – Wikipedia

長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。

問題設定

それではまず今回考える問題をちゃんと設定しましょう。

問題設定

・ある運送会社は100個の荷物を最大20台のトラックで運送しなければならない。
・1台のトラックに積める荷物は合計で1000kgまで。
・荷物の重さは1kg以上100kg以下。

目的
運送に使うトラックの台数を最小化したい

おそらく何も考えずにトラックを20台使ったら運送できそうですね。でもそれだとコストがかかりすぎるので、トラックの台数の最適化を行いましょう。

整数計画問題として定式化

「記号の設定」、「目的関数の設定」、「制約条件の設定」の3つに分けて説明したいと思います。

記号の設定

パラメータとして荷物の集合と、トラックの集合、荷物の重さ、トラックの重量制限を設定します。変数は0-1変数\(x_{ij},y_j\)を使いたいと思います。

パラメータ：
\(L\) : 荷物の集合 \((|L| = 100)\)
\(T\) : トラックの集合 \((|T| = 20)\)
\(w_i\) : 荷物\(i\)の重さ \((w_i \in [1,100], w_i \in \mathbb{Z})\)
\(K\) : トラックの重量制限 \((K = 1000)\)

変数：

\(x_{ij} \in \{0,1\}\) : 荷物\(i\)がトラック\(j\)に積まれるなら1、そうでないなら0を取る0-1変数
\(y_j \in \{0,1\}\) : トラック\(j\)に荷物が積まれたら1、そうでないなら0を取る0-1変数

わざわざ記号を用いるのはより一般的な問題でも適用できるようにするためです。今回の問題を解くだけならかっこの中を参照してください。

目的関数の設定

この問題の目的は

「運送に使うトラックの台数を最小化したい」

です。よって以下のように表すことができます。

目的関数：\(\sum\limits_{j = 1}^{20} y_j \)

例えばトラック1、4、17を使うとします。このとき目的関数値は

\(\sum\limits_{j = 1}^{20} x_i = y_1 + y_4 + y_{17}= 3\)

となります。この値は何台トラックを使ったかに対応します。今回はこれを最小化することを考えます。

目的関数を最小化する

\( \min \;\;\; \sum\limits_{j = 1}^{20} y_j \)

制約条件の設定

制約条件：

\(\sum\limits_{i = 1}^{100} w_ix_{ij} \leq 1000 \;\;\; ( j = 1,2,…,20)\) → ①
\(\sum\limits_{j = 1}^{20} x_{ij} = 1 \;\;\; (i = 1,2,…,100)\) → ②
\(100y_j \geq \sum\limits_{i = 1}^{100} x_{ij} \;\;\; (j = 20)\) → ③

1つずつ解説していきます。

1つ目の制約

1つ目の制約：

\(\sum\limits_{i = 1}^{100} w_ix_{ij} \leq 1000 \;\;\; ( j = 1,2,…,20)\)

1つ目の制約はトラックに積めるの荷物の重さの合計は1000kgということを表しています。

例えばトラック1に荷物1,2,3,4,5を積むとします。簡単のため荷物の重さは全部100kgだとします。このとき制約式の左辺は

\(\sum\limits_{i =1}^{100} w_ix_{i1} = 100x_{11}+100x_{21}+100x_{31}+100x_{41}+100x_{51} = 500\)

となり、1000以下となるので制約式を満たします。これは荷物1,2,3,4,5の重さの合計が500kgで、重量制限を満たしていることを表しています。一方例えばトラック1に荷物1～15を積もうとします。このとき制約式の左辺は

\(\sum\limits_{i =1}^{100}w_ix_{i1} = 100x_{11}+100x_{21}+ \cdots +100x_{151} = 1500\)

となり、1000より大きくなるので制約式を満たしません。これは荷物1～15の重さの合計が1500kgで、重量制限を満たしていないことを表しています。

2つ目の制約

2つ目の制約：

\(\sum\limits_{j = 1}^{20} x_{ij} = 1 \;\;\; (i = 1,2,…,100)\)

2つ目の制約は荷物が必ずいずれかのトラックに積まれることを表しています。

例えば荷物1がどのトラックにも積まれないとします。このとき\(x_{1j} = 0 \; (\forall j \in T)\)となります。そして制約式の左辺は

\(\sum\limits_{j = 1}^{20} x_{1j} = x_{11}+x_{12} + \cdots + x_{120} = 0\)

となり、制約式を満たしません。逆にあり得ない仮定ですが、荷物1がトラック1とトラック3に積まれるとします。このとき\(x_{11} = x_{13} = 1\)となり、制約式の左辺は

\(\sum\limits_{j =1}^{20} x_{1j} = x_{11}+x_{12} + \cdots + x_{120} = 1+1 = 2\)

となり、制約式を満たしません。

このように左辺が1となる場合は、荷物が必ず1つのトラックに積まれる場合と対応しています。

3つ目の制約

3つ目の制約：

\(100y_j \geq \sum\limits_{i = 1}^{100} x_{ij} \;\;\; (j = 20)\)

3つ目の制約はトラック\(j\)に1つでも荷物が積まれたら\(y_j=1\)となる制約です。

例えばトラック1に荷物3,4,5が積まれるとします。このとき右辺は

\(\sum\limits_{i = 1}^{100} x_{i1} = x_{31} + x_{41} + x_{51}=3\)

となります。\(y_1 \in \{0,1\}\)なので、制約式を満たすためには\(y_1 = 1\)となる必要があります。

\(y_j\)の係数が100なのは、荷物の総数が100個だからです。制約式の右辺の式が取る値は最大でも100なので\(y_i = 1\)とすれば必ず制約式が成り立ちます。

逆にトラック1に荷物が1つも積まれないとします。このとき右辺は0を取ります。よって\(y_j\)が満たすべき式は

\(100y_1 \geq 0\)

となります。これだと\(y_1 = 1\)でも\(y_1 = 0\)でもどっちでも良くなります。しかし目的関数は\(y_j\)の合計の最小化なので、\(y_1 = 0\)の方が採用されます。

以上のことからトラック\(j\)に1つでも荷物が積まれたら\(y_j=1\)、そうでないなら\(y_j=0\)となることが分かります。

整数計画問題としてまとめる

以上のことを踏まえて整数計画問題として定式化しましょう。

変数：

\(x_{ij} \in \{0,1\}\)
\(y_i \in \{0,1\}\)

\( \min \;\;\; \sum\limits_{j = 1}^{20} y_j \)
\(\;\text{s.t.}\;\;\;\sum\limits_{i = 1}^{100} w_ix_{ij} \leq 1000 \;\;\; ( j = 1,2,…,20)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{j = 1}^{20} x_{ij} = 1 \;\;\; (i = 1,2,…,100)\)
\(\;\;\;\;\;\;\;\;\; 100y_j \geq \sum\limits_{i = 1}^{100} x_{ij} \;\;\; (j = 20)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(i = 1,2,…,100, \; j = 1,2,…,20)\)
\(\;\;\;\;\;\;\;\;\; y_{j} \in \{0,1\} \;\;(j = 1,2,…,20)\)

より一般的な形で定式化すると以下のようになります。

パラメータ：
\(L\) : 荷物の集合\((|L|=n)\)
\(T\) : トラックの集合
\(w_i\) : 荷物\(i\)の重さ
\(K\) : トラックの重量制限

変数：

\(x_{ij} \in \{0,1\}\)
\(y_i \in \{0,1\}\)

\( \min \;\;\; \sum\limits_{j \in T} y_j \)
\(\;\text{s.t.}\;\;\;\sum\limits_{i \in L} w_ix_{ij} \leq K \;\;\; (\forall j \in T)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{j \in T} x_{ij} = 1 \;\;\; (\forall i \in L)\)
\(\;\;\;\;\;\;\;\;\; ny_j \geq \sum\limits_{i \in L} x_{ij} \;\;\; (\forall j \in T)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(\forall i \in L, \; \forall j \in T)\)
\(\;\;\;\;\;\;\;\;\; y_{j} \in \{0,1\} \;\;(\forall j \in T)\)

pythonで解いてみる

それでは実際にこの問題をpythonで解いてみましょう。結論以下のコードを実行することで問題を解くことができます。

## 事前準備
!pip install pulp
from pulp import *
import random
random.seed(1)

## 記号の定義
L = [i for i in range(100)] # 荷物の集合
T = [j for j in range(20)] # トラックの集合
w = [random.randint(1,100) for _ in range(100)] # 重さの集合
K = 1000

## 整数計画問題として定式化
prob = pulp.LpProblem(sense = LpMinimize) # 問題をMaximizeに設定
x = LpVariable.dict("x",(L,T), cat = "Binary") # 0-1変数の設定
y = LpVariable.dict("y",T, cat = "Binary") # 0-1変数の設定

prob += lpSum(y[j] for j in T) # 目的関数の設定

for j in T:
  prob += lpSum(w[i] * x[i,j] for i in L) <= K # 重量制限

for i in L:
  prob += lpSum(x[i,j] for j in T) == 1 # 荷物は必ずいずれかのトラックに積まれる

for j in T:
  prob += len(L) * y[j] >= lpSum(x[i,j] for i in L)


result = prob.solve() # 問題を解く

## 結果の表示
print(LpStatus[result]) # 得られた結果の状態を表示（Optimalなら最適解が得られている）
print("最適値 :", prob.objective.value()) # 最適値を表示

このコードを実行したら以下の結果が得られました。

コードの説明と結果の解釈の2つに分けて話したいと思います。

コードの説明

事前準備

## 事前準備
!pip install pulp # pulpをインストール
from pulp import *
import random
random.seed(1)

問題を解くための事前準備としてpulpをインストール、インポート、randamをインポートします。pulpはpythonで数理計画問題を解くのに便利なやつです。randomはpythonで乱数を使うときに便利なやつです。2行目でpulpのインストール、3行目でpulpのインポート、4行目でrandomのインポート、5行目でランダム値の固定を行っています。

記号の定義

## 記号の定義
L = [i for i in range(100)] # 荷物の集合
T = [j for j in range(20)] # トラックの集合
w = [random.randint(1,100) for _ in range(100)] # 重さの集合
K = 1000

7～11行目では記号の定義をしています。8行目で荷物の集合\(I\)、9行目でトラックの集合、10行目で荷物\(i\)の重さ\(w_i\)をそれぞれリスト形式で設定しています。11行目でトラックの重量制限を設定しています。

整数計画問題として定式化

## 整数計画問題として定式化
prob = pulp.LpProblem(sense = LpMinimize) # 問題をMaximizeに設定
x = LpVariable.dict("x",(L,T), cat = "Binary") # 0-1変数の設定
y = LpVariable.dict("y",T, cat = "Binary") # 0-1変数の設定

prob += lpSum(y[j] for j in T) # 目的関数の設定

for j in T:
  prob += lpSum(w[i] * x[i,j] for i in L) <= K # 重量制限

for i in L:
  prob += lpSum(x[i,j] for j in T) == 1 # 荷物は必ずいずれかのトラックに積まれる

for j in T:
  prob += len(L) * y[j] >= lpSum(x[i,j] for i in L)


result = prob.solve() # 問題を解く

13～30行目で整数計画問題として定式化しています。

14行目では問題を最大化(Maximize)に設定しています。
15行目では変数\(x_{ij}\)の設定をしています。
16行目では変数\(y_j\)の設定をしています。
18行目では目的関数を設定しています。
20～21行目では制約条件\(\sum\limits_{i \in L} w_ix_{ij} \leq K \;\; (\forall j \in T)\)を設定しています。
23～24行目では制約条件\(\sum\limits_{j \in T} x_{ij} = 1 \;\; (\forall i \in L)\)を設定しています。
26～27行目では制約条件\(ny_j \geq \sum\limits_{i \in L} x_{ij} \;\;\; (\forall j \in T)\)を設定しています。
30行目で問題を解いています。

結果の表示

## 結果の表示
print(LpStatus[result]) # 得られた結果の状態を表示（Optimalなら最適解が得られている）
print("最適値 :", prob.objective.value()) # 最適値を表示

32～34行目で計算結果を表示しています。

33行目で解の状態を表示しています。Optimalと表示されたら最適解が得られています。
34行目で最適値を表示しています。

変数の数が大きいので最適解は表示しないです。

結果の解釈

1行目は無視して大丈夫です。（pulpがちゃんとインストールされていることを示しています。）
2行目でOptimalと返されているのでちゃんと最適解が得られていることが分かります。
3行目は最適値が表示されています。最適値が6なので合計6台のトラックを使えば全ての荷物を運送できることが分かりました。

上図は各トラックに積む荷物の個数と各トラックに積む荷物の重量を表したグラフです。例えば最も多くの荷物を積んでいるトラックはトラック15であり、荷物の重量の合計はほぼ1000kgであることが分かります。

他の定式化でも解いてみる

ちなみにこの問題を解くための定式化は上記で紹介したもの以外にもあります。例えば以下のように定式化することもできます。

パラメータ：
\(L\) : 荷物の集合
\(T\) : トラックの集合
\(w_i\) : 荷物\(i\)の重さ
\(K\) : トラックの重量制限

変数：

\(x_{ij} \in \{0,1\}\)
\(y_i \in \{0,1\}\)

\( \min \;\;\; \sum\limits_{j \in T} y_j \)
\(\;\text{s.t.}\;\;\;\sum\limits_{i \in L} w_ix_{ij} \leq Ky_j \;\;\; (\forall j \in T)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{j \in T} x_{ij} = 1 \;\;\; (\forall i \in L)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(\forall i \in L, \; \forall j \in T)\)
\(\;\;\;\;\;\;\;\;\; y_{j} \in \{0,1\} \;\;(\forall j \in T)\)