列生成による配船計画 アルゴリズムの数値計算結果.

Presentation on theme: "列生成による配船計画 アルゴリズムの数値計算結果."— Presentation transcript:

1 列生成による配船計画 アルゴリズムの数値計算結果

2 配船計画問題の定式化 目的関数 制約条件 全ての船舶の総移動コストの最小化 オーダーの制約：時間指定 船の制約：輸送量、船型
移動コスト：移動距離/移動時間/燃料消費量/CO2排出量など 制約条件 オーダーの制約：時間指定 船の制約：輸送量、船型 移動の制約：移動時間 港・荷役の制約：入出港時間、 　　　荷役時間 揚港 移動 積港 船 オーダー

3 列生成法による計画作成 各船舶ごとに、運航可能な航路で効率的なものを列挙しておく
全てのオーダーが処理されるように、各船舶の運航航路を1つずつ選ぶ

4 列生成法による計画作成 各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 集合分割問題を解いて、最終的な計画を得る
繰り返す 集合分割問題を解いて、最終的な計画を得る これまでに得られている候補からなる集合分割問題を解いて、良いスケジュールを選ぶ 2で得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

5 列生成法による計画作成 候補ルート 船1の候補 船2の候補 船3の候補 オーダー1 オーダー2 オーダー3 オーダー4 オーダー5
6 7 8 9 オーダー1 オーダー2 オーダー3 オーダー4 オーダー5 オーダー6

6 運航航路を１つずつ選ぶ 10隻だとすると、[ 数万本]の10乗とおりをチェック しなければならない 人手では不可能
実際は、2週間50オーダーで1隻あたり数万本以上 10隻だとすると、[ 数万本]の10乗とおりをチェック しなければならない 人手では不可能 集合被覆問題に定式化して解く

7 cT x A x = １ 集合分割問題への定式化 最小化 制約条件 x は0または1の変数
　最小化 A x = １ 制約条件 x は0または1の変数 c, x: n次元ベクトル, A: m × nの行列

8 A 計算手法 X x9 1 2 3 4 5 6 7 8 9 オーダー1 オーダー2 オーダー3 オーダー4 オーダー5 オーダー6 x1

9 各候補ルートの航行距離をコストと定義する
目的関数： 船舶の総航行距離の最小化 1 2 3 4 5 6 7 8 9 各候補ルートの航行距離をコストと定義する タスク1 タスク2 タスク3 タスク4 タスク5 c1 c2 c3 c4 c5 c6 c7 c8 c9 c

10 A c X b 集合分割問題への定式化 最小化 = 1 2 3 4 5 6 7 8 9 タスク1 タスク2 タスク3 タスク4 タスク5
タスク6 A 集合分割問題への定式化 X c 最小化 b

11 最も自明な計算方法 全ての可能なスケジュールを列挙して、その中でもっとも 効率のよいものを選べばよい→ 全列挙による解法
効率のよいものを選べばよい→　全列挙による解法 ところが、全列挙には控えめに見て数日かかる 条件を満たす配船計画の集合 最も効率的な計画 　列挙型アルゴリズムの例：　制約論理プログラミング（ＣＰ）

12 制約論理プログラミング 目的関数を最小化するものを見つける方法ではない Constraint Programming, CP
制約条件をみたすものを、全て列挙するための手法 目的関数を最小化するものを見つける方法ではない 用途： ●ごく小規模な問題で、 (配船計画ではせいぜい３日分) ●制約条件が線形不等式で表現できないほど複雑なとき ●条件を満たすものを全て列挙するために用いる 間違ってつかうと機能しない ↑ CPソフトの販売元も注意を喚起している 制約条件を満たす要素の集合

13 制約論理プログラミング 目的関数を最小化するものを見つける方法ではない どうしても目的関数を設定したければ、、、、
今まで見つかった物の中で、最も目的関数が小さいものを採用する。 全列挙するのは数日かかるんじゃないの？、、、、 目的関数を制約条件として指定する方法を提唱されているが、そもそもそういう用途に使うものではない、、、、 早く見つかることを祈って待つ 制約条件を満たす要素の集合

14 条件を満たす配船計画の集合はいくつあるのか？
全列挙とはどういうことか？ 条件を満たす配船計画の集合はいくつあるのか？

15 全列挙とはどういうことか？ 巡回セールスマン問題 配船計画よりも遙かに簡単で、有名な組合せ最適化問題
与えられるデータ：n個の点と、各点間の距離 制約条件：全ての点を１度ずつ通り、最初の点に戻る 目的：巡回路の距離をできるだけ短くしたい

16 全列挙とはどういうことか？ 巡回セールスマン問題を全列挙で解く： 可能な経路を全て列挙し、その中で距離が一番小さなものを選ぶ
実際に計算機を用いて数え上げるとどれくらいかかる？ 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億年

17 全列挙とはどういうことか？ 全列挙計算を実用システムで用いるとどうなるか？
都市数 巡回路の数 計算時間 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億年 全列挙計算を実用システムで用いるとどうなるか？ 都市数１５の問題が２秒で解けたユーザーは、 都市数２０の問題を解くのに５６日かかるとは思わない 実用システムでは、小規模な問題以外では全列挙ベースの計算手法は使ってはいけない

18 「最短路問題」により、コスト面で明らかに解にならないものがわかる
列生成の概念図 「最短路問題」により、コスト面で明らかに解にならないものがわかる 条件を満たす配船計画の集合 こういうものは、見なくてよい 有効な集合はごく一部 ここだけ見ておけばよい

19 列生成法に関する注目点 ②定数時間の計算時間が期待できる 船の数が２倍、あるいは計画期間が２倍になって
も、せいぜい２倍+αの計算時間しかかからない ことが期待できる 　　　厳密には理論的には違うが、実際の計算では 　　　　　　　　　　　　　そう見てよい

20 目的：　実用規模の問題を解く 計算手法の開発 十分短い計算時間 入力データに対する頑強性

21 現在のオペレーター担当者へのヒアリングより、想定される使用方法
十分短い計算時間 現在のオペレーター担当者へのヒアリングより、想定される使用方法 担当者 配船計画案 受注状況の調整 データの変更 繰り返す 計算結果 受注貨物データ 船舶データ 配船計画システムに入力 入力

22 どのような偏りのある貨物データが来ても、
入力データに対する頑強性 貨物需要は月によって変化　　 ① どのような偏りのある貨物データが来ても、 問題無く結果を出すこと ユーザーが解きたい問題のサイズは そのたびに異なる　 数倍程度問題が大きくなっても、 問題無く結果を出すこと ②

23 定数時間のアルゴリズム ではどうするか？ 問題規模がK倍になっても 計算時間はせいぜいK倍プラスアルファしか大きくならず、
実用システムでは、全列挙ベースの計算手法は使ってはいけない ではどうするか？ 問題規模がK倍になっても 計算時間はせいぜいK倍プラスアルファしか大きくならず、 十分よい解が得られることが実験などで確かめられている アルゴリズムを用いる必要がある

24 定数時間のアルゴリズム Standing on the shoulders of giants
そんなものが作れるのか？ １から作るのは、非常に難しい 膨大な数値実験が必要 幸い、数十年に渡る膨大な既存研究があり、 さまざまな手法に対するアイデア、計算機実験による検証は既に行われている Standing on the shoulders of giants Don’t reinvent the wheel

25 配船計画の既存研究 １９６０年代から多数の研究が存在している。 → 有効な計算手法はほぼ出揃っている。
→　有効な計算手法はほぼ出揃っている。 「どの計算手法が適しているか？」の議論は既に完了 現在は事例開発、発表がなされているフェーズ

26 運航スケジュール作成 研究者 発表年 目的 Cargo 計算手法 Bausch et al. 1998 Min.cost
Refined oil SP Bremer and Perakis 1992 Crude oil Brown et al. 1987 Cho and Perakis 2001 Bulk IP Christiansen and Fagerholt 2002 Dry bulk Fagerholt Fagerholt and Christiansen 2000a,b Fertilizers Perakis and Bremer Ronen 1986 IP+heuristics Scott 1995 Langarnge relaxation. Sherali et al. 1999 Cruide oil MIP and heuristic Vukadinovic et al. 1994 Gravel Neural network Vukadinovic et al 1997

27 船隊規模設計、航路決定 研究者 発表年 目的 Cargo 計算手法 Bendall and Stent 2001 Max. profit
Containers MIP Cho and Perakis 1996 SP Crary et.al. 2002 - MIP + 担当者操作 Dantzig and Fulkerson 1954 Min. num of ves. Crude oil LP Darzentas and Spyrou Evaluate solution Passengers Simulation Fagerholt 1999 Min. cost IP+DP Fagerholt et. Al. 2000 General Cargo Fagerholt et.al Fresh Water Imai and Rivera Min.cost Larson 1988 Sludge Heuristics Mehrez et al. 1995 Dry bulk Pesenti Richetta and Larson 1997 Solid Waste Heirustics

28 在庫管理＋運航スケジュール 研究者 発表年 目的 Cargo 計算手法 Chajakis 1997,2000 Min. cost
Bulk oil MIP and sim. Christiansen 1999 Bulk ammonia MIP + Dantig -Wolfe 分解 Christiansen and Nygreen 1998a,b,2001 Flatberg et al. 2000 Heuristics Fox and Herden Ammonia products MIP Kao et al. 1993 Coal 非線形計画 Liu and Sherali MIP and heuristics Mehrez et al. 1995 Dry bulk minerals Ronen 2002 Liquird oil Shih 1997

29 不定期船のスケジューリング 研究者 発表年 目的 Cargo 計算手法 Appelgren 1969,1971 Max. profit
Refrigerateded MIP+Dantzig-Wolfe分解 Bausch et al. 1998 Min. cost Liquid bulk oil SP Christiansen 1999 Bulk anmonia Fagerholt 2003 Any Heuristics Kim and Lee 1997 Bulk Sherali et al. Crude oil MIP and heuristics

30 定期船スケジューリング 研究者 発表年 目的 Cargo 計算手法 Jaramillo and Perakis 1991 Min. cost
General LP + heuristics Perakis and Jaramillo Powell and Perakis 1997 IP

31 ： 頻繁に用いられる手法（実績のある手法）
用いられる計算手法 ：　　頻繁に用いられる手法（実績のある手法） 計算手法 LP (線形計画問題) IP（整数計画問題） MIP（混合整数計画問題） 計算手法 SP（集合分割問題） Simulation IP+DP（IP+動的計画法） 計算手法 Heuristic（近似解法） MIP+Dantzig-Wolfe NLP（非線形計画問題） 解きたい問題（現実の問題） モデル化 MIP IP SP 問題のクラス NLP Simulation 計算手法 解く Dantzig-Wolfe分解 Heuristic DP

32 配船計画の既存研究 最も有効な手法を選択し、 国内の海運、港湾環境に合わせて修正すること 条件の変化、問題規模の増大に対して頑強な解法
→　有効な計算手法はほぼ出揃っている。 我々のやるべきこと 最も有効な手法を選択し、 国内の海運、港湾環境に合わせて修正すること 条件の変化、問題規模の増大に対して頑強な解法　 →　列生成法(Dantzig-Wolfe分解)による近似解法

33 今回採用した手法 対象の問題 問題のクラス 計算手法 NLP MIP Dantzig-Wolfe分解 IP SP Heuristic
DP(動的計画法) 対象の問題 問題のクラス 計算手法 MIP NLP Dantzig-Wolfe分解 IP SP Heuristic Simulation DP

34 効率的な候補は少ない １隻あたり数万本以上の候補の ほとんどは非効率

35 効率的な候補を選ぶ 「最短路問題」 極めて高速 定数時間 制約条件を満たすスケジュール候補 数万本？数十万本？もっと？ 効率的な数百本の候補
見込みのない候補は、探索の必要すらない 制約条件を満たすスケジュール候補 数万本？数十万本？もっと？

36 効率的な候補を選ぶ 「最短路問題 」は定数時間で解ける！！！ 各船舶に対して、「最短路問題」と呼ばれる最適化問題を解けばよい
「最短路問題　」は定数時間で解ける！！！ 貨物数（期間）が倍になっても、計算時間は２倍程度

37 数値実験 Ａ社 対象製品 白油３０品目 対象船 石油タンカー （5000DWT程度） 対象隻数 １4隻 対象港 ４０港

38 数値実験 各船毎に「最短路問題」を解き、 定数時間で解ける： 有効な候補スケジュールを求める (反復回数)x(隻数）
これまでに得られている候補から、良いスケジュールを選ぶ 小規模な線形計画問題を解くだけので非常に高速 整数計画問題を解く ←ほとんどの場合は数分で済むが、、、非常に時間がかかることはあり得る（今後の課題） 集合分割問題を解いて、最終的な計画を得る

39 ２週間分、１４隻の計画作成 ① ② ③ ①最短路：73秒 ②：暫定スケジュール選択：0.1秒 ③：集合分割問題：0.5秒
各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 航行距離5.4パーセント減少 繰り返す ② ③ これまでに得られている候補から、良いスケジュールを選ぶ 集合分割問題を解いて、最終的な計画を得る 反復は70回で終了 （１隻あたり70本の候補） 得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

40 ３週間分、１４隻の計画作成 ① ② ③ ①最短路：224秒 ②：暫定スケジュール選択：0.2秒 ③：集合分割問題：53秒
各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 航行距離6.5パーセント減少 繰り返す ② ③ これまでに得られている候補から、良いスケジュールを選ぶ 集合分割問題を解いて、最終的な計画を得る 反復は127回で終了 （１隻あたり127本の候補） 得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

41 ３週間分、１４隻の計画作成 ① ② ③ ①最短路：80秒(<-224秒) ②：暫定スケジュール選択：0.2秒
③：集合分割問題：74秒(<-53秒) ① 各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 航行距離4.5パーセント減少 繰り返す ② 127回のときは6.5 ③ これまでに得られている候補から、良いスケジュールを選ぶ 集合分割問題を解いて、最終的な計画を得る 反復は50回で打ち切り （１隻あたり50本の候補） 得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

42 ４週間分、１４隻の計画作成 ① ② ③ ①最短路：651秒 ②：暫定スケジュール選択：0.5秒 ③：集合分割問題：7.8秒
各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 航行距離6．2パーセント減少 繰り返す ② ③ これまでに得られている候補から、良いスケジュールを選ぶ 集合分割問題を解いて、最終的な計画を得る 反復は300回で打ち切り （１隻あたり300本の候補） 得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

43 ４週間分、１４隻の計画作成 ① ② ③ ①最短路：185秒 ( <- 651秒) ②：暫定スケジュール選択：0.2秒
③：集合分割問題：44秒 ( <- 7.8秒) ① 各船毎に「最短路問題」を解き、 有効な候補スケジュールを求める 航行距離6．2パーセント減少 繰り返す ② 300回と同じ答え ③ これまでに得られている候補から、良いスケジュールを選ぶ 集合分割問題を解いて、最終的な計画を得る 反復は100回で打ち切り （１隻あたり100本の候補） 得られた双対情報から、もっとよいスケジュールを求めるための最短路問題を定義する これ以上良い候補がなくなれば終了

44 *: 候補スケジュールの生成を途中で打ち切った場合
列生成による計画作成 期間 隻数 候補生成 本数/隻 LP 選択 トータル 改善 2週間 14隻 73秒 70本 0.1秒 0.5秒 5.4% 3週間 224秒 127本 0.2秒 53秒 275秒 6.5% 80秒* 50本* 74秒 154秒 4.5% 4週間 651秒* 300本* 7.8秒 659秒 6.2% 185秒* 100本* 44秒 229秒 25隻 1500秒* 1秒 50秒 1550秒 5% *: 候補スケジュールの生成を途中で打ち切った場合

45 ちなみにＣＰでは、、 これは列生成の結果 期間 隻数 候補生成 本数/隻 LP 選択 トータル 改善 2週間 14隻 73秒 70本
0.1秒 0.5秒 5.4% ２週間１４隻分の配船計画：　列生成では１分超で最も航行距離の小さい計画が求まる、 ところが、CPでは実行可能な計画を１つ見つけるのすら難しい。 たった一つの赤い点を見つける 白い点をどれか一つ見つける ここで扱っている配船計画問題は、CPの適用可能範囲を遙かに超えている 白い点ひとつ見つけるより、たった一つの赤い点を見つける方が遙かに難しい

46 CPでは、３日を超える計画を見つけることは難しい、そこで例えば
これは列生成の結果 期間 隻数 候補生成 本数/隻 LP 選択 トータル 改善 2週間 14隻 73秒 70本 0.1秒 0.5秒 5.4% CPでは、３日を超える計画を見つけることは難しい、そこで例えば １．初日１日分の実行可能な計画をいくつかCPで列挙し、その中から一つを選ぶ ２．次の一定期間（２日程度）のデータについて実行可能な計画を 　　CPによって列挙し、その中から初日とうまくつながるものを選ぶ ３．次の一定期間のデータについて実行可能な計画をCPによって 　　列挙し、その中から2.の期間とうまくつながるものを選ぶ 　　以下、3.を繰り返す。 たった一つの赤い点を見つける 白いものをどれか一つ見つける この方法により、２時間（！！）で 実行可能な計画（白い点）が１つ求まった