配送最適化システムについて - LOG OPT HOME

2
数理的なシステムとは？
ｼﾐｭﾚｰｼｮﾝ
実際の問題
トラックを１台
増やしたら総費用
はどう変わるんだろう?
数理的モデル
最適化
意思決定者
What If 分析
日常の作業を簡略化するシステム
エキスパートの知識の借り物のシステム
3
ロジスティクスシステムとは
スケジューリング
生産計画
原材料
調達物流
生産
工場内物流輸送
輸送計画
施設配置計画
配送拠点配送
配送計画
需要
地点
4
輸送問題
供給量
供給地点
需要地点
4
3
10
需要量
15
4
20
30
25
6
8
4
Kantrovich & Koopmans (Novel Prize)
Hitchcock型輸送問題
20
5
輸送問題
供給量
供給地点
需要地点
4
3
10
需要量
15
4
20
30
25
6
8
4
Kantrovich & Koopmans (Novel Prize)
Hitchcock型輸送問題
20
6
輸送問題
4t,10t,14t,19t
在庫費用
時間指定，
配送順序，etc.
7
輸送問題
 線形計画問題になるので数理計画ソフ
トウェアで求解可能
lp_solve (free), LINDO (2万-),
EXPRESS-MP (30万-), NUOPT (40万-),
etc. etc.
 湾岸戦争での輸送作戦
 石油会社等では日常業務に利用
成功（？）事例 (湾岸戦争)
ADANS: Aircraft Deployment Analysis System
8
350,000の人員
100,000トンの荷物の最適輸送
OR/MS Today April 1991 pp. 36-45
9
成功事例
 ＧＭ（General
Motors)社（1987年）
 Daganzoら (Carifornia大学,Berkeley)
 手法：在庫費用＋輸送費用最小化の解
析的手法
 効果：年間2,900,000$の費用削減
Franz Edelman Award (1987)
Interfaces 17 (1987) pp. 26-47
10
General Motors
GM 組立て工場
Delco Electronics
Milwaukee
Kokomo
Matamoros
11
成功事例
 シェブロン社
（１９８１年)
 Brown & Graves
 手法：ネットワーク最適化
 効果：物流関連費用の１３％削減
Management Science 27(1981) pp.55-70
12
成功事例
 米国
Marshalls社（１９８７年）
 Nickerson (Stanford), Powell
(Princeton)ら
 手法：パソコン上のロジスティクス計
画ツール (ネットワークモデル)
 効果：年間250,000$の費用削減
Interfaces 17, No.4 (1987)
pp. 16-26
13
施設配置問題
供給地点
需要地点
14
施設配置問題
供給地点
需要地点
15
施設配置問題
需要地点の重心！？
Weber (1929)
16
施設配置問題
需要地点の重心！？
Weber (1929)
施設配置問題
ロジスティクスネットワーク再編成
Supply Chain Management
17
18
成功事例
 米国
Hunt-Wesson社（１９７５年）
 GeoffrionとGraves
 手法：Bendersの分解原理(数理計画)
– 数千の品種を17個にグループ化，14の工場，45の
配送センター，消費地も121個にグループ化
 記念碑的な成功事例
Harvard Business Review, July-August
(1976) pp. 92-99
19
成功事例
 DEC（Digital Equipment Corporation)
（1995年）
 Global Supply Chain再編成，どこで何
を生産し，どこへ運ぶか (関税の考慮)
 手法：混合整数計画法
 効果：年間1億$の費用削減
Franz Edelman Award (1995)
Interfaces 25 (1995) pp. 69-93
20
Digital Equipment Corporation
5.0％関税
４．７％関税
７．７％関税
DEC's Global Supply Chain Management
21
TL (Truckload) 輸送問題
次の日の荷量が不確実
空輸送
最小化
動的モデル
22
成功事例


North American Van Lines社（１９８８年）
Powell(Princeton)，Sheffi (MIT)，Nickerson
(Stanford)ら
 手法：将来に対する不確実性を持ったTruckload
輸送問題: LOADMAP (Load Matching and Pricing；
荷物の動的評価＋空輸送最小化システム)
 効果：サービス向上+年間2.9 million$の費用削減
Franz Edelman Award (1988)
Interfaces 18 (1988) pp. 21-41
LTL (Less-Than-Truckload)
輸送問題
中長距離便（トレーラー中心)
地域内配送・収集
(小型トラック中心)
ターミナル
行き先別に積み替え
23
24
成功事例
 CN
Express, Canadian & French 鉄道,
Canada Post Corporation
(1989,1984,1986,1989年)
 Roy & Cranic
 NETPLAN (Network Planning)による
ＬＴＬ(Less-Than-Truckload)輸送問題
の準最適化
25
成功事例
 モービルオイル社 (１９９５年）
 Brown
(Gravesの弟子)ら
 手法：ＬＴＬ(Less-Than-Truckload)＋
幹線輸送問題; ルート生成法
 効果：年間１００万＄の削減
Interfaces 25 (1995) 1-17
26
配送計画問題(運搬経路問題)
 総費用最小化
顧客(需要点)
 ルート内の顧客
デポ
ルート
需要量が積載容
量以下
 一日の稼働時間
の上限を超えな
い
27
配送計画の歴史１
 1950年以前（経済からロジスティクスへ)
– Kantrovitch, Koopmansの輸送モデル
– Dantzigの線形計画
 1950-60
(黎明期)
– Dantzig & Ramserのタンカースケジュール
– Dantzig Fulkerson, Johnsonの巡回セール
スマン問題
28
配送計画の歴史２
 1960-80（初期の近似解法)
– Clarke & Wrightのセービング法
– Gillet & Millerのスイープ法
 1980-90
(近似解法の洗練と事例期)
– Fisher & Jaikumarの一般化割当法
– 多くの事例研究 (地理的データーベースの
普及)
 1990-現在
(メタ解法と事例の成熟期)
– タブーサーチの成功
29
配送計画の分類
輸送計画
– 1台の車が1箇所を経由
 トレーラー型配送計画
– 2から5箇所を経由
 （標準型）配送計画
– 6から100箇所を巡回
 巡回セールスマン型配送計画
– 数百箇所を巡回

30
トレーラー型配送計画
 工場・倉庫間
 タンクローリ，トレーラ
 飛行機の空路・人員スケジューリング
集合分割アプローチが有効！
特徴：付加条件が付くほど)易しい
31
成功事例
 モービルオイル社
（1987年)
 Brown
& Gravesら
 軽油のタンクローリーによる輸送
 手法：整数計画＋ヒューリスティック
 効果：年間３００万＄の削減
1987年度 Franz Edelman Award
Interfaces (1987) 17 pp.107-120
32
成功事例
 Flying Tiger Line, Pacific Sothwest
Airways, Continental Airlines, Helsinki City
Transport （１９８１年）
 Marstenら
 手法：航空貨物運搬スケジューリング
問題に対する集合分割アプローチ
 効果：年間300,000$の費用削減
Networks 11 (1981) pp. 165-177
33
標準型配送計画



構築法
– セービング法(Clarke & Wright法)
クラスター先・ルート後法
– スイープ法(Gillet & Miller法)
– 一般化割当法
メタ解法(ヒューリスティック)
– ニューラルネット
– 遺伝的アルゴリズム
– シミュレーテッドアニーリング法
– 禁断探索法(タブーサーチ)
34
セービング法 (Clarke
& Wright)
ー
＋
＋
デポ
デポ
IBMがVSPとして売り出したため有名になった！
35
セービング法の解の例
OR Lib. の199顧客問題
重量，稼動時間条件付き
２０台
総距離１７０６
弱点：
横広がりのルートを形成
36
巡回セールスマン型配送計画
 クラスター先・ルート後法
– 地図(領域)を分割し，それから巡回路を作
る方法
 ルート先・クラスター後法
– 全ての顧客を通る巡回路を作成し，それか
らルートに分割する方法
 難しいが厳密に解く必要性は減少する
37
巡回セールスマン問題
全ての点をちょうど一回経由
する最短経路を求める問題
古典的な最適化問題
 点数が増えると難しい

38
巡回セールスマン問題
Aberdeen
Belfast
Edinburgh
Liverpool
Dublin
Cardiff
London
39
巡回セールスマン問題
Aberdeen
Belfast
Edinburgh
Liverpool
Dublin
Cardiff
London
40
巡回セールスマン問題
 応用
– 基盤配線，配送計画，スケジューリング，
基盤穿孔，Ｘ線構造解析実験，タンパク質
構造解析，ＤＮA 並べ替え，ＶＬＳＩ設
計, etc.
 問題集(TSPLIB)あり．
巡回セールスマン問題
(ATT48 in TSPLIB)
41
42
巡回セールスマン問題について
のより詳しい情報は．．．
オペレーションズリサーチ1994年1,2,3月号
巡回セールスマン問題への招待1,2,3
巡回セールスマン問題への招待
（朝倉書店）
クラスター先・ルート後法
(スイープ法: Gillet & Miller）
デポ
43
クラスター先・ルート後法
（スイープ法）
デポ
44
45
スイープ法の弱点
 稼動時間の上限や時間枠などの時間的
要因を陽的には組み込めない
– クラスター先・ルート後法の根本的弱点
 細長いルートを形成しがち
 トラックの重量，容量条件がきついと
解が極端に悪化
クラスター先・ルート後法
(一般化割当法: Fisher & Jaikumar）
+
-
+
デポ
Seed Point
46
クラスター先・ルート後法
(一般化割当法）
重量，容量
重量，容量
重量，容量
47
制約付きの割当
(一般化割当)
クラスター先・ルート後法
(一般化割当法）
デポ
48
49
一般化割当法の弱点と利点
 弱点
– 一般化割当問題自身が困難な問題である
 利点
– 現在では最強のクラスター先・ルート後法
– 指定したトラックでの実行可能解を算出
 METRO
でも初期解生成に組み込んでお
り，一般化割当はタブーサーチで解く!
50
一般化割当法の解の例
１８台
総距離
１４９２
時間の超過２４３
51
ルート先・クラスター後法
デポ
52
ルート先・クラスター後法
デポ
53
Tabu Search (禁断探索法)
 人間の記憶過程にアナロジーを持つ．
 別名
– 最急上昇・最緩下降法 (steepest ascent
mildest descent method)
– 適応型記憶計画(adaptive memory
programming)
 同じ場所を巡回しないように，記憶を
頼りに，常に最も高い方向(下りの場合
は最も勾配の緩やかな方向)を目指す．
禁断探索法（タブーサーチ）
の解
54
１８台
総距離
１３６４
55
解法の比較
（ベンチマーク問題: OR-Lib.)
0.3
0.2
セービング
スイープ
0.15
0.1
0.05
顧客数
平均
100
120
100
120
199
150
100
75
50
199
150
100
75
0
50
タブーサーチとの相対誤差
0.25
56
標準ベンチマーク問題
OR-Lib.
TSPLIB
入手法
mail [email protected] (send info)
ftp: elib.zib-berlin.de (130.73.108.11)
pub/mp-data/tsp/
http://www.zib-berlin.de/
配送計画ソフトの有効性の目安！
57
成功事例
 デュポン
（１９８２年）
 Fisher
ら
 手法：一般化割当法
 効果：配送費用の１５％削減
Interfaces (1982) 16 pp. 18-23
58
成功事例
 Air
Product & Chemical社
（１９８３年）
 Bellら
 手法：集合分割アプローチ
 効果：配送費用の６から１０％削減
Interfaces (1983) 11 pp. 4-23
59
成功事例
 コカコーラ他４件の清涼飲料水会社
（１９８７年）
 Golden ら (Maryland大学)
 手法：主に構築法 ROADNET (ROADNET
Systems Corp.100,000$-200,000$), TRUCKSTOPS
(Booz,Allen & Hamilton), MICRO VEH PLAN
 効果：配送費用の１０％削減
Operations Research (1987) 35 pp. 6-17
60
成功事例
 ボランティアによる食事の配達
（１９８３年）
 Bartholdi & Platzman (Georgia Tec.)
 手法：ルート先・クラスター後法
 効果：配送費用の１３％削減
 特徴：導入費用が安価
Interfaces (1983) 13 pp. 1-8
61
成功事例
 Suiker
Unie (オランダ生協)(1992年)
 ORTEC Consultants
 手法：時間枠付き配送計画問題に対す
る対話型スケジューリングシステム
(SHORTREC Package)
 効果：配送費用の７％削減
Interfaces (1992) 22 pp. 4-14
62
成功事例
 Southern
California Gas Company
(1988年)
 Bodinら (Maryland大学)
 手法：ガスの検針スケジューリング問
題に対する枝巡回法(SOCAL Package)
 効果：年間 874,185$以上の削減
Interfaces (1992) 22 pp. 22-30
63
成功事例
 西アフリカの黒蠅駆除
(1992年)
 Solomonら (Northeastern大学)
 手法：ヘリコプターの巡回順決定に対
する配送計画スケジューリング手法の
適用
 効果：年間 100,000$の削減
Interfaces (1992) 22 pp. 88-99
64
成功事例
 ナイジェリア：モービル石油の油田巡
回 (1992年)
 Pulletblank (IBM, Thomas Watson研)
 手法：先行順序を持つヘリコプターの
巡回順決定に対する近似アプローチ
 効果：年間 500,000$の削減
Interfaces (1992) 22 pp. 100-111
65
成功事例
タブーサーチの実装
Taillard, Gendreau,
Glover, Kubo
 スイスの食料品配送計画（1993年）
 Semet
& Taillard
 手法：タブーサーチ
 効果：現行法の一般化割当法に比べて
１６％の費用削減
Ann. OR (1993) 41 pp. 421-451
66
実用化のための付加条件
 時間枠指定
(何時から何時までに)
 積み込み・積み降ろしの考慮
 帰り便 (Backhauling) の考慮
 複数のデポ
 在庫計画との融合
 工程計画との融合
 不確実性の考慮
67
METRO (MEta
Truck Routing Optimizer)
メタ解法
顧客データ
ルートの
構築
地図データ
荷物データ
トラックデータ
最良解
ルートの
改善
制限時間
ユーザーとの対話
68
METROを用いた事例
 協力ゲームの理論を用いて顧客の費用
分担を計算する機能
 この機能を用いた事例
– 某メーカー (収集と配送の同時考慮)
– 年間３億６千万円の削減
– （現状の３４．４％削減）
69
METEOを用いた事例
トラック４種類
重量，容量の同時考慮
70
まとめ
 ロジスティクスネットワーク再編成
(Supply Chain Management)： Easy!
Easyな割には多大な費用削減が可能
 トレーラー型配送計画：数理計画手法
を駆使すれば割とEasy!
 （標準型）配送計画：バリエーションが多い
ため難しい (しかも根本的に難しい!: NP-hard)
– 難しいがゆえに膨大な研究あり！
71
数理的ロジスティクスの今後
実務家
費用削減のためのツール
研究者
実際問題に対する洞察
より高度な意思決定支援

Download Report