Um Algoritmo Evolutivo Baseado em Chaves Aleatórias Viciadas Aplicado ao Problema de Roteamento de Veículos com Janelas de Tempo

Resumo

O Problema de Roteamento de Veículos (PRV), introduzido na literatura por [1], e´ um dos mais clássicos problemas da pesquisa operacional. A forma mais simples do PRV é o Problema de Roteamento de Veículos Capacitados (PRVC), onde uma frota de veículos, localizada inicialmente em um depósito, deve atender a um conjunto de consumidores com diferentes demandas de produtos a serem distribuídos por essa frota. Neste trabalho abordaremos o Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT), o qual e´ uma extensão do PRVC. Além da restrição de capacidade, são adicionadas restrições relacionadas ao horário em que cada consumidor exige ser atendido. Para cada consumidor i, e´ associado um intervalo de tempo ou janela de tempo [ai, bi] indicando o horário de início do atendimento, e um tempo de serviço si, determinando o período de tempo que o veículo deve aguardar a finalização  das tarefas. O algoritmo evolutivo proposto para resolver este problema, consiste em determinar um conjunto de rotas com o menor custo possível, respeitando um determinado conjunto de restrições. Neste trabalho propomos um método de solução para o PRVJT utilizando um algoritmo genético baseado em chaves aleatórias viciadas, denominado BRKGA (Biased Random-key Genetic Algorithm). Representamos a solução do problema por um vetor de n chaves aleatórias, sendo essas chaves números reais dentro do intervalo [0, 1). Um decodificador e´ usado para mapear o vetor de chaves aleatórias e transformá-lo numa solução do PRVJT, ou seja, em um vetor de números inteiros, em que subsequências desses números correspondem a rotas formadas pelas cidades da instância utilizada. Inicialmente e´ gerada uma população de p vetores de chaves aleatórias e em seguida são selecionadas as melhores soluções. O conjunto de tamanho pe contendo as melhores soluções é preservado para a próxima geração ou iteração do algoritmo. Um novo conjunto de tamanho p − pe é adicionado às melhores soluções, compondo a nova população da próxima geração. Este novo conjunto de soluções é gerado a partir de combinações entre pais e filhos conforme uma dada distribuição probabilística. De acordo com [2], um RKGA (Random Key Genetic Algorithm) evolui uma população, de p vetores de chaves aleatórias aplicando o princípio de Darwin, ou seja, ha´ uma maior probabilidade de que os indivíduos mais aptos sobrevivam. Uma população inicial de p vetores de n chaves aleatórias e´ gerada de forma randômica. Na k−e´sima geração, a população e´ particionada em dois conjuntos: pe < p/2 e pne = p − pe, conjunto elite e na˜o-elite, respectivamente. O conjunto pe e´ constituído dos vetores que formam as melhores soluções, e consequentemente o conjunto pne e´ formado pelo restante da população. Para a k + 1−e´sima geração, a nova população e´ formada pelos conjuntos pe, pm e pr . O conjunto pm e´ composto por vetores de chaves aleatórias, e, e´ denominado de mutante, pois desempenha o mesmo papel dos operadores de mutação nos algoritmos genéticos clássicos, ou seja, evita que a população estacione em um ótimo local. O conjunto pr = p − pe − pm complementa a população. Os vetores deste último conjunto são gerados combinando pares de soluções da população da k−e´sima geração, ambos escolhidos aleatoriamente, com a combinação uniforme seguindo os parâmetros de [4]. [...]