Solving the ship inventory routing and scheduling problem with undedicated compartments

This paper presents a ship inventory routing and scheduling problem with undedicated compartments (sIRPSP-UC). The objective of the problem is to find a minimum cost solution while satisfying a number of technical and physical constraints within a given planning horizon. In this problem, we identify four sub-problems that need to be decided simultaneously: route selections, ship selection, loading, and unloading activity procedures. To solve this problem, first, we developed a mixed integer linear programming model. We then developed a one-step greedy heuristic, and then based on this heuristic, we propose a set of heuristics. Each heuristic has a combination of rules for each sub-problem. A number of problem instances are used to compare the solutions of the two approaches. We applied selected good combinations of rules to solve each problem using the heuristic approach. The results show that 8 out 12 of the considered problem instances have no gap with MILP solution solved using LINGO. We also find that the average gap is 1.96%. In contrast when we consistently use the same combination for all iterations, there are no dominant combinations of heuristics that can find good solutions for all the problem instances.