Microsoft PowerPoint - 01-yagiura.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 01-yagiura.ppt"

ことここやぎ
5 years ago
Views:

1 時間枠つき配送計画問題に対するメタ戦略アルゴリズム柳浦睦憲 ( 京都大学 ) with 橋本英樹 ( 京都大学 ) 茨木俊秀 ( 関西学院大学 ) 今堀慎治 ( 東京大学 ) 久保幹雄 ( 東京海洋大学 ) 増田友泰 ( アクセンチュア ) 野々部宏司 ( 法政大学 ) 祖父江謙介 ( トヨタ ) 宇野毅明 ( 国立情報学研究所 )

2 時間枠付配送計画問題入力 : 節点 V = {0, 1,, n} (0: デポ, i 1: 客 ), 車両 M = {1,, m}, 距離 d ij, 移動時間 t ij, 容量 Q, 重み q i 出力 : 総距離を最小にする車両ルート制約 : 容量制約および時間枠制約 q 2 q 11 q 12 q 1 q 3 q 4 q 10 q 9 デポ q 8 q 7 q 6 q 5 容量制約 q 1 + q 2 + q 3 + q 4 Q 1 q 5 + q 6 + q 7 + q 8 Q 2 q 9 + q 10 + q 11 + q 12 Q 3

3 一般化時間枠各客はサービスを受ける時刻に対する希望を提示するペナルティペナルティ関数 p i (t) t 客 i に対する時間枠 p i (t): 非凸かつ不連続でもよい ( ただし区分線形関数のみ )

4 目的関数 co st( σ ) = D( σ ) + T ( σ ) + Q( σ ) σ D(σ ) T (σ ) Q(σ ) 車両スケジュール総距離総時間ペナルティ総容量超過時間枠制約および容量制約ソフト制約

5 計算例配送計画問題の基本モデルの問題例計算例 1 時間枠つきの問題例計算例 2

6 2 スケジューリング客仕事車両機械移動時間処理時間とセットアップ時間時間枠制約準備時間や納期など容量制約資源制約機械 1 機械 2 機械時刻

7 問題構造と探索空間車両スケジュール : (a) 客の車両への割当 (b) 各車両における客の訪問順序 (c) 各客のサービス開始時刻 (a) と (b) (c) 局所探索法により探索動的計画法により最適に解く ((a) と (b) は固定という条件の下で )

8 局所探索法適当な初期解から始め現在の解 σ の近傍 N(σ) の中に σ よりもよい解 σ があれば σ:= σ と置き換える操作を反復現在の解 σ 改良解局所最適解 - 探索空間 - 解の評価法 - 近傍 - 初期解生成法近傍 N (σ)

9 近傍操作 Or-opt 2-opt 2-opt* Cross exchange L Oopt ins l ins l Oopt path L path 2opt l L cross L l1 cross l2 L O( L Oopt path L Oopt ins n) O( L 2opt n) O( n 2 ) O( ( L cross ) 2 n 2 ) 近傍内の解 : 現在の解のパスを高々 4 つつなぎ合わせることで生成できる

10 最適サービス開始時刻決定問題もともとの目的関数 co st( σ ) = D( σ ) + T ( σ ) + Q( σ ) 問題 ( 車両ルートは固定 ) Optimal Start Time Problem (OSTP) 入力 : 車両の客の訪問順序 σ ( 0), σ (1), K, σ ( n ), σ ( n + 1) 出力 : 車両の時間ペナルティを最小にするような各客のサービス開始時刻動的計画法により厳密に最適化

11 OSTP の関連研究時間ペナルティ関数が一般の場合 Ibarai, Imahori, Kubo, Masuda, Uno & Yagiura, 2005 時間ペナルティ関数が凸の場合関連研究 : Garey, Tarjan & Wilfong 1988 Powell & Solomon 1992 Davis & Kanet 1993 Taillard, Badeau, Gendreau, Guertin & Potvin 1997 Tamai, Komori & Abe 1999 Ahuja & Orlin 2001 Hochbaum & Queyranne 2003 OSTP は線形計画問題になる isotonic median regression 問題を含む O(n log n ) 時間のアルゴリズムあり

12 f h (t) : 動的計画法客 σ (0), σ (1),, σ (h) が時刻 t 以前にサービスされるときのこれらの客の時間ペナルティの最小値 f f 0 h ( t) ( t) = = +, 0, min( t' t f h 1 t (, e t [ e ( t' τ 0 h-1, + ) ) + p 0 h ) ( t')), 1 h n + 1 p h e 0 τ h (t) : 車両のデポからの出発可能時刻 : h 番目の客から h + 1 番目の客への移動時間 : h 番目の客の時間ペナルティ関数

13 動的計画法の実行例 penalty f ( ) 1 t τ h 1 ph ( t) h + p h (t) f h 1( t) f h 1 h t f h (t) ( t τ 1) fh ( t) = min( fh 1( t' τ h-1) + t' t p h ( t'))

14 動的計画法の計算時間 n : 車両のルート内の客数 δ : 車両のルート内の客の時間ペナルティ関数の線形区分数の合計 ( 通常 δ =O(n )) 最適ペナルティ値決定 f ( ) f ( ) 0 t O( δ 1 t ) O( δ f ) 2 ( t) f ) O( δ 3 ( t) n f n ) O( δ (t) 総計算時間 : O(n δ ) n f n + O( δ 1( t) )

15 時間ペナルティの評価の高速化アイデア - 近傍内の解の評価に現在の解 σ の f h (t) ( 計算済 ) を再利用 - 解が更新されたときには動的計画法 (DP) を再計算ペナルティ関数が一般の場合 : 近傍内の解の評価 : O(δ ) 平衡木解の移動の際のDPの再計算 : O(n δ ) を利用ペナルティ関数が凸の場合 : 近傍内の解の評価 : O(log δ ) 解の移動の際のDPの再計算 : O(δ log δ )

16 b h (t) : 時間ペナルティの高速計算客 σ (h), σ (h+1),, σ (n +1) が時刻 t 以降にサービスされるときのこれらの客の時間ペナルティの最小値 f h (t) と同様に計算できる 0 1 h h+1 n n +1 τ h f h (t) b ( t h+1 ) ルートの最小ペナルティ : ( f ( t) b ( t + τ )) min h + h + 1 h ペナルティが一般の場合 O(δ ), 凸の場合 O(log δ ) 時間 2-opt* には直接利用可. それ以外の場合は交換されるパス内の客の f h (t) を効率よく再計算できるよう探索順序に工夫の必要あり. t

17 DP: 時間ペナルティが凸の場合 p i (t): 全ての i に対して凸 f h (t): 凸 f h (t) を平衡木で表現 - 葉節点 f h (t) の線形区分のひとつ - 根から葉へのパス葉に対応する線形区分の傾きや切片などの情報平衡木 f ( ) 1 t τ 1 p ( t) h h- + h 基本操作 : O(log δ ) 時間総計算時間 : O(δ log δ ) 追加した線形区分

18 効率化のアイデア近傍の制限 - 近傍リスト : TSP や VRP に対し大きな効果 - サービス開始時刻が近い客のペア動的計画法の関数 f h (t) の区分数の削減 - 関数 f h (t) の線形区分の中で対応するペナルティ値が非常に大きいものを削除

19 反復局所探索法 (ILS) 局所探索を多数反復過去の探索で得られたよい解に少しのランダムな変形を加えたものを初期解

20 問題例計算環境と実験方法計算実験 Gehring & Homberger のベンチマーク問題例 (Solomon の問題例と同様の生成法. より大規模 ) 時間枠制約と容量制約 : 絶対制約客数 : 200, 400, 600, 800, 1000 各サイズに対して 60 問 ( 全部で 300 問 ) C 言語 ; PC (Pentium IV 2.8GHz) 絶対制約ペナルティ関数 ; 適応的重み調整出力する解 : 絶対制約を満たす解車両数 : 既知の最良値 (± 1)

21 number of customers best nown MB (2003) GH (2002) LC (2003) our ILS CNV CTD time (min) CNV CTD time (min) CNV CTD time (min) CNV CTD time (min) CNV CTD time (min) CNV: cumulative number of vehicles CTD: cumulative total distance MB: Mester and Bräysy GH: Gehring and Homberger LC: Le Bouthillier and Crainic

22 より高い汎用性を目指して時刻依存の移動時間および移動コスト - 朝夕のラッシュ - 生産ラインにおけるセットアップ移動時間が可変, 移動時間に応じたコスト - 有料道路の利用により移動時間を短縮 - 特急仕事として高速処理一般の時間ペナルティをもつ問題に上のいずれかを追加した問題を考える

23 待移動 s i s j 待時刻依存の移動時間 τ ij (t i ) t i τ ij (t i ) 時刻連続 FIFO t < t' t + τ ij (t) < t' + τ ij (t') τ ij (t i ) τ ij (t i ) (a) 従来のモデル ti (b) 提案モデル ti

24 移動時間コスト関数 q ij (t ij ) si q ij ( t ij + ) i サービス移動待ち時間 t ij j s j q ij ( t ij + 時刻 ) サービス時間 ( 処理時間 ) 人手やコストをかけて短縮可能移動時間 ( セットアップ時間 ) 有料道路の利用など待ち時間小さいほうがよい場合 (a) 従来のモデル t ij (b) 提案モデル t ij

25 計算の複雑さに関する結果時刻依存の移動時間および移動コスト - 移動時間関数の総複雑度に対して線形時間の DP - 移動時間関数の複雑度が各客ペアで O(1) 移動時間が定数の場合と同程度の計算時間移動時間が可変, 移動時間に応じたコスト - 移動時間コスト関数が一般 NP 困難 ; 擬多項式時間の DP - 移動時間コスト関数が凸 ( 時間ペナルティ関数は一般 ) 多項式時間の DP

26 まとめ時間枠に対する要求を一般的なペナルティ関数として表現できる汎用的な問題の定式化時間ペナルティ最小化問題を解く必要性動的計画法の提案高速化のさまざまな工夫 Gehring & Homberger のベンチマーク問題例に対する良好な結果移動時間に対する汎用的な定式化

27 今後の課題異なるタイプの汎用化配送ルートの探索能力の向上大規模問題例への適用時間枠の取り扱いより実装しやすい単純なアルゴリズムで高速かつ実用的なものの開発 cf. 提案手法はいずれも非常に複雑で実装困難

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法組合せ計画問題組合せ計画問題とは : 有限個のものの組合せの中から, 目的関数を最小または最大にする組合せを見つける問題例 1: 整数計画問題全般