저항성능은 식 (2)를 기반으로 하여 계산한다 (ISO, 2002).

식 (2)에서 R_TT는 운항 중 선박의 전 저항, R_TS는 정수 중 선박의 전 저항, ∆R_Wave는 파랑 부가저항, ∆R_Air는 바람 부가저항을 의미한다. 전 저항은 정수 중 선박의 전 저항, 파랑 부가저항, 바람 부가저항을 합한 값이다.

정수 중 전 저항은 식 (3)을 기반으로 하여 계산한다 (ISO, 2002). 식 (3)에서 ρ는 해수 밀도, S는 침수 표면적, S_BK는 빌지 킬 침수 표면적, C_FS는 평판마찰계수, ∆C_F는 마찰수정계수, C_R은 잉여저항계수이다. 평판마찰계수는 ITTC 1957 추정식을 사용하며 식 (4)와 같이 계산한다. 식 (4)에서 Rn은 레이놀즈 수이다.

파랑 부가저항은 식 (5)를 기반으로 하여 계산한다 (ISO, 2002). 식 (5)에서 ｆ는 입사파의 주파수, Ｇ는 입사파의 방향 분포, S(f)는 입사파의 주파수 분포, α는 입사파의 방향, ∆ｒ/ξ²_A는 규칙파 중 응답함수이다. 바람 부가저항은 식 (6)을 기반으로 하여 계산한다 (ISO, 2002). 식 (6)에서 ρ_A는 공기 밀도, A_T는 수면 아래 정면 방향 투영면적, V_R은 바람에 대한 선박의 상대 속력, C_AA0는 정면 공기저항계수, ｋ(θ)는 풍향영향계수이다. 정면 공기저항계수와 풍향영향계수는 ISO 15016:2002를 기반으로 하여 계산한다.

연료 소모량을 계산하기 위해서 제동 동력을 계산해야 하며 제동 동력은 저항과 선박 계수를 이용하여 계산한다. 유효동력, 전달동력, 제동 동력은 식 (7), (8), (9)와 같이 표현된다.

P_E는 유효동력, P_D는 전달동력, P_B는 제동 동력, Ｖ는 선박의 속력, η_D는 추진효율, η_T는 축 전달효율이다. 식 (7)에서 선박의 속력은 시운전 자료를 기반으로 선박의 속력과 엔진 회전수 상관관계를 이용하여 계산한다.

추진효율과 축 전달효율은 식 (10)을 기반으로 하여 계산한다. η_H는 선각효율,η_R은 상대회전효율,η_O는 프로펠러 단독효율, ｔ는 추진감소계수, ω는 반류계수이다.

선박의 속도에서 조류는 상대속도로 반영되어 연료 소모량을 추정하기 위해 사용된다. 조류가 있으면 표류 때문에 원하는 위치로 갈 수 없으므로 적절한 방향각의 조절이 필요하다. 방향각 조절 값 θ는 식 (11)을 통해 구할 수 있다 (Park and Kim, 2014).

식 (11)에서 V는 선박의 속력, ｕ_cx는 조류의 x축 성분, ｕ_cy 는 조류의 y축 성분을, p는 실제 선박의 진행 방향을 의미한다. 위 식을 방향각 조절 값 θ에 대해 정리하면 선박 속력의 변화 δV를 식 (12)와 같이 쓸 수 있다.

앞서 계산한 제동 동력과 조류에 의한 선속 변화를 고려하여 연료 소모량을 추정할 수 있다. 식 (13)은 전체 항로를 N개로 나누어 구간별로 제동 동력과 선박의 속력을 계산하여 총 연료 소모량을 계산하는 식이다.

식 (13)에서 N은 구간, ｆ_rate는 시간, 마력당 연료 소모량, P_B(ｎ_i)는 엔진 회전수가 ｎ_i일 때 제동 동력, ｌ_i는 항해 거리, V(ｎ_i)는 엔진 회전수가 ｎ_i일 때 선박의 속력, δV는 조류에 의한 선박의 속력 변화량이다. 엔진 회전수와 해상 상태에 따라 연료 소모량이 달라지며 제동 동력과 선박의 속력을 계산하여 연료 소모량을 계산한다.

A* 알고리즘은 경로 탐색에 많이 사용되는 알고리즘으로 전역 최적 해에 가까운 지역 최적 해를 찾으며 계산 시간이 짧아 많이 사용되는 알고리즘이다. 본 연구는 실공간에서 항로를 탐색해야 하므로 Dijkstra 알고리즘과 같은 그래프 기반 알고리즘을 사용하기 어려워 A* 알고리즘을 사용하였다. 격자 기반이 아닌 실공간에서 A* 알고리즘을 사용하여 경로를 탐색하기 때문에 잘못된 지역 최적 해를 찾아낼 가능성이 있다. 이러한 단점을 보완하기 위해 A* 알고리즘을 변형한 Sparse A* 알고리즘을 사용하였다 (Szczerba, 2000).

동일한 환경에서 A* 알고리즘은 전역 최적화 방법인 Dijkstra 알고리즘에 비해 계산 시간은 21.9%, 연산량은 30.7% 낮다 (Yukel & Sezgin, 2005). 또한, 최적 경로 문제에서 유전 알고리즘을 사용할 때 연산량이 크게 증가하는 부분은 장애물과 간섭을 계산하는 부분이다 (Szlapczynska & Smierzchalski, 2007). 연안에는 육지와 섬이 다수 존재하기 때문에 Dijkstra 알고리즘을 사용할 때 격자를 조밀하게 생성해야 하며 이는 연산량이 크게 증가하는 이유가 된다. 격자를 생성하지 않는 유전 알고리즘을 사용하면 장애물과 간섭을 반복적으로 계산하므로 불필요한 연산시간이 증가한다. 이러한 이유로 본 논문에서는 격자를 생성하지 않고 장애물과 간섭 계산을 최소화하여 빠른 시간 내에 최적 경로를 계산하는 Sparse A* 알고리즘을 사용하였다.

Sparse A* 알고리즘은 최소 힙(min heap)을 이용하여 잘못된 지역 최적 해를 찾는 경우를 방지하도록 설계된 알고리즘이다. 알고리즘을 사용하는 데 필요한 변수는 시작점, 도착점, 최소 탐색 길이, 최대 회전 각도, 탐색 방향 수, 최대 항로 길이이다. 탐색 방향 수는 최대 회전 각도 내 이동 가능한 위치의 수를 의미한다. 탐색 방향 수가 많을수록 더 좋은 해를 찾을 수 있지만, 알고리즘의 연산 시간이 증가한다. 최대 항로 길이는 장애물을 만났을 때 너무 멀리 돌아가는 것을 방지하기 위해 설정한다. 알고리즘의 수행 과정은 다음과 같다.

(1) Step 1. 비용이 0인 시작점을 갖는 최소 힙을 생성한다.

(2) Step 2. 최소 힙 최상단 노드(root)의 경로를 불러와 마지막 위치를 현재 위치로 설정한다. 현재 위치에서 진행 방향으로 최대 회전 각도 내 최소 탐색 길이만큼 이동 가능한 위치를 탐색한다. 진행 방향이 없는 시작점에서는 360° 방향으로 이동 가능한 위치를 탐색한다.

(3) Step 3. 현재 위치에서 이동 가능한 위치까지의 비용 함수를 계산한다. 시작점부터 현재 위치까지 이동한 거리와 현재 위치에서 도착점까지 직선거리의 합이 최대 항로 길이보다 작거나 같으면 계산한 비용과 경로를 최소 힙에 추가한다.

(4) Step 4. 현재 위치에서 이동 가능한 위치가 없으면 최소 힙의 최상단 노드(root)를 제거한다.

(5) Step 5. 현재 위치와 도착점의 거리가 최소 탐색 길이보다 작을 때까지 최소 힙의 최상단 노드에 대해 Step 2-4를 반복한다.

(6) Step 6-1. 현재 위치와 도착점의 거리가 최소 탐색 길이보다 작으면 도착점을 경로에 추가하여 비용을 업데이트하고 알고리즘을 종료한다.

(7) Step 6-2. 현재 위치와 도착점의 거리가 최소 탐색 길이보다 크지만, 최소 힙이 비어 있어 탐색을 진행할 수 없을 때 알고리즘을 종료한다. 이러한 경우는 해를 찾지 못한 경우이며 최대 회전 각도나 탐색 회수와 같은 알고리즘 변수를 변경하여 알고리즘을 수행하면 경로를 찾을 수 있다.

Sparse A* 알고리즘은 Fig. 2와 같이 현재 위치에서 갈 수 있는 모든 위치에서 평가함수를 계산하고 평가함수가 가장 작은 위치로 이동하는 단계를 반복하여 수행한다. A* 알고리즘을 실공간에서 그대로 사용하게 되면 Fig. 2의 파란색 경로와 같이 지역 최적 해에 빠질 가능성이 있다. Sparse A* 알고리즘 중 최소 힙을 사용하여 지역 최적 해에 빠질 가능성을 최소화하였다.

Fig. 2 
Comparison between A* and Sparse A* algorithm

평가함수를 계산하기 위해 엔진 회전수를 설정해야 하며 알고리즘을 시작할 때 엔진 회전수는 가능한 엔진 회전수 중 가장 작은 값으로 설정한다. 출항지와 입항지까지 소요된 시간이 제약 조건을 위반하면 엔진 회전수를 증가시킨다. 소요된 시간이 주어진 항해 시간과 차이가 없을 때까지 A* 알고리즘을 반복 수행하여 최적 엔진 회전수를 계산한다.

식 (16)과 같이 평가함수 f(ｘ)를 비용 함수 ｇ(ｘ)와 휴리스틱 함수 ｈ(ｘ)의 합으로 나타내었다. ｇ(ｘ)는 현재 위치에서 위치 x까지 도달하는데 드는 비용이며 ｈ(ｘ)는 위치 x에서 도착지까지 드는 비용이다.

비용 함수는 식 (17)과 같이 정의하였다. 식 (17)에서 ｆ_rate는 시간, 마력당 연료 소모량, P_B(ｎ)은 엔진 회전수 ｎ일 때 해상 상태를 고려하여 다음 위치로 가는데 필요한 제동 동력, d_x는 현재 위치에서 다음 위치 x까지의 거리, v(ｎ)은 엔진 회전수 ｎ일 때 속력이다. 현재 위치에서 다음 위치 x까지의 거리와 엔진 회전수를 이용하여 비용 함수를 계산한다.

휴리스틱 함수는 식 (18)과 같이 정의하였다. 휴리스틱 함수에서 d_x-final은 다음 위치 x에서 도착지까지의 거리, gr(x)는 선저여유수심을 고려한 좌초 여부이다. 식 (19)와 같이 gr(x)를 계산하며 다음 위치 x에서 좌초가 일어나면 gr(x)의 값을 ∞로 설정하여 탐색할 수 없는 위치로 설정하였다. 현재 위치에서 다음 위치 x까지의 엔진 회전수와 다음 위치 x에서 도착지까지의 속력이 같고 해상 상태가 같다는 가정을 적용하여 식 (18)의 제동 동력 PB(n)은 비용 함수에서 계산한 결과를 사용하였다.

Sparse A* 알고리즘으로 초기 항로를 탐색하면 많은 변침점이 생성되며 이 중 상당수는 불필요하다. 따라서 항로를 단순화하는 후처리 과정을 통해 불필요한 변침점을 제거해야 한다. 본 연구에서는 항로를 단순화하기 위해 Douglas-Peucker 알고리즘을 사용하였다 (Douglas & Peucker, 1973).

Douglas-Peucker 알고리즘 과정은 Fig. 3에 나타내었다. 초기 항로에서 시작점과 끝점을 잇는 직선을 구하고 그 직선에서 가장 거리가 먼 점을 찾는다 (Fig. 3(a), Fig. 3(b)). 그 거리가 설정한 임계 거리보다 크다면 거리가 먼 점을 그대로 유지한다. 초기 항로의 모든 점에 대해 이 과정을 반복 수행한다 (Fig. 3(c), Fig. 3(d)). 임계 거리보다 작은 모든 점을 제거하면 Fig. 3(e)와 같이 단순화된 항로를 얻게 된다. 초기 항로를 단순화할 때 육지나 섬과 같은 장애물과 교차하는지 확인해야 하며 장애물과 교차할 경우 임계 거리가 작더라도 변침점을 제거하지 않는다.

Fig. 3 
Example of route simplification Douglas-Peucker algorithm

Fig. 4는 임계 거리에 따른 항로 단순화 결과이다. Fig. 4(a)는 적당한 임계 거리를 설정하여 최적 해의 손실 없이 단순화된 결과이며 Fig. 4(b)는 너무 큰 임계 거리를 설정하여 최적 해의 손실이 일어난 결과이다. 임계 거리를 크게 하면 최적 해의 손실이 일어날 수 있어 적당한 값을 선택해야 한다. 식 (20)에서 임계 거리 ε는 Sparse A* 알고리즘에 사용한 최소 탐색 길이 (L)와 단순화하는 부분의 변침점과 가장 가까운 장애물과 거리 (D(x)) 중 작은 값을 이용하여 계산한다. 주변에 장애물 존재 여부에 따라 임계 거리가 달라지도록 하여 장애물 근처의 항로는 단순화되지 않도록 설정하였다.

Fig. 4 
Example of route simplification according to threshold distance

앞서 언급한 방법을 이용하여 항로를 결정하였으므로 연료 소모량이 최소가 되는 최적의 엔진 회전수를 찾아야 한다. 2장에서 설명한 최적화 모델 중 항로 탐색 알고리즘을 수행하여 항로 위치가 결정되었으므로 연료 소모량이 최소가 되는 엔진 회전수를 찾아야 한다. 설계 변수인 항로 위치를 제외하고 엔진 회전수에 대해 최적화 모델을 구성하여 최적의 엔진 회전수를 계산한다. 최적화 모델은 목적함수와 제약 조건식 (1)에서 항로의 위치 (X)를 제외하여 설정한다.

위 연료 소모량 최소화 모델은 비선형이며 제약 조건이 있으므로 제약 조건이 있는 비선형 최적화 모델이다. 이러한 최적화 문제를 푸는 방법으로 SQP (Sequential Quadratic Programming) 방법을 사용하였다.

Table 1은 시뮬레이션에서 사용된 선박의 제원 및 주요 계수를 나타낸 표이다.

정수 중 선박의 속력을 초당 엔진 회전수 n에 관한 함수로 표현하면 식 (21)과 같다. V의 단위는 m/s이고 n의 단위는 RPS (revolution per second)이다.

본 연구에서 시뮬레이션 조건은 다음과 같다. Sparse A* 알고리즘을 수행할 때 현재 위치에서 다음 위치까지의 거리인 최소 탐색 길이를 1 km로 설정하였다. 총 항해 시간의 제약 조건은 4시간 30분이며 목포에서 10시에 출항하는 시나리오이다. 목포항 항만시설 운영세칙에 따라 목포항 주변에서 제한 속력 12노트를 넘지 않도록 제약 조건을 설정하였다. 주기관의 시간, 마력 당 연료 소모량은 125 g/ps·h이다. 육지, 섬, 수심 자료는 전자해도 정보를 기반으로 하였으며 기상정보는 Beaufort Number (BN)에 기반하여 4km 격자를 사용하였다. BN은 Table 2에 나타낸 3~6 사이의 값을 사용하였으며 조류의 속도 범위는 2m/s 이내의 값을 설정하였다 (Huler, 2005).

Fig. 5는 최적 항로 알고리즘을 이용하여 목포(A)에서 출항하여 제주(B)에 입항하는 항로를 계산한 결과이다. 본 시뮬레이션에서 선박은 A와 B 사이를 항해하며 기상조건을 고려하지 않은 항로 1과 기상 조건을 고려한 항로 2를 계산하였다. 항로 1과 항로 2의 계산 시간은 각각 6.8초, 8.7초였으며 기상 조건의 고려 여부로 인해 계산 시간의 차이가 발생했다. 기상조건은 Fig. 5(b)와 같이 특정 구역에서 BN이 높았다.

Fig. 5 
(a) The route between Mokpo and Jeju (left)(b) Determination of route based on Beaufort Number (right)

기상조건에 따라 Sparse A* 알고리즘 결과가 다르게 나오며 비교를 위해 Fig. 5(a)와 같이 두 항로를 계산하였다. 항로 1은 기상조건을 고려하지 않고 최적 항로 알고리즘을 수행한 결과이다. 기상조건을 고려하지 않았기 때문에 정수 중 저항만 고려가 되며 이는 거리가 Sparse A* 알고리즘의 평가함수가 된 것과 같다. 따라서 항로 1은 거리를 Sparse A* 알고리즘의 평가함수로 설정하여 도출한 항로이다. 항로 2는 기상조건을 고려하여 최적 항로 알고리즘을 수행한 결과이다. 기상조건을 고려하여 6.1절과 같이 연료 소모량을 Sparse A* 알고리즘의 평가함수로 설정하여 알고리즘을 수행한다. Table 3은 각 항로의 기상조건에 따른 연료 소모량을 계산한 결과이다.

Table 3에서 보이듯, 항로 1은 항로 2에 비해 항해 거리가 2.56% 감소했지만, 기상조건에 의해 생기는 부가저항 때문에 2.09% 더 많은 연료 소모량을 소비한다. 또한, 항로 1은 항로 2보다 기상조건이 나쁘므로 항로 1은 위험한 항로이다. 항로 2는 항해 거리가 항로 1보다 길지만, 기상조건에 의해 생기는 부가저항이 상대적으로 작아 더 적은 연료 소모량이 필요한 것을 확인하였다.

Table 3에서 보면, BN이 6일 때 항로 1의 동력 증가량이 24~26%로 상당히 높은 것을 볼 수 있다. 하지만 항로 2의 연료 소모량은 항로 1의 연료 소모량보다 2.09%로 상대적으로 적게 나타난다. 이는 항로 2의 항해 거리가 항로 1의 항해 거리보다 길어 정해진 도착시각을 맞추기 위해 항로 2의 항해 속력이 높아졌기 때문이다. 운항 중 동력은 항해 속력의 세제곱에 비례하기 때문에 필요한 동력이 항해 속력이 높아지면 동력 역시 크게 높아진다. 항로 1의 S1-S2 부분과 항로 2의 S1-S2를 보면 이 차이를 알 수 있다. S1-S2를 항해하는 데 필요한 연료 소모량은 항로 1에서 5.58 ton이며 항로 2에서 5.97 ton이다. 따라서 기상조건에 의한 동력 증가량과 항해 거리 증가에 의한 동력 증가량이 상쇄되어 총 연료 소모량 차이가 상대적으로 적게 나오는 결과를 확인하였다.