Optimization models and methods for maritime cargo and inventory routing problems

Abstract

This thesis is part of the DOMinant II project. The DOMinant II project is a collaboration between three Norwegian research groups within the field of operations research. The goal of the project is to reduce the gap between the research frontier and the needs of Norwegian and international maritime and road-based transport industry, by developing new models and solution algorithms for computationally challenging discrete optimization problems in this field. As part of the project, the aim of this thesis is to develop models and efficient and effective solution methods for realistic maritime cargo and inventory routing problems. This thesis consists of four papers. The papers are connected to each other in a way to achieve the goals of the thesis and to partially cover the aims of the DOMinant II project. The first paper provides a benchmark suite for industrial and tramp ship routing and scheduling problems. The second paper considers a problem that combines traditional tramp shipping with a vendor managed inventory (VMI) service and presents a heuristic for realistic sized instances. The effect of offering VMI services to traditional tramp shipping industry is then analyzed. The third paper which covers a large part of the thesis’ purpose, introduces a rich maritime inventory routing problem. In the paper, some realistic features such as considering multiple products and a many-to-many distribution structure make the problem very complex. A hybrid matheuristic is developed to solve realistic instances of the problem within reasonable computing times. The fourth paper focuses on the very well-known ALNS algorithm which is implemented in the first paper, to investigate the role of randomization in this algorithm by using empirical tests through statistical tools. The results indicate that initial implementations of simple straight-forward deterministic alternatives are immediately able to match the performance of the randomized components.