最短路問題から船速・航路計画同時最適化へ

到着時刻と燃料消費量を同時に
最適化する船速・航路計画
目的
• 出発港から到着港まで運行する船舶の運行
計画を作成すること
• 通る航路と、各区間の船速の両方を同時に
最適化する
• 所要時間と、燃料消費量を同時に考慮する
のが特徴
動機
• 運行計画の最適化の研究はいくつかある
• 多くの研究は、一つの目的（例えば所要時
間）を最適化するモデル化を採用
• 実際には２目的を考慮しなければいけない場
合が多いので、さまざまな工夫を追加して答
えを導いている
• 「２目的最短路問題」を使えば、２目的を同時
に最適化できることを紹介する
アプローチ
• 海域上に格子点を設定する
• 通る可能性のある２点間に枝を設定する
• その２点間を航行するのに要する所要時間と
燃料消費量を計算し、設定する
• その点を通る最早時刻と最遅時刻を設定
• 「２目的最短路問題」を解く。
• 航路はこの解として得られる。通る枝を順に
並べたものとして得られる。
最短路問題
最初が点iで最後が点jとなる点の列を、iからjへのパスという
（例： 0 -> 5 -> 2 -> 6は、0から6へのパス）。
２点を結ぶ枝には、「長さ」が定義されている。
iからjへのパスで、そのパスに含まれる枝の長さの総和を、「パスの長さ」という。
ある点から、各点への長さ最小のパスを求める問題を、「最短路問題」という。
最短路問題は高速に解くことができる（多項式時間のアルゴリズム）
超大規模な問題でも解ける（例：数百万点のネットワーク）
5
０
１
6
9
2
４
8
5
２
2
6
1
５
10
8
６
航路のみの計画
航路のみの計画で、目的が一つであれば、「最短路問題」でモデル化できる
•出発地を０
で表し、到着地を６で表す。
•海域上に適宜点を設定し、通る可能性のある２点間には枝を設定し、その枝
の長さは所要時間（または燃料消費量）とする。
•これで最短路問題と解くと、出発地０
から到着地６までのパスで、
所要時間（または燃料消費量）が最小のものが求まる。
5
5
０
１
２
6
9
2
４
8
2
6
1
５
10
8
６
最小所要時間：5+6=11
注意
海域上に適宜点を設定し、通る可能性のある２点間には枝を設定し、
その枝の長さは所要時間とする。
海域上の２点間の所要時間は、数値として与えればよい。
最適化アルゴリズムと、船舶性能評価手法の分離
現在の船舶性能評価手法の元で、最適な航路が求まる。
評価精度が上がり、与える数値の精度があがれば、
最適化アルゴリズムの変更無しに、より精度の高い計
画が得られる。
注意
海域上の２点間の所要時間は、数値として与えればよい。
２点間の所要時間、燃料消費量を計算するためには、
どのような気象条件を取り入れても良いし、どのような
評価モデルを用いても良い。
最短路問題
•出発地を０で表し、到着地を６で表す。
•海域上に適宜点を設定し、通る可能性のある２点間には枝を設定し、その枝
の長さは所要時間とする。
•これで最短路問題と解くと、出発地０
から到着地６
までのパスで、
所要時間が最小のものが求まる。
5
０
１
6
9
2
４
8
5
２
2
6
1
５
10
8
６
最小所要時間：5+6=11
問題点
2点間は、１つの速度しか設定できない。
→同じ２点間でも、運行速度は変えてよいはず。
（
０
１
から
へは、１１knotで走るか、12knotで走るか、13knotで走るか）
5
０
１
6
9
2
４
8
5
２
2
6
1
５
10
8
６
最小所要時間：5+6=11
船速と航路を同時に最適化
2点間を航行する船速（または回転数）が3とおりある場合のモデル化
→2点間に、各船速に対応した枝を並行して張る
長さ5
0
長さ5
1
12knot
12knot
11knot
0
12knot
13knot
2
11knot
1
12knot
13knot
2
船速と航路を同時に最適化
2点間を航行する船速（または回転数）が3とおりある場合のモデル化
→2点間に、各船速に対応した枝を並行して張る
0
長さ5.3
長さ5.3
11knot
11knot
長さ5
12knot
1
長さ5
12knot
長さ4.8
長さ4.8
13knot
13knot
2
最短路問題の答えは、例えば上の赤矢印のように得られる。
この場合、点０から１へ1knotで、点１から点２へ13knotで運行すればよい。
すなわち、船速と航路を同時に最適化していることになる。
船速と航路を同時に最適化
2点間に複数の枝があっても、最短路問題は問題なく解ける。
１本の場合よりも計算量は増えるが、船速・航路計画で現れる最短路問題は
小規模なもの（内航船で点が数百個、枝が数千点）なので、高速に解けると
考えてよい。
5
０
6
9
2
４
8
5
１
２
2
6
1
５
10
8
６
所要時間と燃料消費量を同時に
（いったん、最初に導入した最短路に戻ります）
２点間には、１つの長さ（所要時間または燃料消費量）のみを設定した。
•２点間に２つの長さを定義した拡張が可能
5
０
１
6
9
2
４
8
5
２
2
6
1
５
10
8
６
所要時間と燃料消費量を同時に
２点間には、１つの長さ（所要時間または燃料消費量）のみを設定した。
•２点間に２つの長さを定義した拡張が可能
これを「２目的最短路問題」とよぶ
•１番目の長さを所要時間、２番目の長さを燃料消費量とすると、
０
(5, 6)
１
２
(2,18)
(6,10)
(9,2)
(2,10)
４
(5,11)
(8,3)
(1, 21)
５
(10,2)
(6,4)
(8,3)
６
(11,10)
(19,4)
所要時間と燃料消費量を同時に
•２点間に２つの長さを定義した拡張が可能
•１番目の長さを所要時間、２番目の長さを燃料消費量とすると、
•所要時間を最小にするなら、赤いパス（所要時間１１、燃料消費量２１）
•燃料消費量を最小にするならば、青いパス（所要時間１９、燃料消費量１４）
(5, 9)
０
１
２
(2,18)
(6,3)
(9,5)
(2,4)
４
(5,11)
(8,1)
(1, 21)
５
(10,9)
(6,12)
(8,3)
６
(11,21)
(19,14)
所要時間と燃料消費量を同時に
•所要時間を最小にするなら、赤いパス（所要時間１１、燃料消費量２１）
•燃料消費量を最小にするならば、青いパス（所要時間１９、燃料消費量１４）
•他にも、許される所要時間に従って、燃料消費量を最小にするパスを見つける
ことができる.
所要時間がTまで許される
のならば、燃料消費量がF
で済むパスが存在する。
(5, 9)
０
１
(5,11)
２
(T, F)
(2,18)
(6,3)
(9,5)
(2,4)
４
(8,1)
(1, 21)
５
(10,9)
(6,12)
(8,3)
６
(11,21)
(19,14)
(14,19)
(24,13)
.
.
.
終点でのラベルを求める
(T, F)
(11,21)
(19,14)
(14,19)
(24,13)
.
.
所要時間がTまで許されるのならば、
燃料消費量がFで済むパスが存在する。
この、(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
で提案されている。
擬多項式時間アルゴリズムであるが、船速・航路計画で用いる比較的小規模な
ネットワークであれば、十分高速に動作する場合が多い。
終点でのラベルを求める
(T, F)
(11,21)
(19,14)
(14,19)
(24,13)
.
.
所要時間がTまで許されるのならば、
燃料消費量がFで済むパスが存在する。
この、(T,F)の組を、「ラベル」とよぶことにする。
終点（この例では点６）でのラベルにより、許される所要
時間Ｔ以内のパスの中で燃料消費量が最小のものがわかる。
この(T,F)の要素は、「非劣解」とよばれるものである。
これらの集合は、経済学などでいうところの「効率的フロンティア」に
あたる。
燃料消費量F
(11,21)
(14,19)
(19,14)
(24,13)
所要時間T
まとめ 1
•最初に、２点間に並行に各船速に対応した枝を張るこ
とにより、船速と航路を同時に最適化するためのモデ
ル化を紹介した。
•次に、各枝に２つの目的（所要時間と燃料消費量を想
定）を設定することにより、所要時間の制限内に到着
するパスの中で、燃料消費量を最小にするものを見つ
けるモデル化を紹介した。
まとめ 2
•これらの２つのモデルを組み合わせることで、
1. 所要時間と燃料消費量を同時に考慮したね
2. 船速と航路を同時に最適化する計画
を計算することができる。
航路計画を多目的最適化問題として定式化し、遺伝的ア
ルゴリズムを使う方法が報告されている。遺伝的アルゴリ
ズムは、汎用的であるという長所の一方で、綿密なチュー
ニングを施さなければ、あまり良くない局所最適解に陥ると
いう短所がある。
「多目的」が「２目的」である場合は、ここで紹介したモデル
化と計算手法も検討する価値がある。このアルゴリズムで
は、必ず「大域的最適解」が求まる。

Download Report