Optimal Berth Allocation, Time-variant Quay Crane Assignment and Scheduling with Crane Setups in Container Terminals
We focus on the integrated seaside operations in container terminals, namely the integration of berth allocation, quay crane assignment and quay crane scheduling problems. First, we formulate a mixed-integer linear program whose exact solution gives optimal berthing positions and berthing times of the vessels, along with their crane schedules during their stay at the quay. Then, we propose an efficient cutting plane algorithm based on a decomposition scheme. Our approach deals with berthing positions of the vessels and their assigned number of cranes in each time period in a master problem, and seeks the corresponding optimal crane schedule by solving a subproblem. We prove that the crane scheduling subproblem is NP-complete under general cost settings, but can be solved in polynomial time for certain special cases. Our computational study shows that our new formulation and proposed solution method yield optimal solutions for realistic sized instances with up to sixty vessels.
