Jornal Internacional de Swarm Intelligence e Computação Evolutiva

Abstrato

Um algoritmo imunológico para a optimização combinatória: o problema da distribuição de combustível como caso de estudo

Pavone M*, Costanza J e Cutello V

Resumo Os problemas de encaminhamento são tarefas clássicas de otimização combinatória que encontram muita aplicabilidade em diversos cenários industriais e do mundo real. Uma variante desafiante do problema de roteirização é o Problema de Distribuição de Combustível (FDP) que uma empresa de transportes tem de enfrentar nas suas operações diárias. A principal actividade de uma empresa de combustíveis para transportes é reabastecer todas as suas lojas, ou seja, postos de gasolina, ao longo de um mapa geográfico, com o objectivo de minimizar os seus custos globais. Neste trabalho de investigação apresentamos uma heurística híbrida baseada na metáfora do sistema imunitário para a resolução do FDP, que basicamente pede para encontrar um conjunto de rotas o mais curto possível para um número fixo de veículos da empresa de forma a satisfazer as diversas exigências recebidas. de clientes. Em particular, o algoritmo imunológico apresentado inspira-se no princípio da seleção clonal, cujas principais características são a clonagem, a hipermutação e os operadores de envelhecimento. Tal algoritmo caracteriza-se ainda por possuir uma (i) abordagem determinística baseada no algoritmo Depth First Search (DFS) - utilizado no esquema de atribuição de um vértice a um veículo - e (ii) um operador de busca local, baseado na exploração do bairro . O algoritmo foi testado numa instância de dados reais, com 82 vértices, e outras 25 instâncias artificiais diferentes, retiradas do benchmark de coloração de grafos DIMACS. Os resultados experimentais apresentados neste trabalho, não só comprovam a robustez e eficiência do algoritmo desenvolvido, como também mostram a qualidade da pesquisa local e da abordagem baseada no algoritmo DFS. Ambas as metodologias ajudam o algoritmo a explorar melhor o complexo espaço de pesquisa.