CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Programa de Pós-Graduação em Modelagem
Matemática e Computacional
Uma metodologia híbrida
Colônia de Formigas - Busca
Tabu - Reconexão por Caminhos
para resolução do Problema de
Roteamento de Veículos com
Janelas de Tempo
Dissertação de Mestrado, submetida ao Curso de
Mestrado em Modelagem Matemática e Computacional, como parte dos requisitos exigidos para
a obtenção do título de Mestre em Modelagem
Matemática e Computacional.
Aluno: Marcelo Caramuru Pimentel Fraga
Engenheiro Mecânico – CEFET-MG
Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET-MG)
Co-Orientador: Prof. Dr. Marcone Jamilson Freitas Souza (UFOP)
Belo Horizonte, agosto de 2006.
F811m FRAGA, Marcelo Caramuru Pimentel.
2006
Uma metodologia híbrida Colônia de
Formigas-Busca Tabu-Reconexão por Caminhos
para resolução do problema de roteamento de
veículos com janelas de tempo.
Belo Horizonte: CEFET-MG, 2006.
78p.
Dissertação (Mestrado) Centro Federal de Educação
Tecnológica de Minas Gerais
CEFET/MG.
1. Pesquisa Operacional. 2. Metaheurística.
3. Roteamento de veículos. 4. Colônia de Formigas.
I. Título.
CDD: 001.424
Agradecimentos
“A dúvida é o princípio da sabedoria.”
Aristóteles
A realização deste trabalho só foi possível mediante a contribuição de muitas
pessoas. A elas, gostaria de deixar algumas palavras de reconhecimento.
Inicialmente, agradeço ao prof. Sérgio Ricardo de Souza, por confiar em minha
capacidade e me dar a chance de participar do curso de mestrado, pelo empenho em
minha orientação e, por fim, por se tornar, além de professor orientador, um amigo.
À Tatiana Alves Costa, irmã de mestrado, pela amizade inestimável que surgiu
durante o curso, pela paciência e dedicação em me ensinar e desvendar áreas de
conhecimento inéditas para mim e, com tudo isso, tornar possível a conclusão deste
trabalho.
Ao prof. Marcone Jamilson, pela co-orientação ao trabalho e o aporte para minha
formação acadêmica e profissional.
Aos colegas de mestrado, pelo companheirismo, especialmente aos que se tornaram
grandes amigos: Ricardo Soares, Marcos Medeiros, Alessandra Coelho, Paulo Isnard, Rodrigo Coimbra, Márlon Oliveira, Eliézer Guimarães, Moysés Alberto, Júlio
Pacheco, Alcir Reis, Gabriel Silva e Jefferson Chaves.
Aos demais professores e funcionários do mestrado do CEFET-MG, pelas diversos
auxílios dados a mim, inclusive quanto às minhas formações profissional e pessoal,
especialmente a: Henrique Borges, Paulo Almeida, Gray Farias, Maria das Graças,
Fausto de Camargo, José Evaristo, João Francisco, Elenice Biazi e Ester Naves,
Clayston Damião, Cristiano CCC e Bruno Santos.
Aos amigos de fora do CEFET, responsáveis por momentos de diversão e descontração: Henrique Habib’s, Guilherme Juvenal, Eduardo Feio, Gustavo Barrosão,
Gilberto Peposo, Rosklin Metralha, Paulo Puliça, Fernanda Japinha, Carlos, Rosinha Jaburu e Aninha Causos.
À minha namorada, Renata, que participou da reta final de minha caminhada
com paciência e compreensão.
À prof. Maria José, pelo carinho, amizade e investimento com que acompanhou
minha educação e formação pessoal.
Por fim, a meus pais, Rosa Helena e Fernando Caramuru, por proporcionarem
condições que me permitiram concluir o curso da melhor forma possível; e aos meus
irmãos, Cláudia, Beto e Bruno, além de minha sobrinha Priscilla, por estarem juntos
a mim nos momentos em que mais preciso.
Aos demais amigos e familiares pelo apoio e incentivo.
À CAPES, pelo provimento das bolsas.
A todos vocês, meus sinceros e humildes agradecimentos.
iii
Resumo
Neste trabalho, uma metodologia híbrida, chamada Ant-TPR, é proposta para
resolução do Problema de Roteamento de Veículos com Janela de Tempo (PRVJT).
O PRVJT é uma variação do Problema de Roteamento de Veículos Capacitados
(PRVC) na qual, além das restrições inerentes ao PRVC, o atendimento a cada consumidor deve ser iniciado em um intervalo de tempo denominado janela de tempo.
Neste trabalho, a solução para esse problema consiste em, primeiramente, encontrar o número mínimo de veículos capaz de atender a todos os consumidores e, em
segundo lugar, determinar um conjunto de rotas que minimize a distância total percorrida pelos veículos. O PRVJT é um problema NP-Difícil, logo, o uso de métodos
heurísticos, que exigem menor custo computacional, têm sido amplamente utilizados, sofrendo, no entanto, das dificuldades inerentes à indefinição da qualidade da
solução determinada.
A metodologia Ant-TPR combina o uso das metaheurísticas Colônia de Formigas
e Busca Tabu à técnica de intensificação de resultados Reconexão por Caminhos.
A metaheurística Colônia de Formigas (ACO) se alimenta, em parte, dos próprios
resultados, contribuindo, a cada iteração, para convergência e precisão dos resultados
gerados. A Busca Tabu (BT) é uma estratégia que depende fortemente da solução
inicial e, por isso, a associação com a metaheurística ACO, capaz de produzir boas
soluções, potencializa o resultados de ambas. Periodicamente, a técnica Reconexão
por Caminhos (RC) é aplicada, de forma a tentar inserir bons atributos das melhores
soluções encontrada nas soluções correntes.
A metodologia foi avaliada nos problemas-teste criados por Solomon para o Problema de Roteamento de Veículos com Janela de Tempo e gerou resultados que
diferem em menos de 3% acima do resultado do melhor método existente.
Palavras-Chave: Colônia de formigas, Reconexão por Caminhos, Roteamento de
veículos.
iv
Abstract
In this work, it is presented an hybrid methodology called Ant-TPR to solve the
Vehicle Routing Problem with Time Windows (VRPTW).
The VRPTW is a variation from the Capacitated Vehicle Routing Problem
(CVRP) in which, beyond the inherent restrictions to the CVRP, the attendance of
each consumer must be initiated in a time interval called time window. In this work,
firstly, the solution to this problem consists of finding the minimum number of vehicles able to attend all the consumers. Secondly, the solution consists in determining
a set of routes that minimizes the covered distance of the vehicles. The VRPTW
is a NP-Hard problem, i.e., there are no exact algorithms able to guarantee the
global optimum can be found in viable computational cost for greater instances. On
the other hand, heuristic methods, demanding less computational cost, have been
widely used, suffering, however, the inherent difficulties from the imprecise quality
of the founded solutions.
The Ant-TPR methodology combines two metaheuristics, Ant Colony Optimization (ACO) and Tabu Search (TS), with the Path Relinking intensification technique. The ACO metaheuristic feeds itself, partially from its own results, leading to
convergence and precision of the generated results. Tabu Search strongly depends
of a good initial solution and the association with ACO, capable of producing good
solutions, improves both results. Periodically, the Path Relinking technique (PR)
is applied to insert good attributes from the best solutions found in the current
solutions.
The developed methodology was benchmarked in Solomon’s VRPTW instances,
generating some isolated better results than those found in literature and remaining
less than 3% above the best existing methodology.
Keywords: Ant Colony, Tabu Search, Path Relinking, Vehicle Routing, Metaheuristic.
v
Conteúdo
1 Introdução
1.1 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . .
2 Problema de Roteamento de Veículos
2.1 Caracterização do Problema de Distribuição de Produtos . .
2.2 Problema de Roteamento de Veículos Capacitados . . . . . .
2.3 Formulações Matemáticas do PRVC . . . . . . . . . . . . . .
2.3.1 Modelo de Fluxo de Veículos . . . . . . . . . . . . . .
2.3.2 Modelo de Fluxo de Veículos com Três Índices . . . .
2.3.3 Modelo de Fluxo de Mercadorias . . . . . . . . . . .
2.3.4 Modelo de Particionamento de Conjuntos . . . . . . .
2.4 Problema de Roteamento de Veículos com Janelas de Tempo
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Uma Revisão de Métodos Heurísticos
3.1 Métodos Heurísticos . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Heurísticas Construtivas . . . . . . . . . . . . . . . . . . . . . .
3.3 Heurísticas de Refinamento . . . . . . . . . . . . . . . . . . . . .
3.3.1 Método da Descida . . . . . . . . . . . . . . . . . . . . .
3.3.2 Descida com Primeiro de Melhora . . . . . . . . . . . . .
3.4 Metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Inteligência Coletiva . . . . . . . . . . . . . . . . . . . .
3.5 Algoritmos de Colônia de Formigas . . . . . . . . . . . . . . . .
3.5.1 Algoritmo Ant System . . . . . . . . . . . . . . . . . . .
3.5.2 Algoritmo Ant Colony System . . . . . . . . . . . . . . .
3.5.3 Ant Colony Optimization - Considerações Gerais . . . . .
3.5.4 Comparação entre Formigas Reais e Formigas Artificiais
3.6 Metaheurística Busca Tabu . . . . . . . . . . . . . . . . . . . .
3.7 Reconexão por Caminhos . . . . . . . . . . . . . . . . . . . . . .
4 Metodologia Ant-TPR para Resolução do PRVJT
4.1 Metodologia Ant-TPR . . . . . . . . . . . . . . . .
4.2 Forma de Representação das Soluções . . . . . . . .
4.3 Funções de Avaliação . . . . . . . . . . . . . . . . .
4.4 Movimentos de Realocação . . . . . . . . . . . . . .
4.5 Algoritmo Ant-TPR . . . . . . . . . . . . . . . . .
vi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
.
.
.
.
.
.
.
.
3
. 3
. 5
. 6
. 7
. 8
. 9
. 11
. 12
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
15
17
18
18
19
20
21
22
25
28
30
31
32
36
.
.
.
.
.
39
39
39
40
41
42
.
.
.
.
.
5 Resultados Computacionais
50
5.1 Implementação da Metodologia Ant-TPR . . . . . . . . . . . . . . . . 50
5.2 Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura 52
6 Conclusões Gerais e Trabalhos Futuros
59
6.1 Conclusões Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Referências Bibliográficas
61
vii
Lista de Tabelas
3.1
3.2
Principais aplicações da metaheurística ACO. . . . . . . . . . . . . . 23
Principais aplicações da metaheurística Busca Tabu no PRVJT. . . . 33
4.1
Forma de representação de uma solução. . . . . . . . . . . . . . . . . 39
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
Formato das instâncias Solomon para o PRVJT . . . . . . . . . .
Comparação entre as funções de avaliação propostas. . . . . . . .
Resultados da metodologia Ant-TPR nas instâncias C1. . . . . . .
Melhores resultados da metodologia Ant-TPR nas instâncias C2. .
Melhores resultados da metodologia Ant-TPR nas instâncias R1 .
Melhores resultados da metodologia Ant-TPR nas instâncias R2 .
Melhores resultados da metodologia Ant-TPR nas instâncias RC1
Melhores resultados da metodologia Ant-TPR nas instâncias RC2
Comparação da eficiência da metodologia Ant-TPR com outras .
Comparação entre Ant-TPR e MACS . . . . . . . . . . . . . . . .
Comparação entre Ant-TPR e BBB . . . . . . . . . . . . . . . . .
Ant-TPR vs. outras metodologias . . . . . . . . . . . . . . . . . .
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
51
53
53
54
54
55
55
56
57
57
58
Lista de Figuras
2.1
Conjunto de rotas para o PRVC. . . . . . . . . . . . . . . . . . . . .
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
Heurística Construtiva Gulosa - Pseudo-código. . . . .
Heurística de Refinamento - Pseudo-código. . . . . . .
Comportamento de uma heurística de refinamento. . .
Método da Descida - Pseudo-código. . . . . . . . . . .
Descida com Primeiro de Melhora - Pseudo-código. . .
Comportamento de formigas reais. . . . . . . . . . . . .
Parâmetro Visibilidade. . . . . . . . . . . . . . . . . . .
Parâmetro Rastro de Feromônio. . . . . . . . . . . . .
Pseudo-código do Ant System aplicado ao PCV. . . . .
Pseudo-código do Ant Colony System aplicado ao PCV.
Ciclagem na Busca Tabu. . . . . . . . . . . . . . . . .
Pseudo-código da Busca Tabu . . . . . . . . . . . . . .
Idéia geral da técnica Reconexão Por Caminhos. . . . .
Pseudo-código Path Relinking. . . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
Instância fictícia de 7 cidades. . . . . . . . . . . . . . . . . . . . . . .
Movimento de realocação Intra-rota. . . . . . . . . . . . . . . . . . .
Movimento de realocação Inter-rotas. . . . . . . . . . . . . . . . . . .
Pseudo-código Ant-TPR. . . . . . . . . . . . . . . . . . . . . . . . . .
Instância do PRVJT a ser solucionada. . . . . . . . . . . . . . . . . .
A formiga analisa suas opções de movimento. . . . . . . . . . . . . .
Após movimentar-se, a formiga analisa suas novas opções de movimento.
A formação da rota continua, enquanto gerar soluções factíveis. . . .
Ao final da excursão da formiga, são adicionadas ligações ao depósito.
Uma nova formiga é posicionada e o processo continua. . . . . . . . .
Solução completa e factível gerada pelas formigas. . . . . . . . . . . .
O consumidor 1 isolado em uma rota. . . . . . . . . . . . . . . . . . .
Solução prejudicada pelo consumidor 1. . . . . . . . . . . . . . . . . .
Ant-TPR: O consumidor 1 momentaneamente isolado em uma rota. .
Ant-TPR: Formiga integra o consumidor 1 à nova rota formada. . . .
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
17
18
19
19
20
24
26
26
27
29
34
36
37
37
40
42
42
44
45
45
46
46
47
47
48
48
48
49
49
Lista de Siglas
PRV
PRVC
PRVJT
BT
ACO
AS
ACS
RC
PR
IS
PCV
FA
FO
LTPNNF
LRCC
LTGF
VGR
VRF
LTF
Problema de Roteamento de Veículos
Problema de Roteamento de Veículos Capacitado
Problema de Roteamento de Veículos com Janelas de Tempo
Busca Tabu
Ant Colony Optimization
Ant System
Ant Colony System
Reconexão por Caminhos
Path Relinking
Inteligência Swarm
Problema do Caixeiro Viajante
Função de Avaliação
Função Objetivo
Lista Tabu Para Nascimento de Novas Formigas
Lista Restrita de Consumidores Candidatos
Lista Tabu Geral das Formigas
Vetor Geral de Rotas
Vetor de Rotas da Formiga
Lista Tabu da Formiga
x
Capítulo 1
Introdução
A atividade de transporte representa 2,53% do PIB brasileiro (IBGE (2001)) e
é um serviço que torna viável os demais setores do país, influenciando a segurança,
a qualidade de vida e o desenvolvimento econômico. O transporte é responsável,
dentre outras coisas, pelo fornecimento de matéria-prima às indústrias, pelo envio
de produtos essenciais aos consumidores e, de certa forma, por manter o país em
funcionamento. O Brasil é um país de dimensões continentais, com uma infraestrutura de transporte precária e que tem, em sua malha rodoviária, o principal
meio de transporte de cargas. Tudo isto demonstra a importância e a necessidade
de estudos sobre como realizar a distribuição de produtos de forma eficiente.
A partir deste contexto, este trabalho foi proposto e desenvolvido de forma a
abordar uma parte do processo de distribuição de produtos, representada pelo Problema de Roteamento de Veículos com Janela de Tempo (PRVJT).
O PRVJT é uma variação do Problema de Roteamento de Veículos clássico e
pode ser descrito como um problema no qual uma frota de veículos, inicialmente
situada em um depósito, deve atender a um conjunto de consumidores que possuem diferentes demandas por produtos a serem distribuídos utilizando-se a frota.
O atendimento a cada consumidor deve ser iniciado em um intervalo de tempo denominado janela de tempo.
A solução para esse problema pode variar de acordo com o objetivo a ser seguido.
Geralmente, a solução por métodos exatos procura encontrar a distância mínima
percorrida, capaz de atender a todos os consumidores; e a solução por métodos
heurísticos é feita em duas fases, de tal modo que, inicialmente, é feita a determinação do número mínimo de veículos capaz de atender a todos os consumidores; em
seguida, é feita a minimização da distância percorrida.
O PRVJT é classificado como um problema NP-Difícil, logo métodos heurísticos
têm sido amplamente utilizados para a solução de problemas-teste de diversas ordens, sofrendo, no entanto, das dificuldades inerentes à indefinição da qualidade da
solução determinada. Uma revisão de métodos heurísticos pode ser encontrada em
Blum e Roli (2003).
Este trabalho aborda o estudo da solução do Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), através de uma metodologia híbrida entre as
metaheurísticas Colônia de Formigas e Busca Tabu, aliadas ainda à técnica Reconexão por Caminhos (Path Relinking) de intensificação dos resultados.
Os algoritmos de Colônia de Formigas (ACO ou Ant Colony Optimization) foram
1.1
Organização do Trabalho
2
desenvolvidos a partir da observação do comportamento de formigas reais na natureza e têm sido aplicados em problemas de diversas classes, como ao Problema
do Caixeiro Viajante, apresentado em Gambardella e Dorigo (1996) e Stutzle e
Dorigo (1999); Problema de Roteamento de Veículos, mostrado em Gambardella
et al. (1999a); Problema de Alocação Quadrática, discutido em Gambardella et al.
(1999c); Problema de Alocação Bi-quadrática de Recursos, ilustrado por Taillard
(1998), dentre outros. De acordo com Dorigo et al. (1999), os algoritmos ACO são
um dos mais eficientes algoritmos baseados em inteligência coletiva (Swarm Intelligence). Uma revisão recente da metaheurística ACO pode ser encontrada em Dorigo
e Blum (2005).
A Busca Tabu (BT) é uma metaheurística robusta, mas que depende fortemente
da solução inicial para obter bons resultados. Associada à metaheurística ACO, que
é auto-catalítica, atuam de forma simbiótica e podem potencializar seus resultados.
A metaheurística ACO, por sua capacidade de ser influenciada pelos próprios resultados, pode proporcionar soluções iniciais cada vez melhores para a Busca Tabu
que, por sua vez, é mais eficiente na busca pelo espaço de soluções. A partir de um
ponto inicial mais avançado, a BT tem maiores chances de encontrar boas soluções
do que o algoritmo de Colônia de Formigas atuando sozinho, que parte da construção até a solução final e, diante do grande número de soluções possíveis, tem mais
chances de ficar preso a ótimos locais ou regiões planas. A integração entre essas
metaheurísticas permite ainda que as soluções encontradas pela Busca Tabu influenciem as próximas fases de construção, contribuindo para a convergência e melhora
nos resultados de Colônia de Formigas.
Reconexão por Caminhos é uma estratégia de intensificação da busca sobre resultados gerados, explorando trajetórias que conectam soluções elite, à procura de
uma solução de melhor qualidade. A partir de uma solução-corrente e em direção a
uma solução-guia, busca agrupar em uma única solução bons atributos encontrados
em ambas soluções.
O foco deste trabalho é apresentar a metodologia Ant-TPR, desenvolvida a partir da junção entre as metaheurística ACO e Busca Tabu e associadas à técnica
de Reconexão por Caminhos, de forma a produzir resultados competitivos com os
melhores encontrados na literatura para a classe de problemas PRVJT.
1.1
Organização do Trabalho
Este trabalho está organizado da seguinte forma: o capítulo 2 apresenta a caracterização do Problema de Roteamento de Veículos e da variação a qual este trabalho
se aplica, qual seja, o Problema de Roteamento de Veículos com Janelas de Tempo.
Uma revisão de métodos heurísticos empregados no trabalho pode ser vista no capítulo 3. No capítulo 4 é apresentada a metodologia desenvolvida. No capítulo 5 são
demonstrados os resultados computacionais. Por fim, a seção 6 mostra as conclusões
a respeito do trabalho desenvolvido e propostas de continuidade do mesmo.
Capítulo 2
Problema de Roteamento de Veículos
Este capítulo apresenta a caracterização do Problema de Roteamento de Veículos
e algumas de suas variações. Inicia-se, na seção 2.1, com uma abordagem geral do
Problema de Distribuição de Produtos. Em seguida, na seção 2.2, o Problema de
Roteamento de Veículos Capacitado (PRVC) é descrito. As principais formulações
matemáticas para o PRVC são revistas na seção 2.3. Por fim, a variação para o
qual este trabalho se aplica, chamada de Problema de Roteamento de Veículos com
Janelas de Tempo, é discutida em sua formulação matemática na seção 2.4.
2.1
Caracterização do Problema de Distribuição de
Produtos
A distribuição de produtos é um processo que envolve um número muito elevado
de variáveis a serem determinadas. Dentre elas, pode-se citar o número necessário
de veículos; que tipo de veículo é o mais adequado ao atendimento de cada cliente;
como criar rotas de forma eficiente, minimizando custos e/ou tempo de entrega,
dentre outras questões relevantes que determinam as escolhas a serem efetuadas na
solução do problema.
A malha rodoviária que os veículos percorrem pode ser descrita através de um
grafo, no qual os arcos representam as rodovias e os vértices, as cidades. Os arcos
podem ser ou não direcionados, assim como as estradas podem ou não ser trafegadas
nos dois sentidos. Cada arco está associado a um custo, que geralmente varia com
seu comprimento, e a um tempo de viagem, que pode variar com o tipo de veículo,
tipo de estrada ou o horário em que o arco será atravessado.
Cada consumidor pode possuir características totalmente diferentes dos demais,
porém, todos devem ser atendidos. Não será levado em consideração nesse trabalho
o estudo da viabilidade econômica de cada consumidor, sendo assumido que todos
eles geram lucro para a distribuição.
Os consumidores podem possuir diversos atributos diferentes, como:
• localização: representada pelas coordenadas geográficas;
• demanda: quantidade e tipo de produtos necessários;
• janela de tempo: intervalo no qual o consumidor está disponível para receber
a visita do veículo;
3
2.2
Caracterização do Problema de Distribuição de Produtos
4
• tempo de serviço: tempo necessário para carregar ou descarregar os veículos;
• tipo de veículo adequado para atendimento: o atendimento a cada consumidor
pode exigir, por razões as mais diversas, um veículo diferente. Por exemplo,
devido a problemas de acesso pelas estradas, tamanho das instalações ou tipo
de carregamento e descarregamento que um certo veículo oferece e é mais
adequado aos interesses do cliente.
Já uma frota de veículos pode possuir características diversas como:
• cada veículo tem um depósito como origem, mas que não necessariamente será
seu destino, no caso de múltiplos depósitos;
• a capacidade de carga pode variar com o tamanho, peso ou volume;
• possível subdivisão do compartimento de carga em compartimentos menores
e específicos para cada produto;
• dispositivos para carregamento e descarregamento das mercadorias;
• subconjunto de arcos em que os veículos podem ser empregados. Em uma
instância real, varia de acordo com o terreno ou o tipo de estrada;
• custo associado à utilização do veículo (por distância, por tempo, por rota,
por tipo de veículo utilizado, etc.).
Além dos veículos, os motoristas condutores também possuem particularidades
a serem observadas, como número de horas trabalhadas por dia, horários regulares
para refeições, intervalos de descanso, dentre outros, e isso também acarreta novos
custos para a distribuição. As rotas geradas para atender aos consumidores devem
iniciar e terminar em um depósito, cuja representação no grafo é, também, um
vértice. Cada depósito possui uma capacidade de estocar produtos e uma frota, que
pode variar na capacidade e na quantidade de veículos. As rotas devem satisfazer
uma série de restrições, que variam com a natureza dos produtos transportados,
qualidade do serviço prestado e características dos consumidores e veículos. Para
cada conjunto de rotas gerado, que respeite todas as restrições operacionais, está
associado um custo total, que serve de parâmetro de controle. São objetivos a serem
atingidos ao se solucionar uma instância do Problema de Roteamento de Veículos:
• minimização do custo de transporte, envolvendo todos os fatores associados,
incluindo a distância total percorrida (e o tempo de viagem) e os custos de
utilização relacionados a cada veículo;
• minimizar o número de veículos (e/ou motoristas) necessários para atender a
todos os consumidores;
• equilibrar as rotas, de acordo com o tempo de viagem e a carga do veículo;
• minimizar, caso existam, as penalidades pelo atendimento parcial a um cliente.
2.2
2.2
Problema de Roteamento de Veículos Capacitados
5
Problema de Roteamento de Veículos Capacitados
O Problema de Roteamento de Veículos (PRV) foi introduzido na literatura em
1959 por Dantzig e Ramser (1959), para solucionar um problema da distribuição de
gasolina entre postos de abastecimento. O PRV é um nome genérico, dado a uma
classe de problemas na qual um conjunto de rotas para uma frota de veículos deve
ser determinado para atender um número de cidades ou consumidores dispersos. A
solução para o PRV consiste em encontrar as rotas que satisfazem aos consumidores
ou cidades envolvidos, respeitando-se as restrições existentes.
O Problema de Roteamento de Veículos Capacitados (PRVC) é a forma mais
simples do PRV. Neste problema, uma frota de veículos, localizada inicialmente em
um depósito, deve atender a um conjunto de consumidores com diferentes demandas
de produtos a serem distribuídos por essa frota. A única restrição presente no
PRVC é a capacidade de carga dos veículos. As demandas são conhecidas a priori e
não podem ser fracionadas em sua entrega, ou seja, cada consumidor não pode ser
visitado mais de uma vez para entrega de produtos. Todos os veículos possuem a
mesma capacidade de carga e suas rotas iniciam e terminam no depósito.
A figura 2.1 ilustra um conjunto de rotas do PRVC. O retângulo maior representa
o depósito e os pequenos quadrados representam os consumidores.
Depósito
Figura 2.1: Conjunto de rotas para o PRVC.
Conforme Toth e Vigo (2002), o PRVC pode ser descrito da seguinte forma: seja
G = (V, A) um grafo completo, no qual V = {v0 , v1 , . . . , vn } é o conjunto dos vértices,
que representam cidades ou consumidores, e A = {aij = (vi , vj ) : vi , vj ∈ V, vi 6= vj }
é o conjunto de arcos, que ligam os vértices (vi , vj ). O vértice v0 representa o depósito, mas, em algumas formulações, o depósito pode estar representado pelo vértice
(n+1). Um valor não negativo cij é associado a cada arco e representa o custo de se
viajar do consumidor i para o consumidor j. Normalmente, o uso de arcos fechados
não é permitido e, para evitá-los, faz-se o custo do arco aii como infinito, ou seja,
cii = +∞.
2.3
Formulações Matemáticas do PRVC
6
Se o grafo G for direcionado, sua matriz de custos é assimétrica, ou seja, o
custo de viagem entre duas cidades varia com o sentido a ser seguido, de modo que
cij 6= cji . Nesse caso, o PRVC é chamado de Problema de Roteamento de Veículos
Capacitados Assimétrico (PRVCA). Por outro lado, se o grafo G for não-direcionado
e possuir uma matriz de custos simétrica, na qual o custo de viagem independa do
sentido a ser seguido, ou seja, cij = cji , então o PRVC é denominado Problema de
Roteamento de Veículos Capacitados Simétrico (PRVCS).
Cada consumidor é associado a uma demanda não-negativa qi , e o depósito v0
é associado a uma demanda fictícia q0 = 0. Uma frota de K veículos, com igual
capacidade Q, é disponibilizada no depósito e, para assegurar a factibilidade do
problema, é determinado que a demanda de cada consumidor seja menor ou igual
à capacidade do veículo, ou seja, qi ≤ Q. Cada veículo da frota deverá fazer, no
máximo, uma rota.
O PRVC consiste, então, na determinação de um conjunto de, no máximo, K
rotas, cada uma associada a um veículo específico, com o menor custo possível,
respeitando-se as seguintes restrições:
(i) todas as rotas têm início e término no depósito;
(ii) cada consumidor é visitado uma única vez;
(iii) a demanda total de qualquer rota não deve superar a capacidade Q do veículo
envolvido na mesma.
2.3
Formulações Matemáticas do PRVC
Esta seção apresenta quatro modelos matemáticos básicos, utilizados para representar o PRVC. É baseada em Toth e Vigo (2002), referência na qual outras
formulações podem ser encontradas. Não é objetivo do presente trabalho exaurir a
apresentação e discussão de modelos matemáticos para o PRVC. São apresentados
os modelos:
• Modelo de Fluxo de Veículos;
• Modelo de Fluxo de Veículos com três índices;
• Modelo de Fluxo de Mercadorias; e
• Modelo Particionamento de Conjuntos.
Em todos os modelos, está sendo utilizada a seguinte notação:
V : conjunto dos vértices (cidades ou consumidores);
V\{0} : conjunto dos vértices V, com exceção do vértice 0;
A : conjunto de arcos que ligam dois vértices;
K : número total de veículos disponíveis na frota;
Q : capacidade de cada veículo da frota;
2.3
Formulações Matemáticas do PRVC
7
qi : demanda do vértice i.
As demais variáveis envolvidas serão detalhadas junto a cada modelo.
2.3.1
Modelo de Fluxo de Veículos
Esta é a formulação mais utilizada para caracterizar as versões básicas do VRP.
As variáveis de decisão xij são variáveis inteiras, associadas com cada arco do grafo,
que demonstram o número de vezes que o veículo atravessa o arco em questão ou, no
caso de inteiras binárias, se o arco é ou não utilizado para o roteamento. O modelo
é dado, então, por:
min
XX
cij xij
(2.1a)
i∈V j∈V
sujeito a
X
xij = 1 , ∀ j ∈ V\{0}
(2.1b)
X
xij = 1 , ∀ i ∈ V\{0}
(2.1c)
X
xi0 = K
(2.1d)
X
x0j = K
(2.1e)
i∈V
j∈V
i∈V
j∈V
XX
xij ≥ r(S) , ∀ S ⊆ V\{0}, S =
6 ∅
(2.1f)
i6∈S j∈S
xij ∈ {0, 1} , ∀ i, j ∈ V
(2.1g)
Nessa representação, tem-se que:
xij : variável binária que assume o valor xij = 1, caso o arco aij faça parte da
solução ótima do problema; ou xij = 0, caso contrário;
cij : custo associado ao arco aij ;
r(S) : representa o número mínimo de veículos necessário ao atendimento do conjunto de consumidores S;
A função objetivo (2.1a) busca minimizar o somatório do custo dos arcos pertencentes à solução ótima.
As restrições dadas pela expressão (2.1b) impõem que apenas um veículo pode
partir de uma cidade qualquer i para uma cidade j, ou seja, qualquer arco que
termine em j deve ser utilizado apenas uma vez (com exceção do arco associado ao
depósito). As restrições (2.1c) impõem que apenas um veículo pode chegar a uma
cidade qualquer j a partir de uma cidade j, ou seja, qualquer arco que inicie em j
deve ser utilizado apenas uma vez (com exceção do arco associado ao depósito). As
restrições (2.1d) e (2.1e) exigem que, respectivamente, todos os K veículos devem
terminar e iniciar suas rotas no depósito. As restrições (2.1b)-(2.1e) são denominadas
restrições de grau. As restrições (2.1g) exigem que as variáveis xij sejam binárias.
2.3
Formulações Matemáticas do PRVC
8
As restrições dadas por (2.1f) asseguram a não-violação da capacidade dos veículos e a conectividade da solução encontrada. São chamadas de restrições de corte de
capacidade, em conseqüência. Seu tratamento é uma questão central na solução de
problemas postos na formulação de fluxo de veículos. Devido às restrições de grau,
tem-se que:
XX
XX
xij =
xij , ∀ S ⊆ V\{0}, S =
6 ∅
(2.2)
i6∈S j∈S
i∈S j6∈S
Assim, pode-se escrever (2.1f) como:
XX
xij ≥ r(V \S) , ∀ S ⊂ V, 0 ∈ S
(2.3)
i6∈S j∈S
Uma forma alternativa para (2.1f) pode ser obtida através da mudança da restrição de corte de capacidade em função das restrições de grau, gerando as restrições
de eliminação de sub-rotas, dadas por:
XX
xij ≤ |S| − r(S) , ∀ S ⊆ V\{0}, S =
6 ∅
(2.4)
i∈S j∈S
Essas restrições impõem, segundo Toth e Vigo (2002), que, no mínimo, r(S) arcos
partem de cada subconjunto S de consumidores.
As restrições (2.1f) e (2.4) crescem exponencialmente em número, de acordo
com o número de consumidores. Isso torna praticamente impossível a solução do
problema proposto em (2.1) através de relaxação linear. Uma forma alternativa ao
uso das restrições (2.1f) (ou (2.4)) e com cardinalidade polinomial é a utilização das
restrições de eliminação de subrotas apresentadas em C. E. Miller e Zemlin (1960)
e Desrochers e Laporte (1991):
ui − uj + Qxij ≤ Q − qj , ∀i, j ∈ V\{0}, i 6= j, desde que qi + qj ≤ Q
qi ≤ ui ≤ Q , ∀i ∈ V\{0}
(2.5)
(2.6)
Nessa expressão, ui representa a carga do veículo após visitar o consumidor i. As
restrições (2.5) e (2.6) impõem limites na capacidade e na conectividade do PRVC.
2.3.2
Modelo de Fluxo de Veículos com Três Índices
A finalidade da construção de modelos em três índices é a necessidade de explicitamente definir quais veículos atravessam um certo arco. Nesse caso, duas classes
de variáveis de decisão são necessárias:
xijk : variável binária que assume o valor 1, caso o arco aij faça parte da rota do
veículo k; ou 0, caso contrário;
cij : custo associado ao arco aij ;
yik : variável binária que assume o valor 1, caso o consumidor i seja servido pelo
veículo k na solução ótima do problema, ou 0, caso contrário;
2.3
Formulações Matemáticas do PRVC
9
O modelo é, então, dado por:
min
XX
cij
i∈V j∈V
suj. a
K
X
xijk
(2.7a)
k=1
K
X
yik = 1 , ∀ i ∈ V\{0}
(2.7b)
K
X
y0k = K
(2.7c)
X
xijk =
X
qi yik ≤ Q , ∀ k = 1, . . . , K
k=1
k=1
j∈V
X
xjik = yik , ∀ i ∈ V , k = 1, . . . , K
(2.7d)
j∈V
(2.7e)
i∈V
uik − ujk + Qxijk ≤ Q − qj , ∀ i, j ∈ V\{0}, i 6= j,
desde que qi + qj ≤ Q, k = 1, . . . , K (2.7f)
qi ≤ uik ≤ Q , ∀i, j ∈ V\{0}
(2.7g)
yik ∈ {0, 1} , ∀ i ∈ V , k = 1, . . . , K
(2.7h)
xijk ∈ {0, 1} , ∀ i, j ∈ V , k = 1, . . . K
(2.7i)
Nessa formulação do (PRVC), a função objetivo (2.7a) busca minimizar o somatório do custo dos arcos pertencentes ao conjunto de rotas dos veículos.
O conjunto de restrições guarda semelhança com o apresentado em (2.1), referente à formulação em fluxo de veículos de dois índices. A restrição (2.7b) assegura
que todo consumidor, com exceção do depósito, seja visitado uma única vez, por
um único veículo. A restrição (2.7c) garante que todos os veículos devem iniciar
suas rotas no depósito. Já (2.7d) assegura a continuidade da rota, ou seja, todo
veículo que chega a um determinado consumidor, com exceção do depósito, deve
partir após a realização do serviço. A restrição (2.7e) impõe que a demanda da rota
não ultrapasse a capacidade do veículo responsável por esta rota. A restrição (2.7g)
assegura que a carga atual do veículo seja maior que a demanda do consumidor i e
menor que sua capacidade máxima. Além disso, as restrições (2.7h) e (2.7i) indicam
que yik e xijk são variáveis binárias.
As restrições (2.7f) têm papel semelhante às restrições (2.1f) no caso do modelo
em dois índices. Ela garante a eliminação de sub-rotas e impõe a conectividade da
rota realizada pelo veículo k. Deve-se ressaltar que são versões generalizadas de
(2.5) e (2.6).
É importante enfatizar, ainda, que os modelos em três índices representam generalizações dos modelos em dois índices, permitindo maior flexibilidade à representação do problema de roteamento de veículos.
2.3.3
Modelo de Fluxo de Mercadorias
Os modelos de fluxo de mercadorias foram, inicialmente, introduzidos por Garvin
et al. (1957) e posteriormente por Gavish e Graves (1979) e Gavish e Graves (1982).
2.3
Formulações Matemáticas do PRVC
10
Esta formulação requer, além das variáveis usadas na formulação de fluxo de
veículos de dois índices, um novo conjunto de variáveis a serem associadas aos arcos,
as quais representam o fluxo de demanda entre eles. Além disso, este modelo requer
um grafo estendido G 0 = (V 0 , A0 ), que é obtido de G, adicionando-se o vértice n + 1,
que é uma cópia do vértice-depósito. As rotas agora partem do vértice zero para o
vértice n + 1. Duas variáveis não-negativas de fluxo, yij e yji , são associadas a cada
arco aij = (i, j) ∈ A0 . Quando um veículo viaja do consumidor i para o consumidor
j, yij e yji representam, respectivamente, a carga do veículo e a capacidade residual
do veículo ao longo do arco, ou seja, yji = Q − yij . As regras se invertem, caso
o veículo viaje de j para i. Portanto, para simplificar, a melhor formulação é:
yij + yji = Q, para qualquer arco aij = (i, j) ∈ A0 .
Para qualquer rota de uma solução factível, as variáveis de fluxo definem dois
caminhos direcionados. Um caminho parte do vértice zero para o vértice n+1 e suas
variáveis representam a carga do veículo. O outro caminho parte do vértice n + 1
para o vértice zero e suas variáveis representam a capacidade residual do veículo ao
longo do caminho. Estes caminhos descrevem um veículo que parte do vértice zero
com sua capacidade de carregamento completa, realiza entregas em cada consumidor
da rota, de acordo com suas demandas, e chega vazio ao vértice n + 1. Em seguida,
o veículo parte vazio do vértice n + 1 e coleta, em cada consumidor, uma quantidade
de mercadoria igual à sua demanda, retornando ao vértice zero com a capacidade
de carregamento completa.
O modelo é apresentado, então, como:
X
min
cij xij
(2.8a)
(i,j)∈A0
suj. a
X
j∈V 0
(yji − yij ) = 2qi , ∀ i ∈ V 0 \{0, n + 1}
(2.8b)
X
y0j = q (V 0 \{0, n + 1})
(2.8c)
X
yj0 = KQ − q (V 0 \{0, n + 1})
(2.8d)
X
y(n+1)j = KQ
(2.8e)
j∈V 0 \{0,n+1}
j∈V 0 \{0,n+1}
j∈V 0 \{0,n+1}
yij + yji = Qxij , ∀ (i, j) ∈ A0
X
(xij − xji ) = 2 , ∀ i ∈ V 0 \{0, n + 1}
(2.8f)
(2.8g)
j∈V 0
yij ≥ 0 , ∀ (i, j) ∈ A0
xij ∈ {0, 1} , ∀ i, j ∈ V
(2.8h)
(2.8i)
Nesse modelo, tem-se que:
xij : variável binária que assume o valor 1, caso o arco aij faça parte da solução
ótima do problema; ou 0, caso contrário;
cij : custo associado ao arco aij ;
2.3
Formulações Matemáticas do PRVC
11
yij e yji : carga do veículo e capacidade residual do veículo ao longo do arco direcionado aij .
A função objetivo (2.8a) minimiza o somatório do custo dos arcos pertencentes
à solução ótima. A restrição (2.8b) regula o fluxo de mercadorias nos vértices. O
fluxo de entrada menos o fluxo de saída em um consumidor é igual a duas vezes à
demanda desse consumidor. Já a restrição (2.8c) assegura que a soma das cargas do
veículo na saída do depósito zero seja igual à demanda dos consumidores da rota.
A restrição (2.8d) garante que a soma da capacidade residual do veículo na volta
ao depósito zero seja igual à diferença entre a capacidade do veículo e a demanda
da rota. A restrição (2.8e) assegura que a soma das cargas do veículo na saída do
depósito n + 1 seja igual à capacidade total da frota. A restrição (2.8f) define a
relação entre o fluxo de veículos e mercadorias. Quando um determinado veículo
atravessa o arco aij , a capacidade deste veículo é dada pela soma entre sua carga
atual e a sua capacidade residual. A restrição (2.8g) define o grau dos vértices
do grafo G 0 como 2, ou seja, em cada vértice i ∈ V 0 , com exceção dos depósitos
zero e n + 1, entram e saem exatamente dois arcos, de modo que seja assegurada a
existência do caminho em duas direções. A restrição (2.8h) assegura que a carga no
veículo será sempre maior ou igual a zero. Por fim, a restrição (2.8i) indica que xij
é uma variável binária.
2.3.4
Modelo de Particionamento de Conjuntos
A formulação em particionamento de conjuntos foi introduzida, pela primeira
vez, por Balinski e Quandt (1964). Considere que H = {H1 , . . . , Hq } seja uma
coleção de todos as rotas ou circuitos do grafo G, cada uma correspondendo a uma
rota factível, para q = |H|. Os termos associados são, então, definidos como:
cj : custo associado a cada rota Hj , representando o custo de se utilizá-la na solução
final do problema;
aij : coeficiente binário que assume o valor 1, caso o vértice i seja coberto ou visitado
pela rota Hj ; e 0, caso contrário;
xj : variável binária que assume o valor 1, se a rota Hj é selecionada na solução
ótima do problema; e 0, caso contrário.
O modelo associado é, então, dado por:
min
z=
q
X
c j xj
(2.9a)
j=1
suj. a
q
X
aij xj = 1 , ∀ i ∈ V\{0}
(2.9b)
X
xj = K
(2.9c)
j=1
q
j=1
xj ∈ {0, 1} , ∀ j = 1, . . . , q
(2.9d)
2.4
Problema de Roteamento de Veículos com Janelas de Tempo
12
Nesse modelo, a função objetivo (2.9a) representa o custo mínimo associado à
escolha ótima de rotas que o determinam. A restrição (2.9b) requer que cada cliente
i seja visitado (ou coberto) por exatamente uma única rota ou circuito, selecionado
do conjunto H. A restrição (2.9c) exige que K rotas ou circuitos sejam selecionados.
A principal desvantagem dessa formulação é a exigência de geração de todas as
possíveis rotas factíveis de uma dada instância, impraticável para casos de maior
porte.
2.4
Problema de Roteamento de Veículos com Janelas de Tempo
O Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT) é uma
extensão do PRVC na qual, além da restrição de capacidade, são adicionadas restrições relacionadas ao horário em que cada consumidor exige ser atendido. Para
cada consumidor i, é associado um intervalo de tempo [ai , bi ], chamado de Janela de
Tempo, que indica o horário em que deve ser iniciado o atendimento, e um tempo de
serviço si , que indica o período de tempo que o veículo deve aguardar a conclusão
das tarefas. O horário em que o veículo parte do depósito é adicionado ao tempo
de viagem de cada arco percorrido e ao tempo de serviço em cada consumidor visitado. No caso do veículo ter chegado mais cedo ao consumidor, é permitido que ele
aguarde o início da janela de tempo no local. O tempo de serviço só inicia-se dentro
da janela de tempo e assim que o veículo chega. Logo, o PRVJT consiste, então,
em encontrar um conjunto de rotas, com o menor custo possível, respeitando-se as
seguintes restrições:
(i) : todas as rotas têm início e término no depósito;
(ii) : cada consumidor é visitado por apenas uma rota;
(iii) : a demanda total de qualquer rota não deve superar a capacidade Q do
veículo;
(iv) : para cada consumidor i, o início do atendimento deve estar compreendido
no período de tempo dado por [ai , bi ];
(v) : o veículo deve aguardar o fim do tempo de serviço si .
Os termos associados, utilizados no modelo matemático, são:
xijk : variável binária, que assume o valor 1 caso o veículo k percorra o arco (aij );
e assume o valor 0, caso contrário;
ti : tempo de chegada do veículo no vértice i;
wi : tempo de espera do veículo no vértice i;
K : número total de veículos disponíveis;
N : número total de consumidores;
2.4
Problema de Roteamento de Veículos com Janelas de Tempo
13
dij : distância euclidiana entre os vértices i e j;
cij : custo de viagem associado ao arco aij ;
tij : tempo de viagem entre os vértices i e j;
qi : demanda do consumidor i;
Qk : capacidade do veículo k;
ai : tempo inicial da janela de tempo;
bi : tempo final da janela de tempo;
si : tempo de serviço no consumidor i;
rk : tempo máximo de duração permitido para a rota executada pelo veículo k.
A formulação matemática, proposta por Tan et al. (2001b) para o PRVJT com
frota heterogênea, é a seguinte:
min
N X
N X
K
X
i=0
suj. a:
j=0
j6=i
N
K X
X
cij xijk
(2.10a)
k=1
xijk ≤ K , i = 0
(2.10b)
k=1 j=1
N
X
xijk =
j=1
N
X
i=1
(2.10c)
xijk = 1 , i ∈ {1, . . . , N }
(2.10d)
xijk = 1 , j ∈ {1, . . . , N }
(2.10e)
j=0
j6=i
N
K X
X
k=1
xjik ≤ 1 , i = 0 , k ∈ {1, . . . , K}
j=1
N
K X
X
k=1
N
X
i=0
i6=j
qi
N
X
xjik ≤ Qk , k ∈ {1, . . . , K}
(2.10f)
j=0
j6=1
N X
N
X
xijk (tij + si + wi ) ≤ rk , k ∈ {1, . . . , K}
(2.10g)
t0 = w0 = s0 = 0
N
K X
X
xijk (tij + si + wi ) ≤ tj , j ∈ {1, . . . , N }
(2.10h)
i=0
k=1
j=0
j6=i
(2.10i)
i=0
i6=j
ai ≤ (ti + wi ) ≤ bi , i ∈ {1, . . . , N }
xijk ∈ {0, 1}
(2.10j)
(2.10k)
2.4
Problema de Roteamento de Veículos com Janelas de Tempo
14
A função objetivo (2.10a) minimiza o somatório dos custos dos arcos pertencentes
à solução ótima, visitados por cada veículo.
A restrição (2.10b) exige que todas as rotas se iniciem no depósito. O número de
veículos que parte do depósito deve ser menor ou igual ao número total de veículos
disponíveis. Caso a restrição esteja em forma de igualdade, todos os veículos são
utilizados na solução; caso contrário, nem todos os veículos são utilizados na solução
do problema. A restrição (2.10c) requer que todas as rotas devem terminar no
depósito. Todo veículo que deixa o depósito deve retornar a ele após a execução
da rota. Caso a restrição esteja em forma de igualdade, o veículo k foi utilizado na
solução do problema; caso contrário, o veículo não está sendo usado.
Já as restrições (2.10d) e (2.10e) atuam em conjunto, implicando que cada consumidor deve ser visitado uma única vez e por um único veículo. Além disso, garantem
a continuidade da rota, ou seja, quando um veículo visita um consumidor, deve partir
após o término do serviço. A restrição (2.10f) representa a limitação da capacidade
de cada rota à capacidade de carga dos veículos.
As restrições (2.10g), (2.10h), (2.10i) e (2.10j) definem as restrições de tempo
para as rotas. A restrição (2.10g) exige que o somatório do tempo das rotas percorridas não ultrapasse o tempo máximo permitido para a duração da rota. A restrição
(2.10h) requer que os tempos de partida, de serviço e de viagem do depósito sejam
iguais a zero. Já a restrição (2.10i) impõe que o somatório do tempo dos consumidores percorridos não deva exceder o tempo limite da janela de tempo do próximo
consumidor. Por fim, a restrição (2.10j) garante que o início do atendimento (tempo
de chegada mais o tempo de espera) deverá estar dentro da janela de tempo do
consumidor.
Capítulo 3
Uma Revisão de Métodos Heurísticos
Neste capítulo é feita a caracterização dos métodos heurísticos, suas aplicações,
vantagens, desvantagens e principais métodos heurísticos aplicados ao Problema de
Roteamento de Veículos com Janelas de Tempo. A seção 3.1 descreve as principais
características dos métodos heurísticos. Na seção 3.2 é apresentado o comportamento das heurísticas construtivas. Já na seção 3.3 pode ser visto a forma de atuação das principais heurísticas de refinamento. A seção 3.4 faz a descrição geral do
que são metaheurísticas. Os algoritmos baseados em colônia de formigas são vistos
na seção 3.5. Uma abordagem da metaheurística de Busca Tabu é encontrada na
seção 3.6. Por fim, na seção 3.7 a técnica de Reconexão por Caminhos é revisada.
3.1
Métodos Heurísticos
Uma heurística pode ser definida como uma técnica de procura por boas soluções
em um problema de otimização a um custo computacional compensatório, sendo,
contudo, incapaz de assegurar a qualidade da solução encontrada ou a distância da
solução até o ótimo.
Um problema de otimização combinatória pode ser definido pelo par (S, f ), no
qual:
S: conjunto de soluções s possíveis para o problema;
f : S → <: função objetivo que associa cada solução s ∈ S a um valor real f (s).
A solução para o problema consiste em se determinar a solução ótima s∗ ∈ S,
que satisfaça à relação f (s∗ ) ≤ f (s), ∀ s ∈ S (para um problema de minimização)
ou f (s∗ ) ≥ f (s), ∀ s ∈ S (para um problema de maximização).
Os principais métodos utilizados para solucionar o Problema de Roteamento de
Veículos são os métodos de programação matemática, os métodos aproximativos e
os métodos heurísticos.
A princípio, um método de programação matemática (ou exato) é sempre capaz
de determinar a solução ótima para um problema, mas, para isso, pode exigir um
tempo computacional muito alto. De acordo com Cormen et al. (2002), alguns
problemas nem mesmo possuem algoritmos exatos e, dentre os que possuem, o tempo
computacional necessário pode tornar inviável a utilização do método.
15
3.1
Métodos Heurísticos
16
Os métodos aproximativos são capazes de buscar soluções com desempenho e
tempo consideráveis, além de serem viáveis à maioria dos problemas para o qual
são utilizados. De acordo com Cormen et al. (2002), os algoritmos aproximativos, a
cada iteração, se aproximam da solução ótima, e a qualidade de solução alcançada
está diretamente relacionada ao tempo de execução.
Os métodos heurísticos são capazes de encontrar soluções viáveis em tempo de
execução polinomial, mas não garantem a qualidade da solução encontrada, ou seja,
seu caráter de otimalidade ou não.
Este trabalho se atém à discussão da aplicação de métodos heurísticos na busca
de soluções para o PRV. Portanto, os métodos de programação matemática não
serão objeto de análise. O capítulo 3 apresenta uma revisão a respeito de métodos
heurísticos.
O Problema de Roteamento de Veículos (PRV) é classificado como um problema
de complexidade NP-Difícil e, com isso, o emprego de métodos exatos para sua
resolução é restrito. Em contrapartida, métodos heurísticos têm sido amplamente
utilizados em problemas de diversas ordens, sofrendo, no entanto, das dificuldades
inerentes à indefinição da qualidade da solução encontrada. Uma revisão de métodos
heurísticos é apresentada em Blum e Roli (2003).
A maioria dos métodos exatos desenvolvidos para o PRV procura relaxar as
restrições do modelo matemático, transformando-o em problemas mais simples e
que podem ser resolvidos em tempo polinomial. A resolução do PRV através de
um método exato necessita que o problema seja expresso através de um modelo
matemático. Na seção 2.3 são vistas as formas mais utilizadas de representação
matemática deste tipo de problema.
Os problemas combinatoriais classificados como NP-Difíceis de maior porte não
possuem métodos eficientes capazes de assegurar a otimalidade da solução encontrada. Logo, os métodos heurísticos são utilizados, pois têm uma boa relação entre
os resultados gerados e tempo computacional necessário.
O Problema de Roteamento de Veículos com Janela de Tempo (PRVJT) também
é classificado como NP-Difícil. Por isso, a procura da solução ótima através da
verificação de todas as soluções é inviável em problemas de maior porte, devido ao
custo computacional necessário. Um exemplo de problema de complexidade NPDifícil é o Problema do Caixeiro Viajante (PCV), em que um viajante de negócios
(ou caixeiro viajante) deve visitar um conjunto de n cidades, passando por cada
cidade uma única vez e retornando à cidade origem, percorrendo a menor distância
possível.
O número de soluções possíveis, assumindo que a distância de uma cidade à
outra seja simétrica (a distância de ida seja igual a distância de volta), é dado pela
fórmula (n − 1)!/2. Para uma instância de 20 cidades do PCV, o número total de
soluções possíveis seria da ordem de 1016 . Um computador capaz de calcular uma
solução em 10−8 segundos gastaria 19 anos para encontrar a melhor solução usando
um método que enumere todas as soluções possíveis.
Os métodos exatos possuem técnicas que otimizam a busca, reduzindo o número
de soluções, diminuindo o esforço computacional e, conseqüentemente, o tempo,
permitindo a aplicação em instâncias de maior porte. Ainda assim, a partir de certa
dimensão, o problema se torna inviável para um método exato e a escolha de um
novo método capaz de gerar boas soluções é justificada.
3.3
Heurísticas Construtivas
17
Os métodos heurísticos podem ser classificados da seguinte forma:
heurísticas construtivas: as soluções são construídas elemento a elemento, seguindo
algum critério de classificação, até que se tenha uma solução viável;
heurísticas de refinamento: partem de uma solução inicial viável qualquer e tentam
melhorá-la através de operações diversas, até que não seja mais possível ou
exista algum outro critério de parada;
heurísticas híbridas: combinam estratégias de duas ou mais heurísticas;
metaheurísticas: heurísticas inteligentes, capazes de escapar de ótimos locais e
áreas planas, além de serem mais flexíveis em sua aplicação.
3.2
Heurísticas Construtivas
Uma heurística construtiva gera uma solução de forma incremental, de modo que,
a cada iteração, um novo elemento é escolhido para integrar a solução. O elemento
escolhido varia de acordo com a função de avaliação utilizada e com o problema
abordado. A forma mais comum de escolha é a gulosa, na qual os elementos são
classificados de acordo com a função avaliação e o elemento melhor classificado é o
escolhido. A função de avaliação costuma ser específica para cada problema.
Os métodos aleatórios são heurísticas construtivas, nos quais os elementos são
adicionados de forma aleatória à solução até que esta esteja completa.
De acordo com Stutzle e Dorigo (2000), as soluções geradas por um algoritmo
de construção gulosa geralmente são melhores que as obtidas de forma aleatória. A
desvantagem da construção gulosa é que o número de soluções possíveis é pequeno.
A figura 3.1 apresenta um pseudo-código de uma heurística de construção gulosa.
procedimento Heurística Construtiva Gulosa;
1 sp = ∅;
2 enquanto sp não estiver completa
3
e = Função Gulosa(·);
4
sp = sp ⊗ e;
5 fim-enquanto;
6 retorne sp ;
fim Heurística Construtiva Gulosa;
Figura 3.1: Heurística Construtiva Gulosa - Pseudo-código.
Os algoritmos de construção gulosa são, na maioria das vezes, os métodos de
construção mais rápidos e quase sempre geram soluções que não se aproximam da
ótima. A aplicação de uma heurística de refinamento geralmente melhora os resultados. São exemplos de heurísticas construtivas para problemas de roteamento de
veículos: Vizinho mais próximo, Clark e Wright, Inserção mais barata, etc.
3.3
Heurísticas de Refinamento
3.3
18
Heurísticas de Refinamento
As heurísticas de refinamento partem de uma solução inicial completa e tentam
encontrar uma solução de melhor qualidade em sua vizinhança. Caso encontre, a
solução corrente é substituída pela nova solução e a busca continua. Esse processo é
repetido até que não exista uma solução melhor na vizinhança da solução corrente
ou até que algum critério de parada seja atendido.
A vizinhança de uma solução pode ser definida da seguinte forma: seja S o
conjunto de todas as soluções possíveis para um determinado problema de otimização
e f a função objetivo a minimizar. Uma função g, que varia com a estrutura do
problema tratado, associa cada solução s ∈ S a uma vizinhança N (s) ⊆ S. Um
movimento m transforma uma solução s em uma outra solução s0 , que esteja em sua
vizinhança. Logo, s0 ∈ N (s) é chamado de vizinho de s. A operação da aplicação do
movimento m em s gerando o elemento s0 pode ser representada da seguinte forma:
s0 ← s ⊕ m.
A figura 3.2 demonstra o pseudo-código de um algoritmo de refinamento que
recebe uma solução qualquer e retorna o melhor vizinho da mesma, caso exista.
procedimento Heurística de Refinamento (s ∈ S);
1 s0 = MelhorVizinho(s);
2 enquanto s0 6= s
3
s = s0 ;
4
s0 = MelhorVizinho(s);
5 fim-enquanto;
6 retorne s;
fim Heurística de Refinamento;
Figura 3.2: Heurística de Refinamento - Pseudo-código.
A escolha de uma estrutura de vizinhança é crucial para o desempenho de uma
heurística de refinamento e deve ser feita de forma específica para cada problema.
A estrutura de vizinhança define o conjunto de soluções que podem ser alcançadas
a partir de s em um único passo do algoritmo. As heurísticas de busca local possuem problemas comuns, como ficar facilmente presas a ótimos locais e depender
fortemente da solução inicial para alcançar bons resultados.
As principais heurísticas de refinamento serão descritas nas próximas seções.
3.3.1
Método da Descida
O Método da Descida parte de uma solução inicial qualquer e, a cada iteração,
analisa todos os vizinhos da solução corrente. Ao final de cada iteração, o melhor
vizinho é selecionado e se torna a solução corrente, desde que este represente uma
melhoria na função objetivo do problema. Como o Método da Descida só aceita
soluções de melhora, ele termina quando quando não existe um vizinho melhor do
que a solução corrente, ou seja, uma área plana ou um ótimo local é encontrado.
O comportamento do método em um problema de minimização pode ser visto na
figura 3.3.
3.4
Método da Descida
19
Função Objetivo
Solução Inicial
Ótimo Global
Ótimo Local
Figura 3.3: Comportamento de uma heurística de refinamento.
O pseudo-código do Método da Descida aplicado à minimização de uma função
f , partindo de uma solução s e utilizando uma estrutura de vizinhança N (·) pode
ser visto na Figura 3.4.
procedimento Descida(f (.), N (.), s);
1 V = {s0 ∈ N (s) | f (s0 ) < f (s)};
2 enquanto (|V| > 0) faça
3
Selecione s0 ∈ V, sendo s0 = arg min{f (s0 ) | s0 ∈ V};
4
s ← s0 ;
5
V = {s0 ∈ N (s) | f (s0 ) < f (s)};
6 fim-enquanto;
7 retorne s;
fim Descida;
Figura 3.4: Método da Descida - Pseudo-código.
3.3.2
Descida com Primeiro de Melhora
O método tradicional de descida/subida requer que toda a vizinhança de uma
solução seja explorada a cada iteração. Isso requer, em instâncias de maior porte,
um tempo computacional muito alto. O método de descida com primeiro de melhora
interrompe a busca e move para a próxima vizinhança assim que um melhor vizinho
é encontrado. Desta forma, apenas no pior caso toda a vizinhança é explorada.
Dada uma função f , uma solução s e uma vizinhança N (·), a figura 3.5 mostra o
procedimento de descida com primeiro de melhora.
3.4
Metaheurísticas
20
procedimento P rimeiraM elhora (f (·), N (·), s);
1 V = {s0 ∈ N (s)};
2 enquanto (|V | > 0) faça
3
selecione s0 ∈ V ;
4
se f (s0 ) < f (s);
5
então s ← s0 ;
6
V = {s0 ∈ N (s)};
7
senão V ← V \{s0 };
8
fim se;
9 fim enquanto;
10 retorne s;
fim procedimento;
Figura 3.5: Descida com Primeiro de Melhora - Pseudo-código.
3.4
Metaheurísticas
A palavra heurística é oriunda do verbo grego “heurisken”, que significa procurar,
encontrar, descobrir, enquanto o sufixo “meta” significa além, em um nível superior,
segundo Blum e Roli (2003). Genericamente, pode-se extrapolar o conceito de metaheurísticas como um processo inteligente de busca por soluções.
Uma boa definição de metaheurísticas é devida à Ribeiro (2002):
“As metaheurísticas são procedimentos destinados a encontrar uma boa
solução, eventualmente a ótima, consistindo na aplicação, em cada passo,
de uma heurística subordinada, a qual tem que ser modelada para cada
problema específico.”
As metaheurísticas e as heurísticas se diferenciam por, basicamente, dois fatores.
O primeiro é a capacidade das primeiras em escapar de ótimos locais, através de
técnicas peculiares a cada uma delas. O segundo é o fato das metaheurísticas serem
mais genéricas, ou seja, são aplicadas em uma variedade maior de problemas.
A forma de exploração do espaço de soluções permite dividir as metaheurísticas
em, pelo menos, duas categorias: busca local e busca populacional.
A busca no espaço de soluções nas metaheurísticas de busca local é feita através
de movimentos aplicados sobre a solução corrente, em busca de uma outra solução de
melhor qualidade em sua vizinhança. São exemplos de metaheurísticas de busca local: Busca Tabu, Simulated Annealing, Método de Pesquisa em Vizinhança Variável
e Iterated Local Search.
Os métodos de busca populacional armazenam um conjunto de boas soluções
e as combina de formas diversas. Esta combinação tenta reunir os bons atributos
presentes nas soluções e gerar uma outra ainda melhor. São exemplos de metaheurísticas de busca populacional: Algoritmos Genéticos, Algoritmos Meméticos e
Colônia de Formigas.
3.4
Inteligência Coletiva
3.4.1
21
Inteligência Coletiva
O termo Inteligência Coletiva ou Swarm Intelligence (IS) foi empregado pela
primeira vez em 1988 por Beni (1988), para descrever um sistema robótico celular,
no qual agentes simples se organizaram através do conceito do vizinho mais próximo.
Uma definição mais geral, feita por Bonabeau et al. (1999), é:
“Inteligência Coletiva é qualquer tentativa de projetar algoritmos ou dispositivos distribuídos de resolução de problemas inspirados no comportamento coletivo das colônias de insetos sociais e de outras sociedades
animais.”
Individualmente, os insetos sociais (que vivem em sociedade) têm capacidade de
memória limitada e são capazes apenas de realizar tarefas simples. Entretanto, de
acordo com Hölldobler e Wilson (1994) e Franks (1989), o comportamento coletivo
de uma colônia de insetos sociais é capaz de prover soluções inteligentes a diversos
problemas, como:
• carregar grandes objetos;
• formar pontes;
• encontrar o caminho mais curto entre a fonte de alimento e o ninho;
• criação e manutenção do ninho;
• regular a temperatura do ninho com precisão de até 1o C;
• dar preferência à fonte de comida mais rica disponível.
Um inseto social não tem conhecimento sobre como a tarefa que realiza afeta a
colônia. Suas ações são baseadas em decisões locais, utilizando-se de conhecimentos
primitivos e com resultados, geralmente, imprevisíveis. O comportamento inteligente
da colônia nasce como uma conseqüência da organização das tarefas e do cruzamento
de informações dos diversos insetos.
De acordo com Gaertner (2004), cientistas estudam estes tipos de espécies que
se auto-organizam para tentar entender como regras tão simples podem levar a um
sistema de comportamento tão complexo. Através de modelos abstratos que imitam
esse tipo de comportamento, diversas aplicações dotadas de Inteligência Coletiva
são introduzidas no nosso dia-a-dia.
A Inteligência Coletiva, na maioria das vezes, segue alguns princípios básicos:
• é necessário um certo número de agentes para que o sistema atue de forma
inteligente;
• interações aleatórias entre os agentes são necessárias para mudar o sistema de
forma global.
Nas formigas, as interações entre os agentes são feitas de forma indireta, através
do feromônio, como será visto na seção 3.5. As abelhas, por outro lado, se comunicam através de uma forma de dança rítmica, que indica, para as abelhas ociosas,
3.5
Algoritmos de Colônia de Formigas
22
a direção e a distância em que o alimento se encontra. Quanto maior a duração e
mais freqüente a dança é feita, melhor é a fonte de comida. Mesmo que as abelhas
só vejam uma única dança antes de partirem rumo ao alimento e, além do mais,
tendo em vista a inexistência de um dispositivo que determine o controle central da
qualidade do alimento encontrado por todas elas, ainda assim os agentes coletivos
são capazes de perceber as diferenças no ambiente e otimizar a coleta de comida.
É também conhecido como sinergia esse comportamento de trabalho ou esforço
conjunto de vários subsistemas para realização de uma tarefa complexa. De forma
genérica, pode ser definido como o efeito resultante da ação de vários agentes, que
atuam da mesma forma, tendo valor da ação conjunta resultante mais significativo
que a mera atuação individual.
Desde a década de 90, a Inteligência Coletiva (IS) também é muito explorada na
comunidade de robótica. Nesse caso, um sistema de agentes coletivos costuma ser
dito mais confiável que uma única máquina de funções complexas, conforme Gaertner (2004). Em um experimento do Idaho National Engineering and Environmental
Laboratory utilizando IS em robótica, os agentes coletivos foram capazes de determinar com sucesso o perímetro de um suposto vazamento de lixo tóxico. Quanto
maior o número de robôs envolvidos no processo, mais rápida a tarefa era concluída.
3.5
Algoritmos de Colônia de Formigas
Os algoritmos baseados em Colônia de Formigas (ou Ant Colony Optimization
- ACO) têm origem nos trabalhos de Marco Dorigo que, em Dorigo et al. (1991a),
propôs o algoritmo Ant System (AS) para solucionar o Problema do Caixeiro Viajante (PCV). Esse algoritmo consiste em um sistema multi-agente, no qual o comportamento de cada agente é inspirado no comportamento das formigas na natureza
(veja, para uma revisão completa, Dorigo e Blum (2005)). A partir de então, diversas variações desse algoritmo têm sido reportadas na literatura, nas mais diversas
aplicações. Além disso, é importante relatar que, bianualmente, os principais trabalhos no tema têm sido apresentados no evento ANTS - International Workshop on
Ant Colony Optimization.
A essência dos algoritmos ACO é a combinação de informações sobre a estrutura
do problema, conhecidas a priori e imutáveis, com as informações obtidas a partir
dos resultados gerados, conhecidas a posteriori e dinâmicas. Esta combinação de informações ajuda na convergência dos resultados e torna o processo auto-catalítico,
ou seja, se alimenta dos próprios dados gerados. Outra grande vantagem dos algoritmos ACO é a facilidade com que pode ser paralelizado computacionalmente.
De acordo com Bonabeau et al. (1999), os algoritmos baseados em Colônia de
Formigas são um dos mais bem sucedidos exemplos de inteligência Coletiva e têm
sido aplicados em diversas classes de problemas combinatoriais. Uma lista de aplicações de algoritmos de colônia de formigas a problemas combinatoriais diversos,
bem como as respectivas metodologias desenvolvidas, é apresentada na tabela 3.1,
retirada de Stutzle e Dorigo (2000).
As formigas atraem a atenção de pesquisadores devido ao elevado nível de organização que uma colônia pode atingir, especialmente quando comparado à sim-
3.5
Algoritmos de Colônia de Formigas
23
Tabela 3.1: Principais aplicações da metaheurística ACO.
Aplicação
Algoritmo
Ano Referências
AS
1991 Dorigo (1992), Dorigo et al. (1991b),
Colorni et al. (1996)
Ant-Q
1995 Gambardella e Dorigo (1995)
Problema
ACS e ACS-3-opt 1996 Gambardella e Dorigo (1996),
do
Dorigo e Gambardella (1997a),
Dorigo e Gambardella (1997b)
caixeiro
MMAS
1997 Stutzle e Hoos (1997), Stutzle (1999),
Stutzle e Dorigo (2000)
viajante
ASrank
1997 Bullnheimer et al. (1999c)
BWAS
2000 Stutzle e Hoos (1997)
2004 Hendtlass (2004)
AS-QAP
1994 Maniezzo et al. (1994)
Problema
HAS − QAP a
1997 Gambardella et al. (1999b)
quadrático
MMAS-QAP
1997 Stutzle e Hoos (1997), Stutzle e Dorigo (2000)
de
ANTS-QAP
1998 Maniezzo (1999)
alocação
AS − QAP b
1999 Maniezzo e Colorni (1999)
GA-ACO-LS
2006 Xu et al. (2006)
AS-JSP
1994 Colorni et al. (1994)
Problema
AS-FSP
1997 Stutzle (1998)
de
ACS-SMTTP
1999 Bauer et al. (1999)
agendamento
ACS-SMTWTP
1999 den Besten et al. (2000)
(scheduling)
ACO-RCPS
2000 Merkle et al. (2000)
2002 T’kindt et al. (2002)
Roteamento
AS-VRP
1997 Bullnheimer et al. (1999b),
Bullnheimer et al. (1999a)
de
HAS-VRP
1999 Gambardella et al. (1999a)
veículos
2005 Gambardella et al. (2005)
ABC
1996 Schoonderwoerd et al. (1996),
Schoonderwoerd et al. (1997)
ASGA
1998 White et al. (1998)
AntNet-FS
1998 Caro e Dorigo (1998a)
Roteamento
ABC-smart ants
1998 Bonabeau et al. (1998)
de redes
AntNet e AntNet-FA 1997 Caro e Dorigo (1997), Caro e Dorigo (1998a),
Caro e Dorigo (1998b)
Regular ants
1997 Subramanian et al. (1997)
2005 Bean e Costa (2005)
Coloração
ANTCOL
1997 Costa e Hertz (1997)
de grafos
2006 Bui e Nguyen (2006)
plicidade relativa do comportamento de cada membro da colônia. Em particular
para este trabalho, um objeto de estudo interessante de uma colônia de formigas é a
capacidade de encontrar o caminho mais curto entre a fonte de alimento e o ninho.
De acordo com Wilson e Hölldobler (1990), as formigas, mesmo sendo praticamente cegas, são capazes de estabelecer o caminho mais curto entre o formigueiro
3.5
Algoritmos de Colônia de Formigas
24
e a fonte de alimento, através da cooperação entre indivíduos, usando comunicação
indireta por modificações no ambiente.
Foi estudado também por Beckers et al. (1992) a capacidade das formigas de
se adaptarem a mudanças no ambiente, como, por exemplo, encontrar um novo
caminho mais curto, a partir do momento que o antigo se torna inviável.
A figura 3.6 ilustra uma experiência feita por Goss et al. (1989) para estudar o
comportamento das formigas. Inicialmente, elas exploram, aleatoriamente, a área
ao redor do formigueiro à procura de comida. Enquanto se deslocam, depositam
sobre o solo uma substância volátil chamada feromônio, que as auxilia a encontrar o
caminho de volta ao formigueiro. Desta forma, quando uma formiga estabelece uma
trilha ou caminho entre a fonte de alimento e o formigueiro, o caminho percorrido
ficará marcado por um rastro desta substância. As demais formigas à procura de
alimento detectam a presença de feromônio no solo e tendem a escolher o caminho
com a maior concentração do mesmo. As formigas que escolheram o caminho mais
curto farão o percurso em menor tempo e o rastro de feromônio será reforçado com
uma freqüência maior que nos caminhos mais longos. Assim, os caminhos mais
eficientes, ou seja, de menor distância percorrida, receberão maior quantidade de
feromônio e tenderão a ser os mais escolhidos. Por ser uma substância volátil, a
evaporação do feromônio evita que, com o tempo, um caminho que não esteja sendo
mais utilizado continue a influenciar a decisão das formigas.
R1
L1
L4
L1
L2
R1
?
L3
R3
?
L2
(a)
R2
(b)
L1
R1
L1
R4
L4
L6
R4
R2
R5 R6
L5
L6
L5
R5 R6
R1
L2
R2
R4
L4
L2
R2
L3
R3
(c)
L3
R3
(d)
Figura 3.6: Comportamento de formigas reais.
Observa-se, então, na figura 3.6, que: em 3.6(a), as formigas chegam a um ponto
de decisão; em 3.6(b), as formigas estão escolhendo, de forma aleatória, qual o caminho a seguir; em 3.6(c), as formigas que escolheram o caminho mais curto (caminho
de baixo) alcançam o outro lado mais rapidamente; e em 3.6(d), o feromônio (representado pelas linhas) acumula mais rapidamente no caminho mais curto.
3.5
Algoritmo Ant System
3.5.1
25
Algoritmo Ant System
O algoritmo Ant System (AS), proposto por Dorigo et al. (1991a), foi o primeiro
algoritmo que utiliza a formulação de Colônia de Formigas. Sua principal importância é servir como base para a criação do paradigma ACO de criação de algoritmos.
Nesse algoritmo, a cada iteração, as formigas decidem, de acordo com uma medida probabilística, qual o caminho a seguir dentre aqueles não visitados. Cada
formiga tem uma memória, também chamada de lista tabu, que armazena os caminhos percorridos por ela e previne que um caminho seja visitado pela formiga mais
de uma vez. A probabilidade de escolha de um caminho é proporcional ao rastro de feromônio e à atratividade do mesmo - que varia de acordo com o tipo e a
modelagem do problema em que o algoritmo está sendo aplicado. Se a formiga já
percorreu aquele caminho, a probabilidade de escolha é zero; caso contrário, é positiva. A escolha do caminho a ser seguido pela formiga é feita segundo a expressão:

β
α 
·
η
τ

(r,s)
(r,s)


X β , se s 6∈ Mk
α 

τ(r,u) · η(r,u)
pk (r, s) =
(3.1)
u6∈Mk






0,
caso contrário
Essa expressão é apresentada em Dorigo et al. (1991a). Nela, tem-se que:
• pk (r, s): probabilidade da formiga k mover-se do nó r para o nó s;
• τ(r,s) : quantidade de feromônio associado ao arco (r, s);
• η(r,s) : atratividade do arco (r, s);
• U : conjunto de arcos não visitados;
• Mk : lista tabu da formiga k;
• α e β: parâmetros de controle da influência de τ(r,s) e η(r,s) . Estão situado na
faixa [0, 1].
Caso o arco não tenha sido percorrido por formigas, a deposição de feromônio no
mesmo é zero; caso contrário, é positiva.
No roteamento de veículos, o parâmetro atratividade de um arco é chamado
de visibilidade e é calculado como o inverso da distância entre os consumidores ou
vértices do arco. As figuras 3.7 e 3.8 ilustram o comportamento da formiga e os
parâmetros que influenciam na decisão probabilística da mesma.
Na figura 3.7, a cidade j está mais próxima da cidade i, na qual a formiga se
encontra. Logo, para o parâmetro visibilidade, a cidade escolhida seria a cidade j.
Já na figura 3.8, a cidade k possui um rastro de feromônio mais forte (representado por uma linha mais grossa). Logo, de acordo com esse outro parâmetro, a
cidade escolhida seria a k.
É dito que uma formiga mudou de “estado” quando se move de um nó para outro.
Ao final de cada iteração, uma taxa de evaporação remove parte do feromônio,
reduzindo a quantidade da substância nos arcos. Isso evita que as formigas fiquem
3.5
Algoritmo Ant System
26
i
?
dir
dij
j
Memória da
formiga
dik
r
ηik
ηir
k
ηij
0
1, 0
0, 5
Figura 3.7: Parâmetro Visibilidade.
i
τir
τij
j
τik
r
k
Figura 3.8: Parâmetro Rastro de Feromônio.
presas em ótimos locais e, ao mesmo tempo, diminui a probabilidade de escolha de
arcos que não foram utilizados recentemente. A expressão que determina a variação
do feromônio no algoritmo Ant System é apresentada em Dorigo et al. (1991a) e é
dada por:
τ(r,s) (t + 1) = (1 − ρ) τ(r,s) (t) + ∆τ(r,s) (t)
(3.2)
Nesta expressão, tem-se que:
• ρ: taxa de evaporação;
• τ(r,s) (t): quantidade de feromônio associado ao arco (r, s) na iteração t;
• ∆τ(r,s) (t): variação do feromônio no arco (r, s) na iteração t.
A quantidade de feromônio a ser depositada nos arcos varia de acordo com a
qualidade da solução (distância percorrida). Isso é representado em Dorigo et al.
(1991a) pela expressão:
 k
∆τ
= 0, se a formiga k não passar pelo arco (r, s);


 (r,s)
(3.3)
Q

k

∆τ(r,s) = k , se a formiga k passar pelo arco (r, s).
L (t)
Em (3.3), tem-se que:
3.5
Algoritmo Ant System
27
• Q: quantidade de feromônio de cada formiga;
• Lk (t): distância percorrida pela formiga k na iteração t;
k
• ∆τ(r,s)
: quantidade de feromônio no arco (r, s) depositado pela formiga k.
A deposição do feromônio é feita ao final de cada iteração, ao contrário do que
acontece na natureza, em que é feita durante o caminho da formiga. Por isso, para
fins de compreensão, é considerado que, ao final de cada iteração, as formigas fazem o
caminho inverso da geração da solução, mas, desta vez, depositando o feromônio. A
quantidade de feromônio associada a cada arco representa o aprendizado da colônia
no decorrer do algoritmo.
Inicialmente, conforme aponta Dorigo et al. (1991a), foram definidos três algoritmos, diferindo apenas na forma como o feromônio é depositado: Ant-density,
Ant-quantity e Ant-cycle. Nos algoritmos Ant-density e Ant-quantity, o feromônio é
depositado durante a construção da solução; no algoritmo Ant-cycle, somente após
a construção da solução. Após testes de desempenho, foi verificado que o algoritmo Ant-cycle possui, dentre os três, o melhor desempenho. Assim, os algoritmos
Ant-density e Ant-quantity foram abandonados e o algoritmo Ant-cycle passou a
ser conhecido como Ant System. Essas informações também podem ser obtidas em
Dorigo (1992), Dorigo et al. (1991b), Colorni et al. (1992) e Colorni et al. (1996). A
figura 3.9 mostra o pseudo-código do algoritmo Ant System aplicado ao PCV.
1 repita
2
Aleatoriamente posicione m formigas em n nós
3
para nó = 1 até n faça
4
para formiga = 1 até m faça
5
Escolha, probabilísticamente, o próximo nó para se mover
6
fim para
9
fim para
7
Calcule a distância percorrida de cada formiga
8
Aplique o rastro feromônio de cada formiga
10
Aplique a evaporação do feromônio
11 até Condição-de-saída
Figura 3.9: Pseudo-código do Ant System aplicado ao PCV.
O algoritmo Ant System foi desenvolvido para o PCV mas, inicialmente, não era
capaz de competir com os melhores algoritmos existentes quando de sua publicação.
Os pesquisadores, então, propuseram novas mudanças, com o intuito de melhorar
seu desempenho. A primeira melhoria introduzida, chamada de estratégia elitista,
apresentada em Dorigo (1992) e Colorni et al. (1996), consistia em dar um reforço
adicional de feromônio aos arcos pertencentes à melhor solução global. A solução que
melhor atende à função objetivo, computada desde o início do algoritmo, é chamada
de “melhor solução global”. O nome “elitista” veio da analogia aos algoritmos genéticos, nos quais os melhores indivíduos são selecionados para as próximas gerações,
visando manter suas boas características. A estratégia, então, consistia em premiar
3.5
Algoritmo Ant Colony System
28
as formigas que tivessem arcos pertencentes à melhor solução até o momento, de
forma a procurar soluções ainda melhores em sua vizinhança.
Seguindo a estratégia elitista, uma outra importante melhoria feita no algoritmo
AS padrão foi a chamada ASrank , conforme Bullnheimer et al. (1999c). Nela, a cada
iteração, as formigas são classificadas de acordo com sua performance e apenas uma
fração das melhores formigas poderá depositar feromônio. Além disso, a quantidade
de feromônio a ser depositado pelas formigas varia de acordo com a quantidade a
ser depositada pela própria formiga e pela melhor formiga.
Uma outra modificação no algoritmo AS padrão, introduzida por Stutzle e Hoos
(1997), foi chamada de MAX-MIN Ant-System (MMAS). Para evitar a rápida convergência dos resultados e/ou a possibilidade que a busca fique presa em ótimos
locais, foram introduzidos limites máximos e mínimos à quantidade de feromônio
presente nos arcos. Esses limites, através da influência do feromônio na decisão das
formigas, controlam o comportamento geral da colônia e levam os resultados para
perto dos objetivos.
A principal modificação realizada no algoritmo AS padrão é chamada de Ant
Colony System e será vista na seção 3.5.2.
3.5.2
Algoritmo Ant Colony System
O algoritmo Ant Colony System (ACS) foi introduzido em Gambardella e Dorigo
(1996), Dorigo e Gambardella (1997a) e Dorigo e Gambardella (1997b), de forma a
melhorar a performance do algoritmo Ant System.
Segundo Stutzle e Dorigo (1999), o ACS possui três importantes diferenças com
relação ao algoritmo AS padrão:
• o ACS usa um critério de seleção mais agressivo;
• o feromônio é adicionado apenas aos arcos associados à melhor solução global;
• cada vez que uma formiga percorre um determinado arco (aij ), ela remove
parte do feromônio nele depositado.
Uma das modificações do ACS em relação ao AS é um novo critério de seleção, chamado pseudo-randômico-proporcional, no qual o parâmetro q0 controla a
formação das soluções, se de forma probabilística ou de forma gulosa, conforme a
expressão:
n

β o
α 
, se q ≤ q0 ;
η(r,u)
τ(r,u)
 arg max
u6∈M
s=
(3.4)


expressão (3.1), caso contrário.
Um número aleatório q é gerado e comparado ao parâmetro q0 , cada vez que a
formiga necessita escolher o próximo nó para se mover. O algoritmo funciona de
forma gulosa se o valor de q for menor que o parâmetro q0 . Desta forma, a geração
da solução valoriza o aprendizado gerado pela deposição do feromônio. Caso o valor
de q seja maior que q0 , a geração da solução será de feita de forma probabilística,
segundo a expressão (3.1).
O processo de deposição e evaporação do feromônio no ACS foi modificado em
relação ao AS, de modo que a matriz de feromônio seja atualizada de forma global e
3.5
Algoritmo Ant Colony System
29
1 repita
2
Aleatoriamente posicione m formigas em n nós
3
para nó = 1 até n faça
4
para formiga = 1 até m faça
5
Escolha o próximo nó para se mover
6
Aplique a regra de atualização local do feromônio
7
fim para
8
fim para
9
Calcule a distância percorrida pela formiga m
10
Executar Daemon-Actions (opcional)
11
Aplique a atualização global do feromônio
12 até Condição-de-saída
Figura 3.10: Pseudo-código do Ant Colony System aplicado ao PCV.
local. A atualização global é feita para privilegiar apenas os caminhos pertencentes
à melhor solução global, ou seja, a cada iteração, após todas as formigas terem
gerado suas soluções, apenas a formiga que gerou a melhor solução desde o início do
algoritmo irá depositar feromônio. De acordo com Dorigo e Gambardella (1997b), a
atualização global do ACS evita a lenta convergência dos resultados, concentrando
as buscas na vizinhança da melhor solução. A atualização global do feromônio é
feita pela expressão:
τ(r,s) = (1 − ρ) τ(r,s) + ρ/JΨgb ,
∀ (r, s) ∈ Ψgb
(3.5)
na qual:
• τ(r,s) : quantidade de feromônio associado ao arco (r, s);
• ρ: taxa de evaporação, tal que ρ ∈ [0, 1];
• JΨgb : menor distância percorrida, computada desde o início da aplicação do
algoritmo;
• Ψgb : melhor solução computada desde o início da aplicação do algoritmo.
Segundo Ellabib et al. (2003), a fase final do algoritmo AS (fase de evaporação)
é substituída, no ACS, por uma atualização local do feromônio, com a diferença de
ser aplicada durante a construção das soluções. Cada vez que uma formiga se move
de um arco para outro, a quantidade de feromônio associado ao arco é reduzida. O
resultado da atualização local é a modificação dinâmica da possibilidade de escolha
do caminho pelas formigas. Logo, cada vez que um arco é percorrido por uma
formiga, ele se torna ligeiramente menos desejável para as demais. A forma de
atualização local do feromônio pode ser visto na expressão:
τ(r,s) = (1 − ρ) τ(r,s) + ρτ0
para
• τ(r,s) : quantidade de feromônio associado ao arco (r, s);
(3.6)
3.5
Ant Colony Optimization - Considerações Gerais
30
• ρ: taxa de evaporação, de modo que ρ ∈ [0, 1];
• τ0 : quantidade de feromônio inicial em todos os arcos.
De acordo com Gambardella et al. (1999a), um bom valor inicial para τ0 é dado
por:
1
τ0 =
nJΨh
sendo JΨh a distância percorrida, calculada pela heurística do Vizinho mais Próximo,
introduzida por Flood (1956), e n é o número de nós.
Um procedimento chamado Daemon Actions pode ser usado, opcionalmente,
para auxiliar no processo centralizado de tomada de decisões pelo ACS, em situações
como ativar um procedimento de busca local ao final de cada iteração ou depositar
uma quantidade extra de feromônio sobre a melhor solução. Esses são exemplos de
decisões que não podem ser tomadas pelas formigas individualmente. A figura 3.10
mostra o pseudo-código do algoritmo Ant Colony System aplicado ao PCV.
3.5.3
Ant Colony Optimization - Considerações Gerais
De acordo com Dorigo et al. (1999), os algoritmos baseados em colônias de formigas possuem, de uma forma geral, as seguintes características:
• apesar de cada formiga ser capaz de encontrar uma solução, soluções de boa
qualidade só emergirão como resultado da interação coletiva entre as formigas;
• cada formiga faz uso apenas de suas próprias informações, além das informações locais sobre o nó que visita;
• as formigas se comunicam apenas de forma indireta, através da leitura e escrita
nas variáveis de rastro de feromônio;
• as formigas não são adaptáveis, pelo contrário, modificam a forma como o
problema é representado e percebido para as outras formigas.
Também de acordo com Dorigo et al. (1999), as formigas da colônia possuem
também características como:
• uma formiga procura por uma solução factível de custo mínimo
Jbψ = min Jψ (L, t)
ψ
• uma formiga k possui uma memória M k que usa para armazenar informações
sobre o caminho percorrido até o momento. Esta memória pode ser usada
para: (i) construir soluções factíveis; (ii) para avaliar a solução encontrada; e
(iii) refazer o caminho de trás para frente;
• uma formiga no estado sr = hsr−1 , ii pode-se mover para qualquer nó j em
sua vizinhança factível N ki , definida como N ki = {j|(j ∈ Ni ) f (hsr , ii ∈ S)};
3.5
Comparação entre Formigas Reais e Formigas Artificiais
31
• uma formiga k pode ser associada a um estado sks e a uma ou mais condições
de parada ek ;
• formigas começam de um estado inicial e movem-se para estados vizinhos
factíveis, construindo a solução de forma incremental. O procedimento de
construção termina quando pelo menos uma condição de parada ek de de
qualquer formiga k é atingido;
• uma formiga k localizada em um nó i pode-se mover para um nó j escolhido
de N ki . O movimento é selecionado de acordo com uma regra probabilística.
• a decisão probabilística da formiga baseia-se em: (i) os valores armazenados
de forma local na estrutura do nó Ai = [aij ], chamada tabela de roteamento da
formiga, obtida através da relação entre a quantidade de feromônio presente no
nó e valores heurísticos; (ii) a memória da formiga, que armazena seu passado;
e (iii) as restrições do problema.
• quando se movem do nó i para o nó j, as formigas podem atualizar a quantidade de feromônio presente no arco (i, j). Isto é chamado atualização on line
passo-a-passo do feromônio.
• uma vez construída a solução, a formiga pode retraçar o mesmo caminho
de trás para frente, atualizando o feromônio nos arcos atravessados. Isto é
chamado de atualização on line atrasada do feromônio.
• uma vez que a formiga tenha construído a solução e atualizado o feromônio, a
formiga morre, liberando recursos.
3.5.4
Comparação entre Formigas Reais e Formigas Artificiais
As formigas “artificiais” criadas por Dorigo possuem semelhanças e diferenças com
relação às formigas “reais” encontradas na natureza. Para Dorigo et al. (1999), entre
as semelhanças encontradas, destacam-se:
• Cooperação: tanto na natureza quanto no mundo virtual as formigas cooperam
entre si através da deposição e remoção do feromônio;
• Modificações no ambiente: o feromônio depositado pelas formigas atua nas
duas realidades, modificando o ambiente e, conseqüentemente, fixando o aprendizado gerado pelas formigas;
• Objetivos: as formigas virtuais ou reais partilham alguns objetivos em comum,
como encontrar o caminho mais curto;
• Inteligência / Coletividade: nas duas realidades, a inteligência é obtida através
da coletividade, pois o comportamento individual é insuficiente ou aleatório;
• Comportamento estocástico: a forma probabilística é característica as duas
realidades.
3.6
Metaheurística Busca Tabu
32
Entretanto, existem várias diferenças entre as formigas reais e as criadas por
Dorigo. As principais são:
• Tipo de Movimento: nas formigas reais, os movimentos são contínuos, enquanto nas artificiais são discretos;
• Memória: as formigas reais não possuem uma estrutura de memória como no
caso das virtuais, que as impeça de realizar movimentos.
• Feromônio: o depósito de feromônio no mundo artificial ocorre com base na
qualidade da solução encontrada;
3.6
Metaheurística Busca Tabu
A metaheurística Busca Tabu (BT) foi proposta, de forma independente, por
dois autores, Glover (1986) e Hansen (1986), e rapidamente se tornou uma das mais
robustas e usadas metaheurísticas para a resolução de problemas combinatoriais.
Isso pode ser visualizado pela lista apresentada na tabela 3.2, retirada de Bräysy
e Gendreau (2001), na qual são referenciadas aplicações dessa técnica a problemas
diversos de otimização combinatória.
A Busca Tabu estabelece regras que regem uma heurística de refinamento na
exploração do espaço de soluções. Através do uso de uma estrutura de memória
e da aceitação de movimentos de piora, visa evitar que a busca retorne a soluções
visitadas previamente.
A estrutura de memória presente é uma dos principais características da Busca
Tabu, pois armazena o histórico da busca e guia a procura de forma adaptativa,
prevenindo que a heurística de refinamento fique presa em ótimos locais ou realize
ciclos.
A Busca Tabu funciona a partir de uma solução inicial qualquer, vasculhando
toda a vizinhança da mesma, à procura pelo melhor vizinho. O melhor vizinho
encontrado, mesmo que seja uma solução pior que a atual, se torna a nova solução
corrente e o processo é repetido até que algum critério de parada seja atingido.
3.6
Metaheurística Busca Tabu
33
Tabela 3.2: Principais aplicações da metaheurística Busca Tabu no PRVJT.
Solução inicial
Operadores
Min. Observação
Rotas
Garcia et al. (1994)
Heurística I1 do Solomon 2-opt, Or-opt
Sim Vizinhança restrita a
arcos em distâncias próximas
Rochat e Taillard (1995) Modificação da
2-opt
Não Memória adaptativa
I1 do Solomon, 2-opt
Carlton (1995)
Heurística de inserção
Realocação
Não Busca Tabu Reativa
Potvin et al. (1996)
Heurística I1 do Solomon 2-opt*, Or-opt
Sim Vizinhança restrita a
arcos em distâncias próximas
Taillard et al. (1997)
Heurística I1 do Solomon CROSS
Não Janelas de tempo folgadas,
memória adaptativa
Badeau et al. (1997)
Heurística I1 do Solomon CROSS
Não Janelas de tempo folgadas,
memória adaptativa
Chiang e Russell (1997) Modificação
λ − interchange
Não Busca Tabu Reativa
da Russell (1995)
Backer et al. (2000)
Heurística de Savings
Troca, realocação,
Não Programação de restrições
2-opt*, 2-opt, Or-opt
para checar a factibilidade das soluções
Brandão (1999)
Heurística de inserção
Realocação, troca,
Não Vizinhança restrita a
GENI
arcos em distâncias próximas
Schulze e Fahle (1999) Solomon I1, I1 paralela Ejection chains, Or-opt Sim Rotas geradas armazenadas
e heurística de Savings
em um grupo
Tan et al. (2001b)
Heurística de inserção
λ − interchange,
Não Thangiah (1994)
2-opt*
Lau et al. (2000)
Heurística de inserção
Troca, realocação
Não Diversificação baseada em restrições
Cordeau et al. (2001)
Modificação da
Realocação, GENI
Não Heurística Sweep
Lau et al. (2003)
Relocação de
Troca, realocação
Sim Lista de espera para nós não visitados,
lista de espera
limite de número de rotas
Autor
3.6
Metaheurística Busca Tabu
34
Solução
Ciclagem
Função Objetivo
Ótimo Global
Movimento de Piora
Ótimo Local
Solução
Figura 3.11: Ciclagem na Busca Tabu.
Um problema que surge ao aceitar movimentos de piora e escolher sempre o
melhor vizinho é a ciclagem. Um exemplo de ciclagem ocorre quando um ótimo local
é atingido. Nesse caso, a Busca Tabu se moverá, então, para seu melhor vizinho, o
qual possui uma solução de pior qualidade. Quando este melhor vizinho se tornar a
solução corrente e a Busca Tabu vasculhar a vizinhança a partir do mesmo, o novo
melhor vizinho será novamente o ótimo local encontrado na iteração anterior. A
figura 3.11 demonstra a ocorrência da ciclagem na Busca Tabu.
O uso de uma estrutura de memória, conhecida como lista tabu, na qual são armazenados as soluções visitadas, evita que a ciclagem ocorra, ao proibir que a busca
retorne às soluções que constam na lista. Entretanto, o tempo de processamento de
todos os dados pertencentes à solução pode tornar o processo demasiado lento ou até
mesmo o inviabilizar. Para tornar o processo menos custoso computacionalmente,
a lista tabu, geralmente, é feita de forma a armazenar apenas os movimentos de exploração da vizinhança, reduzindo a quantidade de parâmetros a serem comparados
e, conseqüentemente, o tempo computacional necessário. Isto, contudo, traz novas
dificuldades ao processo, como será visto mais adiante.
Uma lista tabu de movimentos possui movimentos proibidos (ou tabus) que,
quando realizados, podem levar a uma solução já analisada anteriormente. Porém,
existe um conflito de objetivos, pois, por um lado, uma lista tabu grande evitaria a
ciclagem e, por outro, um mesmo movimento pode levar a diferentes soluções.
A lista tabu armazena os movimentos efetuados na forma de fila, ou seja, quando
a lista atinge seu tamanho máximo e um novo movimento deve ser adicionado, o
3.7
Metaheurística Busca Tabu
35
movimento mais antigo é excluído da mesma.
O número de iterações que um movimento estará proibido de ser realizado é
definido pelo tamanho da lista tabu. Uma lista tabu muito grande pode restringir
demais a busca, pois, ao tornar tabu um grande número de movimentos, o procedimento termina de forma prematura, por não existir movimentos factíveis a realizar.
Por outro lado, uma lista tabu muito pequena aumenta as chances do processo ciclar,
pois reduz o número de iterações em que o movimento é proibido de ser realizado.
Por isso, a Busca Tabu deve manter um rigoroso controle sobre o tamanho da
lista tabu. Uma forma de se contornar estes problemas é a implementação de uma
lista de tamanho variável, também chamada de lista tabu dinâmica. Ela tem seu
tamanho alterado periodicamente no decorrer do processo de Busca Tabu, tentando
evitar que a busca fique muito restrita ou cicle. Uma revisão mais completa sobre
lista tabu dinâmicas pode ser vista em Schaefer (1996) e Dammeyer e Voß (1993).
Apesar de todos os esforços para manter uma lista tabu de tamanho adequado,
é possível que um movimento considerado tabu leve a uma solução não analisada
ainda. Neste caso, uma função de aspiração pode tornar possível a aceitação de um
movimento pertencente à lista tabu, desde que leve a uma solução desconhecida e
com bons atributos. O critério de aspiração mais comum na Busca Tabu é baseado
na função de avaliação, ou seja, o movimento tabu é aceito somente se levar a uma
solução melhor do que a melhor solução existente até o momento.
Os critérios de parada mais comuns à Busca Tabu são:
• número de iterações sem melhora: o processo pára após certo número de iterações sem melhora;
• tempo de processamento: o processo pára após um tempo de processamento
pré-determinado;
• limite a atingir: o processo pára quando um limite pré-definido é alcançado.
A Figura 3.12 apresenta o procedimento Busca Tabu. De uma forma geral, a
Busca Tabu pode ser descrita como um conjunto de soluções iniciais viáveis x ∈ X,
no qual cada solução possui um conjunto vizinhança associado, N (x) ⊂ X, chamada
de vizinhança de x. Cada solução da vizinhança x0 ∈ N (x) pode ser alcançada
a partir de x através de um movimento previamente definido. A cada iteração, a
lista tabu restringe a vizinhança N (x) a uma vizinhança N 0 (x) ⊆ N (x), no qual
os elementos de N (x) classificados como tabu não serão parte da vizinhança N 0 (x).
Os movimentos classificados como tabu são impedidos por t iterações de serem
realizados.
Para uma referência mais detalhada sobre a BT, pode-se consultar, por exemplo:
Glover (1986), Glover (1989), Glover (1990), Glover e Laguna (1993), Glover e
Laguna (1997) e Hertz e de Werra (1990). Aplicações recentes da Busca Tabu ao
PRVJT podem ser vistas em Costa (2005) e em Fraga et al. (2005).
Por fim, duas outras estratégias muito utilizadas em conjunto com a Busca Tabu,
mas que não serão abordados aqui, são as estratégias de intensificação e diversificação. A intensificação direciona a busca no espaço de soluções para áreas e movimentos que, historicamente, levam a soluções de boa qualidade. A diversificação faz
o oposto da intensificação, levando a busca à movimentos não utilizados e regiões
não exploradas do espaço de soluções e que diferem das soluções já encontradas.
3.7
Reconexão por Caminhos
36
procedimento BT (f (.), N (.), a(.), |V|, fmin , |T |, BT max, s)
1 s? ← s;
{Melhor solução obtida até então}
2 Iter ← 0;
{Contador do número de iterações}
3 M elhorIter ← 0; {Iteração mais recente que forneceu s? }
4 T ← ∅;
{Lista Tabu}
5 Inicialize a função de aspiração a;
6 enquanto (f (s) > fmin e Iter − M elhorIter < BT max) faça
7
Iter ← Iter + 1;
8
Seja s0 ← s ⊕ m o melhor elemento de V ⊂ N (s) tal que
o movimento m não seja tabu (m 6∈ T ) ou
s0 atenda a condição de aspiração (f (s0 ) < a(f (s)));
9
Atualize a lista tabu T ;
10
s ← s0 ;
11
se (f (s) < f (s? )) então
12
s? ← s;
13
M elhorIter ← Iter;
14
fim-se;
15
Atualize a função de aspiração a;
16 fim-enquanto;
17 s ← s? ;
18 Retorne s;
fim BT ;
Figura 3.12: Pseudo-código da Busca Tabu
3.7
Reconexão por Caminhos
A técnica de Reconexão por Caminhos (Path Relinking) foi introduzida por
Glover (1996) como uma estratégia de intensificação dos resultados, através da exploração de trajetórias que conectam soluções elite (melhores soluções geradas).
A idéia principal do método é unir os bons atributos pertencentes às melhores
soluções em uma única solução. Ela funciona gerando e explorando caminhos no
espaço de soluções, partindo de uma solução corrente até uma solução elite, através
de movimentos que introduzem atributos da solução elite na solução corrente. Reconexão por Caminhos pode ser usada como um processo de intensificação a cada
ótimo local encontrado e, de acordo com Glover e Laguna (1997), essa é a forma
mais eficiente de utilização do método. A figura 3.13 ilustra a idéia geral da técnica
Reconexão Por Caminhos. A partir de uma solução inicial até uma solução guia, são
geradas diversas soluções no caminho, que possuem atributos de ambas as soluções
e que podem ser melhores que ambas. A técnica é aplicada em pares de soluções
(s1 ; s2 ), sendo s1 a solução corrente, obtida após um procedimento de busca local,
e s2 uma solução escolhida aleatoriamente de um limitado conjunto de soluções
elite, gerado durante a construção das soluções. Cada solução obtida ao final de
uma busca local é considerada como uma candidata a ser inserida no conjunto elite,
desde que ela seja melhor que a solução de pior qualidade do conjunto e apresente
um percentual mínimo de diferença em relação a cada solução do conjunto elite. Se o
conjunto estiver vazio, a solução é simplesmente inserida no conjunto. Se o conjunto
3.7
Reconexão por Caminhos
Solução
Inicial
37
Solução Guia
Figura 3.13: Idéia geral da técnica Reconexão Por Caminhos.
procedimento P athRelinking;
1 g ∗ ← s;
2 Atribuir a g 0 a melhor solução entre s e g;
3 Calcular o conjunto de movimentos possiveis ∆(s; g);
4 enquanto |∆(s; g)| =
6 0 faça;
00
5
Atribuir a g a melhor solução obtida
aplicando o melhor movimento de ∆(s; g) a g ∗ ;
6
Excluir de ∆(s; g) o movimento aplicado;
7
g ∗ ← g 00 ;
8
se f (g ∗ ) < f (g 0 ) então;
9
g0 ← g∗;
10
fim se;
11 fim enquanto;
12 retorne g 0 ;
fim procedimento;
Figura 3.14: Pseudo-código Path Relinking.
elite já possui o número máximo de soluções e a solução corrente é candidata a ser
inserida neste conjunto, então esta substitui a solução de pior qualidade.
O método de Reconexão por Caminhos inicia-se computando a diferença de simetria ∆(s1 ; s2 ) entre duas soluções s1 e s2 , resultando em um conjunto de movimentos
que deve ser aplicado a uma delas, dita solução inicial, para “transformar-se” na
outra, dita solução guia. A partir da solução inicial, o melhor movimento ainda
não executado de ∆(s1 ; s2 ) é aplicado à solução corrente, até que a solução guia
seja atingida. A melhor solução encontrada ao longo dessa trajetória é considerada
como candidata à inserção no conjunto elite e a melhor solução já encontrada é
atualizada. Um exemplo da aplicação do método em soluções s1 e s2 , para o caso
de uma rota do PRV e tendo o nó 1 definido como depósito, seria posto da seguinte
3.7
Reconexão por Caminhos
38
forma. Considere que s1 e s2 sejam dados como:
s1 : 1 − 2 − 3 − 4 − 5 − 1
s2 : 1 − 4 − 3 − 5 − 2 − 1
Logo, ∆(s1 ; s2 ) = {2 → 4, 4 → 5, 5 → 2}. Supondo que o movimento 4 → 5
apresentado promova o menor custo dentre os demais possíveis, ele será o escolhido.
Assim, a nova solução s01 , sem refinamento, ficará então da seguinte forma:
s01 : 1 − 2 − 3 − 5 − 4 − 1
s2 : 1 − 4 − 3 − 5 − 2 − 1
Assim, ∆(s01 ; s2 ) = {2 → 4, 4 → 2}. A solução s01 é formada por atributos de ambas
as soluções s1 e s2 . Observe que, quando o último movimento 2 → 4 for realizado, as
soluções s1 e s2 serão iguais. O pseudo-código da técnica de reconexão por caminhos
é apresentado na figura 3.14.
Uma aplicação da técnica de Reconexão por Caminhos ao PRVJT pode ser vista
em Ho e Gendreau (2006).
Capítulo 4
Metodologia Ant-TPR para
Resolução do PRVJT
Neste capítulo, é feita a descrição da metodologia proposta, de suas etapas de construção e do algoritmo final proposto. A seção 4.1 descreve as etapas de construção
a suas características. A seção 4.2 demonstra a forma de representação das soluções
geradas. Diferentes funções de avaliação para o algoritmo são propostas na seção
4.3. Os movimentos de realocação utilizados no algoritmo são vistos na seção 4.4.
Por fim, a seção 4.5 faz o detalhamento do algoritmo desenvolvido.
4.1
Metodologia Ant-TPR
A metodologia Ant-PR proposta consiste em, inicialmente, definir uma forma
de representação das soluções geradas. Em seguida, são definidos os movimentos de
realocação e a estrutura de vizinhança utilizados no algoritmo. Além disso, também
são definidas duas funções de avaliação, para controle da qualidade das soluções
geradas. Por fim, são definidos os parâmetros utilizados, as adaptações feitas e a
junção das metaheurísticas Ant Colony Optimization e Busca Tabu e da técnica de
intensificação Reconexão por Caminhos. Cabe ressaltar que a metodologia Ant-TPR
foi elaborada e implementada exclusivamente para o PRVJT. Sua descrição geral é
realizada a seguir e o pseudo-código associado está apresentado na figura 4.4.
4.2
Forma de Representação das Soluções
A representação da solução no PRVJT consiste em um conjunto de rotas, geradas
através do algoritmo desenvolvido para a solução do problema, que possuem um
determinado custo associado, atribuído por uma função de avaliação, definida na
seção 4.3. Na tabela 4.1 é apresentada a forma de representação de uma solução
Tabela 4.1: Forma de representação de uma solução.
D−5−6−7−D
D−1−D
D − 2 − 3 − 4 − D 450, 00
|
{z
Rota 1
} |
{z
Rota 2
} |
39
{z
Rota 3
} | {z }
Custo
4.3
Funções de Avaliação
40
2
1
7
3
D
6
5
4
Figura 4.1: Instância fictícia de 7 cidades.
para uma instância do PRV de sete cidades, apresentada na figura 4.1, no qual cada
campo constitui uma rota, tendo custo dado pelo campo específico.
4.3
Funções de Avaliação
Inicialmente, foram definidos dois tipos de função de avaliação para as soluções
geradas. A primeira função faz a avaliação das soluções através da penalização das
restrições violadas. Já a segunda função atua de forma lexicográfica.
A primeira função de avaliação proposta, baseada no conceito de penalidades, é
dada por:
X
f (s) = µN (s) + αE(s) + βW (s) +
drs
(4.1)
(r,s)∈A
Na expressão, tem-se que:
• N (s): número de veículos empregados na solução;
• E(s): soma dos excessos de capacidade de todos os veículos (zero, caso não
ocorra);
• W (s): soma de todas as violações referentes às restrições de janelas de tempo;
• µ, α e β: fatores de penalidades não negativos e auto-adaptativos, sendo α
associado à capacidade dos veículos; β associado à maior janela de tempo da
instância; e µ associado ao número de cidades da instância elevado ao quadrado
(conforme proposto em Taillard et al. (1997));
• drs : distância entre os consumidores (r, s);
• A: conjunto dos arcos pertencentes à solução gerada.
Esta função de avaliação penaliza as violações das restrições do problema, caso
existam, de forma auto-adaptativa para a instância em questão.
4.4
Movimentos de Realocação
41
Nela, os principais objetivos a serem cumpridos são dados pelo primeiro e quarto
termos da expressão, que são, respectivamente, a minimização do número de veículos utilizados na solução e a minimização da distância total percorrida. O primeiro
termo da expressão deve ser subtraído do resultado final, pois atua somente para
possibilitar a busca no sentido da minimização da frota, não tendo, portanto, relação
com o custo final da solução encontrada. O segundo e o terceiro termos serão sempre nulos em soluções viáveis, ou seja, quando não ocorrem violação das restrições
existentes no problema.
A outra função de avaliação utilizada é lexicográfica, ou seja, formada por um
conjunto de objetivos distintos, classificados segundo um critério de prioridades.
Nesta metodologia, três objetivos são considerados, na seguinte ordem de prioridade:
• primeiro: minimizar o número de veículos utilizados;
• segundo: minimizar o número de consumidores na menor rota;
• terceiro: minimizar a distância total percorrida.
De forma geral, nos métodos heurísticos, a solução é feita em duas fases, de modo
que, inicialmente, é feita a redução do número de veículos, capaz de atender a todos
os consumidores, e, em seguida, ser feita a minimização da distância percorrida.
Nesta metodologia, cada nova solução gerada é comparada com a anterior, avaliando-se, primeiramente, o critério de maior prioridade. O próximo objetivo é
avaliado somente caso a avaliação com relação a este primeiro critério produza um
resultado melhor ou igual à solução anterior. Existem duas etapas na fase de busca
local. Na primeiro delas, o segundo objetivo é utilizado, até que um ótimo local
seja atingido. Então, na segunda etapa, este objetivo é descartado e o seguinte
(minimização da distância percorrida) assume seu lugar.
4.4
Movimentos de Realocação
Um movimento de realocação consiste em retirar um consumidor de uma rota
qualquer e inseri-lo em uma outra posição, que pode ser tanto dentro da mesma rota
quanto em uma outra rota distinta.
O movimento de realocação dentro de uma mesma rota é chamado de realocação
Intra-rota. Na figura 4.2, o consumidor 4 estava situado entre o consumidor 10 e o
depósito (0) e foi realocado para entre os consumidores 6 e 3 da mesma rota.
O movimento de realocação envolvendo duas rotas distintas é chamado realocação Inter-Rotas. Na figura 4.3, o consumidor 4 estava situado entre o consumidor
10 e depósito (0) de uma rota e foi realocado para entre os consumidores 2 e 8 de
uma outra rota.
A estrutura de vizinhança considerada neste trabalho combina os dois tipos de
movimentos anteriores. Assim, nesta estrutura, um vizinho s0 é obtido de uma
solução s através de movimentos de realocação intra-rotas ou inter-rotas.
Uma estratégia interessante e muito simples, chamada de Elimina Rotas, é proposta no presente trabalho, para contribuir com o objetivo de minimização do
número de veículos. A estratégia consiste em aplicar os movimentos de realocação
de forma ordenada, de modo que os consumidores são escolhidos a partir da menor
4.5
Algoritmo Ant-TPR
42
Figura 4.2: Movimento de realocação Intra-rota.
Figura 4.3: Movimento de realocação Inter-rotas.
rota e realocados a partir da maior rota, privilegiando a eliminação de consumidores
das menores rotas e a manutenção das maiores rotas. Porém, se um dos consumidores da rota não pode ser realocado, a rota deve ser deixada inalterada e o processo
continua para as demais rotas, até que os consumidores pertencentes à maior rota
sejam analisados. Esta estratégia simples e de pouco esforço computacional proporciona forte redução do número de veículos, principalmente nas iterações iniciais, nas
quais o nível de feromônio nos arcos é igual ou muito próximo e as formigas acabam
atuando de forma gulosa, ou seja, o aprendizado dado pelo feromônio ainda não
influencia na tomada de decisões.
4.5
Algoritmo Ant-TPR
Os algoritmos desenvolvidos baseados em colônia de formigas são apenas conceituais, ou seja, podem ser implementados de diversas maneiras. Nesta seção serão
apresentados os passos da implementação da metodologia Ant-TPR.
Nos algoritmos ACO padrão, a cada iteração é gerado um certo número de
formigas e cada uma delas gera uma solução completa para o problema. Pelo fato de
os algoritmos ACO terem sido desenvolvidos, inicialmente, para o PCV, no qual não
existem restrições de capacidade ou janelas de tempo, esta seria uma forma simples
e eficiente para a atuação de cada formiga.
Porém, no PRVJT, estas restrições estão presentes e cada algoritmo procura se
adaptar a estas restrições de forma diferente.
4.5
Algoritmo Ant-TPR
43
A maioria dos autores contorna esse problema através da criação de depósitos
fictícios, quando necessário. Todas as formigas partem do depósito e, sempre que
uma formiga não consegue dar continuidade à formação de sua rota (devido às
restrições existentes), ela retorna ao depósito. Porém, como a memória de cada
formiga previne que ela retorne aos consumidores já visitados, um novo depósito
(fictício ou virtual) é criado, com as mesmas coordenadas do depósito original e o
processo continua, até que todos os consumidores sejam visitados por cada formiga.
Ao final de cada iteração, existe sempre o número pré-definido de formigas e cada
formiga sozinha é responsável por uma solução completa para o problema.
Nesta metodologia, a adaptação para o PRVJT foi tratada de forma diferente,
pois cada solução é formada por uma ou mais formigas. A cada iteração, uma lista
restrita de consumidores candidatos (LRCC) é gerada, contendo todos os consumidores (com exceção do depósito) da instância a ser solucionada. Além disso, uma
lista tabu para nascimento de novas formigas (LTPNNF) e uma lista tabu geral das
formigas (LTGF) (que representa a memória da formiga) são geradas, contendo,
inicialmente, apenas o depósito. Um vetor de rotas geral (VRG) é criado e, inicialmente, não contém nenhuma rota. Em seguida, uma formiga é atribuida a um
consumidor qualquer, escolhido aleatoriamente dentre os consumidores da LRCC, de
modo que o consumidor selecionado nunca pertencerá à LTPNNF. A LTPNNF evita
que, em uma futura iteração, uma formiga seja colocada ou em uma posição que não
permita a formação de novas rotas ou em uma posição já colocada anteriormente.
Um vetor de rotas para a formiga é então iniciado e, caso o consumidor escolhido
já pertença a alguma rota, o vetor rota da formiga (VRF) receberá, desse modo, a
rota do consumidor. A formiga escolhe, dentre os consumidores da LRCC, para qual
consumidor se moverá, de acordo com a expressão (3.4). Cada formiga possui sua
própria lista tabu (LTF) que, inicialmente, é uma cópia da LTGF e para a qual serão
movidos os consumidores analisados. A função da LTGF é evitar que as formigas
visitem consumidores que estejam no meio de rotas, ou seja, que não estejam ou
na primeira ou na última posição dos vetores de rotas das formigas. A união entre
rotas geradas pelas formigas só é possível quando os consumidores envolvidos estão
nas extremidades de cada rota. Quando o consumidor escolhido pela formiga já
pertencer a uma rota, o algoritmo selecionará a rota do consumidor escolhido e
tentará realizar a união.
A cada tentativa mal-sucedida de movimento da formiga (violação de qualquer
uma das restrições existentes), a LTF receberá o consumidor envolvido, para que ela
não retorne aos consumidores já analisados. Caso o movimento da formiga de um
consumidor para outro respeite todas as restrições, a LTGF e o VRG são, então,
atualizados, e a LTF recebe novamente a LTGF. A formiga, assim, move-se para o
último consumidor da rota gerada e continua seus movimentos, até que não existam
mais movimentos possíveis, ou seja, até que todos os consumidores pertençam à
LTF. A formiga, neste caso, é eliminada; sua rota gerada fica armazenada no VRG;
a LRCC e a LTPNNF são atualizadas, de acordo com a LTGF; e uma nova formiga
será gerada. Quando não existirem mais consumidores na LRCC, o custo da solução
gerado pelo conjunto de formigas é analisado e a matriz de feromônio é atualizada.
O psedo-código da metodologia Ant-TPR é apresentado na figura 4.4.
A atuação da metodologia Ant-TPR será demonstrada nas figuras a seguir. A
figura 4.5 mostra uma instância fictícia do PRVJT com 7 consumidores a ser solu-
4.5
Algoritmo Ant-TPR
44
1 MelhorSolução ← PiorSoluçãoPossível
2 MelhorSoluçãoAnterior ← PiorSoluçãoPossível
3 enquanto <> CondiçãoSaída
4
Inicia parâmetros
5
ContaSoluções ← 0
6
enquanto ContaSoluções ≤ 10 OU
FO(SoluçãoGerada) ≥ FO(MelhorSoluçãoAnterior)
7
ListaRestritadeConsumid.Candidatos (LRCC) ← Consumidores da instância
8
ListaTabuParaNascimentodeNovasFormigas (LTPNNF) ← Depósito
9
Lista Tabu Geral das Formigas (LTGF) ← Depósito
10
enquanto LRCC <> 0
11
Selecione aleatoriamente um dos consumidores da LRCC
12
Posicione uma formiga no consumidor selecionado
13
Lista Tabu da Formiga (LTF) ← LTGF
14
enquanto LTF < NúmeroConsumidoresInstância
15
De acordo com o critério de seleção, escolha o próximo movimento
16
Atualizar: LTF, LRCC, VGR
17
fim enquanto
18
fim enquanto
19
se FO(SoluçãoGerada) < FO(MelhorSoluçãoAnterior)
20
então MelhorSoluçãoAnterior ← SoluçãoGerada
Saia do laço enquanto (6)
21
senão ContaSoluções ← ContaSoluções + 1
22
fim se
23
fim enquanto
24
Aplique Busca Local na SoluçãoGerada
25
Aplique Reconexão a cada n iterações
26
se FO(SoluçãoGerada) < FO(MelhorSolução)
27
então se ContaSoluções > 50
28
então TABU
29
fim se
30
MelhorSolução ← SoluçãoGerada
31
fim se
32 fim enquanto
Figura 4.4: Pseudo-código Ant-TPR.
cionada.
Na figura 4.6, uma formiga foi posicionada, de forma aleatória, no consumidor
2. As linhas partindo desse consumidor para cada um dos demais representam suas
opções de movimento.
Baseado nas equações de escolha descritas na expressão (3.4) e respeitando-se as
restrições existentes, supõe-se que o movimento executado foi partir do consumidor
2 para o consumidor 3. Nessa posição, a formiga analisa suas novas opções, como
visto na figura 4.7.
4.5
Algoritmo Ant-TPR
45
2
1
7
3
D
6
4
5
Figura 4.5: Instância do PRVJT a ser solucionada.
1
7
6
D
3
4
5
Figura 4.6: A formiga analisa suas opções de movimento.
Novamente, como pode ser visto na figura 4.8, partindo da cidade 3 e supondo
que o novo consumidor escolhido seja o consumidor 4, a formiga analisa suas opções
de movimento.
No momento em que não mais existirem movimentos possíveis para a formiga
executar (devido às restrições ou caso todos os consumidores já tenham sido visitados), as ligações ao depósito são feitas e a rota gerada pela formiga será integrada
ao conjunto de rotas (fig. 4.9).
Por fim, na figura 4.10 uma nova formiga é aleatoriamente posicionada em um
consumidor que não pertença a nenhuma rota, analisa suas opções de movimento e
continua o processo, até que não existam mais consumidores fora de rotas.
Logo, uma solução completa e factível é gerada pelo conjunto de formigas e o
algoritmo entrará na fase de refinamento (Daemon actions), conforme a figura 4.11.
A fase de refinamento quase sempre é capaz de melhorar as soluções geradas pelas
formigas.
A solução criada por Dorigo et al. (1991a), e seguida pela maioria dos autores,
é mais simples, pois utiliza apenas uma memória para cada formiga, sendo cada
formiga responsável por uma solução completa. Entretanto, a modelagem das formigas desta forma não permite que uma escolha inicialmente ruim se torne uma escolha
4.5
Algoritmo Ant-TPR
46
2
1
7
D
6
4
5
Figura 4.7: Após movimentar-se, a formiga analisa suas novas opções de movimento.
2
1
7
6
D
3
5
Figura 4.8: A formação da rota continua, enquanto gerar soluções factíveis.
melhor. Um exemplo é apresentado nas figuras 4.12 e 4.13. Suponha que o primeiro
consumidor escolhido para integrar uma rota tenha uma janela de tempo em que
mais correto seria atendê-lo por último (representado na figura 4.12 pelo consumidor
1). A formiga se moverá para o consumidor e dará prosseguimento à formação de
sua rota, concretizando a má escolha, como pode ser visto na figura 4.13.
Da forma como a metodologia Ant-TPR foi modelada, esse fato tem menor
chance de ocorrer, pois os consumidores que pertencem às extremidade de rotas
podem fazer parte de novas rotas em formação, desde que respeitem as restrições
existentes. Logo, uma nova formiga pode desfazer a rota do consumidor 1 e anexá-la
a uma nova rota, desde que represente uma melhora na função objetivo, conforme
a figura 4.15.
Em lugar de gerar um conjunto fixo de soluções por iteração, são geradas novas
soluções, até que surja uma solução melhor que a melhor solução da iteração anterior ou até um valor escolhido (foi adotado, de forma experimental, o valor 10).
A solução encontrada é refinada por uma heurística de busca local e a função desenvolvida de eliminação de rotas completas. Após certo número de iterações, o
processo de Busca Tabu é acionado sempre que ocorra uma melhora no valor da
função objetivo. Esse intervalo de tempo sem a atuação da BT é necessário porque,
4.5
Algoritmo Ant-TPR
47
2
1
7
6
3
D
4
5
Figura 4.9: Ao final da excursão da formiga, são adicionadas ligações ao depósito.
2
7
6
D
3
4
5
Figura 4.10: Uma nova formiga é posicionada e o processo continua.
inicialmente, não existe a inteligência gerada pelo aprendizado das formigas. Foi
definido, experimentalmente, o valor de 50 iterações como tempo mínimo necessário
ao aprendizado das formigas, a partir do qual a Busca Tabu é acionada. Devido ao
elevado número de possibilidades combinatórias, a BT tem mais chances de alcançar
melhores resultados, pois atua de forma dependente da solução inicial e, com isso,
é capaz de um refinamento mais apurado. Periodicamente, o processo de reconexão
por caminhos é acionado, tentando trazer bons atributos da melhor solução existente
para a solução corrente (também experimentalmente, foi definido um valor de 15%
do número de consumidores da instância).
4.5
Algoritmo Ant-TPR
48
2
1
7
3
D
6
4
5
Figura 4.11: Solução completa e factível gerada pelas formigas.
2
1
7
3
D
6
4
5
Figura 4.12: O consumidor 1 isolado em uma rota.
2
1
7
6
D
3
4
5
Figura 4.13: Solução prejudicada pelo consumidor 1.
4.5
Algoritmo Ant-TPR
49
2
1
7
3
D
6
4
5
Figura 4.14: Ant-TPR: O consumidor 1 momentaneamente isolado em uma rota.
2
1
7
6
D
3
4
5
Figura 4.15: Ant-TPR: Formiga integra o consumidor 1 à nova rota formada.
Capítulo 5
Resultados Computacionais
Neste capítulo, são relatados os resultados computacionais obtidos pela metodologia Ant-TPR proposta, detalhes de sua implementação, além de comparações com
outras metodologias relevantes para o Problema de Roteamento de Veículos com
Janelas de Tempo. A seção 5.1 começa abordando detalhes de implementação do
software desenvolvido. Em seguida, apresenta-se a comparação das funções de avaliação propostas na seção 4.3, de modo a permitir a escolha daquela que melhor se
adeque aos objetivos desse trabalho. Por fim, são mostrados os melhores resultados
obtidos e são feitas comparações com as demais metodologias relevantes.
5.1
Implementação da Metodologia Ant-TPR
O algoritmo Ant-TPR foi implementado em linguagem C + +, utilizando o compilador Builder 5.0 da Borland, e executado em um computador Pentium 4 2.4 GHz,
com 512 MB de memória RAM, sob plataforma Windows XP Pro. Foram utilizadas,
para teste, as instâncias, ou problemas-teste, introduzidos por Solomon (1987), usados amplamente como referência de desempenho de algoritmos para o PRVJT. Essas
instâncias são formadas por três grupos distintos de consumidores, a saber:
• grupo C - os consumidores estão distribuídos geograficamente em grupos de
consumidores agrupados (clustering) uns dos outros;
• grupo R - os consumidores são distribuídos aleatoriamente (randoming) e distantes uns dos outros;
• grupo RC - uma mistura dos dois grupos anteriores.
As instâncias do tipo 1, ou seja, C1, R1 e RC1, possuem janelas de tempo
estreitas, nas quais o intervalo de tempo em que o serviço em cada consumidor deve
ser iniciado é definido por intervalos curtos de tempo. Já nas instâncias do tipo 2
(C2, R2 e RC2), os intervalos de janelas de tempo são maiores e, por isso, diz-se que
esses problemas apresentam janelas de tempo largas.
A Tabela 5.1 descreve o formato dos problemas-teste utilizados. Nesta tabela,
cada campo tem o seguinte significado:
• NumCidades: representa o número de cidades consideradas na instância;
50
5.1
Implementação da Metodologia Ant-TPR
51
Tabela 5.1: Formato das instâncias Solomon para o PRVJT
NumCidades
CapacVeic
IdCidade
CoordX CoordY Demanda InícioJT FimJT TS
• CapacVeic: representa a capacidade dos veículos utilizados;
• IdCidade: número ou nome que identifica uma certa cidade;
• CoordX e CoordY: coordenadas geográficas que definem a localização da cidade
identificada;
• Demanda: representa a demanda requerida pela cidade identificada;
• InícioJT e FimJT: intervalo de janela de tempo definido para a cidade identificada;
• TS: tempo gasto para realizar o serviço na dada cidade identificada.
Inicialmente, a metodologia Ant-TPR foi testada com diferentes tipos de função
de avaliação, de forma a determinar qual seria a melhor proposta.
A primeira função de avaliação objeto de teste é baseada em penalidades, conforme a expressão (4.1), mas tendo o primeiro termo desconsiderado, ou seja, a minimização da frota não sendo considerado um objetivo a ser atingido. Essa primeira
versão é referenciada neste trabalho como Ant-P.
A segunda função de avaliação é a apresentada na expressão (4.1), considerandose todos os termos em questão. É referenciada como Ant-P2.
A terceira função de avaliação é lexicográfica, tendo sido apresentada na seção
4.3. É denominada como Ant-L e, como será visto ao longo desse capítulo, produziu
os melhores resultados. Como o algoritmo Ant-L foi avaliado por tempo de execução
e os demais por número de iterações, foi escolhido uma faixa de tempo equivalente
para comparação dos mesmos. Os resultados gerados por cada algoritmo podem ser
vistos na tabela 5.2.
Tabela 5.2: Comparação entre as funções de avaliação propostas.
R1
R2
C1
C2
RC1
RC2
Total
(a)
13, 83
5,18 10,00 3,00 13,38
6,13
493(d)
Ant-P 1204, 42(b) 901,67 826,98 587,38 1374,29 1037,74 55809(e)
1062, 5(c) 712,3 779,1 352,0 955,5 685,5 43540(f)
Ant-P2
Ant-L
13,17
1237,67
873,0
12,42
1227,92
609,7
4,75
1317,49
1072,0
3,09
972,41
623,2
10,00
829,05
837,7
10,00
838,12
611,6
3,00
595,06
383,5
3,00
591,05
602,0
13,00
1397,26
1017,9
12,13
1396,26
621,6
4,13
1117,34
778,2
3,38
1184,78
611,1
447
57731
44028
421
58351
34354
Para a tabela 5.2, tem-se (os valores são referentes às melhores soluções encontradas durante as execuções):
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
52
• (a) é o valor médio do número de veículos da solução;
• (b) é a média da distância total percorrida;
• (c) é a média do tempo computacional gasto, em segundos;
• (d) é a soma do número de veículos de todas as soluções;
• (e) é a distância total percorrida;
• (f ) é a soma do tempo computacional total de todas as instâncias.
Conforme pode ser visto na tabela 5.2, o algoritmo com função de avaliação
lexicográfica produziu os melhores resultados dentre os testado. O Ant-L produziu
o menor número de veículos e em menor tempo. Entretanto, os demais algoritmos
foram capazes de uma maior redução na distância total percorrida. É confirmado
pela literatura que os objetivos podem ser antagônicos. O algoritmo de função de
avaliação lexicográfica Ant-L passou então a ser chamado Ant-TPR, em analogia a
associação Formiga - Busca Tabu - Reconexão por Caminhos (Ant - Tabu Search Path Relinking).
Em Fraga et al. (2006b) e Fraga et al. (2006a) podem ser vistos mais detalhes
de implementação e resultados sobre funções de avaliação similares utilizadas na
resolução do mesmo problema.
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
O algoritmo Ant-TPR desenvolvido foi avaliado em cinco intervalos de tempo
pré-definidos: 100, 600, 1200 e 3600 segundos, com a finalidade de se conhecer o
comportamento do método em diversas situações. O algoritmo é interrompido na
primeira iteração após o tempo pré-determinado, gerando pequenas variações no
tempo de execução. Para cada intervalo de tempo, foram feitas dez execuções por
instância, cada uma delas partindo de uma semente diferente de números aleatórios.
Os melhores resultados produzidos pela metodologia Ant-TPR em cada instância podem ser vistos nas Tabelas 5.3, 5.4, 5.5, 5.6, 5.7 e 5.8. Os ótimos globais ou
melhores resultados obtidos de heurísticas diversas que são reportados neste trabalho foram obtidos de Sintef (2005). As colunas “Ant-TPR” mostram os melhores
resultados produzidos pela metodologia proposta.
Para o grupo C de instâncias (conforme Tabelas 5.3 e 5.4), todos os ótimos globais
são conhecidos na literatura. Em 16 das 17 instâncias desse grupo, o algoritmo AntTPR foi capaz de encontrá-los e, em 9 delas, os ótimos locais foram encontrados em
até 100 segundos. O número de veículos encontrados em todo o grupo C foi igual
ao relatado na literatura.
Para o subgrupo R1 (conforme Tabelas 5.5 e 5.6), duas instâncias (R101 e R102)
tiveram resultados melhores que os da literatura. No subgrupo R2, o algoritmo AntTPR produziu resultados com apenas um veículo acima dos resultados relatados na
literatura.
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
53
Tabela 5.3: Resultados da metodologia Ant-TPR nas instâncias C1.
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
C101
10,00
828,94
10,00
828,94
C102
10,00
828,94
10,00
828,94
C103
10,00
828,06
10,00
828,06
C104
10,00
824,78
10,00
825,54
C105
10,00
828,94
10,00
828,94
C106
10,00
828,94
10,00
828,94
C107
10,00
828,94
10,00
828,94
C108
10,00
828,94
10,00
828,94
C109
10,00
828,94
10,00
828,94
Média
10,00
828,38
10,00
828,46
Tabela 5.4: Melhores resultados da metodologia Ant-TPR nas instâncias C2.
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
C201
3,00
591,56
3,00
591,56
C202
3,00
591,56
3,00
591,56
C203
3,00
591,17
3,00
591,17
C204
3,00
590,60
3,00
590,60
C205
3,00
588,88
3,00
588,88
C206
3,00
588,49
3,00
588,49
C207
3,00
588,29
3,00
588,29
C208
3,00
588,32
3,00
588,32
Média
3,00
589,86
3,00
589,86
A instância RC107 do subgrupo RC1 (Tabela 5.7) obteve um resultado melhor
que o encontrado na literatura. O subgrupo RC2 (Tabela 5.7) obteve um resultado
com apenas um veículo a mais que a soma dos melhores resultados da literatura.
Na tabela 5.9 (adaptada a partir de Gambardella et al. (1999a)), a metodologia
Ant-TPR é comparada a outras metodologias quanto à eficiência (tempo necessário)
na resolução das instâncias Solomon de 100 consumidores. Os métodos considerados
foram:
• Adaptive memory programming, de Rochat e Taillard (1995), designado como
(RT);
• Large neighbourhood search, de Shaw (1998), nomeado como (SW);
• Guided local search, a partir de Kilby et al. (1999), identificado como (KPS);
• Alternate K-exchange Reduction, de Cordone e Wolfler-Calvo (2001), chamada
de (CW);
• MACS-VRPTW: Multiple Ant Colony System, de Gambardella et al. (1999a),
chamado de (MACS);
• Adaptive memory programming de Taillard et al. (1997), denominado de (TB);
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
54
Tabela 5.5: Melhores resultados da metodologia Ant-TPR nas instâncias R1
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
R101
19,00
1645,79
18,00
1615,23
R102
17,00
1486,12
17,00
1441,77
R103
13,00
1292,68
13,00
1303,04
R104
9,00
1007,24
10,00
1001,47
R105
14,00
1377,11
14,00
1385,30
R106
12,00
1251,98
12,00
1253,53
R107
10,00
1104,66
10,00
1169,32
R108
9,00
960,88
9,00
1004,73
R109
11,00
1194,73
12,00
1176,25
R110
10,00
1118,59
11,00
1136,08
R111
10,00
1096,72
11,00
1066,84
R112
9,00
982,14
10,00
985,75
Média
11,92
1209,89
12,25
1211,61
Tabela 5.6: Melhores resultados da metodologia Ant-TPR nas instâncias R2
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
R201
4,00
1252,37
4,00
1256,23
R202
3,00
1191,70
3,00
1238,08
R203
3,00
939,54
3,00
961,13
R204
2,00
825,52
2,00
853,60
R205
3,00
994,42
3,00
1021,50
R206
3,00
906,14
3,00
935,66
R207
2,00
890,61
2,00
957,19
R208
2,00
726,75
2,00
739,49
R209
3,00
909,16
3,00
923,72
R210
3,00
939,34
3,00
971,67
R211
2,00
892,71
3,00
798,22
Média
2,73
951,66
2,82
968,77
• Parallel Hybrid Genetic Algorithm, de Berger et al. (2001), referenciado como
(BBB).
A tabela 5.9 mostra, ainda, três colunas para cada subgrupo de instâncias, denominadas como:
• V - média de veículos (objetivo principal);
• D - média das distâncias percorridas;
• T - tempo de execução.
Todos os resultados são referentes às melhores soluções encontradas dentre o número
de execuções feitas (10) para cada instância.
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
Tabela 5.7: Melhores resultados da metodologia Ant-TPR nas instâncias RC1
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
RC101
14,00
1696,94
15,00
1638,29
RC102
12,00
1554,75
13,00
1500,49
RC103
11,00
1261,67
11,00
1277,48
RC104
10,00
1135,48
10,00
1155,82
RC105
13,00
1629,44
14,00
1536,43
RC106
11,00
1424,73
12,00
1401,66
RC107
11,00
1230,48
11,00
1216,96
RC108
10,00
1139,82
11,00
1143,60
Média
11,50
1384,16
12,13
1358,84
Tabela 5.8: Melhores resultados da metodologia Ant-TPR nas instâncias RC2
Instância Veic. Lit. Dist. Lit. Veic. Ant-TPR Dist. Ant-TPR
RC201
4,00
1406,91
4,00
1432,05
RC202
3,00
1365,65
4,00
1206,51
RC203
3,00
1049,62
3,00
1060,45
RC204
3,00
798,41
3,00
800,78
RC205
4,00
1297,19
4,00
1314,84
RC206
3,00
1146,32
3,00
1160,29
RC207
3,00
1061,14
3,00
1117,74
RC208
3,00
828,14
3,00
866,77
Média
3,25
1119,17
3,38
1119,93
55
5.2
R1
D
1214,8
1212,95
1213,35
1211,64
1210,83
1208,43
1202
1197,42
1198,37
1201,47
1201,79
1200,33
1241,89
1233,88
1230,48
1220,35
1251,40
1242,40
1227,92
1221,98
1222,31
1199,97
T
100
300
600
1200
1800
1200
3600
7200
V
3,38
3,33
3,33
3,33
3,33
3,62
3,62
3,62
RC2
D
1191,87
1168,34
1163,08
1153,63
1149,28
1207,37
1155,47
1139,79
T
100
300
600
1200
1800
1300
3900
7800
2900
292
3275
8187
16375
1800
103
602
1203
1804
3608
3,38
3,38
3,38
3,38
3,38
3,25
3,38
3,38
3,38
3,38
3,38
1133,42
1139,7
1248,34
1220,28
1198,63
1258,15
1252,71
1184,78
1156,60
1140,64
1128,25
2900
946
1933
5798
11596
1800
108
611
1249
1815
3611
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
V
12,55
MACS 12,45
12,38
12,38
12,38
12,83
RT
12,58
12,58
12,45
SW
12,35
12,33
KPS 12,67
CW
12,5
12,64
TB
12,39
12,33
BBB 12,17
12,58
Ant- 12,42
TPR 12,33
12,25
12,42
Tabela 5.9: Comparação da eficiência da metodologia Ant-TPR com outras
C1
RC1
R2
C2
T
V D
T
V
D
T
V
D
T
V
D
100 10 828,4 100 12,46 1395,47 100 3,05 971,97 100
3 593,19
300 10 828,38 300 12,13 1389,15 300
3 969,09 300
3 592,97
600 10 828,38 600 12,08 1380,38 600
3 965,37 600
3 592,89
1200 10 828,38 1200 11,96 1385,65 1200
3 962,07 1200
3 592,04
1800 10 828,38 1800 11,92 1388,13 1800
3 960,31 1800
3 591,85
450 10 832,59 540 12,75 1381,33 430 3,18 999,63 1600
3 595,38
1300 10 829,01 1600 12,5 1368,03 1300 3,09 969,29 4900
3 590,32
2700 10 828,45 3200 12,33 1269,48 2600 3,09 954,36 9800
3 590,32
900
12,05 1363,67 900
1800
12 1363,68 1800
3600
11,95 1364,17 3600
2900 10 830,75 2900 12,12 1388,15 2900
3 966,56 2900
3 592,29
1382 10 834,05 649 12,38 1408,87 723 2,91 995,39 1332
3 591,78
2296 10 830,41 2926 12,08 1404,59 1877
3 1046,56 3372
3 592,75
6887 10 828,59 7315
12 1387,01 5632
3 1029,65 10116
3 591,14
13774 10 828,45 14630 11,9 1381,31 11264 3 1013,35 20232
3 590,91
1800 10 828,50 1800 11,88 1414,86 1800 2,73 1056,59 1800
3 590,06
108 10 858,22 108 12,38 1423,78 108 3,09 1003,16 111 3,00 594,43
610 10 838,12 612 12,13 1396,26 622 3,09 972,41 623 3,00 591,05
1256 10 835,35 1211 12,13 1373,23 1257 3,00 966,96 1252 3,00 590,35
1883 10 831,90 1821 12,13 1377,08 1832 3,00 956,13 1823 3,00 590,28
3637 10 830,51 3614 12,13 1362,78 3626 3,00 947,80 3629 3,00 589,86
56
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
57
Tabela 5.10: Comparação entre Ant-TPR e MACS
Ant-TPR
Ant
Ant
Ant
Ant
Ant
Ant
x
TPR
TPR
TPR
TPR TPR TPR
MACS
Final
100s
600s
1200s 1800s 3600s
Número de veículos 2,21% 4,42% 3,44% 2,95% 2,70% 3,19%
Distância percorrida -0,56% 4,02% 1,44% 0,44% 0,02% -1,00%
Tempo (s)
20,81% -94,01% -65,92% -31,13% 1,82% 101,23%
Tabela 5.11: Comparação entre Ant-TPR e BBB
Ant-TPR
Ant
Ant Ant Ant Ant
x
TPR TPR TPR TPR TPR
BBB
Final 100s 600s 1200s 1800s
Número de veículos 2,72% 4,94% 3,95% 3,46% 3,21%
Distância percorrida -0,56% 4,02% 1,44% 0,45% 0,02%
Tempo (s)
-
Ant
TPR
3600s
3,70%
-1,00%
-
O tempo computacional não pode ser comparado diretamente por vários motivos. Primeiro, os autores usaram diferentes tipos de computador. Segundo, alguns
métodos não foram especificamente implementados para o PRVJT. A metodologia MACS foi executada em uma estação Sun UltraSparc 1, de 167MHz, tendo 70
Mflop/s (Dongarra, 1997); RT usou um computador de 15 Mflop/s Silicon Graphics; SW usou uma estação Sun UltraSparc de 63 Mflop/s; KPS usou uma estação
DEC Alpha de 25Mflops/s; CW utilizou um Pentium de 18 Mflop/s; TB usou uma
estação Sun Sparc 10 de 10 Mflop/s; BBB utilizou uma computador Pentium 400
MHz, equivalente a 54 Mflops/s. Cada autor testou sua metodologia em um determinado intervalo de tempo, de forma a avaliar o desempenho do algoritmo proposto.
Na tabela 5.12 (retirada de Chen e Ting (2005)) são mostrados os melhores
resultados obtidos por diversos métodos heurísticos nas instâncias Solomon de 100
consumidores para o PRVJT.
5.2
Comparação entre o Algoritmo Ant-TPR e Algoritmos da Literatura
Tabela 5.12: Ant-TPR vs. outras metodologias
Metod. / Grupo
R1
R2
C1
C2
RC1
a
12, 6
3,1
10
3
12,6
TS − P
1294, 70b 1185,90 861,00 602,50 1465,00
Potvin et al. (1996)
639c
722
435
431
586
12,17
2,82
10
3
11,5
TS − T
1209,35 980,27 828,38 589,86 1389,22
Taillard et al. (1997)
13774
20232 14630 16375 11264
12
2,73
10
3
11,63
M ACS
1217,73 967,75 828,38 589,86 1382,42
Gambardella et al. (1999a) 1800
1800
1800
1800
1800
11,92
2,73
10
3
11,5
BBB
1221,10 975,43 828,48 589,93 1389,89
Berger et al. (2001)
13,20
5,00
10,10
3,25
13,50
HGA
1227,00 980,00 861,00 619,00 1427,00
Chen et al. (2001)
13,10
4,60
10,00
3,30
12,70
SAT S
1213,16 952,30 841,92 612,75 1415,62
Tan et al. (2001a)
12,08
2,91
10,00
3,00
11,75
T ESA
1215,14 953,43 828,38 589,86 1385,47
Li e Lim (2003)
1474
3882
201
1220
916
12,83
3,09
10
3
12,5
IACS
1203,56 932,23 828,76 589,86 1363,84
Chen e Ting (2005)
425
437
239
363
403
12,25
2,82
10,00
3,00
12,13
Ant-TPR
1211,61 968,77 828,46 589,86 1358,84
(Geral)
2857,21 3142,06 847,80 606,76 2420,04
12,58
3,09
10,00
3,00
12,38
Ant-TPR
1242,40 1003,16 858,22 594,43 1423,78
(100s)
108,03 110,95 107,51 102,83 107,91
12,42
3,09
10,00
3,00
12,13
Ant-TPR
1227,92 972,41 838,12 591,05 1396,26
(600s)
609,72 623,17 611,56 602,05 621,61
12,33
3,00
10,00
3,00
12,13
Ant-TPR
1221,98 966,96 835,35 590,35 1373,23
(1200s)
1255,73 1252,17 1211,19 1203,17 1257,27
12,25
3,00
10,00
3,00
12,13
Ant-TPR
1222,31 956,13 831,90 590,28 1377,08
(1800s)
1882,91 1822,70 1820,62 1803,61 1832,30
12,42
3,00
10,00
3,00
12,13
Ant-TPR
1199,97 947,80 830,51 589,86 1362,78
(3600s)
3636,62 3629,09 3613,97 3607,92 3625,89
58
RC2
3,4
1476,10
662
3,38
1117,44
11596
3,25
1129,19
1800
3,25
1159,37
5,00
1223,00
5,60
1120,37
3,25
1142,48
2669
3,75
1079,81
370
3,38
1119,93
2635,30
3,38
1252,71
108,27
3,38
1184,78
611,14
3,38
1156,60
1249,10
3,38
1140,64
1814,67
3,38
1128,25
3610,68
Total
427
64679
32957
410
57953
833390
407
57525
100800
405
57523
478
59405
84000
470
57799
15400
411
57467
100639
432
56429
21146
416
57201
121776
425,00
59834,87
6036,50
421,00
58351,36
34353,94
419,00
57779,87
69419,72
418,00
57536,32
102634,69
420,00
56947,18
202841,18
Capítulo 6
Conclusões Gerais e Trabalhos
Futuros
6.1
Conclusões Gerais
Neste trabalho, foi apresentado um algoritmo híbrido denominado Ant-TPR,
baseado nas metaheurísticas Ant Colony Optimization e Busca Tabu, além da técnica
de Reconexão por Caminhos, desenvolvido para solucionar o Problema de Roteamento de Veículos com Janela de Tempo (PRVJT).
Na metodologia desenvolvida, as soluções para o PRVJT são geradas pela metaheurística ACO, refinadas com busca local e Busca Tabu. Periodicamente, a técnica
de Reconexão por Caminhos é acionada, para intensificar a busca sobre regiões
promissoras e tentar agrupar, em uma única solução, bons atributos pertencentes às
soluções já encontradas.
O método foi avaliado em 56 problemas-teste, propostos por Solomon (1987),
produzindo, de forma isolada, alguns resultados melhores que os relatados na literatura e permanecendo, de forma global, a menos de 3% das melhores metodologias
existentes. Apesar dos bons resultados, a metodologia ainda pode ser melhor explorada, com o uso de uma função de avaliação lexicográfica mais elaborada e com
maior quantidade de objetivos secundários, que atuem de forma a guiar a busca
por soluções de melhor qualidade. O uso de uma função simples, com um único
objetivo secundário além dos esperados para medida de desempenho, limitou muito
a busca, pois foi incapaz de diferenciar adequadamente as vizinhanças das soluções
encontradas.
A associação entre as metaheurísticas Colônia de Formigas e Busca Tabu foi
capaz de proporcionar resultados interessantes e que devem ser melhor estudados,
através de novas implementações e testes.
Dentre as propostas da metodologia, foi visto que o uso de uma função de avaliação do tipo lexicográfica é capaz de proporcionar melhores soluções do que funções
baseadas em penalidades.
A forma proposta para a movimentação e geração de rotas pelas formigas, através
do uso de uma memória comum, além da memória da formiga, também produziu
bons resultados e deve ser melhor estudada e comparada com a forma utilizada pelos
demais autores que se detém no tema.
Apesar da técnica de Reconexão por Caminhos ter sido capaz de melhorar os
59
6.2
Trabalhos Futuros
60
resultados, da forma como foi implementada gera um custo computacional alto.
Logo, algumas modificações devem ser feitas em sua implementação, de modo que
continue a influenciar de forma benéfica as soluções, mas não exija tanto tempo de
processamento.
Por fim, a metodologia Ant-TPR, aplicada ao Problema de Roteamento de Veículos com Janelas de Tempo, foi capaz de produzir resultados com diferença inferior
a 3% dos melhores resultados existentes e ainda produziu algumas soluções isoladas
melhores que as relatadas na literatura.
6.2
Trabalhos Futuros
Os trabalhos futuros serão feitos de forma a dar continuidade ao estudo aqui
apresentado. Inicialmente, a criação de novos objetivos secundários que ajudem a
guiar a busca é a prioridade, na tentativa de levar a metodologia Ant-TPR a alcançar
os melhores resultados da literatura, tanto em desempenho quanto em eficiência.
Em seguida, deverá ser feita uma nova sintonia, mais completa, dos diversos
parâmetros envolvidos na metodologia. Para isso, deve-se realizar maior número de
testes para calibragem final dos mesmos, na busca do resultado desejado.
Por fim, a reestruturação e implementação do algoritmo desenvolvido, de forma a
implementá-lo em paralelismo computacional, visando ganho de eficiência e melhor
atuação em problemas de maior porte.
Bibliografia
Backer, B. De; Furnon, V.; Kilby, P.; Prosser, P. e Shaw, P. (2000). Solving Vehicle
Routing Problems Using Constraint Programming and Metaheuristics. Journal
of Heuristics, v. 6, p. 501–523.
Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J.Y. e Taillard, É. D. (1997).
A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time
Windows. Transportation Research Part C: Emerging Technologies, v. 5, p. 109–
122.
Balinski, M. e Quandt, R. (1964). On a integer program for a delivery problem.
Operations Research, v. 12, p. 300–304.
Bauer, A.; Bullnheimer, B.; Hartl, R. F. e Strauss, C. (1999). An ant colony optimization approach for the single machine total tardiness problem. In Proceedings
of the 1999 Congress on Evolutionary Computation (CEC’99), pág. 1445–1450,
Piscataway, NJ. IEEE Press.
Bean, Nigel e Costa, Andre. (2005). An analytic modelling approach for network
routing algorithms that use “ant-like” mobile agents. Comput. Networks, v. 49,
n. 2, p. 243–268.
Beckers, R.; Deneubourg, J.L. e Goss, S. (1992). Trails and U-turns in the selection
of the shortest path by the ant Lasius niger. Journal of Theoretical Biology, v.
159, p. 397–415.
Beni, Gerardo. (1988). The concept of cellular robotic systems. In Proceedings 1988
IEEE Int. Symp. On Intelligent Control, pág. 57–62, (1988).
Berger, J.; Barkaoui, M. e Bräysy, O. (2001). A parallel hybrid genetic algorithm for
the vehicle routing problem with time windows. Working paper, Defense Research
Establishment Valcartier, Canada.
Blum, C. e Roli, A. (2003). Metaheuristics in Combinatorial Optimization: Overview
and Conceptual Comparison. ACM Computing Surveys, v. 35, n. 3, p. 268–308.
Bonabeau, E.; Dorigo, M. e Théraulaz, G. (1999). From Natural to Artificial Swarm
Inteligence. Oxford University Press.
Bonabeau, E.; Henaux, F.; Guérin, S.; Snyers, D.; Kuntz, P. e Theraulaz, G. (1998).
Routing in telecommunication networks with “Smart” ant-like agents. In Proceedings of IATA’98, Second International Workshop on Intelligent Agents for
61
Referências Bibliográficas
62
Telecommunication Applications, volume Lectures Notes in AI vol. 1437, Berlin,
Germany. Springer Verlag.
Brandão, J. (1999). Metaheuristic for the Vehicle Routing Problem with Time
Windows. Voss, S.; Martello, S.; Osman, I.H. e Roucairol, C., editors, Metaheuristics - Advances and Trends in Local Search Paradigms for Optimization,
pág. 19–36, Boston, EUA. Kluwer Academic Publishers.
Bräysy, O. e Gendreau, M. (2001). Metaheuristics for the Vehicle Routing Problem
with Time Windows. Technical Report SINTEF STF42 A01025.
Bui, N. Thang e Nguyen, ThanhVu H. (2006). An agent-based algorithm for generalized graph colorings. GECCO’06: Proceedings of the 8th Annual Conference on
Genetic and Evolutionary Computation, pág. 19–26, New York, NY, USA. ACM
Press.
Bullnheimer, B.; Hartl, R. F.; , e Strauss, C. (1999)a. An improved ant system
algorithm for the vehicle routing problem. Annals of Operations Research, v. 89,
p. 319–328.
Bullnheimer, B.; Hartl, R. F. e Strauss, C. (1999)b. Applying the Ant System to
the vehicle routing problem. Voss, S.; Martello, S.; Osman, I.H. e C.Roucairol„
editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for
Optimization, pág. 285–296, Boston, EUA. Kluwer Academic Publishers.
Bullnheimer, B.; Hartl, R. F. e Strauss, C. (1999)c. A new rank-based version of the
Ant System: a computational study. Central European Journal for Operations
Research and Economics, v. 7(1), p. 25–38.
C. E. Miller, A.W. Tucker e Zemlin, R.A. (1960). Integer programming formulation
of travelling salesman problems. Journal of the ACM, v. 7, p. 326–329.
Carlton, W.B. A Tabu Search Approach to the General Vehicle Routing Problem.
PhD Thesis, University of Texas, Austin, EUA, (1995).
Caro, G. Di e Dorigo, M. (1997). AntNet: A mobile agents approach to adaptive
routing. Technical Report IRIDIA/97-12, IRIDIA.
Caro, G. Di e Dorigo, M. (1998)a. Extending AntNet for best-effort Quality-ofService routing. Unpublished presentation at ANTS’98 - From Ant Colonies
to Artificial Ants: First International Workshop on Ant Colony Optimization
http://iridia.ulb.ac.be/ants98/ants98.html, October 15-16.
Caro, G. Di e Dorigo, M. (1998)b. Two ant colony algorithms for best-effort routing
in datagram networks. Pan, Y.; Akl, S. G. e Li, K., editors, Proceedings of the
Tenth IASTED International Conference on Parallel and Distributed Computing
and Systems (PDCS’98), pág. 541–546, Anheim. IASTED/ACTA Press.
Chen, Chia-Ho e Ting, Ching-Jung. (2005). Algorithms for vehicle routing and
scheduling problems with time windows constraints. Journal of the Eastern Asia
Society for Transportation Studies, v. 6, p. 2822–2836.
Referências Bibliográficas
63
Chen, T.K.; Lee, L.H. e Ke, O. (2001). Hybrid genetic algorithm in solving vehicle
routing problem with window constraints. Asia-Pacific Journal of Operational
Research, v. 18, p. 121–130.
Chiang, W.C. e Russell, R.A. (1997). A Reactive Tabu Search Metaheuristic for the
Vehicle Routing Problem with Time Windows. INFORMS Journal on Computing,
v. 9, p. 417–430.
Colorni, A.; Dorigo, M. e Maniezzo, V. (1992). Distributed Optimization by Ant
Colonies. In Proceedings of the First European Conference on Artificial Life
(ECAL 91), pág. 134–142, (1992).
Colorni, A.; Dorigo, M. e Maniezzo, V. (1996). The ant system: Optimization
by a colony of cooperating agents. IEEE Transactions on Systems, Man, and
Cybernetics-Part B, v. 26(1), p. 29–41.
Colorni, A.; Dorigo, M.; Maniezzo, V. e Trubian, M. (1994). Ant System for jobshop
scheduling. JORBEL - Belgian Journal of Operations Research, Statistics and
Computer Science, v. 34(1), p. 39–53.
Cordeau, J.F.; Laporte, G. e Mercier, A. (2001). A Unified Tabu Search Heuristic
for Vehicle Routing Problems with Time Windows. Journal of the Operational
Research Society, v. 52, p. 928–936.
Cordone, R. e Wolfler-Calvo, R. (2001). A Heuristic for the Vehicle Routing Problem
with Time Windows. Journal of Heuristics, v. 7(2), p. 107–129.
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L e Stein, C. (2002). Algoritmos: Teoria
e Prática. Tradução da Segunda Edição Americana por Vandenberd D. de Souza.
Campus, Rio de Janeiro.
Costa, D. e Hertz, A. (1997). Ants can colour graphs. Journal of the Operational
Research Society, v. 48, p. 295–305.
Costa, T. A. Metaheurísticas Híbridas GRASP-Busca Tabu Aplicadas ao Problema
de Roteamento de Veículos com Janelas de Tempo. Dissertação de Mestrado,
Centro Federal de Educação Tecnológica de Minas Gerais, Belo Horizonte, (2005).
Dammeyer, F. e Voß, S. (1993). Dynamic tabu list management using the reverse
elimination method. Hammer, P.L., editor, Tabu Search, volume 41, pág. 31–46.
Baltzer Science Publishers, Amsterdan.
Dantzig, G. B. e Ramser, J. H. (1959). The truck dispatching problem. Management
Science, v. 6, p. 80–91.
denBesten, M.; Stutzle, T. e Dorigo, M. (2000). Ant colony optimization for the
total weighted tardiness problem. Schoenauer, M.; Deb, K.; Rudolph, G.; Yao, X.;
Lutton, E.; Merelo, J. J. e Schwefel, H.S., editors, Proceedings of PPSN-VI, Sixth
International Conference on Parallel Problem Solving from Nature, volume 1917
of Lecture Notes in Computer Science, pág. 611–620, Berlin, Germany. Springer
Verlag.
Referências Bibliográficas
64
Desrochers, M. e Laporte, G. (1991). Improvements and extensions to the MillerTucker-Zemlin subtour elimination constraints. Operations Research Letters, v.
10, p. 27–36.
Dorigo, M. Optimization, Learning and Natural Algorithms (in Italian). PhD Thesis,
Dipartimento di Elettronica, Politecnico di Milano, Milão, Itália, (1992).
Dorigo, M. e Blum, C. (2005). Ant colony optimization theory: a survey. Theoretical
Computer Science, v. 344, p. 243–278.
Dorigo, M.; Caro, G. Di e Gambardella, L. M. (1999). Ant Algorithms for Discrete
Optimization. Artificial Life, v. 5, n. 2, p. 137–172.
Dorigo, M. e Gambardella, L. M. (1997)a. Ant colonies for the traveling salesman
problem. BioSystems, v. 43, p. 73–81.
Dorigo, M. e Gambardella, L. M. (1997)b. Ant colony system: A cooperative learning
approach to the traveling salesman problem. IEEE Transactions on Evolutionary
Computation, v. 1, p. 53–66.
Dorigo, M.; Maniezzo, V. e Colorni, A. (1991)a. The Ant System: an autocatalytic optimization process. Technical Report 91-016 Revised. Dipartimento di
Elettronica, Politecnico di Milano, Itália.
Dorigo, M.; Maniezzo, V. e Colorni, A. (1991)b. Positive feedback as a search
strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di
Milano, Italy.
Ellabib, I.; Basir, O. A. e Calamai, P. (2003). A new Ant Colony System updating
strategy for Vehicle Routing Problem with Time windows. MIC2003: The Fifth
Metaheuristics International Conference, pág. 18–1 – 18–6, (2003).
Flood, M. M. (1956). The Traveling Salesman Problem. Operations Research, v. 4,
p. 61–75.
Fraga, M. C. P.; Souza, S. R. e Costa, T. A. setembro(2006)a. Um algoritmo
híbrido baseado em Colônia de Formigas e Reconexão por Caminhos para resolução do PRVJT. Anais do XXXVIII Simpósio Brasileiro de Pesquisa Operacional,
Goiânia, GO. SOBRAPO, CD-ROM.
Fraga, M. C. P.; Souza, S. R.; Costa, T. A. e Souza, M. J. F. (2005). Algoritmos
baseados em GRASP e Busca Tabu para resolução do Problema de Roteamento
de Veículos com Janela de Tempo. VIII Encontro de Modelagem Computacional.
ISBN 85-904971-2-7.
Fraga, M. C. P.; Souza, S. R.; Costa, T. A. e Souza, M. J. F. agosto(2006)b. Um
algoritmo baseado em Colônia de Formigas para resolução do PRVJT. Anais do
SPOLM 2006: IX Simpósio de Pesquisa Operacional e Logística da Marinha, Rio
de Janeiro, RJ. Marinha do Brasil, CD-ROM.
Franks, N.R. (1989). Army Ants: A Collective Intelligence, volume 7. Scientific
American.
Referências Bibliográficas
65
Gaertner, Dorian. (2004). Natural Algorithms for Optimization Problems. Final
Year Project Report.
Gambardella, L.; Montemanni, R.; Rizzoli, A. e Donati, A. (2005). Ant Colony
System for a Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, v. 10(4), p. 327–343(17).
Gambardella, L. M. e Dorigo, M. (1995). Ant-Q: A reinforcement learning approach
to the traveling salesman problem. Prieditis, A. e Russell, S., editors, Proceedings
of the Twelfth International Conference on Machine Learning (ML-95), pág. 252–
260, Palo Alto, CA. Morgan Kaufmann Publishers.
Gambardella, L. M. e Dorigo, M. (1996). Solving symmetric and asymmetric TSPs
by ant colonies. ICEC96 Proceedings of the IEEE Conference on Evolutionary
Computation, pág. 622–627. IEEE Press, (1996).
Gambardella, L. M.; Taillard, É. D. e Agazzi, G. (1999)a. MACS-VRPTW: A
Multiple Ant Colony System for Vehicle Routing Problems with Time Windows.
D. Corne, M. Dorigo e Glover, F., editors, New Ideas in Optimization, pág. 63–76.
McGraw-Hill.
Gambardella, L. M.; Taillard, É. D. e Dorigo, M. (1999)b. Ant colonies for the
quadratic assignment problem. Journal of the Operational Research Society, v.
50(2), p. 167–176.
Gambardella, L. M.; Taillard, É. D. e Dorigo, M. (1999)c. Ant Colonies for the
Quadratic Assignment Problems. Journal of Operational Research Society, v. 50,
p. 167–176.
Garcia, B.L.; Potvin, J.Y. e Rousseau, J.M. (1994). A Parallel Implementation
of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window
Constraints. Computers & Operations Research, v. 21, p. 1025–1033.
Garvin, W. M.; Cranball, H. W.; John, J. B. e Spellman, R. A. (1957). Applications
of linear programming in the oil industry. Management Science, v. 3, p. 407–430.
Gavish, B. e Graves, S. (1979). The travelling salesman problem and related
problems. Working Paper 7905, Graduate School of Management, University
of Rochester, Rochester, NY.
Gavish, B. e Graves, S. (1982). Scheduling and routing in transportation and distributions systems: Formulations and new relaxations. Working paper, Graduate
School of Management, University of Rochester, Rochester, NY.
Glover, F. (1986). Future paths for Integer Programming and Links to Artificial
Intelligence. v. 5, p. 553–549.
Glover, F. (1989). Tabu Search: Part I. ORSA Journal of Computing, v. 1, p.
190–206.
Glover, F. (1990). Tabu Search: Part II. ORSA Journal of Computing, v. 2, p.
4–32.
Referências Bibliográficas
66
Glover, F. (1996). Tabu search and adaptative memory programming - advances,
applications and challenges. Barr, R.; Helgason, R. e Kennington, J., editors, Interfaces in Computer Sciences and Operations Research, pág. 1–75. Kluwer Academic Publishers.
Glover, F. e Laguna, M. (1993). Tabu Search. Reeves, In C.R., editor, Modern
Heuristic Techniques for Combinatorial Problems, Advanced Topics in Computer
Science Series, Capítulo 3, pág. 70–150. Blackwell Scientific Publications.
Glover, F. e Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Boston.
Goss, S.; Aron, S.; Deneubourg, J. L. e Pasteels, J. M. (1989). Self-organized
shortcuts in the Argentine ant. Naturwissenschaften, v. 76, p. 579–581.
Hansen, P. (1986). The steepest ascent mildest descent heuristic for combinatorial
programming. Proceedings of Congress on Numerical Methods in Combinatorial
Optimization, Capri, Itália.
Hendtlass, Tim. (2004). TSP optimisation using multi tour ants. IEA/AIE’2004:
Proceedings of the 17th International Conference on Innovations in Applied Artificial Intelligence, pág. 523–532. Springer Springer Verlag Inc, (2004).
Hertz, A. e deWerra, D. (1990). The tabu search metaheuristic: how we used it.
Annals of Mathematics and Artificial Intelligence, v. 1, p. 111–121.
Hölldobler, B. e Wilson, E.O. (1994). Journey to the Ants. Bellknap Press/Harvard
University Press.
Ho, Sin C. e Gendreau, Michel. (2006). Path relinking for the vehicle routing
problem. Journal of Heuristics, v. 12, p. 55–72.
IBGE,.
(2001).
Contas
Nacionais
Trimestrais.
http://www.ibge.gov.br/home/presidencia/noticias/28032002pib.shtm,
acessado em 7 de agosto de 2006 às 15:00.
Kilby, P.; Prosser, P. e Shaw, P. (1999). Guided Local Search for the Vehicle Routing
Problems With Time Windows. S.Voss,; Martello, S.; Osman, I.H. e C.Roucairol„
editors, Meta-heuristics: Advances and Trends in Local Search for Optimization,
pág. 473–486. Kluwer Academic Publishers, Boston, EUA.
Lau, H.C.; Lim, Y. F. e Liu, Q. (2000). Diversification of Neighborhood via
Constraint-based Local Search and Its Application to VRPTW. Working paper,
School of Computing, National University of Singapore.
Lau, H.C.; Sim, M. e Teo, K.M. (2003). Vehicle Routing Problem with Time
Windows and a Limited Number of Vehicles. European Journal of Operational
Research, v. 148, p. 559–569.
Li, H. e Lim, A. (2003). Local search with annealing-like restarts to solve the
VRPTW. European Journal of Operational research, v. 150, p. 115–127.
Referências Bibliográficas
67
Maniezzo, V. (1999). Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal on Computing,
v. 11(4), p. 358–369.
Maniezzo, V. e Colorni, A. (1999). The Ant System applied to the quadratic
assignment problem. IEEE Transactions on Data and Knowledge Engineering, v.
11(5), p. 769–778.
Maniezzo, V.; Colorni, A. e Dorigo, M. (1994). The Ant System applied to the
quadratic assignment problem. Technical Report IRIDIA/94-28, IRIDIA.
Merkle, D.; Middendorf, M. e Schmeck, H. (2000). Ant colony optimization for
resource-constrained project scheduling. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pág. 893–900, San Francisco,
CA. Morgan Kaufmann Publishers.
Potvin, J.Y.; Kervahut, T.; Garcia, B.L. e Rousseau, J.M. (1996). The Vehicle
Routing Problem with Time Windows Part I: Tabu Search. INFORMS Journal
on Computing, v. 8, p. 157–164.
Ribeiro, C.C. (2002). Metaheuristics and Applications. In Advanced School on
Artificial Intelligence, Portugal.
Rochat, Y. e Taillard, É. D. (1995). Probabilistic Diversification and Intensification
in Local Search for Vehicle Routing. Journal of Heuristics, v. 1, p. 147–167.
Russell, R.A. (1995). Hybrid heuristics for the vehicle routing problem with time
windows. Transportation Science, v. 29, p. 156–166.
Schaefer, A. (1996). Tabu search techniques for large high-school timetabling problems. Proceedings of the 30th National Conference on Artificial Intelligence, pág.
363–368, (1996).
Schoonderwoerd, R.; Holland, O. e Bruten, J. (1997). Ant-like agents for load balancing in telecommunications networks. In Proceedings of the First International
Conference on Autonomous Agents, pág. 209–216. ACM Press, (1997).
Schoonderwoerd, R.; Holland, O.; Bruten, J. e Rothkrantz, L. (1996). Antbased
load balancing in telecommunications networks. Adaptive Behavior, v. 5(2), p.
169–207.
Schulze, J. e Fahle, T. (1999). A Parallel Algorithm for the Vehicle Routing Problem
with Time Window Constraints. Annals of Operations Research, v. 86, p. 585–607.
Shaw, P. (1998). Using Constraint Programming and Local Search Methods to
Solve Vehicle Routing Problems. Maher, M. e Puget, J.-F., editors, Proceedings
of of the Fourth International Conference on Principles and Practice of Constraint
Programming (CP’98), pág. 417–431. Springer-Verlag, (1998).
Referências Bibliográficas
68
Sintef,.
(2005).
Best
Known
Solutions
Identified
by
Heuristics
for
Solomon’s
(1987)
Benchmark
Problems.
http://www.sintef.no/static/am/opti/projects/top/vrp/bknown.html,
acessado em 31 de julho de 2006 às 13:00.
Solomon, M. M. (1987). Algorithms for vehicle routing and scheduling problems
with time windows constraints. European Journal of Operational Research, v. 35,
p. 254–266.
Stutzle, T. (1998). An ant approach to the flow shop problem. In Proceedings of the
6th European Congress on Intelligent Techniques & Soft Computing (EUFIT’98),
volume 3, pág. 1560–1564. Verlag Mainz, Aachen.
Stutzle, T. (1999). Local Search Algorithms for Combinatorial Problems: Analysis,
Improvements, and New Applications. Infix, Sankt Augustin, Germany.
Stutzle, T. e Dorigo, M. (1999). ACO algorithms for the traveling salesman problem.
Miettinen, K.; Makela, M. M.; Neittaanmaki, P. e Periaux, J., editors, Recent
advances in genetic algorithms, evolution strategies, evolutionary programming,
genetic programming and industrial applications. John Wiley and Sons.
Stutzle, T. e Dorigo, M. (2000). The Ant Colony Optimization Metaheuristic:
Algorithms, Applications, and Advances. Technical Report IRIDIA-2000-32.
Stutzle, T. e Hoos, H. H. (1997). The MAX-MIN Ant System and local search for
the traveling salesman problem. Bäck, T.; Michalewicz, Z. e Yao, X., editors, Proceedings of the 1997 IEEE International Conference on Evolutionary Computation
(ICEC’97), pág. 309–314, Piscataway, NJ. IEEE Press.
Subramanian, D.; Druschel, P. e Chen, J. (1997). Ants and reinforcement learning: A case study in routing in dynamic networks. In Proceedings of IJCAI-97,
International Joint Conference on Artificial Intelligence, pág. 832–838. Morgan
Kaufmann, (1997).
Taillard, É. D. (1998). FANT: Fast Ant System. Technical Report IDSIA-46-98,
IDSIA, Lugano, Switzerland.
Taillard, É. D.; Badeau, P.; Gendreau, M.; Guertin, F. e Potvin, J.Y. (1997). A
Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows.
Transportation Science, v. 31, p. 170–186.
Tan, K. C.; Lee, L. H. e Ou, K. (2001)a. Artificial intelligence heuristics in solving
vehicle routing problems with time window constraints. Engineering Applications
of Artificial Intelligence, v. 14, p. 825–837.
Tan, K. C.; Lee, L. H.; Zhu, Q. L. e Ou, K. (2001)b. Heuristic methods for vehicle
routing problem with time Windows. Artificial Intelligence in Engineering, v. 15,
p. 281–295.
Referências Bibliográficas
69
T’kindt, Vincent; Monmarché, Nicolas; Tercinet, Fabrice e Laügt, Daniel. (2002).
An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop
scheduling problem. European Journal of Operational Research, v. 142, p. 250–
257(2).
Toth, P. e Vigo, D. (2002). The Vehicle Routing Problem. SIAM - Society for
Industrial and Applied Mathematics, Philadelphia, 1a edição.
White, T.; Pagurek, B.; , e Oppacher, F. (1998). Connection management using
adaptive mobile agents. Arabnia, H.R., editor, Proceedings of the International
Conference on Parallel and Distributed Processing Techniques and Applications
(PDPTA’98), pág. 802–809, Berlin, Germany. CSREA Press.
Wilson, E.O. e Hölldobler, B. (1990). The ants. Springer-Verlag, Berlin.
Xu, Yi-Liang; Lim, Meng-Hiot; Ong, Yew-Soon e Tang, Jing. (2006). A GAACO-local search hybrid algorithm for solving quadratic assignment problem.
GECCO’06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pág. 599–606, New York, NY, USA. ACM Press.