A Simultaneous Column-and-Row Generation Solution Method for Liner Shipping Network Design

• 成果类型: Article
• 署名作者: Xia, Jun; Xu, Zhou; Baldacci, Roberto
• 署名单位: Shanghai Jiao Tong University; Hong Kong Polytechnic University; Qatar Foundation (QF); Hamad Bin Khalifa University-Qatar
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.0458
• 发表日期: 2025
• 页码: 1825-1848
• 关键词: fleet deployment; cut algorithm; branch; price; optimization; management; PROGRAMS; speed

摘要

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.