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

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

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

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

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

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

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

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

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

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

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

10 問題点 2点間は、１つの速度しか設定できない。 →同じ２点間でも、運行速度は変えてよいはず。
（ から　　　　　へは、１１knotで走るか、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 最短路問題の答えは、例えば上の赤矢印のように得られる。 この場合、点０から１へ1knotで、点１から点２へ13knotで運行すればよい。 すなわち、船速と航路を同時に最適化していることになる。

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

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

15 所要時間と燃料消費量を同時に ２点間に２つの長さを定義した拡張が可能 ２点間には、１つの長さ（所要時間または燃料消費量）のみを設定した。
これを「２目的最短路問題」とよぶ １番目の長さを所要時間、２番目の長さを燃料消費量とすると、 ０ １ ２ ４ ５ ６ (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 所要時間と燃料消費量を同時に ２点間に２つの長さを定義した拡張が可能 １番目の長さを所要時間、２番目の長さを燃料消費量とすると、
所要時間を最小にするなら、赤いパス（所要時間１１、燃料消費量２１） 燃料消費量を最小にするならば、青いパス（所要時間１９、燃料消費量１４） ０ １ ２ ４ ５ ６ (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で済むパスが存在する。
所要時間と燃料消費量を同時に 所要時間を最小にするなら、赤いパス（所要時間１１、燃料消費量２１） 燃料消費量を最小にするならば、青いパス（所要時間１９、燃料消費量１４） 他にも、許される所要時間に従って、燃料消費量を最小にするパスを見つける 　ことができる. 所要時間が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)の組を、「ラベル」とよぶことにする。 終点（この例では点　　）でのラベルにより、許される所要 時間Ｔ以内のパスの中で燃料消費量が最小のものがわかる。 ６ この、終点での「ラベル」を効率的に求めるアルゴリズムが 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,F)の要素は、「非劣解」とよばれるものである。 これらの集合は、経済学などでいうところの「効率的フロンティア」にあたる。 燃料消費量F (11,21) (14,19) (19,14) (24,13) 所要時間T

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

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