Primal decomposition for berth planning under uncertainty

Abstract

Berth planning is an important decision in port operations. The uncertainties in maritime transportation may result in uncertain ship arrival and service times at a port for every week of a planning horizon. In a realistic maritime transportation environment, the uncertain information on ship arrival and service times for a week become known only after a decision is made in the previous week. This study proposes a multi-stage stochastic integer programming (SIP) model for a tactical-level port berth planning problem under uncertainty, which tries to make fixed baseline berthing plans to fit shipping liners’ preferred time slots and reduce their expected delay costs with actual ship arrival and service times for all the weeks of a planning horizon. We propose an original primal decomposition algorithm to solve the multi-stage SIP model. The proposed algorithm passes primal columns of subsequent-stage problems to the first-stage problem to approximate the subsequent-stage decision-making. This algorithm can be generalized to a variety of similarly structured multi-stage SIP models. Using actual berthing data from Xiamen port, we conduct experiments to validate the efficiency of our primal decomposition algorithm. We also conduct experiments to quantify the benefit of using stochastic programming to model the berth planning, the benefit of modelling the problem as a multi-stage program, the benefit of the scenario reduction method designed in this study, and the algorithmic scalability. The proposed multi-stage SIP model for berth planning as well as the primal decomposition algorithm could be potentially useful for port operators to improve operational efficiency of container terminals in uncertain environments.