Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departamento de Informática e Matemática Aplicada
Programa de Pós-Graduação em Sistemas e Computação
Doutorado Acadêmico em Sistemas e Computação
O Problema do Caixeiro Alugador com Coleta
de Prêmios: Um Estudo Algorítmico
Matheus da Silva Menezes
Natal-RN
Março de 2014
Matheus da Silva Menezes
O Problema do Caixeiro Alugador com Coleta de
Prêmios: Um Estudo Algorítmico
Tese de Doutorado apresentada ao Programa
de Pós-Graduação em Sistemas e Computação do Departamento de Informática e Matemática Aplicada da Universidade Federal do
Rio Grande do Norte como requisito parcial
para a obtenção do grau de Doutor em Sistemas e Computação.
Linha de pesquisa :
Algoritmos Experimentais
Orientador
Dr. Marco César Goldbarg
PPgSC Programa de Pós-Graduação em Sistemas e Computação
DIMAp Departamento de Informática e Matemática Aplicada
CCET Centro de Ciências Exatas e da Terra
UFRN Universidade Federal do Rio Grande do Norte
Natal-RN
Março de 2014
Catalogação da Publicação na Fonte. UFRN / SISBI / Biblioteca Setorial
Centro de Ciências Exatas e da Terra – CCET.
Menezes, Matheus da Silva.
O problema do caixeiro alugador com coleta de prêmios: um estudo
algorítmico / Matheus da Silva Menezes. - Natal, 2014.
126 f. : il.
Orientador: Prof. Dr. Marco César Goldbarg.
Tese (Doutorado) – Universidade Federal do Rio Grande do Norte. Centro de
Ciências Exatas e da Terra. Programa de Pós-Graduação em Sistemas e
Computação.
1. Algoritmo – Informática – Tese. 2. Metaheurística – Tese. 3 Caixeiro
alugador com coleta de prêmios – Tese. 4. Computação evolucionária – Tese. I.
Goldbarg, Marco César. II. Título.
RN/UF/BSE-CCET
CDU: 004
p
MATHEUS
o Problema
DA SILVA MENEZES
do Caixeiro Alugador com Coleta de Bônus:
Um estudo AIgorítmico
Esta Tese foi julgada adequada para a obtenção do título de doutor em Ciência
da Computação e aprovado em sua forma final pelo Programa de Pós-Graduação em
Sistemas e Computação do Departamento de Informática e Matemática Aplicada da
niversidade Federal do Rio G ande do Norte.
Banca Examinadora
I'
P of. Dr". Elizabeth Fer
j~
~
~8t"v~ ~
Prof. Dt". Iloneide Carlos de Oliveira Ramos - UFRN
Lf,.Âh6~
Prof. Dr. Henrique Pacca Loureiro Luna - UFAL
yri m Regattieri de Bias da Silva Delgado - UTFPR
Março, 2014
Agradecimentos
Este trabalho é o fruto de quase quatro anos de dedicação e muito trabalho, determinação, privações e ansiedades até que viessem as epifanias salvadoras. Então só quem
conviveu, sabe: não foi fácil. Mas a satisfação de chegar ao m é muito grande. Gostaria
de deixar os meus agradecimentos a todos que compartilharam isso comigo.
Gostaria de agradecer imensamente à minha lha Anna Júlia, por sempre estar ao
meu lado, me apoiar e entender o sentido de tudo. Seu carinho e seus sorrisos foram o
principal combustível de todo esse esforço.
Agradeço aos meus pais, por me apoiarem e por nunca medirem esforços na continuidade de meus estudos e de minha educação. A vontade de ler e aprender foi incentivada
desde cedo, criando bons hábitos, mesmo sendo um gesto discreto em trazer um gibi de
super herói e assim incentivar meu gosto pela leitura e pela ciência.
Agradeço a toda a minha família, por sempre estar perto, por sempre incentivar e
valorizar o conhecimento e a construção do caráter. Especialmente agradeço aos meus
avós, tios e primas que compartilham comigo as alegrias e frustrações desde que estou
nesse mundo. Nesse sentido, faço questão de destacar a minha irmã Aryadne Menezes,
que me apoiou em todos os momentos.
Agradeço aos meus poucos, porém insubstituíveis amigos, que permanecem ao meu
lado após tanto tempo, uns também fazendo doutorado, outros acompanhando a saga
de longe. O apoio de vocês foi muito importante. Agora já posso ir aos churrascos, me
convidem!
Agradecimento especial aos professores Marco César Goldbarg e Elizabeth Ferreira
Goldbarg não apenas pela excelente orientação acadêmica, mas por todas as lições ensinadas durante esse período de convivência. Agradeço por me fazer acreditar que eu era
capaz. Obrigado por me fazer sentir acolhido dentro do grupo, por serem referências de
prossionais sérios, competentes e dedicados e pelas possibilidades e oportunidade que me
foram dadas. Sou muito grato por tudo.
Agradeço ao pessoal do LAE, que sempre se mostrou receptivo e solícito nas ajudas.
Obrigado pela acolhida. Apesar da pouca convivência, fui muito feliz em fazer parte desse
grupo.
Agradeço aos membros da banca pelas contribuições dadas durante a elaboração desse
trabalho, em especial o professor Henrique Pacca Loureiro Luna, com o qual tive o prazer de discutir alguns modelos e, de alguma forma, compartilhar da sabedoria que só a
experiência e uma vida de dedicação à área proporcionam.
Finalmente, agradeço a todos que de uma forma direta ou indireta contribuíram para
o sucesso dessa empreitada. Fica registrado o meu muito obrigado a todos.
Somos todos poeira de estrelas.
Carl Sagan
O Problema do Caixeiro Alugador com Coleta de
Prêmios: Um Estudo Algoritmico
Autor: Matheus da Silva Menezes
Orientador(a): Dr. Marco César Goldbarg
Resumo
Este trabalho apresenta uma nova variante do problema do Caixeiro Alugador ainda não
descrita na literatura, denominada de Caixeiro Alugador com Coleta de Prêmios. Neste
problema são disponibilizados um conjunto de vértices, cada um com um bônus associado e um conjunto de veículos. O objetivo do problema é determinar um ciclo que visite
alguns vértices coletando, pelo menos, um bônus pré-denido e minimizando os custos de
viagem através da rota, que pode ser feita com veículos de diferentes tipos. É apresentada
uma formulação matemática e implementada em um solver produzindo resultados em sessenta e duas instâncias. O problema proposto também é objeto de um estudo algorítmico
experimental baseado na aplicação de quatro metaheurísticas de solução, representando
adaptações do melhor do estado da arte em programação heurística. Nesse trabalho também apresentamos a constituição de novos operadores que exploram as vizinhanças do
problema, procedimentos construtivos e adaptações, criados especicamente para o problema abordado. Experimentos computacionais comparativos e testes de desempenho são
realizados sobre uma amostra de 80 instâncias, visando oferecer um algoritmo de solução
competitivo para o problema. Conclui-se que algoritmos com abordagem memética, transgenética e evolucionária híbrida obtiveram resultados competitivos nos testes efetuados.
Palavras-chave : Caixeiro Alugador com Coleta de Prêmios. Metaheurísticas. GRASP/VNS.
Algoritmo Memético. Transgenética Computacional. Computação Evolucionária.
Prize Collecting Traveling Car Renter Problem: an
Algotithm Study
Author: Matheus da Silva Menezes
Supervisor: Phd Marco César Goldbarg
Abstract
This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated
with a bonus, and a set of vehicles are given. The objective is to determine a cycle that
visits some vertices collecting, at least, a pre-dened bonus, and minimizing the cost of the
tour that can be traveled with dierent vehicles. A mathematical formulation is presented
and implemented in a solver to produce results for sixty-two instances. The proposed
problem is also subject of an experimental study based on the algorithmic application of
four metaheuristics representing the best adaptations of the state of the art of the heuristic
programming. We also provide new local search operators which exploit the neighborhoods
of the problem, construction procedures and adjustments, created specically for the
addressed problem. Comparative computational experiments and performance tests are
performed on a sample of 80 instances, aiming to oer a competitive algorithm to the
problem. We conclude that memetic algorithms, computational transgenetic and a hybrid
evolutive algorithm are competitive in tests performed .
Keywords : The Prize Collecting Traveling Car Renter Problem. Metaheuristics. GRASP/VNS.
Memetic Algorithm. Computational Transgenetic. Evolutionary Computation
Lista de guras
1
Custos Operacionais e Taxas de Retorno das Cidades A, B e E e carros
1, 2 e 3 - CaRS
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .
p. 24
2
Rotas com Custos de Tráfego e Retorno para cada Carro- CaRS
3
Custos Operacionais e Taxas de Retorno para os carros 1, 2 e 3 - pCaRS
p. 45
4
Rotas com Custos de Tráfego e Retorno para cada Carro - pCaRS . . .
p. 46
5
Representação de uma Solução Genérica do problema pCaRS . . . . . .
p. 50
6
Exemplo de aplicaçãoção da busca removeCid()
. . . . . . . . . . . . .
p. 64
7
Exemplo de aplicação da busca inverteSol()
. . . . . . . . . . . . . . .
p. 65
8
Exemplo de aplicação da busca substituiCarro() . . . . . . . . . . . . .
p. 67
9
Exemplo de aplicação da busca substituiCidade()
. . . . . . . . . . . .
p. 68
10
Exemplo de aplicação da busca insereCidade() . . . . . . . . . . . . . .
p. 69
11
Exemplo de aplicação do procedimento de restauração() . . . . . . . . .
p. 71
12
Exemplo de aplicação do procedimento de Path-Relinking . . . . . . . .
p. 73
13
Exemplo de aplicação do procedimento 2Potencial . . . . . . . . . . . .
p. 74
14
Operador de Recombinação - Memético . . . . . . . . . . . . . . . . . .
p. 78
15
Exemplo de transferência de informações via Plasmídeo e Transposon
.
p. 81
16
Fluxo de informações em um algoritmo transgenético
. . . . . . . . . .
p. 83
17
Exemplo de aplicação do operador Plasmídeo Parcial
. . . . . . . . . .
p. 86
18
Exemplo de aplicação do operador Plasmídeo Total
. . . . . . . . . . .
p. 87
19
Exemplo de aplicação do transposon substituiCarro()
20
Ajuste dos parâmetros utilizados no algoritmo GRASP
21
Ajuste dos parâmetros utilizados no algoritmo Memético
. . . . . . . . . .
p. 24
p. 88
. . . . . . . . .
p. 94
. . . . . . . .
p. 99
22
Ajuste dos parâmetros utilizados no algoritmo GRASP
. . . . . . . . .
p. 110
23
Ajuste dos parâmetros utilizados no algoritmo GRASP
. . . . . . . . .
p. 111
Lista de tabelas
1
Resultados para as instâncias Euclidianas - CaRS
. . . . . . . . . . . .
2
Resultados para as instância não Euclidianas - CaRS
. . . . . . . . . .
p. 37
3
Resultados para as instância Euclideanas - GLPK . . . . . . . . . . . .
p. 53
4
Resultados para as instância não Euclideanas - GLPK . . . . . . . . . .
p. 54
5
Procedimentos utilizados por plasmídeos e transponsons
. . . . . . . .
p. 82
6
Resultados para as instâncias Euclidianas - pCaRS
. . . . . . . . . . .
p. 97
7
Resultados para as instância não Euclidianas - Abordagem GRASP
. .
p. 98
8
Resultados para as instância Euclidianas - Abordagem Memético . . . .
p. 101
9
Resultados para as instância não Euclidianas - Abordagem Memético
.
p. 102
10
Resultados para as instância Euclidianas - Abordagem Transgenético
.
p. 104
11
Resultados para as instância não Euclidianas - Abordagem Transgenético p. 105
12
Resultados para as instância Euclidianas - EH1
. . . . . . . . . . . . .
p. 107
13
Resultados para as instância não-Euclidianas - EH1 . . . . . . . . . . .
p. 108
14
Saída do teste Kruskal-Wallis - Problemas Euclidianos
p. 109
15
Saída do teste Kruskal-Wallis - Problemas não Euclidianos
16
Resultados para as instâncias Euclidianas - pCaRS
17
. . . . . . . . .
p. 36
. . . . . . .
p. 110
. . . . . . . . . . .
p. 113
Resultados para as instância não Euclidianas . . . . . . . . . . . . . . .
p. 114
Lista de abreviaturas e siglas
PCV - Problema do Caixeiro Viajante
CaRS - Traveling Car Renter Problem
pCaRS - Prize Collecting Traveling Car Renter Problem
PCTSP - Prize Collecting Traveling Salesman Problem
GRASP - Greedy Randomized Search Procedure
VNS - Variable Neighborhood Search
BQP - Binary Quadratic Problems
PTP - Protable tour problem
OP Orienteering Problem
TTDP - Tourist Trip Design Problems
PPL - Problemas de Programação Linear
BQP - Binary Quadratic Problems
LRC - Lista Restrita de Candidatos
VNS - Variable Neighborhood Algorithm
Lista de algoritmos
1
GRASP genérico para minimização . . . . . . . . . . . . . . . . . . . . .
p. 56
2
VNS genérico para minimização . . . . . . . . . . . . . . . . . . . . . . .
p. 58
3
GRASP proposto para o pCaRS
. . . . . . . . . . . . . . . . . . . . . .
p. 60
4
Fase Construtiva do GRASP
. . . . . . . . . . . . . . . . . . . . . . . .
p. 62
5
Busca Local: removeCidade()
. . . . . . . . . . . . . . . . . . . . . . . .
p. 64
6
Busca Local: InverteSol()
. . . . . . . . . . . . . . . . . . . . . . . . . .
p. 65
7
Busca Local: substituiCarro() . . . . . . . . . . . . . . . . . . . . . . . .
p. 66
8
Busca Local: substituiCidade()
. . . . . . . . . . . . . . . . . . . . . . .
p. 68
9
Busca Local: insereCidade() . . . . . . . . . . . . . . . . . . . . . . . . .
p. 69
10
Busca Local:
. . . . . . . . . . . . . . . . . . . . .
p. 70
11
GRASP VNS com Path Relinking proposto para o pCaRS . . . . . . . .
p. 72
12
Algoritmo memético genérico para minimização . . . . . . . . . . . . . .
p. 75
13
Algoritmo Memético MA1 proposto para o pCaRS
. . . . . . . . . . . .
p. 76
14
Algoritmo Memético MA2 proposto para o pCaRS
. . . . . . . . . . . .
p. 79
15
Algoritmo transgenético genérico para minimização . . . . . . . . . . . .
p. 82
16
Algoritmo Transgenético TA1 proposto para o pCaRS
. . . . . . . . . .
p. 84
17
Transposon: substituiCarro()
. . . . . . . . . . . . . . . . . . . . . . . .
p. 88
18
Transposon: substituiCidade() . . . . . . . . . . . . . . . . . . . . . . . .
p. 89
19
Transposon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 90
20
Algoritmo Evolutivo Híbrido EH1 proposto para o pCaRS . . . . . . . .
p. 93
buscaMultiOperadores
Sumário
1 Introdução
p. 17
1.1
Objetivos da Pesquisa
. . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 18
1.2
Metodologia da Pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 19
1.3
Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 20
1.4
Contribuições da Pesquisa
p. 20
. . . . . . . . . . . . . . . . . . . . . . . . .
2 O Problema do Caixeiro Alugador
2.1
p. 22
Descrição do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
2.1.1
Variações do Problema CaRS
. . . . . . . . . . . . . . . . . . .
p. 25
2.1.2
Estado da Arte do Problema CaRS . . . . . . . . . . . . . . . .
p. 26
2.1.3
Modelo Quadrático de Programação Inteira para o CaRS - CaRSModel 01
2.1.4
2.1.7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
Modelo de Programação Inteira Mista para o CaRS - CaRSModel
03
2.1.6
p. 27
Modelo de Programação Inteira Mista para o CaRS - CaRSModel
02
2.1.5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 31
Linearização das Restrições
. . . . . . . . . . . . . . . . . . . .
p. 32
2.1.6.1
Linearização usual
. . . . . . . . . . . . . . . . . . . .
p. 32
2.1.6.2
Linearização RLT . . . . . . . . . . . . . . . . . . . . .
p. 33
2.1.6.3
Linearização QP-LT
p. 33
. . . . . . . . . . . . . . . . . . .
Solução do modelo proposto através do
3 Caixeiro Alugador com Coleta de Prêmios
solver
GLPK
. . . . . .
p. 34
p. 38
3.1
Problemas de Roteamento com Coleta de Bônus . . . . . . . . . . . . .
p. 38
3.1.1
Protable tour problem . . . . . . . . . . . . . . . . . . . . . . .
p. 39
3.1.2
Orienteering Problem . . . . . . . . . . . . . . . . . . . . . . . .
p. 40
3.1.3
Prize Collection Traveling Salesman Problem(PC- TSP)
. . . .
p. 42
3.2
Trabalhos Relacionados ao Setor Turístico
. . . . . . . . . . . . . . . .
p. 43
3.3
Descrição do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 44
3.4
Formulação Matemática
p. 47
3.5
3.6
. . . . . . . . . . . . . . . . . . . . . . . . . .
O Banco de Instâncias pCaRSLIB
. . . . . . . . . . . . . . . . . . . .
p. 49
Representação de Soluções . . . . . . . . . . . . . . . . . . . . . . . . .
p. 50
3.6.1
p. 51
Solução do modelo proposto através do solver GLPK
. . . . . .
4 Algoritmos Propostos
4.1
4.2
p. 55
GRASP + VNS + Path Relinking . . . . . . . . . . . . . . . . . . . . .
p. 55
4.1.1
GRASP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 55
4.1.2
Variable Neighborhood Search - VNS . . . . . . . . . . . . . . .
p. 57
4.1.3
Path Relinking
p. 58
4.1.4
Algoritmo GRASP + VNS proposto
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
p. 60
4.1.4.1
Pseudo-Código do Algoritmo Proposto . . . . . . . . .
p. 60
4.1.4.2
Fase Construtiva
p. 61
4.1.4.3
Fase de Busca Local - VNS
4.1.4.4
Procedimentos de restauração de soluções
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . .
p. 63
p. 70
4.1.5
Algoritmo GRASP + VNS + Path Relinking proposto
. . . . .
p. 71
4.1.6
Algoritmo GRASP com Lista 2-Potencial . . . . . . . . . . . . .
p. 73
Algoritmo Memético
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 74
4.2.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 74
4.2.2
Pseudo-Código do Algoritmo Memético Proposto
. . . . . . . .
p. 76
População Inicial . . . . . . . . . . . . . . . . . . . . .
p. 76
4.2.2.1
4.3
4.2.2.2
Fase de Busca Local
. . . . . . . . . . . . . . . . . . .
p. 77
4.2.2.3
Recombinação
. . . . . . . . . . . . . . . . . . . . . .
p. 77
4.2.2.4
Renovação da População . . . . . . . . . . . . . . . . .
p. 78
Transgenética Computacional
4.3.1
4.3.2
. . . . . . . . . . . . . . . . . . . . . . .
p. 80
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 80
4.3.1.1
p. 81
Contexto Computacional . . . . . . . . . . . . . . . . .
Pseudo-Código do Algoritmo Transgenético Proposto (TA1)
. .
p. 83
4.3.2.1
População Inicial . . . . . . . . . . . . . . . . . . . . .
p. 85
4.3.2.2
Banco de Informações Genéticas
. . . . . . . . . . . .
p. 85
4.3.2.3
Plasmídeo . . . . . . . . . . . . . . . . . . . . . . . . .
p. 85
4.3.2.4
Transposons . . . . . . . . . . . . . . . . . . . . . . . .
p. 87
4.3.3
Algoritmo Transgenético com Reprodução do Endossimbionte
.
p. 90
4.3.4
Algoritmo Evolucionário Híbrido - EH1 . . . . . . . . . . . . . .
p. 91
5 Experimentos Numéricos Computacionais
p. 94
5.1
Algoritmos GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 94
5.2
Algoritmos Meméticos
. . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 99
5.3
Algoritmos Transgenéticos . . . . . . . . . . . . . . . . . . . . . . . . .
p. 103
5.3.1
. . . . . . . . . . . . . . . . .
p. 106
Análise Comparativa de Resultados . . . . . . . . . . . . . . . . . . . .
p. 109
5.4.1
Instâncias Euclidianas
. . . . . . . . . . . . . . . . . . . . . . .
p. 109
5.4.2
Instâncias não Euclidianas . . . . . . . . . . . . . . . . . . . . .
p. 110
5.4.3
Considerações sobre os resultados . . . . . . . . . . . . . . . . .
p. 111
5.4
Algoritmo Evolucionário Híbrido
6 Considerações Finais
6.1
Sugestão para Trabalhos Futuros
Referências
p. 115
. . . . . . . . . . . . . . . . . . . . .
p. 117
p. 118
17
1
Introdução
O Problema do Caixeiro Viajante (PCV) é um problema muito estudado na área de
Otimização Combinatória com diversos trabalhos desenvolvidos para sua resolução. Suas
aplicações encontram-se nas áreas de sistemas de manufatura, transportes, escalonamento
de tarefas, problemas de coletas e entregas de produtos, roteiros de veículos, localizações
de facilidades, roteamentos, redes de telecomunicações, dentre outros (GOLDBARG;
LUNA,
2005).
O Problema do Caixeiro Alugador ou
descrito na literatura por (GOLDBARG;
Traveling Car Renter Problem (CaRS)
ASCONAVIETA; GOLDBARG,
foi
2012) e é uma gene-
ralização do PCV, na qual um cliente pretende utilizar carros alugados para visitar um
determinado conjunto de cidades, minimizando o custo relacionado ao aluguel de carros
e de percurso. Existem várias opções de veículos de empresas diferentes disponíveis em
cada cidade. Esta multiplicidade de opções abre uma variedade de possibilidades de escolha para o utilizador sobre os carros mais atraentes para viajar por diferentes partes do
percurso pretendido. No caso de turismo, os clientes costumam começar e terminar sua
turnê na mesma cidade.
Dessa forma, o problema consiste em visitar um conjunto de cidades, começando e
terminando no mesmo ponto, minimizando o custo total da rota. Para tomar a decisão
sobre qual carro deve alugar em cada parte do percurso, o cliente deve considerar, além do
custo de locação de cada carro disponível, os custos relacionados ao consumo de combustível e pagamento de taxas. Se um carro é alugado em uma cidade e entregue em outra, o
usuário deve considerar também uma taxa extra para transportar o carro de volta à sua
origem.
Dado que o Problema do Caixeiro Viajante é NP-difícil (GUTIN;
PUNNEN,
2002) e
também é um caso especial do CaRS, quando apenas um carro é usado para realizar o
percurso, o problema CaRS também é um problema NP-difícil.
Neste trabalho é apresentada uma nova variante do problema CaRS denominda Cai-
18
xeiro Alugador com Coleta de Prêmios ou
(pCaRS)
Prize Collecting Traveling Car Renter Problem
, que é uma generalização do Problema do Caixeiro Viajante com Coleta de
Prêmios ou
The prize collecting traveling salesman problem
(PCTSP) . Este último foi
introduzido por (BALAS, 1989), e também é NP-difícil.
No PCTSP uma recompensa e uma penalidade são atribuídas a cada cidade. Devese escolher um subconjunto de cidades a serem visitadas para que o custo da rota e as
penalidades associadas com cada cidade não visitada sejam minimizados e a recompensa
total arrecadada deve ser de, pelo menos, o valor associado a um determinado parâmetro
ω.
O Problema pCaRS é uma variante do CaRS que, assim como no PCTSP, possui um
bônus associado a cada cidade. Esse bônus dene um nível de satisfação em visitar a cidade
associada. É muito comum o caso em que um turista não pode visitar todas as atrações
existentes durante uma viagem, devendo escolher as que possuam maior interesse.
Nesses casos, é interessante tentar maximizar a satisfação visitando os pontos mais
atraentes. O
Mobile Tourist Guide, apresentado por (SOUFFRIAU et al., 2008), foi projetado
para turistas que possuem limitação em visitar todos os lugares que estão interessados
em uma grande cidade. Alguns problemas relacionados ao turismo foram introduzidos
por (VANSTEENWEGEN;
D.,
2007), e um crescente volume de pesquisa tem sido dedicado
a esses problemas (VANSTEENWEGEN;
SOUFFRIAU; OUDHEUSDEN,
2011). Esses artigos,
contudo, não abordam o problema que considera a possibilidade de uso de mais de um
veículo pelos turistas.
No problema pCaRS uma satisfação presumida de visita é atribuída a cada cidade e
uma satisfação cumulativa pré-denida mínima deve ser atendida. Além disso, um vértice é
escolhido para ser a cidade a partir da qual o passeio começa e termina, denominada cidade
base. O objetivo é selecionar um subconjunto de cidades (vértices) a serem visitadas,
visando a minimização do custo total da viagem, incluindo o aluguel dos veículos e que a
satisfação mínima de visitar as cidades, representada pelo parâmetro
ω
seja atendida.
1.1 Objetivos da Pesquisa
O objetivo principal da presente pesquisa é propor e analisar um novo problema ainda
não descrito na literatura, denominado Problema do Caixeiro Alugador com Coleta de
Prêmios.
19
Com o objetivo de possibilitar a obtenção de soluções iniciais para o problema em
questão, será criado um banco de instâncias adaptado do problema CaRS, e também
será apresentada uma formulação matemática, devidamente implementada em um
solver,
denindo os primeiros limites inferiores para o problema.
Como parte da pesquisa serão desenvolvidos algoritmos heurísticos adaptados ao problema proposto, bem como será feita a análise estatística de resultados e desempenho
computacional entre os mesmos.
Para atingir tais objetivos, estabelecemos uma linha de ação preconizada por atos
especícos para este m: (1) Analisar o estado da arte dos problemas relacionados; (2)
Apresentar o problema e propor a formulação matemática correspondente; (3) Criar um
banco de instâncias para o problema; (4) Implementar a formulação matemática em um
solver ;(5) Criar algoritmos experimentais adaptados ao problema, bem como novas formas
de busca local; (6) Realizar experimentos computacionais nos algortimos apresentados,
efetuando a análise dos resultados e testes de desempenho de forma a propor um algoritmo
competitivo para o problema.
1.2 Metodologia da Pesquisa
A primeira etapa do trabalho foi relacionada ao estudo e denição de uma formulação
matemática para o problema CaRS, que serviu de embasamento para a pesquisa. Foram
elaborados e analisados dois modelos distintos com três formas de linearizações em cada,
aplicados na resolução de 62 instâncias do problema CaRS para a denição de limites
inferiores e comparação das estratégias de modelagem.
Em seguida, efetuou-se o estudo do pCaRS propriamente dito, onde foram realizadas
as atividades de denição do problema, a criação de instâncias de trabalho, a denição de
sua formulação matemática e respectiva implementação em um
solver. Nesta etapa tam-
bém foi realizado um levantamento bibliográco de problemas com tipologias semelhantes
e nas estratégias de solução utilizadas, de forma a estabelecer o "estado-da-arte"da área
em questão.
Dando prosseguimento à pesquisa, foi realizada a implementação de algoritmos metaheurísticos na busca por soluções do problema, efetuando as devidas adaptações em termos de estruturas de representação das soluções, operadores de busca local e a denição
de novas estratégias adaptadas ao problema, de forma a conseguir algoritmos competitivos
na busca de soluções do problema.
20
Com os resultados obtidos nos experimentos, através de testes de desempenho, procuramos efetuar comparações estatísticas entre as soluções encontradas pelos diversos
algoritmos propostos, de forma a validar as estratégias mais adaptadas ao problema.
1.3 Organização do trabalho
De forma a alcançar os objetivos preconizados, o trabalho possui a seguinte organização: uma pesquisa bibliográca sobre problemas relacionados é apresentada no Capítulo
2. A denição do problema do caixeiro alugador com coleta de prêmios e uma formulação
matemática são apresentadas no Capítulo 3, bem como os resultados de sua implementação em um
solver
e os respectivos resultados. O trabalho também apresenta algumas
metaheurísticas adaptadas ao problema no Capítulo 4. As metaheurísticas estudadas foram o GRASP, algoritmos meméticos e transgenética computacional. São analisadas 80
instâncias de problemas e os resultados são comparados com os obtidos com o solver. No
Capítulo 5 apresentamos um comparativo entre as versões propostas para cada abordagem, ilustrando alguns resultados qualitativos e de desempenho. Finalmente, são apresentadas as conclusões e considerações acerca do trabalho realizado no Capítulo 6.
1.4 Contribuições da Pesquisa
A presente pesquisa teve por objetivo denir e estudar um novo problema de roteamento de veículos, denominado
Prize Collecting Traveling Car Renter Problem (pCaRS) ,
que é uma generalização do Problema do Caixeiro Viajante com Coleta de Prêmios, combinado com elementos do
Car Renter Salesman Problem - CaRS. Teve como meta denir
os primeiros modelos matemáticos para o problema, e também as primeiras adaptações
metaheurísticas, combinadas ao estado da arte dos problemas correlatos e associados. As
principais contribuições da pesquisa são resumidas nos tópicos a seguir:
•
Proposição de modelagens para o problema CaRS, com a proposta de dois novos
modelos e três linearizações aplicadas em cada, e que serviu de contribuição de
Expert Systems with Applications
algorithm applied to the Traveling Car Renter Problem.
publicação na revista
•
sob o título
A transgenetic
Apresenta a denição do problema pCaRS e desenvolve os primeiros modelos matemáticos para o problema, comprovando que o mesmo é novo na literatura.
21
•
Cria um banco de testes adaptado às instâncias do problema, derivado do banco
CaRSLib
•
Apresenta um operador de busca local integrado, denominado
buscaMultiOperado-
res(), que pesquisa cinco vizinhanças distintas do problema.
•
Apresenta três metaheurísticas adaptadas ao problema, inserindo inovações nas mesmas, de forma a torná-las competitivas.
•
Efetua o estudo de uma abordagem GRASP/VNS considerando uma lista potencial
de grau 2.
•
Apresenta dois estudos com a abordagem memética, com os resultados apresentados
em trabalho completo durante o XLV SBPO.
•
Apresenta um estudo evolutivo híbrido competitivo, que considera a transferência
vertical e horizontal de genes.
•
Apresenta uma abordagem transgenética inovadora, considerando a reprodução do
hospedeiro.
•
Realiza experimentos computacionais considerando os diversos algoritmos propostos, contribuindo para a denição de algoritmos competitivos para o problema.
22
2
O Problema do Caixeiro Alugador
Neste capítulo será apresentado o problema do Caixeiro Alugador, problema do qual
o objeto de estudo da presente tese é derivado. Este capítulo tem por nalidade prencher
a lacuna existente, com a apresentação de três novos modelos de programação linear,
com abordagens distintas para o problema. São efetuados estudos computacionais com a
implementação dos métodos em um
solver
para vericar o desempenho dos modelos.
2.1 Descrição do Problema
De maneira geral, o Problema do Caixeiro Alugador (CaRS), é uma variante do problema do Caixeiro Viajante (PCV), foi descrito de forma pioneira por (GOLDBARG;
NAVIETA; GOLDBARG,
ASCO-
2012), sendo também objeto de estudo do trabalho realizado por
(ASCONAVIETA, 2011). Nesse problema, o caixeiro utiliza-se de veículos alugados para
realizar seu
tour, onde os custos de percorrer cada aresta dependem do veículo utilizado.
No problema, caberá denir quais veículos serão alugados, em que cidades da rota cada
um desses veículos será recebido e devolvido às locadoras e, simultaneamente, a rota percorrida por cada veículo, de forma a minimizar o custo total de viagem. Por se tratar de
um ciclo hamiltoniano, o percurso do caixeiro inicia e termina no mesmo vértice do grafo,
e todas as cidades do grafo são visitadas uma única vez.
Considere
conjunto com
G = (N, A) um grafo onde N
a
é um conjunto com
n nós (cidades) e A é um
arcos (estradas que interligam as cidades). Nesse problema, vários carros
estão disponíveis para aluguel em cada cidade. Cada carro possui custos especícos para
percorrer a distância entre as cidades. O tour inicia e termina na cidade inicial (ou cidade
base) que, nas instâncias consideradas, é a cidade representada pelo nó
problema é encontrar um ciclo hamiltoniano em
G
1. O objetivo deste
que minimize o custo do percurso.
Além disso, o problema descrito possui as seguintes características adicionais (ASCO-
NAVIETA,
2011):
23
1. Estão disponíveis para o aluguel vários tipos de carro, cada qual possuindo características próprias, com custos de operação especícos. Tais custos englobam o
consumo de combustível, eventuais taxas de pedágio e o valor do aluguel. Como as
taxas de pedágio dependem, normalmente, tanto do tipo de carro como da extensão
do trecho percorrido, o valor do aluguel pode ser associado ao quilômetro rodado.
Sem perda de generalidade, pode-se considerar que todos os custos são contabilizados em função de cada carro em um valor associado ao peso ou comprimento das
arestas
(i, j) do grafo G. O custo total de operação de um dado carro c ao percorrer
uma aresta
(i, j)
é representado pelo parâmetro
dcij .
2. Um carro alugado em uma dada operadora somente poderá ser devolvido em uma
cidade que conta com pelo menos uma agência dessa mesma locadora ou agência
conveniada. Consequentemente, não é permitido ao caixeiro alugar um carro de
uma dada operadora para cumprir um trecho de sua rota, se esse carro não puder
ser devolvido na última cidade do trecho (ou seja, se nessa cidade não existir uma
agência com capacidade para executar seu recebimento).
3. Se o carro
c
foi locado em uma cidade
diferente em uma cidade
j,
i,
ele pode ser trocado por outro de custo
tendo para isso que arcar com os custos de retorno do
carro ao nó em que foi alugado (nó i), representado por
4. O caso em que o caixeiro realiza seu
tour
γijc . Caso i = j , então γijc = 0
utilizando apenas um veículo, corresponde
ao problema do caixeiro viajente clássico, considerando-se as demais condições de
custo associadas apenas ao carro selecionado.
5. Mesmo carros de características iguais e alugados em uma única rede de locação
podem ser contratados sob diferentes custos, dependendo da cidade de locação e da
negociação de contrato. Portanto, sem perda de generalidade, a designação de aluguel pode ser ecazmente controlada por decisões associadas aos carros, abstraindose as locadoras. Presentemente o conjunto
C = 1, ..., c, |C| = c
é o conjunto dos
diferentes carros que podem participar da solução.
6. Os custos do retorno do carro alugado podem estar estritamente associados ao caminho entre a cidade de entrega e a de origem, ou serem decorrentes de cálculo
independente.
O ciclo Hamiltoniano resultante da solução do problema também pode ser visto como
a união disjunta dos caminhos realizados por cada veículo na solução sobre
A.
A cidade
24
em que um carro é alugado e outro é devolvido, é a aresta que realiza a ligação entre dois
caminhos disjuntos no grafo.
Figura 1: Custos Operacionais e Taxas de Retorno das Cidades A, B e E e carros 1, 2 e 3 CaRS
Figura 2: Rotas com Custos de Tráfego e Retorno para cada Carro- CaRS
A Figura 1 exemplica, em um grafo completo de cinco vértices, uma típica instância
do CaRS. No exemplo existem três diferentes carros de aluguel, e os carros estão disponíveis para serem alugados e entregues em todas as cidades do grafo. As arestas do grafo
exibem a contabilidade dos custos envolvidos no deslocamento de cada tipo de carro.
Observe-se que, diferentemente do ciclo do caixeiro viajante clássico, a solução do CaRS
depende da cidade escolhida para o início do tour, cidade base do caixeiro.
Esse fato decorre da taxa de retorno poder estar vinculada tanto à cidade que inicia
o ciclo, quanto ao próprio sentido de percurso desse ciclo. No exemplo essa cidade é
representada pelo vértice E.
A Figura 1 ainda mostra alguns dos custos do retorno dos carros a suas bases. Os
25
custos de entrega aparecem como números sublinhados junto aos vértices. A Figura 2 (a)
exibe o grafo de retorno do carro 1, quando alugado no vértice E e devolvido no vértice
A. (b) exibe o grafo de retorno do carro 2, quando alugado no vértice A e devolvido no
vértice B; e (c) o retorno do carro 3, quando alugado no vértice B e devolvido no vértice
E. (d) exibe as rotas utilizadas na solução. No caso geral do problema são conhecidos os
custos de retorno de todos os carros, quando alugados em qualquer uma das cidades.
2.1.1 Variações do Problema CaRS
De acordo com a denição do problema apresentada por (GOLDBARG;
GOLDBARG,
ASCONAVIETA;
2012), o Caixeiro Alugador admite algumas situações especícas, podendo
ser classicado de acordo com:
1.
Disponibilidade de carros para aluguel (parcial
×
total):
Na prática, não
existe garantia de que as empresas de locação se façam presentes em todas as cidades
de um tour. Dessa forma, não se pode estabelecer de forma rigorosa, que qualquer
carro pode ser alugado em qualquer cidade. O caso em que é possível alugar todos os
carros em todas as cidades é denominado total. Em qualquer outro caso, o problema
é denominado parcial.
2.
Alternativas de devolução do carro alugado (restrito
×
irrestrito):
As
empresas de locação podem não operar serviços de recepção de carros em todas as
cidades, não garantindo que qualquer carro alugado possa ser devolvido em qualquer
cidade. No caso em que a recepção pode ser realizada em todas as cidades o problema
é denominado irrestrito. Em qualquer outra situação o problema será denominado
de restrito.
3.
Integridade do contrato (sem repetição
×
com repetição):
Nos casos em
que não seja permitido que o mesmo tipo de carro seja alugado mais de uma vez no
tour
do caixeiro, o problema é denominado sem repetição. No caso sem repetição,
em que todos os carros devam ser obrigatoriamente alugados, é denominado exato.
O problema é denominado com repetição em qualquer outro caso.
4.
Cálculo dos custos de devolução do carro alugado (livre × vinculado): Os
custos de devolução dos carros podem ser constituídos por valores independentes
da topologia ou restrições da rede. Nesse caso, o problema é dito livre. No caso em
que os custos de devolução de um carro são calculados levando em conta a rota
empregada pelo carro para retornar a sua base, o problema é dito vinculado.
26
5.
Simetria das distâncias entre as cidades (simétrico
casos em que
dcij = dcji
para
1 < i, j ≤, 1 ≤ c ≤ ncars
×
onde
assimétrico):
ncars
Nos
representa o
número de carros disponíveis para alugar em dado caso, o problema é denominado
simétrico. Em caso contrário, o problema é denominado assimétrico. Observe-se
que o problema simétrico não implica que os custos nais de operação possam ser
considerados simétricos. A denominação de simetria distingue o tipo da matriz de
distâncias do grafo.
6.
Existência de ligações no grafo de conexão que modela o problema (completo × incompleto): Quando o grafo do problema for completo, o problema
receberá o mesmo nome. O problema será denominado incompleto em caso contrário.
Finalmente, é também possível identicar a variante do caminho do caixeiro alugador.
Nesse caso, o caixeiro alugador não deseja realizar um
tour
que retorne à primeira cidade
do ciclo. Seu desejo, no entanto, é realizar um caminho entre duas determinadas cidades
do grafo.
O problema analisado por (ASCONAVIETA, 2011), (GOLDBARG;
BARG,
2012), (ASCONAVIETA;
GOLDBARG; GOLDBARG,
ASCONAVIETA; GOLD-
2012) e em (GOLDBARG
et al.,
2013) foi total, irrestrito, sem repetição, livre, e completo. Quanto à simetria das distâncias
entre as cidades, foram analisados problemas simétricos e que preservam a desigualdade
triangular.
2.1.2 Estado da Arte do Problema CaRS
O problema CaRS foi objeto de alguns estudos recentes, entre eles (ASCONAVIETA,
2011), (GOLDBARG; ASCONAVIETA; GOLDBARG, 2012), (ASCONAVIETA; GOLDBARG; GOLD-
BARG,
2012) que abordaram sempre a mesma variante do problema, com abordagens
distintas.
As abordagens para resolução exata do problema foram a implementação de um
tracking
em (GOLDBARG;
ASCONAVIETA; GOLDBARG,
back-
2012), que variou entre 1 segundo
para encontrar a solução exata de um problema com 10 cidades e 2 carros disponíveis, até
88 dias para solucionar uma instância de 16 cidades e 2 carros, mostrando-se ineciente
na obtenção de resultados em um tempo computacional razoável. Esta abordagem foi utilizada para conseguir encontrar a solução ótima em 16 pequenas instâncias do problema.
27
Em (GOLDBARG
solver (GLPK;
et al., 2013) foi apresentada uma formulação exata e implementada no
MAKHORIN,
2012), com limitação de tempo disponível para processamento
(70.000 segundos) e memória utilizada (14Gb) em 26 pequenas instâncias do problema,
com tamanho variando entre 10 cidades e 2 carros disponíveis, até 32 cidades e 4 carros
disponíveis para alugel. Neste estudo, foi possível obter soluções de problemas com até
16 cidades e 2 carros. A abordagem exata conseguiu encontrar a solução ótima em 18 dos
problemas analisados. Em problemas maiores, o
solver
não alcançou a solução ótima, por
problemas de limitação de memória ou de tempo de processamento.
As soluções utilizando metaheurísticas abordadas em (GOLDBARG;
GOLDBARG,
ASCONAVIETA;
2012) foram um algoritmo GRASP(Greedy Randomized Search Procedure)
com hibridização de um algoritmo VNS (Variable Neighborhood Search) e um Algoritmo
Memético aplicados em 40 instâncias Euclidianas e não Euclidianas do CaRS, onde 4
backtrack
problemas tiveram a solução ótima vericada pelo
e o algoritmo memético
estabelecendo os outros 36 primeiros limites superiores para o problema.
Em (GOLDBARG
et al.,
2013) foi apresentado um algorimo memético e um algoritmo
transgenético aplicados em 60 instâncias maiores do problema, sendo 30 Euclidianas e 30
não Euclidianas, onde cou evidenciado o desempenho superior em termos de tempo e
qualidade de solução do algoritmo transgenético.
2.1.3 Modelo Quadrático de Programação Inteira para o CaRS CaRSModel 01
Uma formulação matemática para o problema foi apresentada em (GOLDBARG
et al.,
2013). A formulação deriva da ideia de que a formulação do PCV pode ser vista como um
modelo quadrático de programação inteira (BECKMAN;
KOOPMANS,
1957), com a função
objetivo representada por uma função quadrática e com restrições lineares, onde uma
única ordem de visitação
k = 1, ..., n
é denida para cada nó
tamanho do modelo depende essencialmente dos parâmetros
No modelo proposto, a variável
k
ordem
visitação
k < n.
i 6= j ,
com o carro
c
e
0
xcki
é denida como
1
n
e
i ∈ N.
Dessa forma, o
|C|.
quando o nó
i
é visitado na
caso contrário. Nesse modelo, a cidade base tem a ordem de
k = n, fechando o ciclo, enquanto as demais cidades possuem ordem de visitação
Quando um carro
c
é locado em uma cidade
então duas variáveis booleanas
yic
e
zjc
i
e devolvido em uma cidade
tem a atribuição de valor
O modelo apresentado para o problema foi o seguinte:
1.
j,
com
28
|C| n−1
X
X X
X
X
min
[
dcij xcki xc(k+1)j +
dc1j xcn1 xc1j +
γijc yic zjc ]
c=1 k=1 (i,j)∈A
(2.1)
i∈N,j∈N
(1,j)∈A
sujeito a:
|C| n
X
X
xcki = 1 ∀ i = 1, ..., n
(2.2)
xcki = 1 ∀ k = 1, ..., n − 1
(2.3)
c=1 k=1
|C|
n
XX
c=1 i=2
|C|
X
xcn1 = 1
(2.4)
c=1
|C|
X
y1c = 1
(2.5)
z1c = 1
(2.6)
zic = 0 ∀ i = 2, ..., n
(2.7)
xcki ∈ {0, 1} ∀ c = 1, ..., |C|; k = 1, ..., n; i = 1, ..., n
(2.8)
yic ∈ {0, 1} ∀ c = 1, ..., |C|; i = 1, ..., n
(2.9)
zjc ∈ {0, 1} ∀ c = 1, ..., |C|; j = 1, ..., n
(2.10)
c=1
|C|
X
c=1
|C|
|C|
X
c=1
yic −
X
c=1
A função objetivo (2.1) soma os custos referentes aos deslocamentos na rota e custos
de devolução dos veículos. A restrição (2.2) garante que cada cidade é visitada uma única
vez por exatamente um carro. A restrição (2.3) assegura a ordem de visitação genérica
k 6= n
para qualquer cidade diferente da cidade base (nó-1). As restrições (2.4) a (2.6)
dizem respeito a cidade inicial e aparecem apenas uma vez no modelo. A restrição (2.4)
garante que a cidade base é o último nó a ser visitado com um único carro. A restrição
(2.5) assegura que exatamente um carro é alugado, enquanto a restrição (2.6) garante que
um carro é devolvido na cidade base. Para qualquer outra cidade a restrição
i 6= 1,
(2.7)
conrma que se um carro é locado, então um carro também é devolvido naquela cidade.
As demais restrições (2.8), (2.9) e (2.10) denem que cada variável dos vetores
são do tipo booleano, ou seja, podem assumir valores
0
ou
1.
x, y
e
z
29
2.1.4 Modelo de Programação Inteira Mista para o CaRS - CaRSModel 02
O modelo quadrático apresentado não pode ser aplicado diretamente em um
solver,
pois possui função objetivo não linear. De forma a contornar essa diculdade, é proposta
uma adaptação desse modelo, considerando a função objetivo linear, reescrevendo da
seguinte forma:
30
n
XX
X
kc
[
dchi fhi
+
min
X
c c
γij
wij ]
(2.11)
sujeito a:
(2.12)
xcki = 1 ∀ i = 1, ..., n
(2.13)
c∈C k=1 (h,i)∈A
i∈N,j∈N
|C|
n
XX
c=1 k=1
|C| n
X
X
xcki = 1 ∀ k = 1, ..., n
(2.14)
c=1 i=1
|C|
X
xc11 = 1
(2.15)
c=1
|C|
X
y1c = 1
(2.16)
z1c = 1
(2.17)
zic = 0 ∀ i = 1, ..., n
(2.18)
nc
fi1
= xc11 ∀ i = 2, ..., n ∀ c ∈ C
(2.19)
kc
fij
= xcki ∀ k = 2, ..., n ∀ i = 1, ..., n ∀ c ∈ C
(2.20)
c=1
|C|
X
c=1
|C|
X
yic −
c=1
c=1
X
|C|
X
(i,j)∈A
X
(i,j)∈A
X
nc
fhi
= xcni ∀ i = 1, ..., n ∀ c ∈ C
(2.21)
kc
fhi
= xc(k+1)i ∀ k = 1, ..., n − 1 ∀ i = 1, ..., n ∀ c ∈ C
(2.22)
(h,i)∈A
X
(h,i)∈A
X
c
wij
= yic ∀ i = 1, ..., n ∀ c ∈ C
(2.23)
c
wij
= zjc ∀ j = 1, ..., n ∀ c ∈ C
(2.24)
xc(k+1)j ∀ i = 1, ..., n − 1 ∀ c ∈ C∀ k ∈ C
(2.25)
j∈N
X
i∈N
X
yic =
xrki
n
X
j=1
r∈C,r6=c,r<n
X
xrni xc11 ∀ i = 1, ..., n ∀ c ∈ C
(2.26)
xr(k+1)j ∀ i = 1, ..., n − 1 ∀ c ∈ C
(2.27)
r ∈ C, r 6= c, r < nxr11 ∀ i = 1, ..., n ∀ c ∈ C
(2.28)
∈ {0, 1} ∀ c = 1, ..., |C|; k = 1, ..., n; i = 1, ..., n
(2.29)
yic , zjc ∈ {0, 1} ∀ c = 1, ..., |C|; j = 1, ..., n
(2.30)
c
wij
∈ {0, 1}∀ i = 1, ..., n ∀ j = 1, ..., n ∀ c ∈ C
(2.31)
ync =
r∈C,r6=c,r<n
zic =
X
k∈K
znc =
n
X
xcki
X
j6=i,j=1 r∈C,r6=c,r<n
n
X
xcni
i=1
xcki
X
kc
fhi
≥ 0∀(h, i) ∈ A ∀ k = 1, ..., n ∀ c ∈ C
(2.32)
31
2.1.5 Modelo de Programação Inteira Mista para o CaRS - CaRSModel 03
Outra formulação linear interira proposta para o problema do caixeiro viajante foi proposta por (DANTZIG;
FULKERSON; JOHNSON,
1954). Essa formulação foi proposta para
resolver um problema com 49 cidades, formulando o PCV como um problema de programação inteira, com restrições tanto de controle de uxo nos nós, como de eliminação de
possíveis sub-rotas. Com base nessa formulação, é proposto outro modelo para o problema
CaRS:
min
XX
c∈C
dcij · fijk +
XX
c
γijc · wij
(2.33)
c
ij
fijc
=1
∀i ∈ V
(2.34)
fijc = 1
∀j ∈ V
(2.35)
X
(fijc + fjic ) ≤ 1
∀i, j ∈ V, i 6= j
(2.36)
fjir
∀k ∈ K, i ∈ V, i 6= j
(2.37)
fijr
∀k ∈ K, i ∈ V, i 6= j
(2.38)
eci
∀c ∈ C, i ∈ V, j ∈ V
(2.39)
ij
XX
c∈C j∈V
XX
c∈C i∈V
c∈C
aci =
X
fijc ·
j∈V
eci =
X
X X
r∈C,r6=c j∈V
fjic ·
j∈V
X X
r∈C,r6=c j∈V
c
wij
= aci ·
X
ac1 = 1
(2.40)
ec1 = 1
(2.41)
c∈C
X
c∈C
XX
xi,j ≤ |S| − 1
∀S ⊂ N
(2.42)
c
fijc , wij
, aci , eci ∈ [0, 1]
(2.43)
k∈K i,j∈S
A função objetivo é apresentada em (2.33). Ela inclui o custo de percorrer as rotas
com diferentes carros e taxas referentes a devolução dos mesmos. As restrições (2.34 e
2.35) garantem que a rota começa e termina na cidade base, ou seja, o vértice 1. A
restrição (2.36) garante que cada vértice é visitado, no máximo, uma vez e se um carro
chega ao vértice i, um carro deve deixar esse vértice. As restrições (2.37), (2.38) e (2.39),
estão relacionadas ao aluguel e entrega do veículo. A restrição (2.40) garante que um
carro é alugado no nó
1.
A restrição (2.41) assegura que cada carro locado seja entregue.
32
A restrição (2.42) proíbe a formação de subrotas. A restrição (2.43) declara algumas
variáveis binárias.
2.1.6 Linearização das Restrições
Como pode ser visto nos modelos propostos, algumas restrições são não-lineares, mas
suas variáveis são binárias. Binary Quadratic Problems (BQP)
NP-difícil (ELLOUMI;
FAYE; SOUTIF,
são problemas do tipo
2000) e ocorrem quando existe um produto de variá-
veis binárias na função objetivo. Esse problema pode ser linearizado (HANSEN;
2009), (ADAMS;
FORRESTER; GLOVER,
2004), (HE
et al.,
MEYER,
2012a) para obter um problema
de programação linear inteiro mista. As técnicas de linearização propostas nesses estudos
podem ser extendidas e adaptadas para remover a restrição quadrática,
z = x · y.
2.1.6.1 Linearização usual
De acordo com (HANSEN;
MEYER,
2009), a primeira linearização foi proposta de forma
independente por alguns autores, a exemplo de (FORTET, 1960), (DANTZIG, 1960), (BA-
LAS,
1964), (ZANGWILL, 1976), (WATTERS, 1967).
A linearização a seguir, conhecida como linearização usual (LIBERTI, 2007), aponta a
possibilidade de remoção da restrição quadrática, substituindo esta restrição não linear
pelo conjunto de restrições:
Em (GLOVER;
WOOLSEY,
x+y−z ≤1
(2.44)
−x − y + 2z ≤ 0
(2.45)
z ∈ [0, 1]
(2.46)
1974) foi proposta a substituição de uma das restrições,
obtendo o modelo abaixo:
z ≥x+y−1
(2.47)
z≤x
(2.48)
z≤y
(2.49)
z, x, y ∈ [0, 1]
(2.50)
33
De acordo com (HANSEN; MEYER, 2009), esta linearização considera a criação de
O(n2 )
novas variáveis e restrições lineares.
2.1.6.2 Linearização RLT
A linearização RLT é derivada da Linearização Usual ((HANSEN;
a abreviação de
TER; GLOVER,
MEYER,
2009) e é
Reformulation-Linearization Technique, proposta por (ADAMS; FORRES-
2004) e considera a criação de
2n novas restrições lineares. Essa técnica de
linearização foi adaptada da seguinte forma:
x−z ≥0
(2.51)
−x + w ≥ −1
(2.52)
w−y+z =0
(2.53)
x, y ∈ [0, 1], w ≥ 0
(2.54)
2.1.6.3 Linearização QP-LT
A terceira adaptação considerada é baseada na linearização proposta por (CHAO-
VALITWONGSE; PARDALOS; PROKOPYEV,
2004), que foi denominada pelos autores por
Quadratic Programming Linearization Technique - QP-LT, e que aqui é denominada por
Linearização
QP − LT .
Nesse modelo, os autores armam que são criadas apenas
2n
variáveis adicionais, deixando o modelo mais compacto do que outras linearizações. Vale
salientar que a linearização aqui proposta não é exatamente a mesma vista no trabalho
supracitado, tendo sido adaptada para suprir apenas a linearização da restrição. O modelo
proposto por esta linearização é o seguinte:
z =x−w
(2.55)
w ≤1−y
(2.56)
w ≥x−y
(2.57)
x, y ∈ [0, 1], w ≥ 0
(2.58)
Para escrever estas restrições no GLPK, efetuou-se a linearização das mesmas, conforme sugerido em (BISSCHOP, 2012). Outras formas de linearização são discutidas em
34
(HANSEN; MEYER, 2009), (LIBERTI, 2007), (CHAOVALITWONGSE; PARDALOS; PROKOPYEV,
2004) e também em (HE
et al.,
2012b).
2.1.7 Solução do modelo proposto através do solver GLPK
O modelo proposto foi implementado em um computador com processador Intel Core
i5, 14gb de memória RAM, rodando o sistema operacional Ubuntu 12.04 64bits, e implementado no Solver GLPK versão 4.47. O GLPK (GNU Linear Programming Kit) é
um
solver
voltado para a resolução de problemas de programação linear (LP) e progra-
mação inteira mista (MIP). A linguagem utilizada para modelar o problema foi a
MathProg modeling language,
GNU
e o método utilizado foi o SIMPLEX primal. O tempo de
processamento foi limitado a 20000 segundos.
De forma a denir os primeiros limites inferiores para alguns problemas da biblioteca CArSLIB, foram realizados testes em 62 pequenas instâncias do problema, sendo 31
euclidianas e 31 não euclidianas.
As Tabelas 1 e 2 apresentam o resultado desse primeiro experimento computacional.
As colunas
N ome, nCid e nCar estão relacionadas com as características de cada instância
e são, respectivamente, a identicação do problema, o número de cidades e o número
de carros disponíveis. As colunas
M in
e
T (s),
estão relacionadas com a solução obtida
pelo solver GLPK, e mostram o valor da melhor solução viável inteira e o tempo de
processamento, em segundos, para cada modelo e linearização considerados. A coluna
GAP , apresenta o desvio percentual do valor apresentado a partir de um limite global para
a solução exata calculada pelo GLPK. Destaca-se em negrito o melhor valor encontrado
para o problema.
Sendo a precisão computacional representada por
, best_mip
e
best_bound
repre-
sentam, a melhor solução inteira para o problema e a melhor solução relaxada, respectivamente, o GAP é dado por:
GAP =
O modelo
CaRSModel 01
|best_mip − best_bound|
|best_mip + |
(2.59)
não foi implementado, pois sua função objetivo é não li-
CaRSModel 02 aqui é representada como modelo M 1.
O terceiro modelo proposto, denominado CaRSModel 03 é aqui denominado modelo M 2.
near. Sua adaptação, proposta no
A linearização usual é representada por
viação
L2. Já a linearização QP − LT
L1. A linearização RLT é representada pela abre-
é representada como
L3. A junção da nomenclatura
35
de modelo e linearização é apresentada na tabela para representar os resultados do modelo
com a técnica de linearização correspondente. Por exemplo, a coluna
ao modelo
M2
e a aplicação da técnica de linearização
M 2L1
diz respeito
L1.
Os resultados apresentados na Tabela 1 mostram que o modelo
M1
não encontra
a solução ótima para 8 das 31 instâncias euclidianas. O GAP variou entre 0,8 a 52,4.
Independente da linearização utilizada, os problemas que caram sem garantia de solução
ótima para este modelo foram os mesmos. A parada se deu pela limitação de tempo
disponível para a solução do problema. Observa-se também que, com o aumento do número
de cidades e carros nas instâncias, o tempo gasto pelo solver para encontrar a solução
também aumenta.
Ainda na Tabela 1, os resultados do modelo
M2
conseguem alcançar a solução ótima
para todos os problemas, com exceção das linearizações
L1
e
L2,
que não atingiram a
solução ótima para o problema BrasilMG30e, com GAP de 8,3 e 8,8 respectivamente.
Os tempos de processamento do modelo
gastos pelo modelo
M 2.
M1
foram sistematicamente menores do que os
Essa diferença ca evidenciada em alguns problemas, a exem-
plo do problema Sudao15e, onde as linearizações do modelo
M1
tiveram um tempo de
processamento de 10.011, 8.700 e 9.819 segundos respectivamente para alcançar o ótimo,
enquanto para o modelo
M2
os tempos foram de 21, 33 e 28 segundos, respectivamente.
Os resultados para as instâncias não euclideanas apresentados na Tabela 2 mostram
que o modelo
M1
não conseguiu encontrar o ótimo global para 17 instâncias. À medida
em que os problemas aumentaram o número de cidades e carros disponíveis, o GAP teve
uma tendência de aumento. Para os dois maiores problemas, denominados BrasilAM26n e
BrasilMG30n, o GLPK, através do modelo
relaxada. Para o modelo
M 2,
M 1, não conseguiu encontrar nenhuma solução
tivemos 5 problemas em que não foi possível encontrar o
ótimo global, com GAP variando entre 0,5 e 24,2.
Na comparação geral entre os modelos, podemos destacar que o modelo
uma taxa de sucesso maior do que o modelo
M 1,
M2
obteve
cando evidenciado o seu melhor de-
sempenho. Verica-se também que o segundo modelo teve um tempo de execução menor,
tanto em instâncias euclidianas, quanto não euclidianas, quando comparado ao modelo
M 1.
Em relação às linearizações utilizadas, observa-se que houve utuações no desempe-
nho, onde a melhor linearização dependeu de cada problema analisado. Na maioria dos
casos, o tempo utilizado para encontrar o ótimo foi similar para cada modelo, em relação
às linearizações analisadas.
Nome
Mauritania10e
Colombia11e
Angola12e
Peru13e
Libia14e
BrazilRJ14e
Congo15e
Argentina16e
EUA17e
Bolivia10e
AfricaSul11e
Niger12e
Mongolia13e
Indonesia14e
Argelia15e
India16e
China17e
Etiopia10e
Mali11e
Chade12e
Ira13e
Mexico14e
Sudao15e
Australia16e
Canada17e
Arabia14e
Cazaquistao15e
Brasil16e
Russia17e
BrasilAM26e
BrasilMG30e
10
11
12
13
14
14
15
16
17
10
11
12
13
14
15
16
17
10
11
12
13
14
15
16
17
14
15
16
17
26
30
nCid
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
3
3
nCar
904
1154
1229
916
851
1073
1288
631
645
840
764
789
823
1031
M1L1
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
1
14
35
58
82
63
30
2292
1872
11
9
54
3328
113
9102
1853
20000
69
58
830
539
2737
10011
20000
20000
3466
20000
20000
20000
20000
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
10,3%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
10,3%
7,6%
0,0%
0,8%
7,8%
21,3%
52,4%
-%
GAP
904
1136
1180
913
851
1090
1312
631
645
840
764
789
823
1016
M1L2
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
2
12
51
32
112
120
51
3723
2266
10
11
46
3420
126
9203
1500
20000
103
72
866
483
5409
8700
20000
20000
2588
20000
20000
20000
20000
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
8,4%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
12,0%
9,1%
0,0%
2,7%
7,2%
17,7%
52,2%
GAP
919
1229
1234
851
1067
1251
631
645
840
764
789
823
1021
M1L3
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
2
9
37
53
96
73
67
3713
1879
6
11
62
3339
108
7706
1532
20000
47
56
758
720
4493
9819
20000
20000
2529
20000
20000
20000
20000
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
8,8%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
9,4%
4,6%
0,0%
4,8%
15,2%
21,5%
GAP
555
M2L1
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
1003
631
645
840
764
789
823
1051
1251
851
904
1136
1061
467
Tabela 1: Resultados para as instâncias Euclidianas - CaRS
1
1
1
1
1
10
1
8
4
1
1
1
105
2
70
5
298
4
3
31
9
32
21
559
476
24
80
251
588
1057
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
8,3%
GAP
565
M2L2
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
1003
631
645
840
764
789
823
1051
1251
851
904
1136
1061
467
1
2
1
2
1
22
1
24
6
1
1
1
72
2
38
5
2165
2
5
25
8
33
33
509
931
35
70
233
1031
794
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
8,8%
GAP
M2L3
540
620
719
672
730
294
756
955
912
592
567
743
760
799
840
1035
1003
631
645
840
764
789
823
1051
1251
851
904
1136
1061
467
529
1
2
1
2
3
12
2
22
5
1
1
1
82
1
92
4
1430
4
3
17
6
17
28
628
460
42
87
332
858
938
12436
T (s)
36
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
GAP
10
11
12
13
14
14
15
16
17
10
11
12
13
14
15
16
17
10
11
12
13
14
15
16
17
14
15
16
17
26
30
nCid
Problemas
Nome
Mauritania10n
Colombia11n
Angola12n
Peru13n
Libia14n
BrazilRJ14n
Congo15n
Argentina16n
EUA17n
Bolivia10n
AfricaSul11n
Niger12n
Mongolia13n
Indonesia14n
Argelia15n
India16n
China17n
Etiopia10n
Mali11n
Chade12n
Ira13n
Mexico14n
Sudao15n
Australia16n
Canada17n
Arabia14n
Cazaquistao15n
Brasil16n
Russia17n
BrasilAM26n
BrasilMG30n
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
3
3
nCar
896
908
910
913
1043
1071
1154
1057
1137
1270
1112
666
777
799
866
989
924
822
681
714
847
740
M1L1
571
639
656
693
760
1670
886
3
4
8
20
44
42
137
20000
525
77
7069
13733
15891
20000
20000
20000
20000
481
1061
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
4,3%
0,0%
0,0%
0,0%
0,0%
0,0%
5,9%
8,0%
6,1%
4,8%
0,0%
0,0%
3,4%
1,6%
20,6%
18,0%
8,5%
15,4%
15,9%
21,3%
27,0%
19,2%
909
918
903
1044
1076
1153
1033
1153
1216
1123
666
777
796
870
986
929
822
681
714
847
740
894
M1L2
571
639
656
693
760
1670
886
GRASP1
GAP
3
3
10
20
75
48
162
20000
371
58
7477
11080
11976
20000
20000
20000
20000
581
2161
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
3,7%
0,0%
0,0%
0,0%
0,0%
0,0%
5,6%
8,4%
5,1%
5,4%
0,0%
0,0%
4,3%
4,1%
10,6%
17,8%
8,7%
15,2%
10,9%
21,7%
23,2%
19,7%
GAP
897
777
908
909
908
1054
1064
1158
1118
1155
1302
1126
666
805
869
988
921
822
681
714
847
740
2
4
5
36
54
85
319
20000
382
68
7006
12818
15458
20000
20000
20000
20000
417
1890
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
20000
T (s)
GraspPR
M1L3
571
639
656
693
760
1670
886
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
4,3%
0,0%
0,0%
0,0%
0,0%
0,0%
7,3%
8,3%
5,4%
4,5%
0,0%
0,0%
4,8%
1,1%
11,1%
19,4%
770,0%
15,9%
20,8%
21,6%
28,3%
19,8%
GAP
863
281
202
1166
1110
1026
1043
1032
1061
1136
666
777
930
909
902
919
985
M2L1
571
639
656
693
760
1670
886
894
822
681
714
847
740
796
Tabela 2: Resultados para as instância não Euclidianas - CaRS
1
1
1
1
2
6
2
4
921
4
189
95
202
181
20000
503
20000
31
9
932
801
8772
20000
20000
20000
1122
6588
20000
20000
65
20000
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
2,5%
0,0%
1,7%
0,0%
0,0%
0,0%
0,0%
0,0%
6,1%
0,5%
0,7%
0,0%
0,0%
2,3%
24,2%
0,0%
10,7%
GAP
GraspINS1
T (s)
863
280
202
1102
1026
1043
1164
1142
1061
1021
666
777
930
909
902
918
985
M2L2
571
639
656
693
760
1670
866
894
822
681
714
847
740
796
1
1
1
1
1
3
1
1
1
1
242
44
317
263
20000
795
20000
45
6
1006
741
9815
20000
8768
20000
1560
4775
18342
20000
66
20000
T (s)
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
2,8%
0,0%
1,5%
0,0%
0,0%
0,0%
0,0%
0,0%
6,2%
0,0%
10,5%
0,0%
0,0%
0,0%
14,2%
0,0%
10,0%
276
202
1166
1100
1061
1136
1026
1043
1022
666
777
930
909
902
921
985
863
M2L3
571
639
656
693
760
1670
866
894
822
681
714
847
740
796
GraspINS2
GAP
1
1
1
1
8
1
1
1
24
4
114
52
299
194
20000
326
20000
37
6
1311
688
5180
20000
18593
13268
1663
4119
20000
20000
51
20000
T (s)
37
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
0,0%
2,2%
0,0%
4,5%
0,0%
0,0%
0,0%
0,0%
0,0%
6,4%
0,0%
0,0%
0,0%
0,0%
1,0%
13,3%
0,0%
8,7%
GAP
38
3
Caixeiro Alugador com Coleta de
Prêmios
Neste capítulo será apresentado o Problema do Caixeiro Alugador com Coleta de
Prêmios ou
Prize Collecting Traveling Car Renter Problem, objeto de análise do presente
estudo. Inicialmente será feita uma contextualização do problema, na qual é efetuada uma
breve revisão de problemas de roteamento de veículos com coleta de bônus e problemas
relacionados ao setor turístico. Em seguida, será apresentado o problema
pCaRS
com
uma descrição do mesmo, seguida de sua formulação matemática, informações sobre a
geração do banco de instâncias e, nalmente, a implementação e análise dos resultados
do modelo exato proposto no solver GLPK.
3.1 Problemas de Roteamento com Coleta de Bônus
Nesta seção serão apresentados alguns problemas de otimização combinatória envolvendo a coleta de bônus e a otimização de rotas, que possuem características similares ao
problema ora proposto.
O Problema do Caixeiro Viajante com Bônus é uma generalização do caixeiro viajante
em que não se exige que todos os vértices do grafo sejam visitados pelo ciclo hamiltoniano
do caixeiro (FEILLET;
DEJAX; GENDREAU,
2005). Um bônus é associado a cada um dos
vértices do problema. O objetivo geral é a otimização simultânea do bônus recolhido no
ciclo e dos custos de viagem.
Seja
G = (V, A)
conjunto de vértices e
não-negativo
cada arco
Si
aij .
um grafo completo e não orientado, onde
V := {v1 , ..., vN }
é o
A = {(vi , vj ) : vi , vj ∈ V, i < j} é o conjunto de arestas. Um prêmio
é associado a cada vértice
O vértice
v1
vi ∈ V
e o custo de viagem
pode ser interpretado como o depósito. O
consiste em determinar um ciclo Hamiltoniano
0
cij
é associado a
P CV
com bônus
0
G ⊂ G sobre o conjunto V ⊆ V , de forma
que cada vértice seja visitado, no máximo, uma vez, de forma a minimizar os custos de
39
viagem, atendendo as restrições de coleta de bônus.
De acordo com (JOZEFOWIEZ
et al.,
2007), três problemas de caixeiro viajante com
coleta de bônus genéricos podem ser denidos, dependendo da forma como os objetivos
são colocados.
1. Ambos os objetivos são combinados na função objetivo. Nesse caso, o objetivo é
encontrar uma rota que minimiza os custos de viagem, na qual são subtraídos os
bônus recolhidos. Este problema é conhecido como
foi proposto por (AMICO;
MAFFIOLI; VäRBRAND,
Protable tour problem
(PTP) e
1995).
2. Os custos da rota são alocados como restrição do problema. O objetivo é encontar
uma rota que maximize o total de bônus recolhido, desde que não exceda um valor
pré-determinado
Problem
cmax .
(OP) (CHAO;
Este problema é usualmente conhecido como
GOLDEN; WASIL,
Orienteering
1996).
3. A coleta de bônus é alocada como restrição no prolema, e o objetivo passa a ser
encontrar a rota de menor custo, desde que o bônus recolhido não seja menor do
que um valor pré-denido. Este problema é conhecido por
Salesman Problem
prize-collecting Traveling
(PCTSP), e foi proposto por (BALAS, 1989).
No caso em que as penalidades tem valor nulo, o problema é conhecido por
Quota
TSP.
3.1.1 Protable tour problem
O problema
Protable tour problem(PTP)
(AMICO;
MAFFIOLI; VäRBRAND,
1995),
consiste em determinar uma rota através de um ciclo hamiltoniano, que minimiza os
custos de viagem onde são subtraídos os bônus recolhidos.
Uma formulação matemática para o problema denida de acordo com (FEILLET;
JAX; GENDREAU,
2001), é apresentada a seguir:
DE-
40
X
min
X
X
cij xij −
pi y i
(3.1)
xij = yi (vi ∈ V )
(3.2)
xij = yj (vj ∈ V )
(3.3)
y1 = 1
(3.4)
xij ≤ |S| − 1(S ⊂ V )
(3.5)
xij ∈ 0, 1; ∀i, j = 1, ..., N
(3.6)
yi ∈ 0, 1; ∀i = 1, ..., N
(3.7)
Vi ∈V vj ∈V \{vi }
X
sujeito a:
Vi ∈V
vj ∈V vi
X
vi ∈V vj
X X
vi ∈S vj ∈S vi
O problema PTP é NP-Difícil (FISCHETTI;
TOTH,
1988). Além disso, outras opções
de restrição de eliminação de sub-ciclos, além de 3.5 podem ser utilizadas no problema
(FEILLET;
DEJAX; GENDREAU,
2005). Nesse mesmo estudo, o autor apresenta as heurísti-
cas de maior utilização na literatura, ressaltando a dicudade de aplicá-las em conjunto
e de forma eciente.
Para denir a formulação do problema
Quota TSP,
(FEILLET;
DEJAX; GENDREAU,
2001) considera a substituição da função objetivo por:
min
X
X
cij xij
Vi ∈V vj ∈V \{vi }
e a inserção da restrição:
X
pi yi ≥ pmin
Vi ∈V
onde
pmin
é o bônus mínimo a ser coletado.
3.1.2 Orienteering Problem
De maneira geral, o
Orienteering Problem(OP)
(CHAO;
GOLDEN; WASIL,
1996) con-
siste em determinar uma rota através de um ciclo hamiltoniano, de forma que maximize a
coleta de bônus, considerando o tempo máximo disponível como uma limitação imposta
pelo problema.
41
O problema OP pode ser denido da seguinte forma (VANSTEENWEGEN;
OUDHEUSDEN,
{v1 , ..., vN }
2011): Seja
G = (V, A)
de arestas. Um prêmio não-negativo
viagem
tij
circuito Hamiltoniano
saída
(v1 )
Si
é associado a cada aresta
0
G ⊂G
um grafo completo e não orientado, onde
A = {(vi , vj ) : vi , vj ∈ V, i < j}
é o conjunto de vértices e
é associado a cada vértice
aij .
(vN ),
vi ∈ V
é o conjunto
e o tempo de
V,
incluindo a denição de um vértice de
de forma a maximizar o prêmio total coletado,
não excedendo o tempo máximo disponível
Tmax .
Esse problema pode ser denido como um caminho, no qual o vértice inicial
difere do vértice nal
(vN ),
V =
O problema OP consiste em determinar um
sobre o conjunto
e um vértice de chegada
SOUFFRIAU;
(v1 )
bem como também pode ser denido como tendo o vértice
nal coincidente com o vértice de saída, originando assim um caminho fechado.
Considerando a notação denida acima, e ainda que a variável de decisão
indica que o vértice
ui
xij = 1
i foi visitado após o vértice j , e xij = 0 caso contrário e que a variável
indica a posição do vértice
i
no caminho, então a formulação matemática para o OP é
denida de acordo com (VANSTEENWEGEN;
SOUFFRIAU; OUDHEUSDEN,
2011), conforme
apresentado a seguir:
max
N
−1 X
N
X
Si xij
(3.8)
xiN = 1
(3.9)
xkj ≤ 1 ∀k = 2, ..., N − 1
(3.10)
i=2 j=2
N
X
x1j =
j=2
N
−1
X
i=1
xik =
N
X
N
−1
X
i=1
j=2
N
−1 X
N
X
tij xij ≤ Tmax
(3.11)
∀i = 2, ..., N
(3.12)
ui − uj + 1 ≤ (N − 1)(1 − xij );
∀i, j = 2, ..., N
(3.13)
xij ∈ 0, 1;
∀i, j = 1, ..., N
(3.14)
i=1 j=2
2 ≤ ui ≤ N ;
O problema OP é NP-Difícil (GOLDEN; LEVY; VOHRA, 1987). Além disso, (GENDREAU;
LAPORTE; SEMET,
1998) apontam algumas razões que dicultam a criação de boas heu-
rísticas para o OP: o bônus associado a um vértice e o tempo para alcançar este vértice
são independentes e muitas vezes contraditórios entre si. Isto torna muito difícil selecio-
42
nar os vértices que irão fazer parte da solução ótima. Portanto, a construção simples de
soluções e a aplicação de heurísticas de melhoria podem direcionar o algoritmo a direções
pouco vantajosas, no sentido de não explorar ecazmente a solução no espaço de decisões
e efetuar buscas em um espaço pouco promissor.
3.1.3 Prize Collection Traveling Salesman Problem(PC- TSP)
O problema
prize-collecting TSP
(PCTSP) foi proposto por (BALAS, 1989), e consiste
em determinar uma rota através de um ciclo hamiltoniano, onde a coleta de bônus é
alocada como restrição no problema, que tem como objetivo encontrar a rota de menor
custo, desde que o bônus recolhido não seja menor do que um valor pré-denido.
Para denir a formulação do PCTSP, considere o seguinte: Seja
completo e não orientado, onde
vi , vj ∈ V, i < j}
é o conjunto de arestas. Seja
e zero caso contrário,
e outra em
V \S
e seja
πi
o conjunto de vértices e
yi = 1
xe = 1 caso a aresta e ∈ V
cada subconjunto de vértices
S
V := {v1 , ..., vN } é
G = (V, A)
caso o vértice
i∈V
um grafo
A = {(vi , vj ) :
pertença a rota
esteja no tour e zero caso contrário. Para
S , seja δ(S) o conjunto de arestas com uma extremidade em
uma penalidade associada ao vértice
i.
Uma formulação matemática para o problema, denida de acordo com (BIENSTOCK
et al.,
1993), é apresentada a seguir:
min
X
ce x e +
e∈A
sujeito a:
X
πi (1 − yi )
(3.15)
∀i ∈ V
(3.16)
i∈V
X
xe = 2yi
e∈δ(i)
X
xe ≥ 2yi
∀i ∈ V, S ⊂ V,
|S ∩ i, j| = 1
(3.17)
y1 = 1
(3.18)
∀i, j = 1, ..., N
(3.19)
∀i = 1, ..., N
(3.20)
tal que
e∈δ(S)
xe ∈ 0, 1;
yi ∈ 0, 1;
O problema PCTSP é NP-Difícil (FISCHETTI;
TOTH,
1988). Além disso, outras opções
de restrição de eliminação de sub-rotas podem ser utilizadas no problema de acordo com
(FEILLET;
DEJAX; GENDREAU,
2005). Nesse mesmo estudo, o autor apresenta as heurísti-
cas de maior utilização na literatura, ressaltando a dicudade de aplicá-las em conjunto
e de forma eciente.
43
3.2 Trabalhos Relacionados ao Setor Turístico
Os problemas acima mencionados possuem várias aplicações práticas. Por exemplo,
uma aplicação para o problema OP citada por (TSILIGIRIDES, 1984) é o caso em que o
caixeiro não dispõe de tempo suciente para visitar todas as cidades.
Recentemente, algumas aplicações associadas aos problemas acima e voltadas ao turismo estão sendo exploradas, denominadas de
(VANSTEENWEGEN;
D.,
Um exemplo é o
Tourist Trip Design Problems (TTDP)
2007).
Mobile Tourist Guide
(SOUFFRIAU
et al.,
2008), onde os turistas
que visitam uma região não têm disponibilidade de visitar todos os pontos em que estão
interessados em um período de tempo restrito, e por isso devem selecionar as atrações
que estão mais interessados em visitar. Uma aplicação similar modelada de forma multiobjetivo é denida em (SCHILDE
et al.,
2009), onde os pontos de interesse de visita (POI)
são agrupados de acordo com categorias, a partir das quais os turistas devem escolher as
que possuem maior interesse em visitar.
O trabalho de (VANSTEENWEGEN
et al.,
2011) também enfatiza a linha de aplicações
voltadas ao turismo, com a criação de rotas personalizadas em um aplicativo que leva em
consideração os interesses e as restrições de viagem do usuário e os combina em uma base
de dados de localização dos pontos de interesse, a m de prever os interesses pessoais de
visitas. O trabalho de (GARCIA
et al.,
2013) inclui a informação referente ao transporte
público no contexto das visitas aos pontos de interesse.
Contudo, também existe a possibilidade de que o trajeto seja realizado em veículos
alugados, conforme explicitado em (GOLDBARG;
ASCONAVIETA; GOLDBARG,
2012), onde
um cliente pretende utilizar carros alugados para visitar um determinado conjunto de
cidades, minimizando o custo relacionado ao aluguel de carros e ao percurso. Existem
várias opções de veículos de empresas diferentes, disponíveis em cada cidade. Essa multiplicidade de opções abre uma variedade de possibilidades de escolha para o utilizador
sobre os carros mais atraentes para viajar diferentes partes do percurso pretendido. No
caso do turismo, os clientes costumam começar e terminar sua turnê, na mesma cidade.
Para tomar a decisão sobre qual carro deve alugar em cada parte do percurso, o cliente
deve considerar, além do custo de locação de cada carro disponível, os custos relacionados
ao consumo de combustível e pagamento de taxas. Se um carro é alugado em uma cidade e
entregue em uma diferente, o usuário deve considerar também uma taxa extra para levar
o carro de volta a sua origem.
44
As empresas de aluguel de veículos operam geralmente seguindo uma hierarquia simples considerando pólos regionais e distritos de atendimento (FINK;
REINERS,
2006). Usu-
almente as empresas de aluguel de carros utilizam cerca de quinze grupos de carros, onde
cada grupo contém carros de marcas diferentes, mas com tipologia equivalente (por exemplo, nível de equipamentos, conforto etc), onde a diferença de cada grupo é reetida no
custo do aluguel.
Uma revisão sobre problemas de roteamento aplicados à indústria de locação de veículos é apresentada em (YANG;
JIN; HAO,
2008). Um dos principais problemas da indústria
de aluguel de veículos diz respeito à manutenção do estoque, pois carros são locados e
devolvidos em diferentes estações de aluguel, o que exige o constante reabastecimento do
estoque, seja pela devolução do veículo alugado, seja por outro de características similares.
(GEORGE;
XIA,
2011) argumenta que sistemas onde o aluguel e a devolução de veículos
ocorrem em pontos distintos estão em utilização prática em vários locais. Nesses sistemas,
o consumidor chega na estação de aluguel, utiliza o veículo por algum tempo e depois
devolve o veículo em uma estação credenciada de sua escolha, que não é necessariamente
a estação em que ele alugou o veículo. Sugere-se que para as estações com baixa utilização
relativa, deve-se dividir ou redirecionar sua demanda com as estações próximas. Dessa
forma, o retorno do veículo a essas estações pode ser estimulado através de incentivos
dados aos clientes através de descontos nos preços de aluguel, enquanto nas estações
com alta utilização relativa, que recebem veículos de várias estações, poderiam ter seu
recebimento de veículos diminuído, oferecendo incentivos para que os clientes devolvam
os veículos em outras estações que têm utilização relativa inferior.
3.3 Descrição do Problema
É uma situação muito comum o caso em que um turista não pode visitar todas as
atrações existentes durante uma viagem, devendo escolher as que possuam maior interesse. Nesses casos, é interessante tentar maximizar a satisfação visitando os pontos mais
atraentes.
Esse tipo de abordagem foi utilizado em vários estudos, a exemplo do
Mobile Tourist
Guide, apresentado por (SOUFFRIAU et al., 2008), projetado para turistas que não podem
visitar todos os lugares que estão interessados em uma grande cidade. Essa abordagem
também foi mencionada como uma aplicação do
1984).
Orienteering Problem por (TSILIGIRIDES,
45
O Problema pCaRS é uma variante do CaRS que, assim como no PCTSP, um bônus
é associado a cada cidade. Esse bônus dene um nível de satisfação em visitar a cidade
associada e uma satisfação cumulativa pré-denida mínima deve ser atendida.
Além disso, um vértice é escolhido para ser a cidade onde o passeio começa e termina,
denominada cidade base. O objetivo é selecionar um subconjunto de cidades (vértices) a
serem visitadas, visando a minimização do custo total da viagem, incluindo o aluguel dos
veículos e que a satisfação mínima de visitar as cidades, representada pelo parâmetro
ω
seja atendida.
Nesse contexto, o problema pCaRS possui características similiares ao problema CaRS,
no que diz respeito a todas as suas características, exceto no que diz respeito a necessidade de visita de todas as cidades do grafo e na inclusão do parâmetro de satisfação em
visitar determinada cidade. No caso especíco do problema pCaRS, deve-se escolher entre as cidades que minimizem os custos referentes aos custos de percurso, e também que
carros devem ser utilizados em cada trecho escolhido, de forma a minimizar também os
custos referentes ao aluguel e devolução de veículos. A satisfação mínima é um parâmetro
pré-estabelecido no problema e que deve ser obedecido.
Figura 3: Custos Operacionais e Taxas de Retorno para os carros 1, 2 e 3 - pCaRS
46
Figura 4: Rotas com Custos de Tráfego e Retorno para cada Carro - pCaRS
A Figura 3 exemplica, em um grafo completo de cinco vértices, uma típica instância
do pCaRS. No exemplo existem três diferentes carros disponíveis para aluguel, que estão
disponíveis para serem alugados e entregues em todas as cidades do grafo. Os custos
apresentados também exibem a contabilidade dos custos envolvidos no deslocamento de
cada tipo de carro. Observe que a solução do pCaRS depende da cidade escolhida para o
início do tour, cidade base, onde a taxa de retorno pode estar vinculada tanto à cidade
que inicia o ciclo, quanto ao próprio sentido de percurso desse ciclo. No exemplo essa
cidade é representada pelo vértice A.
Nesse exemplo, ilustrado na Figura 4 temos:
(a) a cidade A é tomada como cidade-
base, onde é locado o carro 2, que segue para a cidade B, a partir de onde é devolvido.
O custo de percorrer o trecho AB é de 1, e a taxa de devolução do carro 1 da cidade B
para a cidade A é de custo 1. A satisfação acumulada é de 81 + 68 = 149.
(b) Na cidade
B é locado o carro 3, que faz o percurso até a cidade D, e depois segue para a cidade E,
tendo um custo de percurso correspondente a soma do peso das arestas 2 + 2 = 4. Na
cidade E é efetuada a devolução do veículo para a cidade em que foi locado, cidade B,
pagando para isso a taxa de retorno equivalente a 3. A satisfação de visitar as cidades
nesse trajeto é de 73 + 27 = 100.
(c) Finalmente é locado o carro 1 na cidade E que parte
para cidade A, com um custo de percurso igual a 2, voltando a cidade base e concluindo
o percurso. O carro 1 é devolvido da cidade A para a cidade E a um custo de 2.
(d) Os
custos totais são os equivalentes ao percurso (1 + 2 +2 = 5) somados aos de retorno dos
veículos utilizados (1 + 3 + 2 = 6), perfazendo um custo total igual a 11. A satisfação
acumulada é dada pelo somatório correspondente as cidades visitadas ( 81 + 68 +73 +
27 = 249). Observe que a cidade C não foi visitada, não tendo seus custos considerados
na solução.
47
3.4 Formulação Matemática
Problemas de Programação Linear (PL) são problemas de otimização nos quais a função objetivo e as restrições são todas lineares. A PL é uma importante área da otimização
na qual são expressos muitos problemas práticos em pesquisa operacional (GOLDBARG;
LUNA,
2005).
Com a nalidade de encontar soluções exatas para instâncias do problema pCaRS,
foi desenvolvida uma formulação matemática, com função objetivo linear e com tipologia
inteira mista.
Seja
e
A
G = (V, A)
um grafo completo, onde
V
é um conjunto com n nós (cidades)
é um conjunto de arcos (estradas entre as cidades). Um bônus
atribuído a cada cidade
i ∈ V . Nesse problema, um conjunto C
SV i, i = 1, ..., n
é
de veículos está disponível
para aluguel. Custos operacionais especícos estão associados a cada carro, incluindo o
consumo de combustível, pagamento de pedágio e custos de aluguel. Uma vez que as taxas
de pedágio normalmente dependem do tipo de veículo e do comprimento do caminho
percorrido, é possível assumir, sem perda de generalidade, que o custo operacional de
cada carro para atravessar a aresta
(i, j) ∈ A
Os custos operacionais associados ao carro
por
é uma função daquele carro.
c para cruzar a aresta (i, j) ∈ A é denotado
dcij . O vértice 1 foi escolhido como o ponto de partida e nal do trajeto a ser realizado,
sendo denido como cidade base. Considere um carro
cidade
c alugado na cidade i e entregue na
j . Caso i 6= j , existe uma taxa a ser paga para retornar o carro c para a cidade i. A
formulação matemática considera as seguintes variáveis binárias:
carro
1
c trafega pela aresta (i, j), partindo de i até j
quando o carro
carro
c
variável
c
é locado na cidade
é alugado na cidade
c
wij
i; eci
i
com valor
ω
com valor
1
quando o carro
que é dado por
c
i
1
com valor
quando o
é entregue na cidade
i.
A
i e entregue na cidade j . A formulação
P
0, 8 × ST , onde ST = i∈V SVi , é o
somatório da satisfação de visitar todas as cidades, e a variável inteira
posição do vértice
1 quando o
c
0 caso contrário; wij
c
e entregue na cidade i; ai com valor
indica que um carro foi locado na cidade
também considera o parâmetro
e valor
fijc
no percurso.
Dessa forma, o modelo proposto para o pCARs é o seguinte:
ui
que retorna a
48
min
XX
c∈C
sujeito a:
dcij · fijc +
XX
ij
k
XX
c
f1j
=
c∈C j∈V
c
=
fih
eci =
c0 ∈Cc0 6=c
j∈V
fjic
∀h ∈ V
(3.23)
!
c0
fih
∀c ∈ C, i ∈ V, i > 1
(3.24)
∀c ∈ C, i ∈ V, i > 1
(3.25)
h∈V
!
X
c
≤1
fhj
c∈C j∈V
X X
j∈V
(3.22)
XX
!
fijc
fi1c = 1
c∈C i∈V
c∈C i∈V
aci =
(3.21)
ij
XX
XX
X
c
γijc · wij
!
X X
0
c
fhi
c0 ∈Cc0 6=c h∈V
c
= aci
wij
· eci
∀c ∈ C, i ∈ V, j ∈ V
X
(3.26)
ac1 = 1
(3.27)
c∈C
X
aci ≤ 1
∀c ∈ C
(3.28)
X
∀c ∈ C
(3.29)
c∈C
X
aci =
i∈V
eci
i∈V
!
X
XX
i∈V
c∈C j∈V
fijc
2 ≤ ui ≤ N
X
ui − uj + 1 ≤ (N − 1)(1 −
fijc )
!
sVi
≥ω
(3.30)
∀i = 2, ..., N
(3.31)
∀i, j = 2, ..., N
(3.32)
c
fijc , wij
, aci , eci ∈ [0, 1]
(3.33)
ui ∈ N
(3.34)
c∈C
A função objetivo é apresentada em (3.21). Ela inclui o custo de percorrer as rotas com
diferentes carros e taxas referentes a devolução dos mesmos. A restrição (3.22) garante
que o percurso começa e termina na cidade base, ou seja, o vértice 1. A restrição (3.23)
garante que cada vértice é visitado, no máximo, uma vez e se um carro chega ao vértice
i,
um carro deve deixar esse vértice. A restrição (3.24) associa se um carro é alugado
no nó
i,
e a restrição (3.25) associa se um carro é devolvido no nó
associa se um carro foi locado em uma cidade
i
(3.27) garante que um carro é alugado no nó
i.
A restrição (3.26)
e devolvido em uma cidade
1.
j.
A restrição
A restrição (3.28) assegura que cada
carro seja usado apenas uma vez, e a restrição (3.29) garante que cada carro locado
seja entregue. A restrição (3.30) certica que um nível mínimo de satisfação em visitar
as cidades seja cumprido, previsto para 0,8ST. As restrições (3.31) e (3.32) proíbem a
49
formação de subrotas e foram adaptadas das restrições de Miller-Tucker-Zemlin (MTZ)
para o PCV apresentadas em (MILLER;
(VANSTEENWEGEN;
TUCKER; ZEMLIN,
SOUFFRIAU; OUDHEUSDEN,
1960) e também utilizadas em
2011). A restrição (3.33) declara algumas
variáveis binárias e a restrição (3.34) diz que as variáveis
ui
(3.24), (3.25)
e
Como podemos observar, as restrições
são inteiros positivos.
(3.26)
não são lineares, mas
suas variáveis são binárias. Binary Quadratic Problems (BQP) são problemas do tipo NPdifícil (ELLOUMI;
FAYE; SOUTIF,
2000) e ocorrem quando temos um produto de variáveis
binárias, da forma como se apresentam as restrições acima mencionadas.
Para contornar este problema, foi utilizada a linearização usual previamente denida
nesse trabalho. As restrições foram implementadas no GLPK, conforme sugerido em (BIS-
SCHOP,
2012)
3.5 O Banco de Instâncias pCaRSLIB
Como o problema proposto é novo na literatura, não existe disponível um banco de
instâncias que possa ser utilizado para testes. Dessa forma, foi criada uma biblioteca de
instâncias, denominada pCaRSLib, com o objetivo de aplicar os algoritmos propostos.
Devido à similaridade com o problema CaRS, as instâncias criadas para o pCaRS
foram baseadas nas criadas para o problema original, realizando algumas adaptações referentes às características do novo problema. A biblioteca do CaRS, descrita em (ASCONAVI-
ETA,
2011) está disponível em
http : //www.dimap.uf rn.br/lae/en/projects/CaRS.php,
possuindo as seguintes características: todos os carros podem ser alugados em qualquer
cidade, todos os carros podem ser entregues em qualquer cidade, cada carro pode ser
alugado somente uma vez, a taxa paga para ter um carro de volta para sua cidade de
origem não está associada com a topologia da instância; simétrica, os custos para ir de
para
j
e de
j
para
i
i
são iguais, o grafo é completo e preserva a desigualdade triangular.
As instâncias do problema CaRS são divididas em duas classes: euclidiana e nãoeuclidiana. Três grupos de instâncias foram criados para cada classe. A diferença entre
cada grupo é a forma com que os pesos das arestas foram gerados. Primeiro, um conjunto
principal de pesos de aresta é estabelecido para cada grupo. Os pesos das arestas primárias
foram tomados a partir de mapas reais para o primeiro grupo, gerados uniformemente no
intervalo [10,500] para o segundo grupo e com base em exemplos TSPLIB constantes em
(REINELT, 1991) para o terceiro grupo. Então, o peso de cada aresta correspondente ao
carro
c, 1 ≤ c ≤ |C| foi escolhido aleatoriamente, com probabilidade uniforme, no intervalo
50
[1.1we , 2.0we ],
onde
we
representa o peso primário da aresta
e.
Para o problema pCaRS, efetuamos uma adaptação das instâncias do CaRS, inserindo
os dados referentes à satisfação presumida de visita de cada cidade. As demais informações
permanecem as mesmas já utilizadas e descritas por (ASCONAVIETA, 2011). As adaptações
realizadas foram:
1.
Instâncias Euclidianas: as modicações foram realizadas no espaço de dados que
contém os dados propriamente dito, que compõe as instâncias para o algoritmo de
resolução do problema. O índice de satisfação presumida foi acrescida na secção
N ODE _COORD_SECT ION .
No problema original, essa secção é utilizada para instâncias do tipo euclidianas simétricas. As coordenadas dos vértices do grafo são discriminadas nessa seção, de par
em par. Uma terceira coordenada, que representa o índice de satisfação presumida
de visita da cidade foi inserida. O resultado da distância percorrida é obtida pela
seguinte operação
(sqrt(pow((P [i].x−P [j].x), 2)+pow((P [i].y −P [j].y), 2))). Para o
problema pCaRS, a informação relativa à satisfação presumida foi inserida de forma
explícita. O nível de satisfação atribuído a cada cidade foi gerado uniformemente no
intervalo [0,100].
2.
Instâncias não-Euclidianas: foi inserida uma nova secção, denominada
BON U S _SAT ISF ACT ION _SECT ION , que contém os dados de satisfação presumida de visita anotados de forma explícita em um vetor ordenado da primeira para
a última cidade. A satisfação presumida foi gerada conforme descrito anteriormente.
3.6 Representação de Soluções
Para o problema pCaRS, além da denição da melhor rota a seguir, também é necessário representar a informação de qual foi o carro utilizado para percorrer cada trecho do
percurso. Dessa forma, as soluções do problema são representadas em todos os algoritmos
apresentados neste trabalho em forma de um vetor bidimensional com
n
elementos.
Figura 5: Representação de uma Solução Genérica do problema pCaRS
Observe que a solução é representada por uma matriz de 2 dimensões, conforme
51
ilustrado na Figura 5, onde a rota é representada numa dimensão (superior) e os carros
são representados na outra (inferior). Nessa gura dez cidades são visitadas. Observe que
as cidades 10 e 11 não são visitadas. Esse cromossomo representa uma solução onde o
carro 2 é contratado na cidade base e entregue na 4 cidade, na qual o carro 3 é contratado
e assim por diante.
Assim, as posições da primeira linha dizem respeito à sequência das cidades visitadas
e as posições da segunda linha da solução são anotadas pelos carros que iniciam seu
caminho nas cidades registradas na respectiva coluna da primeira linha. A cidade 1 é
sempre a cidade inicial do percurso e não é representada na solução como destino nal, o
que ca subentendido.
3.6.1 Solução do modelo proposto através do solver GLPK
O modelo proposto foi implementado em um computador com processador Intel Core
i5, 8GB de memória RAM, rodando o sistema operacional Ubuntu 12.04 64bits, e implementado no Solver GLPK versão 4.47. O GLPK (GNU Linear Programming Kit,
http://www.gnu.org/software/glpk/ ) é um solver voltado para a resolução de problemas
de programação linear (LP) e programação inteira mista (MIP). A linguagem utilizada
para modelar o problema foi a
GNU MathProg modeling language, e
o método utilizado
foi o SIMPLEX primal. O problema teve como limitações a memória RAM disponível (14
Gb) e o tempo de processamento máximo de 80000 segundos.
De forma a denir os primeiros limites inferiores para alguns problemas da biblioteca
pCArSLIB, foram realizados testes em 62 pequenas instâncias do problema, sendo 31
euclidianas e 31 não euclidianas.
As Tabelas 3 e 4 apresentam o resultado desse primeiro experimento computacional.
As colunas
Instancia, n
e
|C|
estão relacionadas com as características de cada instância
e são, respectivamente, a identicação do problema, o número de cidades e o número de
carros disponíveis. As colunas
Sol
e
t(s),
estão relacionadas com a solução obtida pelo
solver GLPK, e mostram o valor da melhor solução viável inteira e o tempo de processamento, em segundos. A coluna
GAP
apresenta o desvio percentual do valor apresentado
a partir de um limite global para a solução exata calculada pelo GLPK.
Os resultados apresentados na Tabela 1 mostram que o solver GLPK encontra a
solução ótima para quase todas as instâncias euclidianas, com exceção da China17e, onde
o solver parou devido à limitação de memória e as instâncias Russia17e, BrasilAM26e,
52
BrasilMG30e, onde o solver parou devido à limitação de tempo de processamento. Para
esses casos, o desvio percentual produzido pelo GLPK foi de
28, 60%,
6, 40%, 10, 40%, 20, 50%
e
respectivamente. Observa-se também que, com o aumento do número de cidades
e carros nas instâncias, o tempo gasto pelo
solver
para encontrar a solução também
aumenta.
Os resultados para as instâncias não euclideanas apresentados na Tabela 2 mostram
que o GLPK não teve garantia de ter encontrado a solução ótima em dezoito instâncias
não-euclidianas, para as quais o algoritmo parou devido a limitação de tempo ou de
memória. Os desvios percentuais variam, entre 2% e 37,60%. Observa-se também que
houve uma tendência de maior GAP na medida em que o tamanho da instância aumentou.
53
Tabela 3: Resultados para as instância Euclideanas - GLPK
Instância
n
|C|
Sol
t(s)
GAP
Mauritania10e
10
2
422
5
0,00%
Colombia11e
11
2
326
1
0,00%
Angola12e
12
2
490
8
0,00%
Peru13e
13
2
556
46
0,00%
Libia14e
14
2
521
45
0,00%
BrazilRJ14e
14
2
230
560
0,00%
Congo15e
15
2
513
28
0,00%
Argentina16e
16
2
719
2276
0,00%
EUA17e
17
2
602
71,5
0,00%
Bolivia10e
10
3
384
3
0,00%
AfricaSul11e
11
3
402
11
0,00%
Niger12e
12
3
564
53
0,00%
Mongolia13e
13
3
543
607
0,00%
Indonesia14e
14
3
504
22
0,00%
Argelia15e
15
3
487
351
0,00%
India16e
16
3
705
36
0,00%
China17e
17
3
735
57332
6,40%
Etiopia10e
10
4
283
2
0,00%
Mali11e
11
4
428
10
0,00%
Chade12e
12
4
655
861
0,00%
Ira13e
13
4
532
49
0,00%
Mexico14e
14
4
492
144
0,00%
Sudao15e
15
4
422
46
0,00%
Australia16e
16
4
682
453
0,00%
Canada17e
17
4
783
1599
0,00%
Arabia14e
14
5
482
50
0,00%
Cazaquistao15e
15
5
574
1473
0,00%
Brasil16e
16
5
619
718
0,00%
Russia17e
17
5
760
80000
10,40%
BrasilAM26e
25
3
371
80000
20,50%
BrasilMG30e
26
3
419
80000
28,60%
54
Tabela 4: Resultados para as instância não Euclideanas - GLPK
Instância
Mauritania10n
n
|C|
Sol
t(s)
GAP
10
2
306
1
0,00%
Colombia11n
11
2
461
224
0,00%
Angola12n
12
2
409
50
0,00%
Peru13n
13
2
502
3634
0,00%
Libia14n
14
2
504
77307
0,00%
BrazilRJ14n
14
2
101
58346
0,00%
Congo15n
15
2
573
5747
0,00%
Argentina16n
16
2
647
62007
22,70%
EUA17n
17
2
579
80000
8,10%
Bolivia10n
10
3
448
54
0,00%
AfricaSul11n
11
3
537
7755
0,00%
Niger12n
12
3
607
4069
0,00%
Mongolia13n
13
3
551
80000
2,00%
Indonesia14n
14
3
522
16188
0,00%
Argelia15n
15
3
619
48859
17,30%
India16n
16
3
734
73024
24,90%
China17n
17
3
651
62162
20,10%
Etiopia10n
10
4
403
153
0,00%
Mali11n
11
4
494
262
0,00%
Chade12n
12
4
654
69111
10,40%
Ira13n
13
4
697
54936
20,90%
Mexico14n
14
4
620
61358
18,70%
Sudao15n
15
4
793
80000
29,50%
Australia16n
16
4
551
80000
16,90%
Canada17n
17
4
827
77542
23,80%
Arabia14n
14
5
701
37832
27,80%
Cazaquistao15n
15
5
843
67421
28,80%
Brasil16n
16
5
769
32052
32,50%
Russia17n
17
5
820
52468
37,60%
BrasilAM26n
25
3
107
80000
17,80%
BrasilMG30n
26
3
179
80000
30,20%
55
4
Algoritmos Propostos
Neste trabalho, foram estudadas algumas estratégias aplicadas e adaptadas ao problema pCaRS, selecionando algumas abordagens para a realização de uma análise experimental. Com o objetivo de ter um bom desempenho numérico e computacional, e
buscando encontrar a solução ótima ou aproximada das instâncias do banco inicial do
pCaRS, optou-se pela programação de algoritmos das seguintes metaheurísticas:
1. GRASP (FEO e RESENDE, 1989) + VNS (MLADENOVIC,1995) + Path Relinking
(GLOVER, 1996)
2. Algoritmo Memético (MOSCATO, 1989)
3. Transgenética Computacional (GOLDBARG e GOLDBARG, 2009)
4.1 GRASP + VNS + Path Relinking
4.1.1 GRASP
GRASP é a abreviação da nomenclatura
dure
e proposto por (FEO;
RESENDE,
Greedy Randomized Adaptative Search Proce-
1989) e (FEO;
RESENDE,
1995). Seu diferencial para
outros métodos está na geração da solução inicial, cuja abordagem está referenciada nas
três primeiras iniciais de sua sigla: gulosa
(Greedy), aleatória (Randomized)
e adaptativa
(Adaptive).
Essa metaheurística busca manter um equilíbrio entre ser guloso e aleatório, e envolve
duas fases distintas: a Fase Construtiva, onde busca-se construir boas soluções, utilizandose para isso uma lista de candidatos, listando todos os vizinhos, a partir da qual é gerada a
Lista Restrita de Candidatos - LRC , onde sua composição é formada pelos
vizinhos disponíveis, onde
0 ≤ α ≤ 1.
Valores de
α
melhores
próximos a zero conduzem a soluções
muito próximas aquela obtida pela escolha gulosa, enquanto valores de
conduzem a soluções praticamente aleatórias.
α%
α
próximos a 1
56
A heurística é adaptativa porque os benefícios associados com a escolha de cada
elemento são atualizados em cada iteração da fase de construção, de forma a reetir
as mudanças oriundas da seleção do elemento anterior. O componente probabilístico do
procedimento reside no fato de que cada elemento é selecionado de forma aleatória, a partir
de um subconjunto restrito formado pelos melhores elementos que compõem a LRC.
Na segunda fase aplica-se a Busca Local. Procura-se com ela melhorar as soluções
encontradas, através de um método de exploração da vizinhança. Um algoritmo de busca
local dene uma vizinhança para cada solução, fazendo uma transformação da solução
atual através de uma técnica ou heurística, gerando um conjunto de soluções com características próximas.
De acordo com (RESENDE;
RIBEIRO,
2003), um algoritmo básico com abordagem
GRASP pode ser visto no pseudo-código a seguir:
Algoritmo 1: GRASP genérico para minimização
Entrada: imax - Número de iterações
Saída: x∗ ∈ X - Solução
f∗ ← ∞
para i = 1, ..., imax faça
x←
FaseConstrutiva();
x←
BuscaLocal();
se f (x) < f ∗ então
f ∗ ← f (x)
x∗ ← x
m
m
O valor da melhor solução é armazenada em
f∗
e
imax
dene o número de iterações
GRASP que serão feitas. Cada iteração consiste de uma fase construtiva, seguida de uma
fase de busca local, a partir da solução construtiva do algoritmo. Se a solução resultante da
busca local melhorar a melhor solução encontrada até o momento, a mesma é armazenada
em
x∗ .
A estratégia utilizada pelo GRASP tem sido amplamente utilizada em problemas
relacionados ao roteamento de veículos, a exemplo de (LABADIE;
2011), (SOUFFRIAU
et al.,
et al.,
2007), (MARINAKIS;
2008), (CHAOVALITWONGSE;
MIGDALAS; PARDALOS,
MELECHOVSKý; CALVO,
KIM; PARDALOS,
2005).
2003), (CHAVES
57
4.1.2 Variable Neighborhood Search - VNS
Variable Neighborhood Search
A heurística
(VNS)
foi proposta por (MLADENOVIC,
1995) e consiste na ideia de mudar sistematicamente a vizinhança de busca em duas fases:
primeiramente, na direção de descida para encontrar um ótimo local e depois uma fase de
perturbação para efetuar a busca fora da área de inuência deste mínimo local encontrado.
O método VNS funciona de forma pouco convencional se comparado a outras metaheurísticas (CHAVES
et al.,
2007). Ele explora vizinhanças mais distantes da solução
corrente e concentra a busca em torno de uma nova solução. A solução é atualizada apenas caso um movimento de melhora seja realizado. O método pode incluir também rotinas
de busca local que utilizam diferentes estruturas de vizinhança.
Em (HANSEN;
MLADENOVIC; PéREZ,
2008) é apresentado um editorial destacando as
vantagens do VNS, onde o autor destaca:
1.
Simplicidade: a metaheurística é baseada em um princípio simples e claro, e pode
ser amplamente aplicável.
2.
Coerência: Os princípios da metaheurística devem ser naturalmente aplicáveis em
problemas particulares;
3.
Eciência: a heurística deve ser eciente para o problema, ou seja, fornecer soluções
ótimas ou quase ótimas para todos os casos ou, pelo menos, para as instâncias com
características mais realistas. De preferência, a heurística deve resolver de forma
ótima a maioria dos problemas de testes de
4.
Ecácia:
benchmarks, quando disponíveis.
A heurística deve fornecer soluções ótimas ou próximas do ótimo para
problemas especícos, com um tempo moderado de uso de processamento computacional.
5.
Robustez: A heurística deve ser ecaz e eciente para vários problemas, fornecendo
boas soluções para uma grande variedade de casos, e não ser apenas eciente em
alguns conjuntos especícos e ter um desempenho não tão bom em outros.
6.
Facilidade de Uso: A heurística é bem denida, de fácil entendimento e de fácil
utilização e adaptação. De preferência, ter poucos (ou nenhum) parâmetro.
7.
Inovação:
de preferência, o princípio da metaheurística, ou a eciência e ecácia
de heurísticas derivadas, devem levar a novos tipos de aplicações.
58
8.
Generalidade: a metaheurística deve conduzir a bons resultados para uma grande
variedade de problemas.
9.
Interatividade: a metaheurística deve permitir que o usuário incorporare seus conhecimentos, a m de melhorar o processo de resolução.
10.
Multiplicidade: a metaheurística deve ser capaz de apresentar várias soluções próximas ao ótimo, dentre as quais o usuário pode escolher.
Um algoritmo básico VNS é descrito em (HANSEN; MLADENOVIC, 2001), cuja adaptada
é apresentada a seguir:
Algoritmo 2: VNS genérico para minimização
Inicio
Selecione Vizinhanças
ℵk ,
k = 1, ..., kmax
S ← solInicial()
enquanto não satisfaz critério de parada faça
k←1
enquanto k ≤ kmax faça
S 0 ← buscaLocal(S, ℵk (S))
se f (S 0 ) < f (S) então
S ← S0
k←1
m
k ←k+1
m
m
4.1.3 Path Relinking
O
Path-Relinking
foi proposto de forma pioneira por (GLOVER, 1996) e é uma estra-
tégia de intensicação de soluções, que possui o objetivo de gerar novas soluções a partir
da utilização de trechos de soluções de elite que são inseridos nas soluções do sistema e
assim encontrar soluções de melhor qualidade, que possuam as características relevantes
das soluções de elite.
Para gerar os caminhos, os movimentos são selecionados para apresentar os atributos
que estão presentes na solução de elite, passando-os para a solução atual. O
Path Relinking
pode ser visto como uma estratégia que pretende incorporar atributos de soluções de
59
elevada qualidade, ao favorecer estes atributos nas novas soluções através de movimentos
selecionados.
Seja
xs
xt
a solução de origem e
do cálculo da diferença simétrica
a solução de destino. O procedimento inicia-se através
∆(xs ; xt ) entre as
x
movimentos necessários para atingir
ligando
xs
xt .
e
A melhor solução
x∗
t
a partir de
duas soluções, ou seja, o conjunto dos
xs .
O caminho entre soluções é gerado
nesse caminho é retornada pelo algoritmo.
A estratégia Path Relinking é bastante utilizada como estratégia complementar ao
GRASP, conforme pode ser visto em: (ALVAREZ-VALDES
PRINS,
2007), (SOUFFRIAU
et al.,
dização é vista em (RESENDE;
das do
•
RIBEIRO,
Path-Relinking
2008), (BOUDIA;
LOULY;
2008). Uma revisão sobre os avanços recentes dessa hibri-
RIBEIRO,
2003). Uma aplicação recente do Path-Relinking
ao roteamento de veículos pode ser vista em (SOUFFRIAU
Em (RESENDE;
et al.,
et al.,
2010).
2003), é feita uma revisão das várias alternativas considera-
nas implementações recentes:
periodical relinking: a estratégia de Path-Relinking
não é aplicada sistematica-
mente, e sim periodicamente nas soluções.
•
forward relinking: é aplicado usando a pior solução entre xs e xt como a solução
inicial e a outra como a solução alvo;
•
backward relinking: os papéis de xs e xt são trocados. O procedimento é aplicado
usando o melhor entre
•
xt
como a solução inicial e o outro como a solução alvo;
xs
como a solução inicial e o segundo usando
xt
neste papel;
mixed relinking: explora dois caminhos simultaneamente, sendo o primeira a partir
de
xs
e o outro de
equidistante de
•
e
back and forward relinking: duas trajetórias diferentes são exploradas, o primeiro
com
•
xs
xs
e
xt ,
até que eles se encontram em uma solução intermediária
xt ;
randomized relinking: em vez de selecionar o melhor movimento, seleciona aleatoriamente um entre uma lista de candidatos com os movimentos mais promissores
no caminho que está sendo investigado;
•
truncated relinking: investiga apenas uma parte da trajetória entre xs e xt .
De posse dos comentários acima, foram propostos no presente trabalho quatro algoritmos com abordagem GRASP, sendo o primeiro em sua formulação tradicional + VNS
60
e o segundo hibridizado com VNS e Path-Relinking. Os outros dois algoritmos utilizarão um novo operador de intensicação que será descrito em detalhes posteriormente. Os
algoritmos de abordagem GRASP utilizados no presente trabalho são descritos a seguir.
4.1.4 Algoritmo GRASP + VNS proposto
Nesta seção, é apresentado o algoritmo GRASP hibridizado com VNS, proposto para
a resolução do problema pCaRS. A fase inicial do algoritmo corresponde a fase construtiva
do GRASP. A segunda fase engloba a aplicação de técnicas de busca local com abordagem
VNS nas soluções encontradas.
4.1.4.1 Pseudo-Código do Algoritmo Proposto
O pseudo-código do algoritmo é apresentado a seguir, onde suas partes constitutivas
são explicadas nos itens subsequentes.
Os parâmetros de entrada para o algoritmo são:
nomeInstancia,
que identica o
problema que será executado, imax , que representa o número de iterações que o algoritmo
vai executar, e
α que é o tamanho da Lista Restrita de Candidatos. O conjunto de soluções
encontrados é representado por
X = {x0 , x1 , ..., xn } e a melhor solução encontrada por x∗ .
A função que avalia o custo de cada solução é representada por
f
e
numSol
número de soluções que serão geradas na fase construtiva do algoritmo.
Algoritmo 3: GRASP proposto para o pCaRS
Entrada: nomeInstancia,imax , α
Saída: x∗
leInstancia(nomeInstancia);
f (x∗ ) ← ∞
para i = 1, ..., imax faça
x←
geraSolucaoConstrutiva(α);
x←
buscaMultiOperadores(x);
se f (x) < f (x∗ ) então
f (x∗ ) ← f (x)
x∗ ← x
m
m
∗
retorne(x );
representa o
61
4.1.4.2 Fase Construtiva
A solução inicial é gerada através do procedimento geraSolucaoConstrutiva(α) que
recebe o tamanho da lista restrita de candidatos como parâmetro de entrada.
A cidade inicial escolhida no algoritmo é a cidade base (nó-1). Um carro
aleatoriamente para a primeira cidade. Em seguida, a cidade
k1
é escolhido
i onde o carro k1 será entregue
é também escolhida de forma aleatória.
Um caminho é criado entre as cidades
1
e
i
através da metodologia construtiva do
GRASP, considerando os custos de viagem com o carro
A cidade
i
k1
para montar a LRC.
é a cidade inicial da próxima parte da rota. Em seguida, um novo carro
e uma nova cidade
j
são escolhidos aleatoriamente. Obviamente, a cidade
j
k2
não pode ser
uma cidade visitada anteriormente. Um caminho é construído entre as cidades
i
e
j
com
as cidades não visitadas, utilizando a mesma abordagem.
Caso não existam mais carros disponíveis, utiliza-se o último carro sorteado. O procedimento continua sorteando outra cidade aleatoriamente e construindo o caminho até
que o nível de satisfação seja alcançado, representado por
ω = 0, 8 ∗ ST ,
ou seja, 80% da
satisfação total disponível, quando o ciclo é fechado, considerando a ligação com a cidade
de partida, conforme representado no algoritmo a seguir:
62
Algoritmo 4: Fase Construtiva do GRASP
Entrada: α
Saída: x ∈ X
← N − 1;
cidades_disp
carros_disp
←
←
cid_atual
nCar;
1;
carro_atual
←
sorteiaCarro(carros_disp);
carros_disp
←
removeCarro(carro_atual,carros_disp);
x
←
atualizaSol(cid_atual, carro_atual);
enquanto x.satisf < ω faça
cid_troca
←
sorteiaProxCidade(cidades_disp);
enquanto cid_atual 6= cid_troca E x.satisf < ω faça
LRC
←
montaLRC(cid_atual, carro_atual, cidades_disp,α);
cid_atual
x
←
←
sorteiaCid(LRC);
atualizaSol(cid_atual, carro_atual);
cidades_disp
←
removeCidade(cid_atual,cidades_disp);
m
se carros_disp 6= ∅ então
carro_atual
←
sorteiaCarro(carros_disp);
carros_disp
←
removeCarro(carro_atual,carros_disp);
m
m
retorne(x);
A variável
cid_atual
armazena a cidade que está sendo utilizada na construção da
solução. Após a utilização dessa cidade, a mesma é removida da lista de cidades disponíveis
através da função
A função
removeCidade(cid_atual, cidades_disp).
sorteiaCarro(carros_disp)
retorna um carro sorteado aleatoriamente en-
tre os carros que ainda não foram utilizados na solução, que é atribuído à variável
carro_atual.
Após o sorteio do carro que será utilizado, o mesmo é removido da lista
de carros disponíveis através da função
De posse das variáveis
cid_atual
atual através do procedimento
e
removeCarro(carro_atual, carros_disp).
carro_atual,
as mesmas são inseridas na solução
atualizaSol(cid_atual, carro_atual),
que insere na solu-
ção a cidade atual e o carro utilizado, além de atribuir o índice de satisfação associado a
cidade visitada.
O procedimento
montaLRC(cid_atual, carro_atual, cidades_disp, α) monta a Lista
63
Restrita de Candidatos considerando os custos apenas do percurso para visitar as cidades
restantes e ainda não utilizadas na solução com os custos do carro atual. Após a lista
montada, é efetuado o sorteio da próxima cidade considerando as cidades presentes na
lista.
4.1.4.3 Fase de Busca Local - VNS
Os processos de busca local visam intensicar a procura por um ótimo local, enquanto
a estrutura de diversicação ca por conta da denição de boas regiões de busca resultantes
dos processos evolucionários (KRASNOGOR;
GUSTAFSON,
2004). Este tipo de abordagem
é bastante eciente em problemas de otimização combinatória, do tipo NP-difícil (ONG;
LIM; CHEN,
2010).
O principal desao entre os métodos heurísticos que usam a busca local é denir
uma estratégia eciente para cobrir o espaço de busca, explorando principalmente regiões
promissoras (VANSTEENWEGEN
et al.,
2011).
Vários tipos de busca local aplicadas a problemas envolvento roteamento de veículos
são vistas em (STENGER;
(KE;
ARCHETTI; FENG,
SCHNEIDER; GOEKE,
2008), (CHAO;
2013), (VANSTEENWEGEN
GOLDEN; WASIL,
avanços é vista em (VANSTEENWEGEN;
et al.,
2009),
1996), e uma revisão dos últimos
SOUFFRIAU; OUDHEUSDEN,
2011).
No caso do problema pCaRS, existem três áreas onde a busca local pode atuar: a
melhor rota,a ordem de uso dos carros e o nível de satisfação. A fase de busca local
do algoritmo proposto visa lidar com estas três áreas, a m de melhorar os candidatos
a solução. A busca local é implantada no procedimento
buscaM ultiOperadores()
e é
composta pelos seguintes métodos:
(a)
removeCidade:
Este método está relacionado ao nível de satisfação. Consiste em
remover da solução as cidades com os menores índices de satisfação, enquanto a restrição referente à satisfação mínima é atendida. A cidade base não é considerada para
remoção.
64
Algoritmo 5: Busca Local: removeCidade()
Entrada: x
Saída: x
(x) ← x
enquanto x.satisf < ω faça
se f (x) < f (x) então
x←x
m
x ← removeM enorSatisf (x)
m
retorne(x);
Considere um problema com o vetor de satisfação : [20 70 30 75 33 27 13 92] cuja
soma total é
288.
ST = 360,
e a satisfação atendida deve ser, no mínimo
0, 8 × ST =
A satisfação de visitar cada cidade está representada acima da solução. Agora
considere uma solução com um vetor de satisfação [20 70 92 33 27 13 75] na qual temos
uma satisfação acumulada de 330. Remove-se a cidade que possui a menor satisfação
associada (13) e a satisfação acumulada assume o valor de 317, que ainda é maior
do que o mínimo exigido. Em seguida, remove-se outra cidade, com satisfação (27),
e a satisfação acumulada é de 290, ainda acima do mínimo requerido. Finalmente,
ao tentar excluir a cidade 5 da solução, o índice de satisfação mínimo é violado,
terminando a aplicação do procedimento.
Figura 6: Exemplo de aplicaçãoção da busca removeCid()
65
(b)
InverteSol: Este método inverte a ordem de visita das cidades na solução. Os mesmos
carros estão associados com as mesmas cidades, mas os pontos de aluguel e entrega
são trocados.
Algoritmo 6: Busca Local: InverteSol()
Entrada: x
Saída: x
x←x
para i ← 1 até x.nCid ÷ 2 faça
x.cid[i + 1] ← x.cid[nCid − i + 1]
m
se f (x) < f (x) então
x←x
m
retorne(x);
Por exemplo, considere a rota
tratado na cidade
na cidade
o carro
1
(1, 2, 3, 4, 5) em cinco cidades com um carro sendo con-
1 e sendo devolvido em 3 e o carro 2 alugado na cidade 3 e entregue
1. Após a aplicação do método InverteSol, a rota torna-se (1, 5, 4, 3, 2), com
sendo contratado na cidade
contratado na cidade
4
1
e entregue na cidade
e sendo entregue na cidade
4
e o carro
2
sendo
1.
Figura 7: Exemplo de aplicação da busca inverteSol()
(c)
substituiCarro: Este procedimento concentra-se em veículos que não estão ainda na
solução, examinando a inserção de um novo carro, se possível. O novo carro substitui
outro na solução. Todos os carros que não fazem parte da solução de entrada são
considerados. O carro que não está na solução é inserido em cada posição de forma
iterativa.
66
Algoritmo 7: Busca Local: substituiCarro()
Entrada: x
Saída: x
listaCAR
←
montaListaCarrosDisp(x);
para k ← 1 até #listaCAR faça
para i ← 0 até x.nCid faça
x←x
para j ← i até x.nCid faça
x.car[j] ← listaCAR[k];
x ← reparaCar(x)
se f (x) < f (x) então
x←x
m
m
m
m
retorne(x);
Por exemplo, suponha que uma instância onde os carros 1, 2, 3 e 4 podem ser alugados. Considere-se uma solução com cinco cidades representadas pelo
tour
(1,2,3,4,5)
com carros 2, 3 e 4, sendo contratados (entregue), respectivamente, nas cidades 1,3,5
(3,5,1). O vetor de atribuição de carros para as cidades é representado como (2,2,3,3,4).
O carro 1 não é usado nesta solução. Em seguida, o procedimento
substituiCarro()
examina as possibilidades de inserção do carro 1 na mesma. Primeiro o carro 1 é
inserido na posição 1 produzindo a sequência de carros (1,2,3,3,4), então é inserido o
carro 1 nas posições 2, 3, 4 e 5 que produzem, respectivamente, (1,1,3,3,4), (1,1,1,3,4),
(1,1,1,1,4), (1,1,1,1,1). No passo seguinte, o carro 1 substitui o segundo carro na
seqüência original do carro, produzindo (2,1,3,3,4). A substituição continua a partir
desse ponto, produzindo (2,1,1,3,4), (2,1,1,1,4) e (2,1,1,1,1). Em seguida, a terceira
posição na sequência original é denida como 1 e o processo continua até que todas
as possibilidades sejam examinadas.
67
Figura 8: Exemplo de aplicação da busca substituiCarro()
(d)
substituiCidade: Esse procedimento atua sobre as cidades que ainda não estão na
solução. Ele examina a substituição de cidades na solução por cidades que não estão
presentes na solução. Todas as cidades da solução de entrada são consideradas para
a inserção.
68
Algoritmo 8: Busca Local: substituiCidade()
Entrada: x
Saída: x
listaCID
←
montaListaCidadesDisp(x);
para i = 0 ate #listaCID faça
para j = 2 ate x.nCid faça
x←x
x.cid[j] ← listaCID[i];
x ← reparaSatisf (x)
se f (x) < f (x) então
x←x
m
m
m
retorne(x);
Por exemplo, considere a rota [1 3 4 5 6]. A cidade 2 não está nesta rota. Em seguida,
o procedimento examina as seguintes rotas: [1 2 4 5 6], [1 3 2 5 6], [1 3 4 2 6] e [1 3 4
5 2]. O vetor de carros associados com a rota de entrada não é alterado.
Figura 9: Exemplo de aplicação da busca substituiCidade()
(e)
insereCidade: Esse procedimento também foca em cidades que ainda não estão na
solução de entrada. Insere uma nova cidade na turnê e não remove nenhuma cidade. O
carro atribuído à nova cidade é o mesmo da cidade imediatamente anterior. A inserção
de uma nova cidade é testada entre cada par de cidades da solução de entrada. Todas
as cidades fora da solução de entrada são consideradas para a inserção.
69
Algoritmo 9: Busca Local: insereCidade()
Entrada: x
Saída: x
listaCID
←
montaListaCidadesDisp(x);
para i ← 0 até #listaCAR faça
para j ← 1 até x.nCid faça
x←x
x ← insereCidadeApos(i, x);
se f (x) < f (x) então
x←x
m
m
m
retorne(x);
Por exemplo, considere novamente a turnê [1 3 4 5 6] e a inserção da cidade 2. Em
seguida, o procedimento examina as seguintes rotas: [1 2 3 4 5 6], [1 3 2 4 5 6], [1 3 4
2 5 6], [1 3 4 5 2 6] e [1 3 4 5 6 2].
Figura 10: Exemplo de aplicação da busca insereCidade()
(f )
2-opt: é um algoritmo de busca local simples proposto por (CROES, 1958) para o Problema do Caixeiro Viajante. Um movimento 2-opt consiste em eliminar duas arestas
e religar os dois caminhos, resultando em uma maneira diferente de obter uma nova
rota. Entre todos os pares de arestas cuja troca 2-opt atua, a que resultar no menor
custo de rota é escolhido. Este procedimento é então iterado até que o par de arestas
mais econômico seja encontrado. A rota resultante é chamada de 2-ótima. Nesse caso,
a sequência de carros associados permanece a mesma.
70
Essas buscas locais são aplicadas em seqüência no procedimento
buscaM ultiOperadores(),
conforme ilustrado na gura a seguir.
Algoritmo 10: Busca Local: buscaMultiOperadores
Entrada: x
Saída: xk ∈ N (x)
x←
removeCidade(x);
x←
inverteSol (x);
x←
insereCidade(x);
x←
substituiCidade(x);
x←
substituiCarro(x);
x←
2Opt(x);
retorne(x);
A cada aplicação de procedimentos constantes na busca local, a solução
x é atualizada
com o melhor valor encontrado no procedimento. Dessa forma, se a solução de entrada é
melhorada durante a aplicação de um procedimento da fase de busca local, então a nova
solução substitui a antiga. Ao nal do procedimento de busca local é retornada a melhor
solução da vizinhança da solução de entrada
x.
4.1.4.4 Procedimentos de restauração de soluções
Pode ser necessário restaurar a viabilidade de soluções geradas durante a aplicação de
alguns procedimentos. A inviabilidade pode ocorrer sobre rotas, atribuição de carros ou
de satisfação total. Por exemplo, imediatamente depois de ter sido gerado uma solução, a
mesma tem uma solução inviável devido ao percurso e atribuição de veículos. Inviabilidade
em relação às cidades da rota ocorre devido às cidades aparecerem mais de uma vez na
solução. Inviabilidade em relação à atribuição de carros ocorre devido a repetição de
aluguel de um mesmo veículo.
O procedimento de recuperação de rota e de aluguel de veículos adotado neste trabalho
é o mesmo apresentado em (GOLDBARG;
ASCONAVIETA; GOLDBARG,
2012).
Para restaurar a viabilidade sobre as cidades da rota, cada cidade que aparece pela
segunda vez na solução é substituída por um asterisco. Por exemplo, a sequência de cidades
[1 3 7 6 4 3 7 9] é substituída por [1 3 7 4 6 * * 9].
Cada asterisco é substituído por uma cidade diferente, escolhida aleatoriamente entre
aquelas que não fazem parte da solução. A atribuição de carros na solução, [2 2 2 3 2 3 3
71
3], também não é viável, pois o problema considerado neste trabalho exige que cada carro
seja alugado no máximo uma vez.
O processo de restauração substitui repetições do carro por asteriscos. Em seguida,
cada asterisco é substituído pelo carro que aparece na primeira posição anterior. Assim,
a atribuição de carro na solução é substituído por [2 2 2 3 ****] e cada um asterisco é
substituído pelo carro 3 (conforme destacado em laranja).
Figura 11: Exemplo de aplicação do procedimento de restauração()
Se depois de restaurado nos procedimentos anteriormente mencionados, uma solução
não atender ao requisito mínimo de satisfação acumulada, um procedimento para restaurar a satisfação é executado. Em primeiro lugar, as cidades com baixo grau de satisfação
são substituídas por outras com melhores níveis de satisfação. Se o nível mínimo de satisfação ainda não for atingido, então cidades são adicionadas aleatoriamente na solução
até atingir a satisfação do mínimo requerido. O carro atribuído a cada nova cidade é o
mesmo atribuído a uma cidade imediatamente anterior a ele.
4.1.5 Algoritmo GRASP + VNS + Path Relinking proposto
O procedimento de
Path Relinking
é bastante utilizado em conjunto com a metaheu-
rística GRASP, como estratégia de intensicação de soluções (RESENDE;
Duas estratégias básicas de utilização do
•
O
Path Relinking
Path-Relinking
RIBEIRO,
2003).
são:
é aplicado a todos os pares de soluções elite, ou periodicamente,
durante as iterações do GRASP, ou após todas as iterações GRASP em uma etapa
de pós-otimização; e
72
•
O procedimento é aplicado como uma estratégia de intensicação a cada ótimo local
obtido após a fase de busca local.
Escolhemos a primeira dessas estratégias para a implementação do
Path Relinking. O
algoritmo a seguir ilustra o algoritmo GRASP-VNS com Path Relinking.
Algoritmo 11: GRASP VNS com Path Relinking proposto para o pCaRS
Entrada: nomeInstancia,imax , α
Saída: x∗ ∈ X
leInstancia(nomeInstancia);
f (x∗ ) ← ∞
para i = 1, ..., imax faça
x←
geraSolucaoConstrutiva(α,
x←
buscaMultiOperadores(x);
numSol);
se f (x) < f (x∗ ) então
f (x∗ ) ← f (x)
x∗ ← x
m
E←
montaConjuntoElite(qtd);
m
x←
PathRelinking(E);
se f (x) < f (x∗ ) então
f (x∗ ) ← f (x)
x∗ ← x
m
∗
retorne(x );
O
Path Relinking
proposto considera que uma quantidade pré-denida das melhores
soluções geradas pelo algoritmo GRASP formarão o conjunto de elite representado pelo
conjunto
E.
Este conjunto é atualizado e ordenado a cada iteração até atingir o número
máximo de soluções pré-determinado. Se uma nova solução for melhor do que a última
solução do conjunto (e consequentemente a pior solução), então a nova boa solução é
adicionada ao conjunto e a última é removida, reordenando o conjunto.
De posse dessas soluções, o procedimento funciona utilizando a melhor solução do
conjunto como solução base. A solução de destino é escolhida como sendo a segunda
melhor solução do conjunto. Em seguida busca-se inserir cada cidade, com seu respectivo
carro na solução de destino, sobrepondo o par cidade-carro anteriormente existente. O
algorimo considera a inserção acumulativa das cidades constantes na solução base na
solução destino, na mesma ordem em que estão presentes na solução base.
73
Ao nal desse processo, ca-se com a melhor solução obtida, que será a nova solução
base. A terceira melhor solução do conjunto é então escolhida como solução de destino,
repetindo todo o processo. O procedimento continua de forma semelhante até que não
existam mais soluções destino no conjunto de elite.
A gura a seguir ilustra o funcionamento da escolha das soluções base e destino e do
operador de
Path Relinking
proposto:
Figura 12: Exemplo de aplicação do procedimento de Path-Relinking
É importante ressaltar que as soluções podem ter tamanhos (quantidade de cidades)
diferentes, o que pode tornar o procedimento apenas parcial, conforme ilustrado na Figura
12. Após cada inserção, pode ser necessário aplicar o procedimento de restauração de
soluções, já descrito anteriormente.
4.1.6 Algoritmo GRASP com Lista 2-Potencial
Este terceiro experimento com o GRASP considerou a utilização de uma nova abordagem na construção da lista de candidatos. Para cada candidato, vericou-se a adequação
para inserção considerando dois passos adiante, considerando as três cidades com menor
custo de inserção em cada passo. A intenção dessa abordagem é de tentar evitar que seja
74
efetuada uma inserção que é boa considerando a LRC atual, mas que não será uma boa
opção para o restante da solução a longo prazo.
Para cada cidade na Lista de Candidatos, são consideradas as próximas três melhores
cidades (com menor custo), e a partir de cada uma dessas cidades, as três próximas
de menor custo. A montagem da lista é feita considerando o somatório cumulativo de
cada caminho com todos os carros disponíveis. Cada cidade da lista de candidatos terá
nCar × 9
opções geradas para a lista. A LRC é montada a partir da lista de candidatos,
considerando os
α% melhores. A gura a seguir ilustra o funcionamento dessa abordagem
a partir de uma entrada de cidade
A
da lista de candidatos da abordagem tradicional:
Figura 13: Exemplo de aplicação do procedimento 2Potencial
Foram consideradas para implementação duas variações dessa abordagem, com diferenças na forma como o sorteio na LRC é efetuado, sendo:
•
Versão 1: O sorteio na LRC foi efetuado considerando igual probabilidade a todas
os candidatos.
•
Versão 2: O sorteio na LRC foi do tipo "roleta", onde a probabilidade foi proporcional à potencialidade de inserção de cada candidato.
4.2 Algoritmo Memético
4.2.1 Introdução
Algoritmo evolucionário é um termo geral utilizado para a programação evolutiva,
estratégias evolutivas e algorimos genéticos. Essa estratégia vem sendo aplicada com su-
75
cesso em várias problemas de otimização. Os Algoritmos genéticos são baseados na teoria
da Evolução Darwiniana e prezam pela simulação de processos evolutivos em sistemas
articiais. Baseada em População, esta metaheurística possui inspiração biológica, considerando os aspectos de reprodução, recombinação, mutação, seleção e sobrevivência pela
adequação.
Os algoritmos evolucionários híbridos incorporam estratégias de busca local em sua
estrutura e combinam as vantagens de heurísticas ecientes com evolução baseada em
população. Esses algoritmos também são conhecidos por algoritmos genéticos com busca
local, e fazem parte da classe dos algoritmos meméticos (DIGALAKIS;
MARGARITIS,
2004).
Partindo da palavra "mimeme"de origem grega, o termo "meme"foi utilizado por
"The Selsh Gene". Este termo foi utilizado
para denir a unidade básica de transmissão cultural ou de imitação".
(DAWKINS, 1976) em seu livro denominado
Os algoritmos meméticos que também podem ser vistos como uma hibridização dos
algoritmos evolucionários com algum tipo de busca local. Foram propostos por (MOSCATO,
1989) e são utilizados em uma vasta gama de aplicações. Eles diferem dos algoritmos
genéticos por considerarem a evolução Lamarckiana. Dessa forma, a abordagem memética
considera um aperfeiçoamento não-genético na população com auto-reprodução, herança
de características, mudança aleatória no genótipo e sobrevivência regulada por combinação
de habilidades herdadas.
De acordo com (KRASNOGOR;
GUSTAFSON,
2004), um algoritmo básico com aborda-
gem memético pode ser visto no pseudo-código a seguir:
Algoritmo 12: Algoritmo memético genérico para minimização
X←
GeraPopInicial();
para i = 1, ..., ngeracoes faça
x←
Recombinação();
x←
Mutação();
x←
BuscaLocal();
Seleciona_para_próxima_geração();
m
retorna_melhor_solução();
Alguns exemplos de aplicação de algoritmos meméticos voltados ao roteamento de
veículos são vistas em (ONG;
LIM; CHEN,
2010). (GOLDBARG;
2012) também aplicam essa abordagem ao problema CaRS.
ASCONAVIETA; GOLDBARG,
76
4.2.2 Pseudo-Código do Algoritmo Memético Proposto
O pseudo-código do algoritmo memético proposto é apresentado a seguir, onde suas
partes constitutivas são explicadas nos itens subsequentes.
Os parâmetros de entrada para o algoritmo são:
nomeIstancia,
que identica o pro-
blema que será executado, imax , que representa o número de iterações que o algoritmo vai
executar,
tamP op
binação, e
T xM ut
representado por
representa o tamanho da população,
T xRec
que é a taxa de recom-
representa a taxa de mutação. O conjunto de soluções encontradas é
X = {x0 , x1 , ..., xn }
e a melhor solução encontrada por
x∗ .
Algoritmo 13: Algoritmo Memético MA1 proposto para o pCaRS
Entrada: nomeInstancia,imax , tamP op, T xRec, numIter
Saída: x∗
leInstancia(nomeInstancia);
numIter ← 0;
pop[] ← gera_P op_ini(tamP op);
pop[] ← buscaM ultiOperadores(pop[]);
enquanto numIter < imax faça
sel[] ← seleciona(pop[], T xRec);
of f [] ← recombina(sel[]);
of f [] ← buscaM ultiOperadores(of f []);
pop[] ← novaP op(pop[], of f []);
m
∗
retorne(x );
As soluções para o problema são representadas por uma matriz de 2 dimensões, conforme ilustrado na Figura 5, onde a rota é representada numa dimensão (superior) e os
carros são representados na outra (inferior). Dessa forma, o cromossomo também possuirá
esta representação.
4.2.2.1 População Inicial
A população inicial é gerada através do procedimento
recebe o tamanho da população,
tamP op,
geraP opInicial(tamP op)
que
como parâmetro de entrada. Uma heurística
gulosa adaptada do problema CaRS é usada para gerar os cromossomos da população
inicial.
Um carro
k1
é escolhido aleatoriamente para a primeira cidade. Em seguida, a cidade
77
i
onde o carro
k1
será entregue é também escolhida de forma aleatória. Um caminho é
criado entre as cidades
1
e
i
através da heurística do vizinho mais próximo, considerando
os custos de viagem com o carro
k1 .
rota. Em seguida, um novo carro
k2
Claramente, a cidade
j
A cidade
i
é a cidade inicial da próxima parte da
e uma nova cidade
j
são escolhidos aleatoriamente.
não pode ser uma cidade visitada anteriormente. Um caminho é
construído entre as cidades
i
e
j
com as cidades não visitadas. O procedimento continua
sorteando outra cidade aleatoriamente e construindo o caminho até que não existam mais
carros para adicionar na solução, ou o nível de satisfação seja alcançado, quando o ciclo
é fechado considerando a ligação com a cidade de partida.
4.2.2.2 Fase de Busca Local
A fase de busca local é composta pelos mesmos operadores previstos na fase de busca
local denominada
buscaM ultiOperadores()
e apresentada no algoritmo GRASP citado
anteriormente. Da mesma forma que a abordagem GRASP, as buscas locais são aplicadas
em sequência, retornando o indivíduo viável de melhor adequação de acordo com a função
de avaliação.
4.2.2.3 Recombinação
Esta etapa corresponde à troca de informação entre os cromossomos da população.
Para efetuar a recombinação, é montado um vetor, denominado
a quantidade prevista no parâmetro
da função
seleciona(pop[], T xRec),
T xRec
sel[],
onde é armazenado
de indivíduos na população atual através
que escolhe aleatoriamente indivíduos na população,
tendo o cuidado de selecionar cada indivíduo apenas uma vez.
Após essa seleção, o operador de recombinação de um ponto é utilizado em dois
indivíduos selecionados no vetor
sel[] e o resultado é armazenado no vetor of f []. Uma vez
que o número de genes em cromossomos pode variar, um ponto aleatório é escolhido na
gama de índices do menor cromossomo. A recombinação dos dois pais,
descendentes,
C
e
A
e
B,
gera dois
D, tal como ilustrado na Figura 14. O ponto de cruzamento é ilustrado
com uma linha tracejada nos cromossomos
A
e
B.
78
Figura 14: Operador de Recombinação - Memético
Pode ser necessário restaurar a viabilidade de soluções geradas durante a recombinação. A inviabilidade pode ocorrer sobre rotas, atribuição de carros ou de satisfação total.
Por exemplo, imediatamente depois de ter sido gerado o cromossomo
C
o mesmo tem
uma solução inviável devido ao percurso e atribuição de veículos. Nesse caso, é executado
o procedimento de restauração apresentado anteriormente.
4.2.2.4 Renovação da População
Para a renovação da população, é feito um torneio binário entre um novo indivíduo
em
ospring[]
pop[].
constante no vetor
of f []
e um indivíduo da população, constante no vetor
Caso o valor da função de avaliação
f
do indivíduo presente em
of f []
seja menor
que o valor avaliado para o indivíduo da população, o mesmo é substituído.
A reprodução, tradicionalmente, é divididas em três etapas: acasalamento, recombinação e mutação. O acasalamento é a escolha de dois indivíduos para se reproduzirem
(geralmente gerando dois descendentes para manter o tamanho populacional). A recombinação, ou
crossing-over
é um processo que imita o processo biológico homônimo na
reprodução sexuada: os descendentes recebem em seu código genético parte do código
genético do pai e parte do código da mãe. Esta recombinação garante que os melhores
indivíduos sejam capazes de trocar entre si as informações que os levam a ser mais aptos
a sobreviver, e assim gerar descendentes ainda mais aptos.
A seleção aleatória dos pais pode dicultar a convergência do método. Por este motivo,
consideramos a inclusão de uma estratégia de elite no experimento.
Foram consideradas para implementação duas variações dessa abordagem, com diferenças na forma como o os candidatos para recombinação são escolhidos.
•
Versão MA1: Os pais que serão utilizados na recombinação são selecionados alea-
79
toriamente na população.
•
Versão MA2: Essa versão contará com uma população de elite, a partir de onde
será escolhido um dos pais para a recombinação. O outro pai será escolhido aleatoriamente na população.
Logo, a versão
M A2
do algoritmo memético considera que uma quantidade pré-
denida das melhores soluções geradas pelo algoritmo após a busca local formarão o
conjunto de elite representado pelo vetor
popElite[].
De posse dessas soluções, o procedi-
mento que seleciona os pais para a recombinação sorteia uma solução deste conjunto que
será um dos pais, enquanto o outro será sorteado aleatoriamente da população.
Sendo assim, as mudanças em relação ao algoritmo
M A1
proposto seriam relativas a
inserção do conjunto de elite e também na forma como os pais serão selecionados para a
recombinação. O parâmetro
qtd diz respeito à quantidade de indivíduos que farão parte do
conjunto de elite. Os demais parâmetros e métodos são idênticos ao primeiro algoritmo. O
algoritmo da versão
M A2
é apresentado a seguir, com as diferenças em relação ao
destacadas em negrito.
Algoritmo 14: Algoritmo Memético MA2 proposto para o pCaRS
Entrada: nomeInstancia,imax , tamP op, T xRec, numIter,qtd
Saída: x∗
leInstancia(nomeInstancia);
numIter ← 0; pop[] ← gera_P op_ini(tamP op);
pop[] ← buscaM ultiOperadores(pop[]);
popElite[] ← montaPopElite(pop[],qtd);
enquanto numIter < imax faça
sel[] ← seleciona(pop[], T xRec);
o[] ← recombina(sel[ ],popElite[ ]);
of f [] ← buscaM ultiOperadores(of f []);
pop[] ← novaP op(pop[], of f []);
popElite[] ← montaPopElite(pop[],qtd);
m
∗
retorne(x );
M A1
80
4.3 Transgenética Computacional
4.3.1 Introdução
Os algoritmos transgenéticos foram propostos por (GOLDBARG;
GOLDBARG,
2009), e
pertencem à classe dos algoritmos evolucionários, cuja metáfora baseia-se na endossimbiose e propriedades do uxo intracelular. Nesse contexto, a evolução biológica envolve uma
célula hospedeiro, endossimbiontes xados no citoplasma da célula hospedeira e vetores
que permitem que endossimbiontes e hospedeiro troquem informações genéticas entre si.
A abordagem endosimbiótica foi proposta por (MARGULIS, 1992) sendo uma teoria
evolucionária que baseia sua formulação na premissa de que dois ou mais organismos
independentes podem se unir em um sistema simbiótico e constituir um novo organismo,
contribuindo para a constituição de saltos adaptativos ou a formação de espécies híbridas
ou novas (MOROWITZ, 2004).
Enquanto o processo de movimento de material genético entre bactérias utiliza a reprodução para a transferência vertical de genes, onde uma bactéria herda material genético
de seu ancestral, existe um conhecido conjunto de processos endosimbióticos apresentados
na literatura sob o nome de
transferência horizontal, que ocorre entre microorganismos de
modo distinto ao da reprodução. Dois dos conhecidos veículos de transferência horizontal
que serviram de inspiração para o algoritmo proposto neste trabalho são os plasmídios e
os transposons.
Os transposons, ou genes saltadores, são elementos genéticos que podem se mover
espontaneamente de uma posição para outra dentro do DNA. Eles se movem de uma
localização para outra no DNA de uma mesma célula caracterizando uma permutação.
Esse fenômeno denominado transposição, foi descoberto nos anos 1950 por Barbara McClintock, e lhe rendeu o Prêmio Nobel de Medicina em 1983 (PRAY;
ZHAUROVA,
2008).
Devido ao seu carácter dinâmico, os transposons têm uma enorme inuência na evolução e composição de genomas de plantas e animais. De acordo com (GIORDANO
et al.,
2007), a possibilidade de inserção dentro de genes do próprio organismo pode causar
diversas doenças, bem como ser fonte de nova informação genética.
Os plasmídios são partículas genéticas móveis, anéis de DNA, que podem ser intercambiadas entre certas células e que podem se replicar independente de um cromossomo.
Transferência de DNA de um doador para um recipiente por contato físico direto entre
as células. Em bactérias existem dois tipos de conjugantes: um doador (macho) e um
81
recipiente (fêmea) e a direção da transferência do material genético é única (unidirecional);
O DNA é transferido de um doador para um recipiente.
O comportamento biológico dos veículos de transferência horizontal citados é ilustrado
na Figura 15 a seguir:
Figura 15: Exemplo de transferência de informações via Plasmídeo e Transposon
4.3.1.1 Contexto Computacional
Os algoritmos transgenéticos, adaptando os conceitos da endossimbiose ao contexto
computacional, propõem a execução da evolução através de um processo de troca de informações entre uma população de cromossomos simbiontes e um hospedeiro. A troca ocorre
através de vetores transgenéticos, que coordenam a obtenção e compartilhamento de informações genéticas. De acordo com (ASCONAVIETA, 2011), os algoritmos transgenéticos
fundamentam-se nas seguintes premissas:
1. A evolução ocorre no interior de uma célula hospedeiro que foi invadida ou que
absorveu outras unidades vivas. A mistura de criaturas forma uma quimera. A
quimera deve evoluir para formar uma unidade biológica cuja função de avaliação
seja melhor do que as partes que compõem a quimera.
2. A evolução da quimera acontece de forma guiada e inuenciada pelo DNA do hos-
82
pedeiro. Portanto o repositório genético que evolui é residente em dois diferentes
contextos, e o contexto do hospedeiro é predominante.
3. O processo de troca de informações genéticas necessário à evolução é operacionalizado sicamente através de partículas genéticas móveis. Esses elementos constituem
um terceiro contexto evolucionário.
Um algoritmo transgenético genérico para minimização, adaptado de (GOLDBARG;
BAGI; GOLDBARG,
2009), pode ser visualizado no pseudo-código a seguir:
Algoritmo 15: Algoritmo transgenético genérico para minimização
Inicia Populacao;
Inicia Banco de Informações Genéticas;
repita
Gera vetores transgenéticos;
Seleciona cromossomos para manipulação;
Manipula os cromossomos selecionados;
Atualiza Banco de Informações Genéticas;
até enquanto não satisfaz critério de parada ;
Os vetores transgenéticos considerados neste trabalho recebem o mesmo nome dos
veículos naturais nos quais foram inspirados, sendo eles: plasmídios e transposons.
De acordo com (GOLDBARG;
por uma dupla
λ = (I, Φ),
nipulaçao, onde
onde
GOLDBARG,
I
2009), um vetor transgenético,
é uma cadeia de informação e
Φ = (p1 , ..., ps ), pj , j = 1, ..., s,
do vetor. Quando a cadeia de informação
transgenéticos provavelmente modicarão
I
S
Φ
λ, é formado
é um método de ma-
são procedimentos que denem a atuação
é inltrada no cromossomo
e seu
tness.
S,
os vetores
A tabela a seguir resume os
procedimentos que compõem o método de manipulação de vetores transgenéticos.
Tabela 5: Procedimentos utilizados por plasmídeos e transponsons
Procedimento
Caracterização
p1
Ataque (A)
Dene o critério de avaliação que dene quando um cromossomo
p2
Transcrição
é suscetível a manipulação de um vetor transgenético
Se o cromossomo
C
I,
transportada pelo vetor, será transferida
para o cromossomo.
Identicação
Identica posições que serão utilizadas para limitar a
operação do vetor.
λ
for suscetível a manipulação, o procedimento
dene como a informação
p3
C
83
Um vetor
Φ
é dito um plasmídeo quando sua cadeia de informação
I
é descrita no
mesmo formato que os cromossomos endossimbiontes, uma subcadeia de DNA, e seu
método utiliza os procedimentos
p1
e
p2 .
Um transposon é um vetor
Φ
cuja cadeia de
informação corresponde a uma regra ou método que utiliza os procedimentos
A Figura 16 é parte constituinte de (GOLDBARG;
GOLDBARG,
p1 , p2
e
p3 .
2009) e ilustra o pro-
cesso do uxo de informações na abordagem transgenética.
Figura 16: Fluxo de informações em um algoritmo transgenético
Alguns exemplos de aplicação da transgenética computacional em problemas relacionados ao roteamento de veículos são vistos em (GOLDBARG;
(GOLDBARG;
BAGI; GOLDBARG,
2008),
BAGI; GOLDBARG, 2009), (ALMEIDA et al., 2010). A abordagem transgenética
é aplicada ao problema CaRS em (GOLDBARG
et al.,
2013).
4.3.2 Pseudo-Código do Algoritmo Transgenético Proposto (TA1)
O pseudo-código do algoritmo transgenético proposto, em sua primeira versão, denominada
T A1
é apresentado a seguir, e suas partes constitutivas são explicadas nos itens
subsequentes.
Os parâmetros de entrada para o algoritmo são:
blema que será executado,
vai executar,
T amP op
imax ,
nomeIstancia,
que identica o pro-
que representa o número de iterações que o algoritmo
representa o tamanho da população, e
quantidade de iterações em cada estágio.
evEstagio
representa a
84
Algoritmo 16: Algoritmo Transgenético TA1 proposto para o pCaRS
Entrada: nomeInstancia,imax , tamP op, evEstagio
Saída: x∗ ∈ X
f∗ ← ∞
leInstancia(nomeInstancia);
pop[] ← geraP opini(tamP op);
BIG[] ← bancoInf ormacoesGeneticas();
pop[] ← buscaM ultiOperadores(pop[]);
para t = 1 ate imax /evEstagio faça
#probP lasmideo ← def ineP rob(t)
para z = 1 ate evEstagio faça
prob = sorteio(0, 1);
para c = 1 ate tamP op faca faça
se prob < #probP lasmideo então
inf ormacao ← sorteio(BIG)
x ← P lasmideo(pop[c], inf ormacao);
m
senão
x ← T ransposon(pop[c], metodo);
m
se f (x) < f (pop[c]) então
pop[c] ← x
se f (x) < f (x∗ ) então
x∗ ← x
m
m
BIG[] ← bancoInf ormacoesGeneticas();
m
m
m
∗
retorne(x );
Um fato que merece destaque é que a variável
#probP lasmideo
rado durante a execução do algoritmo, porém permanece xo por
tem seu valor alte-
#evEstagio
iterações.
Esse conjunto de iterações é chamado de estágio evolucionário. Nesse estágio, a probabilidade da escolha do agente plasmídio é denido na variável
#probP lasmideo,
a probabilidade de escolher um transposon é dado pelo seu complementar.
enquanto
85
A relação entre a probabilidade de escolha de plasmídeos ou transposons é denida
de acordo com a relação
imax /evEstagio,
permanecendo assim durante esta quantidade
especíca de iterações. Em cada estágio evolucionário, os parâmetros do esquema de manipulação são mantidos. Os parâmetros são alterados entre os estágios de modo a alterarem
a probabilidade de escolha de cada agente. Inicialmente, existe um favorecimento na escolha do agente plasmídeo, que privilegia o uxo de informações vindo do hospedeiro
para os endossimbiontes. No decorrer do processo, a probabilidade de escolha dos agentes
transposons vai ganhando espaço, favorecendo o processo intracelular de transposição.
4.3.2.1 População Inicial
A população inicial é gerada através do procedimento
geraP opInicial(tamP op)
cujo
procedimento é o mesmo descrito na abordagem do algoritmo memético.
4.3.2.2 Banco de Informações Genéticas
O Banco de Informações Genéticas (BIG) guarda as fontes de informações de plasmídeos. Nesse estudo, as informações contidas neste repositório dizem respeito apenas às
20% melhores soluções encontradas pelo algoritmo, sem nenhum informação adicional, ou
seja, contendo apenas indivíduos da população. O banco é atualizado a cada iteração do
algoritmo.
4.3.2.3 Plasmídeo
A forma de atuação do agente plasmídeo procura mimetizar a metáfora biológica, onde
ocorre o transporte de material genético do hospedeiro no cromossomo endossimbionte.
Este procedimento é ativado através da função
A variável
inf ormacao
P lasmideo()
do algoritmo.
armazena a cadeia de informações do cromossomo doador,
que é escolhido aleatóriamente do banco de informações genéticas e que será transcrita
no cromossomo destino. No presente algoritmo, essa informação, cujo tamanho é sorteado
aleatóriamente em relação ao tamanho do menor entre os dois cromossomos envolvidos
no processo, varia entre
2 ≤ tam ≤ 0, 4 × tamM enorCromossomo.
Após denido o
tamanho do trecho que será retirado, sorteia-se em que parte do cromossomo será retirada
a informação, que diz respeito a um vetor bi-dimensional, contendo um trecho, que será
composta por um trecho de rota e uma sequência de carros, oriundas do cromossomo
doador. A parte removida do cromossomo destino possui o mesmo tamanho denido
86
anteriormente, e também é denida aleatoriamente.
Foram analisados dois operadores de plasmídeo, denominados
P lasmideoT otal
P lasmideoP arcial
e
cujas probabilidades de ataque são complementares. Se o vetor plasmí-
deo for considerado para ataque, então é feito um sorteio com igual probabildiade entre
os dois operadores disponíveis. Se o
P lasmideoT otal
O operador
P lasmideoP arcial
for escolhido, então o operador
não atuará nesse ataque.
P lasmideoP arcial
é ilustrado na Figura 19. Neste exemplo, uma cadeira
de tamanho três é selecionada e retirada do cromossomo doador. Em seguida, uma cadeia
de mesmo tamanho é retirada do cromossomo destino. Testa-se a conjugação em todos
os possíveis pontos, de forma a buscar uma melhoria no custo da solução. Caso a solução
gerada seja inviável, a mesma é submetida a um procedimento de restauração, descrito
anteriormente.
Figura 17: Exemplo de aplicação do operador Plasmídeo Parcial
O operador
P lasmideoT otal
proposto possui uma tentativa de inserção maior no
hospedeiro, visando ampliar a sua atuação na solução de destino. O algorimo considera a
inserção em todas as posições possíveis do trecho na solução destino. Em seguida, outro
trecho consecutivo de mesmo tamanho é excluído na solução destino e novamente é feita
a inserção. Este procedimento continua até que não existam mais trechos consecutivos a
serem excluídos. A gura a seguir ilustra o funcionamento desse plasmídeo.
87
Figura 18: Exemplo de aplicação do operador Plasmídeo Total
4.3.2.4 Transposons
Caso o procedimento escolhido para manipulação do endosimbionte seja o operador
transposon, o procedimento
transposon()
é ativado. Este tipo de operador manipula os
cromossomos da população sem transportar material do hospedeiro. No caso do algoritmo desenvolvido, os operadores descritos na operação
buscaM ultiOperadores()
foram
adaptados para funcionar como transposons no problema.
Ao ativar o procedimento
transposon(), os mesmos são aplicados na mesma sequência
que foram aplicados no operador
inverteSol, InsereCidade
baixo. As buscas locais
buscaM ultiOperadores(). As buscas locais removeCidade,
permaneceram inalteradas por terem um custo computacional
substituiCidade, substituiCarro e 2Opt, sofreram algumas adap-
tações, que são destacadas a seguir.
(a)
substituiCarro: Esse procedimento atua somente em um trecho pré-denido da solução. Esse método concentra-se em veículos que não estão ainda na solução, examinando a inserção de um novo carro, se possível. O novo carro substitui outro na
solução. Todos os carros que não fazem parte da solução de entrada são considerados.
O carro que não está na solução é inserido em cada posição do intervalo escolhido, de
forma iterativa.
88
Algoritmo 17: Transposon: substituiCarro()
Entrada: x, posIni, posF im
Saída: x
listaCAR
←
montaListaCarrosDisp(x);
para k = 1 ate #listaCAR faça
para i = posIni ate posF im faça
x←x
para j = i ate posF im faça
x.car[j] ← listaCAR[k];
x ← reparaCar(x)
se f (x) < f (x) então
x←x
m
m
m
m
retorne(x);
A Figura 19 ilustra a aplicação do transposon
substituiCarro()
a uma solução. O
segmento escolhido para manipulação pelo agente está destacado em linhas tracejadas.
No procedimento, ocorre a inserção do carro
k=4
em todas as posições do intervalo
escolhido, cumulativamente.
Figura 19: Exemplo de aplicação do transposon substituiCarro()
89
(b)
substituiCidade:
Esse procedimento atua em um trecho pré-denido da solução
sobre as cidades que ainda não estão na solução. Ele examina a substituição de cidades
na solução por cidades que não estão presentes na solução. Todas as cidades da solução
de entrada são consideradas para a inserção no intervalo escolhido.
Algoritmo 18: Transposon: substituiCidade()
Entrada: x,posIni, posF im
Saída: x
listaCID
←
montaListaCidadesDisp(x);
para i = 0 ate #listaCAR faça
para j = posIni ate posF im faça
x←x
x.cid[j] ← listaCID[i];
x ← reparaSatisf (x)
se f (x) < f (x) então
x←x
m
m
m
retorne(x);
(c)
2-opt: é um algoritmo de busca local simples proposto por (CROES, 1958) para o PCV.
Um movimento 2-opt consiste em eliminar duas arestas e religar os dois caminhos,
resultando em uma maneira diferente de obter uma nova rota. No caso especíco do
transposon, o operador irá atuar apenas em um intervalo pré-denido. Entre todos
os pares de arestas cuja troca 2-opt atua, a que resultar no menor custo de rota é
escolhido. Este procedimento é então iterado até que o par de arestas mais econômico
do intervalo analisado seja encontrado.
Os operadores são aplicadas em seqüência no procedimento
ilustrado na gura a seguir.
transposon(),
conforme
90
Algoritmo 19: Transposon
Entrada: x
Saída: xk ∈ N (x)
x
←
removeCidade(x);
x
←
inverteSol (x);
x
←
insereCidade(x);
x
←
substituiCidade(x,posIni,
x
←
substituiCarro(x,posIni,
x
←
2Opt(x,posIni,
posF im);
posF im);
posF im);
k
retorne(x );
4.3.3 Algoritmo Transgenético com Reprodução do Endossimbionte
Os algoritmos transgenéticos não necessariamente fazem a reprodução dos endossimbiontes. Por outro lado podem utilizar naturalmente informações sobre o problema e
obtidas a priori ao desenvolvimento do processo evolucionário conjuntamente com informações obtidas durante esse processo.
Tais informações podem ser obtidas
a priori, a partir de algum conhecimento prévio
do problema. Soluções heurísticas, limites para a solução, resultados de análise estatística
do problema, entre outros dados enriquecem o banco de informações genéticas com boas
informações que serão repassadas durante o processo.
Outras informações obtidas
a posteriori,
são constituídas a partir da evolução das
soluções iniciais do algoritmo. Informações obtidas
a priori e a posteriori são residentes no
hospedeiro. A informação residente na população de endossimbiontes evolui paralelamente
a evolução da informação do hospedeiro.
Nesse contexto, a transformação da quimera em um novo organismo eciente é preponderantemente dependente das trocas genéticas entre hospedeiro e endossimbiontes.
Evidentemente, a qualidade das informações obtidas
a priori
possui grande inuência no
processo.
No contexto tradicional da evolução transgenética, caracterizada como um fenômeno
predominantemente intracelular, não existe necessidade de reproduzir nem o hospedeiro
e nem os endossimbiontes para otimizar a adequação da quimera formada. Portanto os
passos de seleção de cromossomos reprodutores, de seleção de cromossomos sobreviventes,
91
etc., se mostram completamente dispensáveis na metáfora.
Por outro lado, a evolução da quimera não necessita de mecanismos de mutação aleatória para promover a diversicação biológica, pois o próprio processo de sua constituição
já arrasta consigo um bom potencial de diversicação.
Observa-se que no algoritmo
T A1 considerado o banco de informações genéticas conta
apenas com cromossomos e nenhuma informação
a priori. A atualização de melhores in-
formações ocorre em paralelo com a evolução do algoritmo. Esse fator pode ser prejudicial
à convergência do algoritmo pois, em uma primeira etapa, temos uma maior probabilidade
de utilização do operador
plasmideo,
que tem por objetivo inserir boas informações na
solução.
Para amenizar as perdas geradas nesse contexto, a segunda versão do algortimo transgenético proposto, denominada
T ARep
considera a reprodução dos endosimbiones, de
forma a melhorar a qualidade das informações repassadas.
Dessa forma, modicou-se a função
goritmo proposto para o
BIG[] ← bancoInf ormacoesGeneticas()
T A1. Os indivíduos que compõe o BIG
do al-
passam por um processo
de reprodução vertical, com seleção de pais, cruzamento e seleção dos melhores para permanecer na população. Os pais são selecionados aleatoriamente no BIG e passam pelo
processo de recombinação previamente descrito no algoritmo memético. A seleção se dá
por cotas, pois o tamanho do BIG é xo em
0, 2×tamP op. As soluções obtidos pela evolu-
ção transgenética só passarão a fazer parte do BIG se forem melhores que as já existentes
nesse repositório.
4.3.4 Algoritmo Evolucionário Híbrido - EH1
A evolução biológica pode ser entendida como a mudança das características hereditárias de uma população de uma geração para outra. Este processo faz com que as
populações de organismos mudem e se diversiquem ao longo do tempo.
Durante muito tempo, a pesquisa evolutiva vislumbrou apenas a passagem de genes de
pai para lho, conhecido como transferência de genes vertical. Este processo, agiu durante
as eras do tempo geológico, dando origem à estrutura de ramicação da árvore da vida.
A árvore da vida é uma metáfora usada para descrever as relações entre os organismos,
tanto os vivos quanto os extintos. Charles Darwin utilizou o termo para expressar o
conceito de divergência e ramicação de variedades e espécies, seguida de um processo
92
de descendência comum de ancestrais (DARWIN, 1936). Ernst Haeckel cunhou o termo
logenia para as relações evolutivas de espécies ao longo do tempo, e foi mais longe do
que Darwin em propor histórias logenéticas da vida. O desenvolvimento moderno dessa
ideia é chamada de árvore logenética (HAECKEL, 1879).
A transferência horizontal de genes vêm adquirido importância nos estudos de biologia
evolutiva nas últimas décadas, especialmente por causa da grande troca de genes que teria
ocorrido entre os primeiros procariontes, no início da evolução biológica em nosso planeta
e, também, no começo da divergência entre bactérias, archaea e eucariontes primitivos.
Nesse processo, um organismo transfere material genético para outra célula que não é sua
descendente. Transferência vertical, por contraste, ocorre quando um organismo recebe
material genético do seu antecessor, por exemplo dos pais ou de uma espécie a partir da
qual evoluiu.
Desde a década de 1980, os cientistas evolucionistas têm se tornado cada vez mais
conscientes que a transferência gênica horizontal ou lateral também desempenha um papel
importante na evolução (LIPPS, 2008). Nesse contexto, os plasmídeos são agentes chave na
transferência horizontal de genes, que aceleram a adaptação bacterial ao meio (HARRISON;
BROCKHURST,
(MCDANIEL
2012). Esses processos ocorrem com frequência elevada no meio marinho
et al.,
2010).
As questões levantas pela extensa transferência lateral de genes que teria ocorrido
no período inicial de evolução celular, zeram com que alguns cientistas questionassem a
adequação da metáfora
ou
árvore da vida
propondo, em seu lugar, que estruturas de
redes
anéis, neste período inicial, representariam melhor as relações genéticas entre os orga-
nismos que, na realidade, teriam evoluído de maneira bem promíscua, tanto por meio da
transferência vertical (de ancestral para descendente) de seu material genético, como pela
transferência horizontal (DOOLITTLE, 2000).
De acordo com o contexto gerado, é proposto um algoritmo evolutivo baseado no
que foi proposto para o
M A2,
considerando além do contexto evolutivo vertical com a
reprodução e recombinação, que a transferência gênica também possa ocorrer de forma
horizontal através de um operador plasmídeo.
Dessa forma, o algoritmo proposto, denominado de algoritmo Evolutivo Híbrido
EH1
considera a inclusão de uma probabilidade de transferência vertical ou horizontal de genes
em cada geração. Para o presente estudo, foi considerada uma igual probabilidade de
escolha entre os dois operadores. O funcionamento do algoritmo proposto é ilustrado a
seguir:
93
Algoritmo 20: Algoritmo Evolutivo Híbrido EH1 proposto para o pCaRS
Entrada: nomeInstancia,imax , tamP op, T xRec, numIter
Saída: x∗
leInstancia(nomeInstancia);
numIter ← 0;
pop[] ← geraP opini(tamP op);
pop[] ← buscaM ultiOperadores(pop[]);
popElite[] ← montaP opElite(pop[], qtd);
enquanto numIter < imax faça
sel[] ← seleciona(pop[], T xRec);
p ← aleatorio(100)
se p > 50 então
of f [] ← recombina(sel[], popElite[]);
m
senão
of f [] ← P lasmdeo(sel[], popElite[]));
m
of f [] ← buscaM ultiOperadores(of f []);
pop[] ← novaP op(pop[], of f []);
popElite[] ← montaP opElite(pop[], qtd);
m
∗
retorne(x );
Esse algoritmo evolutivo híbrido considera que uma quantidade pré-denida das melhores soluções geradas pelo algoritmo após a busca local formarão o conjunto de elite
representado pelo vetor
utilizado no
ritmo
M A2.
popElite[], de forma idêntica ao que foi adotado no procedimento
A reprodução também ocorre de forma similar ao já descrito no algo-
M A2.
A aplicação do plasmídeo ocorre da mesma forma que o operador
descrito no algoritmo
P lasmideoP arcial
T A1. O procedimento sorteia uma solução deste conjunto que servirá
de solução base, e uma solução constante no vetor de cidades selecionadas, que será a
cidade destino na aplicação do plasmídeo.
94
5
Experimentos Numéricos
Computacionais
As metaheurísticas propostas e seus respectivos experimentos computacionais são
apresentados com detalhes no presente capítulo. Com a nalidade de validar os algoritmos propostos, os mesmos foram implementados em um PC Intel Core i5, 16G de
RAM, rodando Ubuntu 12.04 64bits, utilizando a linguagem C++ e executados trinta
vezes para cada instância.
5.1 Algoritmos GRASP
Os testes preliminares para anação de parâmetros do algoritmo, consideraram seis
instâncias da biblioteca pCaRSLib, com um número de cidades na faixa de 9 a 25 e 2 a
4 veículos, onde foram executadas 20 vezes cada uma. Na análise realizada, o parâmetro
alpha
que regula o tamanho da LCR, variou entre
0, 15 ≥ α ≥ 0, 30.
O número de
iterações adotado foi 5000. A Figura 20 a seguir ilustra o comportamento dos parâmetros
analisados.
Figura 20: Ajuste dos parâmetros utilizados no algoritmo GRASP
95
A partir da análise desse gráco, observamos que os valores mínimos se estabilizaram
com valores de alfa próximos a
uma lista LCR de tamanho
0, 25.
Logo, os parâmetros utilizados no GRASP foram
α = 0, 25
e como critério de parada, foi estabelecido 5000
iterações.
As abordagens GRASP analisadas foram:
1.
GRASP1: GRASP + VNS
2.
GRASPPR: GRASP + VNS + Path Relinking
3.
GRASP2P: GRASP 2-Potencial Sorteio + VNS + Path Relinking
4.
GRASP2PRol: GRASP 2-Potencial Roleta + VNS + Path Relinking
Os algoritmos com abordagem GRASP propostos obtiveram uma boa adaptação aos
problemas analisados. Os algoritmos variaram na fase de pós otimização, onde tivemos
a proposta com e sem
Path-Relinking. Além disso, foi proposta a abordagem 2-Potencial
com duas formas de escolha do candidato na LCR: através de sorteio e através de roleta.
Os resultados são exibidos nas tabelas 6 e 7. O menor tempo de processamento em
todas as instâncias provém da abordagem GRASP sem estratégias de pós-otimização,
representado no gráco pela sigla GRASP1. A abordagem GRASPPR também obteve
um tempo de processamento ligeiramente superior ao da abordagem GRASP1, indicando
que o operador de
Path Relinking
é leve e demanda pouco esforço computacional. A
abordagem 2Potencial obteve um tempo de processamento pouco maior que as outras
duas abordagens.
O menor valor encontrado para o problema, incluindo os resultados do modelo exato
apresentado são tidos como valor de referência para o problema. Como o problema considerado é de minimização, quanto maior o resultado desta operação, pior é a solução encontrada pelo algoritmo. Em relação a essa variável, verica-se que a versão GRASPPR
foi mais eciente, encontrando, de forma geral, os menores valores da abordagem considerada. O GRASP1 também obteve um bom desempenho, com soluções próximas ao
mínimo encontrado. A abordagem 2-Potencial não foi eciente, tendo um desempenho
pior do que o algoritmo com a abordagem tradicional.
Os menores valores médios foram encontrados pela abordagem GRASPPR, que utiliza o operador de
Path-Relinking
como pós-otimização. As abordagens de GRASPPR e
GRASP1 obtiveram soluções médias muito próximas, e com comportamento semelhante.
96
Observe que estas duas abordagens se destacaram em relação a utilização da metaheurística GRASP com abordagem 2Potencial.
É importante ressaltar que quanto maior o número de cidades na instância, maior é a
diferença entre a solução mínima encontrada e a solução média dos algoritmos, indicando
uma perda de eciência na busca dos valores mínimos em instâncias com maior número
de cidades.
Problemas
Instancia nCid nCar
Mauritania10e
10
2
Colombia11e
11
2
Angola12e
12
2
Peru13e
13
2
Libia14e
14
2
BrazilRJ14e
14
2
Congo15e
15
2
Argentina16e
16
2
EUA17e
17
2
Bolivia10e
10
3
AfricaSul11e
11
3
Niger12e
12
3
Mongolia13e
13
3
Indonesia14e
14
3
Argelia15e
15
3
India16e
16
3
China17e
17
3
Etiopia10e
10
4
Mali11e
11
4
Chade12e
12
4
Ira13e
13
4
Mexico14e
14
4
Sudao15e
15
4
Australia16e
16
4
Canada17e
17
4
Arabia14e
14
5
Cazaquistao15e
15
5
Brasil16e
16
5
Russia17e
17
5
BrasilAM26e
25
3
BrasilMG30e
26
3
BrasilCO40e
40
5
att48eA
48
3
att48eb
48
4
berlin52eA
52
3
berlin52eB
52
4
st70eA
70
3
st70eB
70
4
eil76eA
76
3
eil76eB
76
4
371
419
-
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
735
283
428
655
532
492
422
682
783
482
574
619
760
Exato
1898
1657
1689
589
637
790
372
431
636
26535
27719
6514
6130
1804
482
711
810
283
428
655
532
492
422
741
504
487
705
544
384
402
564
610
422
326
490
556
521
230
513
719
Min
GRASP1
Media #vezes
422
30
326
30
490
30
556
25
529
10
233
1
513
28
729
6
639
4
384
30
402
30
564
30
545
1
517
15
492
13
724
5
762
3
283
30
428
30
676
1
541
12
492
30
422
30
777
1
878
1
482
28
611
2
647
3
821
1
392
1
445
1
677
1
27903
1
29658
1
6803
1
6537
1
1902
1
1809
1
1938
1
1734
1
T (s)
10
10
11
15
16
17
17
20
26
10
11
14
13
16
16
21
27
9
13
17
18
17
15
27
30
18
23
24
30
61
88
226
296
349
370
395
869
1163
1069
1235
1588
1853
5667
1801
1689
6154
23268
26522
585
637
781
349
391
599
482
711
817
283
428
655
532
492
422
736
504
487
705
545
384
402
564
610
422
326
490
556
521
230
513
719
Min
GraspPR
Media #vezes
422
30
326
30
490
30
556
25
521
16
232
15
514
24
727
9
642
1
384
30
402
30
564
30
545
15
515
10
493
12
725
5
762
1
283
30
428
30
673
4
540
17
492
29
422
30
775
1
879
1
482
30
607
1
648
3
818
1
366
1
423
1
632
1
26569
1
28678
1
6694
1
6240
1
1867
1
1752
1
1910
1
1692
1
T (s)
10
10
11
15
16
17
17
20
26
11
12
15
15
17
17
22
27
11
15
19
22
19
17
30
32
18
25
25
31
68
98
258
301
352
374
397
884
1180
1092
1257
1607
1833
6390
1817
1707
6063
26663
27125
342
382
597
585
637
775
783
482
730
283
428
655
532
492
422
736
230
513
719
602
384
402
564
543
504
487
705
533
422
326
490
556
Min
Grasp3P
Media #vezes
422
30
326
30
490
30
559
7
533
26
230
28
513
30
727
3
623
3
384
30
402
30
564
30
545
1
519
14
489
21
705
28
744
6
383
30
428
30
673
3
534
20
492
30
422
30
762
1
836
1
482
30
600
2
652
1
814
1
373
1
423
1
648
1
28347
1
29705
1
6807
1
6652
1
1906
1
1792
1
1919
1
1687
1
Tabela 6: Resultados para as instâncias Euclidianas - pCaRS
T (s)
12
12
15
18
20
22
22
25
33
14
16
20
20
24
25
31
36
14
18
22
26
25
22
40
43
30
37
40
47
96
140
355
407
485
499
543
1048
1328
1472
1713
589
638
799
349
394
609
30457
29101
7381
7031
2028
1894
1920
1712
482
727
837
532
492
422
675
283
428
736
504
487
705
545
230
513
719
602
384
402
564
533
422
326
490
556
Min
Grasp3PRol
Media #vezes
422
30
326
30
490
30
560
16
544
5
230
26
520
4
729
2
620
2
386
22
402
30
567
24
545
28
532
8
501
1
721
6
766
1
283
30
428
30
682
1
583
1
492
30
422
30
788
1
924
1
490
15
640
1
658
9
821
1
375
1
439
1
640
2
32545
1
32801
1
7888
1
7294
1
2093
1
1991
1
1976
1
1821
1
T (s)
14
14
17
20
22
23
23
26
33
16
18
22
22
25
26
32
36
26
20
23
27
25
26
40
44
32
28
42
47
86
128
314
370
432
462
491
1028
1317
1293
1494
97
Problemas
Instancia nCid nCar
Mauritania10n
10
2
Colombia11n
11
2
Angola12n
12
2
Peru13n
13
2
Libia14n
14
2
BrazilRJ14n
14
2
Congo15n
15
2
Argentina16n
16
2
EUA17n
17
2
Bolivia10n
10
3
AfricaSul11n
11
3
Niger12n
12
3
Mongolia13n
13
3
Indonesia14n
14
3
Argelia15n
15
3
India16n
16
3
China17n
17
3
Etiopia10n
10
4
Mali11n
11
4
Chade12n
12
4
Ira13n
13
4
Mexico14n
14
4
Sudao15n
15
4
Australia16n
16
4
Canada17n
17
4
Arabia14n
14
5
Cazaquistao15n
15
5
Brasil16n
16
5
Russia17n
17
5
BrasilAM26n
25
3
BrasilMG30n
26
3
BrasilCO40n
40
5
att48nA
48
3
att48nB
48
4
berlin52nA
52
3
berlin52nB
52
4
st70nA
70
3
st70nB
70
4
eil76nA
76
3
eil76nB
76
4
179
-
107
654
697
620
793
551
827
701
843
769
820
403
494
619
734
651
647
1225
1034
638
993
870
444
671
655
953
171
781
116
742
833
688
827
551
522
616
723
646
403
494
649
693
610
769
525
608
448
537
589
306
461
409
502
504
101
573
642
579
448
537
607
551
522
306
461
409
502
504
101
573
Min
Exato
GRASP1
Media #vezes
306
30
461
30
409
30
502
30
504
10
101
30
573
21
645
4
602
1
448
30
537
30
614
1
551
28
522
30
620
2
729
2
659
1
403
30
494
22
650
12
693
24
610
27
773
9
537
1
898
1
705
1
859
1
742
13
790
3
121
1
186
1
469
1
751
1
712
1
1026
1
716
1
1203
1
992
1
1337
1
1118
1
T (s)
10
11
12
14
17
16
16
23
25
8
11
12
16
15
22
23
25
12
16
18
18
18
23
25
33
24
27
23
33
59
93
244
316
441
378
481
807
952
1054
1098
1194
917
938
646
1055
890
618
779
110
173
416
684
742
830
688
834
723
646
403
494
649
693
610
769
525
617
551
522
609
448
537
643
589
306
461
409
502
504
101
573
Min
GraspPR
Media #vezes
306
30
461
30
409
30
502
30
504
7
101
30
573
25
645
3
600
2
448
30
537
30
614
1
551
27
522
28
621
3
728
5
659
2
403
30
494
17
650
20
693
20
610
28
774
4
534
3
886
1
698
1
859
1
742
16
792
1
65
2
180
4
436
2
723
2
673
1
995
1
691
1
1162
1
957
1
1261
1
1001
1
T (s)
10
11
12
14
17
16
15
22
23
10
12
14
18
16
24
24
27
12
16
18
18
19
24
26
34
26
29
24
36
65
103
279
323
420
387
490
916
955
1220
1270
659
923
651
1104
876
1252
938
171
407
648
109
742
778
831
403
494
649
693
610
769
525
825
688
651
723
617
448
537
607
551
522
648
583
306
461
409
502
504
101
573
Min
Grasp3P
Media #vezes
306
30
461
30
409
30
502
25
504
30
101
24
573
29
658
1
590
1
448
30
537
30
608
11
551
30
522
30
620
2
726
5
661
2
403
30
494
26
650
18
693
12
611
21
774
3
537
2
859
2
694
14
855
1
742
25
789
1
112
3
179
2
439
1
736
1
699
1
983
1
695
1
1193
1
967
1
1348
1
1045
1
Tabela 7: Resultados para as instância não Euclidianas - Abordagem GRASP
T (s)
12
13
15
18
21
22
20
26
32
12
17
19
23
22
31
31
36
17
23
26
26
29
34
38
46
38
42
40
52
87
142
350
386
499
463
589
1081
1458
1405
1504
679
1199
979
1361
1091
912
452
738
729
171
780
110
742
834
688
771
534
834
403
494
649
693
610
656
723
620
580
448
537
607
551
522
646
306
461
409
502
504
101
573
Min
Grasp3PRol
Media #vezes
306
30
461
30
409
30
503
18
504
13
101
5
573
30
666
1
588
3
448
30
537
30
613
6
551
26
522
30
628
1
731
1
665
1
403
30
494
22
655
4
694
3
611
24
778
2
545
1
931
1
712
5
870
1
742
24
803
1
117
1
179
1
482
1
799
1
775
1
1077
2
772
1
1305
1
1053
1
1483
1
1189
1
T (s)
13
15
17
20
23
23
22
28
32
14
18
21
25
24
32
33
36
17
22
24
25
27
34
37
46
40
45
41
53
86
135
351
377
499
454
590
1098
1396
1381
1464
98
99
5.2 Algoritmos Meméticos
Os testes preliminares para anação de parâmetros do algoritmo, consideraram três
instâncias da biblioteca pCaRSLib, com um número de cidades na faixa de 9 a 25 e 2 a 4
veículos, onde foram executadas 20 vezes cada uma.
Foram considerados para análise o tamanho da população, variando entre
tamP op ≤ 200,
e também a taxa de recombinação, que variou entre
50 ≤
0, 4 ≤ txRec ≤ 0, 7.
A gura 21 ilustra o comportamento dos parâmetros analisados.
Figura 21: Ajuste dos parâmetros utilizados no algoritmo Memético
Dessa forma, os parâmetros utilizados no algoritmo memético foram uma população
com 150 indivíduos, uma taxa de recombinação
T xRec = 0, 60 e como critério de parada,
foi estabelecido o limite de 100 iterações.
Como pode ser visualizado nas Tabela 8 e 9, todas as soluções ótimas encontradas
pelo GLPK também foram encontrados pelo algoritmo memético, exceto para a instância
Brasil16e onde a solução produzida pelo último apresentou desvio de 2,83 por cento a
partir do primeiro.
Um fato que deve ser observado é que em instâncias maiores, o esforço computacional
gasto nas fases de busca local benecia a pesquisa feita pelo algoritmo memético. As
tabelas mostram que a medida que o tamanho das instâncias aumenta, o desempenho do
algoritmo memético melhora em relação aos resultados obtidos pelo
solver.
A abordagem memética sem a utilização da população de elite obteve um menor tempo
100
de processamento. Já a abordagem memética com população de elite, representado sigla
M A2,
teve um tempo de processamento superior ao utilizado pela primeira abordagem.
Essa diferença ca mais evidente nas maiores instâncias testadas.
Os menores valores encontrados, incluindo os resultados do modelo exato, são tidos
como valores de referência para o problema. Pode-se observar nas instâncias Euclidianas
que, de uma forma geral, os dois algoritmos tiveram um bom desempenho, com o algoritmo
M A2
tendo vantagem nas instâncias maiores, destacando que os menores valores
foram encontrados pela abordagem
M A2.
Contudo, observa-se que as duas estratégias
alcançaram valores mínimos muito próximos. Em relação a abordagem não Euclidiana, a
tendência foi oposta, com o algoritmo
M A1
sendo levemente superior.
É importante ressaltar que quanto maior o número de cidades na instância, maior é a
diferença entre a solução mínima encontrada e a solução média dos algoritmos, indicando
uma perda de eciência na busca dos valores mínimos em instâncias com maior número
de cidades.
101
Tabela 8: Resultados para as instância Euclidianas - Abordagem Memético
Problemas
Instancia nCid nCar
Mauritania10e
10
2
Colombia11e
11
2
Angola12e
12
2
Peru13e
13
2
Libia14e
14
2
BrazilRJ14e
14
2
Congo15e
15
2
Argentina16e
16
2
EUA17e
17
2
Bolivia10e
10
3
AfricaSul11e
11
3
Niger12e
12
3
Mongolia13e
13
3
Indonesia14e
14
3
Argelia15e
15
3
India16e
16
3
China17e
17
3
Etiopia10e
10
4
Mali11e
11
4
Chade12e
12
4
Ira13e
13
4
Mexico14e
14
4
Sudao15e
15
4
Australia16e
16
4
Canada17e
17
4
Arabia14e
14
5
Cazaquistao15e
15
5
Brasil16e
16
5
Russia17e
17
5
BrasilAM26e
25
3
BrasilMG30e
26
3
BrasilCO40e
40
5
att48eA
48
3
att48eb
48
4
berlin52eA
52
3
berlin52eB
52
4
st70eA
70
3
st70eB
70
4
eil76eA
76
3
eil76eB
76
4
Exato
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
735
283
428
655
532
492
422
682
783
482
574
619
760
371
419
-
Min
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
728
283
428
655
532
492
422
682
783
482
574
638
750
341
368
478
19725
22710
5076
5114
1095
1156
1230
959
MA1
Media #vezes
423
23
326
30
490
30
557
26
521
30
230
20
515
19
720
9
603
25
384
30
402
30
564
30
544
1
504
30
487
30
721
19
734
6
283
30
428
30
655
30
542
4
492
30
422
30
684
22
803
2
482
30
578
19
646
1
784
2
344
17
372
3
482
1
20047
1
23726
1
5314
1
5265
1
1143
1
1206
1
1268
1
986
2
T (s)
9
6
10
17
17
19
18
21
28
9
12
16
16
19
18
22
33
8
14
23
24
16
13
38
36
14
29
24
34
84
132
283
369
422
461
430
1180
1370
1385
1176
Min
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
728
283
428
655
532
492
422
682
783
482
574
637
750
341
368
478
19725
21361
4996
5040
1089
1141
1237
951
MA2
Media #vezes
422
29
326
30
490
30
556
30
521
30
230
19
517
12
720
11
603
24
384
30
402
30
564
24
544
1
505
26
487
30
743
6
730
17
283
30
428
30
656
28
542
7
492
30
422
30
692
12
801
2
482
30
581
15
645
1
782
4
341
25
370
12
481
2
20114
3
23202
3
5195
2
5302
1
1149
1
1201
1
1279
1
981
1
T (s)
16
11
18
27
28
34
30
35
44
15
19
26
26
32
29
40
53
13
24
40
42
25
21
61
60
25
47
39
63
145
221
443
768
886
984
986
1585
2255
2707
2095
102
Tabela 9: Resultados para as instância não Euclidianas - Abordagem Memético
Problemas
Instancia nCid nCar
Mauritania10n
10
2
Colombia11n
11
2
Angola12n
12
2
Peru13n
13
2
Libia14n
14
2
BrazilRJ14n
14
2
Congo15n
15
2
Argentina16n
16
2
EUA17n
17
2
Bolivia10n
10
3
AfricaSul11n
11
3
Niger12n
12
3
Mongolia13n
13
3
Indonesia14n
14
3
Argelia15n
15
3
India16n
16
3
China17n
17
3
Etiopia10n
10
4
Mali11n
11
4
Chade12n
12
4
Ira13n
13
4
Mexico14n
14
4
Sudao15n
15
4
Australia16n
16
4
Canada17n
17
4
Arabia14n
14
5
Cazaquistao15n
15
5
Brasil16n
16
5
Russia17n
17
5
BrasilAM26n
25
3
BrasilMG30n
26
3
BrasilCO40n
40
5
att48nA
48
3
att48nB
48
4
berlin52nA
52
3
berlin52nB
52
4
st70nA
70
3
st70nB
70
4
eil76nA
76
3
eil76nB
76
4
Exato
306
461
409
502
504
101
573
647
579
448
537
607
551
522
619
734
651
403
494
654
697
620
793
551
827
701
843
769
820
107
179
-
Min
306
461
409
502
504
101
573
642
579
448
537
607
551
522
616
723
638
403
494
649
693
610
769
525
824
692
830
742
778
107
160
329
528
447
676
441
663
510
783
507
Media
306
461
409
502
504
101
573
643
579
455
537
608
551
522
616
723
638
403
494
449
693
610
775
531
825
693
832
742
778
108
161
335
533
462
688
445
682
530
798
527
MA1
#vezes
30
30
30
30
30
30
30
18
22
30
18
23
30
30
30
30
18
30
30
30
22
30
10
20
4
2
13
30
30
6
5
2
2
1
2
1
2
1
1
1
T (s)
7
8
11
12
17
17
15
18
24
7
10
18
20
17
26
26
25
10
17
19
16
17
26
27
40
28
30
24
32
77
113
355
419
532
472
525
1353
1799
1563
1605
Min
306
461
409
502
504
101
573
642
579
448
537
607
551
522
616
723
638
403
494
649
693
610
769
525
824
692
830
742
778
107
160
328
528
450
676
442
656
501
790
506
Media
306
461
409
502
504
101
573
644
579
448
537
609
551
522
617
724
638
403
494
649
693
610
780
543
830
696
835
742
783
108
161
338
537
465
695
449
684
542
801
530
MA2
#vezes
30
30
30
30
30
30
30
9
27
30
21
22
30
30
27
29
12
30
30
30
8
30
2
6
10
1
13
29
17
10
5
1
1
2
1
1
1
1
1
1
T (s)
12
13
17
19
29
28
24
29
38
12
17
30
34
27
41
43
40
17
28
29
25
27
41
41
62
43
48
38
49
118
170
542
747
948
858
893
2197
3014
2384
2434
103
5.3 Algoritmos Transgenéticos
Em consonância com as demais estratégias analizadas, pode-se observar a partir dos
dados apresentados, que os algoritmos com abordagem transgenética propostos também
tiveram uma boa adaptação aos problemas analisados. As abordagens variaram principalmente na utilização do operador plasmídeo, onde foram propostas três abordagens
diferentes nos quatro algoritmos propostos. O tempo de processamento e a qualidade da
solução variaram de acordo com cada algoritmo proposto.
Os resultados são apresentados nas tabelas 10 e 11. O menor tempo de processamento
em todas as instâncias provém da abordagem transgenética em sua formulação tradicional,
representado na tabela pela sigla
T A1.
A abordagem
T ARep,
também obteve um baixo
tempo de processamento, sendo levemente superior a primeira abordagem.
O menor valor encontrado para o problema, incluindo os resultados do modelo exato
apresentado são tidos como valor de referência para o problema. Verica-se que o desempenho da abordagem
T A1 cou bem abaixo do esperado. Esse fator se deve, parcialmente,
a falta de informações
a priori,
o que deixa o Banco de Informações Genéticas com so-
luções iniciais de baixa potencialidade, contribuindo para o fraco desempenho geral do
algoritmo.
Já a abordagem
T ARep
teve um desempenho satisfatório. Um fato que merece des-
taque é que, dentre todas as abordagens analisadas, o
encontrar o ótimo para a instância
Brasil16e,
T ARep
foi o único que conseguiu
encontrada também pelo GLPK.
Observa-se a efetividade da hibridização com a recombinação, pois ao utilizar apenas
o plasmídeo, temos uma média de soluções com qualidade inferior ao utilizado no
T A2.
Esta abordagem utilizou tempo de processamento semelhente a abordagem original, e
garantiu soluções médias mais próximas aos valores mínimos encontrados pelos algoritmos
estudados.
É importante ressaltar que quanto maior o número de cidades na instância, maior é a
diferença entre a solução mínima encontrada e a solução média dos algoritmos, indicando
uma perda de eciência na busca dos valores mínimos em instâncias com maior número
de cidades. Nesse quesito, o desempenho do algoritmo
T ARep
destacou-se.
104
Tabela 10: Resultados para as instância Euclidianas - Abordagem Transgenético
Problemas
Instancia nCid nCar
Mauritania10e
10
2
Colombia11e
11
2
Angola12e
12
2
Peru13e
13
2
Libia14e
14
2
BrazilRJ14e
14
2
Congo15e
15
2
Argentina16e
16
2
EUA17e
17
2
Bolivia10e
10
3
AfricaSul11e
11
3
Niger12e
12
3
Mongolia13e
13
3
Indonesia14e
14
3
Argelia15e
15
3
India16e
16
3
China17e
17
3
Etiopia10e
10
4
Mali11e
11
4
Chade12e
12
4
Ira13e
13
4
Mexico14e
14
4
Sudao15e
15
4
Australia16e
16
4
Canada17e
17
4
Arabia14e
14
5
Cazaquistao15e
15
5
Brasil16e
16
5
Russia17e
17
5
BrasilAM26e
25
3
BrasilMG30e
26
3
BrasilCO40e
40
5
att48eA
48
3
att48eb
48
4
berlin52eA
52
3
berlin52eB
52
4
st70eA
70
3
st70eB
70
4
eil76eA
76
3
eil76eB
76
4
Exato
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
735
283
428
655
532
492
422
682
783
482
574
619
760
371
419
-
Min
437
326
490
567
535
234
550
747
668
392
402
564
549
550
517
826
736
283
428
655
549
492
424
745
886
482
634
638
822
361
377
486
25775
25809
5515
5342
1355
1347
1509
1240
TA1
Media #vezes
437
30
326
30
490
30
567
30
28
21
234
30
550
30
749
27
668
30
398
22
402
30
602
4
549
30
574
1
540
11
845
4
741
22
283
30
428
30
692
9
666
1
507
1
431
1
790
3
945
10
558
1
717
4
658
3
856
8
361
30
383
7
494
3
25779
8
25892
4
5599
1
5668
2
1396
1
1349
3
1525
1
1270
1
T (s)
26
13
28
59
61
82
64
85
134
23
32
51
48
66
54
106
145
17
36
65
78
43
32
145
147
39
84
69
129
521
872
2208
5187
4823
7210
6180
27064
36126
36838
30274
Min
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
728
283
428
655
532
492
422
682
783
482
574
619
750
338
369
461
18785
20549
4912
4874
1109
1111
1257
979
TARep
Media #vezes
422
30
326
30
490
30
557
18
521
30
230
26
513
28
719
26
602
30
384
30
402
30
564
30
544
3
504
28
487
30
721
9
732
8
283
30
428
30
657
25
534
20
492
30
422
30
682
30
785
21
482
30
580
14
628
11
773
13
339
13
372
3
466
2
20314
1
20610
6
4936
1
4966
1
1140
1
1131
1
1267
1
991
1
T (s)
26
15
28
59
62
83
65
93
147
23
32
51
48
67
55
110
148
17
36
63
79
40
32
149
151
63
85
72
124
546
880
2188
6771
5338
7331
6989
27093
31801
40708
32104
105
Tabela 11: Resultados para as instância não Euclidianas - Abordagem Transgenético
Problemas
Instancia nCid nCar
Mauritania10n
10
2
Colombia11n
11
2
Angola12n
12
2
Peru13n
13
2
Libia14n
14
2
BrazilRJ14n
14
2
Congo15n
15
2
Argentina16n
16
2
EUA17n
17
2
Bolivia10n
10
3
AfricaSul11n
11
3
Niger12n
12
3
Mongolia13n
13
3
Indonesia14n
14
3
Argelia15n
15
3
India16n
16
3
China17n
17
3
Etiopia10n
10
4
Mali11n
11
4
Chade12n
12
4
Ira13n
13
4
Mexico14n
14
4
Sudao15n
15
4
Australia16n
16
4
Canada17n
17
4
Arabia14n
14
5
Cazaquistao15n
15
5
Brasil16n
16
5
Russia17n
17
5
BrasilAM26n
25
3
BrasilMG30n
26
3
BrasilCO40n
40
5
att48nA
48
3
att48nB
48
4
berlin52nA
52
3
berlin52nB
52
4
st70nA
70
3
st70nB
70
4
eil76nA
76
3
eil76nB
76
4
Exato
306
461
409
502
504
101
573
647
579
448
537
607
551
522
619
734
651
403
494
654
697
620
793
551
827
701
843
769
820
107
179
-
Min
306
465
409
516
504
103
607
685
618
449
538
634
551
532
633
733
648
403
494
649
694
623
793
562
837
718
851
743
875
107
160
328
679
622
899
588
923
801
1068
747
Media
306
467
409
516
504
103
607
685
618
453
557
657
556
532
646
747
676
403
494
660
736
645
806
576
1023
763
905
752
916
107
160
332
695
658
940
618
944
835
1143
797
TA1
#vezes
30
26
30
28
30
30
29
28
29
13
4
4
13
30
2
21
3
30
30
11
2
7
1
8
1
2
1
11
1
30
24
1
1
1
1
1
1
1
1
1
T (s)
18
24
31
48
58
66
48
80
124
17
38
47
71
53
112
100
126
24
51
55
47
48
86
88
149
88
105
68
119
509
879
3507
7728
8194
9604
8216
34378
44901
39239
34974
Min
306
461
409
502
504
101
573
642
580
448
537
607
551
522
616
723
639
403
494
649
693
610
769
525
824
688
830
742
778
107
160
333
526
452
692
460
671
514
792
517
TARep
Media #vezes
306
30
461
30
409
30
506
1
504
30
101
30
573
30
644
11
605
1
448
29
537
27
608
23
551
30
522
29
616
28
723
28
644
1
403
30
494
30
649
30
693
24
615
18
769
30
525
29
825
19
691
12
835
5
742
30
778
30
107
29
161
16
338
1
533
1
460
1
700
1
463
1
680
1
520
1
797
1
521
1
T (s)
18
25
31
52
58
66
49
81
125
18
40
48
74
53
115
103
125
24
51
56
48
50
88
94
154
208
110
67
128
480
838
3271
6651
7670
8728
8900
32724
41455
32944
33387
106
5.3.1 Algoritmo Evolucionário Híbrido
O último dos algoritmos propostos foi o algoritmo evolucionário híbrido. Os parâmetros de execução obedeceram as mesmas condições consideradas para o algoritmo memético.
De forma a aferir a eciência desta abordagem, denominada
EH1,
efetuamos experi-
mentos numéricos nas mesmas condições e instâncias efetuadas anteriormente.
O tempo de execução do algoritmo foi intermediário, entre os considerados para a
abordagem memética e a abordagem transgenética.
As soluções mínimas encontradas para as instâncias Euclidianas foram, no geral, melhores que as demais abordagens. A solução média encontrada também obteve destaque
em relação às outras metaheurísticas consideradas.
O bom desempenho se extendeu às instâncias não Euclidianas, mostrando que o algoritmo é competitivo em relação às abordagens consideradas.
107
Tabela 12: Resultados para as instância Euclidianas - EH1
Exato - GLPK
Problema
n
|C|
Mauritania10e
10
2
Colombia11e
11
2
Angola12e
12
2
Peru13e
13
2
Libia14e
14
2
BrazilRJ14e
14
2
Congo15e
15
2
Argentina16e
16
2
EUA17e
17
2
Bolivia10e
10
3
AfricaSul11e
11
3
Niger12e
12
3
Mongolia13e
13
3
Indonesia14e
14
3
Argelia15e
15
3
India16e
16
3
EH1
Exato
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
China17e
17
3
Etiopia10e
10
4
Mali11e
11
4
Chade12e
12
4
Ira13e
13
4
Mexico14e
14
4
Sudao15e
15
4
Australia16e
16
4
Canada17e
17
4
Arabia14e
14
5
Cazaquistao15e
15
5
Brasil16e
16
5
283
428
655
532
492
422
682
783
482
574
619
735
Russia17e
17
5
760
BrasilAM26e
25
3
371
BrasilMG30e
26
3
419
BrasilCO40e
40
5
-
att48eA
48
3
-
att48eb
48
4
-
berlin52eA
52
3
-
berlin52eB
52
4
-
st70eA
70
3
-
st70eB
70
4
-
eil76eA
76
3
-
eil76eB
76
4
-
Min
422
326
490
556
521
230
513
719
602
384
402
564
545
504
487
705
728
283
428
655
532
492
422
682
783
482
574
Média
#
vezes
T(s)
422
30
19
326
30
10
490
30
20
557
23
39
521
30
40
230
25
51
517
15
41
720
12
50
605
17
78
384
30
16
402
30
22
564
30
34
545
30
34
504
29
38
487
29
35
715
18
54
729
22
83
283
30
13
428
30
25
655
30
47
535
22
50
492
30
28
422
30
21
685
17
93
804
1
88
482
30
23
577
21
56
637
644
5
44
750
786
2
79
341
10
278
372
1
431
480
1
1066
19900
8
2388
21077
10
2583
4921
2
3762
4997
1
2772
1142
1
8507
1131
2
12209
1231
1
17643
972
1
10087
338
368
461
19725
20549
4879
4872
1114
1131
1207
948
108
Tabela 13: Resultados para as instância não-Euclidianas - EH1
Exato - GLPK
Problema
EH1
n
|C|
Exato
Mauritania10n
10
2
Colombia11n
11
2
Angola12n
12
2
Peru13n
13
2
Libia14n
14
2
BrazilRJ14n
14
2
Congo15n
15
2
306
461
409
502
504
101
573
Argentina16n
16
2
647
EUA17n
17
2
Mongolia13n
13
3
Indonesia14n
14
3
579
448
537
607
551
522
Argelia15n
15
3
619
India16n
16
3
734
Bolivia10n
10
3
AfricaSul11n
11
3
Niger12n
12
3
China17n
17
3
Etiopia10n
10
4
Mali11n
11
4
651
403
494
Chade12n
12
4
654
Ira13n
13
4
697
Mexico14n
14
4
620
Sudao15n
15
4
793
Australia16n
16
4
551
Canada17n
17
4
827
Arabia14n
14
5
701
Cazaquistao15n
15
5
843
Brasil16n
16
5
769
Russia17n
17
5
820
BrasilAM26n
25
3
107
BrasilMG30n
26
3
179
BrasilCO40n
40
5
-
att48nA
48
3
-
att48nB
48
4
-
berlin52nA
52
3
-
berlin52nB
52
4
-
st70nA
70
3
-
st70nB
70
4
-
eil76nA
76
3
-
eil76nB
76
4
-
Min
306
461
409
502
504
101
573
642
579
448
537
607
551
522
616
723
638
403
494
649
693
610
769
525
824
688
830
742
778
107
160
328
527
439
677
441
653
501
777
502
Média
#
vezes
T(s)
306
30
13
461
30
15
409
30
20
502
25
22
504
30
39
101
30
39
573
30
32
645
6
39
579
24
59
448
29
11
537
21
17
609
21
41
551
30
43
522
29
35
616
30
61
723
30
62
638
27
51
403
30
17
494
30
34
649
30
36
693
17
27
612
24
28
776
6
50
526
27
51
825
16
92
693
1
53
836
6
56
742
29
42
779
26
58
107
20
251
160
16
303
335
1
1392
532
2
3118
458
1
4031
692
1
4149
444
6
3654
669
1
15211
517
1
22155
789
1
17577
510
1
15353
109
5.4 Análise Comparativa de Resultados
O teste estatístico não paramétrico para esses indicadores é feito através do método
de Kruskal-Wallis (KRUSKAL;
de signicância de
WALLIS,
1952). O teste foi realizado considerando um nível
5%.
O teste de Kruskal-Wallis, é utilizado para avaliação do desempenho de cada algoritmo
em relação ao
gap
obtido na solução dos problemas. O
gap
representa o erro percetual da
solução encontrada pelo algoritmo em relação ao melhor valor encontrado entre todas as
abordagens. Como fontes de variação foram analisados tanto a abordagem utilizada (no
caso, a metaheurística), como também o método (cada algoritmo proposto). As variáveis
escolhidas para análise foram o tempo médio, o valor mínimo encontrado e a média dos
valores encontrados pelos algoritmos.
5.4.1 Instâncias Euclidianas
Os resultados para as instâncias Euclidianas são apresentados na tabela a seguir:
Tabela 14: Saída do teste Kruskal-Wallis - Problemas Euclidianos
EH1
Grasp1
graspPR
grasp3P
grasp3PRol
MA1
MA2
EH1
Grasp1
graspPR
grasp3P
grasp3PRol
MA1
MA2
TA1
-
TA1
TARep
0,000000
0,000000
0,000000
0,000000
0,000037
0,000018
0,000000
1,000000
-
1,000000
0,704304
0,024199
0,000000
0,000000
0,000000
0,000000
-
1,000000
0,000093
0,000000
0,000000
0,000000
0,000000
-
0,000000
0,000000
0,000000
0,000000
0,000000
-
0,000000
0,000000
0,000005
0,000000
-
1,000000
0,000000
0,000000
-
0,000000
0,000000
-
0,000000
TARep
Os resultados da tabela 15 mostram que todos os algoritmos caram na mesma categoria de classicação. Contudo, é possível vericar o melhor desempenho do algoritmo
T A2
(com reprodução), mesmo que a diferença não seja signicativa no teste realizado.
Observa-se a grande proximidade dos resultados encontrados pelos quatro primeiros algoritmos. Por outro lado, os cinco últimos algoritmos também tiveram desempenho semelhante entre si.
-
110
Figura 22: Ajuste dos parâmetros utilizados no algoritmo GRASP
Pode-se observar que o teste classicou todas as abordagens no mesmo nível, ou
seja, não houve diferença estatítica signicativa de acordo com os parâmetros denidos.
Contudo, observa-se que o desempenho do algoritmo evolutivo híbrido foi melhor que as
demais abordagens, seguida pela abordagem memética e pela transgenética. Por últimos
tempos a abordagem GRASP, que, para esse parâmetro obteve os piores resultados.
5.4.2 Instâncias não Euclidianas
Para as instâncias não Euclidianas, o primeiro teste apresentado analisa a variável
min, que diz respeito ao valor mínimo encontrado por cada abordagem. Os resultados são
apresentados na tabela a seguir:
A comparação entre todos os algoritmos considerados para essa variável é apresentada
na tabela 19 a seguir:
111
Tabela 15: Saída do teste Kruskal-Wallis - Problemas não Euclidianos
EH1
Grasp1
graspPR
grasp3P
grasp3PRol
MA1
MA2
TA1
EH1
Grasp1
graspPR
grasp3P
-
TARep
0,000000
0,000000
0,000000
0,000000
0,034105
0,000000
0,000000
0,165996
-
1,000000
0,243921
1,000000
0,000000
0,000000
0,000000
0,000000
-
0,000770
1,000000
0,000000
0,000000
0,000000
0,000000
-
0,057230
0,000000
0,000000
0,000000
0,000000
-
0,000000
0,000000
0,000000
0,000000
-
0,426666
0,000000
1,000000
-
0,000000
0,133498
-
0,000000
grasp3PRol
MA1
MA2
TA1
-
TARep
Os resultados da tabela 19 mostram que todos os algoritmos caram na mesma categoria de classicação. Contudo, é possível vericar que o desempenho das quatro primeiras
abordagens não apresentou quase nenhuma diferença. A aboradgem Grasp obteve o pior
desempenho entre os algoritmos considerados.
Figura 23: Ajuste dos parâmetros utilizados no algoritmo GRASP
Pode-se observar que o teste classicou todas as abordagens Evolutivo Híbrido e Memético no mesmo nível. A abordagem transgenética cou classicada entre os dois níveis,
e o Grasp obteve o pior desempenho entre as abordagens para a variável considerada.
112
5.4.3 Considerações sobre os resultados
De uma forma geral, os algoritmos analisados tiveram uma boa adaptação para as
instâncias menores, tanto Euclidianas, quanto não Euclidianas. Ao aumentar o tamanho
da instância, os algoritmos vão perdendo eciência na busca pelo valor ótimo, e tendem
a demandar maior tempo de processamento. A perda de eciência é mais notória nas
instâncias não Euclidianas.
Para as instâncias Euclidianas, o algoritmo
T ARep
obteve o melhor resultado qua-
litativo, porém demandou um maior tempo de processamento em relação aos demais
algoritmos. Na mesma categoria, tivemos o algoritmo
EH1
proposto e os algoritmos Me-
méticos, esses últimos com uma demanda menor de tempo em relação as outras duas
abordagens citadas.
A abordagem Grasp obteve o pior desempenho qualitativo, porém, demandou o menor
tempo de processamento entre todas as abordagens. O Algoritmo
Grasp2P Rol não obteve
resultados qualitativos satisfatórios, indicando que a abordagem 2-Potencial com escolha
através de roleta não foi bem adaptada ao problema.
Para as instâncias não Euclidianas, no aspecto qualitativo das soluções encontradas
vericamos uma variação na disputa entre os algoritmos
M A1, EH1 e T ARep, onde todos
caram bem posicionados nas variáveis que indicam essa característica. Novamente, o
desempenho da abordagem Grasp foi inferior às demais consideradas.
Em relação ao tempo de processamento, observamos que as abordagens Grasp e Memética tiveram uma menor demanda de processamento, o que reetiu no tempo médio
gasto por essas abordagens. As abordagens Evolutivo Híbrido e Transgenética foram na
contramão e necessitaram de um maior tempo de processamento quando comparadas às
demais abordagens.
De forma geral, a abordagem memética proposta foi competitiva em termos de qualidade as soluções encontradas e tempo médio de processamento. O Algoritmo Evolutivo
Híbrido obteve um desempenho qualitativo ligeiramente melhor em relação aos algoritmos meméticos nas instâncias Euclidianas e um desempenho similar para as instâncias
não Euclidianas, porém demandou um tempo de processamento maior. Na abordagem
transgenética, o algoritmo
T ARep
obteve vantagens em relação ao outro proposto para
essa abordagem, tanto em uma análise qualitativa, quanto analisando o tempo de processamento gasto.
Entre as abordagens, podemos eleger o GraspPR como o melhor Grasp proposto.
113
A estratégia de utilização de uma população de elite melhorou também o desempenho
do algoritmo memético, fazendo com que o
M A2
se destacasse ligeiramente. O algoritmo
transgenético em sua formulação tradicional não obteve um bom desempenho. Contudo, a
modicação proposta no
T ARep obteve o efeito desejado e melhorou consideravelmente o
desempenho. O algoritmo
EH1 proposto obteve um bom desempenho entre os algoritmos
evolucionários propostos, mostrando a boa adequação ao problema proposto. A seguir,
apresentamos os resultados dos melhores algoritmos de cada abordagem.
Problemas
Instancia nCid nCar
Mauritania10e
10
2
Colombia11e
11
2
Angola12e
12
2
Peru13e
13
2
Libia14e
14
2
BrazilRJ14e
14
2
Congo15e
15
2
Argentina16e
16
2
EUA17e
17
2
Bolivia10e
10
3
AfricaSul11e
11
3
Niger12e
12
3
Mongolia13e
13
3
Indonesia14e
14
3
Argelia15e
15
3
India16e
16
3
China17e
17
3
Etiopia10e
10
4
Mali11e
11
4
Chade12e
12
4
Ira13e
13
4
Mexico14e
14
4
Sudao15e
15
4
Australia16e
16
4
Canada17e
17
4
Arabia14e
14
5
Cazaquistao15e
15
5
Brasil16e
16
5
Russia17e
17
5
BrasilAM26e
25
3
BrasilMG30e
26
3
BrasilCO40e
40
5
att48eA
48
3
att48eb
48
4
berlin52eA
52
3
berlin52eB
52
4
st70eA
70
3
st70eB
70
4
eil76eA
76
3
eil76eB
76
4
760
371
419
-
283
428
655
532
492
422
682
783
482
574
619
735
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
Exato
585
637
781
349
391
599
23268
26522
6154
5667
1801
1689
1853
1588
482
711
817
283
428
655
532
492
422
736
504
487
705
545
384
402
564
610
422
326
490
556
521
230
513
719
Min
GRASPPR
Media #vezes
422
30
326
30
490
30
556
25
521
16
232
15
514
24
727
9
642
1
384
30
402
30
564
30
545
15
515
10
493
12
725
5
762
1
283
30
428
30
673
4
540
17
492
29
422
30
775
1
879
1
482
30
607
1
648
3
818
1
366
1
423
1
632
1
26569
1
28678
1
6694
1
6240
1
1867
1
1752
1
1910
1
1692
1
T (s)
10
10
11
15
16
17
17
20
26
11
12
15
15
17
17
22
27
11
15
19
22
19
17
30
32
18
25
25
31
68
98
258
301
352
374
397
884
1180
1092
1257
1141
1237
951
1089
478
19725
21361
4996
5040
368
341
750
637
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
728
283
428
655
532
492
422
682
783
482
574
Min
MA2
Media #vezes
422
29
326
30
490
30
556
30
521
30
230
19
517
12
720
11
603
24
384
30
402
30
564
24
544
1
505
26
487
30
743
6
730
17
283
30
428
30
656
28
542
7
492
30
422
30
692
12
801
2
482
30
581
15
645
1
782
4
341
25
370
12
481
2
20114
3
23202
3
5195
2
5302
1
1149
1
1201
1
1279
1
981
1
T (s)
16
11
18
27
28
34
30
35
44
15
19
26
26
32
29
40
53
13
24
40
42
25
21
61
60
25
47
39
63
145
221
443
768
886
984
986
1585
2255
2707
2095
1257
979
1111
4912
4874
1109
461
18785
20549
369
422
326
490
556
521
230
513
719
602
384
402
564
543
504
487
705
728
283
428
655
532
492
422
682
783
482
574
619
750
338
Min
TARep
Media #vezes
422
30
326
30
490
30
557
18
521
30
230
26
513
28
719
26
602
30
384
30
402
30
564
30
544
3
504
28
487
30
721
9
732
8
283
30
428
30
657
25
534
20
492
30
422
30
682
30
785
21
482
30
580
14
628
11
773
13
339
13
372
3
466
2
20314
1
20610
6
4936
1
4966
1
1140
1
1131
1
1267
1
991
1
Tabela 16: Resultados para as instâncias Euclidianas - pCaRS
T (s)
26
15
28
59
62
83
65
93
147
23
32
51
48
67
55
110
148
17
36
63
79
40
32
149
151
63
85
72
124
546
880
2188
6771
5338
7331
6989
27093
31801
40708
32104
1207
948
1114
1131
20549
4879
4872
19725
750
338
368
461
637
504
487
705
728
283
428
655
532
492
422
682
783
482
574
545
422
326
490
556
521
230
513
719
602
384
402
564
Min
EH1
Media #vezes
422
30
326
30
490
30
557
23
521
30
230
25
517
15
720
12
605
17
384
30
402
30
564
30
545
30
504
29
487
29
715
18
729
22
283
30
428
30
655
30
535
22
492
30
422
30
685
17
804
1
482
30
577
21
644
5
786
2
341
10
372
1
480
1
19900
8
21077
10
4921
2
4997
1
1142
1
1131
2
1231
1
972
1
T (s)
19
10
20
39
40
51
41
50
78
16
22
34
34
38
35
54
83
13
25
47
50
28
21
93
88
23
56
44
79
278
431
1066
2388
2583
3762
2772
8507
12209
17643
10087
114
Problemas
Instancia nCid nCar
Mauritania10n
10
2
Colombia11n
11
2
Angola12n
12
2
Peru13n
13
2
Libia14n
14
2
BrazilRJ14n
14
2
Congo15n
15
2
Argentina16n
16
2
EUA17n
17
2
Bolivia10n
10
3
AfricaSul11n
11
3
Niger12n
12
3
Mongolia13n
13
3
Indonesia14n
14
3
Argelia15n
15
3
India16n
16
3
China17n
17
3
Etiopia10n
10
4
Mali11n
11
4
Chade12n
12
4
Ira13n
13
4
Mexico14n
14
4
Sudao15n
15
4
Australia16n
16
4
Canada17n
17
4
Arabia14n
14
5
Cazaquistao15n
15
5
Brasil16n
16
5
Russia17n
17
5
BrasilAM26n
25
3
BrasilMG30n
26
3
BrasilCO40n
40
5
att48nA
48
3
att48nB
48
4
berlin52nA
52
3
berlin52nB
52
4
st70nA
70
3
st70nB
70
4
eil76nA
76
3
eil76nB
76
4
179
-
107
654
697
620
793
551
827
701
843
769
820
403
494
619
734
651
579
448
537
607
551
522
647
306
461
409
502
504
101
573
Exato
779
110
173
416
684
618
938
646
1055
890
1194
917
688
830
742
834
403
494
649
693
610
769
525
646
723
617
551
522
609
448
537
643
589
306
461
409
502
504
101
573
Min
GRASPPR
Media #vezes
306
30
461
30
409
30
502
30
504
7
101
30
573
25
645
3
600
2
448
30
537
30
614
1
551
27
522
28
621
3
728
5
659
2
403
30
494
17
650
20
693
20
610
28
774
4
534
3
886
1
698
1
859
1
742
16
792
1
65
2
180
4
436
2
723
2
673
1
995
1
691
1
1162
1
957
1
1261
1
1001
1
T (s)
10
11
12
14
17
16
15
22
23
10
12
14
18
16
24
24
27
12
16
18
18
19
24
26
34
26
29
24
36
65
103
279
323
420
387
490
916
955
1220
1270
790
506
501
442
656
676
528
450
830
742
778
107
160
328
692
306
461
409
502
504
101
573
642
579
448
537
607
551
522
616
723
638
403
494
649
693
610
769
525
824
Min
Media
306
461
409
502
504
101
573
644
579
448
537
609
551
522
617
724
638
403
494
649
693
610
780
543
830
696
835
742
783
108
161
338
537
465
695
449
684
542
801
530
MA2
#vezes
30
30
30
30
30
30
30
9
27
30
21
22
30
30
27
29
12
30
30
30
8
30
2
6
10
1
13
29
17
10
5
1
1
2
1
1
1
1
1
1
T (s)
12
13
17
19
29
28
24
29
38
12
17
30
34
27
41
43
40
17
28
29
25
27
41
41
62
43
48
38
49
118
170
542
747
948
858
893
2197
3014
2384
2434
452
692
460
671
514
792
517
526
333
403
494
649
693
610
769
525
824
688
830
742
778
107
160
639
448
537
607
551
522
616
723
580
306
461
409
502
504
101
573
642
Min
TARep
Media #vezes
306
30
461
30
409
30
506
1
504
30
101
30
573
30
644
11
605
1
448
29
537
27
608
23
551
30
522
29
616
28
723
28
644
1
403
30
494
30
649
30
693
24
615
18
769
30
525
29
825
19
691
12
835
5
742
30
778
30
107
29
161
16
338
1
533
1
460
1
700
1
463
1
680
1
520
1
797
1
521
1
Tabela 17: Resultados para as instância não Euclidianas
T (s)
18
25
31
52
58
66
49
81
125
18
40
48
74
53
115
103
125
24
51
56
48
50
88
94
154
208
110
67
128
480
838
3271
6651
7670
8728
8900
32724
41455
32944
33387
441
653
501
777
502
677
439
527
306
461
409
502
504
101
573
642
579
448
537
607
551
522
616
723
638
403
494
649
693
610
769
525
824
688
830
742
778
107
160
328
Min
Media
306
461
409
502
504
101
573
645
579
448
537
609
551
522
616
723
638
403
494
649
693
612
776
526
825
693
836
742
779
107
160
335
532
458
692
444
669
517
789
510
EH1
#vezes
30
30
30
25
30
30
30
6
24
29
21
21
30
29
30
30
27
30
30
30
17
24
6
27
16
1
6
29
26
20
16
1
2
1
1
6
1
1
1
1
T (s)
13
15
20
22
39
39
32
39
59
11
17
41
43
35
61
62
51
17
34
36
27
28
50
51
92
53
56
42
58
251
303
1392
3118
4031
4149
3654
15211
22155
17577
15353
115
116
6
Considerações Finais
O objeto de estudo do presente trabalho, o problema denominado
com Coleta de Prêmios
Caixeiro Alugador
é novo na literatura. Nesse estudo foram propostas e adaptadas
métodos e técnicas inovadoras para resolução do problema. Consequentemente, lidou com
o desao de criar as primeiras abordagens, modelos, métodos e algoritmos especializados
em sua resolução, buscando garantir que as soluções propostas estão de acordo com o
estado da arte em programação heurística.
O presente trabalho apresentou uma revisão bibliográca de trabalhos relacionados,
tais como outros problemas de roteamento de veículos, problemas relacionados a coleta
de bônus, trabalhos relacionados ao contexto turístico e o problema do caixeiro alugador
em si, do qual este trabalho é derivado.
O problema pCaRS proposto no presente trabalho possui aplicações explícitas relativas
ao segmento turístico associado à locação de veículos para visitar os pontos de interesse.
Além disso, em situações em que o turista não pode visitar todas as cidades, a atribuição
de um índice de satisfação presumida em visitar a cidade é de fundamental importância
para que a escolha possa ser feita da maneira mais econômica dentro das opções de maior
prioridade do turista.
Foram propostas modelos e estratégias exatas e heurísticas para a resolução do problema. Com a nalidade de vericar a efetividade das abordagens de solução propostas,
foi adaptado o banco de instâncias do problema CaRS, com a inclusão da informação
relativa à satisfação presumida de vistida da cidade, dando origem a um novo banco de
instâncias, denomindado pCaRSLib.
Algumas opções de modelagem matemática para os problemas CaRS e pCaRS foram
propostas. O contexto analisado variou entre a concepção básica da formulação do caixeiro, considerando as ideias de (BECKMAN;
FULKERSON; JOHNSON,
KOOPMANS,
1957) e também de (DANTZIG;
1954). Os modelos possuem características não lineares em todas
as formulações apresentadas. Por esse motivo, foram analisadas três formas de linearização
117
aplicadas à resolução do problema, com experimentos computacionais associados.
Foram analisadas quatro metaheurísticas para a solução do problema, onde operadores especícos para o problema pCars foram desenvolvidos e adaptados para a utilização
nas mesmas. As metaheurísticas analisadas neste trabalho foram GRASP com VNS, algoritmos meméticos, transgenética computacional e uma abordagem evolutiva híbrida.
Para a abordagem GRASP-VNS, analisamos quatro variações onde apenas a primeira
versão não contou com uma fase de pós-otimização. Nas demais, analisamos o operador
de
path-relinking. A segunda versão do algoritmo mostrou que o operador foi eciente na
melhoria da solução ótima encontrada pelo algoritmo, a um custo de tempo de processamento relativamente baixo. Foi proposta uma nova abordagem de montagem da Lista de
Candidatos denominada 2Potencial, que não teve resultados promissores. Nessa proposta,
o sorteio da LCR também foi feito através de roleta, cujos resultados foram inferiores a
todas as outras abordagens. O ponto positivo dessa metaheurística foi relativa ao baixo
tempo de processamento, quando comparado as demais abordagens analisadas.
No caso de algoritmos meméticos, foram propostas duas versões do algoritmo, onde a
diferença foi apenas a inserção de uma população de elite, que foi utilizada na escolha dos
pais na fase de recombinação do algoritmo. A utilização da população de elite no segundo
algoritmo memético proposto melhorou a solução média encontrada pela primeira versão
a um custo de processamento baixo.
A abordagem transgenética foi outra metaheurística estudada neste trabalho, onde
desenvolvemos duas versões da mesma. A primeira versão contou com a formulação tradicional com um banco de informações genéticas sem informações
a priori.
A segunda
formulação contou com a reprodução do endosimbionte, que é uma abordagem ainda não
descrita na literatura. O tempo de processamento das duas alternativas foi similar, mas
a segunda abordagem obteve um desempenho qualitativo bem superior.
Finalmente, foi apresentado um algoritmo evolucionário híbrido, que considera a possibilidade de transferência horizontal e vertical de genes, considerando a utilização conjunta dos operadores de plasmídeo e recombinação proporcionando bons resultados. Essa
abordagem apresentou, nas instâncias Euclidianas, resultados qualitativos superiores a
abordagem memética, porém a um custo computacional mais elevado que essa abordagem, porém, inferior ao utilizado pela abordagem transgenética.
O problema do caixeiro alugador com coleta de prêmios aqui propostos possui uma
maior diculdade na fase de busca local, pois possui três regiões onde as buscas podem
118
atuar: na rota da solução, nos pontos de troca dos veículos, e no recolhimento de bônus.
Cada busca aplicada pode ser efetiva para um dos aspectos acima, porém sem garantias
de melhoria dos demais, sendo um dos aspectos mais sensíveis do problema, pois eles são
conitantes entre si.
Nesse sentido, o procedimento de busca local proposto, denominado
buscaM ultiOperadores(),
buscou atuar em todas essas dimensões, e mostrou bons resultados qualitativos, apesar
de também demandar um alto custo de processamento em suas seis fases de busca apresentados.
Este trabalho, que representa o primeiro estudo do tema, possibilita a vericação
da potencialidade dos algoritmos propostos, bem como os operadores que os constituem.
Vericamos que a abordagem memética tem o melhor equilíbrio entre o tempo de processamento e a média das soluções encontradas. Das abordagens analisadas, o transgenético
com reprodução, obteve resultados promissores.
6.1 Sugestão para Trabalhos Futuros
O estudo realizado é apenas uma amostra da potencialidade de estudos complementares que se fazem possíveis com a proposta desse problema. Abre-se um amplo leque de
possibilidades de pesquisa, dentre as quais pode-se destacar:
1. Denir outros modelos e estratégias de solução exatos mais ecientes que possam
ser adaptadas ao problema;
2. Estudo e adaptação de outras metaheurísticas ao problema;
3. Melhoria dos operadores e soluções apresentadas no presente estudo;
4. Denição e análise de informações
a priori
que possam ser utilizadas na composição
do banco de informações genéticas na abordagem transgenética computacional;
5. Estudo das outras variantes do problema, propostas no presente estudo;
6. Estudo de possiblidade de utilização de outras formas de transporte durante o percurso, a exemplo do transporte público;
7. Estudo e análise de estratégias que diminuam o tempo de execução das buscas locais
propostas;
119
Referências
ADAMS, W. P.; FORRESTER, R. J.; GLOVER, F. W. Comparisons and enhancement
strategies for linearizing mixed 0 - 1 quadratic programs.
Discret. Optim.,
Elsevier
Science Publishers B. V., Amsterdam, The Netherlands, The Netherlands, v. 1, n. 2, p.
99120, nov. 2004. ISSN 1572-5286.
ALMEIDA, C. et al. A transgenetic algorithm for the bi-objective traveling purchaser
problem. In:
Evolutionary Computation (CEC), 2010 IEEE Congress on.
[S.l.: s.n.],
2010. p. 18.
ALVAREZ-VALDES, R. et al. {GRASP} and path relinking for project scheduling under
partially renewable resources.
European Journal of Operational Research, v. 189, n. 3, p.
1153 1170, 2008. ISSN 0377-2217.
AMICO, M. D.; MAFFIOLI, F.; VäRBRAND, P. On prize-collecting tours and the
International Transactions in Operational
Research, Blackwell Publishing Ltd, v. 2, n. 3, p. 297308, 1995. ISSN 1475-3995.
asymmetric travelling salesman problem.
ASCONAVIETA, P.
O Problema do Caixeiro Alugador: Um Estudo Algorítmico. Tese
(Doutorado) Universidade Federal do Rio Grande do Norte, 2011.
ASCONAVIETA, P. H.; GOLDBARG, M. C.; GOLDBARG, E. F. Algoritmo em colônia
de formigas com multiferomônios para a solução do problema do caixeiro alugador. In:
XVI Latin-Ibero-American Conference on Operations Research and XLIV Brazilian
Symposium on Operations Research. [S.l.]: CLAIO SBPO, 2012. p. 0.
BALAS, E. Extension de l'algorithme additif à la programmation en nombres entiers
Comptes Rendus Hebdomadaires des Séances de
l'Académie des Sciences, Paris, Gauthier-Villars, Paris, v. 258, p. 51365139, 1964.
et à la programmation non linéaire.
BALAS, E. The prize collecting traveling salesman problem.
Networks,
v. 19, n. 0, p.
621636, 1989.
BECKMAN, M.; KOOPMANS, T. Assignment problems and the location of economic
activities.
Econometrica, v. 25, p. 5376, 1957.
BIENSTOCK, D. et al.
A note on the prize collecting traveling salesman problem. 1993.
BISSCHOP, J. Aimms modeling guide. In:
. [S.l.]: Paragon Decision Technology
B.V., 2012. (0, v. 1), cap. Integer Programming Tricks, p. 7585.
BOUDIA, M.; LOULY, M.; PRINS, C. A reactive {GRASP} and path relinking for a
combined production distribution problem.
Computers and Operations Research, v. 34,
n. 11, p. 3402 3419, 2007. ISSN 0305-0548.
120
CHAO, I.-M.; GOLDEN, B. L.; WASIL, E. A. A fast and eective heuristic for the
orienteering problem.
European Journal of Operational Research,
v. 88, n. 3, p. 475 489, 1996. ISSN 0377-2217.
CHAOVALITWONGSE, W.; KIM, D.; PARDALOS, P. Grasp with a new local search
scheme for vehicle routing problems with time windows.
Journal of Combinatorial
Optimization, Kluwer Academic Publishers, v. 7, n. 2, p. 179207, 2003. ISSN 1382-6905.
CHAOVALITWONGSE, W.; PARDALOS, P. M.; PROKOPYEV, O. A. A new
linearization technique for multi quadratic 0 1 programming problems.
Research Letters, v. 32, n. 6, p. 517 522, 2004.
Operations
CHAVES, A. A. et al. Metaheurísticas híbridas para resolução do problema do caixeiro
viajante com coleta de prêmios.
Produção,
scielo, v. 17, p. 263 272, 08 2007. ISSN
0103-6513.
CROES, G. A. A method for solving traveling salesman problems.
Operations Research,
v. 6, n. 0, p. 791812, 1958.
DANTZIG, G.; FULKERSON, R.; JOHNSON, S. Solution of a large-scale travelingsalesman problem.
Operations Research, v. 2, p. 393410, 1954.
DANTZIG, G. B. On the signicance of solving linear programming problems with some
integer variables.
Econometrica, The Econometric Society, v. 28, n. 1, p. pp. 3044, 1960.
The origin of species. [S.l.]: Dent, 1936. (Everyman's library).
DARWIN, C.
DAWKINS, R.
The Selsh Gene. 1th. ed. Oxford: Oxford University Press, 1976.
DIGALAKIS, J.; MARGARITIS, K. Performance comparison of memetic algorithms.
Journal of Applied Mathematics and Computation, Elsevier Science, v. 158, p. 237252,
2004.
DOOLITTLE, W. F. Uprooting the tree of life.
Scientic American,
v. 282, n. 2, p.
9095, fev. 2000.
ELLOUMI, S.; FAYE, A.; SOUTIF, E. Decomposition and linearization for 0 1 quadratic
programming.
Annals of Operations Research, Kluwer Academic Publishers, v. 99, n. 1-4,
p. 7993, 2000. ISSN 0254-5330.
FEILLET, D.; DEJAX, P.; GENDREAU, M. Traveling salesman problems with prots:
An overview.
Transportation Science, v. 39, p. 188205, 2001.
FEILLET, D.; DEJAX, P.; GENDREAU, M. Traveling salesman problems with prots:
An overview.
Transportation Science, v. 39, p. 188205, 2005.
FEO, T. A.; RESENDE, M. G. A probabilistic heuristic for a computationally dicult
set covering problem.
Operations Research Letters,
v. 8, n. 2, p. 67 71, 1989. ISSN
0167-6377.
FEO, T. A.; RESENDE, M. G. Greedy randomized adaptive search procedures.
of Global Optimization, v. 6, p. 109133, 1995.
Journal
121
FINK, A.; REINERS, T. Modeling and solving the short-term car rental logistics
problem.
Transportation Research Part E: Logistics and Transportation Review, v. 42,
n. 4, p. 272 292, 2006. ISSN 1366-5545.
FISCHETTI, M.; TOTH, P. An additive approach for the optimal solution of the
prize-collecting traveling salesman problem. In: ASSAD, A. A. (Ed.).
Vehicle Routing:
Methods and Studies. [S.l.]: Elsevier Science Publishers, 1988. V, p. 319343.
FORTET, R. Applications de l'algebre de boole en recherche operationelle.
Française de Recherche Operationelle, v. 4, n. 0, p. 1726, 1960.
Revue
GARCIA, A. et al. Integrating public transportation in personalised electronic tourist
guides.
Computers and Operations Research, v. 40, n. 3, p. 758 774, 2013.
GENDREAU, M.; LAPORTE, G.; SEMET, F. A tabu search heuristic for the undirected
selective travelling salesman problem.
European Journal of Operational Research, v. 106,
n. 2, p. 539 545, 1998.
GEORGE, D. K.; XIA, C. H. Fleet-sizing and service availability for a vehicle rental
system via closed queueing networks.
European Journal of Operational Research, v. 211,
n. 1, p. 198 207, 2011. ISSN 0377-2217.
GIORDANO, J. et al. Evolutionary history of mammalian transposons determined by
genome-wide defragmentation.
PLoS Computational Biology, v. 3, n. 7, 2007.
GLOVER, F. Tabu search and adaptive memory programing: Advances, applications and
challenges. In:
Interfaces in Computer Science and Operations Research. [S.l.]: Kluwer,
1996. p. 175.
GLOVER, F.; WOOLSEY, E. Converting the 0 - 1 polynomial programming problem to
a 0 - 1 linear program.
Operations Research, v. 22, n. 1, p. 180182, 1974.
GLPK; MAKHORIN, A.
GNU Linear Programming Kit.
jul. 2012. Version 4.45.2
Disponível em: <http://www.gnu.org/software/glpk/>. Acesso em Dezembro 9,
2012.
GOLDBARG, E.; GOLDBARG, M. Transgenetic algorithm: A new endosymbiotic
Foundations of
Computational Intelligence Volume 3. [S.l.]: Springer Berlin Heidelberg, 2009, (Studies
approach for evolutionary algorithms. In: ABRAHAM, A. et al. (Ed.).
in Computational Intelligence, v. 203). p. 425460. ISBN 978-3-642-01084-2.
GOLDBARG, M.; BAGI, L.; GOLDBARG, E. Transgenetic algorithm for the traveling
purchaser problem.
European Journal of Operational Research, v. 199, n. 1, p. 36 45,
2009. ISSN 0377-2217.
GOLDBARG, M. C.; ASCONAVIETA, P. H.; GOLDBARG, E. F. G. Memetic algorithm
for the traveling car renter problem: an experimental investigation.
Memetic Computing,
Springer-Verlag, v. 4, n. 2, p. 89108, 2012. ISSN 1865-9284.
GOLDBARG, M. C.; BAGI, L. B.; GOLDBARG, E. F. G. Algoritmo transgenético
aplicado ao problema do caixeiro comprador capacitado.
v. 28, p. 93 121, 04 2008. ISSN 0101-7438.
Pesquisa Operacional, scielo,
122
GOLDBARG, M. C. et al. A transgenetic algorithm applied to the traveling car renter
problem.
Expert Systems with Applications, v. 40, n. 16, p. 6298 6310, 2013.
GOLDBARG, M. C.; LUNA, H. L. P.
Otimização Combinatória e Programação Linear.
3th. ed. Rio de Janeiro: Elsevier, 2005.
GOLDEN, B.; LEVY, L.; VOHRA, R. The orienteering problem.
Logistics, v. 34, n. 0, p. 307318, 1987.
Naval Research
GUTIN, G.; PUNNEN, A. Traveling salesman problem and its variations.
Academic Publishers, v. 0, n. 0, p. 0, 2002.
Kluwer
The evolution of man : a popular exposition of the principal points of
human ontogeny and phylogeny. [S.l.]: New York Appleton 1879. 536 p.
HAECKEL, E.
HANSEN, P.; MEYER, C. Improved compact linearizations for the unconstrained
quadratic 0 1 minimization problem.
Discrete Applied Mathematics, v. 157, n. 6, p. 1267
1290, 2009. ISSN 0166-218X. <ce:title>Reformulation Techniques and Mathematical
Programming</ce:title>.
HANSEN, P.; MLADENOVIC, N. Variable neighborhood search: Principles and applications.
European Journal of Operational Research,
v. 130, n. 3, p. 449 467, 2001. ISSN 0377-2217. Disponível em:
<http://www.sciencedirect.com/science/article/pii/S0377221700001004>.
HANSEN, P.; MLADENOVIC, N.; PéREZ, J. A. M. Variable neighborhood search :
Editoria.
European Journal of Operational Research, v. 191, n. 0, p. 593595, 2008.
HARRISON, E.; BROCKHURST, M. A. Plasmid-mediated horizontal gene transfer is a
coevolutionary process.
Trends in Microbiology, v. 20, n. 6, p. 262 267, 2012.
HE, X. et al. An improved linearization technique for a class of quadratic 0 1
programming problems.
Optimization Letters, Springer-Verlag, v. 6, n. 1, p. 3141, 2012.
ISSN 1862-4472.
HE, X. et al. An improved linearization technique for a class of quadratic 0 1
programming problems.
Optimization Letters, Springer-Verlag, v. 6, n. 1, p. 3141, 2012.
ISSN 1862-4472.
JOZEFOWIEZ, N. et al. Multi-objective meta-heuristics for the traveling salesman
problem with prots.
J Math Model Algor, v. 0, n. 0, p. 0, 2007.
KE, L.; ARCHETTI, C.; FENG, Z. Ants can solve the team orienteering problem.
Computers and Industrial Engineering, v. 54, n. 3, p. 648 665, 2008.
KRASNOGOR, N.; GUSTAFSON, S. A study on the use of self-generation in memetic
algorithms.
Natural Computing, Kluwer Academic Publishers, v. 3, n. 1, p. 5376, 2004.
ISSN 1567-7818.
KRUSKAL, W. H.; WALLIS, W. A. Use of Ranks in One-Criterion Variance Analysis.
Journal of the American Statistical Association, American Statistical Association, v. 47,
n. 260, p. 583621, 1952. ISSN 01621459.
123
LABADIE, N.; MELECHOVSKý, J.; CALVO, R. W. Hybridized evolutionary local
search algorithm for the team orienteering problem with time windows.
Heuristics, Springer US, v. 17, n. 6, p. 729753, 2011. ISSN 1381-1231.
LIBERTI, L. Compact linearization for binary quadratic problems.
Journal of
4OR, Springer-Verlag,
v. 5, n. 3, p. 231245, 2007. ISSN 1619-4500.
LIPPS, G.
Plasmids: Current Research and Future Trends. 1th. ed. Bayreuth, Germany:
Caister Academic Press, 2008.
Symbiosis in Cell Evolution: Microbial Communities in the Archean and
Proterozoic Eons. 2th. ed. [S.l.]: W H Freeman and Co., 1992.
MARGULIS, L.
MARINAKIS, Y.; MIGDALAS, A.; PARDALOS, P. Expanding neighborhood grasp for
the traveling salesman problem.
Computational Optimization and Applications, Kluwer
Academic Publishers, v. 32, n. 3, p. 231257, 2005. ISSN 0926-6003.
MCDANIEL, L. D. et al. High Frequency of Horizontal Gene Transfer in the Oceans.
Science, American Association for the Advancement of Science, v. 330, n. 6000, p. 50,
out. 2010.
MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer programming formulation of
traveling salesman problems.
J. ACM, ACM, New York, NY, USA, v. 7, n. 4, p. 326329,
out. 1960. ISSN 0004-5411.
MLADENOVIC, N. A variable neighborhood algorithm a new metaheuristics for
combinatorial optimization. In:
Montreal. [S.l.: s.n.], 1995.
MOROWITZ, H.
Abstracts of Papers Presented at Optimization Days.
Beginnings of Cellular Life: Metabolism Recapitulates Biogenesis. [S.l.]:
Yale University Press, 2004. ISBN 9780300102109.
On evolution, search, optimization, genetic algorithms and martial arts:
Towards Memetic Algorithm. [S.l.], 1989.
MOSCATO, P.
ONG, Y.-S.; LIM, M.-H.; CHEN, X. Memetic computation: Past, present and future
[research frontier].
Computational Intelligence Magazine, IEEE,
v. 5, n. 2, p. 2431,
2010. ISSN 1556-603X.
PRAY, L.; ZHAUROVA, K. Barbara mcclintock and the discovery of jumping genes
(transposons).
Nature Education, v. 169, n. 1, 2008.
REINELT, G. Tsplib a traveling salesman problem library.
Computing, v. 3, n. 4, p. 376, 1991. ISSN 08991499.
RESENDE, M. G.; RIBEIRO, C. C.
Applications. [S.l.], 2003.
ORSA Journal on
GRASP with Path-Relinking: Recente Advances and
SCHILDE, M. et al. Metaheuristics for the bi objective orienteering problem.
Intelligence, Springer US, v. 3, n. 3, p. 179201, 2009. ISSN 1935-3812.
Swarm
SOUFFRIAU, W. et al. A greedy randomised adaptive search procedure for the team
EU/MEeting 2008 on metaheuristics for logistics and vehicle
routing, Troyes, France, 23-24 October. [S.l.: s.n.], 2008.
orienteering problem. In:
124
SOUFFRIAU, W. et al. A path relinking approach for the team orienteering
problem.
Computers and Operations Research,
v. 37, n. 11, p. 1853 1859, 2010.
<ce:title>Metaheuristics for Logistics and Vehicle Routing</ce:title>.
SOUFFRIAU, W. et al. A personalised tourist trip design algorithm for móbile tourist
guides.
Applied Articial Intelligence, v. 22, n. 10, p. 964985, 2008.
STENGER, A.; SCHNEIDER, M.; GOEKE, D. The prize-collecting vehicle routing
EURO Journal on
Transportation and Logistics, Springer-Verlag, v. 2, n. 1-2, p. 5787, 2013.
problem with single and multiple depots and non-linear cost.
The Journal of the
Operational Research Society, Springer US, v. 35, n. 9, p. 797809, 1984.
TSILIGIRIDES, T. Heuristic methods applied to orienteering.
VANSTEENWEGEN, P.; D., V. O. The mobile tourist guide: An or opportunity.
Insights, v. 20, n. 3, p. 2127, 2007.
OR
VANSTEENWEGEN, P. et al. A guided local search metaheuristic for the team
orienteering problem.
European Journal of Operational Research, v. 196, n. 1, p. 118 127, 2009.
VANSTEENWEGEN, P. et al. The city trip planner: An expert system for tourists.
Expert Systems with Applications, v. 38, n. 6, p. 6540 6546, 2011. ISSN 0957-4174.
VANSTEENWEGEN, P.; SOUFFRIAU, W.; OUDHEUSDEN, D. V. The orienteering
problem: A survey.
European Journal of Operational Research, v. 209,
n. 1, p. 1 10,
2011. ISSN 0377-2217.
WATTERS, L. J. Reduction of integer polynomial programming problems to zero-one
linear programming problems.
Operations Research, v. 15, nov. 1967.
YANG, Y.; JIN, W.; HAO, X. Car rental logistics problem: A review of literature.
Service Operations and Logistics, and Informatics, 2008. IEEE/SOLI 2008. IEEE
International Conference on. [S.l.: s.n.], 2008. v. 2, p. 28152819.
In:
ZANGWILL, W. Media selection by decision programming. In:
Mathematical Models
in Marketing. [S.l.]: Springer Berlin Heidelberg, 1976, (Lecture Notes in Economics and
Mathematical Systems, v. 132). p. 132133.