Tramp Ship Routing with Transshipment Possibilities: Solution Approaches and Parameter Estimation Methods

This paper presents solution methods for tramp ship routing and scheduling problems with transshipment possibilities. It presents formulations which are able to find optimal solutions for relatively small instances and heuristics which can determine low-cost solutions when the problem instances become larger. Furthermore, parameter estimation methods are presented which can be used to determine efficient parameter settings for the different heuristics. Finally, nine different sets of parameters are provided which can be adopted for different types of problems, dependent on their characteristics. For all methods the benchmark instances as provided by Hemmati et al. (2014) are used to estimate performance. Out of the 240 problem instances provided there, new optimal values were found or confirmed for 15 instances and improved solutions were found for 59 instances. Finally, by including transshipment possibilities in the model, a cost decrease was found for 144 of the problems. In some cases, this corresponded to cost savings of well over ten percent.