Network Design for Container Shipping Using Cutting Planes

The network design problem in container shipping is of increasing importance in the strongly competitive markets where potential cost reductions are of the utmost importance. We combine the network design and fleet assignment problem into a mixed integer linear programming model minimizing the overall cost.

The real-life container shipping network design problem differs in several ways from the standard network design problem. Examples of these differences are the cyclic routes of vessels and the fact that a route is continuously sailed for a given forecast period. To model these real-life situations we have introduced a cyclic constraint and included the time of a vessel route in the calculation of the capacity of that route.

Moreover we have added an inhomogeneous fleet to the model and included the cost of transshipment, which is one of the major costs for shipping companies. To simulate the fact that the route of a ship allows for subtours, we introduce the concept of pseudo-simple routes. To solve the problem we use a branch and cut solution method using clover and capacity cuts we defined for the problem.