• 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
https://doi.org/10.11606/D.3.2021.tde-01072021-160528
Documento
Autor
Nome completo
Hadir Alexander Garcia Castro
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2021
Orientador
Banca examinadora
Mendes, André Bergsten (Presidente)
Barretto, Marcos Ribeiro Pereira
Leite, Laura Silvia Bahiense da Silva
Título em português
Uma meta-heurística simulated annealing para o problema de localização-roteirização periódico com designação fixa de cliente-depósito.
Palavras-chave em português
Heurística
Localização de instalações
Otimização combinatória
Pesquisa operacional
Roteirização
Veículos
Resumo em português
A localização de instalações e a roteirização de veículos são dois processos logísticos de grande importância no gerenciamento das cadeias de suprimentos. A tomada de decisão sobre a localização de instalações integrada com o processo de elaboração das rotas dos veículos, tem se mostrado vantajosa em vários contextos, gerando ganhos econômicos maiores do que quando as decisões são tomadas sequencialmente. Na literatura, esta classe de problemas é conhecida como problema de localização-roteirização (LRP). Nesta dissertação de mestrado é desenvolvida uma metaheurística simulated annealing (SA) como método de solução para a variante do LRP, que considera um horizonte de planejamento dividido em múltiplos períodos. Esta variante é conhecida como o problema de localização-roteirização periódico (PLRP), sendo a sua principal caraterística a programação periódica dos atendimentos aos clientes, obedecendo a um padrão de visitas definido em função de uma frequência de atendimento preestabelecida por cada cliente. Em um contexto de distribuição periódica com múltiplos depósitos, é comum que existam situações em que os clientes estejam designados a um depósito específico para satisfazer suas demandas em cada período. Esta forma de operação contrasta com aplicações encontradas na literatura, em que os clientes são atendidos a partir de quaisquer depósitos ao longo do horizonte de planejamento. Portanto, nesta dissertação, foi imposta uma designação fixa de cada cliente para um único depósito, por meio de uma restrição incorporada na formulação matemática do PLRP e no método de solução desenvolvido. Uma caraterística da metaheurística SA é a utilização de soluções iniciais que servem como entrada para o algoritmo de busca. Nesta dissertação, as soluções iniciais são geradas utilizando um modelo de programação inteira mista (MIP) de uma versão relaxada do PLRP, seguido de uma heurística route-first cluster-second. Para ganho de desempenho computacional, o método de solução aproveita os recursos de computação paralela presentes nas unidades de processamento (CPUs) atuais. Os resultados obtidos, após a realização dos testes computacionais sobre as instâncias do PLRP disponíveis na literatura, comprovam a eficiência do método implementado.
Título em inglês
A simulated annealing metaheuristic for the periodic location-routing problem with fixed customer-depot assignment.
Palavras-chave em inglês
Combinatorial optimization
Facility location
Heuristic methods
Operational research
Vehicle routing
Resumo em inglês
Facility location and vehicle routing are two of the main logistics processes in the supply chain management field. In many contexts, when these processes are combined in the decision-making process, larger economic benefits are perceived than when decisions are sequentially made. In the literature, this class of problems is known as the location-routing problem (LRP). In this dissertation is proposed a simulated annealing (SA) metaheuristic to solve the variant of the LRP that considers a planning horizon divided into multiple periods. This variant is known as the periodic location-routing problem (PLRP), being its main feature, the schedule of periodic visits to serve the customers' demand, following a service pattern defined in function of the customers' service frequency. In a context of periodic distribution with multiple depots, it is often necessary to have customers assigned to fixed depots, from which the demand is satisfied at each time period. In contrast, in other contributions found in the literature, customers may be served from different depots on each time period. Thus, in this dissertation it was imposed a fixed customer-depot assignment, which was treated as a constraint in the mathematical formulation of the PLRP and also in the proposed solution method. A characteristic of the SA metaheuristic is the use of an initial solution as input of the search algorithm. In this research, initial solutions are generated by solving a mixed integer programming (MIP) model of a relaxed version of the PLRP, followed by applying a route-first cluster-second heuristic. For improving the computational performance, the proposed solution method makes use of the parallel computing resources available in current CPU architectures. The results obtained, after running the proposed methods over PLRP instances available in the literature, confirm the efficiency of the method.
 
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
2021-07-01
 
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-2021. Todos os direitos reservados.