Algoritmos de Otimização Para Problemas de Roteamento · 2018. 11. 26. · Os conceitos básicos...

Algoritmos de Otimização Para Problemas de Roteamento

Aluno: Rogério Takashi Hirata

Orientador: Luis Augusto Angelotti Meira

Faculdade e Tecnologia – Universidade Estadual de Campinas

R. Paschoal Marmo, 1888 - CEP:13484-332 -

Resumo

O objetivo deste projeto é desenvolver algoritmos de otimização para problemas de roteamento. Quando um veículo recebe um conjunto de pontos de entrega, ele deve utilizar uma rota otimizada, minimizando a distância percorrida ou o tempo total. Trata-se do clássico problema do Caixeiro Viajante (TSP). O objetivo deste projeto é analisar e projetar algoritmos de roteamento de veículos. Durante o projeto, o aluno estudou e implementou diversos algoritmos para o TSP, como o nearest neighbour algorithm, 2-opt e algoritmo genético. Esta iniciação será dedicada à otimização das rotas através de algoritmos bio-inspirados. Ao nal, espera-se que aluno tenha formado sólidos conhecimentos nas áreas de programação matemática, otimização e algoritmos.

1 Introdução

Dentre diversos problemas explorados pela otimização combinatória, um dos problemas mais conhecido é o Problema do Caixeiro Viajante (TSP) [1][2]. A origem exata do Problema do Caixeiro Viajante é desconhecida. A forma geral do TSP parece ter sido estudada, pela primeira vez, por volta de 1930 ou 1940 por matemáticos de Harvard e Viena. Posteriormente, o problema foi estudado por Hassler Whitney e Merril Flood em Princeton. A primeira referência contendo o termo TSP foi reportado por Julia Robinson,“On the Hamiltonian Game (a traveling salesman problem)” em 1949. O nome do problema ficou globalmente conhecido por volta de 1950 [1]. A otimização desse problema é capaz de prover soluções para operações de logística e reduções de custos às empresas. Passados 40 anos após a exposição do TSP, diversos métodos heurísticos foram propostos para solucionar o problema [5]. Métodos heurísticos bio-inspirados buscam explorar técnicas computacionais baseado nos princípios da natureza e podem ser utilizados para solucionar o TSP [4].

Em 1991, Gerhard Reinelt criou uma biblioteca de instâncias para o TSP chamado TSPLib, onde reuniu mais de 100 instâncias de diversos tipos de problemas e tamanho, relacionados ao TSP [13]. Essa coleção tem sido de uma grande ajuda à pesquisas relacionados ao TSP, já que provém um banco de testes comum para abordagem de soluções novas e antigas [1]. Todas as instâncias foram resolvidas em 2007, após 16 anos de grandes progressos em desenvolvimento de algoritmos [3].

Neste relatório de IC, vamos apresentar algumas técnicas de otimização utilizando métodos heurísticos bio-inspirados,como o algoritmo genético para solucionar instâncias de TSP coletados do TSPLib e realizar um estudo sobre a eficiência desses algoritmos.

Revisão Bibliográfica

Os conceitos básicos relacionados ao TSP foram abordados com grande ênfase por G Reinelt (1994) [9], onde são abordados temas fundamentais como a teoria dos grafos, a relação entre TSP e grafos, as aplicações práticas do TSP e métodos heurísticos que posteriormente são utilizados como base da metodologia e dos algoritmos implementados nessa pesquisa. Reinelt também realiza uma abordagem breve sobre o algoritmo genético e estratégias evolucionárias, mostrando as etapas que devem estar contidas na implementação nesse tipo de solução.

A contextualização inicial sobre a utilização dos algoritmos genéticos para a resolução do TSP, foi baseado no livro de Michalewicz (1996) [12], no qual são apresentados os conceitos essenciais sobre o que é, como funciona e o por que do algoritmo genético funcionar. Além disso, foi apresentado diversos conceitos fundamentais sobre a estrutura e estratégias que são utilizados para implementar esse tipo de solução.

Para complementar essa contextualização inicial, foi consultado a pesquisa de Larranaga (1999) [7], onde é realizado uma pesquisa mais extensiva sobre a representação do TSP e dos operadores que podem ser utilizados para a implementação do algoritmo genético. A partir dessa pesquisa, foi determinado o tipo de operador que seria implementado posteriormente pela nossa pesquisa.

Objetivos

O objetivo inicial do projeto é compreender os conceitos gerais do TSP. Em seguida, determinar possíveis algoritmos de otimização que podem ser implementados inicialmente no projeto e que ao mesmo tempo possam ser utilizados para a implementação do algoritmo genético. O objetivo principal do projeto consiste na implementação do algoritmo genético para otimizar as instâncias retirados do TSPlib. E por fim, realizar uma análise dos resultados obtidos pelo projeto e concluir o projeto.

Definição do Problema

O problema do caixeiro viajante é definido sobre um grafo não-dirigido G(V,E,𝓌), onde V = {v1,...,vn} é um conjunto de vértices e E = { ( i, j ) : i, j ∈ V , i < j } um conjunto de arestas. A função do peso é definido por 𝓌 : E → N. O problema consiste em designar uma rota R onde o custo da rota R = (r1 , … , rn ) é dado por

w(r1,rn)+ w(r

i ,ri+1)∑n − 1

i = 1

sendo r

1o ponto inicial da rota e sendo w, uma função de distância entre vértices. O

objetivo do problema é encontrar uma rota que tenha o menor custo possível, utilizando somente um veículo, começando por um vértice inicial r

1e retornado ao

vértice r1 , considerando que cada vértice é visitado somente uma única vez [11].

2 Metodologia

No estágio inicial do projeto foi utilizado o algoritmo de busca randômica. O algoritmo de busca randômica pertence ao campo da Otimização Estocástica e seus métodos de otimização também são caracterizados como uma busca direta. A estratégia da busca randômica consiste em gerar uma rota aleatória partindo de um ponto inicial aleatório e a cada iteração, sortear um vértice que ainda não foi visitado, para ser o próximo vértice a ser visitado. Dessa forma, o algoritmo gera uma rota válida ao TSP e totalmente aleatória a cada vez que o algoritmo é executado.

Após o estágio inicial, foi desenvolvido o algoritmo 2-opt. O 2-opt é um algoritmo de busca local que tem como principal estratégia, a permutação de arestas para formar rotas mais otimizadas. Esse algoritmo compara todas as possibilidades de permutação possíveis através de uma iteração e quando percebe que existem 2 arestas que podem ser otimizadas, elas são eliminadas e reconectadas para formar uma nova rota [9].

Figura 1. Exemplo de uma permutação do algoritmo 2-opt.

Inicialmente o método recebe uma rota como entrada e ao final da iteração,o algoritmo retorna essa mesma rota otimizada. Abaixo, temos um exemplo de um pseudocódigo do algoritmo:

Repete enquanto há melhora {

inicio:

melhor_distancia= calcular_distancia_total(rota_atual)

for (i = 1; i < numero_total_de_vertices - 1; i++) {

for (k = i + 1; k < numero_total_de_vertices; k++) {

nova_rota = permutacao2opt(rota_atual, i, k)

nova_distancia= calcular_distancia_total(rota_atual)

if (nova_distancia < melhor_distancia) {

rota_atual = nova_rota

goto inicio.

}

}

}

}

Um outro algoritmo implementado, foi o algoritmo do vizinho mais próximo. O

algoritmo do vizinho mais próximo (Nearest Neighborhood Algorithm) tem como principal estratégia, estar sempre buscando um vértice próximo do final da rota. A otimização inicia-se em um vértice e a partir desse vértice, é adicionado sempre ao final da rota, uma aresta formada entre o vértice e o vértice mais próximo do final da rota. Esse processo é iterado até que o final da rota retorne ao ponto inicial [9].

Uma outra família de algoritmos são os bio-inspirados. O algoritmo bio-inspirado escolhido para ser implementado foi o algoritmo genético. O algoritmo genético é uma ramificação de um grupo muito maior, conhecido como Computação Evolutiva. Dentro da Computação Evolutiva, temos os algoritmos evolutivos, que inspiram-se em mecanismos propostos na Teoria Evolutiva por meio da Seleção Natural, proposto por Charles Darwin (1859), e também em conceitos da genética.

No algoritmo genético, temos um conjunto ou uma população de possíveis soluções para um determinado problema. Essas soluções passam por uma processo de recombinação e mutação, produzindo novas soluções, e o processo é repetido por várias gerações até encontrar um critério de parada.

A seguir, serão apresentadas algumas terminologias relacionados ao estudo do algoritmo genético,como cromossomo,genes e alelos.

O cromossomo é uma cadeia de bits que representam uma possível solução de um problema. Uma implementação de um algoritmo genético começa com uma população de cromossomos. A estrutura desses cromossomos é formada por genes, que no caso, representam um elemento de uma posição do cromossomo. A

posição do gene em um cromossomo é denominada de locus. E por fim, os possíveis valores que um gene pode assumir é denominado de alelo [6] .

Figura 2 - Exemplo de estrutura de dados e terminologia de um AG.

Cromossomos com 10 genes e alelos binários. Fonte: Coello et al. (2002) [6]

2.1 Componentes do Algoritmo Genético

A estrutura de um algoritmo genético deve consistir de seguintes

componentes [12]:

Inicialização da População: população é o conjunto de possíveis soluções candidatas e também pode ser definido como um conjunto de cromossomos. A população deve ter como características principais a diversidade de soluções, para se evitar a convergência prematura durante a busca pela solução final, e um número de candidatos otimizados para o problema com o objetivo de não tornar a execução do algoritmo demasiadamente devagar. Avaliação da População: a avaliação da população é realizado pela função fitness. A função fitness é uma função que calcula o quão boa é uma solução candidata para solucionar um determinado problema. Para isso, a função retorna um valor numérico como uma forma de avaliação para a solução candidata. Em problemas de otimização, a função fitness pode também ser o custo da solução. Se o objetivo for minimização, as soluções de maior fitness são as que possuem menor custo.

Seleção de Reprodutores: a seleção de reprodutores é o processo de selecionar cromossomos para serem combinados com o objetivo de gerar novos cromossomos para a próxima geração. A seleção de reprodutores é fortemente influenciado pelos resultados das funções fitness para se determinar as combinações mais suscetíveis a produzirem melhores cromossomos. Nesse projeto, foi implementado o Fitness Proportionate Selection, também conhecido como Proportional Roulette Wheel Selection. Em Proportional Roulette Wheel, os indivíduos são selecionados com a probabilidade diretamente proporcional ao valor do seu fitness e cada valor fitness corresponde a parte do Roulette Wheel. Com isso, quanto maior o valor fitness do cromossomo, maior será a sua probabilidade de ser selecionado para o processo de Cruzamento de Selecionados [10]. Se f

i é o valor fitness do indivíduo i na

população a probabilidade de ser selecionado é:

, onde n é o número de indivíduos na população.

Cruzamento de Selecionados (Crossover): o cruzamento de selecionados é o processo responsável em fazer a combinação dos reprodutores selecionados pela Seleção de Reprodutores com o objetivo de gerar novos cromossomos para as próximas gerações. Para tal, existem diversos operadores para se realizar essa recombinação [7]. O operador escolhido para ser utilizado nesse projeto foi o Order- Crossover (OX1). Esse método foi proposto por Davis (1985) e tem como propósito, encontrar uma lista ordenada de cidades para representar o caminho da solução [8]. Ele constrói um offspring escolhendo um subtour de um cromossomo e preservando a ordem relativa das cidades de um outro cromossomo. Vamos tomar como exemplo os seguintes cromossomos:

Cromossomo 1: (1 2 3 4 5 6 7 8) Cromossomo 2: (2 4 6 8 7 5 3 1)

Inicialmente, escolhemos 2 pontos de corte para ambos os cromossomos. Nesse exemplo, vamos selecionar o primeiro ponto entre o 2º e 3º bit e o segundo corte entre 5º e 6º bit:

Cromossomo 1: (1 2 | 3 4 5 | 6 7 8) Cromossomo 2: (2 4 | 6 8 7 | 5 3 1)

Após selecionar os pontos de corte, os segmentos entre os pontos de cortes são copiados para os offsprings resultantes:

Offspring 1: (* * | 3 4 5 | * * *) Offspring 2: (* * | 6 8 7 | * * *)

Para gerar os offsprings resultantes, seguimos os seguintes passos:

- Para gerar o Offspring 1, preenchemos os valores faltantes do Offspring 1 percorrendo o Cromossomo 2 para selecionar os valores em ordem, omitindo os valores que já estão no segmento do Offspring 1.

- Para gerar o Offspring 2, preenchemos os valores faltantes do Offspring 2 percorrendo o Cromossomo 1 para selecionar os valores em ordem, omitindo os valores que já estão no segmento do Offspring 2.

Com isso, geramos os seguintes offsprings:

Offspring 1: (2 6 | 3 4 5 | 8 7 1) Offspring 2: (1 2 | 6 8 7 | 3 4 5)

Mutação dos Resultantes: a mutação é um processo que realiza alterações em um cromossomo para gerar um novo cromossomo, com a finalidade de manter e introduzir mais diversidade para a população. Geralmente ocorrem com uma baixa probabilidade, e utilizam-se de diversos operadores para realizar essa mudança como inversão de bits, troca de valores, inversão de sequências de valores, entre outros. A operação utilizado neste projeto foi o operador de troca de valores. O operador de troca de valores (Banzhaf 1990) , consiste em selecionar 2 pontos de uma determinado cromossomo, com o objetivo de trocar os valores de seus respectivos pontos para gerar um cromossomo modificado [7] . Como exemplo, considere o seguinte cromossomo:

( 1 2 3 4 5 6 7 8 ),

e suponhamos que o 3 e 5 são selecionados. Com isso, temos o seguinte resultado:

( 1 2 5 4 3 6 7 8 ) Avaliação dos Resultantes: a avaliação dos resultantes é responsável em avaliar o valor fitness dos novos cromossomos gerados pelo processo de cruzamento e mutação apresentados anteriormente.

Atualização da População: com os novos cromossomos já avaliados, existe um processo responsável em atualizar a população. Para isso, são inseridos na população os novos cromossomos gerados pelos processos anteriores e são removidos da população, os cromossomos que apresentam um fitness com valores baixo. Posteriormente, o fluxo de execução retorna para a Avaliação da População e o processo é repetido até que a condição de terminação seja atingida

A condição de parada de um algoritmo genético é crucial para determinar a

otimização e tempo de execução do algoritmo genético. O algoritmo converge para a solução ótima de forma rápida mas tende a saturar nos estágios finais da iteração, quando as melhorias são mínimas. Geralmente, essas condições são utilizadas:

1. Quando chegamos em x geração; 2. Quando não há melhora na população em x gerações; 3. Quando a função fitness chega a um valor pré-determinado x ;

A condição de parada utilizado nesse projeto foi a primeira, sendo x = 100.

Portanto, sempre quando o nosso algoritmo atinge-se a 100ª geração, o algoritmo interrompe a otimização e encerra a execução. 3 Implementações

No início do projeto foram desenvolvidos classes para a realização de leitura de instâncias que seriam utilizados pelo projeto. As instâncias utilizadas foram coletados do TSPLib e armazenados no formato .txt. Portanto, para a realização da leitura desses arquivos foram desenvolvida a classe TSPReader.java que era rensponsável em interpretar esses arquivos e devolver as coordenadas das localizações para que fossem utilizadas na otimização.

Além disso, foi desenvolvido a primeira versão do Graph.java onde seriam aclutinados as localizações coletadas no arquivo anterior e as arestas entre essas localizações. Adicionalmente, foi desenvolvido uma classe chamada DrawPNG que era responsável em gerar uma imagem no formato PNG que representasse a solução final da otimização gerada pelo projeto.

Após a primeira revisão do projeto, foram realizadas diversas refatorações no código e foi desenvolvido a classe Optimize.java que era responsável em gerar as primeiras rotas do projeto. O primeiro algoritmo implementado gerava uma rota randômica. Logo após, implementamos um algoritmo de busca local chamado 2-opt com a finalidade de otimizar essa rota randômica.

Juntamente, foi implementado o nearest neighbour algorithm e a utilização deste algoritmo com o 2-opt, gerava boas soluções para a resolução das instâncias.

Porém, essas soluções ainda poderiam ser melhoradas através da utilização do algoritmo genético.

Figura 2. Organização das classes implementadas.

Para a implementação do algoritmo genético, foi realizado um estudo mais

aprofundado sobre o assunto. Os principais fundamentos estudados durante esse período foram terminologias básicas utilizados durante o desenvolvimento do algoritmo genético, a estrutura básica de um algoritmo genético, a representação genótipo do problema e os algoritmos relacionados a implementação do algoritmo genético.

Inicialmente, foi criado uma classe chamada OptimizeGA e em sua primeira versão, implementamos métodos responsáveis em criar a população inicial de possíveis soluções para o problema. Com o algoritmo de geração de rotas dinâmicas, foram criadas 30 rotas que posteriormente eram convertidos em cromossomos, representados pela classe Chromosome e também foi criada uma classe Population, onde um array de cromossomos são armazenados e manipulados no decorrer da otimização.

Figura 3. Organização das classes do algoritmo genético.

Na classe Population foram implementadas boa parte das operações utilizadas nos algoritmos genéticos. A primeira a ser implementada foi uma função para calcular o fitness do problema. Para isso, foi tomado como parâmetro principal, a distância total das rotas e a maior distância gerada inicialmente dentre as rotas, utilizando-a como um pivô. A função fitness subtrai o valor da distância da rota do valor pivô e obtém um valor numérico positivo que posteriormente é utilizado como o valor do fitness do cromossomo.

Posteriormente foi desenvolvido o método roulletSelection responsável em selecionar um cromossomo dentre os cromossomos disponíveis na população,baseando-se no conceito de Roulette Wheel Selection. Através desse método, o método parentSelection seleciona 2 cromossomos (pais) que serão utilizados para se obter novas combinações de rotas, chamadas de offspring no projeto.

Com os cromossomos pais em mãos, o próximo passo foi desenvolver os métodos responsáveis em realizar o Crossover, a geração de Offsprings, Mutação e a Seleção de Sobreviventes.

Para implementar o método de Crossover, foi necessário realizar um estudo sobre quais os tipos de Crossover que poderiam ser aplicados para o projeto e em paralelo, descobrir qual deles seria o mais adequado para o problema. Ao final do estudo, foi decidido implementar a operação de Crossover usando o Davis Order Crossover (OX1). O método recebe como parâmetro 2 cromossomos (pais) e gera 2 cromossomos (filhos) denominados de Offsprings que posteriormente são retornados pelo método.

Após a geração de Offsprings, foi desenvolvido uma função responsável em realizar a mutação dos cromossomos existentes, com o objetivo de diversificar a população e criar novas soluções. A função de mutação usa uma operação de swap para trocar os alelos de posição e gerar um cromossomo modificado.

Em sequência, são calculados os valores fitness dos offsprings gerados pela função de crossover. Uma função simples que toma como entrada, os cromossomos gerados anteriormente e que chama a função de calcular fitness utilizado anteriormente para calcular os valores fitness da população.

Com o valor fitness já calculado, esses novos cromossomos são inseridos na população e ordenados dentro da população baseando se no fitness. Com isso, temos uma população com resultados ordenados de melhores resultados a piores resultados. Sabendo disso, os cromossomos com os piores resultados são retirados da população e novos cromossomos repõem a população para que se mantenha uma quantidade fixa de cromossomos.

Esse processo é iterado até que a condição de terminação seja completada,que no caso, é limitado a iterar até a 100ª geração. Quando o algoritmo atinge a 100ª geração,o mesmo interrompe a otimização e encerra a execução

4 Resultados Os resultados obtidos pela otimização do TSP foram produzidos apenas com

a utilização de 1 veículo. A coleta de dados para o cálculo do melhor resultado, média, desvio padrão e média de tempo de execução foram extraídos da execução dos algoritmos de otimização. Cada algoritmo foi limitado para ser executado somente 5 vezes cada.

Inicialmente foram aplicados os algoritmos randômico, Nearest Neighbour e 2-OPT sobre a instância Berlin52. Esta instância possui um total de vértices igual a 52. Os resultados estão na Tabela 1. Podemos notar que, os algoritmos Nearest Neighbour e 2-OPT conseguem otimizar significativamente em relação ao resultado do algoritmo randômico.

Aproveitando a implementação dos algoritmos Nearest Neighbour e 2-OPT, aplicamos a combinação de execuções desses dois algoritmos sobre a instância Berlin52 para tentarmos otimizar ainda mais a rota. O resultado está na tabela 1 e podemos notar que o resultado apresentou uma média melhor em relação ao algoritmo Nearest Neighbour e 2-OPT mas ainda não chegando muito próximo do resultado ótimo.

Por fim, aplicamos o algoritmo genético sobre a instância Berlin52. O resultado apresentando novamente na Tabela 1, podemos notar que o algoritmo genético apresentou o melhor resultado em relação aos algoritmos anteriores, obtendo o valor ótimo para a solução. Vale notar que, pelo fato do algoritmo possuir uma maior complexidade, o tempo médio de execução acaba sendo maior como também podemos notar na Tabela 1.

Algoritmo Melhor Resultado Média, DVP Tempo (média)

Randômico 26823 28814±1560 845 ms

Nearest Neighbour 8980 8980±0 558 ms

2-OPT 9538 10092±437 565 ms

Nearest Neighbour + 2-OPT 8401 8401±0 478 ms

Genético 7542 7725±166 927 ms

Ótimo 7542 - -

Tabela 1. Comparação de resultados da instância Berlin52

No gráfico a seguir, podemos notar que os algoritmos de otimização, quando

aplicados em uma instância pequena, chegam bem próximos ao resultado ótimo.

Figura 5. Custo do melhor resultado x Algoritmo. Instância Berlin52

Em seguida, aplicamos a mesma sequência de algoritmos aplicados na

instância anterior para a instância ch150, que possui um total de vértices igual a 150. Podemos notar que os resultados dessa instância apresentaram um comportamento similar ao que foi aplicado na instância Berlin52. O algoritmo genético continua apresentando um resultado melhor em relação aos outros algoritmos apresentados e é o resultado que ainda mais se aproxima do resultado considerado ótimo.

Algoritmo Melhor Resultado Média, DVP Tempo (média)

Randômico 52089 53909±1266 617 ms

Nearest Neighbour 8191 8191±0 378 ms

2-OPT 9814 10409±546 371 ms

Nearest Neighbour + 2-OPT 7307 7307±0 308 ms

Genético 6753 6832±64 9609 ms

Ótimo 6528 - -

Tabela 2. Comparação de resultados da instância ch150

Figura 6. Custo do melhor resultado x Algoritmo. Instância Ch150

Em seguida, aplicamos a mesma sequência de algoritmos para a instância lin318 que possui um total de vértices equivalente a 318. Podemos notar que os resultados apresentados na tabela 3 possuem um comportamento similar aos apresentados nas instâncias berlin52 e ch150. Um ponto importante a se notar é o grande aumento no tempo médio necessário para a execução do algoritmo genético. Isso se deve ao aumento no número de vértices e também está relacionado com a complexidade do algoritmo genético em relação aos outros algoritmos.

Algoritmo Melhor Resultado Média, DVP Tempo (média)

Randômico 584733 593675±8141 6585 ms

Nearest Neighbour 54019 54019±0 1869 ms

2-OPT 69074 70273±1029 2985 ms

Nearest Neighbour + 2-OPT 49666 49666±0 2363 ms

Genético 43627 43948±290 89733 ms

Ótimo 42029 - -

Tabela 3. Comparação de resultados da instância lin318

Figura 7. Custo do melhor resultado x Algoritmo. Instância lin318

Por fim, aplicamos a nossa sequência de algoritmos na instância pr439 que possui um total de vértices igual a 439. Podemos notar na tabela 4 que os resultados são maiores em relação aos resultados anteriores. Os resultados dos algoritmos apresentaram um comportamento similar aos resultados obtidos anteriormente e notamos que o algoritmo genético foi o que algoritmo que mais se aproximou do resultado ótimo novamente. Podemos notar também que o tempo médio de execução do algoritmo genético cresceu significamente em relação ao tempo de execução das instâncias anteriores,o que torna a execução da otimização exaustivo.

Testamos também a combinação de execução do algoritmo Nearest Neighbour com 2-OPT para as outras instâncias e observamos que os resultados também apresentaram uma melhora em relação a execução dos algoritmos isolados, demonstrados pela tabela 2, 3 e 4.

Por fim, observamos que os desvios padrões encontrados para o algoritmo genético foram consideravelmente menores que o desvios padrões dos algoritmos 2-OPT e randômico para as todas as instâncias testadas. A redução do desvio padrão do 2-OPT para o algoritmo genético variaram entre 62% a 88,2%.

Algoritmo Melhor Resultado Média, DVP Tempo (média)

Randômico 1866243 1906604±35079 35430 ms

Nearest Neighbour 131281 131281±0 10727 ms

2-OPT 173978 184196±7715 13562 ms

Nearest Neighbour + 2-OPT 123095 123095±0 11051 ms

Genético 111537 113628±1231 244203 ms

Ótimo 107217 - -

Tabela 4. Comparação de resultados da instância pr439

Figura 8. Custo do melhor resultado x Algoritmo. Instância pr439

5 Conclusões

No início deste Projeto de Pesquisa foi proposto o desenvolvimento de algoritmos para a resolução do TSP, com o objetivo de realizar uma análise comparativa entre a qualidade de resolução e o tempo de execução de cada abordagem. Os algoritmos selecionados para serem implementados foram Randômico, Nearest Neighbour,2-OPT e Genético.

Com os algoritmos implementados e testados, foi concluído que o algoritmo que mais se aproximou nos resultados considerados ótimos foi o algoritmo genético. Exemplificado na tabela da instância Berlin52 (Tabela 1), onde o melhor resultado encontrado pelo algoritmo genético foi de 7542, sendo o mesmo valor considerado como ótimo pela TSPLib.

Observamos também que o aumento do número de vértices impacta diretamente no tempo de execução do algoritmo ao compararmos o tempo de execução do algoritmo genético da instância berlin52 e pr439 com um tempo médio de 927ms e 244203ms respectivamente.

Testamos também a combinação de execução do algoritmo Nearest Neighbour com 2-OPT e observamos que os resultados apresentaram uma melhora em relação a execução dos algoritmos isolados.

Notamos também que o valor do desvio padrão encontrado para o algoritmo genético em cinco execuções foi consideravelmente menor que o desvio padrão dos algoritmos 2-OPT e randômico. A redução do desvio padrão do 2-OPT em relação ao algoritmo genético variaram entre 62% a 88,2%.

Bibliografia [1] David L Applegate.The traveling salesman problem: a computational study. Princeton University Press, 2006. [2] Jorge Tavares Francisco Baptista Pereira, editor. Bio-inspired Algorithms for the Vehicle Routing Problem, volume 161. Springer. [3] Luis A. A. Meira, Paulo S. Martins, Mauro Menzori, Guilherme A.Zeni. Multi-Objective Vehicle Routing Problem Applied to Large Scale Post Office Deliveries. arXiv:1801.00712, 2017. [4] Jorge Tavares Francisco Baptista Pereira, editor. Bio-inspired Algorithms for the Vehicle Routing Problem, volume 161. Springer. [5] Laporte,G., Gendreau,M., Potvin,J.Y., Semet, F.: Classical and Modern Heuristics for the Vehicle Routing Problem. International Transactions in Operational Research 7 (2000) [6] Coello Coello, C. A.; Van Veldhuizen, D. A.; Lamont, G. B. Evolutionary algorithms for solving multi-objective problems. Genetic Algorithms and Evolutionary Computation. New York, NY: Kluwer Academic, 2002

[7] Larranaga, Pedro & Kuijpers, Cindy & H. Murga, R & Inza, I & Dizdarevic, S. (1999). Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review. 13. 129-170. 10.1023/A:1006529012972. [8] Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence, 162–164. [9] Reinelt, Gerhard. The traveling salesman: computational solutions for TSP applications. Springer-Verlag, 1994. [10] Razali, Noraini Mohd, and John Geraghty. "Genetic algorithm performance with different selection strategies in solving TSP." Proceedings of the world congress on engineering. Vol. 2. Hong Kong: International Association of Engineers, 2011. [11] Jünger, Michael, Gerhard Reinelt, and Giovanni Rinaldi. "The traveling salesman problem." Handbooks in operations research and management science 7 (1995): 225-330. [12] MICHALEWICZ, Z. “Genetic algorithms + Data Structures = Evolution Programs”, 3rd edition, Springer-Verlag, 1996. [13] REINELT, G. TSPLIB-- A Traveling Salesman Problem Library. ORSA Journal on Computing, [s. l.], v. 3, n. 4, p. 376, 1991.