Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-05-22T20:04:01Z No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:27Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:34Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Made available in DSpace on 2017-05-31T13:52:08Z (GMT). No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Vehicle routing problems occur in many practical situations where the distribution of goods and / or services to different demand points is necessary. In this context, this research aims to study a ship routing and scheduling problem that arises at the collection and delivery operations of different types of crude oil from offshore platforms to coastal terminals. In the paradigm adopted for the representation of the problem, the transportation is largely the result of the need to maintain inventories at each supply point (platforms) between minimum and maximum levels, considering production rates on these operating points and the demand attendance of each product in the coastal terminals. The routing and scheduling of the fleet aims to achieve minimum variable cost solutions, and considers various operational constraints, such as the maximum cargo volume transported on each ship, the ships mooring in the operational points ports, the simultaneous unloading of the ships in terminals with more than one berth, among many others. In this research, Inventory Constrained Routing Problem (ICRP) models in the maritime context have been modified and extended for appropriately representating and solving real problems based on data collected in a case study performed on a Brazilian oil company, involving relatively short distances and time horizons. Small sized instances are solved by a mathematical programming software. Given the difficulties of solving larger examples, this study proposes a multistart heuristic method that includes a metaheuristic GRASP and improvement procedures, and also a rolling horizon heuristic. Both methods provide feasible good quality solutions in reasonable computing times. In order to improve the quality of the solutions found by these constructive methods, it is also discussed a procedure that combines the mathematical programming software and local search heuristic methods (matheuristic). The results show the potential of the proposed models and solution methods to tackle the problem and produce competitive solutions. / Problemas de roteirização de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição de bens e/ou serviços a pontos dispersos de demanda. Nesse contexto, a presente pesquisa visa o estudo de um problema de roteirização e programação de navios presente em operações de coleta e entrega de diferentes tipos de óleo cru de diversas plataformas offshore para vários terminais costeiros. No paradigma adotado para representação do problema, o transporte dos produtos é em grande parte o resultado da necessidade de manutenção dos estoques em cada ponto de suprimento (plataformas) entre níveis mínimos e máximos, considerando-se as taxas de produção nesses pontos operacionais, assim como o atendimento da demanda de cada produto nos terminais costeiros para abastecer as refinarias. A roteirização e programação da frota visa a obtenção de soluções de mínimo custo variável e considera várias restrições operacionais, tais como o volume máximo de carga transportada em cada navio, a viabilidade de atracação de navios em portos dos pontos operacionais, os descarregamentos simultâneos de navios em terminais com mais de um berço, dentre várias outras. Nesse sentido, modelos de otimização da literatura de roteirização veículos com restrições de estoque (Inventory Constrained Routing Problem – ICRP) no contexto marítimo foram modificados e estendidos para representação do problema e resolução de exemplares de uma situação real, definidos a partir de dados coletados em um estudo de caso realizado em uma empresa petrolífera nacional, envolvendo distâncias relativamente curtas e com horizontes de planejamento de curto prazo (poucas semanas). Exemplares de pequeno porte são resolvidos por meio da utilização de um software de programação matemática. Dada a dificuldade de resolução dos exemplos de maior porte, é proposto um método heurístico de múltiplos reinícios composto por uma metaheurística GRASP e procedimentos de melhoria, além de uma heurística de horizonte rolante, que proporcionaram a obtenção de soluções factíveis de boa qualidade em tempos computacionais aceitáveis. Com intuito de melhorar a qualidade das soluções encontradas pelos métodos construtivos, é também discutido um procedimento que combina o software de programação matemática e métodos heurísticos com busca local (mateheurística). Os resultados mostram o potencial dos modelos e métodos de solução aqui desenvolvidos e propostos para abordar o problema e produzir soluções competitivas em relação às soluções da empresa.