Optimization of Container Line Networks with Flexible Demands

Liner shipping is at the core of the world’s supply chains, with an estimated 36 % of the value of global merchandize trade being shipped in containers. The containers, carried on thousands of container vessels in intricate networks operated by global liner shipping carriers, constitute a very important part of the world economy.

Although maritime transport an environmental friendly transport mode, it is also an industry which emits millions of tonnes of CO2 yearly. Highlighting the need to control the environmental impact. Container carriers operate in a highly competitive market, where the assets must be deployed in the best way possible to create a healthy business.

To better manage the assets invested in container shipping and to control the use of fossils fuels used by the liner shipping industry, optimization methods for liner shipping is studied in this thesis. The domain is investigated and models supporting decision making is developed, with the aim of reducing costs, bunker consumption and increasing the revenue and service levels of a liner shipping company.

These problems are complex, dealing with millions of containers traveling on hundreds of vessels calling hundreds of ports, all over the world. From an industry view, the complexity of managing this network has grown tremendously in the last decades, with yearly two-digit growth rates. Developing from a few trades with 10 - 20 vessels deployed, which could be considered independently, to a massively interconnected network spanning the globe.

From a mathematical point of view these problems are among the very hardest, in the class of NP-hard problems. And when considering network design problems, these are among the most difficult of NP-hard problems, which rarely can be solved to optimality for medium or large instances. The problems are studied with operations research techniques, which successfully have been used, for planning and logistical problems in other transportation industries, resulting in great improvements.

The thesis follows two main research directions, the first focuses on liner shipping network design, the second on other decision problems faced in liner shipping, that can be studied with operations research methods. Research in liner shipping network design has been relatively scarce until recently, and the research that has been done, have been distributed, lacked focus and agreement on which aspects where important and relevant to include.

To alleviate this a thorough description of the domain of liner shipping is given, explaining the industry in the words of an operations researcher. At the same time a set of benchmark instances LINER-LIB 2012 is introduced. It is the hope that this description together with the benchmark instances will provide a common ground for research in liner shipping network design, enabling comparisons of methods and easing entry barriers for new researchers in this important field.

This thesis presents three different approaches for liner shipping network design. The first presents a model that allows for the creation of services (loops of vessels, following the same route) connecting to form a liner shipping network. This model is decomposed in a novel manner, where the partial ow of demand and construction of services is done in the same subproblem.

This work also introduces an interesting aggregation of demands, which can greatly reduce the problem sizes. A second approach to liner shipping network design models how demand can ow on services, as opposed to owing directly between ports. This allows for the creation of more complicated networks than previously seen.

By solving an important issue faced by previous liner shipping network design methods, allowing a service to call the same ports, multiple times. This model is implemented and run on the LINER-LIB 2012 instances providing results for these. Lastly a model focusing on the design of a single service is considered.

The method optimizes the profit, while considering operational and commercial aspects of liner shipping as capacity of vessels and transit time of demand, which is a very important factor for designing actual container services. The second part of the thesis considers two decision problems faced in liner shipping.

These are important as the fierce competition in liner shipping, gives very small margins of profit. Due to this a successful carrier, will need to control the details, and consistently manage the operational challenges well. Two examples of this is studied: how to purchase bunker fuel considering contracts and how to manage disruptions in the sailing schedule of a vessel.

Bunker fuel is a huge expense for a liner shipping company, and at current market rates it constitutes up to 30 % of a networks operational cost, equalling in billions of dollars for large container carriers. To manage this, carriers will often use contracts for delivery of bunker to ensure supply and achieve a small discount on volume.

As these contracts are shared between vessels, it constitutes a shared resource, which must be distributed optimally. A model is formulated, which is decomposed, implemented and run on real world problem instances of 500+ vessels and 500+ contracts. The method allows a global liner carrier to efficiently plan bunker purchases for their vessels, using a large number of bunker contracts to lower costs.

Container vessels operate on tight schedules to meet the customers transit time requirements, reach their port berth slots and catch connections to other vessels. Often disruptions occur to the schedules due to adverse weather, mechanical failures and port delays. These disruptions have a great impact on the service provided to customers and the cost for recovering from them are high.

A mixed integer programming model is developed, which can suggest an optimal mitigation for a given disruption. The model considers common disruption scenarios and is run on four real cases, finding optimal solutions in less than 5 seconds. The cases show up to 58 % savings in recovery costs compared to manually realized recovery costs.

This thesis aims at opening up research in the important area of liner shipping network design in a number of ways. It gives a thorough introduction to the domain, presents a number of benchmark instances and proposes several models for liner shipping network design, which highlights important and not previously studied aspects of the problem.

This allows further research in the area to use some of this work as building blocks for new methods. Two operational problems faced in liner shipping are considered with good results, showing the breadth of research areas existing in liner shipping. From an industry point of view, models assisting with design of a single service or small networks have been presented and both the operational models shows promise for implementation in an actual decision support system.

These can help overcome some of the complex problems faced in liner shipping, showing that operations research techniques can be applied to real liner shipping problems.