[논문]실시간 적응 A* 알고리즘과 기하학 프로그래밍을 이용한 선박 최적항로의 2단계 생성기법 연구

박진모; 김낙완

doi:10.5574/ksoe.2015.29.3.263

문제 정의

이러한 문제를 직접적으로 접근 하는 것은 상당히 시간이 많이 소요될 수 있으며, 도출된 해가 지역 최적화에 빠질 염려가 있으므로 적절한 방법을 통한 문제의 해결이 요구된다. 본 논문에서는 기하학적 프로그래밍(Geometric programming)을 이용하여 이 속도계획 문제를 해결하였다.
본 논문에서는 선박의 최적항로 문제를 두 단계로 나누어 해결하는 방법을 제시하였다. 첫번째 단계 Phase 1에서는 선박의 속도를 고정한 후 RTAA* 알고리즘을 통해 경로를 최적화 하였다.
본 논문에서는 최적 항로 생성을 위한 고려 사항으로 해상환경에 의한 선속의 변화량과 선박의 항해중 안전성을 고려하였다. 이들 두 요소는 최적항로 생성을 위한 가장 중요한 요소로써 선속의 변화는 Phase 1과 2에서 안전성은 Phase 2에서 반영된다.
그러므로 환경 변화를 반영하는 동시에 연료 소모량 측면에서 최적화된 항로를 도출하기 위해서는 해상 환경 예보가 바뀌는 시간 단위에 따라 적절한 시간 내에 계산이 가능한 방법이 필요하다. 본논문에서는 효율적인 계산 시간과 높은 정도의 경로 최적화를 위하여 항로 도출에 실시간 적응 A* 알고리즘과 기하학적 프로그래밍을 바탕으로 최적항로 도출 방안을 제시하고자 한다. 선박의 경우 연산시간의 여유가 큰 편이나, 수백 척의 선박을 운영하는 대형 해운사의 경우 각각의 선박이 기상상태를 전송 받고 최적경로를 생성하는 것 보다는 중앙관제센터에서 업데이트된 기상상태를 바탕으로 수십척 이상의 운항중인 선박의 최적경로를 생성하고 각 선박에게 전송하는 통합 운영방식이 최적경로 시스템 및 기상상태 서비스의 개수를 최소화시킬수 있다는 점에서 경제적인데, 이런 경우 계산시간의 중요성이 증가하고 본 논문에서 제시한 기법으로 최적경로 생성에 소요되는 계산시간을 감소시킬 수 있다.
4의 선박의 속도는 엔진 출력을 고정한 항해 시나리오의 패턴과 유사함을 알 수 있다. 이를 통해 선박의 속도 계획 최적화는 각 시각별 속도와 엔진 출력이라는 두 가지 변수에 대해 자유도를 가지게 되고 이에 대한 최적화를 이루어냈다고 판단할 수 있다.
이를 위하여 선박의 정해진 설계 속도의 60% 정도의 속도로 저속운항을 하거나 선체에 부가물을 붙여 저항을 감소시키는 등의 노력들이 이루어지고 있다(He-ping, 2007). 최적항로 계획은 이러한 연료 소비량 감소 및 온실가스 배출 감소를 위한 노력의 하나로 주어진 해상환경에서 최소의 연료로 목적지까지 도달하기 위한 경로 생성에 관한 연구이다. 이와 관련하여 알고리즘 방법론에 관한 연구로는 3차원 동적 프로그래밍을 이용하여 선박의 속도와 경로를 변경 시켜가며 경로를 도출 한연구와(Shao et al.

제안 방법

Phase 1에서 수행되는 최적 경로 생성을 위한 그리드는 경도기준 1.5도, 위도기준 0.3도로 하여 선박의 방향각을 좀 더 다양하게 줄 수 있도록 하였다. 이때, 하나의 노드에서 뻗어 나갈 수있는 노드 연결 가지 수는 아홉개로 설정 하였다.
RTAA* 알고리즘에서 주어지는 좀 더 좋은 정보의 휴리스틱 값을 통해 길 찾기에서 노드 확장 횟수를 줄여 최적 항로 생성에서 계산 시간을 단축할 수 있음을 보였다. Phase 2에서는 비선형 최적화 문제를 기하학적 프로그램으로 변환하여 구간별 속도를 최적화 하였다. 두 번째 단계에서 기하학적 프로그래밍으로 변환을 할 경우 이 최적화 문제는 컨벡스 형태를 지니게되므로 문제를 효율적으로 해결할 수 있으며 이때 나오는 최적화 해는 전역 최적해를 보장할 수 있다는 장점이 있다.
이때, 하나의 노드에서 뻗어 나갈 수있는 노드 연결 가지 수는 아홉개로 설정 하였다. 또한 속도 계획의 유효성을 보기 위하여 엔진 출력을 고정한 항해 시나리오 그리고 선박의 속력을 고정한 시나리오와 연료 소모량 측면에서 비교를 수행하였다. 또한 본 논문에서 시뮬레이션을 위해 사용한 컴퓨터는 i7- 1.
평가함수 식 우변의 첫 두항 g(V) di-1, i + gad(V, βi-1, i)di-1, i의 값은 현재 위치에서 다음 위치까지 갈 때의 정확한 연료 소모량을 뜻하므로, 코스트 값의 역할을 한다. 마지막 항인 h값은 휴리스틱 값으로, 최초 A* 알고리즘을 통해 항로를 생성할 때 BN = 2일 때의 값을 적용하여 다음 위치에서 최종 목적지까지의 연료 소모값을 추정하였다. 이 값은 시행착오에 의해 얻어진 값으로, 다익스트라 알고리즘과 비교하여 같은 경로가 나오게 될 때의 값을 이용한 것이다.
1로 설명할 수 있다. 매 여섯 시간 마다 업데이트 되는 일기 예보를 바탕으로 Phase 1에서 선박 속도를 고정하고 Real Time A* 알고리즘을 이용하여 최적항로를 생성하고 Phase 2에서는 Phase 1을 통해 생성된 최적항로에서 기하학 프로그래밍을 이용하여 최적 운항 속도를 계획한다.
본 논문에서는 CVX TOOL을 이용하여 매트랩(MATLAB)에서 문제를 해결하였다.
제안된 최적항로 도출법의 실효성을 검증하기 위하여 간단한 시뮬레이션이 수행되었다. 본 논문에서 수행된 시뮬레이션은 동경에서 샌프란시스코까지 가는 8000TEU 급의 컨테이너선을 대상으로 수행 되었으며, 해상환경에 의한 선속의 저하, 그리고 선박의 항해중 안전성 반영을 위하여 ECMWF에서 제공되는 기상정보 중 유의파고, 파 주기, 파향, 풍속을 획득하였으며, 시뮬레이션을 수행하는 대상 날짜는 2013년 12월 1일부터 8일까지의 총 8일간의 항해를 기준으로 하였다.
방법을 제시하였다. 첫번째 단계 Phase 1에서는 선박의 속도를 고정한 후 RTAA* 알고리즘을 통해 경로를 최적화 하였다. RTAA* 알고리즘에서 주어지는 좀 더 좋은 정보의 휴리스틱 값을 통해 길 찾기에서 노드 확장 횟수를 줄여 최적 항로 생성에서 계산 시간을 단축할 수 있음을 보였다.
최적항로 문제에 RTAA* 알고리즘을 적용하기 위해서 본 논문에서는 선박의 속력을 고정시키고 방향각을 정하여 최적항로를 생성하였다. 이때 사용된 평가함수는 다음과 같이 쓰여질 수 있다.

대상 데이터

수행되었다. 본 논문에서 수행된 시뮬레이션은 동경에서 샌프란시스코까지 가는 8000TEU 급의 컨테이너선을 대상으로 수행 되었으며, 해상환경에 의한 선속의 저하, 그리고 선박의 항해중 안전성 반영을 위하여 ECMWF에서 제공되는 기상정보 중 유의파고, 파 주기, 파향, 풍속을 획득하였으며, 시뮬레이션을 수행하는 대상 날짜는 2013년 12월 1일부터 8일까지의 총 8일간의 항해를 기준으로 하였다. 일기 정보의 해상도는 위도 경도를 기준으로 하여 1.

이론/모형

이 선박의 속력 저하를 정확히 계산하기 위해서는 선박의 부가저항을 계산하여 반영하여야 하지만 이는 푸는 과정에서 시간이 오래 걸리며 방법이 지나치게 복잡하므로 선박의 최적 항로 생성 도출에 과도한 시간이 소요될 수 있다. 그러므로 본 논문에서는 Beaufort number (BN)을 기반으로 한선박속력 저하식을 이용하도록 한다.(Townsin and Kwon, 1993)이 약산식은 다음과 같이 주어진다.
또한 속도 계획의 유효성을 보기 위하여 엔진 출력을 고정한 항해 시나리오 그리고 선박의 속력을 고정한 시나리오와 연료 소모량 측면에서 비교를 수행하였다. 또한 본 논문에서 시뮬레이션을 위해 사용한 컴퓨터는 i7- 1.7GHz 쿼드 코어 컴퓨터 이며, Matlab을 이용하여 구현하였다. 이를 바탕으로 수행한 시뮬레이션 결과는 다음과 같다.
본 논문에서 선박의 항해 중 안전성의 반영은 IMO (International Maritime Organization)에서 제시된 항해 안전성에 대한 가이드라인(IMO, 2007)에 따르도록 한다. 여기서 정의되는 각도 β는 선박과 파가 만나게 되는 상대적인 각도로 0도일 때를 Head sea 그리고 180도 일 때를 Following sea로 정의한다.
해상환경이 일반적으로 그리드 셀의 형태로 주어지게 되므로, 그리드 셀 기반의 길찾기 방법을 사용하는 것이 타당할 수 있다고 할 수 있다. 본논문에서 사용한 길찾기 알고리즘은 기존의 A* 알고리즘을 변형하여 계산속도에서 향상을 가져올 수 있는 Real-Time Adaptive A* (RTAA*) 알고리즘을 사용하였다. 이 알고리즘의 기본적인 형태는 A* 알고리즘과 같지만, 휴리스틱 값을 업데이트 하는 부분에서 다르다고 할 수 있다.

성능/효과

Phase1에서 수행되는 계산 시간을 비교해보면 기존 A* 알고리즘에 비해 RTAA* 알고리즘은 노드 확장 수가 두 번째 단계에서 12.7% 감소하는 것을 보이지만 실제 계산 시간은 15.3% 감소하는 것을 알 수 있다. 이는 길찾기 알고리즘의 특성상 데이터의 더미(Stack)가 쌓이게 되면서 일어나는 현상으로, 경로점을 많이 설정하여 최적항로 생성을 할 경우 RTAA* 알고리즘을 통해 계산시간에서 더 좋은 효율을 얻을 수 있을 것으로 기대된다.
첫번째 단계 Phase 1에서는 선박의 속도를 고정한 후 RTAA* 알고리즘을 통해 경로를 최적화 하였다. RTAA* 알고리즘에서 주어지는 좀 더 좋은 정보의 휴리스틱 값을 통해 길 찾기에서 노드 확장 횟수를 줄여 최적 항로 생성에서 계산 시간을 단축할 수 있음을 보였다. Phase 2에서는 비선형 최적화 문제를 기하학적 프로그램으로 변환하여 구간별 속도를 최적화 하였다.
이는 길찾기 알고리즘의 특성상 데이터의 더미(Stack)가 쌓이게 되면서 일어나는 현상으로, 경로점을 많이 설정하여 최적항로 생성을 할 경우 RTAA* 알고리즘을 통해 계산시간에서 더 좋은 효율을 얻을 수 있을 것으로 기대된다. Table 5에서 알 수 있듯이 경로 최적화를 한 경우 (Phase 1)와 대권항로에서 속도를 고정한 항해를 비교하면 항해거리에서는 최적항로가 287km 더 길었지만 4.6%의 연료 소모감소를 보였으며 총 운항시간에서도 5.2 시간의 단축을 보였고, 최적화 된 경로에서 속도 최적화를 한 항해의 경우(Phase 2) 대권항로에 비해 8.4%의 연료 소모값 감소를 보였다. 이를 통해 Phase 1에서의 경로 최적화가 적절히 이루어짐을 알 수 있으며 또한 Phase2를 통해 또 한번의 항해 전략의 최적화를 이루어냈다고 판단 할 수 있다.
두 번째 단계에서 기하학적 프로그래밍으로 변환을 할 경우 이 최적화 문제는 컨벡스 형태를 지니게되므로 문제를 효율적으로 해결할 수 있으며 이때 나오는 최적화 해는 전역 최적해를 보장할 수 있다는 장점이 있다. 마지막으로 연료 소모값에서 최적화 된 경로에서 속도 계획은 대권항로에서의 항해와 비교하여 8.4%의 연료 감소 효과를 보일 수 있었다. 본 논문에서 제시된 방법을 통해 최적항로 문제에서 도움을 줄 수 있는 길을 제시할 수 있을 것이다.
본논문에서는 효율적인 계산 시간과 높은 정도의 경로 최적화를 위하여 항로 도출에 실시간 적응 A* 알고리즘과 기하학적 프로그래밍을 바탕으로 최적항로 도출 방안을 제시하고자 한다. 선박의 경우 연산시간의 여유가 큰 편이나, 수백 척의 선박을 운영하는 대형 해운사의 경우 각각의 선박이 기상상태를 전송 받고 최적경로를 생성하는 것 보다는 중앙관제센터에서 업데이트된 기상상태를 바탕으로 수십척 이상의 운항중인 선박의 최적경로를 생성하고 각 선박에게 전송하는 통합 운영방식이 최적경로 시스템 및 기상상태 서비스의 개수를 최소화시킬수 있다는 점에서 경제적인데, 이런 경우 계산시간의 중요성이 증가하고 본 논문에서 제시한 기법으로 최적경로 생성에 소요되는 계산시간을 감소시킬 수 있다.

후속연구

4%의 연료 감소 효과를 보일 수 있었다. 본 논문에서 제시된 방법을 통해 최적항로 문제에서 도움을 줄 수 있는 길을 제시할 수 있을 것이다.
3% 감소하는 것을 알 수 있다. 이는 길찾기 알고리즘의 특성상 데이터의 더미(Stack)가 쌓이게 되면서 일어나는 현상으로, 경로점을 많이 설정하여 최적항로 생성을 할 경우 RTAA* 알고리즘을 통해 계산시간에서 더 좋은 효율을 얻을 수 있을 것으로 기대된다. Table 5에서 알 수 있듯이 경로 최적화를 한 경우 (Phase 1)와 대권항로에서 속도를 고정한 항해를 비교하면 항해거리에서는 최적항로가 287km 더 길었지만 4.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] **실시간 적응 A* 알고리즘과 기하학 프로그래밍을 이용한 선박 최적항로의 2단계 생성기법 연구
Two-Phase Approach to Optimal Weather Routing Using Real-Time Adaptive A* Algorithm and Geometric Programming** 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 실시간 적응 A* 알고리즘과 기하학 프로그래밍을 이용한 선박 최적항로의 2단계 생성기법 연구 Two-Phase Approach to Optimal Weather Routing Using Real-Time Adaptive A* Algorithm and Geometric Programming 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

박진모 (1) 김낙완 (18)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] **실시간 적응 A* 알고리즘과 기하학 프로그래밍을 이용한 선박 최적항로의 2단계 생성기법 연구
Two-Phase Approach to Optimal Weather Routing Using Real-Time Adaptive A* Algorithm and Geometric Programming** 원문보기

AI 본문요약
AI-Helper