【輸送計画問題】DC経由にするか工場直送にするかを整数計画法で解いてみる
工場直送かDC経由かを輸送計画したいケース
あるメーカーは工場からDC(物流センター)を経由して卸へ納品していますが、工場に近い3か所については直送で卸に納品することもあります。
どちらから送るかは、受注時に貨物量を見ながら判断しています。
アイテム数は2で、ある日、3社の受注箱数は下記の通りでした。
また、DC及び工場の在庫箱数は下記の通りでした。
DC及び工場から納品先への運賃は箱単位で、商品別に次のように決まっています。
一方、車建て(チャーター)の運賃もあり、その場合は1,500箱満載のトラックの運賃が
DC⇒卸3か所周遊・・・65,000円
工場⇒卸3か所周遊・・・50,000円
です。
この日は、どのように配車すれば配送料金が最小になるでしょうか?
業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!
車建て優先で配車する場合の最適解
まず車建て優先で配車した場合のケースを考えてみましょう。
最小運賃の計算が簡単だからです。
卸3社からの受注数の合計は3,300箱です。
トラック1台につき1,500箱しか積載できませんので、最小でも3台は必要です。
また、工場だけですべての受注を賄うことができないため、運賃の安い工場発のトラックだけを3台チャーターすることもできません。
従って工場発を2台、DC発を1台チャーターするのが最も合計運賃が安くなります。
50,000円×2+65,000円=165,000円
ちなみに、DCと工場から1,500箱ずつをチャーター便(車建て運賃)で運び、残りの300箱を個建ての料金で運ぶという手もありますが、最低積載量の1,200箱に満たないためこの選択肢も使えません。
個建て優先で配車する場合の最適解
整数計画法に定式化
続いて、すべて個建てで運ぶ場合の最小運賃を計算します。
合計運賃が最小になるように、商品別/ルート別で運ぶ箱数を決める問題になりますので、決める変数を次のように定義します。
すると、これらの変数に個建ての料金を掛けて、合計運賃は次のように計算できます。
合計運賃=50xd1a+70xd1b+90xd1c+20xf1a+30xf1b+100xf1c+60xd2a+80xd2b
+100xd2c+30xf2a+40xf2b+110xf2c・・・①
一方、これらの変数には供給サイドで在庫数という制約が、また需要サイドで受注数という制約があり、それぞれ次式のように表すことができます。
在庫数の制約
xd1a+xd1b+xd1c≦1,000・・・②
xf1a+xf1b+xf1c≦2,000・・・③
xd2a+xd2b+xd2c≦1,000・・・④
xf2a+xf2b+xf2c≦2,000・・・⑤
受注量の制約
xd1a+xf1a=1,000・・・⑥
xd1b+xf1b=700・・・⑦
xd1c+xf1c=600・・・⑧
xd2a+xf2a=500・・・⑨
xd2b+xf2b=400・・・➉
xd2c+xf2c=100・・・⑪
また、トラック1台当たりの最低積載量は1,200箱という制約もありますので、DC発と工場発のトラックそれぞれについて次のような制約式が成り立ちます。
xd1a+xd1b+xd1c+xd2a+xd2b+xd2c ≧1,200・・・⑫
xf1a+xf1b+xf1c+xf2a+xf2b+xf2c ≧1,200・・・⑬
これで定式化できました。
式②~⑬を制約条件とし、式①を最小化するような最適化問題になりました。
更にこれらの式はすべて一次式になっていますので、線形計画法の問題です。
但し、変数である積載数量は整数という制約条件付きですので、厳密には整数計画法と言います。
整数計画法は線形計画法より解くのが難しいのですが、Excelのソルバー機能を使えば同じように解けてしまいます。
Excelのソルバーで最適解を求める
まずは下記のようにExcelシートに表を作ります。

続いてデータ⇒ソルバーをクリックしソルバー画面を開いて、下記のように目的関数と制約条件を入力します。

後は、「解決」ボタン(英語バージョンではSolveボタン)をクリックすれば1秒で計算してくれます。
結果はこのようになりました。

図で書くと次のようになります。
在庫管理面からの考察
倉庫コストも考慮すべき
このように毎日の受注数量を見ながら、DCから出荷するか工場から出荷するかを毎日判断すれば、輸送コストは最小化できます。
しかし、物流コストは輸送コストだけではありません。
倉庫コストもあります。
そして倉庫コストは在庫数量に左右されます。
適正在庫管理をするという観点では、上記のような方法は適切でしょうか?
適正在庫は下図にように安全在庫と需要予測在庫に分けられます。
このうち、安全在庫は日々の需要のばらつきの大きさに左右され、需要予測在庫は需要予測精度に左右されます。
需要予測精度が下がり適正在庫管理ができなくなる
そこで、先の例のようなトラックの運用をしていたらどうなるでしょうか?
日によってDCから出荷したり工場から出荷したりしていては、DCから出荷される需要が予測できませんね。
勿論、それだけ需要のばらつきも大きくなります。
つまり、適正在庫量が大きくなります。
これによる倉庫コストへの影響は、先の輸送コスト計算では考慮されていません。
またこの方法では前日に工場から出荷した商品を、次の日にはDCから送ることになるかもしれません。
そうすると日付の逆転も起こる可能性が高く、食品や医薬品ではこれは致命的です。
また先の例では、卸aへは商品1、2共にDCと工場の両方から同じ日に出荷しています。
これによっても、日付逆転が起こる可能性は高いでしょう。
このように部分最適を追い求めるために全体最適がないがしろにされ、物流コストの上昇につながっているケースは多くの会社で見られます。
このような数理最適化による改善の芽は至るところに転がっています。
Udemyの関連講座
Optimization with Excel: Operations Research without Coding
Optimization with Gurobi, CBC, IPOPT. Linear programming, nonlinear, genetic algorithm. Using Excel, without coding
Assignment and Transportation Problem Operations Research 01
The Hungarian Assignment Problem and Transportation Problem
Optimization with Python: Solve Operations Research Problems
Solve optimization problems with CPLEX, Gurobi, Pyomo… using linear programming, nonlinear, evolutionary algorithms…
業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!