Premium
A new formulation for the liner shipping network design problem
Author(s) -
Ameln Marie,
Sand Fuglum Julie,
Thun Kristian,
Andersson Henrik,
Stålhane Magnus
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12659
Subject(s) - transshipment (information security) , network planning and design , polyhedron , mathematical optimization , computer science , set (abstract data type) , flow network , class (philosophy) , service (business) , layer (electronics) , mathematics , artificial intelligence , computer network , chemistry , geometry , computer security , economy , organic chemistry , economics , programming language
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.