The berth allocation and quay crane assignment problem with crane travel and setup times

Abstract

In this paper, we propose a new approach for including quay crane travel and setup times in the berth allocation and quay crane assignment problem. We first develop a new mixed integer linear programming model (MILP) for the problem without setups (BACASP), in which berthing positions and times are considered as continuous variables. Several groups of valid inequalities are also set forth. Then, for the BACASP with crane travel and setup times, which we denote as BACASP-S, we propose two MILPs: the first is based on the previous BACASP formulation and the second on routing formulations. Due to the complexity of the BACASP-S, we also propose a genetic algorithm and an exact approach which combines various MILPs with the genetic algorithm. All methods and valid inequalities are computationally tested over two different sets of randomly generated instances. According to the results, the models and algorithms can optimally solve, in less than one hour, BACASP-S instances of up to 40 vessels within a quay one kilometer long and a time horizon of one week. Additionally, extensive experiments were conducted on a new large set of instances to assess the effect of various BACASP-S input parameters on the computation effort required to solve the problem. Ceteris paribus, the computational effort required seems to increase with decreasing number of cranes, while vessel processing times and crane setup times seem not to affect it.