組合せ最適化を材料調達に応用してみた

# はじめに
材料調達業務に数理最適化を使用した例があまり出てなさそうな気がしたので、新卒で調達業務をしていた頃に行った数年前の事例をデフォルメして記すことします。
大した例ではないですが、どなたかの役に立てば幸いです。

# 調達業務とは
- この記事では**メーカーの調達業務**を取り扱うことにします。
- つまり自社の生産ラインに必要な材料を他社から買い付ける人（バイヤー）の業務を扱います。
 - 例えばPCメーカーL社のバイヤーは半導体メーカーI社からCPUを買い付けます。

# 概要
### バッグ生産の工程
- C社の工場ラインでは様々な大きさのバッグ(同じ素材でサイズ違い)を作ることにする。
- バッグにはD社の生地を使用する。
- C社の工程は以下の通り。（詳細は下の図）
    - 切り替え工程：裁断機の上下から現在の生地を降ろし、別の幅の生地をセットする。
    - 裁断工程：裁断機を動かし、規定の幅へ裁断（トリミング）する。切れ端は廃棄する。
    - 縫製工程：裁断された上下の生地を縫い合わせバッグを作る。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/985685/8852f434-5dc4-b50a-ccde-f18bcd7fb986.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/985685/f9c02321-0c0f-b880-ccc8-5ffd08ad88e0.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/985685/cd4cc419-da99-e70a-f21a-12ec99c8a9da.png)

**※注意**<br>実際は全く別の製品で最適化を行っています。<br> したがって上記製法は正しくないかもしれませんが、あくまで例としてお読みください。

###材料調達状況
- C社はD社から同じ素材の生地を**5幅**買っている。
- D社の生地は幅(mm)によらず、単価は100円/㎡とする。


|No.|幅|単価(㎡)|
|:----:|:----:|:----:|
|1|520mm|100円/㎡|
|2|600mm|100円/㎡|
|3|740mm|100円/㎡|
|4|800mm|100円/㎡|
|5|1,000mm|100円/㎡|

- 調達する生地の幅や幅数は変更できるが、D社の設備仕様上、生地の幅(mm)は10mm刻みで最小500mm～最大1,000mmしか作れない。

### バッグの生産・販売状況

- ロール状の生地は重いので切り替え工程は大変。生地の幅数が1つ増えるごとに切り替え工程の工数が1,500,000円/年増える（ことにする）。
- 生地が5幅しかない一方、各販売先の要望サイズは多岐にわたるため、C社はこの**5幅**の生地から縦横サイズの異なる**100種類**のバッグを生産している。

# 考えたこと
- 裁断工程で生じる切れ端分の生地も100円/㎡で買っているので、バッグになることなく廃棄するのはもったいない。切れ裁断工程で生じる切れ端を最小にしたい。
- 一方で、生地の切り替え工数もなるべく抑えたい。

# やりたいこと
- pythonを用いて**切れ端となって廃棄する生地の金額**と生地の**切り替え工数**が最も小さくなる**生地幅の組み合わせ**を求めたい。

# 前提条件
- C社が客先に販売するバッグの寸法と年間数量は(ランダムで起こした)以下とする。

|バッグの品番|幅寸法(mm)|縦寸法(mm)|数量(個/年)|生地幅(最適化前)|
|:----|:----|:----|:----|:----|
|1|817|1,855|2,120|1,000|
|2|565|859|21,770|600|
|3|778|646|28,491|800|
|4|668|917|27,361|740|
|5|563|1,129|22,365|600|
|6|662|1,720|21,431|740|
|7|575|897|302|600|
|8|549|1,150|15,500|600|
|9|668|1,583|12,934|740|
|10|605|731|17,716|740|
|11|737|862|12,626|740|
|12|924|1,409|19,809|1,000|
|13|946|911|9,780|1,000|
|14|910|1,088|780|1,000|
|15|935|1,883|18,478|1,000|
|16|989|1,115|21,332|1,000|
|17|630|1,946|9,947|740|
|18|768|619|23,197|800|
|19|585|1,576|26,454|600|
|20|958|1,121|10,220|1,000|
|21|564|266|10,511|600|
|22|665|281|16,989|740|
|23|941|1,775|10,050|1,000|
|24|546|1,092|8,674|600|
|25|840|1,962|408|1,000|
|26|932|1,650|894|1,000|
|27|596|1,440|23,985|600|
|28|649|1,861|6,140|740|
|29|936|631|20,634|1,000|
|30|915|994|13,803|1,000|
|31|865|324|15,460|1,000|
|32|971|586|6,415|1,000|
|33|722|1,003|3,979|740|
|34|933|1,681|22,587|1,000|
|35|846|1,991|10,813|1,000|
|36|740|1,439|8,708|740|
|37|586|940|7,609|600|
|38|843|622|1,952|1,000|
|39|904|1,261|15,705|1,000|
|40|523|1,366|12,390|600|
|41|508|424|18,736|520|
|42|659|1,945|18,830|740|
|43|978|1,408|14,805|1,000|
|44|987|314|24,601|1,000|
|45|661|750|8,738|740|
|46|947|728|16,274|1,000|
|47|832|269|19,437|1,000|
|48|707|575|23,943|740|
|49|982|1,775|3,118|1,000|
|50|576|236|24,583|600|
|51|899|788|832|1,000|
|52|845|243|13,364|1,000|
|53|866|468|25,456|1,000|
|54|960|1,413|15,472|1,000|
|55|960|1,535|12,313|1,000|
|56|536|904|28,872|600|
|57|988|1,745|9,226|1,000|
|58|894|703|5,418|1,000|
|59|509|1,006|17,315|520|
|60|623|1,601|28,039|740|
|61|985|744|3,017|1,000|
|62|656|1,797|6,931|740|
|63|780|361|24,886|800|
|64|606|313|26,229|740|
|65|820|794|21,857|1,000|
|66|911|627|24,301|1,000|
|67|935|937|6,146|1,000|
|68|656|691|17,998|740|
|69|586|1,081|6,946|600|
|70|506|1,265|14,622|520|
|71|732|271|26,999|740|
|72|773|507|5,041|800|
|73|547|1,435|18,547|600|
|74|870|1,874|25,541|1,000|
|75|599|906|9,180|600|
|76|769|706|6,036|800|
|77|592|397|15,923|600|
|78|595|1,231|11,845|600|
|79|831|1,747|4,402|1,000|
|80|685|1,933|29,523|740|
|81|549|1,342|20,865|600|
|82|618|464|11,997|740|
|83|722|939|7,863|740|
|84|802|523|16,194|1,000|
|85|554|1,516|22,599|600|
|86|506|1,488|14,829|520|
|87|856|574|22,849|1,000|
|88|764|1,629|7,477|800|
|89|529|1,674|1,061|600|
|90|589|733|14,085|600|
|91|759|883|2,513|800|
|92|719|474|4,763|740|
|93|508|1,961|23,064|520|
|94|747|587|20,981|800|
|95|864|1,646|316|1,000|
|96|576|536|25,852|600|
|97|764|289|18,777|800|
|98|598|1,203|7,705|600|
|99|708|925|4,784|740|
|100|800|969|4,193|800|

- バッグの縦方向と幅方向を置換して裁断することはできない。
- 今回は在庫については検討から除外する。

# pythonで作ってみた
- [前回](https://qiita.com/mmura001/items/a826fcc89da8ae575cac)のきれいでないコードを用いているので、読みにくいですがご容赦ください。

### ライブラリのインストール

```python:python
import math
import numpy as np
import pandas as pd
from pulp import*
from ortoolpy import addvars, addbinvars
```

### 生産するバッグの品番情報(CSV)の読み込み
- CSVを読み込み、品番数×生地幅(D社生産可能な500mm～1000mm：10mm刻み)の表へ変形。
- この後の計算の都合上、tbl2のTrue/Falseを入れ替え(tbl_2)。

```python:python
tbl1 = pd.read_csv('bag_model.csv') #csvの読み込み

a = tbl1['幅寸法(mm)']
b = tbl1['縦寸法(mm)']
c = tbl1['数量(個/年)']
widmin = 500 # 生地の最小幅は500mm
widmax = 1000  # 生地の最大幅は1000mm
widlist =[i for i in range(widmin,widmax+1,10)] 
# D社の作れる生地の幅をリスト化（10mm刻みで作れる。）

bag = len(tbl1) #bagのモデル数
widnum=len(widlist)
tbl2 = np.zeros(bag*widnum).reshape(bag,widnum)
for i in range(bag):
    just = math.ceil(a[i]/10)*10 #バッグを作成できる最小の生地幅。
    startrow = (just-500)//10
    tbl2[i,startrow:]=1 # バッグを作成できる最小幅(mm)から最大幅1000mmまで1にする。
tbl2 = tbl2.astype(np.bool).copy() #作成可能な生地幅を1に変更。

tbl_2 = ~tbl2 #~でFalseとTrueを裏返す。このあとtbl4で使用する。
tbl_2 = tbl_2.astype(np.int) # 0と1に戻す。
```

### 品番ごとの総切れ端(㎡/年間)表の作成
- 各品番ごとですべての生地幅における総切れ端(㎡/年間)を計算しテーブルを作成。
    - (生地幅－バッグ横幅)×バッグ縦幅×年間数量で計算可能。
- 生地幅<バッグ横幅の場合は生産できないので、便宜的に(最適解にならないよう)1億㎡とした。
<Br>※前回のコードを流用しているのでtbl3はありません。

```python:python
#各幅での切れ端(m2/年)の表を作成。
#生地幅<バッグの幅になってはならないので、ペナルティで1億m2。
tbl4 = tbl_2*100000000
for i in range(bag):
    just = math.ceil(a[i]/10)*10
    startrow = (just-500)//10 #最小の幅が何列目か計算。
    count = 0 
    for j in range(widnum-startrow):
        material_loss =((just - a[i] + count)/1000)*(b[i]/1000)*2*c[i] #切れ端m2/年の計算。(生地幅ーバッグ横幅)×バッグ縦幅×年間数量
        tbl4[i,j+startrow]=material_loss
        count+=10
```

### 変数の宣言
- 生地幅の採用有無が入るバッグ数×生地幅数のバイナリ変数を作る(tbl5)。
- 採用幅数を計算するためのバイナリ変数を作る(tbl6)。

```python:python
tbl5 = np.array(addbinvars(widnum,bag))
#バッグの品番数×生地の幅数で変数matrixを作成(バイナリ変数)

tbl6 = addbinvars(widnum) #生地の幅数計算のためのテーブル。使用する生地幅に1が立つのでlpSumで幅数を計算可能。

tbl_2 = tbl_2.T.tolist() #目的関数作成用に変換
tbl4 = tbl4.T.tolist()
```

### モデル化・最適化処理
- 条件を式に落とし最適化計算。

```python:python
Closs = 100 #切れ端金額のペナルティ 100円/m2。
Cswt = 1500000 #切り替え工数金額のペナルティ。150万円/幅数。

m = LpProblem(sense=LpMinimize) #最小化問題の宣言
m += (Closs * lpDot(tbl4,tbl5)
    + Cswt * lpSum(tbl6))
# 目的関数の式
# 1行目はすべてのバッグ品番の切れ端廃棄金額(年間)
# 2行目は切り替え工数(年間)
# すべての合計が最小になるときの各バッグ品番ごとの生地幅表を出力

for i in range(widnum):
    m += tbl6[i] >= (lpSum(tbl5[i,:])/bag)

# 制約条件の式1
# 選択された生地幅に1を、選択されない生地幅に0が立つ。

for j in range(bag):
    m += lpSum(tbl5[:,j]) <= 1
    m += lpSum(tbl5[:,j]) >= 1

# 制約条件の式2
# 1品番あたり、必ず1つ幅を決める

m.solve()
print('目的関数', value(m.objective))
```

### 結果の出力
- 計算結果をCSVに出力。
- 最初に読み込んだbag_list.csvの右に最適化の結果を追記して、新たにbag_opt.csvとして保存。

```python:python
result = np.vectorize(value)(tbl5).astype(int).T #ソルバーの出力結果（生地幅数×品番数で0-1が埋まっている）
widkey = [i for i in range(widnum)] 
widdic = {key: width for key, width in zip(widkey, widlist)} 
result = [widdic[sum(result[i]*widkey)] for i in range(bag)] #各品番の最適幅のリストを作衛

tbl1['幅寸法(mm)'] = a.copy()
tbl1['縦寸法(mm)'] = b.copy()
tbl1['数量(個/年)'] = c.copy()
tbl1['最適幅']= result
tbl1.to_csv('bag_opt.csv',index=False,encoding='utf-8_sig')  #csvで出力。
```

|バッグの品番|幅寸法(mm)|縦寸法(mm)|数量(個/年)|生地幅(最適化前)|生地幅(最適化後)|
|:----|:----|:----|:----|:----|:----|
|1|817|1,855|2,120|1,000|870|
|2|565|859|21,770|600|600|
|3|778|646|28,491|800|780|
|4|668|917|27,361|740|670|
|5|563|1,129|22,365|600|600|
|6|662|1,720|21,431|740|670|
|7|575|897|302|600|600|
|8|549|1,150|15,500|600|550|
|9|668|1,583|12,934|740|670|
|10|605|731|17,716|740|670|
|11|737|862|12,626|740|780|
|12|924|1,409|19,809|1,000|940|
|13|946|911|9,780|1,000|990|
|14|910|1,088|780|1,000|940|
|15|935|1,883|18,478|1,000|940|
|16|989|1,115|21,332|1,000|990|
|17|630|1,946|9,947|740|670|
|18|768|619|23,197|800|780|
|19|585|1,576|26,454|600|600|
|20|958|1,121|10,220|1,000|990|
|21|564|266|10,511|600|600|
|22|665|281|16,989|740|670|
|23|941|1,775|10,050|1,000|990|
|24|546|1,092|8,674|600|550|
|25|840|1,962|408|1,000|870|
|26|932|1,650|894|1,000|940|
|27|596|1,440|23,985|600|600|
|28|649|1,861|6,140|740|670|
|29|936|631|20,634|1,000|940|
|30|915|994|13,803|1,000|940|
|31|865|324|15,460|1,000|870|
|32|971|586|6,415|1,000|990|
|33|722|1,003|3,979|740|780|
|34|933|1,681|22,587|1,000|940|
|35|846|1,991|10,813|1,000|870|
|36|740|1,439|8,708|740|780|
|37|586|940|7,609|600|600|
|38|843|622|1,952|1,000|870|
|39|904|1,261|15,705|1,000|940|
|40|523|1,366|12,390|600|550|
|41|508|424|18,736|520|550|
|42|659|1,945|18,830|740|670|
|43|978|1,408|14,805|1,000|990|
|44|987|314|24,601|1,000|990|
|45|661|750|8,738|740|670|
|46|947|728|16,274|1,000|990|
|47|832|269|19,437|1,000|870|
|48|707|575|23,943|740|780|
|49|982|1,775|3,118|1,000|990|
|50|576|236|24,583|600|600|
|51|899|788|832|1,000|940|
|52|845|243|13,364|1,000|870|
|53|866|468|25,456|1,000|870|
|54|960|1,413|15,472|1,000|990|
|55|960|1,535|12,313|1,000|990|
|56|536|904|28,872|600|550|
|57|988|1,745|9,226|1,000|990|
|58|894|703|5,418|1,000|940|
|59|509|1,006|17,315|520|550|
|60|623|1,601|28,039|740|670|
|61|985|744|3,017|1,000|990|
|62|656|1,797|6,931|740|670|
|63|780|361|24,886|800|780|
|64|606|313|26,229|740|670|
|65|820|794|21,857|1,000|870|
|66|911|627|24,301|1,000|940|
|67|935|937|6,146|1,000|940|
|68|656|691|17,998|740|670|
|69|586|1,081|6,946|600|600|
|70|506|1,265|14,622|520|550|
|71|732|271|26,999|740|780|
|72|773|507|5,041|800|780|
|73|547|1,435|18,547|600|550|
|74|870|1,874|25,541|1,000|870|
|75|599|906|9,180|600|600|
|76|769|706|6,036|800|780|
|77|592|397|15,923|600|600|
|78|595|1,231|11,845|600|600|
|79|831|1,747|4,402|1,000|870|
|80|685|1,933|29,523|740|780|
|81|549|1,342|20,865|600|550|
|82|618|464|11,997|740|670|
|83|722|939|7,863|740|780|
|84|802|523|16,194|1,000|870|
|85|554|1,516|22,599|600|600|
|86|506|1,488|14,829|520|550|
|87|856|574|22,849|1,000|870|
|88|764|1,629|7,477|800|780|
|89|529|1,674|1,061|600|550|
|90|589|733|14,085|600|600|
|91|759|883|2,513|800|780|
|92|719|474|4,763|740|780|
|93|508|1,961|23,064|520|550|
|94|747|587|20,981|800|780|
|95|864|1,646|316|1,000|870|
|96|576|536|25,852|600|600|
|97|764|289|18,777|800|780|
|98|598|1,203|7,705|600|600|
|99|708|925|4,784|740|780|
|100|800|969|4,193|800|870|

### 結果と効果整理
- 最適化前は5幅、最適化後は7幅となった。

|No.|幅(最適化前)|幅(最適化後)|
|:----:|:----:|:----:|
|1|520mm|550mm|
|2|600mm|600mm|
|3|740mm|670mm|
|4|800mm|780mm|
|5|1,000mm|870mm|
|6|-|940mm|
|7|-|990mm|

- 最適化による効果は△6,803千円/年となった。詳細は以下の通り。

|項目|最適化前|最適化後|効果|
|:----:|:----:|:----:|:----:|
|1.切れ端生地の金額|17,099,145円/年|7,295,875円/年|△9,803,270円/年|
|2.切り替え工程の工数|7,500,000円/年|10,500,000円/年|+3,000,000円/年|
|1と2の合計|24,599,145円/年|17,795,875円/年|△6,803,270円/年|

# まとめ・感想
　実際の業務でも大幅な効果が出ました。何より一度このような計算の仕組みを作ってしまえば、販売数量・材料市況などが変化しても常に最適解で材料発注ができることが大きいと思います。
　今回の事例では材料調達先における生産ラインの制約を守ったうえで発注戦略を検討し、自社の工場ラインの無駄取りを行いました。このようにメーカーの調達というのは材料調達先の生産条件に精通し、調達先の潜在能力を最大限活用しながら、自社のものづくりを改善していくことができる役職であると思います。
　いずれにしても、最適化を用いて材料調達先と自社製造現場というサプライチェーンをまたいだ無駄取りが簡単にできるのは素晴らしいことだと思います。このような活動も広まっていけばよいなと思う次第です。

# 参考
- [「組合せ最適化でナーススケジューリング問題を解く」](https://qiita.com/SaitoTsutomu/items/a33aba1a95828eb6bd3f)
- [「遺伝的アルゴリズムでナーススケジューリング問題（シフト最適化）を解く」](https://qiita.com/shouta-dev/items/1970c2746c3c30f6b39e)