非線形な目的関数をもつ! 船舶スケジューリングに対するルート列挙解法小林和博海上技術安全研究所運航・物流系 ! 日本オペレーションズ・リサーチ学会 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としたとき，単位時間当たりで３乗 = 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