• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.3.2021.tde-01072021-160528
Document
Author
Full name
Hadir Alexander Garcia Castro
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2021
Supervisor
Committee
Mendes, André Bergsten (President)
Barretto, Marcos Ribeiro Pereira
Leite, Laura Silvia Bahiense da Silva
Title in Portuguese
Uma meta-heurística simulated annealing para o problema de localização-roteirização periódico com designação fixa de cliente-depósito.
Keywords in Portuguese
Heurística
Localização de instalações
Otimização combinatória
Pesquisa operacional
Roteirização
Veículos
Abstract in Portuguese
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.
Title in English
A simulated annealing metaheuristic for the periodic location-routing problem with fixed customer-depot assignment.
Keywords in English
Combinatorial optimization
Facility location
Heuristic methods
Operational research
Vehicle routing
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2021-07-01
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.