E-mail ：kubo@ipc.tosho-u.ac.jp ロジスティクスにおける 最適化の応用 東京商船大学 　　流通システム e-mail ：kubo@ipc.tosho-u.ac.jp http://www.ipc.tosho-u.ac.jp/~kubo 久保　幹雄.

Presentation on theme: "E-mail ：kubo@ipc.tosho-u.ac.jp ロジスティクスにおける 最適化の応用 東京商船大学 　　流通システム e-mail ：kubo@ipc.tosho-u.ac.jp http://www.ipc.tosho-u.ac.jp/~kubo 久保　幹雄."— Presentation transcript:

1 e-mail ：kubo@ipc.tosho-u.ac.jp
ロジスティクスにおける 最適化の応用 東京商船大学 　　流通システム 久保　幹雄

2 ロジスティクスとは 費用削減 サービスの向上 NO x,CO2 の削減 交通渋滞の緩和 原材料 調達 生産 輸送 配送拠点 配送 需要 地点
工場内物流 輸送 配送拠点 配送 需要 地点 費用削減 サービスの向上 NO x,CO2 の削減 交通渋滞の緩和

3 我が国のロジスティクスの現状 山勘による意思決定 企業間の力関係による部分最適化 情報化 全体最適化

4 プロジェクト遂行の手順 1. 問題抽出 2. ターゲットインスタンスの策定 3. 問題の定式化 4. プロトタイプ問題の選定
5. 解法の選定と実験的解析 6. （メタ）解法の設計 7. 実際問題に対するテスト 8. システム構築

5 　ロジスティクス ネットワーク 顧客群 配送 顧客 工場 製品群 設備 調達 倉庫 輸送

6 　工場選択・生産輸送問題 倉庫数＝数百 工場数＝数十 設備数＝数百 製品群数＝数百

7 　倉庫選択・顧客群割当問題 倉庫数＝数百 顧客群数=数千 製品群数＝数百

8 運搬経路問題 デポ数＝1 (から数個） 顧客数=数万 運搬車数=数百 時間枠制約 多期間 回転の考慮
etc., etc., etc., etc. , etc.

9 ロジスティクス・ネットワーク設計問題 ＋ 工場選択・生産輸送問題 倉庫選択・顧客群割当問題

10 ロジスティクス・ネットワーク設計問題 ストラテジック（長期レベルの意思決定）モデル k-median問題 容量制約付き施設配置問題
プロトタイプ問題（ベンチマーク問題: OR-Lib., TSPLIB） k-median問題 容量制約付き施設配置問題 多重制約ナップサック問題 集合被覆（分割）問題

11 ロジスティクス・ネットワーク設計問題 に対する（メタ）解法
デモ Lagrange緩和 連続型（多ソースWeber問題）を利用した局所探索法（拡張Weiszfeld法） 戦略的振動を用いたタブーサーチ 集中化・多様化制御法 変数固定テスト+分枝限定法

12 運搬経路問題 オペレーショナル（短期レベルの意思決定）モデル （時間枠付き）運搬経路問題 多期間運搬経路問題 巡回セールスマン問題
プロトタイプ問題(ベンチマーク問題: Solomonの問題,TSPLIB） （時間枠付き）運搬経路問題 多期間運搬経路問題 巡回セールスマン問題 多重制約ナップサック問題 集合被覆（分割）問題

13 運搬経路問題に対する（メタ）解法 Cross-opt近傍を用いた （誘導）局所探索法 (0,1)-opt近傍を用いたタブーサーチ
初期解生成法 挿入法 貪欲ランダム化適応型探索法（GRASP） ルート先・クラスター後法 multiple fragment 法 ルート選択ヒューリスティック （=施設配置ヒューリスティック+分枝価格法） 階層的積木法

14 (0,1)-opt

15 Or-opt or Insertion-opt

16 Cross-opt

17 (0,1)-opt (1) fixed radius near neighbor (using K-d tree) depot depot

18 (0,1)-opt (2) fixed radius near neighbor (using K-d tree)

19 (0,1)-opt (3) fixed radius near neighbor (using K-d tree)

20 (0,1)-opt (4) fixed radius near neighbor (using K-d tree)

21 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.

22 Or-opt or Insertion-opt (2)

23 Or-opt or Insertion-opt (3)

24 Or-opt or Insertion-opt (4)

25 Cross-opt (1)

26 Cross-opt (2)

27 Cross-opt (3)

28 Cross-opt (4)

29 Cross-opt (5)

30 Cross-opt (6)

31 Cross-opt (7)

32 Cross-opt (8)

33 Cross-opt (9)

34 Cross-opt (10)

35 Building Block 2 F: Set of Feasible Solutions F1 ⊂F U: Ground Set φ
Monotonization F2 ⊂F1 Building Block B= F + F1+…+U ・ U: Ground Set φ

36 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

37 Hierarchical Building Block Method (HBBM)
Neighborhood Search F DECOMPOSITION BUILD Controlled Int. /Div. Scheme U φ

38 HBBM for VRP Cross-opt Tabu Search (TS) Route Selection Heuristic
Branch & Price (Set Partitioning Approach) First Fit Decreasing +TS TS GRASP Location Based Heuristic Route-1st/Cluster 2nd TS Long Term Diversification

39 Solomonの時間枠付き運搬経路ベンチマーク問題 ランダムタイプ （r101-112, r201-211）

40 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) R

41 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) R

42 Solomonの時間枠付き運搬経路ベンチマーク問題 クラスタータイプ （c101-109, c201-208）

43 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) C

44 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) C

45 Solomonの時間枠付き運搬経路ベンチマーク問題 混合タイプ （rc101-108, rc201-208）

46 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) RC

47 Solomonの時間枠付き運搬経路ベンチマーク問題に対する比較
100 ×(各解法の近似値 - Iterated Cross-optの値)/ Iterated Cross-optの値　(%) RC

48 実際問題における改善（某消費財メーカーの例）
　現状からの総費用と各曜日の運搬車台数の減少率（％） デモ 顧客数

49 （ロジスティクスに限らず） 実際の問題を解くには．．．
まとめ （ロジスティクスに限らず） 実際の問題を解くには．．． 　問題に対する深い洞察 　解法に対する深い洞察 　頑強かつ高速なデータ構造と実装 etc.,etc., etc., etc., etc. 　 実務家 研究者