탠덤 크레인 스케줄링 문제를 위한 분기절단법 알고리즘 연구

A strengthened ILP model and branch-and-cut algorithm for tandem quay operation problem

Container terminals today are facing the challenge of accommodating larger vessels and enhancing productivity in response to the escalating global trade volumes. As part of these endeavors, a novel quay crane has been introduced, capable of equipping multiple spreaders to efficiently manage multiple container handling tasks concurrently. This study delves into the scheduling problem aimed at minimizing the makespan of discharging operations for a ship bay assigned to a quay crane equipped with two spreaders. In this problem, the quay crane can execute either a single lift using a single spreader or a tandem lift using two spreaders, contingent upon weight constraints. Moreover, the associated changeover time for each spreader mode is considered. Building upon this basis, this study introduces a novel integer linear programming (ILP) formulation for addressing this problem. Additionally, enhancement strategies and a branch-and-cut framework are applied to this formulation. This approach was evaluated in 30 instances, comprising 24 and 50 containers, respectively. The experimental results demonstrated that the novel formulation performed well on 50 container instances when compared to previous ILP formulations. Moreover, it solved instances that were previously deemed intractable within the time limit.

컨테이너 터미널은 오늘날 증가하는 글로벌 무역량에 따라 메가 컨테이너선을 수용하고, 터미널의 생산성을 향상해야 하는 과제에 직면해 있다. 따라서, 이러한 추세에 따라 여러 개의 스프레더를 장착해 동시에 여러 컨테이너를 처리할 수 있는 새로운 케이 크레인이 도입되었다. 본 연구는 두 개의 스프레더를 장착한 탠덤 크레인이라고도 불리는 안벽 크레인에 할당된 선박의 안벽 구역에서의 하역 작업의 완료 시간을 최소화하기 위한 스케줄링 문제를 다룬다. 이 문제에서 안벽 크레인은 무게 제약 조건에 따라 단일 스프레더를 사용한 싱글 리프트 또는 두 개의 스프레더를 사용한 탠덤 리프트를 실행할 수 있으며, 스프레더 모드 전환 시에는 전환 시간이 발생한다. 이를 바탕으로 본 연구에서는 이 문제를 해결하기 위한 새로운 정수 계획 모형을 제안한다. 또한, 이 모형의 성능 개선을 위한 전략과 분기절단(branch-and-cut) 프레임워크를 제안한다. 이러한 접근은 24개 및 50개의 컨테이너로 구성된 30개의 인스턴스를 통해 실험되었으며, 본 연구에서 제안한 모형을 기존의 모형들과 비교했을 때 50개의 컨테이너로 구성된 인스턴스에서 우수한 성능을 보였으며, 이전에는 제한 시간 내에 해결할 수 없었던 인스턴스들도 해결할 수 있었다.