2
数理的なシステムとは?
シミュレーション
実際の問題
トラックを1台
増やしたら総費用
はどう変わるんだろう?
数理的モデル
最適化
意思決定者
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
成功事例
 GM(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
成功事例
 シェブロン社
(1981年)
 Brown & Graves
 手法:ネットワーク最適化
 効果:物流関連費用の13%削減
Management Science 27(1981) pp.55-70
12
成功事例
 米国
Marshalls社(1987年)
 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社(1975年)
 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%関税
4.7%関税
7.7%関税
DEC's Global Supply Chain Management
21
TL (Truckload) 輸送問題
次の日の荷量が不確実
空輸送
最小化
動的モデル
22
成功事例


North American Van Lines社 (1988年)
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)による
LTL(Less-Than-Truckload)輸送問題
の準最適化
25
成功事例
 モービルオイル社 (1995年)
 Brown
(Gravesの弟子)ら
 手法:LTL(Less-Than-Truckload)+
幹線輸送問題; ルート生成法
 効果:年間 100万$の削減
Interfaces 25 (1995) 1-17
26
配送計画問題(運搬経路問題)
 総費用最小化
顧客(需要点)
 ルート内の顧客
デポ
ルート
需要量が積載容
量以下
 一日の稼働時間
の上限を超えな
い
27
配送計画の歴史1
 1950年以前(経済からロジスティクスへ)
– Kantrovitch, Koopmansの輸送モデル
– Dantzigの線形計画
 1950-60
(黎明期)
– Dantzig & Ramserのタンカースケジュール
– Dantzig Fulkerson, Johnsonの巡回セール
スマン問題
28
配送計画の歴史2
 1960-80(初期の近似解法)
– Clarke & Wrightのセービング法
– Gillet & Millerのスイープ法
 1980-90
(近似解法の洗練と事例期)
– Fisher & Jaikumarの一般化割当法
– 多くの事例研究 (地理的データーベースの
普及)
 1990-現在
(メタ解法と事例の成熟期)
– タブーサーチの成功
29
配送計画の分類
輸送計画
– 1台の車が1箇所を経由
 トレーラー型配送計画
– 2から5箇所を経由
 (標準型)配送計画
– 6から100箇所を巡回
 巡回セールスマン型配送計画
– 数百箇所を巡回

30
トレーラー型配送計画
 工場・倉庫間
 タンクローリ,トレーラ
 飛行機の空路・人員スケジューリング
集合分割アプローチが有効!
特徴:付加条件が付くほど)易しい
31
成功事例
 モービルオイル社
(1987年)
 Brown
& Gravesら
 軽油のタンクローリーによる輸送
 手法:整数計画+ヒューリスティック
 効果:年間300万$の削減
1987年度 Franz Edelman Award
Interfaces (1987) 17 pp.107-120
32
成功事例
 Flying Tiger Line, Pacific Sothwest
Airways, Continental Airlines, Helsinki City
Transport (1981年)
 Marstenら
 手法:航空貨物運搬スケジューリング
問題に対する集合分割アプローチ
 効果:年間300,000$の費用削減
Networks 11 (1981) pp. 165-177
33
標準型配送計画



構築法
– セービング法(Clarke & Wright法)
クラスター先・ルート後法
– スイープ法(Gillet & Miller法)
– 一般化割当法
メタ解法(ヒューリスティック)
– ニューラルネット
– 遺伝的アルゴリズム
– シミュレーテッドアニーリング法
– 禁断探索法(タブーサーチ)
34
セービング法 (Clarke
& Wright)
ー
+
+
デポ
デポ
IBMがVSPとして売り出したため有名になった!
35
セービング法の解の例
OR Lib. の199顧客問題
重量,稼動時間条件付き
20台
総距離 1706
弱点:
横広がりのルートを形成
36
巡回セールスマン型配送計画
 クラスター先・ルート後法
– 地図(領域)を分割し,それから巡回路を作
る方法
 ルート先・クラスター後法
– 全ての顧客を通る巡回路を作成し,それか
らルートに分割する方法
 難しいが厳密に解く必要性は減少する
37
巡回セールスマン問題
全ての点をちょうど一回経由
する最短経路を求める問題
古典的な最適化問題
 点数が増えると難しい

38
巡回セールスマン問題
Aberdeen
Belfast
Edinburgh
Liverpool
Dublin
Cardiff
London
39
巡回セールスマン問題
Aberdeen
Belfast
Edinburgh
Liverpool
Dublin
Cardiff
London
40
巡回セールスマン問題
 応用
– 基盤配線,配送計画,スケジューリング,
基盤穿孔,X線構造解析実験,タンパク質
構造解析,DNA 並べ替え,VLSI設
計, 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
一般化割当法の解の例
18台
総距離
1492
時間の超過 243
51
ルート先・クラスター後法
デポ
52
ルート先・クラスター後法
デポ
53
Tabu Search (禁断探索法)
 人間の記憶過程にアナロジーを持つ.
 別名
– 最急上昇・最緩下降法 (steepest ascent
mildest descent method)
– 適応型記憶計画(adaptive memory
programming)
 同じ場所を巡回しないように,記憶を
頼りに,常に最も高い方向(下りの場合
は最も勾配の緩やかな方向)を目指す.
禁断探索法(タブーサーチ)
の解
54
18台
総距離
1364
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
成功事例
 デュポン
(1982年)
 Fisher
ら
 手法:一般化割当法
 効果:配送費用の15%削減
Interfaces (1982) 16 pp. 18-23
58
成功事例
 Air
Product & Chemical社
(1983年)
 Bellら
 手法:集合分割アプローチ
 効果:配送費用の6から10%削減
Interfaces (1983) 11 pp. 4-23
59
成功事例
 コカコーラ他4件の清涼飲料水会社
(1987年)
 Golden ら (Maryland大学)
 手法: 主に構築法 ROADNET (ROADNET
Systems Corp.100,000$-200,000$), TRUCKSTOPS
(Booz,Allen & Hamilton), MICRO VEH PLAN
 効果:配送費用の10%削減
Operations Research (1987) 35 pp. 6-17
60
成功事例
 ボランティアによる食事の配達
(1983年)
 Bartholdi & Platzman (Georgia Tec.)
 手法:ルート先・クラスター後法
 効果:配送費用の13%削減
 特徴:導入費用が安価
Interfaces (1983) 13 pp. 1-8
61
成功事例
 Suiker
Unie (オランダ生協)(1992年)
 ORTEC Consultants
 手法:時間枠付き配送計画問題に対す
る対話型スケジューリングシステム
(SHORTREC Package)
 効果:配送費用の7%削減
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
 手法:タブーサーチ
 効果:現行法の一般化割当法に比べて
16%の費用削減
Ann. OR (1993) 41 pp. 421-451
66
実用化のための付加条件
 時間枠指定
(何時から何時までに)
 積み込み・積み降ろしの考慮
 帰り便 (Backhauling) の考慮
 複数のデポ
 在庫計画との融合
 工程計画との融合
 不確実性の考慮
67
METRO (MEta
Truck Routing Optimizer)
メタ解法
顧客データ
ルートの
構築
地図データ
荷物データ
トラックデータ
最良解
ルートの
改善
制限時間
ユーザーとの対話
68
METROを用いた事例
 協力ゲームの理論を用いて顧客の費用
分担を計算する機能
 この機能を用いた事例
– 某メーカー (収集と配送の同時考慮)
– 年間3億6千万円の削減
– (現状の34.4%削減)
69
METEOを用いた事例
トラック4種類
重量,容量の同時考慮
70
まとめ
 ロジスティクスネットワーク再編成
(Supply Chain Management): Easy!
Easyな割には多大な費用削減が可能
 トレーラー型配送計画:数理計画手法
を駆使すれば割とEasy!
 (標準型)配送計画:バリエーションが多い
ため難しい (しかも根本的に難しい!: NP-hard)
– 難しいがゆえに膨大な研究あり!
71
数理的ロジスティクスの今後
実務家
費用削減のためのツール
研究者
実際問題に対する洞察
より高度な意思決定支援
ダウンロード

配送計画モデル - LOG OPT HOME