ロジスティクスにおける 最適化の応用 東京商船大学 流通システム e-mail ：[email protected] http://www.ipc.tosho-u.ac.jp/~kubo 久保 幹雄 ロジスティクスとは 原材料 調達 生産 工場内物流 輸送 配送拠点 配送 •費用削減 •サービスの向上 •NO x,CO2 の削減 •交通渋滞の緩和 需要 地点 我が国のロジスティクスの現状 山勘による意思決定 企業間の力関係による部分最適化 情報化 全体最適化 プロジェクト遂行の手順 1. 問題抽出 2. ターゲットインスタンスの策定 3. 問題の定式化 4. プロトタイプ問題の選定 5. 解法の選定と実験的解析 6. （メタ）解法の設計 7. 実際問題に対するテスト 8. システム構築 ロジスティクス ネットワーク 顧客群 調達 工場 製品群 設備 輸送 倉庫 配送 顧客 工場選択・生産輸送問題 •倉庫数＝数百 •工場数＝数十 •設備数＝数百 •製品群数＝数百 倉庫選択・顧客群割当問題 •倉庫数＝数百 •顧客群数=数千 •製品群数＝数百 運搬経路問題 •デポ数＝1 (から数個） •顧客数=数万 •運搬車数=数百 •時間枠制約 •多期間 •回転の考慮 • etc., etc., etc., etc. , etc. デポ ロジスティクス・ネットワーク設計問題 工場選択・生産輸送問題 ＋ 倉庫選択・顧客群割当問題 ロジスティクス・ネットワーク設計問題 ストラテジック（長期レベルの意思決定）モデル プロトタイプ問題（ベンチマーク問題: OR-Lib., TSPLIB） k-median問題 容量制約付き施設配置問題 多重制約ナップサック問題 集合被覆（分割）問題 ロジスティクス・ネットワーク設計問題 に対する（メタ）解法 デモ Lagrange緩和 連続型（多ソースWeber問題）を利用した 局所探索法（拡張Weiszfeld法） 戦略的振動を用いたタブーサーチ 集中化・多様化制御法 変数固定テスト+分枝限定法 運搬経路問題 オペレーショナル（短期レベルの意思決定）モデル プロトタイプ問題(ベンチマーク問題: Solomonの問題,TSPLIB） （時間枠付き）運搬経路問題 多期間運搬経路問題 巡回セールスマン問題 多重制約ナップサック問題 集合被覆（分割）問題 運搬経路問題に対する（メタ）解法 Cross-opt近傍を用いた （誘導）局所探索法 (0,1)-opt近傍を用いたタブーサーチ 初期解生成法 挿入法 貪欲ランダム化適応型探索法（GRASP） ルート先・クラスター後法 multiple fragment 法 ルート選択ヒューリスティック （=施設配置ヒューリスティッ ク+分枝価格法） 階層的積木法 (0,1)-opt Or-opt or Insertion-opt Cross-opt (0,1)-opt (1) fixed radius near neighbor (using K-d tree) depot depot (0,1)-opt (2) fixed radius near neighbor (using K-d tree) (0,1)-opt (3) fixed radius near neighbor (using K-d tree) (0,1)-opt (4) fixed radius near neighbor (using K-d tree) Or-opt or Insertion-opt (1) To evaluate a neighbor in O(1) time, compute • 1. Total Time • 2. Earliest Departure • 3. Latest Arrival of the path in O(1) time. Or-opt or Insertion-opt (2) Or-opt or Insertion-opt (3) Or-opt or Insertion-opt (4) Cross-opt (1) Cross-opt (2) Cross-opt (3) Cross-opt (4) Cross-opt (5) Cross-opt (6) Cross-opt (7) Cross-opt (8) Cross-opt (9) Cross-opt (10) Building Block U 2 F: Set of Feasible Solutions F1 ⊂F Building Block B= F + F1+…+U F2 ⊂F1 ・ ・ Monotonization U: Ground Set φ Building Blocks for Vehicle Routing Problem (VRP) F = Set of Solutions F1 = Set of Vehicle Routes (schedule of a vehicle) F2 = Set of Routes F3 = Set of Paths (Strings) U = Set of Edges Hierarchical Building Block Method (HBBM) Neighborhood Search F DECOMPOSITION BUILD Controlled Int. /Div. Scheme U φ HBBM for VRP Cross-opt Tabu Search (TS) Route Selection Heuristic Branch & Price (Set Partitioning Approach) TS GRASP Location Based Heuristic Route-1st/Cluster 2nd First Fit Decreasing +TS TS Long Term Diversification Solomonの時間枠付き運搬経路ベンチマーク問題 ランダムタイプ （r101-112, r201-211） R101 1603 18 R201 1163 5 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) R101-112 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 5 10 15 20 25 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) R201-211 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 20 40 60 Solomonの時間枠付き運搬経路ベンチマーク問題 クラスタータイプ （c101-109, c201-208） C101 903 10 C201 565 3 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) C101-109 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 5 10 15 20 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) C201-208 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 10 20 30 40 Solomonの時間枠付き運搬経路ベンチマーク問題 混合タイプ （rc101-108, rc201-208） RC101 1611 16 RC201 1296 6 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) RC101-111 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 5 10 15 20 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較 100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値 (%) RC201-208 Kantravdis-Bard (GRASP) Solomon (Insertion) Taillard et al. (Adaptive Memory Programming) Rochat-Taillard (TS) Thangiah et al. (GA+SA+TS) Thangiah et al. (GA+SA) Thangiah (GA) Potvin-Bengio (GA) Chiang-Russell (SA) Chiang-Russell (Hybrid) 0 20 40 60 実際問題における改善（某消費財メーカーの例） 現状からの総費用と各曜日の運搬車台数の減少率（％） 50 デモ 45 40 総費用 月 火 水 木 金 35 30 25 20 15 10 5 0 3300 3700 5500 顧客数 まとめ （ロジスティクスに限らず） 実際の問題を解くには．．． • 問題に対する深い洞察 • 解法に対する深い洞察 • 頑強かつ高速なデータ構造と実装 • etc.,etc., etc., etc., etc. 実務家 研究者
© Copyright 2024 ExpyDoc
