2017/3/3 配送計画と収益管理 東京海洋大学 久保　幹雄

意思決定レベルによる分類 配送計画 生産 需要 原材料 配送拠点 輸送 配送 地点 ロジスティクス・ネットワーク最適化 長期 中期 短期 2017/3/3 意思決定レベルによる分類 原材料 調達物流 生産 工場内物流 輸送 配送拠点 配送 需要 地点 ロジスティクス・ネットワーク最適化 ストラテジック 長期　　中期　　短期 資源配分最適化 安全在庫配置 在庫方策最適化 生産計画最適化 ロットサイズ最適化 スケジューリング最適化 配送計画最適化 配送計画 タクティカル オペレーショナル

配送計画とは？ サプライ・チェインの最下流における最適化 タクティカル（中期）からオペレーショナル（短期）の意思決定 2017/3/3 配送計画とは？ サプライ・チェインの最下流における最適化 タクティカル（中期）からオペレーショナル（短期）の意思決定 配送センターから複数の顧客（小売店，港など）への輸送手段（トラック，船など）による巡回輸送の最適化 我が国で最も普及しているサプライ・チェイン最適化システム

配送計画の目的と制約 総費用最小化 ルート内の顧客需要量がトラックの積載重量（容量）の上限以下 一日の稼働時間の上限を超えない 2017/3/3 配送計画の目的と制約 総費用最小化 ルート内の顧客需要量がトラックの積載重量（容量）の上限以下 一日の稼働時間の上限を超えない 時間枠を満たす 入庫可能トラックの制限 デポ 顧客(需要点) ルート

配送計画の歴史１ 1950年以前（経済からロジスティクスへ) 1950-60 (黎明期) 2017/3/3 配送計画の歴史１ 1950年以前（経済からロジスティクスへ) Kantrovitch, Koopmansの輸送モデル Dantzigの線形計画 1950-60 (黎明期) Dantzig & Ramserのタンカースケジュール Dantzig, Fulkerson & Johnsonの巡回セールスマン問題

配送計画の歴史２ 1960-80（初期の近似解法) 1980-90 (近似解法の洗練と事例期) 1990-2000 (メタ解法の発展) 2017/3/3 配送計画の歴史２ 1960-80（初期の近似解法) Clarke & Wrightのセービング法 Gillet & Millerのスイープ法 1980-90 (近似解法の洗練と事例期) Fisher & Jaikumarの一般化割当法 航空機（人員）スケジューリングへの応用 多くの事例研究 (地理的データーベースの普及) 1990-2000 (メタ解法の発展) タブー（禁断）探索，遺伝的アルゴリズムなど 2000-現在（普及と他のサプライ・チェイン最適化システムとの融合） ベンダー管理在庫

配送計画の分類 輸送計画 1台の車が1箇所を経由 トレーラー型配送計画 2から5箇所を経由 （標準型）配送計画 6から100箇所を巡回 2017/3/3 配送計画の分類 輸送計画 1台の車が1箇所を経由 トレーラー型配送計画 2から5箇所を経由 （標準型）配送計画 6から100箇所を巡回 巡回セールスマン型配送計画 数百箇所を巡回

トレーラー型配送計画 工場・倉庫間 タンクローリ，トレーラ 飛行機の空路・人員スケジューリング 集合分割アプローチが有効！ 特徴：付加条件が付くほど)易しい

2017/3/3 集合分割アプローチ（１） 費用　　５ 顧客１　１ 顧客２　１ 顧客３　１ 顧客４　０ 顧客５　０ ２ １ デポ ３ ５ ４

集合分割アプローチ（２） 費用 ５６ ２ 顧客１ １０ １ 顧客２ １１ 顧客３ １１ 顧客４ ０１ 顧客５ ００ デポ ３ ５ ４ 2017/3/3 集合分割アプローチ（２） 費用　　５６ 顧客１　１０ 顧客２　１１ 顧客３　１１ 顧客４　０１ 顧客５　００ ２ １ デポ ３ ５ ４

集合分割アプローチ（３） 費用 ５６４ ２ 顧客１ １００ １ 顧客２ １１０ 顧客３ １１０ 顧客４ ０１１ 顧客５ ００１ デポ ３ ５ 2017/3/3 集合分割アプローチ（３） 費用　　５６４　 顧客１　１００ 顧客２　１１０ 顧客３　１１０ 顧客４　０１１ 顧客５　００１ ２ １ デポ ３ ５ ４

2017/3/3 集合分割アプローチ（４） 費用　　５６４６３３５ 顧客１　１００１１０１ 顧客２　１１０１０００ 顧客３　１１０００１１ 顧客４　０１１００１０ 顧客５　００１１１００ ２ １ デポ ・・・ ３ ５ ４

2017/3/3 集合分割アプローチ（５） 費用　　５６４６３４５ 顧客１　１００１１０１ 顧客２　１１０１０００ 顧客３　１１０００１１ 顧客４　０１１００１０ 顧客５　００１１１００ ２ １ デポ ・・・ ３ ５ ４

成功事例 モービルオイル社 （1987年) Brown & Gravesら 軽油のタンクローリーによる輸送 2017/3/3 成功事例 モービルオイル社 （1987年) Brown & Gravesら 軽油のタンクローリーによる輸送 手法：整数計画＋ヒューリスティック 効果：年間３００万＄の削減 1987年度 Franz Edelman Award Interfaces (1987) 17 pp.107-120

2017/3/3 成功事例 Flying Tiger Line, Pacific Sothwest Airways, Continental Airlines, Helsinki City Transport （１９８１年） Marstenら 手法：航空貨物運搬スケジューリング問題に対する集合分割アプローチ 効果：年間300,000$の費用削減 Networks 11 (1981) pp. 165-177

標準型配送計画 禁断探索法(タブーサーチ) 構築法 セービング法(Clarke & Wright法) クラスター先・ルート後法 2017/3/3 標準型配送計画 構築法 セービング法(Clarke & Wright法) クラスター先・ルート後法 スイープ法(Gillet & Miller法) 一般化割当法 メタ解法(ヒューリスティック) ニューラルネット 遺伝的アルゴリズム シミュレーテッドアニーリング法 禁断探索法(タブーサーチ)

セービング法 (Clarke & Wright) ＋ ＋ デポ デポ IBMがVSPとして売り出したため有名になった！

セービング法の解の例 OR Lib. の199顧客問題 重量，稼動時間条件付き ２０台 総距離　１７０６ 弱点： 横広がりのルートを形成

巡回セールスマン型配送計画 クラスター先・ルート後法 ルート先・クラスター後法 難しいが厳密に解く必要性は減少する 2017/3/3 巡回セールスマン型配送計画 クラスター先・ルート後法 地図(領域)を分割し，それから巡回路を作る方法 ルート先・クラスター後法 全ての顧客を通る巡回路を作成し，それからルートに分割する方法 難しいが厳密に解く必要性は減少する

巡回セールスマン問題 全ての点をちょうど一回経由 する最短経路を求める問題 古典的な最適化問題 点数が増えると難しい

巡回セールスマン問題 Aberdeen Edinburgh Belfast Liverpool Dublin Cardiff London

巡回セールスマン問題 Aberdeen Edinburgh Belfast Liverpool Dublin Cardiff London

巡回セールスマン問題 応用 問題集(TSPLIB)あり． 2017/3/3 巡回セールスマン問題 応用 基盤配線，配送計画，スケジューリング，基盤穿孔，Ｘ線構造解析実験，タンパク質構造解析，ＤＮA 並べ替え，ＶＬＳＩ設計, etc. 問題集(TSPLIB)あり．

クラスター先・ルート後法 (スイープ法: Gillet & Miller） デポ

クラスター先・ルート後法（スイープ法） デポ

スイープ法の弱点 稼動時間の上限や時間枠などの時間的要因を陽的には組み込めない 細長いルートを形成しがち 2017/3/3 スイープ法の弱点 稼動時間の上限や時間枠などの時間的要因を陽的には組み込めない クラスター先・ルート後法の根本的弱点 細長いルートを形成しがち トラックの重量，容量条件がきついと解が極端に悪化

クラスター先・ルート後法 (一般化割当法: Fisher & Jaikumar） + - + デポ Seed Point

クラスター先・ルート後法 (一般化割当法） 制約付きの割当 (一般化割当) 重量，容量 重量，容量 重量，容量

クラスター先・ルート後法 (一般化割当法） デポ

一般化割当法の弱点と利点 弱点 利点 一般化割当問題自身が困難な問題である クラスター先・ルート後法 指定したトラックでの実行可能解を算出 2017/3/3 一般化割当法の弱点と利点 弱点 一般化割当問題自身が困難な問題である 利点 クラスター先・ルート後法 指定したトラックでの実行可能解を算出

一般化割当法の解の例 １８台 総距離　　１４９２　 時間の超過　２４３

ルート先・クラスター後法 デポ

ルート先・クラスター後法 デポ

Tabu Search (禁断探索法) 人間の記憶過程にアナロジーを持つ． 別名 2017/3/3 Tabu Search (禁断探索法) 人間の記憶過程にアナロジーを持つ． 別名 最急上昇・最緩下降法 (steepest ascent mildest descent method) 適応型記憶計画(adaptive memory programming) 同じ場所を巡回しないように，記憶を頼りに，常に最も高い方向(下りの場合は最も勾配の緩やかな方向)を目指す．

禁断探索法（タブーサーチ）の解 １８台 総距離　１３６４

配送計画問題に対する解法の歴史 近似解法 AMP Tabu Search Local Search 一般化割当法 GRASP 構築法 Genetic Algorithm AMP (Adaptive Memory Programming) Tabu Search Local Search Simulated Annealing Location Based Heuristic ルート選択 Ｈｅｕｒｉｓｔｉｃ 一般化割当法 GRASP (Greedy Randomized Adaptive Search Procedure) 構築法 (Saving, Insertion) 階層的 積木法 下界導出 Set Partitioning Approach State Space Relax. Cutting Plane K-Tree Relax. 1960 1970 1980 1990

成功事例 デュポン （１９８２年） Fisher ら 手法：一般化割当法 効果：配送費用の１５％削減 2017/3/3 成功事例 デュポン （１９８２年） Fisher ら 手法：一般化割当法 効果：配送費用の１５％削減 Interfaces (1982) 16 pp. 18-23

成功事例 Air Product & Chemical社 （１９８３年） Bellら 手法：集合分割アプローチ 2017/3/3 成功事例 Air Product & Chemical社 　　　　（１９８３年） Bellら 手法：集合分割アプローチ 効果：配送費用の６から１０％削減 Interfaces (1983) 11 pp. 4-23

成功事例 コカコーラ他４件の清涼飲料水会社 （１９８７年） Golden ら (Maryland大学) 2017/3/3 成功事例 コカコーラ他４件の清涼飲料水会社 （１９８７年） 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.) 2017/3/3 成功事例 ボランティアによる食事の配達　　（１９８３年） Bartholdi & Platzman (Georgia Tec.) 手法：ルート先・クラスター後法 効果：配送費用の１３％削減 特徴：導入費用が安価 Interfaces (1983) 13 pp. 1-8

成功事例 Suiker Unie (オランダ生協)(1992年) ORTEC Consultants 2017/3/3 成功事例 Suiker Unie (オランダ生協)(1992年) ORTEC Consultants 手法：時間枠付き配送計画問題に対する対話型スケジューリングシステム (SHORTREC Package) 効果：配送費用の７％削減 Interfaces (1992) 22 pp. 4-14

成功事例 Southern California Gas Company (1988年) Bodinら (Maryland大学) 2017/3/3 成功事例 Southern California Gas Company (1988年) Bodinら (Maryland大学) 手法：ガスの検針スケジューリング問題に対する枝巡回法(SOCAL Package) 効果：年間 874,185$以上の削減 Interfaces (1992) 22 pp. 22-30

成功事例 西アフリカの黒蠅駆除 (1992年) Solomonら (Northeastern大学) 2017/3/3 成功事例 西アフリカの黒蠅駆除 (1992年) Solomonら (Northeastern大学) 手法：ヘリコプターの巡回順決定に対する配送計画スケジューリング手法の適用 効果：年間 100,000$の削減 Interfaces (1992) 22 pp. 88-99

成功事例 ナイジェリア：モービル石油の油田巡回 (1992年) Pulletblank (IBM, Thomas Watson研) 2017/3/3 成功事例 ナイジェリア：モービル石油の油田巡回 (1992年) Pulletblank (IBM, Thomas Watson研) 手法：先行順序を持つヘリコプターの巡回順決定に対する近似アプローチ 効果：年間 500,000$の削減 Interfaces (1992) 22 pp. 100-111

成功事例 スイスの食料品配送計画（1993年） Semet & Taillard 手法：タブーサーチ 効果：現行法の一般化割当法に比べて１６％の費用削減 Ann. OR (1993) 41 pp. 421-451

実用化のための付加条件 時間枠指定 (何時から何時までに) 積み込み・積み降ろしの考慮 帰り便 (Backhauling) の考慮 2017/3/3 実用化のための付加条件 時間枠指定 (何時から何時までに) 積み込み・積み降ろしの考慮 帰り便 (Backhauling) の考慮 複数のデポ 在庫計画との融合 工程計画との融合 不確実性の考慮，etc.

2017/3/3 稼働時間（距離）制約 デポ １つのルートの 総距離（稼働時間） が一定値以下

2017/3/3 積み込み・積み降ろしの 同時考慮 デポ 帰り荷（backhaul）は特殊形

2017/3/3 複数デポ

2017/3/3 異なる種類の運搬車 デポ ４トン車以下でないと入れない顧客

2017/3/3 回転（運搬車ルート）の考慮 デポ ＋昼食時間

時間枠（時刻指定）の考慮 [12:30,6:30] [1:30,2:00] デポ 11:00ちょうど [3:30,4:30] 2017/3/3 時間枠（時刻指定）の考慮 [12:30,6:30] [1:30,2:00] デポ 11:00ちょうど [3:30,4:30]

2017/3/3 配送計画最適化システム　 実務的な拡張 複数デポ 積み込み・積み降ろし 回転 異なる運搬車 時間枠

ソフト時間枠 penalty ペナルティ関数 時間枠 ペナルティ関数（区分的線形関数） （非凸でも非連続でもＯＫ）

2017/3/3 多期間モデル 週に２回｛（月，木），（火，金），（水，土）｝ 火 水 月 週に３回｛（月，水，金），（火，木，土）｝

在庫配送計画(事例） (VMI: Vender Managed Inventory) 30日間の多期間モデル 総費用４０％減，品切れ数1/5 ・・・ １ ２ ３ ４ ５

2017/3/3 顧客の荷の分割の考慮

2017/3/3 時間依存の移動時間 [8:00前] ２時間 [8:00-9:00] 1.5時間 [9:00-12:00] 1時間 デポ

2017/3/3 不確実性の考慮 顧客の需要量 　　　？ 移動時間 ？ デポ

応用事例 協力ゲームの理論を用いて顧客の費用分担を計算する機能 この機能を用いた事例 某メーカー (収集と配送の同時考慮) 2017/3/3 応用事例 協力ゲームの理論を用いて顧客の費用分担を計算する機能 この機能を用いた事例 某メーカー (収集と配送の同時考慮) 年間３億６千万円の削減 （現状の３４．４％削減）

国内の事例 トラック４種類 重量，容量の同時考慮

収益管理（Revenue Management）とは？ 2017/3/3 収益管理（Revenue Management）とは？ 陳腐化資産（ある時刻になると価値が０） 航空機の座席，ホテルの部屋，ゴルフのプレー権，レンタカー，スポーツの観戦券 価格の変更による需要の適切な管理(収益最大化) 価格帯の異なる予約の販売をいつ停止するかを決定する． 最近では，インターネット直販における動的な価格の変更戦略にも利用されている．

ホテルの部屋に対する収益管理 宿泊 在庫 正規価格10000円 価格 正規価格の 0.6倍の価格 割引価格6000円 2017/3/3 ホテルの部屋に対する収益管理 宿泊 割引価格 停止 在庫 正規価格10000円 価格 正規価格の 0.6倍の価格 割引価格6000円 在庫切れ（満室）の確率＝0.6 期 割引価格6000=正規価格×0.6（期待収益）

収益管理の分類 価格固定 価格可変 期間予測可能 映画のチケット ホテルの部屋 航空機の座席 レンタカー クルーズ 期間予測不能 レストラン スポーツ観戦券 宴会場 ホテルの部屋 航空機の座席 レンタカー クルーズ 期間予測不能 レストラン ゴルフコース 介護サービス 病院 =>現状：理論体系はほぼ完成，日本国内では不調

動的価格付け 商品の価格を動的に変更 （単なる割引セールとは異なる．） 陳腐化資産に限定しない 　（単なる割引セールとは異なる．） 陳腐化資産に限定しない インターネットを用いた直販（E-Business）により注目 製造・輸送などの資源制約を考慮 収益最大化だけでなく，需要や生産の変動を削減 => サプライ・チェイン最適化の拡張

動的価格付け（従来研究） Whitin (1955) : 経済発注量モデルの拡張 Thomas (1970): 動的ロットサイズ決定モデルの拡張 Chan, Shen, Simchi-Levi and Swann (2004): 確率的在庫モデルの拡張（サーベイ） Swann (2004): ケーススタディ（GMの事例）； 線形・独立な需要・価格関数を用いた多期間生産・在庫モデル

“Employee Discount for Everyone” campaign GMの年間販売台数の推移 “Employee Discount for Everyone” campaign (2005, June)

動的価格付けの適用例 価格を変化させることによって需要をコントロール 独立でない価格-需要関数のモデル化（消費者選択モデル） 需要量 2017/3/3 動的価格付けの適用例 価格を変化させることによって需要をコントロール 独立でない価格-需要関数のモデル化（消費者選択モデル） 需要量 （価格一定） 価格 在庫曲線 新製品の顧客？ 自社の他製品？ 需要の増加は 他社の顧客？ 期 期 需要量 （価格制御） 価格 新製品 投入 在庫曲線

動的価格付けの実際 需要・価格関数の予測は困難（人間の行動モデルの難しさ） サプライ・チェイン最適化をサブルーチンとしたWhat If 分析 Supply Chain Modeling Language (SCML) 価格変更に伴う 需要変化のシナリオ ロジスティクス・ネットワーク設計 在庫最適化 配送計画 生産スケジューリング

まとめ 実務家 研究者 配送計画，収益管理 サプライ・チェイン最適化の20年以上の橋渡し 2017/3/3 配送計画，収益管理 サプライ・チェイン最適化の20年以上の橋渡し 多くの課題 例：ロジスティクス・ネットワーク設計＋収益管理 サプライ・チェイン・リスク管理 人道支援ロジスティクス（サプライ・チェイン） 実務家 研究者