Column Generation for the Integrated Berth Allocation, Quay Crane Assignment, and Yard Assignment Problem

摘要

This study investigates an integrated optimization problem on the three main types of resources used in container terminals: berths, quay cranes, and yard storage space. It presents a mixed integer linear programming model, which takes account of the decisions of berth allocation, quay crane assignment, and yard storage space unit assignment for incoming vessels. In addition, since the majority of the liner shipping services operate according to a weekly arrival pattern, the periodicity of the plan is also considered in the model and in the proposed algorithm. To solve the model on large-scale instances, a column generation (CG) procedure is developed to provide a lower bound for the integrated problem, in which an exact pseudopolynomial algorithm is designed for the pricing problems. Using this procedure, we propose a CG-based heuristic with different solution strategies and apply dual stabilization techniques to accelerate the algorithm. Based on some realistic instances, we conduct extensive numerical experiments to validate the effectiveness of the proposed model and the efficiency of the algorithm. The results show that the CG-based heuristic can yield a good solution with an approximate 1% optimality gap within a much shorter computation time than that of CPLEX.