Como SimpliRoute Resolve o Problema de Roteirização de Veículos.

O Problema da Roteirização de Veículos

O problema de rotas de veículos, conhecido como VRP por sua sigla em Inglês, é um problema de otimização complexo que visa minimizar os custos de transporte associados com rotas de entregas.

Quão complexo é resolver um VRP depende de diferentes recursos ou restrições que devem ser considerados para resolver alguns problemas. Existem algumas variantes de VRP:

• VRP com frota heterogênea: quando veículos da frota são diferentes.
• VRP com rotas abertas: os veículos não voltam para o ponto de partida.
• VRP com janelas de tempo: os pedidos devem ser entregues dentro de um intervalo de tempo pré-definido.
• VRP com pick-up e entrega: os veículos, como parte de seu percurso, tem que passar em centros de abastecimento para carregar os pacotes a serem distribuídos.

Mesmo com todo o avanço tecnológico atual, a alta complexidade de VRPs não permitiu encontrar soluções exatas em horários razoáveis, classificando o VRP dentro de NP-hard  (tempo polinominal não determinístico de difícil/alta complexidade). Diante disso, esses problemas são resolvidos usando heurísticas ou algoritmos visando encontrar a melhor solução possível em um tempo limitado.

‍

A solução que a SimpliRoute fornece ao seu VRP

O objetivo principal da SimpliRoute é fornecer para todas as empresas que necessitam resolver os seus próprios VRP, um plataforma on-line de fácil uso para planejar rotas eficientes em menos de 15 minutos.

A solução que a SimpliRoute propõem é baseada em um algoritmo poderoso, que é submetido a melhorias contínuas após longos processos de pesquisa e desenvolvimento, integrando a literatura acadêmica mais recente na área e a própria formulação de novas estratégias para melhorar a solução do VRP .

Hoje SimpliRoute fornece soluções de qualidade para 7 variantes de VRP, que podem ocorrer de forma única ou como uma mistura entre elas, que inclui:

• Capacidade de Carga: os veículos têm uma capacidade limitada de carga, seja em peso ou em volume. Diante disso, as rotas só se tornam viáveis se cada veículo comportar a carga a ser distribuída ao longo de sua rota.
• Frota Heterogênea: os veículos disponíveis para a distribuição podem ter características diferentes. Por exemplo, eles podem ser de tamanhos diferentes (diferentes capacidades), iniciar a rota e terminar em lugares diferentes, possuir diferentes horários de trabalho, etc.
• Rotas Abertas: é possível definir uma rota com um ponto final para cada veículo (pode ser o mesmo que o inicial, ou outro), ou permitir que o algoritmo decida qual é o melhor lugar para deixar o veículo uma vez que o percurso for finalizado.
• Áreas Geográficas: algumas empresas necessitam, pela natureza do seu negócio, atribuir seus veículos para determinadas áreas geográficas. Dada esta necessidade, SimpliRoute têm integrado dentro de  suas funcionalidades a opção de atribuir à um veículo uma ou mais zonas, e também vários veículos na mesma área.
• Habilidades Especiais: algumas visitas/entregas têm características especiais, fazendo com que somente alguns(m) veículos possam realizar essas entregas, e o sistema  SimpliRoute pode indicar esta relação através de “habilidades”. Se um pedido é marcado com uma habilidade especial, apenas veículos com tal habilidade associada  poderão realizar essa entrega/visita.
• Prioridades: com SimpliRoute é possível trabalhar de forma especial entregas consideradas "mais importantes". Por exemplo, é possível garantir que os clientes marcados como prioridade não sejam deixados de fora da rota de entrega quando não for possível entregar todas as encomendas (seja por limitações de tempo, capacidade ou outros motivos).
• Janela de Horário: alguns clientes podem ser visitados apenas em um determinado horário, de modo que o algoritmo da SimpliRoute foi concebido para ser capaz de integrar essas informações antes de gerar as rotas.

O algoritmo inicia com uma solução inicial viável, que é então comparada com uma outra solução viável. Entre as 2 soluções, é escolhida aquela com os melhores resultados, ou seja, qual melhor otimiza os objetivos definidos  (LocalSearch).

Este processo é repetido milhares de vezes até encontrar a solução mais próxima possível do ideal, respeitando todas as condições que foram estabelecidas tanto para os veículos quanto para os pontos a serem visitados (variantes).

Com o algoritmo SimpliRoute é possível resolver VRPs para uma frota de 100 veículos e 2.000 clientes em menos de 15 minutos. Mas o desafio não termina aí: SimpliRoute está testando técnicas novas e inovadoras para reduzir o tempo de cálculo para menos de 5 minutos, além de entregar soluções mais personalizadas para operações específicas que necessitam de optimização.

Se você se interessar em aprender mais sobre este assunto, um bom resumo de métodos de resolução de VRPs são esses dois trabalhos de Braysy e Gendreau:

Roteamento de Veículos Problema com Windows Time, Part I: Route Construção e Local Search Algoritmos

Roteamento de Veículos Problema com Windows Time, parte II: Metaheurísticas