2017/2/27 ロジスティクス・ネットワーク 最適化 東京海洋大学 久保　幹雄.

Presentation on theme: "2017/2/27 ロジスティクス・ネットワーク 最適化 東京海洋大学 久保　幹雄."— Presentation transcript:

1 2017/2/27 ロジスティクス・ネットワーク 最適化 東京海洋大学 久保　幹雄

2 意思決定レベルによる分類 生産 需要 原材料 配送拠点 輸送 配送 地点 ロジスティクス・ネットワーク最適化 長期 中期 短期 調達物流
2017/2/27 意思決定レベルによる分類 原材料 調達物流 生産 工場内物流 輸送 配送拠点 配送 需要 地点 ロジスティクス・ネットワーク最適化 ストラテジック 長期　　中期　　短期 資源配分最適化 安全在庫配置 在庫方策最適化 生産計画最適化 ロットサイズ最適化 スケジューリング最適化 配送計画最適化 配送計画 では，まず前回の復習から入りましょう．たしか，ロジスティクスにおける意思決定のためには， 意思決定とレベルを意識することが重要でしたよね？ タクティカル オペレーショナル

3 ロジスティクス・ネットワーク設計 サプライ・チェイン全体を通したストラテジック（戦略的）な意思決定 例
2017/2/27 ロジスティクス・ネットワーク設計 サプライ・チェイン全体を通したストラテジック（戦略的）な意思決定 例 どこから原材料（もしくは部品）を調達するか，どの工場のどの生産ラインで生産するか どの地点からどの地点にどのような輸送手段（モード）で輸送を行うか どこに工場もしくは倉庫を新設するか（もしくは移転するか，閉鎖するか） 今日のテーマはロジスティクス・ネットワークの最適設計ということですが，これはどんな問題なんですか？ （久保） ロジスティクス・ネットワーク設計の目標は，サプライ・チェイン全体を通したストラテジックな意思決定を包括的に支援することです． ストラテジックレベルの意思決定には，どこから原材料や部品を調達するか，どの工場のどの生産ラインで生産するか， どの地点からどの地点にどのような輸送モードで輸送を行うか， どのような生産方式で生産を行うか，どこに工場もしくは倉庫を新設するか（もしくは移転するか，閉鎖するか）などがあります．これらの意思決定を，1年以上，数年から数十年のスパンで計画するのが， ロジスティクス・ネットワーク設計の目的です．

4 ロジスティクス・ネットワーク最適化 ストラテジック（長期）レベルの意思決定 ロジスティクス・ネットワーク全体の最適設計
継続期間が比較的長い調達活動の是非の決定 活動の位置的な情報を決定（生産をどこで行うか，製品資源のフロー） グローバル・ロジスティクス（関税，関税控除，移転価格） （為替，需要などの）不確実性 リバース・ロジスティクス 温室化ガス排出量 サプライ・チェイン途絶に 対するリスク管理

5 施設配置問題 ORの古典：１９５７年のKoopmansの本 “ Three Essays on the State of Economic Science” 需要地点 供給地点

6 2017/2/27 施設配置問題 需要地点の重心！？ Weber (1929)

7 ロジスティクス・ネットワーク最適化

8 ロジスティクスネットワーク最適化における主な意思決定項目
各製品を，どこで（どの工場のどの製造ラインで）どれだけ製造するか? 各製品をどの中継拠点で保管するか? 各製品をどのような輸送手段（モード）で輸送するか? 各顧客の各製品の需要をどの配送センターから運ぶか? 中継拠点をどこに新設（移転，閉鎖）するか? （新製品投入や顧客の需要の変化に対応するために）どこに工場を新設(移転，閉鎖)するか? どのような製造ラインをどこに新設(移転，閉鎖)するか?

9 混合整数計画＋凹費用 (区分的線形近似）最適化
2017/2/27 混合整数計画＋凹費用 (区分的線形近似）最適化 安全在庫費用 The LND model can be formulated as a multi-commodity network flow model. Supply chain or logistics network is modeled as a network composed of nodes and arcs. The raw materials, parts, intermediates, final products or items are modeled as commodities or flow through the network. We have to model the bill-of-material (BOM) or recipe structure that represents the relationship between the items. That means which product is composed of which parts or raw materials. We also incorporate the safety inventory cost into the model that is a concave function of the flow volume through the arc. Usually, the concave cost minimization problem is difficult; it is called NP-hard. That means it’s probably impossible to find an efficient algorithm to solve it in general. But by using approximation of concave functions, the LND problem can be formulated as a mixed integer programming problem and can be solved by standard MIP solvers (here MIP means mixed integer programming) such as CPLEX, Xpress-MP, they are commercial solvers, or GLPK, SCIP, they are free solvers. J I

10 施設配置問題の 混合整数計画定式化 工場から顧客への輸送費用 工場の固定費用 =1 工場開設, =0 それ以外 工場から顧客への輸送量
2017/2/27 施設配置問題の 混合整数計画定式化 工場から顧客への輸送費用 工場の固定費用 Because the MIP formulation of the LND problem is too complicated, I’ll show you a simpler model named the simple facility location problem that is a sub-model of the LND problem. We are given two sets I and J where “I” represents the set of customers and “J” represents the set of plants. Each customer demand is scaled to 1 and must be satisfied. Each plant has a fixed cost f_j that is incurred when it is open. We also need a transportation cost c_{ij} from plant j to customer i. We use two variables, x and y. x represents the flow volume from plant to customer, while y is a binary variable that represents the open or close decision of the plant. The objective function to be minimized is the sum of the fixed and transportation costs. The first constraint means that every customer demand must be satisfied. The second constraint forces the plant to be open if some products are shipped from the plant. By using a MIP solver, we can solve this problem easily if the problem size is not so large. If the problem is too large to be solved by your MIP solver, you can use specialized algorithms such as Lagrangean relaxation or Benders decomposition. But both are beyond the scope of this lecture. =1 工場開設, =0 それ以外 工場から顧客への輸送量

11 2017/2/27 適用例 吸収・合併後のネットワーク再編成 Baxter Healthcare +American Hospital Supply (1985) （今のAllegiance Healthcare） 新製品投入時の意思決定 Pet +Progresso (食品） (1984)，NABISCO ロジスティクスにおける戦略的提携 Kodak + Sterling Winthrop +Sanofi グローバルネットワークの再編成 Deital Equipment Corporation (DEC) リサイクリングネットワーク設計（リバース・ロジスティクス） Eastman Kodak

12 Hunt-Wesson Food, Inc. の事例
Geoffrion-Gravesによる最初の適用事例 （１９７０年） 数百の製品群 14の工場 数十の流通センター（DC）を通して127の顧客群（ゾーン）へ 年間数百万ドルの費用の削減

13 Geoffrion-Gravesモデル どのDCを選択（新設，閉鎖，移転）するか?を決めるモデル 最小化
製造費用+輸送費用+DC設置固定費用+ DC稼働費用 条件 すべての顧客ゾーンの需要量は製品ごとに満たされる． 工場の製品ごとの製造量上限 （DCを稼働させた場合の）取り扱い量の上下限 各顧客ゾーンは1つのDCによってカバーされる． (option）

14 Geoffrion-Gravesモデルの概念図
顧客ゾーン（１２７） 流通センター（ＤＣ） の候補地点（数十） 工場（１４） 製品群（数百）

15 Brown-Graves-Honczarenko (NABISCO) モデル
工場内での施設の配置も同時に考慮したモデル（1980年） 最小化 製造費用+輸送費用+ 工場固定費用+ 施設固定費用 条件 すべての顧客ゾーンの需要量は製品ごとに満たされる． （施設を稼働させた場合の）取り扱い量の上下限 各施設はいずれかの工場に割り振られる． 各工場に割り振られる施設数の上下限

16 NSBISCOモデルの概念図 顧客ゾーン（１70） 工場（20） 製品（200） （１００） （２００） 施設１ （オーブン） 施設２
（包装） （１００） （２００）

17 ＣＩＭＰＥＬ (Computer Integrated Modeling and Planning Environment for Logistics)
Ｇｅｏｒｇｉａ Ｉｎｓｔｉｔｕｔｅ of Technologyで開発中 （１９９０年） 最小化 工場設置固定費用 + 工場内製造費用+工場内在庫費用 +DC設置固定費用 + DC内施設費用 + DC内在庫費用 + DC内加工費用 +輸送費用+輸送中の在庫費用 条件 すべての顧客ゾーンの需要量は製品ごとに満たされる 工場の製品ごとの製造量上限 DCでの取り扱い量の上下限 ，在庫量の上下限 DCの種類の選択 運搬車の数の上下限 ，運搬車の重量・容量制約 DCと顧客（ゾーン）への移動距離制約

18 CIMPELの概念図 多製品，多段階，多チャネルを考慮した統合ロジスティクスツール 在庫費用 複数の輸送モード 製造費用 積み替え費用

19 ＤＥＣの事例 Global Supply Chain再編成 手法：混合整数計画法 効果：年間1億$の費用削減 どこで何を生産し，どこへ運ぶか
2017/2/27 ＤＥＣの事例 DEC（Digital Equipment Corporation)（1995年） Global Supply Chain再編成 どこで何を生産し，どこへ運ぶか どの部品をアウトソーシングするか どのベンダーから調達するか 手法：混合整数計画法 効果：年間1億$の費用削減 Franz Edelman Award (1995) Interfaces 25 (1995) pp

20 ＧＳＣＭ （Global Supply Chain Model）の 概念図
2017/2/27 ＧＳＣＭ （Global Supply Chain Model）の 概念図 5.0％関税 ４．７％関税 ７．７％関税

21 ＤＥＣ モデルのデータ 各国における顧客位置，需要量，供給者の位置，供給量 各国での労働者の賃金（および供給可能な場所）
国家間の各輸送モード（航空機，トラック，船舶）での輸送費用（含保険料），輸送時間 税金回避地（tax heavens；Singapore, Puerto Rico, Ireland） 国家間の貿易取り決めおよび数値目標 グローバル部品展開図 関税および控除条件

22 （グローバル）部品展開図 顧客ゾーン シンガポール ニューヨーク ドイツ メキシコ 台湾 スペイン メキシコ イギリス 台湾 カナダ
マレーシア アイルランド ドイツ コロラド コロラド マレーシア アイルランド ドイツ イギリス マサチューセッツ 台湾 カナダ イギリス メキシコ 台湾 カナダ マサチューセッツ 日本 オランダ イギリス 日本 イタリア サウスカロライナ

23 関税控除条件 ブラジル 中国 台湾 ヨーロッパ そのまま 再輸出 付加価値のついた ものの再輸入 付加価値をつけて 再輸出
2017/2/27 関税控除条件 そのまま 再輸出 ブラジル 中国 台湾 ヨーロッパ 付加価値のついた ものの再輸入 付加価値をつけて 再輸出

24 ＤＥＣ （Digital Equipment Corporation) モデル
最小化 α[製造費用在庫費用+ 輸送費用+製造固定費用 + 工場固定費用 + 施設固定費用－関税控除・免除] + (1－α) [ 製造日数+ 輸送日数 ] 条件 顧客ゾーンの需要量は製品ごとに各期ごとに満たされる． 在庫，輸送，製造のバランス制約 組み立て前，組み立て後の製品数のバランス条件 （工場，施設の）取り扱い量の上下限 製造，在庫，輸送量の上下限 製造ライン（施設）数，工場数の上下限 国家ごとの貿易取り決め条件 関税控除，免除条件

25 DECの事例（改善前） ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール NewEnglandSites Ayr
Queensterry Hull Kantana Galway Cororado Augusta Clonmel Nijimegen NewEnglandSites WCVC Cupertino Hudson Westminster Shenzhen Tokyo Phenix Greenville Shrewsbury springfiled Boston India Westfield Mexico Taiwan Mariboro Franklin HongKong Andover PuetroRico Saiem Singapore Brazil Sydney ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール

26 DECの事例（改善後） ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール Ayr Queensterry Kantana
Cororado Augusta England Nijimegen WCVC Tokyo Albuquerque Greenville Mexico Taiwan HongKong Singapore Sydney ＝ロジスティクス・センター ＝チップ＆メディア ＝本体 ＝モジュール

27 プロジェクト実施の手順（１） 仮実験 構築したモデルおよび収集したデータの妥当性を確認するための予備的な実験（意思決定者の直感との整合性）
小規模最適化 一部の製品，地域，部門のみを対象とする． 全体最適化 すべての変数を意思決定の対象にして最適化を行う．

28 プロジェクト実施の手順（２） もしこうなったら分析
経営環境の仮想的な変化をWhat if... （もしこうなったら）型の問いをできるだけ多くすることによってモデルを様々な観点から適用する． もし（最適化によって閉鎖させられる）DCを開設することにしておいたらどうなるだろう? もしある顧客ゾーンへのサービスを（最適化によって得られたものと）異なるDCから行ったらどうなるだろう? もしある地点間の輸送費用が交渉によって下げられたらどうなるだろう? もしあるDCのリース費用が交渉によって下げられたらどうなるだろう?

29 プロジェクト実施の手順（３） 感度分析 トレードオフ分析 データを変化させたときの目的関数（総費用）の変化をみるために系統的な実験を行う．
過去のデータを用いた（時系列）感度分析 トレードオフ分析 ロジスティクス・システム全体の評価に必要な費用以外の要因（主なものではサービスレベル）とのトレードオフを調べる．

30 プロジェクト実施の手順（４） 優先順位分析 最適解と現状とのずれを，どのような順番で実施していくかを分析する．
例：ＤＣ (A)の移転，ＤＣ (B)の閉鎖，工場の閉鎖が最適 （１４億２千万円削減可能）と出たとき １．DCへの顧客の割り振りの変更 （１０億円削減） ２．DC (Ａ) の移転 （３億円削減） ３．工場の閉鎖 （１億円削減） ４．DC (Ｂ) の閉鎖（２千万円なので実施しない）

31 ロジスティクス・ネットワーク最適化の例 （施設のネットワークと製品群）

32 ロジスティクス・ネットワーク最適化の例（部品展開図と主要な工程）

33 ロジスティクス・ネットワーク最適化の例 （最適化後のネットワークと製品群フロー）

34 資源配分最適化 多期間ロジスティクス・ネットワーク設計
長期タクティカルレベルの意思決定，多期間を考慮 継続期間が中程度の調達活動の是非の決定 活動の位置的な情報を決定（生産をどこで行うか，製品資源のフロー） 工場内のMPS（Master Production System）をサプライ・チェイン全体に拡張 需要の季節変動，景気変動の考慮 製品ライフサイクルを考慮した（リバース）ロジスティクス・ネットワーク設計 収益管理（価格も決定変数） 製品の需要量 製品の回収量 再製造品の需要量 期（月）

35 資源配分最適化におけるトレードオフ 需要量 生産量上限（資源制約） 期 残業 生産量 生産量一定 在庫

36 2017/2/27 なぜ最適解が必要か？ 厳密解法 最適解を出す保証があるアルゴリズム ただし，難しい問題（NP-困難問題）の場合には時間がかかる（もしくは計算が終了しない）こともある． Bad News: サプライ・チェインのほとんどの問題はNP-困難 ヒューリスティクス（近似解法） 最適解の保証がないアルゴリズム ロジスティクス・ネットワーク設計の費用は膨大（0.1％の削減でも大きい）＋比較的解きやすい ->厳密解法を用いる

37 ヒューリスティクスがうまくいなかい例 2017/2/27

38 最も近い倉庫から補充する方法 2017/2/27

39 最も近い倉庫から補充する方法 2017/2/27 足りない分は 工場１から運ぶ

40 最も安い経路（工場-倉庫-顧客）を選択する方法
2017/2/27

41 最も安い経路（工場-倉庫-顧客）を選択する方法
2017/2/27

42 倉庫２から顧客３への輸送費用が半額のとき 2017/2/27 4万->2万 増えている！

43 さらに倉庫２から顧客１への輸送費用を5000円にしたとき
2017/2/27 2万->0.5万 さらに増えている！

44 2017/2/27 Excelソルバーによる求解 変化させるセル

45 Excelソルバーの設定（１） 2017/2/27 目的関数のセルを指定 工場の供給量上限 倉庫の入量=出量 需要は必ず満たす

46 2017/2/27 Excelソルバーの設定（２） 線形モデル， 非負数を仮定を チェックする！

47 感度レポートの解釈 双対変数の最適値のこと 工場2の生産量上限60000を１単位増やすと総費用が1減る
2017/2/27 感度レポートの解釈 双対変数の最適値のこと 工場2の生産量上限60000を１単位増やすと総費用が1減る 制約を90000まで増やすか，10000まで減らすと解が変わる

48 例題の最適解 2017/2/27

49 在庫の取り扱い 輸送中在庫：輸送時間，輸送量に依存：変動費用に含める． サイクル在庫：サイクル時間を与えることによる近似
2017/2/27 在庫の取り扱い 輸送中在庫：輸送時間，輸送量に依存：変動費用に含める． サイクル在庫：サイクル時間を与えることによる近似 作り置き在庫：多期間モデルで考慮 安全在庫：需要のばらつきを表す変動比率を与えることによって近似 輸送中在庫は，サプライ・チェイン内を品目が移動しているときに必然的に発生する在庫です．これは輸送時間と輸送量によって決まるので，変動費用に含めて考えます． サイクル在庫とは，輸送や生産が定期的に行われているときに発生する在庫です． 作り置き在庫は，季節変動をもつ需要に対して，限られた資源で対応するために発生する在庫です．これは多期間モデルで考慮することができます． 安全在庫は，需要の不確実性に対処するために保持する在庫です．

50 輸送中在庫費用 2017/2/27 ３０日 １日 変動費用に，１日・１品目あたりの在庫費用×輸送日数を加える．

51 2017/2/27 サイクル在庫 固定

52 サイクル在庫費用と 輸送頻度のトレードオフ
2017/2/27 サイクル在庫費用と 輸送頻度のトレードオフ サイクル在庫　大 サイクル在庫　小 ３日一度 毎日 サイクル在庫費用＝エシェロン在庫費用×サイクル時間/2

53 2017/2/27 作り置き在庫と残業のトレードオフ 需要量 生産量上限（資源制約） 期 残業 生産量 生産量一定 在庫

54 2017/2/27 安全在庫量の計算 を導入（品目ごとに同一と仮定） なので

55 ロジスティクス・ネットワーク最適化 （意思決定支援）システム
2017/2/27 ロジスティクス・ネットワーク最適化 （意思決定支援）システム　 点データ　 資源データ 品目データ 枝データ 期データ　 点・品目データ 枝・資源データ 品目・資源データ 品目対データ 枝・品目・資源データ 枝・品目・資源・期データ パラメータデータ 最適ネットワーク 戦略/戦術的 意思決定 最適在庫配置 在庫方策 ユーザーとの対話 (what if 分析, シナリオ分析)

56 まとめ 施設の立地問題 ロジスティクス・ネットワーク設計問題 ヒューリスティクスの危険性 多期間モデル 複雑な費用の表現法
2017/2/27 まとめ 施設の立地問題 ロジスティクス・ネットワーク設計問題 ヒューリスティクスの危険性 多期間モデル 複雑な費用の表現法 意思決定支援システム