• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2018.tde-18092018-090636
Documento
Autor
Nome completo
Gabriel Feriancic
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2005
Orientador
Banca examinadora
Cunha, Claudio Barbieri da (Presidente)
Brinati, Marco Antonio
Morabito Neto, Reinaldo
Título em português
Modelagem matemática do problema de programação de entregas de derivados de petróleo.
Palavras-chave em português
Algoritmos
Derivados de petróleo
Heurística
Modelos matemáticos
Pesquisa operacional
Resumo em português
Esta dissertação trata do problema da distribuição de combustíveis com caminhões-tanque para realizar a entrega de derivados de petróleo para diversos postos de abastecimento a partir de uma base de distribuição. O problema consiste da determinação de rotas para veículos de uma frota heterogênea, visando minimizar o custo total de distribuição dos veículos envolvidos sujeitos a restrições de capacidade dos compartimentos de cada veículos. O objetivo é garantir que cada entrega seja alocada a exatamente um veículo e que todos os veículos sejam adequadamente seqüenciados. Deve-se notar que cada caminhão pode ter até seis compartimentos com diferentes capacidades. Além disso, são consideradas restrições que impedem que um veículo atenda determinado cliente. As restrições relacionadas a essa alocação de pedidos aos compartimentos dos veículos fazem esse problema tornar-se muito diferente de outros problemas de roteirização de veículos. Para ilustrar isso, uma entrega de 5.000 litros para um cliente apenas pode ser alocada em um compartimento de exatamente 5.000 litros, mas não a um compartimento maior preenchido parcialmente. Adicionalmente, caminhões do mesmo tamanho e capacidade (e.g. 30.000 litros) podem possuir diferentes números de compartimentos, inclusive de diferentes tamanhos (e.g. um caminhão de 30.000 litros pode ter 6 compartimentos de 5.000 litros ou 2 compartimentos de 10.000 litros e 2 compartimentos de 5.000 litros), tornando o problema aindamais complexo. Propõe-se inicialmente uma modelagem matemática inédita para o problema. Dada a dificuldade de resolver instâncias de tamanhos reais utilizando ferramentas comerciais de otimização como o ILOG CPLEX 9.0, foi também proposto um algoritmo heurístico que pode alcançar boas soluções em tempos curtos de processamento. Este algoritmo é inspirado em algumas idéias do GRASP. ) Ele se baseia em um método heurístico rápido de construção, que é repetidamente aplicado, baseado em um algoritmo de controle que, repedida e aleatoriamente, remove alguns pedidos da solução corrente, e então reconstrói uma nova solução a partir dos pedidos não-alocados restantes. Também são relatados resultados computacionais com diversos problemas de teste que foram gerados, considerando diferentes tamanhos de problema, bem como diferentes níveis de dificuldade de alocação de pedidos aos caminhões.
Título em inglês
Mathematical modeling of the petroleum derivatives distribution problem.
Palavras-chave em inglês
Algorithms
Heuristic
Mathematical modeling
Operational research
Petroleum derivates
Resumo em inglês
This Master's dissertation deals with the problem of distributing fuels by petroleum tank trucks in the context of the delivery of petroleum products to gas stations originating at a single distribution base. The problem comprises determining the vehicle delivery routes for a heterogeneous fleet, aiming to minimize the total distribution and fixed costs of the vehicles involved subject to capacity constraints for the tank compartments of each vehicle. The objective is to ensure that each delivery is assigned to exactly one truck and all trucks are properly sequenced. It should be noticed that each truck may have one to six tank compartments with different capacities eventually. In addition, there may be restrictions on which vehicles can service each client. The constraints related to the assignment of deliveries to truck compartments makes this problem much different from other vehicle routing problems, thus preventing the traditional routing approaches and formulations to be applied in this case. To illustrate this, a delivery of 5,000 liters to a single client can only be assigned to a compartment of exactly 5,000 liters, but not to a larger compartment which is not entirely filled up. In addition, trucks of the same size and capacity (e.g. 30,000 liters) may have different numbers of compartments and even different sizes (e.g. a 30,000 liters truck may have 6 compartments of 5,000 liters or 2 compartments of 10,000 liters and 2 compartments of 5,000 liters), making the problem even more complicated. We initially propose a novel mathematical IP formulation for this problem. Given the difficulty to solve instances of the same size as found in practice using off-the-shelf cutting-edge optimization tools like ILOG CPLEX 9.0, we also propose a heuristic algorithm that can reach good solutions in very short CPU times. This algorithm is inspired on some ideas of GRASP. ) It relies on a fast constructive heuristic, which is repeatedly applied, based on a control algorithm that repeatedly and randomly remove some deliveries from the current solution, and then rebuilds a new solution from the remaining unassigned and unrouted deliveries. We also report the computational results with several test problems that we have generated, considering different problem sizes, as well as different levels of difficulty related to assignment of orders to trucks.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2018-09-18
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.