A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards. (April 2017)

• Record Type: Journal Article
• Authors: Jiang, Xin Jia; Jin, Jian Gang
• Is Part Of: Transportation research. Volume 98(2017)
• Page Start: 62
• Page End: 75
• Publication Date: 2017-04
• Subjects: Transshipment container yard -- Yard template -- Yard crane deployment -- Container allocation -- Branch-and-price method; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2016.12.014
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: An MIP model for integrated yard crane deployment and container allocation formulated for short-term planning. Column generation under Dentzig Wolfe decomposition was proposed to find a lower bound based on model structure. A novel branch-and-price method based on YC movement paths has been proposed to search for near-optimal integer solutions. The proposed method could find near-optimal solutions for both small scale and large scale problems. Abstract: 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.