配送計画と収益管理 東京海洋大学 久保 幹雄 1 意思決定レベルによる分類 原材料 長 期 調達物流 ストラテジック 生産 工場内物流 輸送 配送拠点 配送 需要 地点 ロジスティクス・ネットワーク最適化 資源配分最適化 中 期 短 期 タクティカル オペレーショナル 安全在庫配置 在庫方策最適化 生産計画最適化 配送計画最適化 ロットサイズ最適化 スケジューリング最適化 配送計画 2 配送計画とは？ サプライ・チェインの最下流における最適化 タクティカル（中期）からオペレーショナル（短期） の意思決定 配送センターから複数の顧客（小売店，港など） への輸送手段（トラック，船など）による巡回輸送 の最適化 我が国で最も普及しているサプライ・チェイン最 適化システム 3 配送計画の目的と制約 総費用最小化 ルート内の顧客需 要量がトラックの 積載重量（容量） の上限以下 一日の稼働時間の 上限を超えない 時間枠を満たす 入庫可能トラック の制限 顧客(需要点) デポ ルート 4 配送計画の歴史１ 1950年以前（経済からロジスティクスへ) Kantrovitch, Koopmansの輸送モデル Dantzigの線形計画 1950-60 (黎明期) Dantzig & Ramserのタンカースケジュール Dantzig, Fulkerson & Johnsonの巡回セール スマン問題 5 配送計画の歴史２ 1960-80（初期の近似解法) Clarke & Wrightのセービング法 Gillet & Millerのスイープ法 1980-90 (近似解法の洗練と事例期) Fisher & Jaikumarの一般化割当法 航空機（人員）スケジューリングへの応用 多くの事例研究 (地理的データーベースの普及) 1990-2000 (メタ解法の発展) タブー（禁断）探索，遺伝的アルゴリズムなど 2000-現在（普及と他のサプライ・チェイン最適 化システムとの融合） ベンダー管理在庫 6 配送計画の分類 輸送計画 1台の車が1箇所を経由 トレーラー型配送計画 2から5箇所を経由 （標準型）配送計画 6から100箇所を巡回 巡回セールスマン型配送計画 数百箇所を巡回 トレーラー型配送計画 工場・倉庫間 タンクローリ，トレーラ 飛行機の空路・人員スケジューリング 集合分割アプローチが有効！ 特徴：付加条件が付くほど)易しい 集合分割アプローチ（１） ２ １ デポ ３ ５ ４ 費用 ５ 顧客１ 顧客２ 顧客３ 顧客４ 顧客５ １ １ １ ０ ０ 集合分割アプローチ（２） ２ １ デポ ３ ５ ４ 費用 ５６ 顧客１ 顧客２ 顧客３ 顧客４ 顧客５ １０ １１ １１ ０１ ００ 集合分割アプローチ（３） ２ １ デポ ３ ５ ４ 費用 ５６４ 顧客１ 顧客２ 顧客３ 顧客４ 顧客５ １００ １１０ １１０ ０１１ ００１ 集合分割アプローチ（４） ２ １ デポ ３ ５ ４ 費用 ５６４６３３５ 顧客１ 顧客２ 顧客３ 顧客４ 顧客５ １００１１０１ １１０１０００ １１０００１１ ・・・ ０１１００１０ ００１１１００ 集合分割アプローチ（５） ２ １ デポ ３ ５ ４ 費用 ５６４６３４５ 顧客１ 顧客２ 顧客３ 顧客４ 顧客５ １００１１０１ １１０１０００ １１０００１１ ・・・ ０１１００１０ ００１１１００ 成功事例 モービルオイル社 （1987年) Brown & Gravesら 軽油のタンクローリーによる輸送 手法：整数計画＋ヒューリスティック 効果：年間３００万＄の削減 1987年度 Franz Edelman Award Interfaces (1987) 17 pp.107-120 成功事例 Flying Tiger Line, Pacific Sothwest Airways, Continental Airlines, Helsinki City Transport （１９８１ 年） Marstenら 手法：航空貨物運搬スケジューリング問題 に対する集合分割アプローチ 効果：年間300,000$の費用削減 Networks 11 (1981) pp. 165-177 標準型配送計画 構築法 セービング法(Clarke & Wright法) クラスター先・ルート後法 スイープ法(Gillet & Miller法) 一般化割当法 メタ解法(ヒューリスティック) ニューラルネット 遺伝的アルゴリズム シミュレーテッドアニーリング法 禁断探索法(タブーサーチ) セービング法 (Clarke & Wright) ー ＋ ＋ デポ デポ IBMがVSPとして売り出したため有名になった！ セービング法の解の例 OR Lib. の199顧客問題 重量，稼動時間条件付き ２０台 総距離 １７０６ 弱点： 横広がりのルートを形成 巡回セールスマン型配送計画 クラスター先・ルート後法 地図(領域)を分割し，それから巡回路を作る 方法 ルート先・クラスター後法 全ての顧客を通る巡回路を作成し，それから ルートに分割する方法 難しいが厳密に解く必要性は減少する 巡回セールスマン問題 全ての点をちょうど一回経由 する最短経路を求める問題 古典的な最適化問題 点数が増えると難しい 巡回セールスマン問題 Aberdeen Belfast Edinburgh Liverpool Dublin Cardiff London 巡回セールスマン問題 Aberdeen Belfast Edinburgh Liverpool Dublin Cardiff London 巡回セールスマン問題 応用 基盤配線，配送計画，スケジューリング，基盤 穿孔，Ｘ線構造解析実験，タンパク質構造解 析，ＤＮA 並べ替え，ＶＬＳＩ設計, etc. 問題集(TSPLIB)あり． クラスター先・ルート後法 (スイープ法: Gillet & Miller） デポ クラスター先・ルート後法（スイー プ法） デポ スイープ法の弱点 稼動時間の上限や時間枠などの時間的要 因を陽的には組み込めない クラスター先・ルート後法の根本的弱点 細長いルートを形成しがち トラックの重量，容量条件がきついと解が 極端に悪化 クラスター先・ルート後法 (一般化割当法: Fisher & Jaikumar） + - + デポ Seed Point クラスター先・ルート後法 (一般化割当法） 重量，容量 重量，容量 重量，容量 制約付きの割当 (一般化割当) クラスター先・ルート後法 (一般化割当法） デポ 一般化割当法の弱点と利点 弱点 一般化割当問題自身が困難な問題である 利点 クラスター先・ルート後法 指定したトラックでの実行可能解を算出 一般化割当法の解の例 １８台 総距離 １４９２ 時間の超過 ２４３ ルート先・クラスター後法 デポ ルート先・クラスター後法 デポ Tabu Search (禁断探索法) 人間の記憶過程にアナロジーを持つ． 別名 最急上昇・最緩下降法 (steepest ascent mildest descent method) 適応型記憶計画(adaptive memory programming) 同じ場所を巡回しないように，記憶を頼りに，常 に最も高い方向(下りの場合は最も勾配の緩や かな方向)を目指す． 禁断探索法（タブーサーチ）の解 １８台 総距離 １３６４ 配送計画問題に対する解法の歴史 近似解法 Genetic Algorithm Local Search Tabu Search Simulated Annealing 一般化割当法 構築法 (Saving, Insertion) 下界導出 1960 AMP (Adaptive Memory Programming) Location Based Heuristic ルート選択 Ｈｅｕｒｉｓｔｉｃ GRASP (Greedy Randomized Adaptive Search Procedure) Set Partitioning Approach State Space Relax. Cutting Plane K-Tree Relax. 1970 1980 1990 階層的 積木法 成功事例 デュポン （１９８２年） Fisher ら 手法：一般化割当法 効果：配送費用の１５％削減 Interfaces (1982) 16 pp. 18-23 成功事例 Air Product & Chemical社 （１９８３ 年） Bellら 手法：集合分割アプローチ 効果：配送費用の６から１０％削減 Interfaces (1983) 11 pp. 4-23 成功事例 コカコーラ他４件の清涼飲料水会社 （１９８ ７年） Golden ら (Maryland大学) 手法： 主に構築法 ROADNET (ROADNET Systems Corp.100,000$-200,000$), TRUCKSTOPS (Booz,Allen & Hamilton), MICRO VEH PLAN 効果：配送費用の１０％削減 Operations Research (1987) 35 pp. 6-17 成功事例 ボランティアによる食事の配達 （１９８３ 年） Bartholdi & Platzman (Georgia Tec.) 手法：ルート先・クラスター後法 効果：配送費用の１３％削減 特徴：導入費用が安価 Interfaces (1983) 13 pp. 1-8 成功事例 Suiker Unie (オランダ生協)(1992年) ORTEC Consultants 手法：時間枠付き配送計画問題に対する 対話型スケジューリングシステム (SHORTREC Package) 効果：配送費用の７％削減 Interfaces (1992) 22 pp. 4-14 成功事例 Southern California Gas Company (1988 年) Bodinら (Maryland大学) 手法：ガスの検針スケジューリング問題に 対する枝巡回法(SOCAL Package) 効果：年間 874,185$以上の削減 Interfaces (1992) 22 pp. 22-30 成功事例 西アフリカの黒蠅駆除 (1992年) Solomonら (Northeastern大学) 手法：ヘリコプターの巡回順決定に対する 配送計画スケジューリング手法の適用 効果：年間 100,000$の削減 Interfaces (1992) 22 pp. 88-99 成功事例 ナイジェリア：モービル石油の油田巡回 (1992年) Pulletblank (IBM, Thomas Watson研) 手法：先行順序を持つヘリコプターの巡回 順決定に対する近似アプローチ 効果：年間 500,000$の削減 Interfaces (1992) 22 pp. 100-111 成功事例 スイスの食料品配送計画（1993年） Semet & Taillard 手法：タブーサーチ 効果：現行法の一般化割当法に比べて１ ６％の費用削減 Ann. OR (1993) 41 pp. 421-451 実用化のための付加条件 時間枠指定 (何時から何時までに) 積み込み・積み降ろしの考慮 帰り便 (Backhauling) の考慮 複数のデポ 在庫計画との融合 工程計画との融合 不確実性の考慮，etc. 稼働時間（距離）制約 デポ １つのルートの 総距離（稼働時間） が一定値以下 積み込み・積み降ろしの 同時考慮 デポ 帰り荷（backhaul）は特殊形 複数デポ 異なる種類の運搬車 デポ ４トン車以下でないと入れない顧客 回転（運搬車ルート）の考慮 デポ ＋昼食時間 時間枠（時刻指定）の考慮 [12:30,6:30] [1:30,2:00] デポ 11:00ちょうど [3:30,4:30] 配送計画最適化システム 実務的な拡張 • 複数デポ • 積み込み・積み降ろし • 回転 •異なる運搬車 •時間枠 53 penalty ソフト時間枠 ペナルティ関数 pi (t ) t 時間枠 ペナルティ関数（区分的線形関数） （非凸でも非連続でもＯＫ） 54 多期間モデル 週に２回｛（月，木），（火，金），（水，土）｝ 月 火 週に３回｛（月，水，金），（火，木，土）｝ 水 在庫配送計画(事例） (VMI: Vender Managed Inventory) 30日間の多期間モデル 総費用４０％減，品切れ数1/5 ・・・ １ ２ ３ ４ ５ 56 顧客の荷の分割の考慮 時間依存の移動時間 [8:00前] ２時間 [8:00-9:00] 1.5時間 [9:00-12:00] 1時間 デポ 不確実性の考慮 顧客の需要量 ？ 移動時間 ？ デポ 応用事例 協力ゲームの理論を用いて顧客の費用分 担を計算する機能 この機能を用いた事例 某メーカー (収集と配送の同時考慮) 年間３億６千万円の削減 （現状の３４．４％削減） 国内の事例 トラック４種類 重量，容量の同時考慮 収益管理（Revenue Management）とは？ 陳腐化資産（ある時刻になると価値が０） 航空機の座席，ホテルの部屋，ゴルフのプレー権，レンタ カー，スポーツの観戦券 価格の変更による需要の適切な管理(収益最大化) 価格帯の異なる予約の販売をいつ停止するかを決 定する． 最近では，インターネット直販における動的な価格 の変更戦略にも利用されている． 62 ホテルの部屋に対する収益管理 宿泊 在庫 割引価格 停止 正規価格10000円 価格 正規価格の 0.6倍の価格 割引価格6000円 在庫切れ（満室）の確率＝0.6 割引価格6000=正規価格×0.6（期待収益） 63 期 収益管理の分類 価格固定 価格可変 映画のチケット ホテルの部屋 期間予測可能 スポーツ観戦券 航空機の座席 宴会場 レンタカー クルーズ レストラン 介護サービス 期間予測不能 ゴルフコース 病院 =>現状：理論体系はほぼ完成，日本国内では不調 64 動的価格付け 商品の価格を動的に変更 （単なる割引セールとは異なる．） 陳腐化資産に限定しない インターネットを用いた直販（E-Business）により 注目 製造・輸送などの資源制約を考慮 収益最大化だけでなく，需要や生産の変動を削 減 => サプライ・チェイン最適化の拡張 65 動的価格付け（従来研究） Whitin (1955) : 経済発注量モデルの拡張 Thomas (1970): 動的ロットサイズ決定モデル の拡張 Chan, Shen, Simchi-Levi and Swann (2004): 確率的在庫モデルの拡張（サーベイ） Swann (2004): ケーススタディ（GMの事例）； 線形・独立な需要・価格関数を用いた多期間 生産・在庫モデル 66 GMの年間販売台数の推移 “Employee Discount for Everyone” campaign (2005, June) 6,000,000 5,000,000 4,000,000 3,000,000 2,000,000 1,000,000 0 1998 2000 2002 2004 年度 2006 2008 2010 67 動的価格付けの適用例 価格を変化させることによって需要をコントロール 独立でない価格-需要関数のモデル化（消費者選択モデル） 需要量 （価格一定） 価格 在庫曲線 新製品の顧客？ 自社の他製品？ 需要量 （価格制御） 需要の増加は 他社の顧客？ 期 価格 新製品 投入 期 在庫曲線 68 動的価格付けの実際 需要・価格関数の予測は困難（人間の行 動モデルの難しさ） サプライ・チェイン最適化をサブルーチンと したWhat If 分析 Supply Chain Modeling Language (SCML) 価格変更に伴う ロジスティクス・ネットワーク設計 需要変化のシナリオ 在庫最適化 配送計画 生産スケジューリング 69 まとめ 配送計画，収益管理 サプライ・チェイン最適化の20年以上の橋渡し 多くの課題 例：ロジスティクス・ネットワーク設計＋収益管理 サプライ・チェイン・リスク管理 人道支援ロジスティクス（サプライ・チェイン） 実務家 研究者 70
© Copyright 2024 ExpyDoc
