Normalizacion + Geocode + Ruteo con Geopy & OR Tools.
En la empresa en la que actualmente me desenvuelvo (Logística), se buscaba encontrar la ruta mas eficiente para que los repartidores llegaran a todos sus destinos del día.
Muchas veces la experiencia de transportistas con muchos años en el rubro y/o en una zona determinada, generam un KnowHow muy particular, con el que entendimos desde el principio que iba a ser difícil de competir, sin embargo no nos podemos permitir +10 años de entrenamiento, para decir que probablemente, estemos usando la ruta mas optima en la mayoría de los casos.
Sin mas preámbulos, saltamos a buscar la solución del problema. El primer approach fue leer la info disponible, sobre la solucion matematica del problema. El problema en cuestión lleva el nombre de “Travelling Salesman Problem” Donde lo que se busca es el camino mas corto para que un vendedor de estados unidos, recorra el país, consumiendo la menor cantidad de recursos. El highlight del problema es el siguiente:
- El problema es NP-Hard. Lo que significa que la cantidad de resultados que necesitamos estudiar, para encontrar un optimo absoluto, esta dado por n! donde n son la cantidad de lugares a visitar. Por lo que buscar por fuerza bruta, es computacionalmente muy caro.
Para 8 destinos => 40.320
Para 16 destinos => 20922789888000Una vez que estamos interiorizados, aunque sea de manera superficial, en el problema y en sus posibles soluciones, nos arremangamos y nos hacemos cargo.
Recepcion de datos y normalización de direcciones.
Por empezar, analizamos bien de que manera nos van a llegar los datos, y como vamos a limpiar el archivo para tener únicamente la info que nosotros necesitamos, de la manera mas limpia posible.
Nuestro input es un txt con la siguiente forma:
G000528470 63 PEIRANO 00240 A $0 $0
G0009090 54 Peirano Nro: 273 P: D: 273 A $0 $0
3600040610 3 Moreno 1143 S $0 $0
3000002990 10 Callao 242 S $0 $0
900008126780 58 LOS LAZARISTAS 371 R $0 $0
900000048210 57 LOS LAZARISTAS 371 A $0 $0
3627651690 2 Las Heras 2751 A $0 $0
36007730 20 Mateo Gelves 1245 A $0 $0
25054 6 PASEO DE JULIO 488 S $0 $0
...Esta info nos llega pegada de una tabla, por lo que si quisiésemos divdir manualmente el archivo para que sea un CSV, lo que tendriamos seria:
Numero de envio, peso, direccion, numero, letra, precio,precio
3627651690, 2, Las Heras 2751, ,A, $0, $0- Lo único que necesitamos de esta data es la dirección y el numero. Todo el resto se puede ir. Para esto tenemos en cuenta que el único valor null de la tabla puede ser el campo numero.
- En caso de que el numero no este (Ya que se cargo en el campo dirección), vamos a colocar un 0 para no tener el campo null.
- Todos los números ya sea en dirección o en numero, tenemos que pasarlos a formato int, ya que hay strings donde el numero tiene 0 a la izquierda, y esto atenta contra la geolocalización.
for line in hdr:
###### 1 ########
hdiv = line.split()
hdiv = hdiv[2:]
hdiv = hdiv[:-3]
num = hdiv[-1]
hdiv = hdiv[:-1]
#hdiv = " ".join(hdiv)
num = "".join(num)
###### 2 ########
#Si algun valor de "numero", NO ES UN NUMERO, entonces lo reemplazo por 0.
try:
num = int(num)
except ValueError:
num = 0
###### 3 ########
#Si algun valor de hdiv es numero, que quede como numero. (ELIMINO LOS CASOS EJEMPLO: 0025)
for x in range(len(hdiv)):
try:
hdiv[x] = int(hdiv[x])
except ValueError:
hdiv[x] = hdiv[x]
data.append([hdiv,num])El vector data tendría entonces toda la info cortada de esta manera:
direccion, numero,
PEIRANO, 240,
Las Heras 2751, 0,
Peirano Nro: 273 P: D:, 273,La siguiente tarea es normalizar un poco mas las direcciones, para adaptarse a las particularidades de la región, en este caso Argentina.
- El número de la calle viene después del nombre de la calle, Toda la info después del número de la calle debe ser borrada (departamento, localidad, etc) ##El set de datos, viene por localidad y eso lo colocaremos posteriormente en la direccion ##
- Si tengo un número antes que el nombre de la calle, lo borro. Ya que si esta mal ubicado, igualmente lo tendré en el campo numero. Existe únicamente la excepción donde algunas calles tengan un nombre con numero, generalmente una fecha, por lo que admitiremos números menores a int(35).
- Por ultimo si el campo dirección tiene un numero, lo debo comparar con el numero de la calle, para no repetirlo.
buscar = True
borrar = False
a = 0
b = 0
numindex =0
dire=[]
#Recorro mi vector de data
for i in data:
print(i)
while buscar:
#i[0] contiene la direccion , i[1] contiene el numero
# Si el valor que tomo, es un integer entonces, si es el primero lo borro y si no es el primero, dejo de buscar.
#Si encuentro un numero paro de buscar. (Con la excepcion del primero)
if type(i[0][a]) == int:
if a == 0:
if i[0][a] > 35: #### 2 #####
borrar = True
else:
buscar = True
else:
buscar = False
a = a + 1
#Si en mi vector no hay ningun numero, igual salgo del while
if a >= len(i[0]):
buscar = False
numindex = a #Largo de i[0] (HASTA EL PRIMER NUMERO)
temp = [] #Vector con la direccion final
#Pongo toda la info en el vector temporal (Hasta el primer numero)
for h in range(numindex): ### 1 ###
temp.append(str(i[0][h]))
#Si la direccion empieza con un numero mayor a 35 lo borro
print(borrar)
if borrar == True : #### 2 ####
del temp[0]
#Si el campo numero es disinto de 0 (y del ultimo campo de la direccion) entonces lo agrego a la direccion if i[0][numindex-1] != i[1] and i[1] != 0: ### 3 ###
temp.append(str(i[1]))
#Agrego la info al vector de direcciones y reinicio las variables
print(i[1])
dire.append(" ".join(temp))
buscar = True
borrar = False
a = 0
b = b +1
### Paso todo a un DF para el siguiente programa ###df = pd.DataFrame(data = dire , columns= ["Direccion"])
df.to_csv("DireccionesNomrmalizadas.csv")
Por último tenemos un CSV con el Output de la normalización de la siguiente forma:
, dirección
10,Peirano Nro: 273
11,Moreno 1143
12,Callao 242
13,LOS LAZARISTAS 371
14,LOS LAZARISTAS 371
15,Las Heras 2751
16,Mateo Gelves 1245
17,PASEO DE JULIO 488
...Geolocalización de direcciones.
La geolocalización de direcciones se puede hacer mediante varias API, tanto opensource como pagas, por suerte para evitar la codificación particular de cada una de estas, existe una librería llamada Geopy, que incluye modulos para cada uno de los servicios existentes (Los mas comunes). Esto además de darnos practicidad en la sintaxis, nos permite evaluar que geolocalizador funciona mejor con el set de datos que tenemos nosotros.
En mi caso particular empecé haciendo pruebas con Nominatim, que es el modulo para OpenRouteServices, pero era muy errático entre pequeñas variaciones en la sintaxis de la dirección. Luego de varias pruebas, decidí pasarme a ArcGis, que tiene resultados mucho mas consistentes.
Para entender la lógica utilizada, voy a comenzar explicando que el request por dirección que mando, puede setearse para recibir un único resultado de coordenadas, o varios que tengan una aproximación relativa.
Me resulto conveniente pedir el vector entero con todas las posibilidades y elegir de ese lake de info, el mejor resultado. Lo que realiza el programa ->
- Le entregamos el punto de partida del transportista (Por lo general cada sucursal tiene un area de cobertura)
- Le entregamos la primera dirección a geolocalizar (Agregándole la sucursal y código postal, que viene dado por el set de datos)
- Recibe el json con la información
- Si el primer resultado (El que mas matchea según la API) esta dentro del área de cobertura de la sucursal -> Toma ese valor, lo guarda y pasa a la siguiente geolocalizacion
- En caso contrario, compara la distancia de todos los puntos con respecto a la sucursal y se queda con el mas cercano.
- **Disclaimer: Esto no significa que este punto será el correcto, sin embargo de esta manera es mucho mas fácil y rápido encontrar los puntos mal geolocalizados, ya que al menos estarán mas cerca para buscarlos por el mapa***
6. Por ultimo ploteamos todas las direcciones en el mapa como control.
import folium
from folium.plugins import BeautifyIcon
import pandas as pd
import geopy
from geopy.geocoders import Nominatim
from geopy.geocoders import ArcGIS
import numpy
ubicacion = [ -34.344129, -58.788988] #Escobar
m = folium.Map(location=ubicacion,
zoom_start=12)
geopy.geocoders.options.default_user_agent = "Geoposicionador"
nom = ArcGIS()
def geolocalizar(direccion):
x = nom.geocode(direccion, exactly_one = False)
###Si x me devuelve una lista, entonces...
###### Me fijo si el primer elemento (Que es el most likely to be el correcto) esta dentro de 10 km de la sucursal.
#########En caso de que si, ya me quedo con ese dato y salgo de la subrutina
#########En caso de que no:
############Agarro cada elemento de la lista (Unicamente si tienen mas de 20 chrs (o sea que son direcciones)), y me fijo su distancia a la sucursal
############Guardo en un vector de distancias y me quedo con la mas cercana.
print(x)
contlat = ubicacion[0]
conlong = ubicacion[1]
Areacobertura = 0.1
Analisis = True
if x:
n = 0
if float(x[n].latitude) < (contlat + Areacobertura) and float(x[n].latitude) > contlat - Areacobertura:
if float(x[n].longitude) < (conlong+Areacobertura) and float(x[n].longitude)> conlong-Areacobertura:
lat = x[n].latitude
long = x[n].longitude
Analisis = False
while Analisis:
if x:
n=0
lstdist= []
dist = 1000
for i in x:
if len(i[0]) >20:
d1 = contlat - i.latitude
d2 = conlong - i.longitude
dtot = numpy.sqrt((d1**2+d2**2))
lstdist.append(dtot)
n = lstdist.index(min(lstdist))
print(len(lstdist))
lat= x[n].latitude
long = x[n].longitude
else:
lat = 0
long = 0
print("Destino no encontrado o fuera del area de cobertura.")
Analisis = False
return lat,long
dfdire = pd.read_csv("DireccionesNomrmalizadas.csv")
direcciones = dfdire["Direccion"].tolist()
latitudes = []
longitudes = []
for dire in direcciones:
n = n+1
dire = dire +" , Escobar , B1625"
lat, long = geolocalizar(dire)
latitudes.append(lat)
longitudes.append(long)
folium.Marker(
location=[lat, long],
tooltip=dire,
icon=BeautifyIcon(
icon_shape='marker',
number=n,
spin=True,
text_color='red',
background_color="#FFF",
inner_icon_style="font-size:12px;padding-top:-5px;"
)
).add_to(m)
m.save("mapa.html")
data = {"direccion":direcciones, "lat":latitudes,"long":longitudes}
df= pd.DataFrame(data)
df.to_csv("direcciones2.csv")
print(df)
#print(nom.reverse([lat, long]))OutPut:
,direccion,lat,long
10,Peirano Nro: 273,-34.34110623733946,-58.79590066902237
11,Moreno 1143,-34.34059060884143,-58.797245785716306
12,Callao 242,-34.34051268218677,-58.79648247517158
13,LOS LAZARISTAS 371,-34.34260190849943,-58.79596122143443
14,LOS LAZARISTAS 371,-34.34260190849943,-58.79596122143443
15,Las Heras 2751,-34.315210692178546,-58.81418252144322
16,Mateo Gelves 1245,-34.337754831675774,-58.79421318128834
17,PASEO DE JULIO 488,-34.337191095818675,-58.80143206270873
...
Ruteador
Finally here! Ahora que ya tenemos todos los puntos que queremos unir, debemos encontrar la mejor manera de unirlos.
Como escribí anteriormente, existen varias maneras de resolver el problema, de todas las que probé, la manera mas sencilla es utilizar la librería OR Tools, de Google.
OR Tools, es una librería que tiene diferentes módulos para resolver problemas de Investigación operativa. Una de estas es para routing o TSP, con distintos grados de complejidad (Llegando y saliendo del mismo lugar, múltiples vehículos, limitaciones de horario, etc…)
El input que necesita OR Tools, para devolver el orden optimizado de repartición, es una matriz de distancias entre los puntos a unir.
Ahora si vayamos al pseudocódigo del programa:
- Lo primero que hacemos es colocar la ubicación de la sucursal, de la misma saldrá y llegara el transportista (Concatenado al Df de direcciones)
- Pasamos nuestro DataFrame a una lista y lo colocamos como body
- Usamos la API de OpenRouteServices para hacer el request de la matriz de distancias. (#El token es personal y se “tramita” desde tu usuario en la pagina)
- Redondeamos los valores de la respuesta (OR Tools, trabaja con int)
- Luego generamos un vector Data = [] Que es el encargado de llevar 3 valores claves. La matriz de distancias, La cantidad de vehiculos (En este caso 1), y el punto origen.
- Resolvemos con OR Tools. (Obtenemos una vector donde están ordenados los destinos, se referencian con el numero de index del vector origen)
- Ordeno mi lista de coordenadas, en base al resultado de OR Tools.
- Le pido a la API de OpenRoute, el polyline del camino entre puntos
- Ploteo en mapa la polyline + los puntos de entrega.
El codigo en cuestion:
import pandas as pd
import numpy as np
import requests
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
import folium
from folium.plugins import BeautifyIcon
UbicacionSucursal = [ -34.344129, -58.788988] #Escobar
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
#Abro el archivo con las rutas del dia
pd.set_option('display.max_columns', None)
df1 = pd.read_csv("Direcciones2.csv")
dfnew = pd.DataFrame({"direccion": 'Sucursal', "lat": UbicacionSucursal[0],"long": UbicacionSucursal[1]}, index=[0])
df = pd.concat([dfnew,df1]).reset_index(drop=True)
####Busco la matriz de distancias.
#Genero la lista de coordenadas como array de arrays
df['Coord'] = df[['long', 'lat']].values.tolist()
x = df["Coord"].tolist()
#Genero el mensaje y hago el request
body = {"locations":x,"metrics":["distance"],"units":"m"}
Token = '5b3ce3597851110001cf6248f472a82d932147fdba76bc87aac20d04'
headers = {
'Accept': 'application/json, application/geo+json, application/gpx+xml, img/png; charset=utf-8',
'Authorization': Token,
'Content-Type': 'application/json; charset=utf-8'
}
call = requests.post('https://api.openrouteservice.org/v2/matrix/driving-car', json=body, headers=headers)
info = call.json()
print(call)
distancias = info["distances"]
distancias = np.array(distancias)
distancias = np.around(distancias,0)
distancias = distancias.tolist()
#print(distancias)
data={}
data['distance_matrix'] = distancias
data['num_vehicles'] = 1
data['inicio-fin'] = 0
print(data)
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['inicio-fin'])
routing = pywrapcp.RoutingModel(manager)
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
solution = routing.SolveWithParameters(search_parameters)
def get_routes(solution, routing, manager):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
for route_nbr in range(routing.vehicles()):
index = routing.Start(route_nbr)
route = [manager.IndexToNode(index)]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
routes.append(route)
return routes
routes = get_routes(solution, routing, manager)
# Display the routes.
print(routes)
###YA TENGO MI RUTA OPTIMIZADA AHORA PASO A HACER UNA LISTA DE LAS COORDEANADAS Y PEDIRLE EL POLYLINE A OPENROUTES
list_viaje = []
for i in routes[0]:
list_viaje.append(df["Coord"][i])
#Ordeno mi DF con el orden de entrega (Elimino temporalmente el ultimo campo, ya que sale y llega al mismo destino)
df["orden"] = 0
n = 0
orden = routes[0]
orden = orden[:-1]
for i in orden:
df.loc[i,"orden"] = n
n = n +1
df = df.sort_values(by=['orden'])
print(df)
print(list_viaje)
body = {"coordinates":list_viaje}
call = requests.post('https://api.openrouteservice.org/v2/directions/driving-car/geojson', json=body, headers=headers)
info = call.json()
print(call)
linea = info["features"][0]["geometry"]["coordinates"]
print(linea)
#Cambio de long a lat para que se adecue al folium
for i in linea:
temp = i[0]
i[0] = i[1]
i[1] = temp
#Creo el mapa
m = folium.Map(location= UbicacionSucursal,
zoom_start=15)
folium.PolyLine(linea,
color='red',
weight=15,
opacity=0.8).add_to(m)
for location in df.itertuples():
folium.Marker(
location=[location.lat, location.long],
tooltip=location.direccion,
icon=BeautifyIcon(
icon_shape='marker',
number=int(location.orden),
spin=True,
text_color='red',
background_color="#FFF",
inner_icon_style="font-size:12px;padding-top:-5px;"
)
).add_to(m)
m.save("mapa.html")El resultado final de todo este proceso se ve así:
Resultados finales — Conclusión
Como resultado final, obtenemos una mejora sustancial con respecto al proceso manual, sin embargo entiendo que el proceso va a estar supeditado al deseo del transportista en 3 escenarios fundamentales:
- Si el transportista frena su auto, para entregar un paquete y ve que debería entregar y seguir andando, sin embargo tiene un punto de entrega a la vuelta de la manzana. Intuirá que es mejor dejar el auto estacionado e ir caminando a entregar de una vez ambos. El programa no tiene complejidad suficiente por el momento, para combinar la situación Auto (Donde debo respetar sentidos) y Caminata, donde no respeto sentidos.
- Si el transportista sabe que va a pasar por una zona insegura, y prefiere modificar su recorrido para no pasar por ahí.
- El transportista no confía en el programa o simplemente desea pasar por algún lado extra a tal hora para tomar un break, o algún tipo de restricción que simplemente no tenemos en cuenta.
Teniendo en cuenta todo lo anterior, igualmente conviene poder geolocalizar en el mapa y ver el routing. Ya sea que el transportista sea nuevo y siga el ruteo al pie de la letra. O mismo a un transportista de larga data la información le acelera el proceso de ordenamiento de sus paquetes permitiéndole salir a distribución de manera mas rápida.
