A Matheuristic Approach For Planning Interrelated Voyages With Separation Requirements In Maritime Transportation

Abstract

Roll-on/Roll-off (RoRo) vessels represent the primary source for transport- ing vehicles and other types of rolling material over long distances. How- ever, comparatively little operational research has been done on RoRo ship- ping, suggesting there is room for improvement. In this thesis, I focus on the single trade ship routing and scheduling problem (STSRSP) in RoRo- shipping. This problem considers which ports a voyage should visit along a trade route, which vessels should be deployed for a given voyages, as well as where and when these vessels should load and unload goods. In the STSRSP, the objective is to minimize the total cost of all activities, while satisfying contractual requirements Hansen et al. (2018). Efforts to solve mathematical formulations of this problem with standard MIP solvers have shown that the run time is prohibitively large for direct use in opera- tional level decisions. Hence, the purpose of this thesis have been to create a heuristic that can be used to reduce the time used to solve single instances of the STSRSP to within an acceptable accuracy. In this thesis, I propose a new solution method to solve the STSRSP. The solution method uses a matheuristic approach that divides the problem into several parts, combining both mathematical models to determine routes and vessel assignment, as well as a heuristic for placing the contracts on voyages. Finally, a service level search is implemented to make sure the separation requirement is satisfied. Computational results show that the matheuristic has the potential to solve STSRSP instances within very short time limits.