[논문]트랜스포터 결합을 고려한 조선소 블록 운반 일정계획

신재영; 박나현

doi:10.5394/kinpr.2014.38.3.299

초록
AI-Helper

트랜스포터란 조선소에서 작업장 간에 조선 블록을 운반하는 장비이다. 트랜스포터 일정 계획을 효율적으로 하는 것은 선박 건조과정에서 매우 중요한 역할을 한다. 블록 운반에 있어서의 트랜스포터 일정 계획에 관한 몇몇 연구들이 수행되었다. 이러한 연구들은 트랜스포터 결합을 고려하지 않았다. 본 논문에서는 결합을 고려한 효율적인 트랜스포터 일정 계획 모형을 제안한다. 수리적 모형에서는 운영 비용을 최소화하면서 트랜스포터 간의 작업 부하를 가능한 균등하게 하는 것을 목적으로 하였다. 또한 본 모형의 해를 탐색하기 위해 타부 서치 기반의 세 가지 휴리스틱 알고리즘을 제시하였으며 컴퓨터 실험을 통해 제안된 휴리스틱들의 효율성을 검증하였다.

Abstract ▼ AI-Helper

In a ship-building, a transporter is the moving equipment to transport ship blocks from a workshop to another in a shipyard. The efficient scheduling of transporters has an important role for the operation of a building ship to be completed on schedule. There are the previous studies on the transpor...

In a ship-building, a transporter is the moving equipment to transport ship blocks from a workshop to another in a shipyard. The efficient scheduling of transporters has an important role for the operation of a building ship to be completed on schedule. There are the previous studies on the transporter scheduling for moving blocks in a shipyard. These studies have no consideration for the transporter combination to increase the productivity of moving blocks. This paper presents an efficient transporter scheduling model considering transporter combination explicitly. The objective of this model is to minimize the operational cost and maintain the workload balance among transporters. we also present three heuristics algorithms based on tabu search for finding the solution of the model. The efficiency of the proposed heuristics are verified with several computational tests.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

플로팅 도크로 PE 블록을 운반하는 장비로 해상크레인, 모듈 트랜스포터 등이 있으며 트랜스포터를 결합하여 대형블록을 운반하는 것이 해상크레인을 이용하는 것보다 안전 하며 더 큰 블록을 운반할 수 있다는 점에서 경쟁력이 있다. 동적인 조선소 환경에서 트랜스포터를 결합하여 블록을 운반 하게 되면 다양한 운반 계획이 가능하고 유연하게 대처할 수 있다는 점에서 본 연구에 의의가 있다.
2의 3가지 operator로 이웃해를 탐색하는 것을 제안한다. 또한 타부 서치를 여러 번 반복하게 하여 탐색 영역을 넓혀 해 개선 가능성을 높이고자 한다. 3.
하지만 조선소에서는 작업자의 숙련도에 의해 작업 속도가 결정되는 작업이 많고 조선 자체가 프로젝트의 성격을 띠므로 건조 중 설계 변경이 빈번하다. 또한 트랜스포터의 고장 및 정비로 인해 계획의 변경이 불가피할 경우가 종종 발생하므로 본 연구에서는 동적 환경에서도 적용할 수 있도록 빠른 시간 내에 근사 최적해를 낼 수 있는 휴리스틱 알고리즘을 제안한다. 제안하는 초기해 생성을 위한 경로 생성 알고리즘과 타부서치 알고리즘의 상세 단계는 다음과 같다.
본 논문에서는 트랜스포터의 결합에 따라 용량 제약 및 시간 제약이 변하는 것을 고려하였으며 조선소에서 발생하는 블록 이동을 적시에 수행하기 위해 트랜스포터를 스케줄링하는 문제를 연구하였다. 조선소의 블록 운반 상황에 맞춰 문제를 설정하고 그에 따른 수리적 모형과 휴리스틱 해법을 제시하였다.
본 연구에서는 트랜스포터 결합을 고려하여 정해진 작업 일정을 지키고 물류비를 줄이기 위해 트랜스포터 보유량을 최소화하고 할당된 트랜스포터들의 운행 시간을 평준화하는 수리적 모형을 구축한다. 최소화에만 초점을 둘 경우 특정 차량에 작업이 몰리게 될 수 있으며 예상 시각에 맞춰 작업을 완료하지 못할 경우에 문제가 발생할 수 있다.

가설 설정

일반적으로 변형기법에 비해 좋은 해를 낼 수 없었지만 블록의 수가 많아질수록 단순히 타부 서치를 반복하는 것이 가장 좋은 해를 탐색하는 방법이다. H2는 대체로 가장 좋은 해를 탐색하였지만 시간이 다른 알고리즘들에 비해 오래 걸린다는 것을 볼 수 있다. 반면 H3는 모든 경우에서 가장 짧은 탐색 시간을 가졌고 H1, H2의 해와 비슷한 답을 제시하거나 특정 블록 개수군의 데이터에서는 가장 우수한 답을 내기도 하였다.
여기서 가상의 출발, 도착 데포를 0으로 가정한다. Fig 2는 본 연구에서 정의한 블록 운송의 흐름 예제이다.

제안 방법

또한 타부 서치를 여러 번 반복하게 하여 탐색 영역을 넓혀 해 개선 가능성을 높이고자 한다. 3.2의 타부 서치를 단순히 반복하는 알고리즘(H1), 일정한 확률로 개선이 발생하지 않는 경우에도 해로 대치될 수 있도록 하여 반복하는 알고리즘(H2), 초기해를 재구성하여 반복하는 알고리즘 (H3)의 세 가지 알고리즘을 제안한다. 경로 생성 알고리즘의 Step 1에서는 차량을 크기에 따라 정렬하였으나 H3 알고리즘은 일정 기간 이웃해 탐색에 개선이 없으면 랜덤하게 차량을 배치하여 생성된 해를 초기해로 재구성하는 방법이다.
경로 생성 알고리즘에서 블록당 한 대의 차량을 배치시켜 초기해를 구성하고 3.2의 3가지 operator로 이웃해를 탐색하는 것을 제안한다. 또한 타부 서치를 여러 번 반복하게 하여 탐색 영역을 넓혀 해 개선 가능성을 높이고자 한다.
본 논문에서 제시한 수리적 모형은 MIP 모형으로 컴퓨터를 이용하지 않으면 최적해를 찾기가 어려우므로 ILOG CPLEX 12.0를 이용하여 초기해를 탐색한다. 그리고 제안된 휴리스틱 알고리즘 및 타부 서치 알고리즘은 C#으로 구현하였다.
만일 정해진 차량으로 운영하는 것에만 목적이 있을 경우 목적함수에서 차량최소화에 관한 가중치를 0으로 두면 된다. 위의 내용을 바탕으로 초기해로 사용될 휴리스틱 알고리즘을 제안하고 메타 휴리스틱 중 하나인 타부서치 알고리즘을 이용한 총 3가지의 휴리스틱 알고리즘을 제시하여 각각의 결과를 비교해 보고자 한다.
본 논문에서는 트랜스포터의 결합에 따라 용량 제약 및 시간 제약이 변하는 것을 고려하였으며 조선소에서 발생하는 블록 이동을 적시에 수행하기 위해 트랜스포터를 스케줄링하는 문제를 연구하였다. 조선소의 블록 운반 상황에 맞춰 문제를 설정하고 그에 따른 수리적 모형과 휴리스틱 해법을 제시하였다. 그리고 수리적 모형 및 제안한 해법을 이동해야 할 블록 수에 따라 다양한 데이터로 실험한 후 분석을 통해 해법의 효율성을 검증하였다.

대상 데이터

그리고 제안된 휴리스틱 알고리즘 및 타부 서치 알고리즘은 C#으로 구현하였다. 실험에 쓰인 트랜스포터와 블록 데이터는 Jeong(2006)에서 제시한 현장 데이터를 기준으로 작성하였다.

데이터처리

조선소의 블록 운반 상황에 맞춰 문제를 설정하고 그에 따른 수리적 모형과 휴리스틱 해법을 제시하였다. 그리고 수리적 모형 및 제안한 해법을 이동해야 할 블록 수에 따라 다양한 데이터로 실험한 후 분석을 통해 해법의 효율성을 검증하였다. 실험 분석 결과, 제안한 휴리스틱으로 짧은 시간 내에 우수한 해 탐색이 가능하므로 동적 환경의 트랜스포터 일정 계획에서 이용될 수 있을 것으로 기대된다.

이론/모형

Yim et al(2008)은 공주행을 최소로 하는 트랜스포터의 운반 계획 알고리즘을 제안하였다. 운반 거리를 결정하기 위해 Dijkstra 알고리즘을 이용하였고, 최적의 블록 할당 및 운반순서를 결정하기 위해 개미 알고리즘과 유전 알고리즘을 혼합한 혼합형 알고리즘으로 문제를 해결하였다. Lee et al(2008)은 조선소에서 계획기간동안 갑작스런 블록 수송정보의 변경이나 트랜스포터의 고장 등이 발생하게 될 경우, 동적인 환경에서 트랜스포터 일정 계획을 위해 4가지 휴리스틱들을 제안하고 각각의 성능을 비교하였다.

성능/효과

이동 블록 수가 20일 경우 평균 9의 차이를 보였으며 최적해에 근사한 해를 출력하는 것으로 볼 수 있다. 또한, 10개에서 20개로 이동 블록 수가 증가할 때 최적해 탐색에 소요되는 시간이 크게 증가한데 반해 휴리스틱 알고리즘의 수행 시간은 이동 블록 수가 10, 20개인 실험에서 모두 1초를 넘지 않은 것으로 나타나 본 알고리즘의 탐색 시간의 효율성을 보여준다. 이동 블록 수가 30를 넘어갈 때는 최적해를 구하는 것이 불가능하여 구해진 해의 품질을 비교할 수 없었다.
최적해를 구할 수 없었던 실험 결과까지 포함하여 제안한 3개의 휴리스틱 알고리즘들을 비교 해보면 블록 수가 200개 이하일 때, H2 > H3 > H1, 200~300 개일 때는 H3 > H2 > H1 순으로 좋은 해를 탐색하였으며 500개일 때는 H1 > H3 > H2 순으로 좋은 해를 탐색하였다. 여기서 300개까지 H1의 결과 값은 H2나 H3에 비해 나빴으며 계산 시간도 H3에 비해 오래 걸리는 것을 확인할 수 있었으며 500개부터는 가장 좋은 해를 탐색했다. 일반적으로 변형기법에 비해 좋은 해를 낼 수 없었지만 블록의 수가 많아질수록 단순히 타부 서치를 반복하는 것이 가장 좋은 해를 탐색하는 방법이다.
최적해를 구할 수 없었던 실험 결과까지 포함하여 제안한 3개의 휴리스틱 알고리즘들을 비교 해보면 블록 수가 200개 이하일 때, H2 > H3 > H1, 200~300 개일 때는 H3 > H2 > H1 순으로 좋은 해를 탐색하였으며 500개일 때는 H1 > H3 > H2 순으로 좋은 해를 탐색하였다.
최적해와 제안한 알고리즘의 수행 결과 및 계산 시간을 Table 1과 같이 나타낼 수 있다. 최적해와 알고리즘 결과 값을 비교해보면 이동 블록 수가 10일 경우 평균 1의 차이가 있으며 5개 중 2개의 경우에서는 알고리즘으로 최적해를 구할 수 있었다. 이동 블록 수가 20일 경우 평균 9의 차이를 보였으며 최적해에 근사한 해를 출력하는 것으로 볼 수 있다.

후속연구

그리고 수리적 모형 및 제안한 해법을 이동해야 할 블록 수에 따라 다양한 데이터로 실험한 후 분석을 통해 해법의 효율성을 검증하였다. 실험 분석 결과, 제안한 휴리스틱으로 짧은 시간 내에 우수한 해 탐색이 가능하므로 동적 환경의 트랜스포터 일정 계획에서 이용될 수 있을 것으로 기대된다.
향후 블록 적치장의 블록 반출입 계획과 공정 계획에 트랜스포터 일정 계획을 연계하여 계획을 하게 되면 전체 블록 흐름상 더 좋은 해를 낼 것으로 보이며 그에 따른 추가적인 연구가 필요할 것으로 보인다.

질의응답

핵심어	질문	논문에서 추출한 답변
	적절한 블록 운반 계획을 세우고 이행하는 것은 어떤 효과를 가져올 것으로 예상되는가?	게다가 납기일이 다른 여러 선박들이 동시에 건조되므로 전체 일정에 영향을 주지 않게 각각의 일정계획을 준수하는 것이 중요하다. 그러므로 적절한 블록 운반 계획을 세우고 이행하는 것은 물류비 감소로 인해 매출 대비 순이익 증가를 가져올 뿐만 아니라 납기일을 준수할 수 있게 됨으로써 신뢰도 및 경쟁력을 향상시킬 것으로 예상한다.
	트랜스포터란 무엇인가?	트랜스포터란 조선소에서 작업장 간에 조선 블록을 운반하는 장비이다. 트랜스포터 일정 계획을 효율적으로 하는 것은 선박 건조과정에서 매우 중요한 역할을 한다.

참고문헌 (12)

Chung, C. Y. and Shin, J. Y.(2012), "Efficient Yard Tractor Control Method for the Dual Cycling in Container Terminal", Journal of navigation and port research, Vol. 36, No. 1, pp. 69-74.

원문보기 상세보기
Dror, M., Trudeau, P.(1990), "Split delivery routing", Naval Research Logicsticcs, Vol.37, No.3, pp. 383-402.

상세보기
Desaulniers, G.(2010), "Branch-and-price-and-cut for the split delivery vehicle routing problem with time windows". Operations Research, Vol.58, No.1, pp. 179-192.

상세보기
Dror, M., Laporte, G., Trudeau, P.(1994), "Vehicle routing with split deliveries", Discrete Applied Mathematics, Vol.50, No.3, pp. 239-254.

상세보기
Ho, S., Haugland, D.(2004). "A tabu search heuristic for the vehicle routing problem with time windows and split deliveries". Computers and Operations Research, Vol.31, pp. 1947-1964.

상세보기
Jeong, Y. S.(2006). Block Transportation Management System, Thesis(master), pp.8-9.
Kim, J. H. et al(2008), "A Development of Floating Dock Control Simulator for Skid Launching System", Journal of navigation and port research, Vol. 32, No. 1, pp. 1-7.

원문보기 상세보기
Lee, W. S. et al(2008), "Transporter Scheduling for Dynamic Block Transportation Environment", IE Interfaces, Vol. 21, No. 3, pp. 274-282.
Lee, W. S. et al(2009), "Transporter Scheduling Based on a Network Flow Model for Dynamic Block Transportation Environment", IE Interfaces, Vol. 22, No. 1, pp. 63-72.
Park, C. K. and Seo, J. Y.(2012), "A GRASP approach to transporter scheduling and routing at a shipyard ", Computers & Industrial Engineering, Vol. 63, No. 2, pp. 390-399.

상세보기
Shin, J. Y. and Kwon S. C.(2009), "Effective Operation Strategies for Pooling Yard Tractors m Container Terminals", Journal of navigation and port research, Vol. 33, No. 6, pp. 401-407.

원문보기 상세보기
Yim, S. B. et al(2008), "Optimal Block Transportation Scheduling Considering the Minimization of the Travel Distance without Overload of a Transporter", Journal of the Society of Naval Architects of Korea, Vol. 45, No. 6, pp. 646-655.

원문보기 상세보기

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

연합인증

트랜스포터 결합을 고려한 조선소 블록 운반 일정계획
Transporter Scheduling with Transporter Combination in Shipbuilding 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

트랜스포터 결합을 고려한 조선소 블록 운반 일정계획 Transporter Scheduling with Transporter Combination in Shipbuilding 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

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

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

신재영 (25)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

트랜스포터 결합을 고려한 조선소 블록 운반 일정계획
Transporter Scheduling with Transporter Combination in Shipbuilding 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper