[pt] No cenário atual da economia mundial, é essencial aumentar a integração entre os diferentes atores da cadeia de suprimentos das empresas, reduzindo custos operacionais e melhorando a eficiência. O roteamento de navios é parte imprescindível dessa integração no comércio marítimo global, sendo objeto de estudo de muitos autores. Neste trabalho, apresentamos diferentes metodologias para resolver variantes do Problema de Roteamento Marítimo com Estoques. Esse problema envolve um grande número de variáveis e é computacionalmente complexo de ser resolvido. Nossa principal motivação é resolver um caso real de roteamento de navios de uma grande empresa do setor de Óleo e Gás, obtendo soluções de alta qualidade em tempos computacionais plausíveis e melhorando os resultados atuais da empresa. Todas as metodologias desenvolvidas são baseadas em uma combinação de uma meta-heurística com um modelo matemático de programação linear. Uma das principais diferenças entre as metodologias está no modelo matemático para resolver o problema de estoque, onde testamos abordagens de tempo discreto e tempo contínuo. As outras diferenças dizem respeito ao número de produtos avaliados (único ou múltiplos produtos) e à meta-heurística usada (heurística de busca local com um fator de probabilidade de Simulated Annealing ou Hybrid Variable Neighborhood Search). Para a metodologia que utiliza um modelo de tempo discreto, os resultados são satisfatórios, com violações baixas e pontuais do estoque em um tempo computacional aceitável. Para a metodologia que utiliza um modelo de tempo contínuo, os resultados são ainda melhores, uma vez que, em reduzido tempo computacional, as violações de estoque permanecem baixas ou inexistentes, dependendo do cenário avaliado e da meta-heurística utilizada. Os resultados obtidos neste trabalho são notáveis e permitem sua aplicação prática em casos reais. / [en] In the current scenario of the world economy, it is essential to increase the integration between the different players in the companies supply chain, reducing operational costs, and improving efficiency. Ship routing is a substantial part of this integration regarding global maritime commerce, being the object of study by many authors. In this work, we present different methodologies to solve variants of the Maritime Inventory Routing Problem. This problem involves a large number of variables and is a computationally complex problem to solve. Our primary motivation is to solve a ship routing real case of a large company in the Oil and Gas sector, achieving high-quality solutions in plausible processing times and improving companies current results. All developed methodologies are based on a metaheuristic combination with a linear mathematical model. One of the main differences between the methodologies lies in the mathematical model to solve the inventory problem, where we tested discrete-time and continuous-time approaches. Other differences concern the number of evaluated products (single or multi-product) and the metaheuristic used (local search heuristics with a Simulated Annealing probability factor or Hybrid Variable Neighborhood Search). For the methodology using the discretetime model, the results are satisfactory, with low and punctual inventory violations in an acceptable computational time. For the methodology using the continuous-time model, the results are better once, in reduced computational time, inventory violations remain low or non-existent, depending on the scenario evaluated and the metaheuristic used. The results obtained in this work are remarkable and allow its practical application for real cases.

[pt] O problema de roteamento de navios com gestão de estoques (conhecido pelo termo em inglês Maritime inventory routing ou MIR) representa um problema prático de logística onde o transportador da carga também é responsável pela manutenção dos estoques do produto transportado nos portos de carga e descarga. Esta tese estuda um caso real do problema MIR. Um conjunto de testes é apresentado de modo a comparar diferentes formulações matemáticas da literatura, a fim de encontrar aquela mais aderente ao problema real. Em função da complexidade computacional do problema, é apresentada uma abordagem heurística que consegue encontrar soluções similares e reduz consideravelmente o tempo computacional quando comparadas com as formulações baseadas em PLIM. No entanto, problemas reais são muito influenciados por aspectos incertos. Sendo assim, é apresentada uma abordagem robusta para a otimização do problema MIR, que considera incerteza no tempo de estadia do navio nos portos. A abordagem apresentada produz soluções para diferentes níveis de robustez. Em outras palavras, considera o risco de variação no tempo de estadia do navio em um porto durante uma operação de carga ou descarga. Assim, é capaz de determinar a probabilidade de inviabilidade da solução encontrada para cada nível de robustez oferecido, além do impacto no custo de transporte à medida que soluções mais robustas são apresentadas. Esta abordagem oferece ao tomador de decisão a medida do trade-off entre robustez e custo de transporte. Desta forma, o mesmo pode determinar qual o nível de conservadorismo irá adotar em sua programação de navios e quanto isto irá impactar o custo de transporte. Os experimentos apresentados identificaram que, aumentos sutís no nível de robustez (com pequeno impacto no custo de transporte) podem reduzir consideravelmente a probabilidade de inviabilidade de uma solução. / [en] Maritime inventory routing (MIR) problem is an academic name for a practical logistic problem that represents the routing or scheduling of vessels to carry product(s) between ports. Meanwhile, the product(s) inventory levels in these ports must remain between operational bounds during the entire planning horizon. This thesis focus on how to support decision on a real-life MIR problem faced by a Brazilian petroleum company. To do so, we structure a set of tests to compare different formulation from literature and identify which is more adherent to real problem. Due to computational complexity of the problem, we present an heuristic approach that provides reasonably good solutions when compared to deterministic mixed integer linear programming (MILP) formulations and reduces considerably the computational time of solving real-life instances. However, uncertainty events have great impact in the ship scheduling planning. Therefore, we propose a robust optimization approach that considers uncertainty in the time spent at ports in each ship visit. Our approach is able to determine the probability of infeasibility and the impact in the objective function for each level of robustness, helping to measure the uncertain aversion of the decision maker. Our experiments identified that, for a certain instance, varying the level of robustness one may reduce the probability of infeasibility from 87 per cent (of deterministic solution) to 2 per cent and it represents an increase in the transportation costs of about 13 per cent.