A simultaneous column-and-row generation solution method for liner shipping network design

Abstract

The liner shipping network design (LSND) problem involves creating regular ship rotations to transport containerized cargo between seaports. The objective is to maximize carrier profit by balancing revenue from satisfied demand against operating and transshipment costs. Finding an optimal solution is challenging because of complex rotation structures and joint decisions on fleet deployment, cargo routing, and rotation design. This work introduces a set partitioning–like formulation for LSND with transshipment costs, featuring an exponential number of variables and constraints. The formulation captures key service components, such as ship type, sailing speed, and frequency. Addressing transshipment costs requires numerous rotation-dependent variables and constraints, making even linear programming relaxation difficult to solve. To tackle this, we propose a simultaneous column-and-row generation (SCRG) solution method with novel speedup techniques. Integrating SCRG into a branch-and-price algorithm, we develop an exact method for LSND and test it on two variants with different rotation configurations. Extensive computational experiments demonstrate the method’s effectiveness and efficiency. In addition to advancing solution methods for LSND, this work enhances the SCRG-based method and expands its practical applications.