A new formulation for the liner shipping network design problem

Abstract

The liner shipping network design problem (LSNDP) is an important problem within liner shipping because a good network can reduce costs and increase profits. Given sets of ports, vessel classes, and demands between the ports, the problem is to design a network of cyclic routes and assign a vessel class to each route so that all demands can flow through the network at minimal cost. In this paper, we analyze a new formulation of the LSNDP based on a two‐layer network structure. The formulation takes into account the cost of transshipment and allows for complex service structures. Valid inequalities and a novel approach of inner representations of low‐dimensional polyhedra are proposed. A new set of small instances with up to 12 ports has been developed and the formulation has been tested on these instances. Instances with up to 10 ports are solved to optimality, but the largest instances are not, confirming that the LSNDP is a very complex problem. The proposed improvements of the formulation are also shown to have a positive effect.