GEO LOGOS – 2021

1 Caixeiro viajante: Rota Multiponto

Dado um conjunto de pontos a serem visitados (clientes) e um ponto de partida, o problema do caixeiro viajante tem como objetivo determinar a seqüência ótima, que minimizará o custo total da rota, na qual os clientes são visitados uma única vez.

O problema do caixeiro tem diversas aplicações, tais como reabastecimento de alimentos ou de drogarias a partir de um ponto de distribuição central; otimização do trajeto de caminhões de entrega ou de coleta, etc.

Numerosos métodos foram propostos para resolvê-lo. Encontrar a rota ótima para um problema particular não tem sido prático para problemas que contém muitos pontos, na prática acima de 20 clientes. O tempo computacional de solução é demasiadamente alto para problemas reais. Os procedimentos heurísticos (algoritmos aproximados) de solução têm sido boas alternativas, entre eles o 2-opt (vários filtros) e heurística de inserção mais distante. Esses procedimentos apresentam bons resultados com um tempo computacional bastante reduzido.

2 Roteamento de Veículos

Roteamento de veículos (PRV) ou roteirização consiste em definir roteiros que minimizem o custo total de atendimento, cada um iniciando e terminando no depósito/Garagem, assegurando que cada ponto seja visitado exatamente uma vez e nenhuma restrição seja violada. Uma condição básica a ser considerada é que a demanda em qualquer rota não exceda a capacidade do veículo que a atende.

Existem extensões para o problema de roteamento. Dentre elas pode-se citar o problema de roteamento com janela de tempo, onde se deve respeitar um horário específico de entrega. Existe também o problema de coleta e entrega, onde existem pontos onde se deve fazer coleta de alguma mercadoria, e outros onde se deve fazer entregas.

Em vez de considerar um único ponto de partida (depósito), existe a alternativa de partir de vários depósitos, logo o algoritmo deve estabelecer de qual depósito cada veículo deve partir, a fim de minimizar o custo total das rotas. Há uma tendência das empresas de transporte em utilizar veículos com multi-compartimentos, logo a restrição de cubagem de cada compartimento, bem como o tipo de produto que pode ser alocado, deve ser respeitada.

O problema de roteirização de veículos é bastante aplicado em empresas de distribuição e transporte de cargas. Algumas dessas empresas chegam a ter que roteirizar milhares de clientes por dia, e possuem uma frota considerável de veículos de diversas capacidades e custos. Encontrar a solução exata para esses problemas é praticamente impossível para problemas reais, logo a utilização de heurísticas se faz necessária,

A aplicação dos problemas citados requer a utilização de diversas informações, dentre elas a localização espacial dos clientes e a localização geográfica da rede de vias, sejam rodovias ou vias urbanas. A utilização de eixos de logradouros como base cartográfica é de vital importância para resolver problemas de roteirização, devido aos atributos de conectividade e direção. Sem falar que os limites de numeração e o nome do trecho da via), contidos nessas bases, permitem a localização espacial dos clientes, através de procedimentos de busca de endereço.

Exemplo:

Circuito – Caixeiro Viajante

Seqüência de pontos de coleta ou entrega no cadastro do cliente sem a preocupação de orientação otimizada, ou seja seqüencia de paradas com objetivo de menor caminho e tempo entre todos os pontos.

Sequência de pontos orientados no formato de circuito Horário

Aplicação do algoritmo do Caixeiro Viajante apenas no formato de um circuito.

Sequência de pontos orientados no formato de circuito Anti-Horário

Aplicação do algoritmo do Caixeiro Viajante apenas no formato de um circuito.

OBS: O objetivo do algoritmo não contempla a menor distancia entre todos os pontos, mas apenas a criação de circuito horário ou anti-horário. A vantagem desse algoritmo, mesmo havendo  um número muito elevado de pontos (clientes), a  nova ordenação é criada rapidamente, ou seja, um tempo computacional muito baixo. Se houver vários setores de entrega ou coleta com milhares de pontos (clientes), e se deseja construir  um  circuito de menor custo (distancia/tempo),  dentro de um tempo determinado, talvez essa seja a única saída possível.  

A busca da sequência no formato de circuito horário inicia na triangulação entre os pontos, e a escolha das arestas extremas  de menor distancia entre os pontos, circundando o polígono gerado pela triangulação.