Two essays on liner shipping network design

Abstract

Liner shipping network design is a comprehensive decision problem for the carrier to plan their service operations. A series of related decisions from tactical and operational levels are coordinated to maximize the profits. In this thesis, we study two network design problems for carriers in liner shipping. The first work focuses on the joint decision makings for the network design, in which a general fuel consumption function is assumed. The second work studies the solution to a compact optimization model for the network design, in which the transshipment cost is taken into account. In this thesis, we have developed novel optimization techniques to solve both problems. In the first study, we develop a mathematical programming model that addresses fleet deployment, speed optimization, and cargo allocation jointly, so as to maximize total profits for carriers at the strategic level. To capture fuel costs precisely, our model adopts a general fuel consumption function that depends on both vessel speed and vessel load. To overcome intractability caused by nonlinear terms in the model, we separate fuel consumption costs into two terms associated with ship speed and ship load, respectively, so as to obtain a mixed integer linear programming formulation for approximation. Based on column generation techniques, we develop an iterative search algorithm that adaptively reorganizes the approximated formulation. We conduct extensive experiments using generated data sets from actual liner shipping services in different regions of the world to show the effectiveness of our approach as well as the significant impact of speed-load factors on fuel consumptions. Managerial insights are obtained by testing the model under different scenarios, which may greatly assist decision makers in the liner shipping industry. In the second study, we study a problem that aims at creating a set of regular services for a designated fleet of oceangoing ships to transport the containerized cargos among seaports. Containers can be transshipped from one ship to another at an intermediate port in order to improve the transportation efficiency. The objective of the problem is to maximize the revenues from the satisfied demands while minimizing the operating cost including the transshipment cost. For this issue, many solution methods known to be effective for problems assuming zero transshipment cost cannot directly apply, because the calculation of transshipment cost has significantly complicated the problem and its mathematical formulation. To tackle this challenge, we develop for this problem a new compact mixed-integer linear programming model. However, the new model may contain exponentially many variables and constraints, making its solution very challenging. Therefore, we propose a novel application of simultaneous column-and-row generation to solve the linear programming relaxation of the new model, so as to derive an upper bound for the profit of an optimal network design. Based on this, we have developed a branch-and-price to find optimal or near-optimal integer solutions for this problem. Results from experiments have shown the effectiveness and efficiency of our models and solution methods.