Liner shipping network design - a new decomposition

Liner shipping is the foundation for global commerce, but international shipping is responsible for about 2.7% of the global CO2 emission. It is therefore important to develop decision support tools for designing liner shipping networks, minimizing energy consumption. Formally, the liner shipping network design problem is to construct a number of routes operated on a weekly schedule such that a given set of demands can be transported at minimum operational cost. Only a few MIP models have been proposed for this problem, and generally these models are only able to solve small problems to optimality. Hence, most algorithms are based on a two-stage decomposition: First, a number of routes are constructed, and then a multi-commodity network problem is solved to flow the demands through the network. However, due to the complexity of solving large-scale multicommodity flow problems with time constraints, it is only possible to search a small subset of routes. In this talk we present a dierent decomposition based on first flowing the demand, and then constructing routes that cover the flow. The proposed relaxation is a time-constrained network design problem with edge setup costs. This problem is also NP-hard to solve, so a heuristic approach is used based on variable-size neighbourhood search. At the end of the presentation it is discussed how solutions to the relaxed problem can be used to construct routes for the original liner shipping network design problem.