Janelas horárias no Problema de Roteirização de Veículos (PRV)

No mundo real, cada VRP (Vehicle Routing Problem - Problema de Roteirização de Veículos) tem suas próprias restrições e condições especiais, que dependem das variantes do problema que estão relacionadas ao tipo de indústria e requisitos de negócios, entre outras coisas.

Uma das variantes mais estudadas do problema de roteirização de veículos é aquela que considera janelas de tempo (VRPTW por sua sigla em inglês): definir em que horário é possível fazer ou não uma visita, melhora a gestão e a operação da cadeia de transporte, impactando positivamente a experiência dos clientes que recebem ou enviam um produto.

Cada variante que compõe um PRV acrescenta um certo grau de dificuldade na obtenção de soluções de qualidade (que não são necessariamente exatas, como vimos no artigo anterior). Em particular, a variante Time Window (Janela Horária) reduz significativamente o cálculo de rotas, desafiando a SimpliRoute a desenvolver um novo algoritmo que forneça soluções inteligentes em menos de 15 minutos.

A diminuição da velocidade no cálculo de uma solução de qualidade deve-se principalmente ao processo de verificação que avalia a viabilidade da inserção de um novo cliente na rota (com janela horária própria), sem afetar as entregas daqueles que já foram avaliados e adicionados à essa rota.

Rota Original

Cada novo cliente inserido significa outra rodada de reavaliação da viabilidade de entregas. Esse processo é realizado muitas vezes durante a busca por melhores soluções, o que acaba sendo responsável por uma grande porcentagem do tempo total de execução do algoritmo. Por exemplo, se quisermos calcular o resultado de um problema com 600 entregas e 35 veículos, essa avaliação precisa ser feita cerca de 750 milhões de vezes.

‍Reavaliação por Inserção de Nova Visita

Depois de um trabalho árduo de investigação e discussão em grupo, concluiu-se que para resolver um VRP com a Janela Horária no tempo desejado, você pode seguir a metodologia descrita por Lu & Dessouky (2006), onde é calculado o tempo máximo que um pedido pode atrasar sem afetar as entregas seguintes. Assim, usando tal informação, é possível calcular muito mais rapidamente se, dentro desse intervalo de tempo, for possível inserir uma nova visita à rota. Tomando o mesmo exemplo do parágrafo anterior (600 entregas e 35 veículos), se for aplicada esta estratégia, o número de checagens a serem efetuadas reduz para menos de 100 milhões, o que permite oferecer uma solução da mesma qualidade em um tempo 30% menor.

Para demonstrar como esse mecanismo funciona, suponha que temos uma rota que atualmente recebe ordens dos clientes "1", ..., "7", e queremos ver se é possível inserir o cliente "a" entre os clientes "3" e "4". (na figura, nos balões rosas são mostrados o tempo de espera).

‍ ‍Rota após a inserção de uma nova visita

Digamos que antes de inserir o cliente "a", todos os clientes da rota devem ser atendidos dentro de sua janela de tempo e, em particular, o cliente "4" deve ser às 13:00. Suponha também, que se o cliente "a" for inserido, como agora ele não irá diretamente para o "4" depois de atender o cliente "3", senão ele passará primeiro por "a", o novo horário de chegada no " 4 “ será 13:45. Esse atraso de 45 minutos pode fazer com que o horário de chegada no cliente "4" saia de sua própria janela de horário, mas também pode acontecer que a chegada em "4" não tenha problemas, ou ainda que o atraso faça com que algum dos clientes "5", "6" ou "7" não possa mais ser atendido no prazo.

Neste exemplo, se usarmos a maneira antiga de avaliar a viabilidade para garantir que todas as entregas continuem a atender às janelas de horário após adicionar a entrega "a" à rota, precisaríamos verificar uma por uma as entregas "4", " 5 "," 6 "e" 7. Por outro lado, se usarmos o novo algoritmo, só temos que calcular quanto mais tarde o cliente "4" é alcançado depois de entregar "a", e comparar esse valor com aquele que entrega essa nova metodologia, que corresponde ao tempo máximo que a chegada ao "4" pode ser atrasada sem que esse atraso interfira na janela de horário dos clientes posteriores. Assim, como o atraso é de 45 minutos, sabemos que o cliente não pode ser inserido, já que o balão rosa mostra que o tempo de espera/folga é de apenas 40 minutos, portanto, antes do cliente "4" só pode ser inserido um cliente que provoque um atraso máximo de 40 minutos.

‍ ‍Inserção de nova visita com heurística Lu & Dessouky

Entendemos que o tempo que a nossa plataforma leva para fornecer uma resposta é essencial, portanto, sempre que implementamos qualquer aprimoramento em nossos algoritmos, nosso foco não é apenas entregar rotas com custos menores, mas também manter os tempos de execução razoáveis. Em particular, a maneira como estamos verificando as janelas de horário nos permite manter o tempo de resposta em menos de 15 minutos para operações grandes, e em menos de 1 minuto para operações pequenas. O que estamos procurando é que a otimização de rotas seja rápida, para que os roteadores possam tomar decisões, fazer alterações e finalizar seu planejamento em uma única sessão de trabalho.

É inútil ter o algoritmo mais preciso do mundo se levar 20 dias para entregar uma resposta!

Possa lhe interessar

SimpliRoute planeja e realiza o rastreamento de rotas de entregas, visitas à clientes e serviços técnicos, além de outras operações de campo.

Teste grátis