事例: 自動販売機に対する在庫配送計画 宮本 裕一郎（発表者） 久保 幹雄 東京商船大学 共同研究：富士電機（株） 2001年3月5日 1 内容 新しいアルゴリズムを開発した話ではなく， 既存のアルゴリズムを適用した話 •在庫配送計画とは •自動販売機について •開発したシステム •自動販売機が一台の場合の訪問期決定法（動的計画法） •自動販売機が複数台の場合の構築法（挿入法） •自動販売機が複数台の場合の改善法（Cross-opt） •計算実験結果 2001年3月5日 2 在庫配送計画とは Bellらの論文（1983年）より例を引用 単純な例 需要点 商品を消費 在庫可能 デポ 商品を配送 2001年3月5日 3 在庫配送計画とは 商品の消費量は需要点によって異なる （時間に関しては一定） 一台の配送車が補充できるのは6個まで 2001年3月5日 4 在庫配送計画とは これを毎日繰り返す 2001年3月5日 5 在庫配送計画とは 1日目 2日目 3日目 4日目 5日目 ・・・ 2001年3月5日 6 在庫配送計画とは 別な計画も考えられる 2001年3月5日 7 在庫配送計画とは 別な計画も考えられる 2001年3月5日 8 在庫配送計画とは 別な計画も考えられる 2001年3月5日 9 在庫配送計画とは これを交互に繰り返す 2001年3月5日 10 在庫配送計画とは 1日目 2日目 3日目 4日目 5日目 ・・・ 2001年3月5日 11 在庫配送計画とは 1日目 2日目 3日目 4日目 5日目 ・・・ ・・・ 配送費用と品切れリスクとのトレードオフ 2001年3月5日 12 自動販売機の場合 需要は非確定的 自動販売機の台数はたいへん多い 1998年現在，日本全国にある飲料用自動販売機は約260万台 それらの年間売上高は約3兆円 飲料用自動販売機一台あたりの配送費用は約7000円 平均週に一回は配送しているとすると 年間の総配送費用は約1兆円 これはおいしい これは研究者としてやりがいのある課題 2001年3月5日 13 自動販売機の変遷 今まで 売上（品切れ）がわかる のは，配送で訪問した とき ↓ これから 自販機にPOSシステム と通信機が組み込まれ， リアルタイムで 正確なデータが 収集可能 2001年3月5日 14 自動販売機の変遷 2001年3月5日 15 自動販売機の情報源 詳しくは http://www.fujireiki.co.jp/museum/museum.html http://www.jvma.or.jp/ などを参照 2001年3月5日 16 いろいろな工夫が可能 あまり売れないところには自動販売機を置かない よく売れる地区にデポを配置 施設配置問題 よく売れる商品を自動販売機に陳列 あまり売れない商品は陳列しない 商品棚割問題 在庫・品切れ・配送の費用を考慮して商品を配送・補充 在庫配送計画問題 2001年3月5日 17 ローリングホライズン方式(Rolling horizon) 本来 在庫配送計画の計画期間は 無限期間 ↓ 有限期間に帰着 ↓ ローリングホライズン方式 2001年3月5日 18 Rolling horizon 例えば 7日間の計画を立てる 時間 最初の1日は 計画通りに運用 2001年3月5日 19 Rolling horizon 2日目以降の計画は使わない 時間 初日に偏ったいびつな計画を避けるためだけに使用 2001年3月5日 20 Rolling horizon 時間 2日目以降は，最新の情報をもとに，あらためて 7日間（2日目～8日目）の計画を立てる 2001年3月5日 21 Rolling horizon 0 1 2 3 4 5 6 7 8 9 10 （日） 1日目 新しい情報の下、 7日間（2～8日）分 解き直す。 2日目 3日目 2001年3月5日 22 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module 2001年3月5日 23 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module 地図情報から移動距離，時間，費用，を計算 2001年3月5日 24 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module 顧客と製品から需要を予測 2001年3月5日 25 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module 在庫配送ルート最適化 2001年3月5日 26 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module ルート出力，ルート運用の是非は人間が判断 意思決定支援システム 2001年3月5日 27 在庫配送計画システム Customer Table Product Table Truck Table Depot Table Forecasting Module Movement Table Route Table GIS Module IVRP Solver Module 餅は餅屋 2001年3月5日 28 在庫配送問題の仮定 •商品は期首に補充，期末に需要 •商品需要は既知 •補充には，配送費用がかかる •各商品満タンまで補充 •在庫費用 •品切れ費用 2001年3月5日 29 在庫配送問題のデータ •デポは一つ •自販機の数，位置 •計画期間 •個々の自販機の，各商品の最大収容量 •配送車の台数 •配送車の容量 •配送車の最大訪問数 •初期在庫 2001年3月5日 30 在庫配送問題 •計画期間におけるルートを決定 •在庫費用＋品切れ費用＋配送費用 の最小化 •ルート数制限 •個々のルートの制限 2001年3月5日 31 解法の概要 構築法＋改善法 挿入法 Cross-optによる 局所探索 Forall 全ての自販機 do 一台の自販機への訪問期を決定 スピード重視 最短路問題へ帰着 2001年3月5日 実装が容易 32 自動販売機が一台の場合 •配送費用は固定 •需要は既知 •商品の在庫費用と品切れ費用の算 出方法は既知 •最適な配送日を決定可能 2001年3月5日 33 自動販売機が一台の場合 配送費用 (固定費用) 在庫費用 品切れ費用 1 2 3 4 5 6 7 需要 2001年3月5日 時間(日) 34 自動販売機が一台の場合 配送費用 ダミーノード 在庫費用 (固定費用) 品切れ費用 0 1 配送費用 2 +在庫費用 3 4 +品切れ費用 5 6 7 1 2 5 6 7 3 4 Pathの長さ = 総費用 2001年3月5日 35 自動販売機が一台の場合 最短路 = 最小費用を実現する配送計画 0 1 2 3 4 5 6 7 計算時間は O(P T 2) P :商品の種類数 T:計画期間の長さ 2001年3月5日 36 構築法 挿入法を使用 デポから遠い自動販売機から順に，配送日を決定 2001年3月5日 37 挿入法 まず，一つの自動販売機への配送日を決定 配送費用 0 2001年3月5日 1 2 3 38 挿入法 0 2001年3月5日 1 2 3 39 挿入法 0 2001年3月5日 1 2 3 40 挿入法 2001年3月5日 41 挿入法 2001年3月5日 42 挿入法 + - + + 0 2001年3月5日 1 2 3 43 挿入法 + - + + 0 2001年3月5日 1 2 3 44 挿入法 0 2001年3月5日 1 2 3 45 改善法 Cross-optを近傍とした局所探索を採用 この点 2001年3月5日 この点 46 改善法 Cross-optを近傍とした局所探索を採用 2001年3月5日 47 改善法 Cross-optを近傍とした局所探索を採用 遠い点との入れ替えは ナンセンス K-d木 2001年3月5日 48 改善法 時間的候補は多数 時間 2001年3月5日 49 改善法 この期より先を交換候補 としても効果薄 この点と交換したほうが 時間 良さそう たとえばこの点の近傍 2001年3月5日 50 改善法 近傍を限定 時間 2001年3月5日 51 自動販売機とデポの数 問題のサイズ •デポ： 1 •自動販売機： 500～2000 •配送車： 20～100 •商品の種類： 100～300 2001年3月5日 52 計算実験 問題の大きさ •デポ: 1 計算実験は 富士電機（株） •自動販売機数: 727 •計画期間: 30(日) •製品の種類: 315 現状 •30日あたりの総配送時間: 7297.35[時間] •品切れ発生回数: 57回以上 •ルートの数: 25 2001年3月5日 53 計算実験結果 缶在庫 ｶｯﾌﾟ在 缶売切費 カップ売 ルート数 費 庫費 切費 数 現状に 対する 割合 Case1 3 3 2000 10000 15 60% Case2 3 3 2000 5000 16 64% Case3 3 3 2000 3000 16 64% Case4 3 3 2000 2000 16 64% Case5 3 3 2000 1000 16 64% Case6 3 3 200 2000 14 56% Case7 3 3 1000 1000 16 64% Case8 3 3 10000 10000 15 60% Case9 3 3 4000 20000 15 60% Case10 3 3 100000 100000 15 60% Case11 3 3 1000000 1000000 15 60% 現状 25 2001年3月5日 稼働時間 売切発 総時間 現状に 生回数 対する （計） 割合 4597.68 18 63% 4655.58 17 64% 4654.84 18 64% 4545.61 20 62% 4516.2 60 62% 3766.34 485 52% 4510.34 119 62% 4599.61 13 63% 4600.58 15 63% 4604.75 12 63% 4604.75 12 63% 7297.35 57回以上 54 結論 •在庫配送計画アルゴリズムを提案 •アルゴリズムを実装 •（富士電機が）計算実験，（富士電機が）特許申請 •理論と実務がつながりつつある 2001年3月5日 55 結論２ もしも，日本全国で採用されたならば… 1兆円の4割は4000億円 1%（ 40億円）くらいは報酬としてもらっても良いよね 2001年3月5日 56 今後 •商品陳列を入れ替えるタイミングを考慮した配送計画 •さらなる計算実験による検証が必要 2001年3月5日 57 おわり 2001年3月5日 58
© Copyright 2024 ExpyDoc
