Use este identificador para citar ou linkar para este item: http://www.repositorio.ufop.br/jspui/handle/123456789/13882
Título: Iterated local search aplicado ao problema de roteamento de veículos com coleta e entrega simultânea, janela de tempo e frota heterogênea.
Autor(es): Oliveira, Joao Paulo Franca
Orientador(es): Gomes, Helton Cristiano
Gomes Júnior, Aloísio de Castro
Palavras-chave: Engenharia de produção - logística
Programação linear
Veículos - roteadores - redes de computadores
Pesquisa operacional - meta-heurísticas
Iterated local search - ILS
Data do documento: 2021
Membros da banca: Gomes, Helton Cristiano
Gomes Júnior, Aloísio de Castro
Francisco Neto, Antônio
Reis, Allexandre Fortes da Silva
Referência: OLIVEIRA, Joao Paulo Franca. Iterated local search aplicado ao problema de roteamento de veículos com coleta e entrega simultânea, janela de tempo e frota heterogênea. 2021. Dissertação (Mestrado em Engenharia de Produção) – Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2021.
Resumo: O problema de roteamento de veículos com coleta e entrega simultânea, janela de tempo e frota heterogênea (PRVCESJTFH) possui grande relevância no contexto logístico, uma vez que engloba particularidades inerentes a atividades de logística reversa. Em um PRVCESJTFH, deve-se determinar o conjunto de rotas com o menor custo possível, respeitando a janela de tempo estabelecida pelos clientes enquanto coleta e entrega mercadorias sem ultrapassar a capacidade dos veículos. Visto que o problema de roteamento de veículos é considerado NP-difícil na sua forma mais simples, o PRVCESJTFH também pode ser considerado pois apresenta mais restrições que tornam sua resolução ainda mais difícil. Para solucioná-lo, utilizou-se a meta-heurística Iterated Local Search (ILS). Para validar o método, foram realizados experimentos computacionais utilizando instâncias encontradas na literatura e adaptadas ao problema estudado, e, os resultados foram comparados com os obtidos por um modelo matemático de programação linear inteira. Por fim, foram realizado um teste estatístico com o intuito de verificar a existência de diferença significativa entre as soluções encontradas pelo ILS e o modelo matemático. Comprovou-se que o ILS apresentou um desempenho eficaz na resolução do PRVCESJTFH. Em seguida, o ILS foi aplicado a uma instância real obtida por uma empresa de distribuição de bebidas na região do Vale do Aço. O resultado obtido através da aplicação do ILS foi capaz de melhorar a solução anteriormente utilizada pela empresa.
Resumo em outra língua: The problem of vehicle routing with simultaneous pickup and delivery, time window and heterogeneous fleet (PRVCESJTFH) has great relevance in the logistical context, since it encompasses peculiarities inherent to reverse logistics activities. In a PRVCESJTFH, the set of routes with the lowest possible cost must be determined, respecting the time window established by the customers while collecting and delivering goods without exceeding the capacity of the vehicles. Since the vehicle routing problem is considered NP-hard in its simplest form, the PRVCESJTFH can also be considered because it has more restrictions that make its resolution even more difficult. To solve it, the Iterated Local Search (ILS) meta-heuristic was used. To validate the method, computational experiments were performed using instances found in the literature and adapted to the studied problem, and the results were compared with those obtained by a mathematical model of integer linear programming. Finally, a statistical test was performed in order to verify the existence of a significant difference between the solutions found by the ILS and the mathematical model. It was proven that the ILS presented an effective performance in the resolution of the PRVCESJTFH. Then, ILS was applied to a real instance obtained by a beverage distribution company in the region of Vale do Aço. The result obtained through the application of ILS was able to improve the solution previously used by the company.
Descrição: Programa de Pós-Graduação em Engenharia de Produção. Departamento de Engenharia de Produção, Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto.
URI: http://www.repositorio.ufop.br/jspui/handle/123456789/13882
Licença: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 07/10/2021 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais.
Aparece nas coleções:PPGEP - Mestrado (Dissertações)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTAÇÃO_IteratedLocalSearch.pdf1,74 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons