Dynamic container deployment: Two-stage robust model, complexity, and computational results

Containers are widely used in the shipping industry mainly because of their capability to facilitate multimodal transportation. How to effectively reposition the nonrevenue empty containers is the key to reduce the cost and improve the service in the liner shipping industry. In this paper, we propose a two-stage robust optimization model that takes into account the laden containers routing as well as the empty container repositioning, and define the robustness for this model with uncertainties in the supply and demand of the empty containers. Based on this definition, we present the robust formulations for the uncertainty sets corresponding to the ℓp-norm, where p = 11 2, and ∞, and analyze the computational complexities for all of these formulations. The only polynomial-time solvable case corresponds to the ℓ1-norm, which we use to conduct the numerical study. We compare our approach with both the deterministic model and the stochastic model for the same problem in the rolling horizon simulation environment. The computational results establish the potential practical usefulness of the proposed approach.