A new formulation for the liner shipping network design problem
- 20 March 2019
- journal article
- research article
- Published by Wiley in International Transactions in Operational Research
- Vol. 28 (2) , 638-659
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.Keywords
Funding Information
- Norges Forskningsråd (Dominant II)
This publication has 18 references indexed in Scilit:
- Optimization in liner shipping4OR, 2017
- A matheuristic for the liner shipping network design problemTransportation Research Part E: Logistics and Transportation Review, 2014
- Containership Routing and Scheduling in Liner Shipping: Overview and Future Research DirectionsTransportation Science, 2014
- A Base Integer Programming Model and Benchmark Suite for Liner-Shipping Network DesignTransportation Science, 2014
- Ship routing and scheduling in the new millenniumEuropean Journal of Operational Research, 2013
- Joint Routing and Deployment of a Fleet of Container VesselsMaritime Economics & Logistics, 2009
- Ship Scheduling and Network Design for Cargo Routing in Liner ShippingTransportation Science, 2008
- Ship Routing and Scheduling: Status and PerspectivesTransportation Science, 2004
- Classical and modern heuristics for the vehicle routing problemInternational Transactions in Operational Research, 2000
- Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraintsOperations Research Letters, 1991