Embed Size (px)
Citation preview
Pontifícia Universidade Católica de São Paulo
PUC-SP
Rafael Emidio Murata Rodrigues
Planejamento de rotas dirigidas com base no Problema de Roteamento Humano.
Mestrado em Tecnologias da Inteligência e Design Digital
São Paulo
2018
Pontifícia Universidade Católica de São Paulo PUC-SP
Rafael Emídio Murata Rodrigues
Mestrado em Tecnologias da Inteligência e Design Digital
Dissertação apresentada à Banca Examinadora
da Pontifícia Universidade Católica de São
Paulo, como exigência parcial para a obtenção
do titulo de MESTRE em Tecnologias da
Inteligência e Design Digital, na área de
concentração de Processos Cognitivos e
Ambientes Digitais, na linha de pesquisa de
Design Digital e Inteligência Coletiva, sob a
orientação do Prof. Dr. Ítalo Santiago Vega.
São Paulo
2018
Banca Examinadora:
___________________________
___________________________
___________________________
___________________________
___________________________
Para minha família, e a doce Denise...
Esta dissertação teve o suporte da CAPES - Coordenação de Aperfeiçoamento de Pessoal de
Nível Superior / Programa de Suporte à Pós-Graduação de Instituições Comunitárias de Ensino Superior – mediante concessão de bolsa de Mestrado, objeto do processo nº (88887.149916-2017-00), o que permitiu a realização do curso de Mestrado e a conclusão da Dissertação, que consolida a pesquisa realizada durante o curso.
Agradecimentos
Aos meus pais pelas valiosas lições.
A minha esposa Denise, por seu companheirismo.
Ao meu orientador, Professor Ítalo Santiago Vega, pelos valiosos ensinamentos acadêmicos e
amizade.
Ao professor Hermes, por sempre se fazer disposto a ajudar.
Ao professor Helder, pelos importantes insights.
Ao professor Joao Mattar, aulas e sua ajuda.
Ao meu primo Marcio, pela ajuda.
A Edna Conti pela dedicação incansável.
RESUMO
Na nossa vida, nos locomovemos constantemente em ruas e bairros. Em geral,
consideramos o tempo e (ou a distância), ao planejar a rota. Contudo, suas soluções
podem enfrentar problemas complexos, decorrentes das diversas possibilidades de
soluções. Semelhante a planejamento de rotas, o Problema de Roteamento de
Veículos foi introduzido por George B. Dantzig, e John H. Ramser em 1959 e consiste
em entregar gasolina diversos postos de combustível; a princípio uma proposta
matemática, mais tarde tornou-se uma abordagem algorítmica, para planejamento de
rotas de entrega de produtos de forma otimizada (buscando o “menor caminho”).
Embora, durante a busca de menor caminho, limitam-se ao uso de ruas. Neste
contexto emerge o Problema de Roteamento Humano, tal abordagem não se limita a
ruas, mas faz uso de todos os caminhos possíveis, por veículos e humanos. Tal
problemática, pode ser observada nos planejamentos de rotas em aeroportos,
museus e em uma empresa de supply chain que deseja otimizar a rota de entrega dos
seus produtos, e aumentar a satisfação dos seus clientes. Tomando como base
central, o Problema de Roteamento de Veículos será proposto o Problema de
Roteamento Humano. Sua problemática, será demonstrado em um protótipo, capaz
de auxiliar no planejamento de rotas humanas e três casos de uso. As ideias do
Problema de Roteamento Humano tiveram inspiração no forrageamento dos insetos
coletivos.
Palavras-chave: Otimização combinatória. PRV (Problema de Roteamento de
Veículos). PRH (Problema de Roteamento Humano). Insetos coletivos. Computação
Ubíqua.
ABSTRACT
In our lives, we constantly move in streets and neighborhoods. In general, we consider
time and (or distance) when planning the route. However, their solutions may face
complex problems arising from the different possibilities of solutions. Similar to route
planning, the Vehicle Routing Problem was introduced by George B. Dantzig and John
H. Ramser in 1959 and consists of delivering gasoline to several fuel stations; at first
a mathematical proposal, later became an algorithmic approach, for planning of routes
of delivery of products in an optimized way (searching the "shortest path"). Although,
during the search of shortest path, they are limited to the use of the streets. In this
context emerges the Human Routing Problem, such an approach is not limited to
streets, but makes use of all possible paths, by vehicles and humans. Such a problem
can be observed in route planning at airports, museums and a supply chain company
that wants to optimize the route of delivery of its products and increase customer
satisfaction. Based on the Vehicle Routing Problem, the Human Routing Problem will
be proposed. Its problematic will be demonstrated in a prototype, capable of assisting
in the planning of human routes and three use cases. Ideas of Human Routing Problem
had inspiration in the collective foraging insects.
Keywords: Combinatorial optimization. VRP (Vehicle Routing Problem). HRP (Human
Routing Problem). Collective insects. Ubiquitous computing.
LISTA DE FIGURAS
Figura 1: Macro visão da dissertação ....................................................................................................... 19
Figura 2: Experimento chamado double-bridge; ........................................................................................ 29
Figura 3: Problema das Pontes de Königsberg ......................................................................................... 38
Figura 4: Possível solução para o PRV ..................................................................................................... 40
Figura 5: Percurso de um chimpanzé ....................................................................................................... 46
Figura 6: Possíveis estratégias de forrageamento das formigas ................................................................ 48
Figura 7: Otimizador de rotas e o componente responsável por “Otimizar rotas” ........................................ 60
Figura 8: Problema do aeroporto .............................................................................................................. 62
Figura 9: Possível solução para o problema do aeroporto ......................................................................... 63
Figura 10: Problema do museu................................................................................................................. 64
Figura 11: Possível solução para o problema no museu ............................................................................ 65
Figura 12: Problema no entregas.............................................................................................................. 66
Figura 13: Possível solução para o problema de entregas ......................................................................... 67
LISTA DE EQUAÇÕES
Equação 1: Maximizar e minimizar ........................................................................................................ 35
LISTA DE SIMBOLOS
PRV Problema de Roteamento de Veículos
PRH Problema de Roteamento Humano
PCV Problema do Caixeiro Viajante
PCVG Problema do Caixeiro Viajante Genérico
NP Tempo polinomial não-deterministas
N Tempo polinomial
POI Ponto de interesse
TFO Teoria do Forrageamento Ótimo
SSP Shortest path problems
AS Ant System
ACS Ant Colony System
ACO Ant Colony Optimization
CE Computação Evolucionária
AEs Algoritmos Evolutivos
AG Algoritmos Genéticos
BD Banco de Dados
Sumário
1 Introdução .................................................................................................................................................................... 14
1.1 Contexto da pesquisa .................................................................................................................................. 14
1.2 Caracterização do problema: Questão e hipótese ........................................................................................ 20
1.3 Objetivos ..................................................................................................................................................... 21
1.3.1 Objetivo geral ......................................................................................................................................... 21
1.3.2 Objetivo específico .................................................................................................................................. 21
1.4 Metodologia ................................................................................................................................................ 22
1.5 Estrutura da dissertação .............................................................................................................................. 23
2 Fundamentação .................................................................................................................................................... 24
2.1 Comportamento de forrageio ...................................................................................................................... 24
2.2 Abelhas e formigas como superorganismos ................................................................................................. 25
2.2.1 Forrageamento nas abelhas .................................................................................................................... 27
2.2.2 Forrageamento nas formigas ................................................................................................................... 28
2.3 Otimização geral de algoritmos ................................................................................................................... 30
2.3.1 Computação evolucionária ...................................................................................................................... 32
2.3.2 Programação Linear para otimização ....................................................................................................... 35
2.4 Teoria dos Grafos ........................................................................................................................................ 37
2.5 Problema do Caixeiro Viajante .................................................................................................................... 38
2.5.1 Definição formal do problema ................................................................................................................. 39
2.5.2 Pseudocódigo ......................................................................................................................................... 39
2.6 Problema de Roteamento de Veículos ......................................................................................................... 40
2.6.1 Definição do Problema de Roteamento de Veículos ................................................................................. 42
2.6.2 Pseudocódigo ......................................................................................................................................... 42
2.7 Computação ubíqua .................................................................................................................................... 43
3 Otimização combinatória no movimento espacial animal ...................................................................................... 45
3.1 O Problema do Caixeiro Viajante aplicado no movimento espacial animal .................................................. 45
3.2 O Problema do Caixeiro Viajante no forrageamento das abelhas e formigas ............................................... 47
3.3 Algoritmos bioinspirados ............................................................................................................................. 49
3.3.1 Otimização da Colônia de Formigas ......................................................................................................... 50
3.3.2 Algoritmo de Colônia de Abelhas Artificiais .............................................................................................. 53
4 O Problema de Roteamento Humano .................................................................................................................... 56
4.1 Rotas estáticas e rotas dinâmicas ................................................................................................................ 57
4.2 Definição formal do problema ..................................................................................................................... 58
4.3 Variantes do Problema de Roteamento Humano ......................................................................................... 59
4.3.1 Problema de Roteamento Humano com Múltiplas Viagens ...................................................................... 59
4.3.2 Problema de Roteamento Humano Aberto .............................................................................................. 59
4.4 Protótipo otimizador de rotas humanas ...................................................................................................... 60
5 Casos de uso .......................................................................................................................................................... 62
5.1 Aeroporto – Estudo de caso 1 ...................................................................................................................... 62
5.2 Museu – Estudo de caso 2 ........................................................................................................................... 64
5.3 Shopping Center – Estudo de caso 3 ............................................................................................................ 66
6 Conclusões............................................................................................................................................................. 68
6.1 Discussões ................................................................................................................................................... 69
6.2 Contribuições .............................................................................................................................................. 69
6.3 Trabalhos futuros ........................................................................................................................................ 69
Referências ...................................................................................................................................................................... 70
14
1 Introdução
1.1 Contexto da pesquisa
Durante os últimos 30 anos estudamos diversos problemas complexos
comumente encontrados em sistemas industriais. Tentamos elaborar e resolver
matematicamente os problemas de otimização, dos quais podem nos auxiliar a tomar
decisões e compreender melhor o funcionamento destes sistemas.
Os problemas de otimização nos campos da matemática e da computação,
buscam encontrar a melhor solução de para o problema dentre diversas as soluções
viáveis. Segundo Mandal e Kumar (2016, p.165) “problemas de otimização são
divididos em duas categorias. A primeira consiste em problemas com variáveis
continuas (otimização continua). A segunda categoria de problemas consiste em
problemas de variáveis discretas (otimização discreta)”.
O campo de otimização discreta, agrega diversas áreas de pesquisa como
afirma Lee (2004, p.1) além das aplicações, otimização discreta muitos aspectos o
conectam com outras áreas da matemática (e.g., álgebra, otimização e análise
continua, geometria, logica, análise numeral, topologia, e claro outras subdisciplinas
das matemáticas discretas como a teoria de grafos, teoria matroide, e combinação
enumerativa) bem como a ciência da computação. Ou seja, quando um problema é
de otimização com variáveis discretas é conhecido como um problema de otimização
combinatória.
Vangelis e Paschos (2014, p.5) afirmam que os problemas de otimização
combinatórias podem ser encontrados em; agendamento de tripulação de companhia
aérea; transporte de mercadorias e planejamento; agendamento de tarefas em
programação paralela; aplicações de combinatória poliédrica; planejamento de
produção; modelagem e otimização problemas de síntese e design de rede;
otimização paralela; atribuição de tarefas de múltiplos critérios a processadores
heterogêneos e sua robustez. Mas em particular, um dos problemas de otimização
15
combinatória, que demonstra mais interesse entre os pesquisadores é o Problema de
Roteamento de Veículos (PRV).
Segundo Vigo (2015, p.7) o PRV exige a determinação do conjunto ótimo de
rotas a serem realizadas por uma frota de veículos, para servir a um determinado
conjunto de clientes; sendo considerado um dos problemas de otimização
combinatória, mais importante e estudado. O PRV consiste em minimizar o custo total
de conjunto de rotas para os veículos, onde inicia-se e finaliza-se o roteiro no depósito,
e cada cliente é visitado apenas uma vez, e cada veículo utiliza sua capacidade total
de carga. Embora algumas variações, foram desenvolvidas ao longo dos anos, como
restrições de capacidade, com multiplos depósitos, com janela de tempo, precedência
de relacionamento com o cliente entre outros.
Inicialmente o PRV foi introduzido por G. B. Dantzig e J. H. Ramser (1959) e
seu objetivo era entregar petróleo a um conjunto de postos de gasolina. Este problema
é encontrado em situações diárias devido a sua importância econômica mundial.
Exemplos comuns são a entrega de jornais a varejistas, de alimentos e bebidas a
mercearias e a coleta de produtos lácteos de produtores de leite (GENDREAU, et al.,
2007).
Alguns algoritmos de roteamento fazem uso das técnicas utilizadas para o PRV
em cenários do mundo real, como por exemplo: Gambardella (2003) duas aplicações
chamadas DyvOil e AntRoute para problemas PRV; Fei (2012) apresenta uma
pesquisa sobre otimização de um sistema de emergência; Rizzoli (2007) propõe
utilizar-se do algoritmo ‘Otimização da colônia de formigas’ para solucionar problemas
do PRV.
A PRV constitui uma generalização do Problema do Caixeiro Viajante (PCV),
que consiste em determinar o circuito ou ciclo mais curto que passa por cada um dos
𝑛 pontos apenas uma vez (LAPORTE; NOBERT, 1987). O Problema do Caixeiro
Viajante (PCV) é um problema definido por um conjunto de cidades e as distâncias
entre cada par de cidades. Assim sendo o problema é procurar um caminho que passe
por todas as cidades e termine onde começa.
O PVC destaca-se por encontrar um caminho mais curto passando por todas
as cidades. Mas sua dificuldade é vislumbrada ao observar um problema exponencial,
16
para a visita de diversas cidades ou em um país. PCV é NP-difícil, o que significa que
qualquer solução de algoritmos que calcule uma solução exata de PCV é necessária
uma quantidade de tempo de computação que é exponencial em (𝑁), o tamanho do
problema (GREFENSTETTE, 1985).
Portanto o PCV pertence a classe dos problemas polinomiais não-
deterministas1 (NP). Miller (2001, p.166) descreve “lembre-se que NP-completo
significa que o problema pode somente ser solucionado em tempo NP e todos os
outros problemas NP pode ser eficientemente convertido [...] em contraste, o
problema NP-difícil se não for NP, mas todo problema NP pode ser convertido para
ele”. Ou seja, a classe de problemas em P (polinomial) são os que podem ser
resolvidos de modo determinístico, em tempo polinomial. Logo todo o problema que
esta em P também esta em NP, fazendo-se possível uma solução em tempo
polinomial.
Ao aplicar permutações nos vértices do PVC, em busca de um tour otimizado,
nem sempre pode se obter uma solução ótima, fazendo-se necessário utilizar técnicas
metaheurísticas. Segundo Labadie (2016, p.6) “de fato, em muitos casos, problemas
de otimização combinatória são NP-difícil. Consequentemente, metaheurísticas são
desenvolvidas para os problemas derivados do mundo real, muitas vezes atingem
níveis notavelmente altos de complexidade, embora não sejam capazes de certificar-
se de encontrar soluções otimizadas”.
Ao lidar com cenários difíceis e de grande complexidade computacional2,
pesquisadores aplicaram estratégias heurísticas3 e metaheurísticas, com o objetivo
de torna fácil e rápida sua solução. Caso contrario o tempo de resposta, para um
problema de otimização combinatória, excederia o limite esperado por lidar com
problema reais. Como afirmam Kokubugata, et al. (2007, p.1) mesmo com relação ao
PRV simples, os métodos exatos não são adequados para grandes problemas.
Portanto, as heurísticas têm sido importantes na aplicação do PRV. Na última década,
muitas soluções usando metaheurísticas foram propostas para o PRV. Uma
metaheurística é um algoritmo projetado para resolver uma ampla gama de problemas
1 Do inglês nondeterministic polynomial. 2 Em tempo e espaço. 3 Método de investigação baseado na aproximação progressiva, de um problema.
17
difíceis de otimização sem ter que se adaptar profundamente a cada problema
(BOUSSAÏD, et al., 2013).
“O PRV é NP-difícil porque inclui o PCV [...] em pratica, o PRV é considerado mais
difícil de se resolver que o PCV de mesmo tamanho” (LAPORTE, 2007, p.1). Embora
as soluções para o PRV geralmente complexas devido a vasta gama de soluções
possíveis (como as restrições de agendamento, peso de carga etc.) pesquisadores
encontraram nas técnicas metaheurísticas soluções como: Golden (1998) que estuda
o impacto das metaheurísticas nas soluções para o PRV; Cordeau (2002) os
pesquisadores fazem um estudo sobre os algoritmos que utilizam heurísticas e
metaheurísticas para soluções do PRV; Prins (2004) é proposto um algoritmo genético
para problemas do PRV utilizando metaheurísticas; Bullnheimer, et al. (1999) onde
os pesquisadores buscam inspiração nas formigas, no processo de busca por
alimento, para solucionar problemas do PRV; Yu (2009) os pesquisadores procuraram
aprimorar a utilização formigas artificiais4 em uma nova técnica, para problemas do
PRV; Baker (2003) os pesquisadores fizeram uso de algoritmos genéticos para
solucionar os problemas do PRV; pesquisas do âmbito do PRV e suas variações
continuam sendo amplamente discutidos na literatura.
Da convergência entre as pesquisas em otimização combinatória e o PRV,
emerge a ideia inicial desta pesquisa: o campo de pesquisa de otimização
combinatória, tem-se comprovado obter bons resultados quando aplicados aos
problemas do PRV, que demonstram uma notável5 capacidade obter soluções
otimizadas. Esta dissertação limita-se aos problemas de roteamento humano e busca
inspiração na natureza, observando o forrageamento dos insetos coletivos
especialmente nas abelhas e formigas.
A natureza sempre serviu de modelo para imitar e inspirar os seres humanos
em seu desejo de melhorar sua vida (BAR-COHEN, 2005). A bioinformática e a
biomimética auxiliam, a compreender os fenómenos naturais, e propor modelos ou
sistemas. Como parte do campo da biomimética, os cientistas estão buscando regras,
conceitos, mecanismos e princípios da biologia para inspirar novas possibilidades de
engenharia, incluindo manufatura, mecanismo, materiais, processos e algoritmos.
4 Do inglês artificial ant. 5 Sobre complexidade, medida em tempo e espaço.
18
Tais como roteamento de protocolos, e suas pesquisas levaram a algoritmos como
AntNet de Di Caro e Dorigo (1998) e BeeHive de Wedde, et al. (2004).
Como a bioinformática é uma ciência computacional, um curso de
bioinformática deve se esforçar para apresentar os princípios e as ideias que orientam
um projeto de algoritmos ou explicar o ponto crucial de uma abordagem estatística,
em vez de ser uma coleção de selos de algoritmos e técnicas estatísticas (SINGH,
2015). Portanto, o uso dos campos como biologia, matemática e a computação,
ajudam a avançar o entendimento dos princípios teóricos e práticos, utilizando-se de
ideias e princípios oriundos da natureza.
Os sistemas otimizadores que imitam a natureza fornecem algoritmos de
otimização particularmente eficientes e promissores para a classe de problemas
(SMUTNICKI, 2011). Portanto na literatura é demonstrado que ao utilizar-se da
otimização combinatória, muitas metodologias puderam ser aplicadas ao problemas
humanos como: Yan (2016) que propõe uma cooperação humano-computador para
problemas de otimização combinatória; Kim (1997) que faz uso da otimização
combinatória para a compreensão do aprendizado dos processos do cérebro humano;
Hynes e Czarnuch (2016) onde os pesquisadores propõe um método para melhorar a
precisão de um rastreador humano, utilizando a otimização combinatória (menor
caminho) para redução de ruídos e predição de melhoria, para rastreamento humano;
Hernandez Vela, et al.( 2012) utilizam um framework que faz uso do algoritmo Random
Forest e teoria de corta de grafos6 para reconhecimento de gestos.
Esta dissertação propõe o estudo exploratório dos problemas de roteamento
humano com base no PRV. Os problemas de roteamento humano, têm como objetivo
melhorar a mobilidade urbana. Compreende-se os problemas de roteamento humano
como a busca para melhorar o tempo e (ou distância) entre o inicio da caminhada e o
fim. Embora a distância entre o inicio/fim (caminhada ou tour) possam ser repletos de
“ponto de interesse” (POI) (são pontos de parada, como por exemplo: um guichê,
banca de jornal etc.) representados por diferentes localizações.
Também buscamos incluir as restrições do PRV (como peso, horário etc.) para
o PRH. No PRV suas técnicas de metaheurísticas, facilitam o processo de busca por
6 Do inglês Graph-cuts theory.
19
“menor caminho7” (em tempo ou distância), em cenários do cotidiano em que podem
se aplicar restrições.
Durante a pesquisa sobre o PRV foi observado a limitação de ruas ao “sugerir”
rotas otimizadas para veículos. Embora durante o cotidiano possam haver caminhos
limitados a pedestres como museus, praças, aeroportos e rotas de evacuação. Neste
contexto emergem os Problemas de Roteamento Humano (PRH). O PRH tem como
objetivo uma nova abordagem, sobre as limitações de rotas de veículos e avançar o
conhecimento sobre o PRV.
Tal abordagem inspira-se nos insetos coletivos como as abelhas e as formigas,
durante o forrageamento8. Observações no comportamento destes insetos,
demonstram que não utilizam-se de ruas durante o forrageamento, embora consigam
otimizar seu forrageamento.
Figura 1: Macro visão da dissertação
A figura 1, demonstra como o PCV é a área central de conhecimento,
englobando os diferentes campos. Os problemas do PCV fazem parte do PRH e do
PRV. O PRH inspira-se na natureza para suas ideias.
7 Do inglês shortest path. 8 Forrageamento é a busca e exploração por alimento.
20
1.2 Caracterização do problema: Questão e hipótese
Em resumo, o contexto apresentado acima diz respeito a possibilidade de
utilizar como fundamento base o PRV, para solucionar os problemas de roteamento
humanos, buscando inspiração na natureza.
Durante o cotidiano nos locomovemos constantemente, por ruas e bairros.
Entretanto sempre levamos em consideração tempo e distância na escolha do trajeto.
Esta dissertação tem como pergunta fundamental, como sugerir potenciais trajetos humanos em situações a rota é conhecida ou não e permite otimizar o tempo (ou distância)?
Utilizaremos uma hipótese, lastreada em um estudo exploratório sobre os
problemas de roteamento humano, propondo uma nova abordagem sobre a pergunta.
A otimização discreta, em especial o campo da otimização combinatória pode auxiliar
num melhor proveito das ideias. Contudo, compreende-se outras técnicas
matemáticas existentes, para as possíveis soluções.
As técnicas matemáticas tradicionais, tais como a programação linear (LP), a programação não linear (NLP) e a programação dinâmica (DP), foram frequentemente usadas para resolver problemas de otimização. Tais técnicas geralmente empregas no processo de otimização. No entanto, em problemas do mundo real, existem algumas desvantagens: em LP, ocorrem dificuldades consideráveis quando um modelo ideal linear de um problema do mundo real não-linear é desenvolvido; Na DP, um aumento no número de variáveis aumentaria exponencialmente o número de avaliações do recursivo funcional e imporia à memória do núcleo (a ‘maldição da dimensionalidade9’); na PNL, se as funções usadas na computação não forem diferenciáveis, o algoritmo de resolução pode não encontrar o melhor (GEEM, et al., 2001, p.1).
Considerando as diversas técnicas matemáticas, para uma possível solução
de tempo e (ou distância) nos problemas de rotas humanas, destaca-se o PRV. O
PRV faz uso da otimização combinatória e metaheurísticas para propor rotas
otimizadas, demonstrado sua eficiência no mundo real.
9 A "maldição da dimensionalidade" especifico da programação dinâmica, implica que a sua utilização só seja possível para problemas de dimensão reduzida.
21
Esta dissertação procura responder a tal questão proposta, desenvolvendo
uma nova abordagem chamada Problema de Roteamento Humano (PRH), inspirada
na busca por alimento, das abelhas e formigas. Para uma melhor compreensão serão
demonstradas as ideias oriundas do PRH e um protótipo, seguido de casos de usos.
Compreende-se que o PRH é uma generalização do PRV. Portanto procuramos
avançar os conhecimentos gerados no PRV, para uma união com o PRH.
Durante o desenvolvimento da abordagem PRH, será demonstrado como
alterar rotas estáticas (exemplo rota de trem, os quais improvavelmente admitem
alterações) para rotas dinâmicas (os quais admitem alteração). A alteração de uma
rota dinâmica pode fornecer uma redução de tempo e (ou distância), mas também
evitar o excesso de pedestres numa mesma rota.
1.3 Objetivos
1.3.1 Objetivo geral
Propor o ‘Problemas de Roteamento Humano’, com base no ‘Problema de
Roteamento de Veículos’, inspirando-se no forrageamento dos animais coletivos
como as abelhas e formigas.
1.3.2 Objetivo específico
Investigar o PRV.
Investigar como os insetos coletivos como as abelhas e as formigas, descobrem rotas,
e as utilizam de forma otimizada.
Investigar modelos que utilizam PCV e o PRV no forrageamento nos animais.
Propor o Problema de Roteamento Humano, demostrando suas semelhanças e
diferenças.
Desenvolvimento de três caso de uso, para problemas PRH.
22
1.4 Metodologia
Investigar como os insetos coletivos, solucionam e otimizam seus problemas
de roteamento.
Estudo detalhado do Problema de Roteamento de Veículo, compreendendo
suas eficiências e limitações.
Delimitar o Problema de Roteamento Humano, especificando suas eficiências
e limitações.
Desenvolver um protótipo de uma ferramenta otimizadora para o Problema de
Roteamento Humano, que faz uso da computação ubíqua.
Estudo de casos do Problema de Roteamento Humano.
Discussões pertinentes ao Problema de Roteamento Humano, e suas
subhipóteses.
23
1.5 Estrutura da dissertação
Esta dissertação esta estruturada em seis capítulos.
Capítulo 1 – Introdução. Este capítulo apresentou o panorama da pesquisa.
Primeiramente, foi delineado o contexto no qual ela se insere. Seguindo a definição
da questão fundamental da pesquisa e a declaração da hipótese do trabalho.
Concluindo o capítulo com a especificação dos objetivos, a apresentação da
metodologia e a descrição da estrutura dos capítulos.
Capítulo 2 – Fundamentação, este capítulo será apresentado os conceitos: O
forrageamento nas formigas e abelhas, otimização geral de algoritmos, teoria de
grafos, Problema do Caixeiro Viajante, o Problema de Roteamento de Veículos e
Computação ubíqua.
Capítulo 3 – Otimização combinatória no movimento espacial animal, este
capítulo estuda como o forrageamento nos animais podem inspirar modelos
computacionais. Suas ideias servirão de inspiração para o Problema de Roteamento
Humano.
Capítulo 4 – O Problema de Roteamento Humano, serão demonstradas as
ideias centrais do Problemas de Roteamento Humano, bem como um protótipo de
otimizador de rotas humanas.
Capítulo 5 – Casos de uso, serão apresentados os diferentes cenários em
que são observados os Problemas de Roteamento Humano.
Capítulo 6 – Conclusão, O capítulo apresenta uma conclusão que busca
sintetizar algumas reflexões da pesquisa e sua contribuição.
24
2 Fundamentação
Ao lidar problemas de otimização computacional, em geral a única abordagem
é calcular toda e qualquer possibilidade, para a solução e escolher a melhor. Contudo,
alguns problemas tem uma vasta gama de soluções espaciais, fazendo-se inviável tal
processo. Tais problemas quando não encontrado uma solução em um tempo
razoável, referem-se a gama de problemas chamados NP-difícil ou NP-completo. Um
destes problemas é o PRV. Este capítulo tem como objetivo elucidar os conceitos
necessários para se compreender os insetos coletivos como as abelhas e formigas e
o PRV.
2.1 Comportamento de forrageio
Muitos dos animais exploram os recursos distribuídos no seu ambiente, e a
seleção natural ou evolução genética favorece indivíduos que conseguem melhor
explorar. Se adotarmos a hipótese da seleção natural nos leva (e seus limites) para a
‘sobrevivência do mais forte’ então esperamos entender e observar a morfologia,
fisiologia e o comportamento dos organismos vivos com base nos princípios de
otimização (MANGEL; CLARK, 1988).
Em 1966 Robert MacArthur e Eric Pianka desenvolveram um modelo teórico
para o forrageamento, chamado Teoria do Forrageamento Ótimo (TFO). Modelos de
otimização são amplamente discutidos e utilizados nos campos de ecologia
comportamental, especialmente no campo de teoria do forrageamento ótimo
(CÉZILLY, 2010). Portanto a ideia de utilizar um “modelo”, é uma simples descrição
da natureza.
O TFO é baseado na existência de um balanço entre os custos e benefícios
dessas decisões comportamentais (CARNEIRO, et al., 2013). A teoria do
forrageamento ótimo é o campo em que os biologistas utilizam de teorias de
otimização para predições qualitativas, sobre o comportamento animal durante a
alimentação, e testada por experimentos de observadores.
25
A hipótese do TFO é que os indivíduos serão maximizadores de energia ou
minimizadores de tempo. Contudo, em circunstâncias em que cabe esperar a
aplicação da premissa da maximização energética, a teoria do forrageio ótimo permite
compreender o significado das “decisões” do forrageio tomada pelos predadores
(BEGON, et al., 2009).
O modelo de maximização da taxa mais importante que prevê o tempo ideal
que um animal de forrageamento deve manter em um conjunto de recursos é o
Teorema do Valor Marginal (TVM) (WAJNBERG, 2006). Outro aspecto do forrageio
ótimo considera que o habitat no qual o animal forrageia é heterogêneo, portanto
considera diferentes quantidades de alimentos. Para otimizar seu ganho de energia,
o animal deve caçar nos locais mais rentáveis, medidos por “quantidade de tempo”.
Ou seja, quando um animal forrageia deve permanecer no local ate a “taxa de ganho
energético” tenha se tornado escasso para taxa média do habitat (chamada tempo de
desistência) e por isso o animal deve mover-se para um novo habitat.
A ideia de um modelo de “escolha” de comportamento, determina o melhor
momento em que um animal deve mover-se de uma mancha de alimento para outra.
Assim se um forrageador ficar constantemente em uma determinada mancha, irá
obter informações a respeito de sua qualidade (como disponibilidade de alimento) e
quando estiver em declínio diminuem as vantagens, e o forrageador normalmente
opta por deixar a mancha. A teoria do forrageio ótimo não especifica precisamente
como o forrageador deve tomar as decisões corretas e não exige que ele realize os
mesmos cálculos que o especialista construtor do modelo (BEGON, et al., 2009).
Embora a teoria do forrageio ótimo apresente ótimos modelos na literatura,
nesta dissertação seguiremos com a linha de pesquisa ecologia comportamental.
2.2 Abelhas e formigas como superorganismos
O comportamento coletivo apresentado nos Insetos sociais, demonstram
algumas particularidades sobre os insetos solitários; como a quantidade de indivíduos
que possibilita uma maior organização, dividindo as responsabilidades dos trabalhos;
e a habilidade de compartilhar informações, especialmente a localização do alimento.
26
A palavra “superorganismo” na biologia e na ecologia, designa-se para uma
forma com a qual a natureza explora a cooperação de seus indivíduos. A metáfora e
as teorias do “superorganismo” tomam o organismo individual como um modelo de
integração funcional ou cooperação de partes e ampliam esse modelo para descrever
e explorar grupos sociais de indivíduos (MITCHELL, 2003). Assim indivíduos ou
células, cooperam para o desenvolvimento, manutenção e reprodução de um grupo,
colônia ou sociedade. O estudo de colônias de insetos sociais (formigas, cupins,
vespas e abelhas) durante o século revelou notáveis homeostases social na regulação
de um ambiente de ninho, números e formas individuais de comportamentos
(MORITZ; SOUTHWICK, 2012). Os diversos indivíduos que compõem um
“superorganismo” produzem um comportamento singular e complexo.
O comportamento complexo de cupins, vespas, formigas e abelhas utilizam a
divisão do trabalho e a atividade coordenada e produzem os comportamentos
coletivos. Uma variedade de comportamento coletivo é o resultado espontâneo de
múltiplas interações entre companheiros de ninho, mesmo quando não há influência
de direcionamento imposta por um modelo externo, um marca-passo ou um líder
(DETRAIN; DENEUBOURG, 2006). Portanto o trabalho coletivo organizado, substitui
uma liderança; ou seja, todo o trabalho dos indivíduos do grupo auxilia no
funcionamento da colônia. Estes insetos sociais utilizam-se de suas habilidades
singulares, para lidar com as adversidades cotidianas.
Uma das características mais importantes dos insetos sociais é que eles
podem resolver esses problemas de uma maneira muito flexível e robusta: a
flexibilidade permite a adaptação à mudanças, enquanto a robustez confere à colônia
a capacidade de funcionar, mesmo que algum indivíduo não consiga realizar sua
tarefa (BONABEAU; DORIGO; THERAULAZ, 1999). Algumas conjecturas acerca dos
problemas enfrentados no cotidiano definem as possíveis soluções. Então, a melhor
hipótese para a solução do problema é uma “nova tentativa” em busca da possível
solução, na esperança de que esta seja uma excelente decisão. Cada indivíduo deve
buscar explorar o campo de soluções do problema e superar eventuais adversidades.
Portanto, cada individuo, ao se utilizar da flexibilidade e da robustez, fornece um
campo amplo de possíveis soluções e margem para erros.
27
Destacam-se também os movimentos individuais, de defesa contra
predadores, busca de alimento, construção, manutenção dos ninhos, e em atividades
complexas, das quais requerem algum tipo de engenharia.
A busca por alimento, aparenta ser um padrão comum [...] usualmente o padrão de um individuo ao encontrar alimento é o acidente, tropeçando nisso, por assim dizer. Então, o “truque” é transmitir a localização e o tipo de alimento para o outro indivíduo da comunidade, ou, como é melhor dizer as informações para o “superorganismo” como um todo [...] mas antes disso, o localizador de caminho deve ser capaz de estabelecer a rota ideal. Alguns localizadores de caminhos parecem usar uma espécie de mapa mental da área onde a fonte de alimento e o ninho estão localizados [...] uma maneira mais simples de navegar é encontrar o caminho de volta ao longo de uma leitura fixa, lembrando a distância e a direção da viagem (GRAHAM, 1965, p.412, grifo nosso).
Portanto, o forrageamento envolve dois fatores: a navegação, um exemplo de
comportamento animal que envolve integração sensorial, controle motor, aprendizado
e memória; a capacidade de memória, que permite à colônia regular as atividades de
forrageamento, para recuperar locais gratificantes e buscar locais promissores.
2.2.1 Forrageamento nas abelhas
“Uma abelha que detecte a presença de uma nova e rica fonte de alimento
perto da colméia transmitirá essa informação a outras abelhas da colméia, realizando
uma dança circular [...] a dança circular não indica a direção ou a distância da fonte
de alimento em relação à colméia [...] quando a fonte de alimento esta a mais de 50
ou 100 metros de distância da colméia as abelhas fazem a waggle-dance ao invés da
dança circular” (GILLETT; MCMILLAN, 2001, p. 198). Von Frisch havia descoberto
que, quando uma abelha forrageadora encontra uma rica fonte de alimento, ela
retorna imediatamente a colméia e faz a waggle-dance ou a “dança de linguagem”,
capaz de gerar uma mensagem informando a direção e a distância entre a colméia e
a nova fonte de alimento (néctar, solução de açúcar, ou pólen).
28
Na Alemanha quase a setenta anos atrás, no verão de 1944, quando um distinto professor de zoologia na Universidade de Munich, Karl von Frisch, fez uma descoberta revolucionária o qual eventualmente lhe rendeu o Prêmio Nobel: um inseto, a abelha trabalhadora, pode informar sua colméia sobre a distância e a direção entre uma rica fonte de alimentos por meios de uma dança comportamental (SEELEY, 2010, p. 152).
Ao medir a duração da porção waggle-run (porção da dança do requebrado em
que a abelha requebra ao caminhar pelo meio do “oito” formado na dança) do circuito,
um observador humano consegue dizer aproximadamente qual a distância da fonte
de alimento (ALCOCK, 2016). Esta misteriosa dança é essencial para a comunicação
da colônia e contém três informações sobre o caminho da florada: a direção em que
será encontrada, sua distância da colméia e sua classificação de qualidade (ou
aptidão física) (VASANT, 2012, p. 455, apud BONABEAU; DORIGO; THERAULAZ,
1999).
O pesquisador T. Seeley (2010, p. 180) afirma que abelhas se comunicam
informando as regiões em potencial utilizando um feedback10 positivo. Este processo
é importante pois informa a qualidade de alimento na região. Por fim, destacam-se a
capacidade das abelhas em distinguir uma boa região, dentre as demais e sua
comunicação ao indicar a direção e qualidade da fonte de alimento.
2.2.2 Forrageamento nas formigas
Na década de 1880, John Lubbock (1834-1913) mostrou que formigas usavam
rastros de odor no forrageamento. Acreditava que as formigas se comunicavam
utilizando uma linguagem sofisticada ao tocar as antenas. Alguns anos depois,
através dos experimentos de Von Frisch sobre a waggle-dance, foram observados
mecanismos mais sofisticados de forrageamento naqueles insetos.
10 Informações sobre reações a algo novo, usado como base para melhoria.
29
A tortuosidade ótima do caminho de busca depende não só da provável distribuição de alimento (LACH, et al., 2010,p.214 apud FOURCASSIÉ e TRANIELLO, 1993), mas também do número de pesquisadores cooperativos; se muitos trabalhadores da mesma colônia estão forrageando na mesma área, os forrageadores devem usar caminhos mais diretos para minimizar a sobreposição. Os forrageiros individuais, por outro lado, buscarão otimizar a maior área coberta em volta do ninho, não movendo-se para longe que aumentaria os custos da jornada de retorno (LACH, et al., 2010, p.214).
A pesquisa publicada por E. O. Wilson (1962), demonstrou que as trilhas de
feromônio das formigas fornecem feedback positivo e negativo para organizar o
forrageamento colônia. Formigas marcadoras de trilhas possuem uma glândula de
cheiro abdominal utilizada para produzir um feromônio de trilha, sinal químico que
demarca o caminho para uma fonte de alimento (HILL, et al., 2016). As formigas
utilizam o feromônio para “comunicação” dos seus indivíduos e seu cheiro abdominal
evapora rapidamente.
Este comportamento das formigas foi observado pelos pesquisadores Goss, et
al. (1989); realizaram experimentos em 1989 buscando entender como as formigas
conseguem encontrar o caminho entre o ninho e a fonte de alimento. Este experimento
foi denominado double-bridge (Figura 2).
Figura 2: Experimento chamado double-bridge;
Fonte: (KATIYAR; IBRAHEEM; ANSARI, 2015)
No experimento, foram utilizadas formigas Linepithema humile. E o caminho
entre o ninho e a fonte de alimento, foi separado por duas pontes de tamanho igual.
Foi observado que, inicialmente, as formigas faziam percursos aleatórios ao escolher
os caminhos entre as pontes. Com o passar do tempo, a trilha de feromônio
evaporava-se, reduzindo o atrativo do caminho, deixando apenas uma das duas
pontes com mais feromônio. Em outras palavras, o feromônio deixado ao longo da
menor trilha era reforçado rapidamente; contudo, continuavam a adicionar mais
30
feromônio. Ao final, o caminho com mais feromônio era escolhido como o mais
atrativo, e sempre convergia para o mesmo resultado.
O surgimento deste comportamento de seleção de caminho mais curto pode
ser explicado em termos de autocatálise (feedback positivo) e comprimento do
caminho diferencial, é possibilitado por uma forma indireta de comunicações
conhecida como estigmergia11 de Grassé (1959).
2.3 Otimização geral de algoritmos
Muitos problemas práticos do mundo real foram formulados e resolvidos
usando técnicas de programação matemática durante as últimas quatro décadas
(LUCIC; TEODOROVIC, 2002). Quando procuramos uma otimização em um
problema formulado, nossa tarefa é encontrar a melhor solução utilizando técnicas
matemáticas apropriadas. Entretanto, buscar todas as soluções aleatoriamente para
um determinado problema, pode ser algo ineficiente, dependendo da natureza do
problema. Embora busca aleatória seja uma característica dos algoritmos modernos.
Segundo Coello, et al. (2007, p.21) afirmam que as técnicas de gerais de busca
e otimização são classificadas em três grupos:
• Enumerativas (determina um espaço finito de possíveis soluções e avalia).
• Deterministas (considerados grafos e árvores de busca algorítmicas)
repetindo e expandindo os nós e examinando todos os sucessores (utilizam
heurísticas) são inefetiva quanto aos problemas de classe NP-completos ou
aos mais altos problemas de dimensionalidade; afirmam que, devido as
aplicações do mundo real, os problemas multi-bjetivos são irregulares;
portanto, técnicas enumerativas e deterministas são impróprias.
• Estocásticas (aleatórias) para solucionar os problemas derivados do mundo
real. Pesquisadores utilizaram abordagens como o algoritmo Simulated
11 Pierre Paul Grassé (1895 - 1985) foi um pesquisador a respeito das formigas e realizou experimentos com os insetos sociais, para explicar como realizavam suas tarefas de forma auto-organizada.
31
Annealing, método Monte Carlo, o método de busca chamada Tabu Search
e Computação Evolucionaria (CE). Métodos estocásticos fazem uso de
funções que selecionam o valor de adequação possível (ou parcial) para
solução e codificando/decodificando mecanismos entre o problema do
algoritmo.
Os algoritmos determinísticos seguem procedimentos rigorosos, e repetem
caminhos e valores. Logo os algoritmos estocásticos utilizam aleatoriedade, para
aumentar a probabilidade de um resultado aproximado. Para algoritmos estocásticos,
em geral, temos dois tipos: heurístico e metaheurístico, embora a diferença seja
pequena (YANG, 2011). As diferenças serão apresentadas a seguir.
A palavra heurística significa: baseado em, ou envolvendo tentativa e erro
(RIBENBOIM, 2004). A heurística deriva do verbo heuriskein, que significa
“encontrar”, enquanto o sufixo meta significa “além”, em um nível superior (KATIYAR,
IBRAHEEM e ANSARI, 2015). Os algoritmos metaheurísticos utilizam de
aleatoriedade e busca local.
Os mecanismos metaheurísticos aleatórios fornecem uma forma de ampliar a
busca local para uma busca global. Um dos problemas globais de a otimização é que,
muitas vezes, não é possível determinar se a melhor solução otimizada conhecida
está situada localmente ou globalmente e, assim, a convergência é aceitável (WEISE,
2009). Em outras palavras, usualmente não é claro se o processo busca global, por
uma solução otimizada pode ser “parado” ao encontra uma solução “aceitável”, nas
diversas partes do espaço de busca.
Nestes casos, técnicas heurísticas ou metaheurísticas são aplicadas, e provém
uma aproximação do resultado ideal devida à vasta gama de possíveis soluções para
o mesmo problema. Algoritmos heurísticos são como algoritmos de aproximação, e
eles não servem para encontrar soluções ótimas, mas somente “próximas-do-ótimo”
ou “pior-que-ótimo” ou soluções “aceitáveis” (PAI, 2017).
Nos algoritmos heurísticos, utilizar o método de tentativa e erro, pode produzir
soluções aceitáveis para os problemas complexos em tempo razoável. A
complexidade do problema pode fazer com que a busca das soluções (ou
combinações) tornem-se impossíveis em uma escala de tempo aceitável. A
32
complexidade de um algoritmo é usualmente medida pelo número de operações
elementares (adições, subtrações, comparações etc.) que o algoritmo requer para
solucionar o problema dentre as piores condições de casos (TAYLOR, 2007).
Na literatura da Teoria da Complexidade Computacional, os pesquisadores
acreditam que utilizar-se de algoritmos estocásticos, podem trazer benefícios de
tempo e espaço12. Quando os problemas são “grandes” e complexos, especialmente
se são NP-completos ou NP-difícil, conhecidos como tempo polinomial, o uso de
algoritmos estocásticos se torna obrigatório (WEISE, 2009). Os problemas NP-difícil
(polinomiais não-determinísticos de otimização de tempo difícil) são os problemas
clássicos considerados computacionalmente intratáveis, pois crescem
exponencialmente em tempo polinomial. A terminologia difícil é estabelecida no
contexto de otimização, e relacionada a complexidade computacional tais como
tempo, memoria etc.
Estes métodos (sejam lineares ou não lineares, determinísticos ou
estocásticos) podem ser agrupados sobre a rubrica da Programação Matemática
(COELLO, et al., 2007).
2.3.1 Computação evolucionária
O campo da Computação Evolucionária13 (CE) é frequentemente considerado
como composto por quatro paradigmas principais: algoritmos genéticos, programação
evolucionária, estratégias de evolução e programação genética (EBERHART, et al.,
1996). O campo da (CE) é ramo de pesquisa, que representa um grande esforço para
pesquisadores de diversos campos.
A CE inspira-se no processo natural de Charles R. Darwin (1809-1882)
chamado de evolução. A evolução pode ser vista como um processo de busca, por
soluções para um problema em particular. Segundo Fogel (2000, p.1) “a evolução
darwiniana é intrinsecamente robusta no mecanismo de busca e otimização. A biota
12 No campo da Complexidade Computacional o tempo e o espaço são medidas para complexidade. 13 Do inglês Evolutionary Computation.
33
desenvolvida demonstra um comportamento complexo otimizado em todos os níveis:
a célula, o órgão, o indivíduo e a população. Os problemas que as espécies biológicas
são tipificadas por chance de caos14, temporalidade e interações não-lineares”.
A metáfora fundamental da computação evolucionária relacionou esse poder
da evolução natural com um estilo particular de resolução de problemas - o método
de tentativa e erro (EIBEN e SMITH, 2015). O método de tentativa ou do Inglês
(backtracking) comumente faz uso de técnicas de recursividade encontrar uma
solução de um problema computacional evolutivo.
A terminologia contemporânea denota todo o campo como computação
evolutiva, os algoritmos envolvidos são denominados algoritmos evolutivos (AEs), e
considera evoluir qualquer programação, estratégias de evolução, algoritmos
genéticos e programação genética como subáreas compatíveis com as variantes de
algoritmos correspondentes (EIBEN; SMITH, 2015). A ideia central dos AEs é
aproveitar o poder da evolução biológica e traduzi-la em um eficiente algoritmo de
otimização baseado em computador (REVAY; CIOFFI-REVILLA, 2018).
O programa evolutivo básico, utilizam os três componentes principais de todos os algoritmos da EC: variação de inicialização, avaliação (pontuação) e seleção. Com base neste processo, bem como em outros algoritmos CE, presume-se que, ao menos em um sentido estático, o aprendizado é codificado filogeneticamente versus ontologicamente em cada membro da população. O “aprendizado” é um subproduto do processo evolutivo, pois indivíduos sucessivos são retidos através de tentativa e erro estocástico. Bäck (2000, p.89, grifo nosso).
Assim seus programas básicos oferecem uma forma de seleção e evolução,
aplicando uma forma de “aprendizado”. Portanto, os algoritmos evolucionários podem
oferecer soluções adaptativas às mudanças globais, devido a suas propriedades
evolucionárias.
Algoritmos Genéticos (AG) providos pela EAs fazem uso de busca estocástica
e de soluções através de simulações, utilizando um alto nível de abstração e evolução
das espécies tal como observada na natureza. Em um AG, uma população de
soluções evolui ao longo de várias gerações através da aplicação de operadores,
14 A Teoria do Caos, trata de sistemas complexos e dinâmicos rigorosamente deterministas.
34
como seleção, cruzamento e mutação, que imitam processos genéticos
correspondentes observados na natureza (TAVARES; BAPTISTA, 2009).
O modo formal da GA segundo (TAVARES; BAPTISTA, 2009) pode ser
descrito em um pseudocódigo:
1. Crie uma população inicial de soluções P.
2. Avalie cada solução.
3. Repita por um número fixo de gerações:
3.1 Repita até que as soluções de descendência P sejam criadas:
3.1.1 Selecione duas soluções pai na população (com substituição) usando um procedimento de seleção
randomizado com base nos valores da solução.
3.1.2 Aplique cruzamento às duas soluções pai para criar dois descendentes soluções.
3.1.3 Aplique mutação (com uma probabilidade pequena) a cada descendente.
3.1.4 Inclua os dois descendentes na nova população.
3.2 Avalie cada filho na nova população.
3.3 Substitua a população antiga pela nova.
4.4 Retorne a melhor solução encontrada.
John Von Neumann (1958, p.1) escreveu: “Eu suspeito que um estudo
matemático mais profundo do sistema nervoso [...] afetará nossa compreensão dos
aspectos da matemática em si que estão envolvidos. De fato, isso pode alterar a
maneira como vemos matemática e propriedades logicas.” Na literatura das ‘Redes
Neurais Artificiais’ seus avanços abriram novas perspectivas para a compreensão de
sistemas complexos oriundos da natureza. Como Mira e Sanchez (1999, 2001) entre
outras conferências e publicações.
A mesma abordagem tem sido usada para projetar redes neurais artificiais que
resolvam problemas, ou no desenvolvimento de algoritmos genéticos para otimização:
se o cérebro e a evolução, respectivamente, serviram como metáforas iniciais, a
maioria dos exemplos de redes neurais e algoritmos genéticos no contexto da
35
engenharia estão fortemente desacoplados de suas metáforas subjacentes
(BONABEAU; DORIGO; THERAULAZ, 1999).
2.3.2 Programação Linear para otimização
A programação linear é uma ferramenta matemática poderosa para
otimizações sob um objetivo com limitações dadas em qualquer situação (TANG,
1999). A programação linear insere-se num cenário de certeza (em cenários de
incerteza são aplicadas outras técnicas), utilizando-se de modelos lineares
determinísticos de otimização aplicados a problemas combinatórios, aplicados a uma
vasta gama de soluções (contudo, a cenários sujeitos a limitações, fazendo-se uso
das técnicas matemáticas e algorítmicas) para solução do problema em foco.
A programação linear pode ser encontrada em diversos cenários onde se
possui restrições e busca-se uma solução ótima. O ‘Teorema Fundamental da
Programação Linear’ diz que, se existe uma solução possível, então existe uma
solução básica possível, e se existe uma solução ótima possível, então existe uma
solução ótima básica possível (CARVALHO, 2014). Assim, a programação linear
envolve o planejamento de atividades para obter um resultado ótimo, ou seja, um
resultado que atinge melhor o objetivo especificado (de acordo com o modelo
matemático) entre todas as alternativas viáveis (HILLIER; LIEBERMAN, 1980).
O problema da programação linear exige um processo de otimização no qual
serão utilizados valores não-negativos. Para um conjunto de variáveis de decisão
%𝑥',𝑥),, … 𝑥+,,são selecionados para maximizar (ou minimizar) uma função objetiva.
Segundo Jacobs e Chase (2009, p.394) o problema de otimização pode ser
formalizado matematicamente da seguinte forma:
Maximizar (minimizar)
Equação 1: Maximizar e minimizar
𝑍 = 𝐶'𝑋' +𝐶)𝑋) + ⋯+𝐶+𝑋+
36
Sujeita a restrições de recursos, na forma:
𝐴''𝑋' + 𝐴')𝑋) +⋯+ 𝐴'+𝑋+ ≤ 𝐵'
𝐴)'𝑋' + 𝐴))𝑋) + ⋯+ 𝐴)+𝑋+ ≤ 𝐵)
.
.
.
𝐴7'𝑋' + 𝐴7)𝑋) +⋯+ 𝐴7+𝑋+ ≤ 𝐵7
● Onde 𝐶+𝐴7+ e 𝐵7são constantes conhecidas. Dependendo do problema, as
restrições também podem ser determinadas com sinais de igualdade (=) ou
sinais de maior-que ou igual a (≥).
Sendo:
• 𝑥', 𝑥), …, 𝑥+ são variáveis;
• 𝑐', 𝑐), …, 𝑐+são custos;
• 𝐴'', 𝐴'+, …, 𝐴7', 𝐴7+são coeficientes;
• 𝐵', 𝐵), …, 𝐵+são termos constantes.
Segundo Jacobs e Chase (2009, p.393) afirma que a programação linear é
comumente utilizada nas seguintes aplicações:
Planejamento agregado de vendas e de produção: encontrar a programação de custo mínimo. Análise da produtividade do serviço/produção: compara a eficiência com diversos postos de serviço e de produção utilizam seus recursos em relação a unidade de mais alto desempenho. Planejamento de produtos: encontrar o mix de produtos ideal, onde os diversos produtos têm custo e necessidade de recursos diferentes. Sequenciamento de produtos: encontrar a maneira fácil de produzir um produto que deve ser processado em sequencia em vários centros de maquinas, mas cada maquina dos centros tem custos e características de produção própria.
37
Programação de veículos / tripulação: encontrar a maneira ideal de usar os recursos, como aeronaves, ônibus ou caminhões e as respectivas tripulações profissionais para oferecer serviços de transporte aos clientes e a matérias a serem descolocados entre os diversos locais. Controle de processo: minimizar o volume de matérias refugados gerados ao cortar aço, couro ou tecido de um rolo ou rola de material de estoque. Controle de estoque: encontrar a combinação ideal para estocar em uma cadeia depósitos ou locais de estocagem. Programação da distribuição: encontrar a programação de expedição ideal para distribuir produtos entre as fabricas e depósitos ou entre depósitos dos varejistas. Estudo de localização das fabricas: encontrar o local ideal de uma nova fábrica, avaliando os custos de transporte entre as localizações alternativas e as fontes de oferta e procura. Manipulação de matérias: encontrar as rotas de custo mínimo dos equipamentos de manuseio de matérias (como empilhadeiras) entre os departamentos em uma fabrica, ou transportar materiais de um pátio de abastecimento ate os locais de trabalho, por caminhões, por exemplo. Cada caminhão deve ter capacidades físicas e de desempenho diferentes.
2.4 Teoria dos Grafos
Quando nos locomovemos entre cidades (ou ruas, bairros, estados etc.)
sempre observamos qual a “melhor” rota para o percurso? Mas para alcançar o
destino da cidade desejada, temos que fazer algumas escolhas acerca do trajeto:
• Tráfico de veículos.
• Tempo.
• Distância.
Por muitos anos as pessoas se preocupavam em otimizar seus trajetos.
Leonard Euler (1707 - 1783) foi o pioneiro ao pensar sobre a Teoria dos Grafos; seu
trabalho pode ser encontrado em Euler (1953). Euler estudou o Problema das Pontes
de Königsberg, trata-se de realizar um passeio pela cidade passando por sete pontes,
apenas uma vez e retornar ao ponto de partida.
Leonard Euler considerou as pontes como arestas e ilhas ou margens como
vértices. No total de sete pontes conectadas a duas ilhas. Então se considerarmos os
pontos 𝑎 e 𝑐 como lados de uma ilha, com os pontos 𝑏 e 𝑑 sendo duas ilhas teríamos:
38
Figura 3: Problema das Pontes de Königsberg
Ao final, Euler observou que eram necessários ocorrer um numero par de
pontes na região para que houvesse uma solução. Segundo Szwarcfiter (2018, p.40)
“Euler mostrou que não existe tal trajeto, ao utilizar o modelo em grafos para uma
generalização do problema [...] a solução deste problema é considerada o primeiro
teorema da teoria de grafos”. A Teoria dos Grafos é um ramo da matemática que
estuda as relações entre os objetos de um determinado conjunto (SANTOS, 2017).
2.5 Problema do Caixeiro Viajante
Os algoritmos de CE tornaram-se ferramentas padrão para resolver algumas classes de problemas, enquanto há domínios em que são praticamente desconhecidos. Por exemplo, o PCV é talvez a primeira aplicação do EC como solucionador de problemas favorito (ou pelo menos entre as melhores escolhas) (BARAGONA; FRANCESCO; POLI, 2011, p. 2).
O Problema do Caixeiro Viajante PCV15 é um conhecido problema de
otimização combinatória NP-difícil16, pois quando aplicado a diversas cidades
aumenta-se o leque de soluções, possíveis elevando a complexidade do problema.
Segundo os pesquisadores Baeck, Fogel e Michalewicz (2000, p.1) afirmam que uma
das aplicações da CE é a de rotas.
“[...] o objetivo do PCV é encontrar um caminho mais curto de um vendedor
ambulante que começa em uma cidade inicial, visita um conjunto prescrito de outras
cidades e retorna à cidade inicial” (GUTIN; PUNNEN, 2006, p.11). Também conhecido
como Problema do Caixeiro Viajante Genérico PCVG. Apesar de o circuito não ser
muito complexo em termos de planejamento de rotas, é geralmente considerado um
15 Do inglês Travelling Salesman Problem (TSP). 16 Do inglês NP- hard utilizado na Teoria da Complexidade Computacional.
39
problema de otimização combinatória difícil. Em geral PCV é um problema retirado do
mundo real análogamente.
Muitos problemas considerados pelos cientistas da computação são
simplificações do PCV chamadas Shortest Path Problems (SSP): qual é a menor rota
que começa no ponto A e termina no ponto B utilizando qualquer combinação
existente (muitas vezes não é linha reta) e os caminhos intermediários entre eles?
(BOINSKI; GARBER, 2000).
2.5.1 Definição formal do problema
Definição formal do PCV: Considere 𝑉 = {𝑎, … , 𝑧} sendo um conjunto de
cidades,𝐴 = {(𝑟, 𝑠): 𝑟, 𝑠 ∈ 𝑉} o conjunto de arestas, e 𝛿(𝑟, 𝑠) = 𝛿(𝑠, 𝑟) ser uma medida
associada à aresta (𝑟, 𝑠) ∈ 𝐴. O PCV consiste em encontrar encontrando um tour
mínimo, visitando cada cidade somente uma vez.
2.5.2 Pseudocódigo
A solução clássica do PCV é descrita por (LEVITIN, 2006):
1. Insira a distância da matriz, onde n é um número de arcos na distância da rede. Importante assumir que a direção da conexão do arco
entre os pares dos vértices na rede.
2. selecione aleatoriamente uma cidade base. seja x e exclua a coluna X da matriz da cidade.
3. inclua X como a primeira cidade da turnê.
4. na linha X, localize a entrada de célula matricial menos recuperada e identifique a coluna correspondente (quebra o laço aleatoriamente).
5. Inclua Y como a próxima cidade a ser visitada no passeio.
6. Delete a coluna Y da matriz de distância.
7. Verifique se todas as colunas da matriz de distância são excluídas.
se sim, vá para o passo 9; senão, vá para o passo 8.
8. defina x = y e vá para o passo 4.
9. inclua a primeira cidade como a última cidade do tour.
40
10. liste as cidades na excursão junto com a distância total correspondente da viagem.
2.6 Problema de Roteamento de Veículos
A PRV constitui uma generalização do Problema do Caixeiro Viajante (PCV),
que consiste em determinar o circuito ou ciclo mais curto que passa por cada um dos
𝑛 pontos apenas uma vez (LAPORTE; NOBERT, 1987). O ‘Problema de Roteamento
de Veículos’ (PRV) foi introduzido por G. B. Dantzig e J. H. Ramser em 1959. A
definição formal do problema é mostrada por Vigo e Toth (2002, p.12):
Dado: um conjunto de requisições de transporte e uma frota de veículos.
Tarefa: determinar um conjunto de rotas de veículos para todas as (ou
algumas) requisições de transporte, dada uma frota de veículos com custo mínimo;
em particular, decidir quais veículos gerenciam quais requisições em qual sequência
para que todas as metas sejam atingidas.
A Figura 4 representa uma possível solução, para o PRV. O PRV requer uma
otimização combinatória para seus problemas, preocupando-se em otimizar as
diversas rotas. Devido a sua importância prática e teórica, diversas variantes do PRV
foram obtidas.
Figura 4: Possível solução para o PRV
Fonte: (LABADIE; PRINS; PRODHON, 2016)
41
Centenas de trabalhos foram dedicados a uma solução exata e aproximada das muitas variantes desse problema, tal como o ‘PRV capacitado17’ (CPRV), no qual a frota homogênea de veículos está disponível e a única restrição é a capacidade do veículo, ou a PRV com o ‘Tempo de Janela18’ (PRVTW), onde os clientes podem ser atendidos dentro de um inversor de tempo específico e o cronograma das viagens do veículo precisa ser determinado (GOLDEN; RAGHAVAN; WASIL, 2008 , p. 4)
O ‘Problema do Roteamento do Veículo com a Janela de Tempo’ (PRVTW)
é uma extensão do ‘Problema de Roteamento do Veículo Capacitado’ (CPRV) em que
o serviço para cada cliente deve começar dentro de um intervalo de tempo associado,
chamado de ‘tempo de janela’. Na literatura existente no PRVTW, o número de
veículos disponíveis para servir os clientes geralmente é considerado ilimitado e a
função objetiva depende da natureza do método de solução escolhido. Para métodos
exatos, o objetivo é minimizar a distância total percorrida. Para a heurística, o principal
objetivo é minimizar o número de veículos utilizados e o secundário para minimizar o
total percorrido (TOTH; VIGO, 2014).
O ‘Problema de Roteamento de Veículos Capacitados’ CPRV consiste em
uma frota de veículos homogênea, capaz de servir um conjunto de clientes com uma
demanda previamente conhecida a partir de um único depósito. Entretanto, deve
buscar otimizar as alocações das entregas para a sua frota de veículos, minimizando
a distância total percorrida, para que todos os pedidos sejam entregues. O serviço em
cada cliente deve começar dentro de um intervalo de tempo associado chamado de
‘tempo de janela’. O tempo das janelas pode ser difícil ou suave. Em caso de janelas
difíceis, um veículo que chega também ao cliente deve aguardar até que o cliente
esteja pronto para iniciar o serviço. Em geral, esperar antes do início de uma janela
temporal não incorre em nenhum custo. (GOLDEN; RAGHAVAN; WASIL, 2008).
Nesta Dissertação, o objetivo é a utilização do ‘Problema de Roteamento de
Veículos’. Portanto, o próximo assunto será apresentado uma definição formal do
problema.
17 Do inglês Capacitated PRV. 18 Do inglês Time Windows PRV.
42
2.6.1 Definição do Problema de Roteamento de Veículos
A definição formal do PRV pode ser encontrada em (POTVIN, 2009, p.2).
Considere G = (V, A) um grafo onde V = {1, 2, ..., n} é um vértice de A de um
arco. A vértice 1 é o depósito de uma frota idêntica de veículos Q que coleta a
demanda 𝑞G para cada vértice (cliente) 𝑖 ∈ 𝑉 − {1} . E 𝐴 possui o custo não negativo𝑐GK
associado a cada arco (𝑖, 𝑗) ∈ 𝐴, 𝑖 ≠ 𝑗 . Este custo é interpretado como a distância ou
o tempo do percurso, dependendo do contexto. A menos que começando, assume o
seguinte problema assimétrico, que é 𝑐GK = 𝑐KG para cada arco (𝑖, 𝑗). O problema é
determinado com um conjunto de rotas de veículos tal que:
Cada vértice, além do depósito, é visitado exatamente uma vez por exatamente
um veículo para atender sua demanda;
• Todas as rotas do veículo começam e terminam no depósito;
• A demanda total em cada rota não excede a capacidade do veículo;
2.6.2 Pseudocódigo
A solução clássica do PRV pode ser descrita em um pseudocódigo encontrado
em (TAVARES; BAPTISTA, 2009):
1. Construa um gráfico combinando as arestas das duas soluções pai.
2. Particione o conjunto de arestas neste gráfico com ciclos criados alternadamente selecionando uma borda do primeiro e segundo pais.
3. Selecione um subconjunto de ciclos.
4. Gere uma solução intermediária como segue. Pegue um pai e remova todas as arestas que estão no subconjunto selecionado de ciclos.
Então, as arestas no subconjunto de ciclos que vêm do outro pai são adicionadas. Neste ponto, a solução intermediária é uma coleção de
rotas conectadas ao depósito, além de subroteiros que não estão conectados ao depósito.
5. Crie uma solução completa. Uma heurística gananciosa é aplicada onde, a cada iteração, um subtítulo é mesclado pelo menos custo para
uma rota ou para outro subtítulo. O procedimento é repetido até que seja obtido um conjunto de rotas que visita todos os vértices.
43
6. Elimine as violações de capacidade. Usando uma função de penalidade para a capacidade de rota, trocas de arco 2-opt restritas e swap19
de vértice são aplicadas até que uma solução viável seja obtida. Essas modificações são consideradas restritas porque uma rota inviável deve
estar envolvida.
2.7 Computação ubíqua
O próximo passo na evolução envolve o movimento em direção à computação
onipresente20, na qual os computadores serão incorporados em nossos movimentos
e interações naturais com nossos ambientes - físicos21 e sociais (LYYTINEN; YOO,
2002). O campo da Computação Ubíqua em geral, é utilizado nas áreas da
Engenharia de Software e na Ciência da Computação. A ideia da ‘Computação
Ubíqua’ (ou abreviada: “Ubicomp”) ou ‘Computação Perversiva’, foi de M. Weiser
(1952-1999) (pode ser encontrada em Weiser (1991)), ele acreditava que os
computadores estariam disponíveis no ambiente físico, de forma invisível a seus
usuários.
A computação ubíqua nomeia a terceira onda da computação, apenas começando agora. Primeiro foram mainframes, cada um compartilhado por muitas pessoas. Agora estamos na era da computação pessoal, pessoa e máquina olhando de forma desconfortável uma para a outra na área de trabalho. Em seguida, vem a computação ubíqua, ou a era da tecnologia calma, quando a tecnologia recua para o fundo de nossas vidas (HARRISON; WIESE; DEY, 2010, p.1).
A terceira era da computação ubíqua, é representada nos dias atuais, e
caracterizada pelos avanços tecnológicos. Segundo Krumm (2016, p.12) os sistemas
da Ubicomp visam a heterogeneidade dos dispositivos, incluídos sistemas
embarcados invisíveis no cotidiano, objetos como carros e móveis22 dispositivos
moveis como assistente pessoal (PDAs), smartfones, dispositivos pessoais como
laptops, incluindo uma vasta quantidade de dispositivos, dispositivos grandes como
computadores table-top, simuladores de ambientes e construções que habitamos.
19 Duas vértices trocam de posição para a solução. 20 Ou computação ubíqua, no inglês ubiquitous computing. 21 Neste contexto hidrosfera, atmosfera e litosfera ambiente essências na terra. 22 Dispositivos utilizados na mobília.
44
Entretanto alguns pesquisadores como Saa, et al. (2018) alertam para preocupações
sobre como dispositivos portáteis podem afetar a privacidade das pessoas.
Contudo, o desafio é criar um novo tipo de relacionamento entre pessoas e
computadores, no qual o computador teria que assumir a liderança para se tornar
muito melhor em sair do caminho para que as pessoas pudessem seguir suas vidas
(WEISER, 1993). A visão de Weiser em que o computador não apenas seria capaz
de revolucionar a vida das pessoas, mas também auxilia-las. No entanto, o surgimento
de informações onipresentes não é apenas um sinal, mas também uma oportunidade,
e desafia muitas das hipóteses tradicionais sobre organizações, gerenciamento,
computação, comunicações e trabalho (SØRENSEN, 2005).
O paradigma da ‘Inteligência de Ambiente’ foi criado sob as bases da
Computação Ubíqua e seus sistemas e tecnologias são caracterizados como:
(ZELKHA; EPSTEIN, 1998).
• Incorporado: Muitos dispositivos em rede são integrados ao ambiente.
• Contexto ciente: Esses dispositivos podem reconectar você e seu
contexto situacional.
• Personalizado: Pode ser adaptado às suas necessidades.
• Adaptativo: Eles podem mudar em resposta a você.
• Antecipatório: Eles podem antecipar seus desejos sem meditar
conscientemente.
A Inteligência de Ambiente é relacionada ao termo de ‘Visão Inteligente de
Sistemas de Serviços’, no qual dispositivos embarcados se personalizam e se
adaptam e antecipam seus serviços.
Os dispositivos da computação ubíqua já são consideras tecnologias populares
e podem ser encontradas no cotidiano das pessoas. Com a popularidade dos
dispositivos de rastreamento pessoais tais como o Fitbit Flex e o Nike Fuel Band, e a
introdução do Google Glass, dispositivos portáteis estão entrando na vida
convencional (YE, 2014).
45
3 Otimização combinatória no movimento espacial animal
Este capitulo tem como objetivo, descrever as diferentes aplicações do PCV e
PRV, sistematicamente no movimento espacial animal. Apesar da existência de um
vasto número de espécies de insetos e seus padrões de variação comportamentais
para desenvolver suas tarefas, utilizaremos a computação e a biologia
comportamental para compreender o forrageamento. O PCV e o PRV são bem
conhecidos por encontrar o “menor caminho”, portanto podem ser utilizados para um
possível modelo de forrageamento no movimento espacial animal. Suas
aplicabilidades podem ser demonstradas em dois algoritmos bioinspirados que
utilizam o movimento espacial no forrageamento de formigas e abelhas. O
desenvolvimento de Sistemas Artificiais não implica a imitação completa de sistemas
naturais, mas os explora na busca de ideias e modelos (LUCIC; TEODOROVIC,
2002).
3.1 O Problema do Caixeiro Viajante aplicado no movimento espacial
animal
O estudo sobre o movimento animal, ou como utilizam o espaço, tanto na
natureza como em cativeiro, tem despertado o interesse de pesquisadores como:
Ploger e Yasukawa (2002), Applegate (2006), Boinski e Garber (2000), Jackson
(2015) dentre outros.
Emil Menzel (1973) em seu estudo com um grupo de chimpanzés; seu estudo
consiste em seis chimpanzés mantidos em uma gaiola próxima a um campo. O
treinador selecionava cada animal e mostrava o campo, ao mesmo tempo um
assistente, escondia dezoito pedaços de frutas em locais aleatórios. Após o treinador
retornar todos os chimpanzés à gaiola, passavam-se dois minutos e todos os animais
eram soltos simultaneamente. O animal selecionado usaria então sua memória da
localização do alimento para rapidamente reunir as frutas antes que outros animais
os localizassem por simples forrageamento (APPLEGATE, 2006).
46
Se o chimpanzé já viu no passado a localização de vários objetos escondidos no campo, como ele consegue obtê-los novamente e como ele organiza sua rota de viagem? o que seu itinerário nos diz sobre a natureza desse “mapeamento cognitivo” de sua estratégia e seus critérios de eficiência? (APPLEGATE, 2006, p.39 apud MENZEL, 1973)
Seus estudos, sobre a direção utiliza tanto os processos cognitivos como sua
estratégia de forrageamento ao localizar o alimento. A figura 5 indica o percurso de
um dos chimpanzés sendo “S” o inicio e “F” o fim do percurso, e as setas indicam o
caminho percorrido.
Figura 5: Percurso de um chimpanzé
Fonte: (APPLEGATE, 2006)
Determinar o menor caminho entre um conjunto de cidades a ser visitada é um
problema bem conhecido chamado Problema do Caixeiro Viajante. O estudo deste
problema tem atraído muitos pesquisadores de diferentes campos (por exemplo,
Matemática, Pesquisa Operacional, Física, Biologia ou Inteligência Artificial) e há uma
grande quantidade de literatura sobre ele (Reinelt 1994). O Problema do Caixeiro
Viajante também pode ser adequado para humanos em Macgregor (1996, 2000);
Pesquisadores encontraram no PCV soluções para espaços cognitivos de animais
Macdoland e Wilkie (1990); Gallistel e Cramer (1996); Miyata e Fujita (2010);
Teichroeb e Smeltzer (2018);
Observações de biólogos demonstram que animais viajam longas distâncias a
procura de água, alimentos e companheiros. Durante suas viagens os animais
procuram, rotas eficientes dentre os diversos locais em busca de “menor caminho”.
No caminho, os animais evitam rotas longas, caso contrário, ficariam expostos por
mais tempo aos predadores.
47
3.2 O Problema do Caixeiro Viajante no forrageamento das abelhas e
formigas
Se observamos a natureza, notamos que os insetos forrageadores preferem
obter um determinado nível de beneficio buscando o menor caminho nas suas viagens
forrageadoras. Eles tentam otimizar sua energia de forma eficiente durante a coleta
de néctar e as forrageadoras tomam decisões sem qualquer conhecimento global do
ambiente (ABRAHAM, et al, 2006). Portanto, assemelha-se aos problemas do PCV,
onde o caixeiro deve-se visitar todos os clientes (as forrageadoras visitam as floradas)
otimizando o percurso e minimizando o custo23 da viagem. Nota-se então a
possibilidade de aplicar o PCV, em um modelo que se assemelha ao comportamento
forrageador na natureza.
Se observarmos a natureza notamos que este modelo pode não ser o perfeito,
pois os insetos podem ou não visitar todos os lugares de coleta de alimentos. No livro
Lach (2010, p.214), afirma-se que a maioria das modelagens de estudo sobre
algoritmos (vide sessão 2.1 e 2.2) de forrageamento utilizam-se de caminhadas
aleatórias; entretanto, acreditam que as formigas utilizam estratégia de busca mais
avançada.
A Figura 6 indica (a) busca sistemática, (b) caminhada aleatória correlacionada
com grandes ângulos de giro, (c) caminhada aleatória correlacionada com pequenos
ângulos de giro. Em uma caminhada aleatória regular, a direção de uma etapa é
escolhida aleatoriamente, independentemente da direção do movimento anterior; na
caminhada aleatória correlacionada, as direções dos passos são escolhidas a partir
de uma distribuição centrada em torno da direção anterior do movimento (LACH;
PARR; ABBOTT, 2010).
23 Relevante em energia, despendida pelo animal na viagem.
48
Figura 6: Possíveis estratégias de forrageamento das formigas
Fonte: (LACH, PARR e ABBOTT, 2010)
Se uma forrageadora visitar dois pontos distintos de coleta de alimentos
(pontos 𝐴 e 𝐵) durante o percurso, existe a possibilidade de encontra outra fonte de
alimento promissora evitando o caminho para o ponto 𝐵, mas se alimentando-se no
ponto 𝐶. Tais problemas, encontrados no mundo real, mostram a complexidade24 ao
se obter um modelo da natureza e construir um modelo matemático utilizando
soluções exatas.
Mas se, em vez de invés de entrar nos sistemas em detalhe, apenas
explorarmos as ideias em busca de modelos. Segundo Boinski e Garber (2000, p.
172) é possível como descrevem: “talvez a variante mais flexível do (Problema do
Caixeiro Viajante Genérico) PCVG, é o mais parecido com problemas biológicos de
forrageamento envolvendo recursos de renovação fixa, é o Problema de Roteamento
de Veículos [...] para traduzir este problema a um forrageamento de um beija-flor, nos
canteiros de flores ou um primata se movendo entre as árvores de fruto, substitua
“recursos” para “clientes”, “forrageadoras” para “caminhões”, “locais de descanso”
para “depósitos”, “comida disponível” para o “material a ser pego”, “capacidade do
estômago” para uma “capacidade máxima de caminhão”, “período padrão de
produção” para o “tempo de janela do cliente” e “intervalo de renovação” para o
“horizonte de tempo do cliente”. Claramente, as características de forrageamento são
bem diferentes para cada espécie
Claramente, as características de forrageamento são bem diferentes para cada
espécie. Os herbívoros encontram alimento facilmente e os carnívoros geralmente
gastam mais energia para localizar alimento. Contudo, cada espécie estabelece seu
24 Refere-se a escala dos problemas.
49
padrão de forrageamento. Apesar das diferenças entre as espécies, compreende-se
que os animais preferem optar por caminhos menores ao percorrer longas jornadas
em busca de alimento. Quando um único indivíduo consegue encontrar alimento,
otimizar a rota entre o ninho e a fonte de alimento passa a ser uma necessidade para
a economia de energia.
Se considerarmos os animais com características cognitivas de memorização,
e “aprendizado”, notamos os princípios de evolução nos animais. Observamos que os
animais preferem obter um determinado grau de beneficio durante o cotidiano,
otimizando os percursos do forrageamento. Embora Janson (2014, p.1) afirme que
não existe evidência nos primatas ou em outros animais de utilização do PCV, mas
apenas da utilização de regras simples de forrageamento, tal como visitar recursos
“conhecidos”.
Também observamos que o durante o forrageamento os animais coletivistas
(em especial nas abelhas e formigas) utilizam-se da aleatoriedade. Ao demarcar a
melhor rota entre o ninho e a fonte de alimentos, fazem uso da waggle-dance ou o
ferômonio. A comunicação utilizada nas abelhas pode informar a distancia, direção e
a classificação da fonte de alimento. As formigas utilizam-se do reforço do feromônio
na trilha, para otimizar o percurso. Ambos recursos destinados a procurar a “menor
distância”, um processo semelhante ao qual é utilizado nos algoritmos modernos e na
computação evolucionária.
Portanto, nestes cenários, utilizaríamos as heurísticas e metaheurísticas. Ao
aplicar as heurísticas e metaheurísticas em um modelo, podemos descrever melhor
suas características como estórias, metáforas, fenômenos etc.
3.3 Algoritmos bioinspirados
Os algoritmos bioinspirados, utilizam a natureza como fonte de inspiração para
problemas computacionais. Algoritmos bioinspirados podem ser efetivamente usados
para problemas de otimização, exploração e mapeamento e reconhecimento de
padrões (DRESSLER; AKAN, 2010). As ideias observadas na natureza e nas
atividades biológicas, motivam o desenvolvimento de algoritmos sofisticados para
diversas soluções, de um mesmo problema.
50
A natureza é, naturalmente, uma grande e imensa fonte de inspiração para resolver problemas difíceis e complexos em ciência da computação, uma vez que exibe fenômenos extremamente diversificados, dinâmicos, robustos, complexos e fascinantes. A computação sempre encontra a solução ideal para resolver seu problema, mantendo um equilíbrio perfeito entre seus componentes. Este é o impulso por trás da computação de inspiração biológica. Algoritmos inspirados na natureza são metaheurísticas que imitam a natureza para resolver problemas de otimização, abrindo uma nova era na computação (BINITHA, 2012, p.1).
Esta classe de algoritmos apresenta aspectos evolucionários e “inteligência de
enxame25” pois são inspirados por um processo de “sobrevivência do mais apto” ou
“seleção natural”. As duas classes ou direções mais predominantes e bem-sucedidas
em algoritmos bioinspirados envolvem Algoritmos Evolucionários e Algoritmos
baseados em enxames que são inspirados na evolução natural e no comportamento
coletivo dos animais respectivamente (BINITHA, 2012).
Sistemas que fazem uso da inteligência de enxame tipicamente utilizam uma
população simples de agentes26 computacionais, capazes de interagir com o ambiente
em busca de um objetivo. Estes agentes computacionais seguem instruções simples
e não centralizadas. Na inteligência de enxame são tomados como exemplos da
natureza as colônias de formigas, aves reunindo-se, pastoreio de animais,
crescimento bacteriano etc.
3.3.1 Otimização da Colônia de Formigas
Tomando como “bioinspiração”, uma colônia de formigas, foi desenvolvido o
algoritmo chamado “Otimização da Colônia de formigas27” (ACO). O precursor dos
algoritmos de formiga, de Swarm Intelligence foi o Ant System (AS) desenvolvido por
Dorigo, et al. (1996); seguido do Ant Colony System (ACS) de Dorigo e Gambardella
(1997); e ao final o ACO de Dorigo (1992);
Os algoritmos de formiga foram inicialmente propostos por Dorigo e
colaboradores como uma abordagem “multiagente” para problemas difíceis de
25 Do inglês Swarm Intelligence (SI). 26 A função de um agente especifica a ação executada pelo agente em resposta a qualquer sequência de percepções (RUSSELL e NORVIG, 2013).Compreende-se um agente como uma entidade computacional, que de forma autônoma e continua em um ambiente, realiza ações. 27 Do inglês Ant Colony Optimization (ACO).
51
otimização combinatória, como o Problema do Caixeiro Viajante (PCV) e o Problema
da Atribuição Quadrática (PAQ) (DORIGO; CARO; GAMBARDELLA, 1999). Nos
algoritmos de formiga, a população de formigas artificiais, utilizam técnicas
metaheurísticas para solucionar problemas de otimização combinatória. No ACO o
problema é convertido para um grafo28, e consiste nas formigas artificiais procurarem
o menor caminho entre o ninho e a fonte de alimento (como apresentando no
comportamento de forrageamento). As formigas artificiais movem-se em busca de
uma solução otimizada.
ACO baseia-se nos princípios do processo de forrageamento das formigas [...] as formigas realizam uma busca aleatória (random walk) para localizar comida [...] se for bem-sucedido, as formigas retornam ao ninho (seguindo sua própria trilha) (DRESSLER; AKAN, 2010, p.8).
O feromônio deixado na trilha das formigas artificiais, aumenta a probabilidade
da escolha do mesmo caminho pelas demais. Isso ajuda as formigas a encontrar o
caminho dos membros da equipe, à medida que detectam o feromônio e escolhem,
em probabilidade, caminhos com maior concentração de feromônio (KATIYAR;
IBRAHEEM; ANSARI, 2015).
O algoritmo ‘Otimização da colônia de formigas’ tem sido utilizado para
solucionar problemas como:
• De probabilidade, utilizando o (PCV), Balaprakash (2009).
• De ACO dinâmico de rotas, para conteúdo mobile, Manome e Asaka (2015)
• De convergência adaptativa de trajetória, Zheng (2017).
• De cooperação humano/computador para rotas de tubulação de navio,
Wang, et al. (2018).
• De navegação de um robô mobile, Mallikarjuna, et al. (2018).
28 Com ideia semelhante ao grafo de Euler apresentado na sessão 2.4.
52
• De decisões analíticas que utilizam Mobile Big Data, Banerjee e Badr
(2018).
• De otimização de rotas de desastre em tempos de incerteza, Li, et al. (2018).
Os algoritmos baseados em formigas foram aplicados a outros problemas de
otimização combinatória, como problema de atribuição quadrática, coloração de
gráficos, programação de job-shop, ordenação sequencial e roteamento de veículos
(BONABEAU; DORIGO; THERAULAZ, 1999).
Tavares e Baptista (2009, p.1) sustentam que “os algoritmos bioinspirados são
representativos dessa tendência e foram aplicados a uma grande variedade de
problemas, incluindo problemas de otimização. Entre eles, o Problema de Roteamento
de Veículo (PRV) geraram muita atenção, porque são inerentemente complexos e
ocupam um lugar central nas atividades de distribuição no mundo real”. Os algoritmos
bioinspirados, são uma fonte de inspiração para resolver problemas computacionais
complexos, devidos a sua versatilidade, dinâmica e robustez em busca de uma
solução otimizada.
Pesquisadores encontraram na área de ‘inteligência de enxames’ uma forma
de solucionar os problemas gerados pelo PRV. Seundo Yu (2009, p.1) “Se tomarmos
o depósito central como o ninho e os clientes como alimento, o PRV é muito
semelhante aos comportamentos de busca de alimentos das colônias de formigas na
natureza. Isso faz com que a codificação de uma otimização de colônia de formigas
para o PRV seja simples”. Ao utilizar-se algoritmo ACO para os problemas do PRV, é
possível produzir bons resultados heurísticos, como comprovado ao longo dos anos
como:
• Duas aplicações chamadas DyvOil e AntRoute para problemas PRV,
Gambardella (2003).
• Otimização em um mundo real (real-world) utilizando PRV, Rizzoli (2007).
• PRV utilizando ACO genético, Liangzhi (2008).
53
• Uma melhoria do ACO para PRV, Yu (2009).
• Uma pesquisa sobre otimização de um sistema de emergência, Fei (2012).
• ACO baseadas em distúrbios caóticos e vizinhança, Li, et al. (2013).
A maioria das ideias do ACO vem de formigas verdadeiras. Em particular, o uso de: (a) uma colônia de indivíduos cooperantes, (b) um rastro de feromônio (artificial) para comunicação local estigmergia29, (c) uma sequência de movimentos locais para encontrar caminhos mais curtos, e (d) uma decisão estocástica política usando informações locais e sem olhar para frente (Dorigo et al.,1999, p.141).
Os modelos biológicos, encontrados na natureza ajudam a prever como
grandes colônias de formigas resolvem os problemas de forrageamento, inspirando
sistemas computacionais, que podem enfrentar problemas semelhantes. Os sistemas
computacionais que possuem problemas como flexibilidade e robustez, podem
utilizar-se da mesma inspiração da natureza para suas soluções.
3.3.2 Algoritmo de Colônia de Abelhas Artificiais
Algoritmos de Swarm Intelligence, baseados no comportamento das abelhas
na natureza, são encontrados na literatura especializada. Tais algoritmos possuem
características de coleta de alimentos e aprendizado. Ao pesquisar a literatura de
algoritmos aplicados a colônias de abelhas, podem ser classificados em três linhas
(BAYKASOGLU; ÖZBAKIR; TAPKAN, 2007):
• Comportamentos de coleta de alimentos: Bee System (BS) Lucic e
Teodorovic (2003); A Honey Bee Algorithm Nakrani de Tovey (2003);
Beehive de Wedde, et al. (2004); Artificial Bee Colony Algorithm (ABC) de
Karaboga (2005); BCO Based de Marković e Aćimović (2007);
multiobjective artificial bee colony (MOABC) de Bindma, et al. (2018).
29 Compreende-se como um mecanismo de comunicacao indireta, atraves do meio ambiente, entre os agentes computacionais e suas acoes. Vide sessão 2.2.2.
54
• Comportamentos de acasalamento: Marriage in Honey-Bees Optimization
(MBO) de Abbass e Teo (2003); MBO Based de Chang (2006); Improved
HBMO de Bozorg, et al. (2006).
• Conceito de abelha-rainha: Queen-Bee Evolution Algorithm (QBE) (SUNG,
2003); QBE Based de Qin et al. (2004); Bee Crossover de Kara (2004);
Modified QBE de Azee e Saad (2004).
Um dos algoritmos que simulam o comportamento forrageador das abelhas o
Algoritmo de Colônia de Abelhas Artificiais30 (ABC), foi proposto por Karaboga (2005).
No algoritmo ABC, em uma colônia de abelhas artificiais, as abelhas são classificadas
em três grupos de operárias: campeiras, seguidoras e escudeiras.
Então, o número de abelhas campeiras é igual ao número de fontes de alimento. O número de abelha campeiras é igual ao número de fonte de alimentos. Quando o local de alimento é descartado pela abelha campeira, é forçada a se tornar uma escudeira e busca alimento aleatoriamente. abelhas empregadas compartilham informações com as abelhas do seguidoras em uma colméia para que possa escolher uma fonte de alimento para forragear (Yang, 2010, p.46).
No ABC, as fontes de alimento representam possíveis soluções e a quantidade
de néctar de uma fonte de alimento corresponde a qualidade da solução. Antes de
iniciar o programa no ABC são inseridos três parâmetros: tamanho da colônia
(quantidade de abelhas campeiras e escudeiras); o número de tentativas de melhorar
uma fonte antes de abandonar; e o número de interações (cíclicas do algoritmo). Após
inicializados os parâmetros, cada abelha campeira é designada a sua fonte de
alimento. A abelha campeira carrega a informação sobre a fonte de alimento e
compartilha com uma probabilidade de dança entre as seguidoras que aguardam. As
abelhas seguidoras, aguardam a dança para tomar uma decisão de qual fonte de
alimento explorar. Quanto maior a quantidade de alimento, maior a probabilidade de
a fonte ser preferida entre as seguidoras. E quando a abelha campeira (cuja a fonte
de alimentos é exaurida) torna-se uma abelha escudeira (cujo o objetivo é explorar o
ambiente aleatoriamente) em busca de novas fontes de alimento. O desempenho da
pesquisa local do algoritmo ABC depende em mecanismos de busca de vizinhança e
30 Do inglês Artificial Bee Colony (ABC).
55
seleção gananciosa realizada por abelhas empregadas e observadoras (BINITHA,
2012).
Lucic & Teodorovic (2001) foram os primeiros pesquisadores a empregar os
princípios básicos da inteligência coletiva das abelhas na solução de problemas de
otimização combinatórial, introduzindo BS, que foi usado para resolver o PVC
(SERAPIÃO, 2009). Os avanços produzidos no BS foram capazes de solucionar
problemas como PCV; o PRV estocástico Lucic (2002); e melhorar o BS Lucic e
Teodorovic (2002). Portanto, soluções em que utilizam o ABC para solucionar PRV
foram possíveis: An artificial bee colony algorithm for the capacitated vehicle routing
problem, de Yuen, et al. (2011); Artificial bee colony algorithm with scanning strategy
for the periodic vehicle routing problem, de Yao, et al. (2013).
56
4 O Problema de Roteamento Humano
Na sessão 3 foi discutido como o forrageamento animal pode ser utilizado no
PCV e no PRV, bem como os algoritmos bioinspirados. Seus instintos de navegação,
durante o forrageamento, demonstra a flexibilidade da colônia, quando sujeito as
adversidades cotidianas. Sua capacidade de adaptação, demonstrada quando a
colônia compreende a necessidade de mudanças, permite a sobrevivência da espécie
através da manutenção da colônia.
Neste mesmo contexto o Problema de Roteamento Humano (PRH), também é
inspirado no comportamento de forrageamento dos animais. O PRH pode ser
considerado uma generalização do PRV. O PRV possui um conjunto de soluções, que
permite a utilização de uma frota de veículos heterogênea com restrições (carga,
tempo etc.) destinados a encontrar o “melhor caminho” entre todos os pontos. As
medidas consideradas são as de menor distância entre dois pontos (ou duas cidades)
e compreende-se em termos de tempo. Portanto a noção de distância nem sempre é
em termos de distância física, mas em outras medidas, tal como o tempo.
Quando designados aos humanos, pistas que nos orientem a percorrer longas
distâncias utilizando a navegação nos são úteis, especialmente se considerarmos os
insetos com habilidade neurais. Então, as leis dos problemas de estrutura básica de
movimento espacial demonstrado nos animais podem ser utilizadas pelos humanos,
aplicando as designações apropriadas.
Os desafios significativos de locomoção humana, aumentam a complexidade
quando aplicados a larga escala e a natureza dinâmica dos problemas, recursos
limitados de computação (como arquiteturas heterógenas, arquiteturas centralizadas
em uma mesma infraestrutura) e a dificuldade de se obter uma rota otimizada; nos
levam a falhas (ou problemas) em potencial. Estes desafios foram tratados com
sucesso pela natureza, como resultado de milhões de anos de evolução, e estes
sistemas e processos com características intrínsecas atraentes como adaptabilidade
ambiental, resiliência a falhas, colaboração bem-sucedida e um conjunto de regras
que geram uma inteligência global na organização, e a capacidade de sobrevivência
e evolução.
57
4.1 Rotas estáticas e rotas dinâmicas
Semelhante aos algoritmos bioinspirados apresentados, na sessão anterior,
observa-se que quando temos um conjunto de rotas pré-definidas e desejamos
otimiza-las encontrando o “menor caminho” entre o nó de inicio/fim passando por
todos as cidades (ou clientes como no PRV). Um processo semelhante acontece,
quando mudamos uma rota estática, para uma rota dinâmica, com o objetivo de
encontrar a menor distância.
Compreende-se rotas estáticas, como os caminhos que dificilmente são
alteráveis. Exemplo como as rotas de trens; ou percursos humanos, as quais nos
habituamos a ter êxito e dificilmente mudaríamos. Porém, as rotas dinâmicas,
compreende-se que possa haver uma sugestão de melhoria, e possíveis otimizações
de trajeto.
Portanto mudar uma rota estática, poderia significar uma melhoria em termos
de tempo (ou distância). Como por exemplo, um estabelecimento comercial onde o
caminho está bloqueado momentaneamente, e para tal seria necessário utilizar-se de
uma rota dinâmica e encontrar o local desejado.
58
4.2 Definição formal do problema
Nesta dissertação o PRH será considerado uma generalização do PRV.
Portanto, em alguns aspectos se assemelha (pontos de clientes, serão considerados
pontos de interesse; os veículos, serão substituídos por humanos; devem ser
respeitados os horários em que é permitido visitar os pontos de interesse; depósito é
considerado inicio e o fim do percurso31; pode ou não haver limite de peso em cada
tour – por exemplo: mochilas e bolsas).
Especificações do PRH:
• Limitado a rotas humanas.
• Possui o inicio e o fim do tour no ponto de origem.
• Deve abranger somente ruas, estradas, avenidas e caminhos possíveis
para humanos.
• Todos os pontos de interesse deverão ser percorridos.
• Os pontos de interesse, podem ou não ser agendados horários de
visitação.
• Pode ou não haver limite de peso, durante o passeio.
Portanto o problema formal é definido como:
Dado: um conjunto de requisições de ponto de interesses.
Tarefa: determinar um conjunto de rotas de mínimo custo para os pontos de
interesse; em particular todos os pontos de interesse são obrigatórios.
31 A rota entre um conjunto de pontos de interesse iniciados e finalizados no mesmo ponto.
59
4.3 Variantes do Problema de Roteamento Humano
4.3.1 Problema de Roteamento Humano com Múltiplas Viagens
Semelhante ao “Problema de Roteamento de Veículos com Múltiplas Viagens32”
(PRVMV) chamado Problema de Roteamento Humano com Múltiplas Viagens
(PRHMV). No PRV os clientes são atendidos por apenas um único veículo que, por
sua vez, atente apenas uma rota durante um período de planejamento. No PRHMV
será modificado permitindo múltiplas viagens e, assim, uma pessoa poderá utilizar
mais de uma rota durante um período de planejamento.
4.3.2 Problema de Roteamento Humano Aberto
Semelhante ao “Problema de Roteamento de Veículos Aberto33” (PRVA) chamado
“Problema de Roteamento Humano Aberto” (PRHA); No PRV, o veículo não necessita
voltar ao depósito depois de atender o ultimo cliente. Neste contexto no PRHA, o
usuário não necessita voltar para o ponto de partida
32 Do ingles Vehicle Routing Problem with Multiple Trips (VRPMT). 33 Do ingles Open Vehicle Routing Problem (OVRP).
60
4.4 Protótipo otimizador de rotas humanas
O protótipo utiliza-se da computação ubíqua para avaliar o trajeto de seu
usuário. Durante a interação o usuário pode selecionar quais restrições (representado
pelo input) deseja aplicar durante o percurso e o componente chamado “otimizador
de rotas” buscaria no Banco de Dados (BD) históricos de todos os usuários, e todos
os pontos de interesse e a resposta do protótipo é uma rota otimizada (representado
pelo output y).
Figura 7: Otimizador de rotas e o componente responsável por “Otimizar rotas”
A figura 7, descreve o funcionamento do protótipo e possui dois objetivos: 1)
auxiliar o planejamento dos seus usuários quanto às melhores rotas; e 2) ser utilizado
como ferramenta preditiva quanto à mobilidade urbana. Durante o planejamento de
mobilidade urbana, podem emergir novas ferramentas que visam auxiliar à
compreensão de situações cotidianas dos pedestres durante suas caminhadas, tais
como medição do fluxo de pessoas, análise de seus padrões e identificação de novos
trajetos.
61
Durante uma caminhada, o usuário pode selecionar um trajeto (opcional) tal
como uma caminhada na praia até o restaurante. Tal proposta pode auxiliar novos
planejamentos de comportamento dos pedestres.
62
5 Casos de uso
Os casos de práticos apresentados a seguir demonstram, as diversas
situações em que pode ocorrer um Problema de Roteamento Humano.
5.1 Aeroporto – Estudo de caso 1
Problema: o estudo de caso 1, consiste de um viajante desejando embarcar
voo imediatamente, buscando o seu portão de embarque.
Figura 8: Problema do aeroporto
O viajante seguirá os passos indicados pelo campo “Rota” indicando a direção.
Há uma sequência de paradas tais como o guichê da companhia aérea, a polícia
federal, banheiro, setor de compras e, ao final, o portão de embarque. Neste
momento, o viajante se depara com alguns procedimentos obrigatórios e outros não-
obrigatórios. Contudo, todos os procedimentos levam em consideração o tempo e a
distância. A primeira imagem demonstra o problema. A figura 9, demonstra uma
possível solução ao utilizar-se a ferramenta otimizadora (protótipo da sessão 4.4).
63
Figura 9: Possível solução para o problema do aeroporto
Observações e resultado: através de uma prévia orientação utilizando o
protótipo do PRH, o viajante pode visualizar uma possível rota otimizada durante o
percurso.
64
5.2 Museu – Estudo de caso 2
Problema: estudo de caso 2 - no museu, um visitante tem dois objetivos: 1) conhecer
uma estátua famosa; 2) conhecer uma pintura famosa.
Figura 10: Problema do museu
Há uma sequência de paradas, tais como guichê de bilhetes de ingresso,
estátua 1 (objetivo), banheiros, quadros (1, 2) e, ao final, o quadro 3. A figura 11
mostra uma possível solução quando se utiliza a ferramenta otimizadora (protótipo da
sessão 4.4).
65
Figura 11: Possível solução para o problema no museu
Observações e resultado: através de uma prévia, orientação utilizando o
protótipo do PRH, o visitante pode visualizar uma possível rota otimizada durante o
percurso.
66
5.3 Shopping Center – Estudo de caso 3
Problema: O estudo de caso 3 - em um Shopping Center, uma empresa de
redes de fornecimento34 deseja aumentar a satisfação dos seus clientes. Para atingir
seu objetivo, a empresa deseja entregar rapidamente seus produtos, otimizando o
percurso dos seus entregadores.
Figura 12: Problema no entregas
Devido a uma sequência de fatores, tais como estacionamento, carga e
descarga de produtos, secretaria, elevador, lojas (1,2) e o objetivo (loja 3), o
entregador pode percorrer erroneamente o 1º andar durante a entrega dos produtos.
Tal erro pode gerar atrasos e, eventualmente, descumprir o horário agendado de
entrega a outros clientes. Porém, o erro pode acontecer com maior frequência por
existirem diversos entregadores em diversos locais e horários pré-agendados com os
clientes para a entrega de produtos.
34Do inglês supply chains.
67
Figura 13: Possível solução para o problema de entregas
Observações e resultado: através de uma prévia orientação pela ferramenta
otimizadora de rotas, os entregadores podem alcançar seus objetivos com melhore
orientação.
68
6 Conclusões
Durante a dissertação foi demonstrado como o PCV e o PRV, podem ser
utilizados para modelos computacionais de forrageamento, apesar de sua capacidade
explanatória limitada (devido os fenômenos e comportamentos apresentados nos
insetos coletivistas) quando evolvem fenômenos da natureza.
A metáfora do forrageamento, verdadeira em animais, pode ser aplicar a os
problemas humanos enfrentados no cotidiano, como buscar o “menor caminho”. Nos
casos práticos, foi demonstrada a problemática na qual se insere o Problema de
Roteamento Humano (PRH). Durante a apresentação do conjunto das ideias que
compõem o PRH, foi demonstrado sua principal inspiração no forrageamento dos
insetos coletivistas, tais como sua capacidade auto-organização e decisões
descentralizadas.
A partir da observação do comportamento dos insetos coletivistas, nota-se que
eles não utilizam “ruas”, “avenidas” ou “estradas”, mas todos os caminhos possíveis
para um forrageamento otimizado, capaz de economizar energia. O benefício de se
viver em uma colônia, é que diversos insetos fazem a busca por alimento,
maximizando as chances de encontrar um local promissor.
Foi apresentado o desafio, de propor o Problema de Roteamento Humano,
baseado em um modelo de solução, o PRV, bem como um protótipo e seus casos
práticos. Porém, o campo de soluções para um mesmo problema pode ser vasto, não
se limitando a programação dinâmica, programação linear e não-linear.
As técnicas heurísticas e metaheurísticas auxiliam o PRH, a propor soluções
otimizadas. Pois o PRH herda a complexidade NP-difícil, pois requer boas
combinações dentre as diversas restrições que podem ser aplicadas ao problema.
O principal objetivo do PRH, é melhorar o cotidiano das pessoas, bem como
melhorar a mobilidade urbana. A melhora do cotidiano é em busca de otimizar o tempo
e/ou distância dos trajetos.
69
6.1 Discussões
Ao se utilizar rotas dinâmicas no PRH, demonstra-se uma possibilidade de
otimizar caminhos em situações nas quais rotas de evacuação se fazem necessárias,
tais como eventos para grande público (exemplo: apresentações musicais, saída de
estádios, desembarque de estações) ou um vulcão em erupção.
Estes cenários podem ajudar as autoridades a preverem melhores rotas de
evacuação em massa. Também podem ser utilizados por profissionais que trabalham
para obter melhorias na mobilidade urbana, prevendo melhores caminhos.
6.2 Contribuições
Durante o cotidiano humano, há problemas de tempo e/ou distância nos
percursos. O estudo apresentado destina-se melhoria da mobilidade urbana. Através
de casos práticos, pode-se ter uma melhor visão de onde se insere os Problemas de
Roteamento Humano.
6.3 Trabalhos futuros
Aplicar os algoritmos bioinspirados, Otimização da Colônia de Formigas e o
Algoritmo de Colônia de Abelhas Artificiais para um problema de PRH.
Empresas de planejamento que utilizam do espaço urbano como (shows para
grandes multidões, saída de estádios de futebol ou feiras ao ar livre) das quais
desejam melhorar os percursos dos seus usuários e melhorar a experiência durante
os eventos.
Empresas privadas como (Museus, Aeroportos etc.) podem melhor planejar os
percursos de seus usuários aumentando a satisfação.
70
Referências ABBASS, H.; TEO, J. A True Annealing Approach to the Marriage in Honey-Bees
Optimization Algorithm. International Journal of Computational Intelligence and Applications, 2003.
ALCOCK, J. Comportamento animal: uma abordagem evolutiva. [S.l.]: Artmed
Editora, 2016.
APPLEGATE, D. L. E. A. The Traveling Salesman Problem: A Computational Study.
[S.l.]: Princeton university press, 2006.
AZEEM, M.; SAAD, A. Modified Queen Bee Evolution Based Genetic Algorithm for
Tuning of Scaling Factors of Fuzzy Knowledge Base Controller. IEEE INDICON 2004 Proceedings of the India Annual Conference, p. 299-303, 2004.
BAKER, B. M. . A. M. A. A. A genetic algorithm for the vehicle routing problem.
Computers & Operations Research, v. 30, n. 5, p. 787-800, 2003.
BALAPRAKASH, P. Estimation-based ant colony optimization and local search for the
probabilistic traveling salesman problem. Swarm Intelligence, v. 3, n. 3, p. 223–242,
2009.
BANERJEE, S.; BADR, Y. Evaluating Decision Analytics from Mobile Big Data using
Rough Set Based Ant Colony. In: SKOURLETOPOULOS. Mobile Big Data: A Roadmap from Models to Technologies, 2018. 217–231.
BARAGONA, R.; FRANCESCO, B.; POLI, I. Evolutionary statistical procedures: an
evolutionary computation approach to statistical procedures designs and applications.
[S.l.]: Springer Science & Business Media, 2011.
BAR-COHEN, Y. Biomimetics: biologically inspired technologies. [S.l.]: CRC Press,
2005.
BAYKASOGLU, A.; ÖZBAKIR, L.; TAPKAN, P. Artificial Bee Colony Algorithm and Its
Application to Generalized Assignment Problem. Swarm Intelligence: Focus on Ant and Particle Swarm Optimization, F.T.S. Chan and M.K. Tiwari (Eds.), Itech Education and Publishing, Vienna, Austria, p. 113-144, 2007.
71
BEGON, M.; TOWNSEND, C. R.; HARPER, J. L. Ecologia: de indivíduos a
ecossistemas. [S.l.]: Artmed Editora, 2009.
BÄCK, T. D. B. F. A. Z. M. E. Evolutionary computation 1: Basic algorithms and
operators. [S.l.]: CRC press, v. 1, 2000.
BINDIMA, T.; SHAHANAS, U. K.; ELIAS, E. Low Complexity Fan Filters using
Multiobjective Artificial Bee Colony Optimization Aided McClellan Transformation for
Directional Filtering. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018.
BINITHA, S. E. A. A survey of bio inspired optimization algorithms. International Journal of Soft Computing and Engineering, v. 2, n. 2, p. 137-151, 2012.
BOINSKI, S.; GARBER, P. A. On the move: how and why animals travel in groups.
University of Chicago Press: [s.n.], 2000.
BONABEAU, E.; DORIGO, M.; THERAULAZ, G. Swarm Intelligence: From Natural
to Artificial Systems. [S.l.]: Oxford University Press, 1999.
BOUSSAÏD, I.; LEPAGNOT, J.; SIARRY, P. A survey on optimization metaheuristics.
Information Sciences, v. 237, p. 82-117, 2013.
BOZORG, H.; AFSHAR, A.; MARIANO, M. . Honey-Bees Mating Optimization (HBMO)
Algorithm: A New Heuristic Approach for Water Resources Optimization. Water Resources Management, v. 20, p. 661-680, 2006.
BULLNHEIMER, B.; HARTL, R. F.; STRAUSS, C. An improved ant System algorithm
for thevehicle Routing Problem. Annals of operations research, v. 89, p. 319-328,
1999.
CÉZILLY, F. Encyclopedia of Behavioral Neuroscience. In: THOMPSON, R. Behavior adaptation and selection. [S.l.]: [s.n.], 2010.
CARNEIRO, V. A.; GONÇALVES, B. B.; NETO, C. D. M. S. ESTRATÉGIA DE
FORRAGEAMENTO DE POLINIZADORES EM Galactia peduncularis (Benth.)
Taub.(LEGUMINOSAE: PAPILIONOIDEA) NO PARQUE ESTADUAL DA SERRA DE
CALDAS NOVAS (GO). Geoambiente On-line, n. 19, p. 01-09 , 2013.
72
CARVALHO, J. M. S. Programação Linear: Algoritmos simplex primal, dual,
transporte e afetação. [S.l.]: Vida Economica Editorial, 2014.
CHANG, H. Converging Marriage in Honey-Bees Optimization and Application to
Stochastic Dynamic Programming. Journal of Global Optimization, v. 35, p. 423-
441, 2006.
COELLO, C. C. A.; LAMONT, G. B.; VELDHUIZEN, D. A. V. Evolutionary algorithms for solving multi-objective problems. New York: Springer: [s.n.], v. 5, 2007.
CORDEAU, J.-F. M. G. G. L. J.-Y. P. F. S. A guide to vehicle routing heuristics. Journal of the Operational Research society, v. 5, n. 53, p. 512-522, 2002.
DANTZIG, G.; RAMSER, J. H. The truck dispatching problem, n. 6.1, p. 80-91, 1959.
DETRAIN, C.; DENEUBOURG, J.-L. Self-organized structures in a superorganism: do
ants “behave” like molecules? Physics of life Reviews, v. 3, n. 3, p. 162-187, 2006.
DI CARO, G.; DORIGO, M. AntNet: Distributed stigmergetic control for
communications networks. Journal of Artificial Intelligence Research, v. 9, p. 317-
365, 1998.
DORIGO, M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
DORIGO, M.; CARO, G. D.; GAMBARDELLA, L. M. Ant algorithms for discrete
optimization. Artificial life, v. 5, n. 2, p. 137-172, 1999.
DORIGO, M.; GAMBARDELLA, L. M. Ant colony system: a cooperative learning
approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, v. 1, n. 1, p. 66, 1997.
DORIGO, M.; GAMBARDELLA, L. M. Ant colony system: a cooperative learning
approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, v. 1, n. 1, p. 53-66, 1997.
DORIGO, M.; MANIEZZO, V.; COLORNI, A. Ant system: optimization by a colony of
cooperating agents. IEEE Trans. Syst. Man Cybern. B Cybern., v. 26, n. 1, p. 29-41,
1996.
73
DRESSLER, F.; AKAN, O. B. A survey on bio-inspired networking. Computer Networks, v. 54, n. 6, p. 881-900, 2010.
EBERHART, R. C.; SIMPSON, P. K.; DOBBINS, R. W. Computational Intelligence PC Tools. [S.l.]: Boston: Academic Press, 1996.
EIBEN, A. E.; SMITH, J. E. Introduction to Evolutionary Computing. [S.l.]: Springer,
2015.
EULER, L. Leonhard Euler and the Königsberg bridges., v. 189, p. 66-72., 1953.
FEI, T. The Research of Emergency Logistics Routing Optimization Based on
Improved Ant Colony Optimization. Advanced Materials Research, v. 482, p. 2519-
2523, 2012.
FOGEL, D. B. Evolutionary computation: principles and practice for signal
processing. [S.l.]: SPIE Press, v. 43, 2000.
FOURCASSIÉ, V.; TRANIELLO, J. F. A. Effects of experience on food-searching
behavior in the antFormica schaufussi (Hymenoptera: Formicidae). Journal of Insect Behavior, v. 6, n. 3, p. 287-299, 1993.
GALLISTEL, C. R.; CRAMER, A. E. Computations on metric maps in mammals: getting
oriented and choosing a multi-destination route. Journal of experimental biology, v.
199, n. 1, p. 211-217, 1996.
GAMBARDELLA, L. M. Ant colony optimization for vehicle routing in advanced
logistics systems. Proceedings of the International Workshop on Modelling and Applied Simulation (MAS 2003), 2003.
GEEM, Z. W.; KIM, J. H.; LOGANATHAN, G. V. A New Heuristic Optimization
Algorithm: Harmony Search. simulation, v. 76.2, p. 60-68, 2001.
GENDREAU, M. et al. Metaheuristics for the vehicle routing problem and its
extensions: A categorized bibliography. The Vehicle Routing Problem: Latest Advances and Challenges, B.L. Golden, S. Raghavan, Boston, n. forthcoming,
2007.
74
GOLDEN, B. L. . E. A. W. J. P. K. A. I.-M. C. The impact of metaheuristics on solving
the vehicle routing problem: algorithms, problem sets, and computational results. In Fleet management and logistics, p. 33-56, 1998.
GOLDEN, B. L.; RAGHAVAN, S.; WASIL, E. A. The Vehicle Routing Problem: Latest
Advances and New Challenges. [S.l.]: Springer Science & Business Media, v. 43,
2008.
GOSS, S. E. A. Self-organized shortcuts in the Argentine ant. Naturwissenschaften,
v. 76, n. 12, p. 579-581, 1989.
GRAHAM, C. H. Vision and Visual Perception. 1. ed. [S.l.]: John Wiley & Sons Inc;,
1965.
GRASSÉ, P.-P. La reconstruction du nid et les coordinations interindividuelles
chezBellicositermes natalensis etCubitermes sp. la théorie de la stigmergie: Essai
d’interprétation du comportement des termites constructeurs. Insectes sociaux, v. 6,
n. 1, p. 41–80, 1959.
GREFENSTETTE, J. . G. R. . R. B. . &. V. G. D. Genetic algorithms for the traveling
salesman problem. Proceedings of the first International Conference on Genetic Algorithms and their Applications, p. 160-168, 1985.
GUTIN, G.; PUNNEN, A. P. The Traveling Salesman Problem and Its Variations.
[S.l.]: Springer Science & Business Media, v. 12, 2006.
HARRISON, C.; WIESE, J.; DEY, A. K. Achieving ubiquity: The new third wave. EEE MultiMedia, v. 17, n. 3, p. 8-12, 2010.
HERNÁNDEZ VELA, A. et al. Graph cuts optimization for multi-limb human segmentation in depth maps. In Computer Vision and Pattern Recognition (CVPR),
2012 IEEE Conference on. [S.l.]: IEEE. 2012. p. 726-732.
HILL, R. W.; WYSE, G. A.; ANDERSON, M. Fisiologia Animal. 2. ed. [S.l.]: Artmed
Editora, 2016.
HYNES, A.; CZARNUCH, S. Combinatorial optimization for human body tracking. In International Symposium on Visual Computing, Cham, n. Springer, p. 524-533,
2016.
75
JACKSON, T. Tracking Animal Movement (Animal Trackers). [S.l.]: Capstone
Press, 2015.
JACOBS, R.; CHASE, R. Administração da Produção e Operações: O Essencial.
[S.l.]: Bookman Editora, 2009.
JANSON, C. Death of the (traveling) salesman: primates do not show clear evidence
of multi-step route planning.. American journal of primatology, v. 76, n. 5, p. 410-
420, 2014.
KARA, A. Imitation of Bee Reproduction as a Crossover Operator in Genetic
Algorithms. PRICAI 2004, LNAI 3157, C. Zhang, H.W. Guesgen, W.K. Yeap (Eds.), SpringerVerlag, Berlin Heidelberg, p. 1015-1016, 2004.
KARABOGA, D. An idea based on honey bee swarm for numerical optimization.
Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
KATIYAR, S.; IBRAHEEM, A. Q. A.; ANSARI, A. Q. Ant colony optimization: a tutorial
review. MR International Journal of Engineering and Technology, v. 7, n. 2, p. 35-
41, 2015.
KIM, J. A. S. W. Application of human learning concepts to combinatorial optimization
problems. In Proceedings of the 1997 Annual Meeting of the Decision Sciences Institute. Part 1 (of 3), Decis Sci Inst, 1997.
KOKUBUGATA, H.; MORIYAMA, A.; KAWASHIMA, H. A practical solution using
simulated annealing for general routing problems with nodes, edges, and arcs.
Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Berlin, p. 136-149, 2007.
KRUMM, J. Ubiquitous computing fundamentals. [S.l.]: CRC Press, 2016.
LACH, L.; PARR, C.; ABBOTT, K. (. ). Ant ecology. [S.l.]: Oxford University Press,
2010.
LAPORTE, G. What you should know about the vehicle routing problem, n. 8, p. 811-
819, 2007.
76
LAPORTE, G.; NOBERT, Y. Exact algorithms for the vehicle routing problem. North-Holland Mathematics Studies, North-Holland, p. 147-184, 1987.
LEE, J. A first course in combinatorial optimization. [S.l.]: Cambridge University
Press, 2004.
LEVITIN, A. DESIGN AND ANALYSIS OF ALGORITHMS, 2nd Ed. [S.l.]: Addison-
Wesley Longman Publishing Co, 2006.
LI, Q.; TU, W.; ZHUO, L. Reliable Rescue Routing Optimization for Urban Emergency
Logistics under Travel Time Uncertainty. ISPRS International Journal of Geo-Information, v. 7, n. 2, p. 77, 2018.
LI, Y.; YA, L. I.; WANG, D. Ant colony optimization algorithm based on chaotic
disturbance and neighborhood exchange for vehicle routing problem. Journal of Computer Applications, v. 32, n. 2, p. 444–447, 2013.
LIANGZHI, Z. Vehicle routing problem research based on genetic-ant colony algorithm. IEEE International Conference on Automation and Logistics. [S.l.]: [s.n.].
2008.
LUCIC, P. Modeling transportation problems using concepts of swarm intelligence and
soft computing. PhD diss, Virginia Tech, 2002.
LUCIC, P.; TEODOROVIC, D. Transportation modeling: an artificial life approach.
Tools with Artificial Intelligence, 2002.(ICTAI 2002). Proceedings. 14th IEEE International Conference on, 2002.
LUCIC, P.; TEODOROVIC, D. Computing with bees: attacking complex transportation
engineering problems. International Journal on Artificial Intelligence Tools, v. 12,
n. 3, p. 375-394, 2003.
LYYTINEN, K.; YOO, Y. Issues and Challenges in Ubiquitous Computing.
Communications of The ACM - CACM, v. 45, n. 10, 2002.
MACDONALD, S. E.; WILKIE, D. M. Yellow-nosed monkeys'(Cercopithecus ascanius
whitesidei) spatial memory in a simulated foraging environment. ournal of Comparative Psychology, v. 104, n. 4, p. 382, 1990.
77
MACGREGOR, J. N.; ORMEROD, T. C.; CHRONICLE, E. P. A model of human
performance on the traveling salesperson problem. Memory & Cognition, v. 28, n. 7,
p. 1183-1190, 2000.
MALLIKARJUNA RAO, A.; RAMJI, K.; SUNDARA SIVA RAO, B. S. K. Experimental
Investigation on Navigation of Mobile Robot Using Ant Colony Optimization,
Singapore, 2018.
MANDAL; KUMAR, J. Handbook of research on natural computing for optimization problems. [S.l.]: IGI Globa, 2016.
MANGEL, M.; CLARK, C. W. Dynamic modeling in behavioral ecology. [S.l.]:
Princeton University Press, 1988.
MANOME, S.; ASAKA, T. Dynamic Ant Colony Optimization for Routing in Mobile Content Oriented Networks: Case of Moving Request Nodes. Third International
Symposium on Computing and Networking (CANDAR). [S.l.]: [s.n.]. 2015.
MARKOVIĆ, G. Z.; TEODOROVIĆ, D. B.; AĆIMOVIĆ-RASPOPOVIĆ, V. S. Routing
and wavelength assignment in all-optical networks based on the bee colony
optimization. AI Communications, v. 20, n. 4, p. 273-285, 2007.
MENZEL, E. W. Chimpanzee spatial memory organization. Science 182, p. 943-945,
1973.
MILLER, H. J. . &. S. S. L. Geographic information systems for transportation: principles and applications. [S.l.]: Oxford University Press on Demand., 2001.
MIRA, J.; SANCHEZ-ANDRES, J. V. Engineering Applications of Bio-Inspired Artificial Neural Networks. International Work-Conference on Artificial and Natural
Neural Networks, IWANN'99, Alicante, Spain, June 2-4, 1999, Proceedings, Volume
2. [S.l.]: [s.n.]. 1999.
MITCHELL, S. D. Biological complexity and integrative pluralism. [S.l.]:
Cambridge University Press, 2003.
MIYATA, H.; FUJITA, K. Route selection by pigeons (Columba livia) in “traveling
salesperson” navigation tasks presented on an LCD screen. Journal of Comparative Psychology, v. 124, n. 4, p. 433, 2010.
78
MORITZ, R.; SOUTHWICK, E. E. Bees as superorganisms: an evolutionary reality.
[S.l.]: Springer Science & Business Media, 2012.
NAKRANI, S.; TOVEY, C. On Honey Bees and Dynamic Allocation in an Internet
Server Colony. Proceedings of 2nd International Workshop on the Mathematics and Algorithms of Social Insects, Atlanta, Georgia, USA, 2003.
NEUMANN, J. V. The Computer and the Brain. [S.l.]: Yale University Press, 2000.
PAI, G. V. Metaheuristics for Portfolio Optimization: An Introduction Using Matlab.
[S.l.]: John Wiley & Sons, 2017.
PASCHOS; VANGELIS. Concepts of Combinatorial Optimization. [S.l.]: John Wiley
& Sons, Inc, v. 2, 2014.
PASSINO, K. M. Biomimicry for Optimization, Control, and Automation. [S.l.]:
Springer Science & Business Media, 2005.
PLOGER, B.; YASUKAWA, K. Exploring Animal Behavior in Laboratory and Field.
1. ed. [S.l.]: Academic Press, 2002.
POTVIN, J.-Y. A review of bio-inspired algorithms for vehicle routing. Bio-inspired algorithms for the vehicle routing problem, Springer, Berlin, Heidelberg, 2009. 1-
34.
PRINS, C. A simple and effective evolutionary algorithm for the vehicle routing
problem. Computers & Operations Research, v. 31, n. 12, p. 1985-2002, 2004.
QIN, L. et al. Queen-Bee Evolution Based on Genetic Algorithm for Economic Power
Dispatch. UPEC 2004 39th International Universities Power Engineering Conference, Bristol, UK, p. 453-456, 2004.
RAO, N. M. S.; ARUNA, M.; BHUVANESWARI, S. Meta Heuristic Approaches for
Circular Open Dimension Problem. International Conference on Swarm, Evolutionary, and Memetic Computing, n. Springer, Cham, p. 44-54, 2013.
REINELT, G. The traveling salesman: computational solutions for TSP applications.
[S.l.]: Springer-Verlag, 1994.
79
REVAY, P.; CIOFFI-REVILLA, C. Survey of evolutionary computation methods in
social agent-based modeling studies. Journal of Computational Social Science, v.
1, n. 1, p. 115–146, 2018.
RIBENBOIM, P. The little book of bigger primes. [S.l.]: Springer Science & Business
Media, 2004.
RIZZOLI, A. E. Ant colony optimization for real-world vehicle routing problems. Swarm Intelligence, v. 1, n. 2, p. 135–151, 2007.
RUSSELL, S. J.; NORVIG, P. Inteligencia Artificial. 3. ed. [S.l.]: Campus, 2013.
SAA, P.; MOSCOSO-ZEA, O.; LUJAN-MORA, S. Wearable Technology, Privacy Issues. Proceedings of the International Conference on Information Technology &
Systems (ICITS 2018). [S.l.]: Springer International Publishing. 2018.
SANTOS, M. D. S. C. CICLOS HAMILTONIANOS EM GRAFOS. Ciência e Natura, v.
39, p. 595, 2017.
SEELEY, T. The Five Habits of Highly Effective Honeybees. [S.l.]: Princeton
University Press, 2010.
SEELEY, T. D. Honeybee democracy. [S.l.]: Princeton University Press, 2010.
SERAPIÃO, A. B. D. S. Fundamentos de otimização por inteligência de enxames: uma
visão geral. Sba: Controle & Automação Sociedade Brasileira de Automatica, v.
20, n. 3, p. 271-304, 2009.
SINGH, G. B. Fundamentals of Bioinformatics and Computational Biology. [S.l.]:
Springer International Publishing, 2015.
SMUTNICKI, C. Biomimetic optimizers for job scheduling. International Conference on Computer Aided Systems Theory, Springer, Berlin, Heidelberg, p. 195-202,
2011.
SUNG, H. Queen-Bee Evolution for Genetic Algorithms. Electronic Letters, v. 39, p.
575-576, 2003.
80
SØRENSEN, C. E. A. Designing Ubiquitous Information Environments: Socio-
Technical Issues and Challenges: IFIP TC8 WG 8.2 International Working Conference.
[S.l.]: Springer Science & Business Media, 2005.
SZWARCFITER, J. L. Teoria Computacional de Grafos: os Algoritmos. [S.l.]:
Elsevier Brasil, 2018.
TANG, S. L. Linear Optimization in Applications. [S.l.]: [s.n.], 1999.
TAVARES, J.; BAPTISTA, P. F. Bio-inspired Algorithms for the Vehicle Routing Problem. Studies in computational Intelligence. ed. [S.l.]: Springer, v. 161, 2009.
TAYLOR, G. D. Logistics engineering handbook. [S.l.]: CRC press, 2007.
TEICHROEB, J. A.; SMELTZER, E. A. Vervet monkey (Chlorocebus pygerythrus)
behavior in a multi-destination route: Evidence for planning ahead when heuristics fail.
PloS one, v. 13, n. 5, 2018.
TEODOROVIC, D. E. A. Bee colony optimization: principles and applications. Neural Network Applications in Electrical Engineering, 2006. NEUREL 2006. 8th Seminar on, IEEE, p. 151-156, 2006.
TEODOROVIC, D.; DELL'ORCO, M. Bee colony optimization - a cooperative learning
approach to complex transportation problems. Proceedings of the 10th EWGT Meeting and 16th Mini-EURO Conference, 2005.
TOTH, P.; VIGO, D. The vehicle routing problem. [S.l.]: Society for Industrial and
Applied Mathematics, 2002.
TOTH, P.; VIGO, D. Vehicle Routing: Problems, Methods, and Applications. Second
Edition. ed. [S.l.]: [s.n.], 2014.
VASANT, P. M. Meta-heuristics optimization algorithms in engineering, business, economics, and finance. [S.l.]: IGI Global, 2012.
VIGO, D. Vehicle routing: problems, methods and applications. Society for Industrial and Applied Mathematics, 2015.
WAJNBERG, E. E. A. Optimal patch time allocation for time-limited foragers.
Behavioral Ecology and Sociobiology, v. 60, n. 1, p. 1-10, 2006.
81
WANG, Y.-L. et al. A human-computer cooperation improved ant colony optimization
for ship pipe route design. Ocean Engineering, n. Elsevier, p. 12-20, 2018.
WEDDE, H. F.; FAROOQ, M.; ZHANG, Y. BeeHive: An efficient fault-tolerant routing
algorithm inspired by honey bee behavior. International Workshop on Ant Colony Optimization and Swarm Intelligence, Springer, Berlin, Heidelberg, p. 83-94, 2004.
WEISE, T. E. A. Why is optimization difficult? Nature-Inspired Algorithms for Optimisation, Springer, Berlin, Heidelberg, p. 1-50, 2009.
WEISER, M. The Computer for the Twenty-First Century. Scientific American, p. 94-
104, 1991.
WEISER, M. Some computer science issues in ubiquitous computing.
Communications of the ACM, v. 36, n. 7, p. 75-84, 1993.
WILSON, E. O. Behavior of Daceton armigerum (Latreille), with a classification of self-
grooming movements in ants. Bulletin of the Museum of Comparative Zoology,
1962.
YAN, X.-M. H. H. Z.-F. H. A. G. L. A human-machine cooperative approach for
combinatorial optimization problem. In Machine Learning and Cybernetics (ICMLC), 2016 International Conference on, v. 2, n. IEEE, p. 838-843, 2016.
YANG, X.-S. Nature-inspired metaheuristic algorithms. [S.l.]: Luniver press, 2010.
YANG, X.-S. Review of meta-heuristics and generalised evolutionary walk algorithm.
International Journal of Bio-Inspired Computation 3, n. 2, p. 77-84, 2011.
YAO, B. et al. Artificial bee colony algorithm with scanning strategy for the periodic
vehicle routing problem. Simulation 89, v. 6, p. 762-770, 2013.
YE, H. Current and future mobile and wearable device use by people with visual impairments. Proceedings of the 32nd annual ACM conference on Human factors in
computing systems - CHI. [S.l.]: [s.n.]. 2014.
YU, B. Z.-Z. Y. A. B. Y. An improved ant colony optimization for vehicle routing
problem. European journal of operational research, v. 196, n. 1, p. 171-176, 2009.
82
YUEN, S. W.; WU, Y.; HO, S. C. An artificial bee colony algorithm for the capacitated
vehicle routing problem. European Journal of Operational Research 215, n. 1, p.
126-135, 2011.
ZELKHA, E.; EPSTEIN, B. from devices to "Ambient intelligence". Paper present at the Digital Living Room Conference, 1998.
ZHENG, F. An Adaptive Convergence-Trajectory Controlled Ant Colony Optimization
Algorithm With Application to Water Distribution System Design Problems, v. 21, n. 5,
p. 773-791, 2017.
