Modeling and Solving the Liner Shipping Service Selection Problem

We address a tactical planning problem, the Liner Shipping Service Selection Problem (LSSSP), facing container shipping companies. Given estimated demand between various ports, the LSSSP entails selecting the best subset of non-simple cyclic sailing routes from a given pool of candidate routes, and transporting as much demand as possible over the chosen routes. Since most containers are sent directly or transshipped at most twice in current liner shipping networks, we impose limits on the number of transshipments for each container. The objective is to maximize the net revenue, i.e., revenue from demand served less shipping costs. We propose a new hop-constrained multi-commodity arc flow model for the LSSSP that is based on an augmented network containing, for each candidate route, an arc (representing a sub-path) between every pair of ports that the route visits. This sub-path construct permits us to accurately model transshipment costs and incorporate routing policies such as maximum transit time, maritime cabotage rules, and operational alliances. Our hop-indexed arc flow model is smaller and easier to solve than path flow models. We outline a preprocessing procedure that exploits both the routing requirements and the hop limits to reduce problem size, and describe techniques to accelerate the solution procedure. We present computational results for realistic problem instances from the benchmark suite LINER-LIB.