항법 그래프와 쿼드트리 기반 항로를 이용한 최적 항해 계획

Abstract

친환경선박과 자율운항선박의 중요성이 증가함에 따라 항로 최적화 기술 역시 주목을 받고 있다. 장거리 항해 계획은 여러 어려움이 따른다. 기상 조건 예측, 효율적인 항로 선택, 항만 및 운항 일정 조정, 그리고 다양한 항법 및 안전 규정 준수 등이 포함된다. 특히 극한 기상 조건은 선박의 안전을 위협하고, 부가 저항을 증가시켜 연료 효율을 감소시킨다. 이에 따라 가장 짧은 항로가 항상 최선의 선택이 아니며, 운항 일정 준수를 위한 속도 최적화가 필요하다. 또한, 국제 해사 규정이나 해양 보호 구역, 해상 안전 규정 등을 준수해야 하기 때문에 항해 계획은 더욱 복잡 해진다. 이런 이유로, 장거리 항해 계획은 전문적인 지식과 경험을 필요로 한다. 장거리 항로 계획을 위해 웨더라우팅 기법을 이용한다. 웨더라우팅은 항해 도중 기상 조건을 고려하여 최적의 항로를 계획하는 과정이다. 이는 선박의 안전을 보장하고, 연료 소비를 줄이며, 항해 시간을 최소화하는 데 도움이 된다. 웨더라우팅은 기상 예보 데이터를 사용하여 바람, 파도, 해류 등의 조건을 분석하고, 이를 바탕으로 최적의 항로를 결정한다. 최적 항로 결정을 위해선 탐색 공간의 정의가 필요하다. 공해 상에선 출발/도착지를 잇는 대권(Great circle) 항로를 기준으로 최적화를 수행할 수 있다. 하지만 항구와 항구를 잇는 대원 항로 사이에는 육지, 섬 등의 장애물이 존재한다. 따라서, 본 연구에서는 최단거리 항로를 기반으로 생성한 항법그래프를 제안하였다. 항법 그래프의 기준 항로를 계산하기 위하여 출발/도착지를 잇는 최단거리 항로를 계산해야 한다. 이를 위해 균일 격자 구조의 GEBCO 수심 데이터를 쿼드트리 그래프로 변환하였다. 쿼드트리 그래프 위에서 다익스트라 알고리즘을 활용하여 초기 항로를 구하였다. 초기 항로를 기준으로 가시성 그래프를 활용한 항로 단순화 방법을 사용하여 불필요한 웨이포인트를 제거하였다. 항로 단순화가 적용된 최단거리 항로를 항법 그래프의 참조 항로로 사용하였다. 참조 항로를 따라가는 선박의 방위각을 기준으로 왼쪽과 오른쪽으로 90도의 각도로 경계선을 정의하였다. 참조항로의 웨이포인트와 두 경계가 만드는 선분을 항법 스테이지로 정의하였다. 인접한 스테이지를 연결하여 항법 그래프를 구성한다. 항법 그래프를 기준으로 항로와 속력을 동시에 최적화하는 항로 최적화 알고리즘을 적용하였다. 3D 동적 프로그래밍 방법을 적용하여 연료 소모량을 최소화하면서 ETA 제한 조건을 만족하는 항로를 탐색한다. 본 연구에서는 항법 그래프를 활용한 웨더라우팅 접근법을 아시아, 대서양, 태평양, 중동 항로 및 파나마 운하와 수에즈 운하를 포함하는 항로에 대해 테스트를 진행하였다. 참조 항로를 설계 속력으로 이동한 기준 항로 대비, 제안된 방법의 연료 소비량을 비교하여 구축된 웨더라우팅 시스템의 유용성을 확인하였다.

With the increasing importance of eco-friendly and autonomous ships, route optimization technology is also gaining attention. Long-distance voyage planning comes with several challenges, including weather condition prediction, efficient route selection, port and operation schedule adjustment, and compliance with various navigation and safety regulations. Extreme weather conditions can threaten ship safety and increase additional resistance, reducing fuel efficiency. Therefore, the shortest route is not always the best choice, and speed optimization is needed to comply with the operation schedule. Also, compliance with international maritime regulations, marine protected areas, and maritime safety regulations makes voyage planning more complex. For these reasons, long-distance voyage planning requires professional knowledge and experience. Weather routing is used for long-distance route planning. Weather routing is the process of planning the optimal route during navigation considering weather conditions. It helps ensure ship safety, reduce fuel consumption, and minimize voyage time. Weather routing uses weather forecast data to analyze conditions such as wind, waves, and currents, and determines the optimal route based on this. To determine the optimal route, it is necessary to define the search space. In the open sea, optimization can be performed based on the great circle route connecting the departure/arrival points. However, there are various obstacles such as land and islands between the great circle routes connecting ports. Therefore, in this study, a navigation graph based on the shortest route was proposed. To calculate the reference route of the navigation graph, it is necessary to calculate the shortest route connecting the departure/arrival points. For this, the uniform grid structure of GEBCO bathymetric data was converted into a quadtree graph. The initial route was obtained using the Dijkstra algorithm on the quadtree graph. The initial route was simplified using a visibility graph-based route simplification method to remove unnecessary waypoints. The simplified shortest route was used as the reference route of the navigation graph. The boundary line was defined at an angle of 90 degrees to the left and right based on the bearing of the ship following the reference route. The line segment made by the waypoint of the reference route and the two boundaries was defined as the navigation stage. Adjacent stages are connected to form a navigation graph. A route optimization algorithm that simultaneously optimizes the route and speed based on the navigation graph was applied. A 3D dynamic programming method was applied to search for a route that minimizes fuel consumption while satisfying the ETA limit condition. In this study, a weather routing approach using a navigation graph was tested on routes including Asia, Atlantic, Pacific, Middle East routes, and the Panama Canal and Suez Canal. The usefulness of the constructed weather routing system was confirmed by comparing the fuel consumption of the proposed method with the reference route moved at the design speed.