非線形な目的関数をもつ! 船舶スケジューリングに対する ルート列挙解法 小林 和博 海上技術安全研究所 運航・物流系 ! 日本オペレーションズ・リサーチ学会 2015年春季研究発表会「交通」 1/18 船舶スケジューリング 引き受けた輸送依頼を,複数の船舶で,できる だけ効率よく運ぶスケジュールを求める問題 • 貨物の輸送依頼 貨物ID 積日 積港 揚日 揚港 量 c1 3/25 東京 3/27 仙台 600 c2 3/26 大阪 3/27 宇部 800 c3 3/25 福岡 3/28 名古屋 700 - 船舶は非等質 - 一度に一つの貨物 だけを載せられる 積→積 は,なし 2/18 船舶スケジューリング • 容量制約 • 貨物の量は,船舶の積載容量上限を超えてはならない. • 時間枠制約 • • 積日(揚日)の09:00から15:00までに積港(揚 日)で積まなければならない 喫水制約なども容量制約と同じ取り扱いが可能 3/18 集合分割問題定式化 ルートのコスト 60 100 集合分割問題の 90 250 制約行列 x[r1] x[r2] x[r3] x[r4] r1 r2 r3 r4 s1 c1 0 1 0 1 1 c2 1 0 1 1 c3 0 1 1 1 船1 s2 s3 = 1 1 1 1 1 船2 ルートr2が貨物c1とc3を処理することを, 4/18 行c1と行c3の1で表わす. 集合分割問題定式化 5/18 主問題 列の数=実行可能ルートの数 膨大になるので,陽な全列挙は不可能 or うまくない 有望な列を,「部分問題」を解いて得るのが一般的 集合分割問題定式化 有望な列を,「部分問題」を解いて得るのが一般的 この問題の場合,部分問題は ネットワーク上の最適化問題 6/18 運航ルートのコスト 港間の距離と,港間の運航速度によって決まる 目的は,移動距離の最小化ではなく, 燃料消費量の最小化 i xij : 0-1変数 通るか否か j vij : 連続変数 速度を表わす vmin xij vij vmax xij 7/18 運航ルートのコスト c(v) 1 v-r 平水中(屋内プール)での速度をvと したとき,単位時間当たりで3乗 = c(v) 気象海象の影響で,rの速度低下 があるとすると,単位距離では c(v) 13ノット 19ノット 1 v-r 8/18 9/18 部分問題(MISOCP) min X (i,j)2E s.t. ti + c(vij ) · dij vij rij e i ti ` i コスト(2次関数) dij vij rij · xij 先行制約 0-1変数 tj + M (1 xij ) 8(i, j) 2 E 8i vmin xij vij vmax xij 時間枠制約(iを訪問 するときだけ有効) 8(i, j) 2 E 連続変数 混合整数2次錐最適化問題(MISOCP)として定式化できる. 部分問題(MISOCP) 混合整数2次錐最適化問題(MISOCP)として定式化できる. • ルートxと,その上での速度vを同時に最適化する • 非線形なコストと非線形な制約を持つネットワーク上での 最適化問題 • Gurobi, SCIPなどでは解けるが,時間がかかる. • パスxを固定すると,速度の最適化は2次錐最適化問題 (SOCP) 10/18 全列挙に基づく列追加の手順 MISOCPを解く以外で列を見つける方法 • • • s-tパスxを全列挙して,各パス上での最適な速度 vを求める(SOCP). パスの数が多すぎるから,省けるパスは省きたい 省く方法 : • 各パスで速度最適化の緩和問題を解く • 暫定最適解より緩和値の悪いパスは最適解にはなり 11/18 得ないので除く 速度最適化の緩和問題 目的関数 制約条件 ti + dij vij rij tj + M (1 0にする→実行可能 領域が広くなる Hvattum et al. (2013)の 単調増加な関数で下から抑える アルゴリズムが適用可能 速い 12/18 部分問題を解く手順(列挙による) 1. s-tパスを全列挙する 2. 各パスで速度最適化の緩和問題を解く 3. 緩和値の小さい順にパスを並べたリストを作る 4. リストの順に,次を実行する. 1. 暫定最適値<緩和解なら次のパスへ 2. 暫定最適値>=緩和解なら厳密な最適速度を求める. 5. すべてのパスをチェックしたら終了 13/18 実装 • Python言語 Version 2.7 • モデリング言語 • • LPおよびIP : PuLP (http://www.coin-or.org/PuLP/) • SOCP : PICOS (http://picos.zib.de/) ソルバ • LPおよびIP : CBC ver. 2.8.9 (https://projects.coinor.org/Cbc) • SOCP : CVXOPT ver.1.1.7 (http://cvxopt.org/) 14/18 数値実験 • 乱数による問題生成 • 使う船舶の性能をあらかじめ決め,その船 舶が実行可能な運航ルートになるように, 日付,港を乱数により生成 • 生成したルートに含まれる貨物をばらして 輸送依頼とする. 15/18 17/18 部分問題の実行経過(3隻,貨物12,総計算時間38秒) 緩和値によ 緩和値が パス総数 る省略 正で省略 258 256 0 厳密な速 度最適化 2 最適速度 を再利用 0 速度最適 化累計 2 暫定解更 新回数 1 258 242 0 16 0 18 2 258 257 0 1 0 19 1 258 256 0 2 0 21 1 258 256 0 2 0 23 2 258 252 0 6 0 29 2 258 256 0 2 0 31 1 258 223 0 27 8 58 2 258 213 0 15 30 73 2 258 216 0 7 35 80 2 258 191 0 14 53 94 2 258 207 0 0 51 94 2 258 202 0 0 56 94 1 258 0 202 0 56 94 0 16/18 部分問題の実行経過(4隻,貨物16,総計算時間383秒) 緩和値によ 緩和値が パス総数 る省略 正で省略 厳密な速 度最適化 最適速度 を再利用 速度最適 化累計 暫定解更 新回数 1415 1326 0 89 0 89 1 1415 1222 0 193 0 282 1 1415 1335 0 11 69 463 2 1415 1343 0 52 20 592 1 1415 824 0 212 380 826 2 1415 830 0 102 483 928 1 1415 819 0 58 538 986 1 1415 892 0 11 512 997 1 1415 501 0 53 861 1050 1 1415 597 0 8 810 1058 2 1415 506 0 0 909 1058 2 まとめ • 船舶スケジューリング • 燃料最小化のためのルートと速度の同時最適化 • 集合分割定式化 • 部分問題はISOCPとして定式化される • MISOCPの代わりに,全列挙+緩和問題による効率化 • 数値実験 18/18
© Copyright 2024 ExpyDoc