The Berth Allocation and Quay Crane Assignment Problem with Crane Setup and Travel Times

In this paper we consider, for the first time, the setup and travel times of cranes in the berth allocation and quay crane assignment problem. We first propose a new mixed integer linear programming model (MILP) for the problem without setups (BACASP), in which neither the berthing positions nor the times need to be integer. Several groups of valid inequalities are also set forth. As to the BACASP with crane setup and travel times, which we denote as BASCASP-S, we propose two MILPs: the first one is based on the previous BACASP formulation and the second one is based 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