具海象資料之電子海圖上航路規劃

Efficient Route Planning for ECDIS with Current

為有效維持船舶航路規劃，本文提出一套新的演算法，針對網格化後的電子海圖，船舶由出發港至目的港航路，當遭受海象因素影響下，船舶應如何克服海象影響仍能維持最佳航路規劃。因此，本文藉向量解析概念，導入船艏向來修正航路，俾能維持在原先所規劃路徑。規劃船舶最佳航路時，於每一時間點探討取決船舶應該前進的下一個最佳位置，並以高維迷宮式搜尋演算法為核心演算法。最後，將提出一套創新的具水流之網格圖最佳航路演算法來完成船舶航路規劃，其時間複雜度為O(qN)，空間複雜度為O(N)。其中q 為高維迷宮式搜尋演算法執行的次數，N 代表網格圖中所有網格的數目，且q < N。

Environment is an important factor for route planning problem at sea. The course of the ship will be changed by environment current. To overcome the problem, this study presented an efficient method to search optimal route from source to destination for ECDIS with current on raster. The algorithm is proposed by using the concepts of heading and vector to correct course for ship navigation. The algorithm will decide the optimal route based on Higher Geometry Maze Router. The time and space complexities of the algorithm are O(qN) and O(N), respectively, where N is the number of cells on raster and q is the number of Higher Geometry Maze Router function called and q < N.