Multi-period empty container repositioning with stochastic demand and lost sales

This paper considers repositioning empty containers between multi-ports over multi-periods with stochastic demand and lost sales. The objective is to minimize the total operating cost including container-holding cost, stockout cost, importing cost and exporting cost. First, we formulate the single-port case as an inventory problem over a finite horizon with stochastic import and export of empty containers. The optimal policy for period n is characterized by a pair of critical points (A n, S n), that is, importing empty containers up to A n when the number of empty containers in the port is fewer than A n; exporting empty containers down to S n when the number of empty containers in the port is more than S n; and doing nothing, otherwise. A polynomial-time algorithm is developed to determine the two thresholds, that is, A n and S n, for each period. Next, we formulate the multi-port problem and determine a tight lower bound on the cost function. On the basis of the two-threshold optimal policy for a single port, a polynomial-time algorithm is developed to find an approximate repositioning policy for multi-ports. Simulation results show that the proposed approximate repositioning algorithm performs very effectively and efficiently.