Introdução
Há pelo menos três anos venho usando uma solução proprietária para roteamento, as ferramentas de Networking da Esri são bem completas e permitem uma série de configurações finas como sentido de via, retornos, roteamento multimodal e afins, claro que montar uma base assim demandada muito tempo e esforço continuo. No meio do caminho também pude olhar uma série de opções de roteamento, seja por soluções 'completas' de ponta-a-ponta em plataformas variadas, ou API's de roteamento, existe uma série dessas duas opções no mercado, já que logística sem dúvida é algo que custa muito caro para as companhias. Hoje posso agregar os três grandes problemas dessas soluções em desempenho, controle e custo.
Desempenho, no sentido de que conseguir agregar uma quantidade massiva de dados, em alto nível de detalhe e com agilidade para atender a cadeia de suprimentos (Supply Chain). Controle, no sentido de poder alterar características estratégicas do funcionamento do roteamento ou da base fonte para conseguir prospectar cenários estratégicos. E por fim custos de licenciamento de plataformas e desenvolvimentos relacionados.
É muito difícil encontrar uma solução que atenda um cliente complexo como o do mercado florestal nesses três pilares, a extensão de Networking da Esri oferece um controle intermediário possiblidades de analise ótimas e pode-se configurar muita coisa, mas é uma caixa preta que não se integra com outros sistemas diretamente, o que afeta também o desempenho em relação aos processos, e por fim ainda existe o custo de licenciamento. Por conta dessas questões resolvi iniciar uma busca por soluções de roteamento que tentassem abastecer essas três demandas em algum nível.
Nesse post você irá ver a construção de um protótipo Open Source baseado em Python que tentará criar os primeiros moldes de um modelo de roteamento que consiga atender as três demandas desse tipo de solução.
Bibliotecas
As bibliotecas usada nesse projeto foram as seguintes;
#Essas para manipular os dados
import geopandas as gpd
from shapely.geometry import LineString, mapping
from shapely.ops import linemerge
import pandas as pd
#Essas para roteamento
import osmnx as ox
import taxicab as tc
#Essas para visualização
import matplotlib.pyplot as plt
from ipyleaflet import *Carregando os dados
As suas principais bibliotecas para esse projeto são a Taxicab e a OSMnx, sendo a primeira derivada da segunda e as duas derivadas da biblioteca de analise de rede NetworkX. A biblioteca OSMnx é focada na analise de redes dos dados do Open Street Maps, inclusive é através dela que iremos baixar nossa base de dados inicial. Existe uma gama enorme de opções de download de dados através da OSMnx, neste projeto optei por fazer o download através do raio em relação a um ponto em especifico.
#Localização
location = (-20.819077,-51.8050747)
raio = 25000 #Em metros
mode = "drive" #Modo de roteamento
#Pegas as informações de estradas OSM do raio especificado e põe em
#um sistema de rede
G = ox.graph_from_point(location,
dist=raio,
simplify=True, #Simplifica a geometria do download
network_type=mode)
#Geodataframe dos nós e das arestas
nodes_proj, edges_proj = ox.graph_to_gdfs(G, nodes=True, edges=True)
Roteando com a biblioteca Taxicab
Para rotear coma biblioteca Taxicab é simples, a função tc.distance.shortest_path após receber pontos de origem e destino retorna uma lista com respectivamente;
Distância em metros da rota
Lista de nós
geometria do começo da rota
geometria do fim da rota
origin_point = (-20.797642,-51.8887437)
destination_point =(-20.813228, -51.730378)
route_tc = tc.distance.shortest_path(G, origin_point, destination_point)
route_tc
A biblioteca OSMnx também tem uma função de distâncias porém considera os pontos de origem e destino os nós mais próximos. Basicamente a função get_nearest_node tem como retorno uma lista de nós assim como a função do Taxicab tc.distance.shortest_path, porém sem os outros detalhamentos.
Inclusive foi essa falta de detalhamento uma das motivações do autor da biblioteca. A imagem abaixo que vem direto da documentação do Taxicab e exemplifica bem essa questão.
O roteamento com a biblioteca OSMnx funciona da seguinte maneira.
#Busca os nós mais próximos das coordenadas indicadas
origin_node = ox.get_nearest_node(G, origin_point)
destination_node = ox.get_nearest_node(G, destination_point)
#Busca a lista de nós entre os dois nós indicados
route_nodee = ox.shortest_path(G,
origin_node,
destination_node,
weight='length')
#Mostra lista de nós
route_nodee
Para poder ver as geometrias montei uma função que dada uma lista de nós, retorna uma lista coordenadas que compõe as linhas. Adaptei essa função do blog do Apurv Priyam.
def node_route(G, node_list):
edge_nodes = list(zip(node_list[:-1], node_list[1:]))
lines = []
for u, v in edge_nodes:
# se houver arestas paralelas, selecione o menor em comprimento
data = min(G.get_edge_data(u, v).values(), key=lambda x: x['length'])
# se tiver um atributo de geometria (ou seja, uma lista de segmentos de linha)
if 'geometry' in data:
# adicione-os à lista de linhas para plotar
xs, ys = data['geometry'].xy
lines.append(list(zip(xs, ys)))
else:
# se não tiver um atributo de geometria, a aresta é reta
# linha de nó a nó
x1 = G.nodes[u]['x']
y1 = G.nodes[u]['y']
x2 = G.nodes[v]['x']
y2 = G.nodes[v]['y']
line = [(x1, y1), (x2, y2)]
lines.append(line)
lat = []
long = []
for i in range(len(lines)):
z = list(lines[i])
l1 = list(list(zip(*z))[0])
l2 = list(list(zip(*z))[1])
for j in range(len(l1)):
lat.append(l2[j])
long.append(l1[j])
df = pd.DataFrame({
'Latitude': lat,
'Longitude': long})
gdf = gpd.GeoDataFrame(df, geometry=gpd.points_from_xy(df.Longitude, df.Latitude))
return gdf
node_route(G,route_nodee)
Na sequência crio duas funções, para retornar a geometria e a distância dos roteamentos feitos com Taxicab e OSMnx .
def routing_Taxicab(G,origin_point,destination_point):
route = tc.distance.shortest_path(G, origin_point, destination_point)
shortest_path_points = node_route(G, route[1]) #Reutilizo a função que pega o GeoDataframe da lista de nós
x = linemerge((LineString(shortest_path_points.geometry.values),route[2],route[3]))#Aqui junto todas a geometrias
geo = gpd.GeoDataFrame([x], columns=['geometry'])#transformo em um GeoDataframe com a linha inteira
dist = route[0]
path = [dist,geo]
return path
def routingOSMNX(G, edges, origin_point,destination_point):
origin_node = ox.get_nearest_node(G, origin_point)
destination_node = ox.get_nearest_node(G, destination_point)
node_list = ox.shortest_path(G,
origin_node,
destination_node ,
weight='length')
route_node1 = node_route(G,node_list)
#transformo em um GeoDataframe com a linha inteira
geo = gpd.GeoDataFrame([LineString(route_node1.geometry.values)],
columns=['geometry'])
x = 0
edges_proje = edges.reset_index()
for i in range(len(node_list)):
if node_list[i] == node_list[-1]:
break
else:
y = edges_proje['length'][edges_proje['u']==node_list[i]]
[edges_proje['v']==node_list[i+1]]
x = x+y.values[0]
output = [x,geo]
return output
As distâncias para cada método foram de 17.2 KM no Taxicab e 15.9 KM no OSMNX.
#Rota Taxicab
route_Taxicab = routingTaxicab(G,origin_point,destination_point)
#Rota OSMnx
route_OSMNX = routingOSMNX(G,edges_proj ,origin_point,destination_point)
Como puderam ver na imagem anterior o roteamento da biblioteca Taxicab é mais preciso, montei também uma visualização dinâmica que usa a função que montamos acima para calcular a rota mais curta entre dois pontos no mapa. Você pode encontrar o código que monta essa visualização junto com todos os outros no repositório do projeto.
Conclusões
Até aqui conseguimos montar um protótipo Open Source para roteamento que roda em Python e utiliza metodologias Open Source, ou seja, sem custos.
Quanto ao controle da base e demais configurações, existe uma série de funções que podem ajudar em como essa rotas são feitas, inclusive podemos subir nossa própria base de rotas, armazenar em cache e outras coisas, porém vou deixar para próximos posts.
Quanto ao desempenho há ressalvas, a primeira delas é que embora a biblioteca Taxicab seja mais precisa ela tem menos desempenho do que o método que usa o OSMnx, no comparativo que fizemos nesse post dentro do ambiente de Colab do Google (Que é uma maquina virtual até que parruda) os tempos de execução foram de 7 segundos para Taxicab e 0,5 para a OSMnx. Parece pouco, mas em um cenário de analise de 100 rotas isso seria 13 minutos de processamento para o Taxicab e 50 segundos para a OSMnx.