IMPACTO DA LISTA TABU NA DIVERSIDADE POPULACIONAL NA APLICAÇÃO DO ALGORITMO GENÉTICO AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO

Aluno de Iniciação Científica: Michel Ehrlich (PIBIC/UFPR-TN)
Curso: Engenharia de Produção
Orientador: Neida Maria Patias Volpi
Departamento: Engenharia de Produção
Setor: Tecnologia
Palavras-chave: Roteamento de veículos com janelas de tempo , Algoritmo Genético , Lista-tabu
Área de Conhecimento: 30802008 - PESQUISA OPERACIONAL

O presente estudo teve como objetivo a análise do impacto de uma lista-tabu, característica da meta-heurística Busca Tabu, na utilização da meta-heurística Algoritmo Genético quando da resolução do problema de roteamento de veículos com janelas de tempo. O problema consiste em definir um roteiro para entregas ou coletas de produtos à clientes com localizações definidas através de caminhões partindo de um ponto determinado, percorrendo a menor distancia possível. Cada caminhão possui uma capacidade definida e cada cliente uma demanda específica e uma janela de tempo na qual deve ser atendido. Como trata-se de um problema da classe NP-hard, a resolução exata através de um modelo de programação inteira binária é aplicável somente para problemas de pequenas dimensões. Para um maior número de clientes, utilizam-se heurísticas ou meta-heurísticas. Algoritmos genéticos são métodos de otimização propostos por John Holland na década de 70 baseados nos princípios darwinistas de seleção e evolução natural. Cada cromossomo representa uma possível solução e são avaliados por uma função de adaptação. Os indivíduos mais aptos têm maior probabilidade de se reproduzir através de cruzamentos com outros indivíduos da população, gerando descendentes com características de ambas as partes. Também é possível modificar os indivíduos através de mutações. Um problema recorrente na utilização dos algoritmos genéticos é a convergência prematura para ótimos locais, caracterizada quando os indivíduos da população são iguais ou muito semelhantes entre si e a operação de cruzamento não gera mais indivíduos diferentes. Este trabalho apresentou como alternativa a esse problema a utilização de lista-tabu. Esta lista, contendo os indivíduos de gerações imediatamente anteriores, não permite a ocorrência de soluções iguais dentro da população, preservando sua diversidade. O algoritmo foi testado em dados reais de uma empresa que realiza entregas de refeições no município de Colombo. Deseja-se minimizar a distância total a ser percorrida, visando reduzir os custos operacionais, e ao mesmo tempo atender as especificações de prazos dos clientes, o que melhora a qualidade do serviço ofertado e sua rentabilidade. Foram realizados experimentos com o problema reduzido a 9 clientes (com os quais é possível comparar com a solução exata), a 14 clientes e com o problema completo de 53 clientes. Em todos os casos, os experimentos com a lista-tabu apresentaram resultados médios melhores do que sem a utilização da mesma, com um incremento pequeno no tempo computacional.

 

0545