Lucas Diogo

Posted on Mar 24, 2022

Desmistificando roteirizações com Python

#python #datascience #routing #advanced

Desmistificando roteirizações com Python

Uma abordagem completa de como otimizar sua frota.

Atualmente nos Estados Unidos, estima-se que exista 1,2 milhões de empresas de transporte rodoviário responsáveis por cerca de 70% do frete anualmente no país, representando US$ 671 bilhões em mercadorias transportadas por caminhões. Esse segmento levanta uma receita total de aproximadamente 255 bilhões de dólares.

Uma frota de caminhões pode passar por diversos postos de coletas/entregas diariamente, e para isso existe um conceito chamado roteirização, que serve basicamente como um mapa logístico que define o caminho que cada motorista irá percorrer para cumprir o seu objetivo e traz diversos benefícios como:

Redução de custo: Indicando o caminho mais curto a se fazer no dia, economizando combustível e distância percorrida, podendo reduzir até 20% nos custos de entrega.

Aumento de produtividade: Traz melhor visibilidade na distribuição de pontos de coleta para cada veículo fazendo com que a não haja discrepância em distâncias, por exemplo, ao invés de deslocar um caminhão X para atender o ponto Y que está 1000 KM de distância, o caminhão Z a 100 KM será designado para atender o ponto Y pois está mais perto, podendo até mesmo aumentar o número de entregas no mês.

**Satisfação do cliente: **Quanto mais otimizado for o processo de deslocamento na cadeia de suprimentos até chegar ao cliente final, mais satisfeito ele estará por receber sua mercadoria rápido.

Após uma breve introdução, antes de partirmos para a parte prática, precisamos conhecer os problemas computacionais que envolvem a construção do nosso roteirizador.

Quando falamos de otimização de rotas, temos como referência o Vehicle Routing Problem (VRP) e o Travelling Salesman Problem (TSP).

TSP (Travel salesman problem)

O travel salesman problem, também conhecido por “O problema do caixeiro viajante” é um dos problemas mais conhecidos na área de ciência da computação e pesquisa operacional.

Consiste em, dado um conjunto de cidades e suas posições, o problema é encontrar o caminho mais curto para que cada cidade seja visitada apenas uma vez e, finalmente, retorne ao ponto de partida.

No entanto, a medida que o número de destinos aumenta, o número correspondente de combinações de viagens de ida e volta pode exceder a capacidade de até mesmo computadores com grande poder de processamento, pois com 10 destinos o número de cálculos pode chegar a 300.000 combinações, já com 15 destinos pode ultrapassar 87 bilhões.

VRP (Vehicle Routing Problem)

No problema de VRP, ou também conhecido “Problema de roteamento de veículos”, o objetivo é encontrar rotas otimizadas para vários veículos que visitam um conjuntos de localizações (quando é somente um veículo o problema é o TSP), considerando restrições específicas do negócio como, limitações de veículos, recursos, janela de tempo entre outros. Esse problema possui outras variantes que não iremos abordar no nosso exemplo, mas que são facilmente extensíveis para implementação.

São elas as mais famosas:

Vehicle Routing Problem with Time Windows (VRPTW): Os locais de entrega têm janelas de tempo dentro das quais as entregas (ou visitas) devem ser feitas.
Capacitated Vehicle Routing Problem: CVRP or CVRPTW. Os veículos têm uma capacidade de transporte limitada das mercadorias que devem ser entregues.
Vehicle Routing Problem with Multiple Trips (VRPMT):Os veículos podem fazer mais de uma rota.
Open Vehicle Routing Problem (OVRP): Os veículos não são obrigados a retornar ao depósito.
Inventory Routing Problem (IRP): Os veículos são responsáveis por atender as demandas em cada ponto de entrega.
Multi-Depot Vehicle Routing Problem (MDVRP): Existem vários depósitos a partir dos quais os veículos podem começar e terminar.

A otimização é baseada em uma abordagem heurística que não garante a solução perfeita, porém, se bem configurada, pode nos fornecer ótimas soluções em pouco tempo.

Agora iremos para a melhor parte, e ao decorrer da implementação irei me aprofundando em alguns conceitos.

O nosso exemplo irá se basear em VRP e terá como premissa 6 veículos que deverão visitar todos os 49 estados americanos (o Havaí e o Alaska não estão na lista, pois são possíveis outliers já que estão muito distante dos demais).

Como requisito, necessitaremos das bibliotecas listadas abaixo, a instrução de instalação das mesmas pode ser encontrado nos links.

Após instalado os pacotes necessários, em nosso notebook jupyter iremos importa-los como mostrado abaixo.

Após a importação das nossas bibliotecas , será necessário a obtenção dos dados dos nossos pontos de visita e dos nossos veículos.

Basicamente nesse trecho de código fizemos o seguinte:

Linha 2 : Importamos os dados contendo a informação de latitude e longitude de todos os estados americanos usando pandas.

Linha 5: Removemos os nossos estados “outliers” no caso Alaska e Havaí por serem muito distante dos demais.

Linha 8: Criamos os dados dos seis veículos contendo somente nome e placa.

13 a 22: Utilizaremos 6 estados americanos randomicamente para ser o nosso ponto de partida e chegada dos nossos veículos e adicionamos a informação de latitude e longitude ao dataframe. Os dados amostrados como ponto de partida retiramos do dataset de estados americanos pois teoricamente os veículos já estarão partindo deles então não é necessário uma visita, o que restará 6 veículos e 43 pontos de visitas.

Os nossos dados ao final terão o seguinte formato:

Após a obtenção dos dados entraremos na etapa de pré-processamento, ou seja, iremos realizar o tratamento necessário em nossos dados antes de processa-los.

Mas antes disso, explicarei como é feito o processo de otimização por baixo dos panos.

1- Calculamos as distancias de todas as localizações envolvidas no processo e envolvendo também os pontos de partida e chegada e isso pode ser feito através de uma matriz de distâncias.

A matriz de distancias é uma matriz bidimensional que contem todas as distancias correlacionadas.

Suponha que você tenha 5 locais A, B, C, D e E, então a matriz de distância consiste em todas as 20 distâncias (5*5–5)

No nosso exemplo temos 55 locais (6 locais de partida, 6 locais de chegada,43 pontos de visita) ou seja, uma matriz de 2.970 combinações.

2- Com base na matriz, os pontos de visita são atribuídos aos veículos, que em seguida para cada veículo no problema, é atribuída uma rota de modo que a função objetivo especificada seja minimizada. É usado então uma heurística com base no vizinho mais próximo (NNS) que combina elementos de algoritmos de recozimento simulado e de aceitação de limiar.

Funciona da seguinte maneira:

Partindo de uma solução inicial, a mesma é quebrada em várias partes onde obtemos:
Um conjunto de pontos de visita que não são mais atendidas por um veículo.
Solução parcial contendo todas as outras entregas.
Com base na solução parcial, todas os pontos de visita do conjunto são incluídos novamente, gerando uma nova solução. Se a nova solução for boa, ela é aceita como a nova melhor solução quando uma nova iteração de recriação é iniciada. Essas etapas são repetidas várias vezes até que um determinado critério de término seja atendido, por exemplo: Tempo de processamento ou número de iterações

Linha 1 a 17: Aqui criei um método onde separo todos os dados de geolocalização (latitude e longitude) em partida, chegada, pontos de visita e por último, uma contendo todas as geolocalizações, que será necessário para montar nossa matriz de distâncias. Note que na linha 15 é utilizado a função do Numpy radians onde contém todas as localizações. Isso serve para normalizar os nossos dados e ter uma melhor desempenho no cálculo.

**Linha 21 a 27: **Aqui é apenas um método para montar um DTO contendo algumas informações para passarmos para o nosso método que será responsável por processar a o problema e nos entregar uma solução.

**Linha 30 a 32: **Aqui é onde utilizamos as nossas coordenadas para criar a matriz de distâncias utilizando a classe DistanceMetric, onde é possível selecionar o tipo de métrica para a construção dessa matriz.

Em ciência de dados existem várias formas de calcular distâncias, por exemplo: em linha reta (euclidiana), em curvatura como um globo (haversine) entre outras. Todas elas possuem uma fórmula matemática diferente para serem calculadas e ao todo são 9. Para saber mais você pode clicar aqui.

Na etapa de processamento vamos utilizar o Google OR-Tools que será responsável por definitivamente resolver o problema de VRP.

A implementação desse método você encontra na documentação da própria biblioteca.

Porém, irei comentar sobre alguns parâmetros usados que valem como ponto de atenção.

Linha 5: *Nessa linha note ser passado por parâmetro os *dados que pré processamos anteriormente para o método RoutingIndexManager do OR Tools.

**Linha 40: **Já aqui é definido o limite de tempo em segundos que será gasto no processamento, pois como comentado anteriormente, será realizado vários ciclos em busca procurando pela melhor solução para o problema, e quanto mais elementos temos, mais pesado é o processamento logo, definir um tempo limite é importante.

Linha 43: Esse parâmetro é utilizado para visualizarmos os logs para entendermos melhor como está sendo realizado o processo dessa busca da solução. Se olharmos atentamente aos logs veremos algumas informações como o número de soluções geradas, tempo, ramificações, memória utilizada para gerar a solução entre outras…

Observação: Note ser utilizado cerca de 200 MB de memória para cada solução gerada.

**Linha 51: **O número passado como parâmetro é a distância máxima (em milhas) que cada veículo poderá percorrer em cada rota.

Ao final do processamento teremos já o VRP resolvido com as rotas definidas para cada veículo. Após isso precisamos estruturar a resposta, ou seja, realizar um pós processamento.

Linha 3: O método MapResult será responsável por converter a resposta obtida no processamento para dados estruturados, retornando assim, uma lista de dataframes, onde cada um possuirá a rota de um veículo.

Linha 58: Através do uso de índices e dos dados originais, esse método é responsável por mapear para dataframe.

Linha 82: A medida que o OR Tools utiliza é milhas, aqui definimos uma pequena função para a nossa resposta sair em quilômetros.

Linha 87 a 90: Caso o processamento não tenha sucesso em sua busca pela solução do problema, é definido uma mensagem de falha e encerramento do fluxo, caso contrário realizaremos o pós processamos da nossa resposta.

Linha 93: Aqui concatenamos todas os dataframes para termos a visão completa da roteirização realizada, e esse é o resultado:

Se observarmos os dados atentamente, a primeira e ultima linha de cada veículo será o mesmo local, pois representam o local de partida e chegada respectivamente.

E para fechar com chave de ouro, vamos criar um método para visualizar essa distribuição no mapa.

Para fazer isso, utilizarei o MapBox para trabalhar com dados de geolocalização. Siga os seguintes passos:

1- Crie uma conta na plataforma clicando aqui .

2- Após logar, na aba Tokens, crie um novo token

3- Copie o token gerado e cole, atribuindo o token a variável mapbox_token.

E finalmente:

Cada cor representa um veículo, e as numerações são as ordens de quais pontos devem ser visitados.

Podemos ir ainda mais além na nossa visualização e utilizar por exemplo uma API de directions para desenhar a rota no mapa.

O código completo pode ser encontrado aqui no meu Github:
GitHub — LucasDiogo96/Routing-Optimizer: This solution was written in python and is based on the…

Um planejamento efetivo de rotas é primordial para qualquer empresa de entregas. Mais que definir uma sequência de entregas, é necessário elaborar um planejamento realista considerando as principais variáveis do negócio.

Para garantir a efetividade é preciso investir em dois quesitos fundamentais: tecnologia e planejamento. Justamente por unir ambas que o *roteirizador *é tão importante, e acaba se tornando a peça chave para estar à frente dos concorrentes e manter a competitividade no mercado.

Até a próxima !!!