No comércio marítimo global, o roteamento de navios é parte essencial da integração e otimização da cadeia de suprimentos, sendo objeto de estudo de muitos autores. O Maritime Inventory Routing Problem (MIRP) envolve um elevado número de variáveis e, por isso, é considerado um problema computacionalmente complexo de ser resolvido. A busca por soluções de alta qualidade em menores tempos de processamento é uma das motivações deste trabalho. Realizou-se uma revisão de literatura sobre métodos heurísticos e metaheurísticos que, nos últimos anos, são aplicados para a resolução do MIRP, e desenvolveu-se uma metaheurística auxiliada por um modelo matemático de programação linear. Esta abordagem foi aplicada na resolução de um caso real de roteamento de navios de uma importante empresa do setor de Óleo & Gás, capaz de gerar resultados satisfatórios, com violações de estoque baixas e pontuais, boa utilização média dos navios e em um tempo computacional aceitável.