Solution methods for a maritime inventory routing problem

Abstract

This thesis presents a matheuristic framework and a metaheuristic approach for solving a Maritime Inventory Routing Problem (MIRP). The problem combines two main components: ship routing and inventory management at ports. Each port has a storage capacity and variable production or consumption rates along with the planning horizon. The vessels differ with respect to capacity, speed, and travel costs. The problem consists of defining a route and schedule for each vessel, besides the amount of product loaded or unloaded in each port visit, while keeping the ports’ inventory between lower and upper limits. Constraints on ports inventory and vessel capacity are accounted for the problem, besides side constraints based on a real world scenario. The objective is to maximize the revenue of delivering the product at discharging ports, deducted traveling, and operational costs. The matheuristic framework is composed of a relax-and-fix algorithm and a fix-andoptimize algorithm. The relax-and-fix algorithm builds an initial solution and consists of dividing the original problem into subproblems solved iteratively. The fix-and-optimize algorithm is responsible for improving the solution, solving partially fixed subproblems derived from a starting solution. The matheuristic framework was tested in two discretetime formulations, and several formulations components such as additional constraints, preprocessing phase, restriction strategies, and valid inequalities were proposed. The metaheuristic approach is composed of a multi-start algorithm and a large neighborhood search, being the first proposed method for the MIRP variant considered in this work independent of a mathematical solver. Tests were carried out on instances from the literature and on modified instances. We evaluated the contribution of the different formulation components of the matheuristc framework, besides different parameter values of the metaheuristic approach, considering the solution quality and processing time. We considered tests with a priori parameter setting and also using an automatic configuration tool. The computational results demonstrated that the proposed methods are potentially effective for solving the MIRP when applied to a public dataset, obtaining new best-known solutions, and providing solutions for instances in which no attempts to solve them were presented in the literature.

Esta tese de doutorado apresenta matheuristicas e metaheuristicas para resolver um Problema de Roteamento de Inventário Marítimo (MIRP - Maritime Inventory Routing Problem) de produto único. O problema combina dois componentes chave: o roteamento de navios e a gestão de estoque nos portos. Cada porto possui uma capacidade de estocagem e produz ou consome determinada quantidade de produto ao longo do horizonte de planejamento. A frota de navios é heterogênea, sendo que os navios diferem entre si por capacidade, velocidade, e custos de navegação. O problema consiste em definir uma rota e um escalonamento para cada navio, que é composto por uma sequência de visitas a portos de carregamento e descarregamento em períodos de tempo específicos. Além disso, é necessário definir em cada visita a quantidade a ser carregada/descarregada pelo navio. São consideradas restrições de capacidade de estoque nos portos e capacidade dos navios, além de restrições auxiliares baseadas em cenários do mundo real. O objetivo é maximizar a receita através da entrega de produto nos portos de descarregamento, subtraindo os custos operacionais e de viagem dos navios. A estrutura matheurística é composta por um algoritmo relax-and-fix e por um algoritmo fix-and-optimize. O primeiro constrói uma solução inicial e consiste em dividir o problema em subproblemas que são resolvidos de forma iterativa. O segundo é responsável por melhorar a solução obtida pelo primeiro, resolvendo problemas inteiros mistos parcialmente fixados de forma iterativa. A estrutura matheuristica foi testada em duas formulações de tempo discreto: um modelo de rede espaço-tempo e um modelo de fluxo de carga fixa. Além disso, diversos componentes para foram propostos, tais como restrições adicionais, desigualdades válidas e pré processamento. A solução metaheuristica é composta de um algoritmo multi-start e algoritmo large neighborhood search, sendo o primeiro método a ser proposto para a variante do MIRP considerada neste trabalho que não depende de um resolvedor matemático para obter soluções. Os testes computacionais foram executados sob instâncias da literatura e instâncias modificadas. Nós avaliamos a contribuição de diferentes componentes das formulações da estrutura matheuristica, além de diferentes valores de parâmetros da abordagem metaheuristica considerando a qualidade da solução obtida e o tempo de execução. Foram considerados testes com a definição de parâmetros a priori e também utilizando uma ferramentade configuração automática de parâmetros. Os resultados demonstraram que os métodos propostos são potencialmente efetivos para resolver o problema quando aplicados a um conjunto de instâncias públicas, obtendo novas melhores soluções conhecidas, e fornecendo soluções para instâncias nas quais não foram apresentadas na literatura tentativas de solução.