スライド(PDF,0.5MB)

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