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