A New Optimization-based Algorithm for a Maritime Inventory Routing Problem

Maritime transportation has a long tradition of taking a dominant role in the global trade. Remarkable improvements in the efficiency of maritime transportation have been made in the last 50 years, but still significant improvements can be made by improving the routing and scheduling of ships through the use of operations research (OR). This thesis considers the problem of routing bulk tankers to minimize costs while managingthe inventory in ports. Multiple unmixable products are transported and the allocation of products to undedicated compartments on board the ships is an important aspect of the problem. One aim of the thesis is to contribute to the literature on maritime inventory routing problems (MIRPs) by including the dynamic allocation of products to undedicated compartments on board the ships. An arc-flow formulation of the problem is proposed together with several types of valid inequalities and tightening constraints. The model has been tested on three differently sized test cases. The valid inequality imposed on the minimum number of compartments needed in each port was the most efficient valid inequality. The formulation proposed proved difficult to solve with an exact solution method within a reasonable time. We propose a new optimization based algorithm for solving the multiproduct MIRP. The algorithm is an iterative matheuristic, and it utilizes the structure of the problem. In a construction phase, the routing component of the problem is extracted and solved independently based on the series of valid inequalities designed. When the solution of the routing problem is known, the remaining part of the problem is solved with the sequence of port visits from the routing problem fixed. If the problem is not feasible given the current routes, new routes are generated utilizing information from the infeasibilities. The iterations continue until a feasible solution is found. An improvement heuristic is utilized to improve the discovered feasible solution. By decomposing the problem, the size of each of the two subproblems is reduced remarkably. The effectiveness of the exact solution method decreases with the size of the test case. Simultaneously, the effectiveness of the matheuristic increases with the size of the test case. On average, the construction phase of the matheuristic returns high quality solutions in significantly shorter time than the exact solution method. The solutions are further improved in the improvement phase. The proposed matheuristic represents a remarkable improvement in both efficiency and solution quality when solving the complex MIRP