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

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

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

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

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

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

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

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

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

ロジスティクス・ネットワーク設計問題 ストラテジック（長期レベルの意思決定）モデル k-median問題 容量制約付き施設配置問題 プロトタイプ問題（ベンチマーク問題: 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 2 F: Set of Feasible Solutions F1 ⊂F U: Ground Set φ Monotonization F2 ⊂F1 Building Block B= F + F1+…+U ・ 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) First Fit Decreasing +TS TS GRASP Location Based Heuristic Route-1st/Cluster 2nd TS Long Term Diversification

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

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

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

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

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

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

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

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

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

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

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