Tramp Ship Routing and Scheduling - Incorporating Additional Complexities

In tramp shipping, ships operate much like taxies, following the available demand. This contrasts liner shipping where vessels operate more like busses on a fixed route network according to a published timetable. Tramp operators can enter into long term contracts and thereby determine some of their demand in advance. However, the detailed requirements of these contract cargoes can be subject to ongoing changes, e.g. the destination port can be altered. For tramp operators, a main concern is therefore the efficient and continuous planning of routes and schedules for the individual ships. Due to mergers, pooling, and collaboration efforts between shipping companies, the fleet sizes have grown to a point where manual planning is no longer adequate in a market with tough competition and low freight rates. This thesis therefore aims at developing new mathematical models and solution methods for tramp ship routing and scheduling problems. This is done in the context of Operations Research, a research field that has achieved great success within optimisation-based planning for vehicle routing problems and in many other areas. The first part of this thesis contains a comprehensive introduction to tramp ship routing and scheduling. This includes modelling approaches, solution methods as well as an analysis of the current status and future direction of research within tramp ship routing and scheduling. We argue that rather than developing new solution methods for the basic routing and scheduling problem, focus should now be on extending this basic problem to include additional complexities and develop suitable solution methods for those extensions. Such extensions will enable more tramp operators to benefit from the solution methods while simultaneously creating new opportunities for operators already benefitting from existing methods. The second part of this thesis therefore deals with three distinct ways of extending the basic tramp ship routing and scheduling problem to include additional complexities. First, we explore the integration of bunker planning, then we discuss a possible method for incorporating tank allocations and finally, we consider the inclusion of voyage separation requirements. For each of these extensions, we develop a new solution method and discuss the impact of incorporating these additional complexities. Aside from a comprehensive introduction to tramp ship routing and scheduling, the main contribution of this thesis is the exploration of the three aforementioned extensions of the basic tramp ship routing and scheduling problem. The work on these three distinct extensions together represent a diverse collection of both problems and solution methods within tramp ship routing and scheduling.