Presentation is loading. Please wait.

Presentation is loading. Please wait.

到着時刻と燃料消費量を同時に最適化する船速・航路計画

Similar presentations


Presentation on theme: "到着時刻と燃料消費量を同時に最適化する船速・航路計画"— Presentation transcript:

1 到着時刻と燃料消費量を同時に最適化する船速・航路計画

2 目的 出発港から到着港まで運行する船舶の運行計画を作成すること 通る航路と、各区間の船速の両方を同時に最適化する
所要時間と、燃料消費量を同時に考慮するのが特徴

3 動機 運行計画の最適化の研究はいくつかある 多くの研究は、一つの目的(例えば所要時間)を最適化するモデル化を採用
実際には2目的を考慮しなければいけない場合が多いので、さまざまな工夫を追加して答えを導いている 「2目的最短路問題」を使えば、2目的を同時に最適化できることを紹介する

4 アプローチ 海域上に格子点を設定する 通る可能性のある2点間に枝を設定する
その2点間を航行するのに要する所要時間と燃料消費量を計算し、設定する その点を通る最早時刻と最遅時刻を設定 「2目的最短路問題」を解く。 航路はこの解として得られる。通る枝を順に並べたものとして得られる。

5 最短路問題は高速に解くことができる(多項式時間のアルゴリズム)
最初が点iで最後が点jとなる点の列を、iからjへのパスという (例: 0 -> 5 -> 2 -> 6は、0から6へのパス)。 2点を結ぶ枝には、「長さ」が定義されている。 iからjへのパスで、そのパスに含まれる枝の長さの総和を、「パスの長さ」という。 ある点から、各点への長さ最小のパスを求める問題を、「最短路問題」という。 最短路問題は高速に解くことができる(多項式時間のアルゴリズム) 超大規模な問題でも解ける(例:数百万点のネットワーク) 6 2 9 8 1 5 10

6 航路のみの計画で、目的が一つであれば、「最短路問題」でモデル化できる
出発地を     で表し、到着地を     で表す。 海域上に適宜点を設定し、通る可能性のある2点間には枝を設定し、その枝の長さは所要時間(または燃料消費量)とする。 これで最短路問題と解くと、出発地     から到着地     までのパスで、所要時間(または燃料消費量)が最小のものが求まる。 6 2 9 8 1 5 10 最小所要時間:5+6=11

7 最適化アルゴリズムと、船舶性能評価手法の分離
注意 海域上に適宜点を設定し、通る可能性のある2点間には枝を設定し、その枝の長さは所要時間とする。 海域上の2点間の所要時間は、数値として与えればよい。 最適化アルゴリズムと、船舶性能評価手法の分離 現在の船舶性能評価手法の元で、最適な航路が求まる。 評価精度が上がり、与える数値の精度があがれば、 最適化アルゴリズムの変更無しに、より精度の高い計画が得られる。

8 注意 海域上の2点間の所要時間は、数値として与えればよい。 2点間の所要時間、燃料消費量を計算するためには、
どのような気象条件を取り入れても良いし、どのような 評価モデルを用いても良い。

9 最短路問題 0 6 出発地を で表し、到着地を で表す。
出発地を     で表し、到着地を     で表す。 海域上に適宜点を設定し、通る可能性のある2点間には枝を設定し、その枝の長さは所要時間とする。 これで最短路問題と解くと、出発地     から到着地     までのパスで、所要時間が最小のものが求まる。 6 2 9 8 1 5 10 最小所要時間:5+6=11

10 問題点 2点間は、1つの速度しか設定できない。 →同じ2点間でも、運行速度は変えてよいはず。
( から     へは、11knotで走るか、12knotで走るか、13knotで走るか) 6 2 9 8 1 5 10 最小所要時間:5+6=11

11 船速と航路を同時に最適化 2点間を航行する船速(または回転数)が3とおりある場合のモデル化 →2点間に、各船速に対応した枝を並行して張る
長さ5 長さ5 1 2 12knot 12knot 11knot 11knot 1 2 12knot 12knot 13knot 13knot

12 船速と航路を同時に最適化 2点間を航行する船速(または回転数)が3とおりある場合のモデル化 →2点間に、各船速に対応した枝を並行して張る
長さ5.3 長さ5.3 11knot 11knot 長さ5 1 長さ5 2 12knot 12knot 長さ4.8 長さ4.8 13knot 13knot 最短路問題の答えは、例えば上の赤矢印のように得られる。 この場合、点0から1へ1knotで、点1から点2へ13knotで運行すればよい。 すなわち、船速と航路を同時に最適化していることになる。

13 船速と航路を同時に最適化 2点間に複数の枝があっても、最短路問題は問題なく解ける。
1本の場合よりも計算量は増えるが、船速・航路計画で現れる最短路問題は 小規模なもの(内航船で点が数百個、枝が数千点)なので、高速に解けると 考えてよい。 5 5 6 2 9 8 2 6 1 8 10

14 所要時間と燃料消費量を同時に (いったん、最初に導入した最短路に戻ります) 2点間に2つの長さを定義した拡張が可能
2点間には、1つの長さ(所要時間または燃料消費量)のみを設定した。 2点間に2つの長さを定義した拡張が可能 6 2 9 8 1 5 10

15 所要時間と燃料消費量を同時に 2点間に2つの長さを定義した拡張が可能 2点間には、1つの長さ(所要時間または燃料消費量)のみを設定した。
これを「2目的最短路問題」とよぶ 1番目の長さを所要時間、2番目の長さを燃料消費量とすると、 (6,10) (2,10) (9,2) (8,3) (2,18) (1, 21) (6,4) (5,11) (10,2) (5, 6) (11,10) (19,4)

16 所要時間と燃料消費量を同時に 2点間に2つの長さを定義した拡張が可能 1番目の長さを所要時間、2番目の長さを燃料消費量とすると、
所要時間を最小にするなら、赤いパス(所要時間11、燃料消費量21) 燃料消費量を最小にするならば、青いパス(所要時間19、燃料消費量14) (6,3) (2,4) (9,5) (8,1) (2,18) (1, 21) (6,12) (8,3) (5,11) (10,9) (5, 9) (11,21) (19,14)

17 所要時間がTまで許されるのならば、燃料消費量がFで済むパスが存在する。
所要時間と燃料消費量を同時に 所要時間を最小にするなら、赤いパス(所要時間11、燃料消費量21) 燃料消費量を最小にするならば、青いパス(所要時間19、燃料消費量14) 他にも、許される所要時間に従って、燃料消費量を最小にするパスを見つける  ことができる. 所要時間がTまで許されるのならば、燃料消費量がFで済むパスが存在する。 (6,3) (2,4) (9,5) (8,1) (2,18) (1, 21) (6,12) (8,3) (5,11) (10,9) (5, 9) (T, F) (11,21) (19,14) (14,19) (24,13) .

18 終点でのラベルを求める (T, F) 所要時間がTまで許されるのならば、 (11,21) 燃料消費量がFで済むパスが存在する。
(19,14) (14,19) (24,13) . この、(T,F)の組を、「ラベル」とよぶことにする。 終点(この例では点  )でのラベルにより、許される所要 時間T以内のパスの中で燃料消費量が最小のものがわかる。 この、終点での「ラベル」を効率的に求めるアルゴリズムが M.Desrochers, F.Soumis, A Generalized Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows, INFOR vol.26, no.3, 1988 で提案されている。 擬多項式時間アルゴリズムであるが、船速・航路計画で用いる比較的小規模なネットワークであれば、十分高速に動作する場合が多い。

19 終点でのラベルを求める (T, F) 所要時間がTまで許されるのならば、 (11,21) 燃料消費量がFで済むパスが存在する。
(19,14) (14,19) (24,13) . この、(T,F)の組を、「ラベル」とよぶことにする。 終点(この例では点  )でのラベルにより、許される所要 時間T以内のパスの中で燃料消費量が最小のものがわかる。 この(T,F)の要素は、「非劣解」とよばれるものである。 これらの集合は、経済学などでいうところの「効率的フロンティア」にあたる。 燃料消費量F (11,21) (14,19) (19,14) (24,13) 所要時間T

20 まとめ 1 最初に、2点間に並行に各船速に対応した枝を張ることにより、船速と航路を同時に最適化するためのモデル化を紹介した。
まとめ 1 最初に、2点間に並行に各船速に対応した枝を張ることにより、船速と航路を同時に最適化するためのモデル化を紹介した。 次に、各枝に2つの目的(所要時間と燃料消費量を想定)を設定することにより、所要時間の制限内に到着するパスの中で、燃料消費量を最小にするものを見つけるモデル化を紹介した。

21 まとめ 2 これらの2つのモデルを組み合わせることで、 所要時間と燃料消費量を同時に考慮したね 船速と航路を同時に最適化する計画
まとめ 2 これらの2つのモデルを組み合わせることで、 所要時間と燃料消費量を同時に考慮したね 船速と航路を同時に最適化する計画 を計算することができる。 航路計画を多目的最適化問題として定式化し、遺伝的アルゴリズムを使う方法が報告されている。遺伝的アルゴリズムは、汎用的であるという長所の一方で、綿密なチューニングを施さなければ、あまり良くない局所最適解に陥るという短所がある。 「多目的」が「2目的」である場合は、ここで紹介したモデル化と計算手法も検討する価値がある。このアルゴリズムでは、必ず「大域的最適解」が求まる。


Download ppt "到着時刻と燃料消費量を同時に最適化する船速・航路計画"

Similar presentations


Ads by Google