Heuristic solution methods for ship routing and scheduling problems

Abstract

Ship routing and scheduling is among the most important task for many shipping companies. Today, only few shipping companies use optimization-based decision support systems for routing and scheduling of their fleet. They still accomplish this task manually based on their experience. However, access to an optimization-based decision support system may be of great value for planners in shipping companies. By proper routing and scheduling of their fleets of ships the shipping companies may get the possibility to increase the income by transporting more optional spot cargoes and/or to reduce the sailing costs. This may have an important financial impact for the shipping companies in an increasingly competitive market.

This thesis presents various short-term ship routing and scheduling problems faced by planners in tramp shipping companies, and proposes solution methods for solving them. The focus is on local search-based heuristic solution methods that can find good solutions to the problems within reasonable time, and hence give valuable decision support for the planners.

The thesis consists of two parts. The first part gives an introduction to ship routing and scheduling problems. The second part consists of four papers that are the major contribution of this thesis. The first paper focuses on decision support for planner in shipping companies. In the second paper an efficient tabu search heuristic is described for solving the tramp ship routing and scheduling problem. Flexible cargo quantities are considered in paper 3, while split loads are introduced and discussed in paper 4. The papers have been submitted to international journals, three have been accepted for publication while one is still in the refereeing process.