• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.3.2021.tde-01072021-160528
Document
Auteur
Nom complet
Hadir Alexander Garcia Castro
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2021
Directeur
Jury
Mendes, André Bergsten (Président)
Barretto, Marcos Ribeiro Pereira
Leite, Laura Silvia Bahiense da Silva
Titre en portugais
Uma meta-heurística simulated annealing para o problema de localização-roteirização periódico com designação fixa de cliente-depósito.
Mots-clés en portugais
Heurística
Localização de instalações
Otimização combinatória
Pesquisa operacional
Roteirização
Veículos
Resumé en portugais
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.
Titre en anglais
A simulated annealing metaheuristic for the periodic location-routing problem with fixed customer-depot assignment.
Mots-clés en anglais
Combinatorial optimization
Facility location
Heuristic methods
Operational research
Vehicle routing
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-01
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.