スライド 1

列生成による配船計画
アルゴリズムの数値計算結果
配船計画問題の定式化

目的関数
• 全ての船舶の総移動コストの最小化


移動コスト：移動距離/移動時間/燃料消費量/CO2排
出量など
制約条件
•
•
•
•
オーダーの制約：時間指定
船の制約：輸送量、船型
移動の制約：移動時間
港・荷役の制約：入出港時間、
荷役時間
オーダー
船
積港
移動
揚港
列生成法による計画作成
各船舶ごとに、運航可能な航路で
効率的なものを列挙しておく
全てのオーダーが処理されるように、各
船舶の運航航路を1つずつ選ぶ
列生成法による計画作成
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
繰
り
返
す
これまでに得られている候補から
なる集合分割問題を解いて、良い
スケジュールを選ぶ
2で得られた双対情報から、もっと
よいスケジュールを求めるための
最短路問題を定義する
集合分割問題
を解いて、最終
的な計画を得る
これ以上良い
候補がなくなれ
ば終了
列生成法による計画作成
船1の候補
船2の候補
船3の候補
候補ルート
1
オーダー1
オーダー2
オーダー3
オーダー4
オーダー5
オーダー6
2
3
4
5
6
7
8
9
運航航路を１つずつ選ぶ
実際は、2週間50オーダーで1隻あたり数万本以上
10隻だとすると、[ 数万本]の10乗とお
りをチェックしなければならない
人手では不可能
集合被覆問題に定式化して解く
集合分割問題への定式化
最小化
制約条件
T
c
x
Ax=１
x は0または1の変数
c, x: n次元ベクトル, A: m × nの行列
計算手法
x1
x1
x2
x2
x3
x3
x4
x4
x5
x5
X
x6
x6
x7
x7
x8
x8
x9
1
2
3
4
5
6
7
8
9
オーダー1
1
1
オーダー2
1
オーダー3
オーダー4
1
1
1
1
1
1
1
1
オーダー5
オーダー6
1
1
1
1
1
1
1
1
目的関数：船舶の総航行距離の最小化
各候補ルートの航行距離をコストと定義する
タスク1
タスク2
タスク3
タスク4
タスク5
c
c1
c2
c3
c4
c5
c6
c7
c8
c9
1
2
3
4
5
6
7
8
9
集合分割問題への定式化
c
X
X
最小化
1
1
1
1
1
1
b=
1
2
タスク1
1
1
タスク2
1
タスク3
タスク4
3
4
5
7
8
9
1
=
1
1
1
1
1
1
1
1
タスク5
タスク6
6
1
1
1
1
1
1
1
最も自明な計算方法
全ての可能なスケジュールを列挙して、その中でもっとも
効率のよいものを選べばよい→ 全列挙による解法
ところが、全列挙には控えめに見て数日かかる
条件を満たす配船計画の集合
最も効率的な計画
列挙型アルゴリズムの例：制約論理プログラミング（ＣＰ）
制約論理プログラミング
Constraint Programming, CP
制約条件をみたすものを、全て列挙するための手法
目的関数を最小化するものを見つける方法ではない
用途： ●ごく小規模な問題で、 (配船計画ではせいぜい３日分)
●制約条件が線形不等式で表現できないほど複雑なとき
●条件を満たすものを全て列挙するために用いる
制約条件を満たす要素の集合
間違ってつかうと機能しない
↑ CPソフトの販売元も注意を
喚起している
制約論理プログラミング
目的関数を最小化するものを見つける方法ではない
どうしても目的関数を設定したければ、、、、
今まで見つかった物の中で、最も目的関数が小さいものを採用する。
全列挙するのは数日かかるんじゃないの？、、、、
早く見つかることを祈って待つ
制約条件を満たす要素の集合
目的関数を制約条
件として指定する方
法を提唱されている
が、そもそもそういう
用途に使うものでは
ない、、、、
全列挙とはどういうことか？
条件を満たす配船計画の集合はいくつあるのか？
全列挙とはどういうことか？
巡回セールスマン問題
配船計画よりも遙かに簡単で、有名な組合せ最適化問題
与えられるデータ：n個の点と、各点間の距離
制約条件：全ての点を１度ずつ通り、最初の点に戻る
目的：巡回路の距離をできるだけ短くしたい
全列挙とはどういうことか？
巡回セールスマン問題を全列挙で解く：
可能な経路を全て列挙し、その中で距離が一番小さなものを選ぶ
実際に計算機を用いて数え上げるとどれくらいかかる？
10TFlopsの計算を用いた場合（１秒間に10^13回の演算が可能)
(地球シミュレーターが35.86TFlops)
都市数
巡回路の数
計算時間
6
60
4.32x10^{-10}秒
8
2520
3.32x10^{-8}秒
10
1.81x10^5
3.63x10^{-6}秒
15
4.36x10^10
1.96秒
20
6.08x10^16
4.87x10^6秒
25
3.10x10^23
3.88x10^13秒
30
4.42x10^30
7.96x10^20秒
56日
122万年
252333億年
全列挙とはどういうことか？
都市数
巡回路の数
計算時間
6
60
4.32x10^{-10}秒
8
2520
3.32x10^{-8}秒
10
1.81x10^5
3.63x10^{-6}秒
15
4.36x10^10
1.96秒
20
6.08x10^16
4.87x10^6秒
25
3.10x10^23
3.88x10^13秒
30
4.42x10^30
7.96x10^20秒
56日
122万年
252333億年
全列挙計算を実用システムで用いるとどうなるか？
都市数１５の問題が２秒で解けたユーザーは、
都市数２０の問題を解くのに５６日かかるとは思わない
実用システムでは、小規模な問題以外では全列挙ベースの計算
手法は使ってはいけない
列生成の概念図
「最短路問題」により、コスト面で明らかに解にならないものがわかる
こういうものは、見なくてよい
条件を満たす配船計画の集合
有効な集合
はごく一部
ここだけ見ておけばよい
列生成法に関する注目点
②定数時間の計算時間が期待できる
船の数が２倍、あるいは計画期間が２倍になって
も、せいぜい２倍+αの計算時間しかかからない
ことが期待できる
厳密には理論的には違うが、実際の計算では
そう見てよい
目的：実用規模の問題を解く
計算手法の開発
十分短い計算時間
入力データに対する頑強性
十分短い計算時間
現在のオペレーター担当者へのヒアリングより、想定される使用方法
担当者
配船計画案
受注状況の調整
データの変更
繰り返す
受注貨物データ
船舶データ
入力
計算結果
配船計画システ
ムに入力
入力データに対する頑強性
貨物需要は月によって変化
①
どのような偏りのある貨物データが来ても、
問題無く結果を出すこと
ユーザーが解きたい問題のサイズは
そのたびに異なる
②
数倍程度問題が大きくなっても、
問題無く結果を出すこと
定数時間のアルゴリズム
実用システムでは、全列挙ベースの計算手法は使ってはいけない
ではどうするか？
問題規模がK倍になっても
計算時間はせいぜいK倍プラスアルファしか大きくならず、
十分よい解が得られることが実験などで確かめられている
アルゴリズムを用いる必要がある
定数時間のアルゴリズム
そんなものが作れるのか？
１から作るのは、非常に難しい
膨大な数値実験が必要
幸い、数十年に渡る膨大な既存研究があり、
さまざまな手法に対するアイデア、計算機実験による検証は
既に行われている
Standing on the shoulders of giants
Don’t reinvent the wheel
配船計画の既存研究
１９６０年代から多数の研究が存在している。
→ 有効な計算手法はほぼ出揃っている。
「どの計算手法が適しているか？」の議論は既に完了
現在は事例開発、発表がなされているフェーズ
運航スケジュール作成
研究者
発表年
目的
Cargo
計算手法
Bausch et al.
1998
Min.cost
Refined oil
SP
Bremer and Perakis
1992
Min.cost
Crude oil
SP
Brown et al.
1987
Min.cost
Crude oil
SP
Cho and Perakis
2001
Min.cost
Bulk
IP
Christiansen and Fagerholt
2002
Min.cost
Dry bulk
SP
Fagerholt
2001
Min.cost
Dry bulk
SP
Fagerholt and Christiansen
2000a,b
Min.cost
Fertilizers
SP
Perakis and Bremer
1992
Min.cost
Crude oil
SP
Ronen
1986
Min.cost
Bulk
IP+heuristics
Scott
1995
Min.cost
Refined oil
Langarnge
relaxation.
Sherali et al.
1999
Min.cost
Cruide oil
MIP and heuristic
Vukadinovic et al.
1994
Min.cost
Gravel
Neural network
Vukadinovic et al
1997
Min.cost
Gravel
Neural network
船隊規模設計、航路決定
研究者
発表年
目的
Cargo
計算手法
Bendall and Stent
2001
Max. profit
Containers
MIP
Cho and Perakis
1996
Max. profit
Containers
SP
Crary et.al.
2002
Max. profit
-
MIP + 担当者操作
Dantzig and Fulkerson
1954
Min. num of ves.
Crude oil
LP
Darzentas and Spyrou
1996
Evaluate solution
Passengers
Simulation
Fagerholt
1999
Min. cost
Containers
IP+DP
Fagerholt et. Al.
2000
Min. cost
General Cargo
IP+DP
Fagerholt et.al
2002
Evaluate solution
Fresh Water
Simulation
2001
Min.cost
Containers
Simulation
1988
Min. cost
Sludge
Heuristics
Mehrez et al.
1995
Min. cost
Dry bulk
MIP
Pesenti
1995
Max. profit
Containers
Heuristics
Richetta and Larson
1997
Evaluate solution
Solid Waste
Heirustics
Imai and Rivera
Larson
在庫管理＋運航スケジュール
研究者
発表年
目的
Cargo
計算手法
Chajakis
1997,2000
Min. cost
Bulk oil
MIP and sim.
Christiansen
1999
Min. cost
Bulk ammonia
MIP + Dantig Wolfe 分解
Christiansen and
Nygreen
1998a,b,2001
Min. cost
Bulk ammonia
MIP + Dantig Wolfe 分解
Flatberg et al.
2000
Min. cost
Bulk ammonia
Heuristics
Fox and Herden
1999
Min. cost
Ammonia products
MIP
Kao et al.
1993
Min. cost
Coal
非線形計画
Liu and Sherali
2000
Min. cost
Coal
MIP and heuristics
Mehrez et al.
1995
Min. cost
Dry bulk minerals
MIP
Ronen
2002
Min. cost
Liquird oil
MIP and heuristics
Shih
1997
Min. cost
Coal
MIP
不定期船のスケジューリング
研究者
発表年
目的
Cargo
計算手法
Appelgren
1969,1971
Max. profit
Refrigerateded
MIP+DantzigWolfe分解
Bausch et al.
1998
Min. cost
Liquid bulk oil
SP
Christiansen
1999
Min. cost
Bulk anmonia
MIP+DantzigWolfe分解
Fagerholt
2003
Max. profit
Any
Heuristics
Kim and Lee
1997
Max. profit
Bulk
SP
Sherali et al.
1999
Min. cost
Crude oil
MIP and
heuristics
定期船スケジューリング
研究者
発表年
目的
Cargo
計算手法
Jaramillo and
Perakis
1991
Min. cost
General
LP +
heuristics
Perakis and
Jaramillo
1991
Min. cost
General
LP +
heuristics
Powell and
Perakis
1997
Min. cost
General
IP
用いられる計算手法
：
頻繁に用いられる手法（実績のある手法）
計算手法
計算手法
計算手法
LP (線形計画問題)
SP（集合分割問題）
Heuristic（近似解法）
IP（整数計画問題）
Simulation
MIP+Dantzig-Wolfe
MIP（混合整数計画問題）
IP+DP（IP+動的計画法）
NLP（非線形計画問題）
解きたい問題（現実の問題）
問題のクラス
モデル化
計算手法
NLP
MIP
IP
SP
解く
Dantzig-Wolfe分解
Heuristic
Simulation
DP
配船計画の既存研究
→ 有効な計算手法はほぼ出揃っている。
我々のやるべきこと
最も有効な手法を選択し、
国内の海運、港湾環境に合わせて修正すること
条件の変化、問題規模の増大に対して頑強な解法
→ 列生成法(Dantzig-Wolfe分解)による近似解法
今回採用した手法
Heuristic（近似解法）
SP（集合分割問題）
Dantzig-Wolfe分解
DP(動的計画法)
対象の問題
問題のクラス
NLP
MIP
IP
計算手法
Dantzig-Wolfe分解
SP
Simulation
Heuristic
DP
効率的な候補は少ない
１隻あたり数万本以上の候補の
ほとんどは非効率
効率的な候補を選ぶ
効率的な数百本の候補
「最短路問題」
極めて高速
定数時間
見込みのない候補は、探
索の必要すらない
制約条件を満たすスケジュール候補
数万本？数十万本？もっと？
効率的な候補を選ぶ
各船舶に対して、「最短路問題」と呼ばれる最適化問題を解けばよい
「最短路問題」は定数時間で解ける！！！
貨物数（期間）が倍になっても、計算時間は２倍程度
数値実験
Ａ社
対象製品
白油３０品目
対象船
対象隻数
対象港
石油タンカー（5000DWT程度）
１4隻
４０港
数値実験
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
これまでに得られている候補から、
良いスケジュールを選ぶ
集合分割問題
を解いて、最終
的な計画を得る
定数時間で解ける：
(反復回数)x(隻数）
小規模な線形計画問
題を解くだけので非
常に高速
整数計画問題を解く
←ほとんどの場合は数
分で済むが、、、非常に
時間がかかることはあ
り得る（今後の課題）
２週間分、１４隻の計画作成
①最短路：73秒
②：暫定スケジュール選択：0.1秒
③：集合分割問題：0.5秒
①
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
航行距離5.4パーセント減少
②
繰
り
返
す
これまでに得られている候補から、良いスケ
ジュールを選ぶ
③
集合分割問題を解いて、最
終的な計画を得る
反復は70回で終了
（１隻あたり70本の候補）
得られた双対情報から、もっとよいスケジュール
を求めるための最短路問題を定義する
これ以上良い候補が
なくなれば終了
３週間分、１４隻の計画作成
①最短路：224秒
②：暫定スケジュール選択：0.2秒
③：集合分割問題：53秒
①
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
航行距離6.5パーセント減少
②
繰
り
返
す
これまでに得られている候補から、良いスケ
ジュールを選ぶ
③
集合分割問題を解いて、最
終的な計画を得る
反復は127回で終了
（１隻あたり127本の候補）
得られた双対情報から、もっとよいスケジュール
を求めるための最短路問題を定義する
これ以上良い候補が
なくなれば終了
３週間分、１４隻の計画作成
①最短路：80秒(<-224秒)
②：暫定スケジュール選択：0.2秒
③：集合分割問題：74秒(<-53秒)
①
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
航行距離4.5パーセント減少
127回のときは6.5
②
繰
り
返
す
これまでに得られている候補から、良いスケ
ジュールを選ぶ
③
集合分割問題を解いて、最
終的な計画を得る
反復は50回で打ち切り
（１隻あたり50本の候補）
得られた双対情報から、もっとよいスケジュール
を求めるための最短路問題を定義する
これ以上良い候補が
なくなれば終了
４週間分、１４隻の計画作成
①最短路：651秒
②：暫定スケジュール選択：0.5秒
③：集合分割問題：7.8秒
①
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
航行距離6．2パーセント減少
②
繰
り
返
す
これまでに得られている候補から、良いスケ
ジュールを選ぶ
③
集合分割問題を解いて、最
終的な計画を得る
反復は300回で打ち切り
（１隻あたり300本の候補）
得られた双対情報から、もっとよいスケジュール
を求めるための最短路問題を定義する
これ以上良い候補が
なくなれば終了
４週間分、１４隻の計画作成
①最短路：185秒 ( <- 651秒)
②：暫定スケジュール選択：0.2秒
③：集合分割問題：44秒 ( <- 7.8秒)
①
各船毎に「最短路問題」を解き、
有効な候補スケジュールを求める
航行距離6．2パーセント減少
②
繰
り
返
す
これまでに得られている候補から、良いスケ
ジュールを選ぶ
③
300回と同じ答え
集合分割問題を解いて、最
終的な計画を得る
反復は100回で打ち切り
（１隻あたり100本の候補）
得られた双対情報から、もっとよいスケジュール
を求めるための最短路問題を定義する
これ以上良い候補が
なくなれば終了
列生成による計画作成
本数/隻
LP
2週間 14隻 73秒
70本
0.1秒
3週間 14隻 224秒
127本
3週間 14隻 80秒*
期間
隻数
候補生成
トータル
改善
0.5秒
73秒
5.4%
0.2秒
53秒
275秒
6.5%
50本*
0.2秒
74秒
154秒
4.5%
4週間 14隻 651秒*
300本*
0.5秒
7.8秒
659秒
6.2%
4週間 14隻 185秒*
100本*
0.5秒
44秒
229秒
6.2%
1秒
50秒
1550秒
5%
2週間 25隻 1500秒* 100本*
選択
*: 候補スケジュールの生成を途中で打ち切った場合
ちなみにＣＰでは、、
これは列生成の結果
期間
隻数
候補生成
2週間 14隻 73秒
本数/隻
LP
70本
0.1秒
選択
0.5秒
トータル
改善
73秒
5.4%
２週間１４隻分の配船計画：列生成では１分超で最も航行距離の小さい計画が求まる、
ところが、CPでは実行可能な計画を１つ見つけるのすら難しい。
白い点をど
れか一つ見
つける
白い点ひとつ見つけるより、
たった一つの赤い点を見
つける方が遙かに難しい
たった一つ
の赤い点を
見つける
ここで扱っている
配船計画問題は、
CPの適用可能
範囲を遙かに超
えている
CPで計画を作ろうとすると、
これは列生成の結果
期間
隻数
候補生成
2週間 14隻 73秒
本数/隻
LP
70本
0.1秒
選択
0.5秒
トータル
改善
73秒
5.4%
CPでは、３日を超える計画を見つけることは難しい、そこで例えば
１．初日１日分の実行可能な計画をいくつかCPで列挙し、その中から一つを選ぶ
２．次の一定期間（２日程度）のデータについて実行可能な計画を
CPによって列挙し、その中から初日とうまくつながるものを選ぶ
３．次の一定期間のデータについて実行可能な計画をCPによって
列挙し、その中から2.の期間とうまくつながるものを選ぶ
以下、3.を繰り返す。
この方法により、２時間（！！）で
実行可能な計画（白い点）が１つ求まった
たった一つ
白いものをの赤い点を
どれか一つ見つける
見つける

Download Report