Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals

• We model a berth allocation, crane assignment and scheduling problem (BACASP).
• We devise a MILP formulation for the problem and propose a decomposition algorithm.
• Our method can deal with time-variant crane assignments and crane setup costs.
• We investigate NP-completeness of the crane scheduling subproblem.
• BACASP can be solved optimally for up to 60 vessels using our approach.

There has been a dramatic increase in world’s container traffic during the last thirty years. As a consequence, the efficient management of container terminals has become a crucial issue. In this work we concentrate on the integrated seaside operations, 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.