Container shipping service selection and cargo routing with transshipment limits

We address the tactical planning problem faced by container liner shipping companies to select a set of sailing services from a given pool of candidate services and route available cargo over the chosen services so as to maximize profit. One of the distinctive features of our model is that it incorporates limits on the number of transshipments for each container, a common service requirement in practice. These limits can vary by shipment attributes such as origin and destination, and cargo priority. We propose a new stage-indexed multi-commodity flow model that is based on an augmented network containing links (representing sub-paths) between every pair of ports visited by a candidate service. This sub-path structure, together with our approach of indexing the flow variables by transportation stage, enables the model to accurately capture transshipment costs and enforce transshipment limits. To reduce the computational time to solve this problem, we develop preprocessing steps that exploit network structure to eliminate variables, describe valid inequalities to strengthen the model's linear programming relaxation, and propose an optimization-based heuristic algorithm to generate good initial solutions. We report successful computational results for realistic problem instances from a benchmark suite of liner shipping problems, solved using a standard solver applied to our reduced and strengthened model.