The sample average approximation method for empty container repositioning with uncertainties

One of the challenges faced by liner operators today is to effectively operate empty containers in order to meet demand and to reduce inefficiency in an uncertain environment. To incorporate uncertainties in the operations model, we formulate a two-stage stochastic programming model with random demand, supply, ship weight capacity, and ship space capacity. The objective of this model is to minimize the expected operational cost for Empty Container Repositioning (ECR). To solve the stochastic programs with a prohibitively large number of scenarios, the Sample Average Approximation (SAA) method is applied to approximate the expected cost function. To solve the SAA problem, we consider applying the scenario aggregation by combining the approximate solution of the individual scenario problem. Two heuristic algorithms based on the progressive hedging strategy are applied to solve the SAA problem. Numerical experiments are provided to show the good performance of the scenario-based method for the ECR problem with uncertainties.

► We build a two-stage stochastic model. ► We apply Sample Average Approximation (SAA) to solve the stochastic programs. ► We apply progressive hedging based algorithms to solve the SAA problems. ► Scenario decomposition is considered. ► Operational cost could be obviously reduced compared with the deterministic model.