[논문]최적 경로 알고리즘들의 계산비용 비교 및 트랜스포터의 최적 블록 운송 계획 적용

문종헌; 유원선; 차주환

doi:10.3744/snak.2016.53.2.115

가설 설정

(2008)과 Roh and Cha (2011)는 트랜스포터의 공주행 거리 최소화를 고려한 블록 운반 계획 문제를 최적화 문제로 정식화하였다, Dijkstra 알고리즘을 이용하여 모든 블록 간의 최단 운반 거리 및 경로와 최단 공주행 거리, 경로 등의 정보를 기반으로 트랜스포터에 블록들을 할당하는 방법을 사용하였다. 개미 알고리즘(Ant Colony Optimization)을 이용하여 단일의 블록들이 주변에 가장 가까운 블록들을 집합으로 해서 각각의 트랜스포터에 운반할 블록을 할당하고, 이를 초기해 집합으로 가정한 후 유전자 알고리즘으로 블록의 운반순서를 결정함으로써 최적 블록 운반 계획을 제시하였다.
4)를 통해 트랜스포터가 운행 가능한 주도로와 주변에 가까운 위치에 있는 지번(적치장, PE장, 각종 조립장 등)과 연결하는 대표 주요절점을 지정하였다. 이 대표 주요 절점 간의 최단경로를 구한다면 대표 주요절점과 연결되어있는 지번까지의 최단경로를 확보할 수 있다고 가정하였다.
다음으로 트랜스포터 별 블록 할당과 블록 운송 순서를 결정하기 위해 최적화 문제를 정의한다. 이 문제를 최적화 문제에 적용하면 목적함수는 공차 이동 시간을 최소화하도록 하면서 트랜스포터의 최소 회전을 하는 것이며(식 (1)), 제약조건으로는 운송 블록의 무게가 트랜스포터의 적재 능력보다 작아야 하며(식 (2)), 모든 블록은 운송 완료 제한 시각 내에 완료(식 (4))된다고 가정하였다. 또한, 모든 블록은 운반 시작 가능 시각 이후에 운송을 시작해야 하고(식 (3)), 우선순위에 따라 블록을 운송(식 (5))해야 한다.

제안 방법

본 연구에서 경로 탐색 기법 중에 Dijkstra, A*, Floyd 알고리즘들의 계산 비용과 정밀도를 검증하였다. 사용되는 문제의 종류와 분야에 따라 장단점이 존재할 수 있음을 확인하였지만, 본 연구에서 제시하는 트랜스포터 운영계획 시나리오에서의 가장 적합한 경로 탐색 기법은 Dijkstra 알고리즘임을 확인하였다.
본 연구에서는 Dijkstra 알고리즘, A* 알고리즘과 Floyd 알고리즘을 사용하여 탐색하는데 걸리는 시간을 비교하였다. 또한, 손상 간선 발생으로 해당 간선을 우회하는 경로를 제시하는 즉각적인 방법이 아니고, 전체 트랜스포터 운영계획 차원에서 손상 간선 발생 및 계획 없던 블록의 추가 등에 대응할 방안을 제시하려 한다.
(2004)은 화물 컨테이너 운반시스템에서 최소의 차량으로 일정한 시간 내의 주어진 컨테이너를 운반하는 차량 경로계획을 설정하는 절차를 제시하였다. 제시된 절차는 우선 공차 이동 시간을 최소로 하는 최적화 모형을 이용하여 차량의 소요 대수 하한 값을 결정하고, Tabu Search 기반의 차량 경로 계획을 수립하였다.
사용되는 문제의 종류와 분야에 따라 장단점이 존재할 수 있음을 확인하였지만, 본 연구에서 제시하는 트랜스포터 운영계획 시나리오에서의 가장 적합한 경로 탐색 기법은 Dijkstra 알고리즘임을 확인하였다. 트랜스포터가 회전 시 소요되는 시간을 탐색 된 공차 이동 경로에 적용하여 최단 공차 이동 경로를 찾을 수 있도록 하였다. 회전을 고려하지 않을 때와 고려하였을 때의 총 공차 이동 시간이 단축된 것을 확인할 수 있었다.
(2012)에서 제시한 최적화 모형을 이용하여 블록 운송 경로에서 트랜스포터가 고장이 날 경우, 사고가 발생할 경우, 갑자기 경로 중 일부가 PE장으로 사용이 될 경우 등에 대처할 방안을 제시하고 있다. 특히 손상 간선이 발생한 경우, 해당 간선은 트랜스포터가 이용할 수 없으므로 손상된 간선을 제외한 최단 경로를 A* 알고리즘으로 재계산하여 새로운 경로를 재탐색하도록 하는 연구를 수행하였다.

대상 데이터

3에서처럼 지번에 있는 절점은 그대로 사용하고 지번에 있는 절점과 연결된 메인도로에 대표 주요절점을 지정하여 로컬노드와 메인도로의 대표 노드를 다대일로 연결하여 알고리즘의 계산에 사용되는 노드의 수를 약 85% 줄였다. 메인도로에 위치한 대표 절점의 수와 도로의 교차지점 절점 수의 총 개수는 238개이며, 238개 절점 간의 최단경로를 탐색하는데 절점 간의 최단거리를 비교하고 걸리는 시간을 비교하였다.
수치실험에 활용한 조선소 안에 있는 지번에 수는 총 1,596개로 이 지번 안에 있는 로컬노드(지번 노드)의 개수와 같으므로 이에 일대일로 대응하는 메인도로의 노드 수 또한 1,596개 이다. 하지만 교차로의 존재하는 노드를 합하면 메인도로의 총 노드 수는 더 증가하게 된다.

데이터처리

조선소에서는 특정 지번과 연관된 도로가 적치장으로 사용되거나 장애물의 발생 또는 특정한 상황이 발생하여 해당 도로를 사용하지 못할 경우, 즉 손상된 도로(간선)에 의해 블록 운송 경로를 변경해야 하는 상황이 발생할 수 있다. 손상 간선에 의한 경로 변경을 블록 운송 계획에 적용시켜 계획을 재수립하는 데 사용되는 Dijkstra 알고리즘과 A* 알고리즘의 경로 재탐색 수행 시간을 비교하였다.

이론/모형

이를 위해 Maxwell과 Muckstadt (1982), Koo, et al. (2004)이 제시한 최적화 모형을 이용하여 휴리스틱 시간(공차 운행 시간, 지연 시간 등)을 최소화하는 트랜스포터 경로 및 일정 계획 절차를 제시하였다.
GA(Genetic Algorithm)를 적용하기 전에 초기 블록 운송 계획을 수립하기 위해 개미가 자주 다니는 길에 페로몬을 남기는 것에 착안하여 가상 개미를 주행시키는 휴리스틱 최적화 방법인 개미 알고리즘(Ant Colony Optimization)을 사용하였고, 그 다음 GA(Genetic Algorithm)를 수행하여 최종 블록 운송 계획을 수립하게 한다. 위의 과정을 통해 결정된 블록 운송 계획에 따라 트 랜스포터를 운행을 하게 되는데, 이때 운송 도중 운송 경로에 문 제가 발생할 경우, 계산 비용이 극도로 많이 소비되는 운영계획 전반을 다시 수행하는 것이 아니고, 손상된 간선을 포함하는 트 랜스포터들의 최단 경로만을 다시 재설정하는 과정을 거친다 (Heo, et al.
우선 블록 운송 계획을 수립하기 전에 트랜스포터의 적재중량, 주행 및 공주행 속력, 작업 일정 등의 정보와 운반할 블록의 중량, 출/도착지의 정보, 운반 일정 등의 블록 정보, 그리고 트랜스포터가 이동하는 조선소의 경로에 대한 정보가 필요하였다. 또한, 각 블록의 출발지와 도착지 간의 최단 경로와 각 블록의 도착지와 다른 모든 블록의 출발지 간의 최단 경로를 미리 계산하는데 A* 알고리즘을 사용하였다.
이 제약조건들을 목적함수에 적용하기 위해 페널티 방법을 사용하였다. 블록의 중량과 트랜스포터의 적재능력 간의 부등식, 제한 시각과 실제 운송 시작/완료 시각 간의 부등식을 비교하여 위배하는 경우 페널티를 부여하는 방식을 사용하였다(Yim, et al., 2008). 다만 목적함수의 회전 관련 항은 본 연구에서 처음 언급된다.
1의 ①과는 다르게 임의 지번의 임의 블록이 추가되는 경우, 불시에 발생한 사고로 손상 간선이 발생할 경우 그리고 일정 경로가 적치장으로 변경 운영되는 경우 등에 대비하기 위해서 조선소에 있는 모든 절점 간의 최단 경로를 先 탐색을 한다. 비교에 참여한 최단경로 탐색 알고리즘으로는 Dijkstra 알고리즘, A* 알고리즘, Floyd 알고리즘 등이며 최단 경로를 탐색하는 시간을 비교하여 본 논문에서 제시한 시나리오를 적용해보았다. 또한 ②에서 볼 수 있듯이, 이미 탐색 된 블록의 이동 경로만을 대상으로 손상된 경로만을 피해 가는 방법에서 탈피하여, 전반적인 경로들을 모두 재탐색하고 이를 운영계획에 반영하는 방안을 택하였다.
또한, 모든 블록은 운반 시작 가능 시각 이후에 운송을 시작해야 하고(식 (3)), 우선순위에 따라 블록을 운송(식 (5))해야 한다. 이 제약조건들을 목적함수에 적용하기 위해 페널티 방법을 사용하였다. 블록의 중량과 트랜스포터의 적재능력 간의 부등식, 제한 시각과 실제 운송 시작/완료 시각 간의 부등식을 비교하여 위배하는 경우 페널티를 부여하는 방식을 사용하였다(Yim, et al.
마지막으로 트랜스포터가 최단경로를 따라 운행 시 직선 구간과는 달리 교차지점에서는 회전시간이 발생하게 되므로, 트랜스포터 운영계획 시 트랜스포터가 회전할 때 걸리는 시간을 트랜스포터의 최소 공차 이동시간에 고려하는 실용적인 접근방법을 적용하였다. 이를 바탕으로 트랜스포터의 운영계획에서 최소 공주행 시간을 가질 수 있도록 주어진 트랜스포터들에 블록 할당 및 운반 순서를 결정하는데 전역 최적화 방법의 하나인 SA(Simulated Annealing) 기법을 사용하였다. 또한, 각각의 블록의 운반 일정 및 트랜스포터가 들 수 있는 최대 중량에 위반되지 않도록 제한조건을 적용하였다.

성능/효과

하위 10%의 경우, Table 6에서 보면 Dijkstra 알고리즘이 약 83%만큼 감소한 것을 확인할 수가 있다. SA(Simulated Annealing)를 통해 도출된 트랜스포터의 운영계획은 제시하였던 모든 구속 조건을 만족함을 확인할 수 있었다.
그리고 손상된 경로를 반영하여 운영 계획을 실시간으로 새롭게 업데이트하는 경우에도 해당 알고리즘의 계산 비용적 및 합리적인 경로 탐색이 A* 알고리즘보다 뛰어남을 확인할 수 있었다. 계산 비용적 특징을 차치하더라도 A* 알고리즘의 휴리스틱 탐색 특성은 손상 경로 탐색의 전역적 최적화 경로를 방해하는 면이 있으며, 본 연구에서 제시하는 가변적 환경에 적합한 트랜스포터 운영계획 시스템에서는 존재하는 모든 지번을 대상으로 최단 경로를 탐색하는 특징을 가지므로 Dijkstra 알고리즘의 시간적 탐색 효율성이 꼭 필요하였다.
회전을 고려하지 않을 때와 고려하였을 때의 총 공차 이동 시간이 단축된 것을 확인할 수 있었다. 그리고 손상된 경로를 반영하여 운영 계획을 실시간으로 새롭게 업데이트하는 경우에도 해당 알고리즘의 계산 비용적 및 합리적인 경로 탐색이 A* 알고리즘보다 뛰어남을 확인할 수 있었다. 계산 비용적 특징을 차치하더라도 A* 알고리즘의 휴리스틱 탐색 특성은 손상 경로 탐색의 전역적 최적화 경로를 방해하는 면이 있으며, 본 연구에서 제시하는 가변적 환경에 적합한 트랜스포터 운영계획 시스템에서는 존재하는 모든 지번을 대상으로 최단 경로를 탐색하는 특징을 가지므로 Dijkstra 알고리즘의 시간적 탐색 효율성이 꼭 필요하였다.
첫 번째 방법은 경로의 개수가 너무 많아 비교하는 데 어려움이 있어서 두 번째 방법인 모든 절점 간의 최단거리에 대한 자료구조를 만들어 일치하는지 비교할 수가 있다. 기존의 논문에서 최단경로를 탐색하는 데 사용한 Dijkstra 알고리즘, A* 알고리즘과 추가로 Floyd 알고리즘을 적용하여 모든 절점 간의 최단거리를 자료구조로 만들어 비교한 결과 Table 1과 같이 모든 절점 간의 최단거리가 같다는 것을 볼 수가 있었다.
종합해 보면, 조선 야드의 블록 물류 이동은 정적인 환경이 아니고 다양한 경우와 사고에 유연하게 대처해야 한다. 본 연구에서는 이를 위해서 미리 모든 지번 간의 최단 경로의 확보가 필요하였고 이를 실시간으로 반영할 수 있는 트랜스포터의 운영계획 시스템을 구축하였으며, 가장 적합한 경로 탐색 알고리즘은 Dijkstra 알고리즘이었다.
본 연구에서 경로 탐색 기법 중에 Dijkstra, A*, Floyd 알고리즘들의 계산 비용과 정밀도를 검증하였다. 사용되는 문제의 종류와 분야에 따라 장단점이 존재할 수 있음을 확인하였지만, 본 연구에서 제시하는 트랜스포터 운영계획 시나리오에서의 가장 적합한 경로 탐색 기법은 Dijkstra 알고리즘임을 확인하였다. 트랜스포터가 회전 시 소요되는 시간을 탐색 된 공차 이동 경로에 적용하여 최단 공차 이동 경로를 찾을 수 있도록 하였다.
종합해 보면, 조선 야드의 블록 물류 이동은 정적인 환경이 아니고 다양한 경우와 사고에 유연하게 대처해야 한다. 본 연구에서는 이를 위해서 미리 모든 지번 간의 최단 경로의 확보가 필요하였고 이를 실시간으로 반영할 수 있는 트랜스포터의 운영계획 시스템을 구축하였으며, 가장 적합한 경로 탐색 알고리즘은 Dijkstra 알고리즘이었다.
이러한 결과는 모든 문제의 계산 비교의 것으로 일반화하기 어렵지만, 절점 간을 연결하는 간선의 수가 비교적 적은 조선 수치지도를 반영한 트랜스포터의 경로탐색 문제에서의 결과임을 밝힌다. 최단경로를 찾는 시간을 비교하여 모든 절점에서의 탐색시간(다대다 탐색 소요시간)은 Dijkstra 알고리즘이 가장 빠르고, 일대일 탐색에서는 A* 알고리즘이 가장 빠른 것을 확인하였다.
트랜스포터가 회전 시 소요되는 시간을 탐색 된 공차 이동 경로에 적용하여 최단 공차 이동 경로를 찾을 수 있도록 하였다. 회전을 고려하지 않을 때와 고려하였을 때의 총 공차 이동 시간이 단축된 것을 확인할 수 있었다. 그리고 손상된 경로를 반영하여 운영 계획을 실시간으로 새롭게 업데이트하는 경우에도 해당 알고리즘의 계산 비용적 및 합리적인 경로 탐색이 A* 알고리즘보다 뛰어남을 확인할 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

최적 경로 알고리즘들의 계산비용 비교 및 트랜스포터의 최적 블록 운송 계획 적용
Comparison of Optimal Path Algorithms and Implementation of Block Transporter Planning System 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

최적 경로 알고리즘들의 계산비용 비교 및 트랜스포터의 최적 블록 운송 계획 적용 Comparison of Optimal Path Algorithms and Implementation of Block Transporter Planning System 원문보기

Abstract ▼ AI-Helper

주제어

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

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

문종헌 (1) 유원선 (17)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

최적 경로 알고리즘들의 계산비용 비교 및 트랜스포터의 최적 블록 운송 계획 적용
Comparison of Optimal Path Algorithms and Implementation of Block Transporter Planning System 원문보기

AI 본문요약
AI-Helper