Desenvolvimento e avaliação de um novo componente baseado em path relinking para o algoritmo Memplas no problema QCARS

Abstract

Este trabalho é um estudo sobre o problema Quota Car Traveling Salesman (QCaRS). Este problema consiste em minimizar o custo de uma viagem entre um grupo de cidades, visitando apenas um subgrupo, e garantindo a visita de cidades que cumpram com uma satisfação mínima para o viajante. Cada cidade possui uma quota, que indica a satisfação do viajante em visitá-la. O viajante precisa também minimizar o custo do percurso. Este trabalho propôs desenvolver e avaliar um componente baseado em Path Relinking para o algoritmo genético MemPlas proposto por Goldbarg et al. (2016). A hipótese considerada neste trabalho é de que a substituição do componente Plasmídeo pelo Path Relinking poderia trazer resultados melhores considerando qualidade de soluções. Dois experimentos foram realizados para avaliar esta hipótese. O primeiro experimento evidenciou que os resultados apresentados pelas três variações do algoritmo não apresentavam diferenças quando todas as instâncias foram analisadas juntas. Ao realizar uma análise por instância, notou-se que o algoritmo MemPlas mais o novo componente Path Relinking apresentou melhoras em algumas instâncias. No segundo experimento, ao remover o componente de busca local, o algoritmo MemPlas original apresentou os melhores resultados no geral e na análise instância por instância, rejeitando a hipótese.