Please use this identifier to cite or link to this item: http://www.monografias.ufop.br/handle/35400000/2081
Title: Estudo e definição de modelos de computação evolucionária para o problema de roteamento de veículos com múltiplos depósitos.
Authors: Marques, Wagner Linhares
metadata.dc.contributor.advisor: Oliveira, Fernando Bernardes de
Alexandre, Rafael Frederico
metadata.dc.contributor.referee: Fonseca, George Henrique Godim da
Lima, Marlon Paolo
Oliveira, Fernando Bernardes de
Alexandre, Rafael Frederico
Keywords: Roteamento de veículos
Computação evolucionária
Issue Date: 2019
Citation: MARQUES, Wagner Linhares. Estudo e definição de modelos de computação evolucionária para o problema de roteamento de veículos com múltiplos depósitos. 2019. 39 f. Monografia (Graduação em Engenharia de Computação) - Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, Ouro Preto, 2019.
Abstract: O Problema de Roteamento de Veículos com Múltiplos Depósitos (do inglês, Multiple Deposit Vehicle Routing Problem – MDVRP) é uma importante variante do clássico Problema de Roteamento de Veículos (PRV) (Vehicle Routing Problem – VRP). O MDVRP tem ampla aplicação prática e representa o contexto de diversas empresas. Como não existe até então um método capaz de obter a solução ótima do problema em tempo polinomial, este trabalho tem como objetivo o estudo do MDVRP a partir da construção de modelos de computação evolucionária. O problema é investigado no contexto monoobjetivo, considerando a redução do custo das rotas percorridas pelos veículos. Este trabalho apresenta uma meta-heurística híbrida baseada na Estratégia Evolutiva (Evolution Strategy – ES) com a incorporação de procedimentos de busca local. A estratégia aplicada é a (μ + lambda)-ES, a qual é responsável pela geração de descendentes a partir da mutação e a seleção dos indivíduos. A busca local é composta por nove estratégias, considerando os critérios de parada Best Improvement e First Improvement. A validação do algoritmo proposto foi realizada por meio de instâncias de teste disponíveis na literatura. Considerando o contexto experimental estabelecido, os resultados foram satisfatórios, sendo que alguns valores estão com um GAP de 10% em relação a literatura. Mesmo não atingindo o valor esperado em todas as instâncias, foi possível obter uma comparação com bons resultados e que podem ainda ser melhorados.
metadata.dc.description.abstracten: The Multiple-Deposit Vehicle Routing Problem (MDVRP) is an important variant of the classic Vehicle Routing Problem. The MDVRP has broad practical application and represents the context of several companies. Since there is no computational method to obtain the optimal solution of the problem in polynomial time, this work has as objective the study of MDVRP from the construction of models of evolutionary computation. The problem is investigated in the mono-objective context, considering the cost minimization of vehicle routings. This work proposes a hybrid meta-heuristic based on the Evolutionary Strategy (Evolution Strategy – ES) with the incorporation of local search procedures. The (μ + lambda)-ES is used, which is responsible for the generation of offspring from the mutation and the selection of individuals. The local search is composed of nine strategies, considering as stop criteria the Best and the First Improvement. Computational experiments were used to evaluate the proposed method. Considering the established experimental environment, our method obtains GAP up to 10% from the literature. Even though the expected values for all instances were not obtained, the results suggest that our method provides competitive results and can also be improved.
URI: http://www.monografias.ufop.br/handle/35400000/2081
Appears in Collections:Engenharia de Computação JMV

Files in This Item:
File Description SizeFormat 
MONOGRAFIA_EstudoDefiniçãoModelos.pdf2,11 MBAdobe PDFView/Open


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