Branch And Price Algorithm For The Integrated Berth Allocation And Quay Crane Assignment

Container-based transport is crucial to international trade.Both berth allocation and quay crane assignment directly influence the operating efficiency of container terminals,and therefore are important issues faced by the terminal operators.Moreover,due to the fact that quay cranes and berths,to some extent,are bound to each other,their integrated allocation becomes more difficult.Therefore,studying how to generate a proper integrated allocation of berths and quay cranes is of significance.This paper studies an integrated problem for the berth allocation and quay crane assignment,with the aim to settle the berth and quay crane profile for each incoming vessel over the planning horizon.In the problem,no overlapping of resources among vessels,time windows for both vessels and berths,the availability of quay cranes,and many other constraints should be satisfied.The features of this problem include the following two points: 1)berths and quay cranes to be allocated simultaneously;and 2)the duration time of vessels depending on the berthing time and the chosen quay crane profile which in turn determines the specific assignment of quay cranes.In contrast to the heuristic algorithm adopted in most of existing research in this field,a branch-and-price algorithm,which has the global optimal perspective,is sought in this paper.Specifically,the Dantzig Wolfe decomposition method is adopted to decompose the original problem into a master problem that correlates all vessels and several pricing problems,each of which only deals with one vessel.In this decomposition framework,three heuristics are designed to help generate better initial feasible columns.Moreover,the sub-gradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon.The branching strategy is implemented in the pricing problem rather than in the master problem to avoid incurring new dual prices,simplifying the branching process.Both breadth-first and depth-first searching policies are applied to select the next node.Based on numerical experiments,the following techniques or policies adopted respectively in the three stages of branch-and-price process are tested: the generation of initial feasible columns,column updating and node selection.The numerical results reveal some conclusions.In the stage of initial feasible columns generation,the time-based algorithm is better than other heuristic algorithms in terms of generating better initial columns,which can lead to faster convergence.In the stage of column updating,the hybrid column-generation method,which integrates the sub-gradient-based Lagrangian relaxation to alter the dual price,does not perform as well as claimed in other literature.In the stage of node selection,the breadth-first method is more stable than the depth-first in terms of the fluctuation in solving time.In addition,the numerical experiments also show that the branch-and-price presented in this paper outperforms the CPLEX in terms of both solution quality and computational time.