Modeling Liner Shipping Service Selection and Container Flows using a Multi-layer Network

We introduce a new formulation for the tactical planning problem facing container shipping companies of selecting the best subset of sailing routes from a given pool of candidate routes so as to maximize profit. 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 (which most previous models do not incorporate). Our multi-layer multi-commodity model associates one commodity with each container origin port, and decides the route for each commodity on a logical network layer whose arcs represent segments (pairs of ports between which a container can use a single service). This approach, combined with commodity flow variables that are indexed by segment sequence permits us to incorporate the transshipment limits while also tracking the commodity’s outflow from the system at various individual destinations. We model the service selection and capacity constraints at the physical layer by allocating the total flow on each segment to various chosen services that can transport the loads on the segment, subject to service capacity constraints. These modeling strategies yield a model that is smaller and easier to solve than a disaggregated multi-commodity model with transshipment limits. We present computational results for realistic problem instances from the benchmark suite Liner-Lib.