PROPOSTA E AVALIAÇÃO DE UMA HEURÍSTICA PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO FLEXÍVEIS
Autor(es):
SOUZA, SAMUEL SILVA DE
Palavras Chaves:
Não informado
Ano de Publicação:
2018
Resumo:
Neste trabalho um método heurístico é proposto para o Problema de Roteamento de Veículos com Janelas de Tempo Flexíveis. Esse problema permite atraso no atendimento dos clientes incorrendo uma penalidade nos objetivos. A heurística descrita é baseada em duas fases: uma fase para geração de soluções iniciais seguida por uma busca local para melhoramento das soluções geradas. Testes são realizados nas instâncias de 100 clientes de Solomon para o Problema de Roteamento de Veículos com Janelas de Tempo Rígidas usando altos valores de penalidade e a qualidade das soluções encontradas é comparada com os melhores resultados encontrados até momento. Nos resultados encontrados pela abordagem proposta foram verificadas melhorias nas soluções para algumas instâncias. Para testar a performance dos algoritmos em uma aproximação mais realística um novo conjunto de instâncias é avaliado. Adicionalmente, um modelo de Programação Linear Inteira Mista que modela todas as restrições e a função objetivo do problema é apresentado. Palavras-chave: Roteamento de Veículos. Janelas de Tempo. Heurística. Busca Local
Abstract:
In this work a heuristic method is proposed for the vehicle routing problem with soft time windows. This problem allows a delay in customer service incurring a penalty in the objective. The heuristic described is based on two phases: a phase for generating initial solutions followed by a local search to improve the solutions generated. Tests are performed on the 100-customers Solomon instances for the vehicle routing problem with hard time windows assuming high penalty values and the quality of the solutions is compared to the best known results found so far. The results found by the proposed approach shows improvements in the solutions for some instances. To test the performance of the algorithms in a more realistic approach a new set of instances is evaluated. In addition, a Mixed Integer Linear Programming models that includes all constraints and the objective function of the problem is presented. Keywords: Vehicle Routing. Time Windows. Heuristic. Local Search
Tipo do Trabalho:
TCC
Referência:
SOUZA, SAMUEL SILVA DE. PROPOSTA E AVALIAÇÃO DE UMA HEURÍSTICA PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO FLEXÍVEIS. 2018. 42 f. Trabalho de Conclusão de Curso (Graduação em 2018) – Universidade Estadual do Ceará, , 2018. Disponível em: Acesso em: 25 de abril de 2024
Universidade Estadual do Ceará - UECE | Departamento de Tecnologia da Informação e Comunicação - DETIC
Política de Privacidade e Segurança Build 1
