How to operate ship fleets under uncertainty

Abstract

Ships operated by a liner company are scattered around the world to transport goods. A liner company needs to adjust its shipping network every few months by repositioning its ships to respond to uncertain container shipping demand. Few studies investigate a liner company's multiperiod heterogeneous fleet deployment problem under uncertainty, considering fleet repositioning, ship chartering, demand fulfillment, cargo allocation, and adaptive fleet sizes. To this end, this study formulates a mixed-integer linear programming model that captures all of these elements. This study also designs a Benders-based branch-and-cut algorithm for this non-deterministic polynomial-time (NP)-hard problem. Two types of acceleration strategies, including approximate upper bound tightening inequalities and Pareto-optimal cuts, are applied to improve the performance of the algorithm. Extensive numerical experiments show that the proposed algorithm significantly outperforms CPLEX and its Benders decomposition framework in solving the model. We conduct an intensive analysis and find that multistage stochastic programming can lead to better solutions than two-stage stochastic programming. We also find that 10% of the benefit provided by the multistage model over the two-stage model is due to better fleet deployment decisions and that 90% of the benefit is due to better demand fulfillment and allocation decisions. By exploring three practical questions regarding driver analysis of liner company profitability, benefits analysis of adaptive fleet sizes, and the influence of the COVID-19 pandemic on liner shipping, we show how liner companies can benefit from managerial insights obtained in this study.