| dc.description.abstract | International shipping is a multibillon dollar business and shipping companies may expect large benefits from improving the routing and scheduling processes of their ships. There has been scarce research efforts when comes to planning problems in liner shipping in contrast to the size and the possible impact of optimization within the industry. Existing reviews on ship routing have mainly focused on industrial and tramp shipping.
In this thesis we have developed three rich exact mathematical models for the liner shipping network design problem (LS-NDP). We take the perspective of a liner shipping company. The objective of the models is to minimize costs by designing an efficient network of routes that satisfy all demand. The three models differ in terms of which route structures they allow. Howevee, they all include important features as transhipment, transhipment cost and a heterogeneous fleet vessel.
The first model, called the \emph{Basic model} constructs simple routes - i.e. routes where no ports can be visited more than once. The two other models are comprehensive models that extend the Basic model to incorporate more complex route structures - i.e. routes where some ports are visited more than once. These models are denoted \emph{the Flower model} and \emph{the Chain model}, and they possess different properties, both in terms of the functionality they provide and how they are modelled. The Flower model allows for a mix of simple and flower routes. A flower route is defined as a route where one and only one port can be visited a multiple number of times in the same route. The Chain model allows for a mix of simple routes and chain routes. A chain route is defined as a route where several ports in one route can be visited at most twice.
%, e.g. \citet{Reinhardt2011},
To the best of our knowledge the most comprehensive liner shipping models have restricted the routes to have at most one port that is visited at most twice, socalled butterfly routes. Thus, as far as we know, this is the first time exact liner shipping models that either incorporate the possibility of multiple visits to a port or multiple ports that are visited twice, have been presented. Studying the route-nets of the world leading liners and finding that a substantial number of the routes they provide are complex routes, have given us a belief that there is a relevance of this research.
As the LS-NDP is strongly NP-hard and exact formulation of the problem may be too time consuming to solve realistic data instances. It has therefore been made a strong effort to strengthen all the formulations in order to reduce the computation time. This has been done by imposing symmetry breaking constraints and valid inequalities.
The Basic model and the Chain model have been extended to take into account a maximum transit time on the demands.
The main focus in this report is the formulation of the rich LS-NDP models. However, we have also implemented the models and performed limited computational study to see how they behave technically and economically. The models are implemented as a mixed-integer program (MIP) and run by commercial software (Xpress-Mosel). | |
