Aluno: Marcelo Wuttig Friske
Orientadora: Profª. Drª. Luciana Salete Buriol
Coorientador: Prof. Dr. Eduardo Camponogara
Título: Solution Methods for a Maritime Inventory Routing Problem
Linha de Pesquisa: Algoritmos e Otimização
Local: Prédio 43412 – Sala 218 (sala de videoconferência) do Instituto de Informática da UFRGS
– Prof. Dr. Agostinho Miguel Mendes Agra (UA – Portugal – por videoconferência)
– Prof. Dr. Reinaldo Morabito Neto (UFSCAR – por videoconferência)
– Prof. Dr. Marcus Rolf Peter Ritt (UFRGS)
Presidente da Banca: Profª. Drª. Luciana Salete Buriol
Abstract: This work presents a matheuristic framework for solving two formulations of a single product Maritime Inventory Routing Problem. The problem combines two main components: ship routing and inventory management at ports. Each port has a storage capacity and produces or consumes a certain amount of product during the planning horizon. The vessels differ between capacity, speed, and traveling costs. The problem consists in defining a route and schedule for each vessel, which is a sequence of visits to loading and discharging ports in specific time periods, and the quantity of product to be loaded/unloaded in each port visit. Constraints on ports inventory and vessels capacity are accounted, besides side constraints based on the real world scenario. The objective is to maximize the revenue of delivering product at discharging ports, deducted traveling and operational costs. The matheuristic framework was tested in two discrete-time formulations: a time-space network model and a fixed-charge network flow model. Additional constraints and valid inequalities are added to the formulation to tighten the linear relaxation and improve the framework performance, as the models cannot be solved directly by state-of-the-art mathematical solvers in reasonable computational time. The matheuristic framework used for solving the formulations is composed by a relax-and-fix algorithm and by four proposed MIP-based local searches. The relax-and-fix builds an initial solution and consists in dividing the original problem into subproblems, relaxing and fixing integer variables iteratively. MIP-based local searches are improvement procedures, which solve mixed integer subproblems derived from a solution partially fixed.Tests were carried out on instances from the literature and on modified instances. The computational results demonstrated that both formulations provided good solutions in reasonable computational time, including new best-known values for the literature instances. Although using different parameters on the relax-and-fix algorithm and MIP-based local searches, the tests with the fixed-charge network flow model outperformed the time-space model considering the average deviation value from the best-known solutions, and the number of instances in which feasible solutions were found. Future research on this thesis will focus on improvements in the matheuristic framework and the development of a metaheuristic approach for solving large size problem instances.
Keywords: Maritime Inventory Routing Problem. Matheuristics. Relax-and-Fix. MIP-based Local Search.