Liner Service Network Design

This thesis concerns design of liner shipping networks using operations research to optimize liner shipping networks at the strategic, tactical and operational level. Liner shipping networks are often compared to public transit networks as they consist of a set of scheduled sailings connecting at main ports to consolidate freight on large vessels. The liner shipping network is constrained by the composition and size of the vessel fleet and the objective is to maximise the profit of freighting containers between origins and destinations by a high utilization of the capacity of the fleet.
The research field of liner shipping network design is relatively young and many open research questions exists. Among others, a unified and rich mathematical model formulating the main characteristics of the business domain has not been clearly described and exact methods for such mathematical models are still not able to solve significant instances of this complex optimization problem.
In this thesis two research directions are explored within the field: The first research direction contributes to basic research on the liner shipping network design problem by describing the domain seen from the perspective of a global liner shipping carrier, present public realistic data instances of the problem to perform computational experiments, and discuss alternative mathematical models of the problem. A domain description, literature survey and a base integer model of the problem is presented. It is accompanied by the description of a public benchmark suite of data instances and a heuristic column generation algorithm to present the first results for this benchmark suite.
The thesis contains a discussion of the complexity of the liner shipping network design problem in relation to mathematical models. The severe complexity of mathematical models of liner shipping network design is discussed in relation to research on the related classical multicommodity capacitated network design (MCND) and Pick-up-and-Delivery-Vehicle-Routing-Problem (PDVRP). It contains a discussion of applying state-of-the-art exact algorithms using Dantzig-Wolfe decomposition and presents ideas on the design of Branch-and-Cut/Branch-and-Price algorithms.
The second research direction is to identify and analyse tractable problems at the tactical and operational level of liner shipping network design. A mathematical model for revenue management of cargo flows considering the significant repositioning of empty containers (Cargo Allocation Problem with Empty Repositioning ) is presented. The model is a multicommodity flow problem with inter-balancing constraints to account for empty repositioning. An arc-flow formulation is decomposed using the Dantzig-Wolfe principle. A linear relaxation of the path flow model is solved using delayed column generation applying a shortest path algorithm to solve the pricing problem. A feasible integer solution is calculated by rounding the fractional solution and adjusting flow balance constraints with leased containers. Computational results are reported for seven instances based on real-life shipping networks. Solving the relaxed linear path flow model with a column generation algorithm outperforms solving the relaxed linear arc flow model with the CPLEX barrier solver even for very small instances. The proposed algorithm is able to solve instances with 234 ports, 16278 demands over 9 time periods in 34 minutes. The integer solutions found by rounding down are computed in less than 5 seconds and the gap is within 0.01% from the upper bound of the linear relaxation.
At the operational level disruption management is of great concern to liner shippers as 70-80% of vessel round trips experience delays in at least one port. A novel mathematical model for handling a disruption using a series of recovery techniques is presented as the The Vessel Schedule Recovery Problem. The model has been applied to four real life cases from Maersk Line, where the solutions found using the MIP model are comparable or superior to the realised recovery actions performed at Maersk Line. The cases are solved using a commercial solver CPLEX, and solutions are obtained within 10 seconds.
Lastly, we present a matheuristic, which may serve both research directions. The matheuristic aims at solving the liner shipping network design problem in its entirety using a construction heuristic. The heuristic aims at designing a neighbourhood and a local search method, which scales well to realistic sized networks. The heuristic is based upon improving the constructed solution by applying an IP model as a large scale neighbourhood to each service in the network. The IP is based on estimating the benefit of inserting and removing port calls within a predefined neighborhood of candidate ports. Furthermore, the heuristic applies delayed column generation to evaluate the resulting network using a warm start method denoted delta column generation. The IP neighborhood as well as the delta column generation scales well to larger instances and may hence be an inspiration to future method development, but the quality of the solutions may be improved upon by combining it with more advanced local search methods to remove and introduce services in the network. The matheuristic may also be applied at a tactical level, as an existing network may be used as input and improved upon by the heuristic. It is also possible to optimize upon a predefined subset of services, while maintaining a full view of the cargo flows in the network. This could prove a valuable decisions support tool for planners when the network is incrementally adjusted to new market situations and to evaluate the consequence of strategic decisions.
The thesis contributes to the understanding of the domain for the Liner Shipping Network Design Problem. Three different mathematical models for the problem are presented. Two heuristics to solve the first model has been implemented and computational results have been presented for small, medium and large scale instances. The thesis explores two planning problems related to liner shipping network design. The Cargo Allocation Problem with Empty Repositioning is the first model to simultaneously consider cargo allocation considering both ordinary cargo and empty repositioning of containers. Computational results confirm tractability of solving networks of realistic size in reasonable time with this model. We also present a novel model to handle disruptions in liner shipping, The Vessel Schedule Recovery Problem. Computational results for four common disruption scenarios from Maersk Line show comparable or improved results compared to the realised recovery actions.