Problemas de roteamento de veículos com dependência temporal e espacial entre rotas de equipes de campo
Resumo
Esta tese apresenta dois novos problemas de roteamento, ambos com funções objetivo
voltadas para o posicionamento relativo das equipes durante o horizonte de roteamento.
O posicionamento relativo resulta em uma dependência temporal e espacial entre rotas
e é quantificado com uma métrica de dispersão não-linear, projetada para avaliar as distâncias
instantâneas entre as equipes ao longo de um intervalo de tempo. Esta métrica
permite a concepção de funções objetivo para aproximar as equipes durante a execução
das rotas, quando minimizada, ou para dispersá-las, quando maximizada. Tanto a aproximação
quanto a dispersão são características importantes de roteamento em algumas
aplicações práticas, e dois novos problemas de otimização são propostos com esses objetivos
opostos. O primeiro é uma variação do Problema de Múltiplos Caixeiros Viajantes,
e seu objetivo é encontrar um conjunto de rotas em que os caixeiros viajam próximos uns
dos outros, minimizando a dispersão. Um Algoritmo Genético com Busca Local é proposto
para resolver o problema. Ele inclui operadores genéticos e vizinhanças especializados.
Um novo conjunto de instâncias é proposto, adaptado para o novo problema de instâncias
da literatura. Resultados computacionais mostram que a abordagem proposta proporciona
soluções com as características desejadas de dispersão mínima. O segundo problema é
um problema de roteamento de arcos biobjetivo em que as rotas devem ser construídas de
modo a maximizar o lucro recolhido e o distanciamento entre as equipes. A maximização
da métrica promove a dispersão das equipes durante a execução das rotas. Normalmente,
os objetivos de lucro e dispersão são conflitantes, e com uma abordagem biobjetivo o tomador
de decisão é capaz de avaliar a troca entre a coleta de lucros e a dispersão de equipes.
Dois métodos de solução são propostos, um Algoritmo Genético Multiobjetivo e um
Algoritmo Genético Multiobjetivo com Busca Local, ambos especializados para explorar as
características do problema. É demonstrado, por meio de experimentos computacionais
sobre um novo conjunto de instâncias, que a abordagem proposta fornece conjuntos de
aproximação com as características desejadas.