Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/25532
Document type: Tese
Access type: Acesso Aberto
Title: Algoritmo memético paralelo baseado em ilhas com busca local Lin- Kernighan para solução do problema de roteamento de veículos heterogêneos em duas fases inspirado em um modelo de distribuição usado por atacadistas
Alternate title (s): Parallel island based memetic algorithm with Lin–Kernighan local search for a real-life two-echelon heterogeneous vehicle routing problem based on brazilian wholesale companies
Author: Bevilaqua, André
First Advisor: Yamanaka, Keiji
First member of the Committee: Peretta, Igor Santos
Second member of the Committee: Queiroz, Thiago Alves de
Third member of the Committee: Lima , Gerson Flávio Mendes de
Summary: Esta tese trata de um Problema de Roteamento de Veículos em Dois Níveis enfrentado por uma empresa brasileira do mercado atacadista. Problemas de roteamento de veículos com mais de um nível existem em contextos nos quais a carga é movimentada passando por estruturas intermediárias (por exemplo, centros de distribuição, satélites, etc) antes de chegar ao destino. O primeiro nível do problema tratado aqui envolve escolher um veículo de primeiro nível, de um conjunto heterogêneo, que sai de um depósito em direção a uma instalação de transbordo intermediária (chamada de satélite) para servir um conjunto de veículos de segundo nível. Depois disso é necessário criar um conjunto de rotas para todos os veículos, também heterogêneos, que sairão dos satélites para visitar os clientes. A solução proposta é um Algoritmo Memético Paralelo Baseado em Ilhas com Busca Local Lin-Kernighan. Para verificar a eficiência do algoritmo, primeiramente ele foi testado em um contexto de problema de roteamento de veículos heterogêneos de um nível a partir de um \textit{benchmark} conhecido. Posteriormente, as instâncias foram adaptadas e usadas para validar o contexto de dois níveis. Por fim, foram criadas novas instâncias com dados reais normalizados para verificar o algoritmo em um contexto mais realista. Em todos os casos o algoritmo foi comparado com os resultados da ferramenta comercial Localsolver usada na solução de problemas de otimização. Foram obtidos importantes resultados para o algoritmo e também análises reveladoras das características do problema tratado. Por fim, são apresentados trabalhos futuros que visam melhorar a exploração do problema proposto.
Abstract: This thesis deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem faced by brazilian wholesale companies. Vehicle routing problems with more than one phase consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin-Kernighan heuristic. In order to attest the algorithm’s efficiency, first it was tested in single echelon heterogeneous fleet vehicle routing benchmark instances. After that the instances were adapted for two-echelon context and used for validation alongside with real world instances created using normalized real data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.
Keywords: Problema de Roteamento de Veículos em Dois Níveis
Two-Echelon Vehicle Routing Problem
Frotas Heterogêneas
Heterogeneous Fleet
Algoritmo Memético Baseado em Ilhas
Island Based Memetic Algorithm
Lin-Kernighan
Mercado Atacadista
Wholesale Companies
Engenharia elétrica
Electrical Engineering
Veículos
Vehicles
Logística Empresarial
Business Logistics
Algoritmos
Algorithms
Modelagem de Processos
Process Modeling
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO
CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Engenharia Elétrica
Quote: BEVILAQUA, André. Algoritmo memético paralelo baseado em ilhas com busca local Lin- Kernighan para solução do problema de roteamento de veículos heterogêneos em duas fases inspirado em um modelo de distribuição usado por atacadistas. 2019. 106 f. Tese (Doutorado em Engenharia Elétrica) - Universidade Federal de Uberlândia, Uberlândia, 2019. Disponível em: http://dx.doi.org/10.14393/ufu.te.2019.5 .
Document identifier: http://dx.doi.org/10.14393/ufu.te.2019.5
URI: https://repositorio.ufu.br/handle/123456789/25532
Date of defense: 24-May-2019
Appears in Collections:TESE - Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
AlgoritmoMeméticoParalelo.pdfTese3.46 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.