A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards

With the trend towards mega-vessels and shipping alliance, the importance of transshipment activities keeps increasing. In transshipment yards, a “yard template” is often used to stack containers in dedicated areas (sub-blocks) pre-reserved for their own destination vessels. At short-term planning level, the yard template is given, but the containers going to a specific vessel still have high flexibility to be allocated among many pre-reserved sub-blocks. The amount of containers allocated to each sub-block, i.e. “container allocation”, not only affects the traffic congestion, but more importantly determines the number of yard cranes (YCs) required in each block. The limited YCs have to switch blocks to fit the needs of container allocation in different periods, i.e. “YC deployment”. This study integrated these two closely related problems and formulated a MIP model. Since the model has a nice block-diagonal structure, column generation under Dentzig Wolfe decomposition was proposed to get lower bounds. A novel branch-and-price (B&P) method was proposed to find near-optimal solutions. To reduce the searching tree size, our B&P method branched on YC paths during the planning horizon, instead of branching on decision variables directly. Numerical experiments under both small and large scale problems showed that our B&P method could efficiently solve the integrated planning problem. The results also showed that YC movements could be reduced effectively without sacrificing operational efficiency or using more yard cranes.