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