Para construir una matriz de distancias, necesitamos obtener la distancia entre cualquier par de ubicaciones. Suena simple, pero la “distancia” realmente depende del contexto. ¿Consideramos el número reportado por aplicaciones cartográficas, como Google Maps, que tienen en cuenta la red de calles, puentes, parques, etc..? Si es así, ¿tomamos la distancia que caminaría un peatón o la que recorrería un automóvil? ¿O tal vez simplemente la buena longitud de una línea recta que conecta los dos puntos? Claramente, tenemos muchas distancias posibles para elegir, con distintos grados de precisión. La primera pregunta que tenemos que responder es: ¿Cómo deberíamos definir “distancia”? en el contexto particular de nuestro problemay en este escenario?
3.1. ¿Debo hacer un esfuerzo adicional para ganar una yarda extra?
Es natural sentirse tentado a utilizar datos precisos. Al final, todos sabemos que la precisión es intrínsecamente valiosa y, por tanto, nos inclinamos a buscar datos precisos, cuanto más, mejor. Pero también debemos recordar que datos más precisos implican código y dependencias más complejos y, por lo tanto, más tiempo de desarrollo y mantenimiento. Mientras seguimos un enfoque ágilno dejamos que el mejor ser el enemigo de la bienentonces Comenzaremos lo más simple posible y luego agregaremos complejidad gradualmente, solo si está justificado.
En este punto en el que tenemos que encontrar distancias entre ubicaciones, podríamos hacer lo que muchos hacen y pasar directamente a soluciones basadas en API de terceros que requieren claves de aplicaciones, credenciales o incluso números de tarjetas de crédito para los proveedores de la nube. Ese enfoque está bien, pero muchas veces es ineficiente, ya que podemos olvidar que La información precisa aporta valor añadido, pero también conlleva costes añadidos..
👁️ No existe la “precisión gratuita”
Recordando que en general siempre “pagamos un precio” por acceder a datos precisos (lo cual está estrechamente relacionado con el concepto de Valor de la información) es otra razón por la que adoptar un enfoque ágil del problema es un curso de acción más sencillo. Por comenzando con suposiciones simples sobre el “nivel requerido de precisión”, y verificando su validez en nuestros propios datos del problemanos estamos asegurando de que, si eventualmente necesitamos aumentar la precisión de nuestros datos, estaremos “pagando un precio” que es vale la pena (esperado) mejores resultados.
Entonces comencemos de manera muy simple. Tenemos coordenadas. Primera idea: Estas coordenadas se distribuyen en parcelas de la Tierra. muy pequeña en comparación con el radio de la Tierra, por lo que podríamos tratar las latitudes como coordenadas Y y las longitudes como coordenadas X en un plano 2D, y luego simplemente calcular la distancia euclidiana (término elegante para la habitual “línea recta”).
- Ventajas: una fórmula simple para la distancia, sin nuevas dependencias o datos, las relaciones espaciales entre ubicaciones se conservan.
- Desventajas: las latitudes y longitudes son números adimensionales, por lo que los números que obtendríamos al resolver el problema no serían distancias reales. Esto significa que cierta información que nos importa, como la distancia total recorrida, no estará disponible, incluso si podemos obtener el recorrido óptimo.
Los contras superan a los pros, por lo que necesitamos un enfoque más complejo (pero sigue siendo simple). Segunda idea: trata las coordenadas como lo que son, puntos de la Tierra, pero aproxima la Tierra como una esfera. Una esfera no tiene la conocida geometría euclidiana, por lo que necesitaremos una fórmula no trivial que considere esta geometría esférica al calcular la distancia en “línea recta” entre dos puntos. Así que ahora sólo es cuestión de implementar esa fórmula usando el radio de la Tierra. Podríamos hacer eso, pero confiaremos en una biblioteca famosa que ya lo hace, e incluso mejor.
3.2. Utilidades de geolocalización con geopy
Si esta serie de artículos se centrara especialmente en la ciencia de datos geoespaciales, sería valioso tomarse el tiempo para explicar e implementar la fórmula para la distancia del gran círculo, una buena opción de línea base para calcular distancias en “línea recta” entre puntos de una esfera. Sin embargo, esta serie de artículos trata sobre la creación de una sistema de planificación turística basado en la optimizaciónpor lo que en lugar de elaborar nuestras propias fórmulas para las utilidades geoespaciales, confiaremos en geopy para hacer el trabajo pesado por nosotros. De esa manera, mantenemos el enfoque en alcanzar una solución rápidamente.
Instálelo ejecutándolo en un indicador de Anaconda (o dentro del entorno conda que creamos en el primer artículosi lo creaste) lo siguiente:
conda install -y -c conda-forge geopy=2.3.0
Ahora hagamos una demostración con geopy para sólo dos ubicaciones.
3.3. Llegando a los puntos
Dadas las coordenadas de dos puntos, la geodesic funcion de geopy calcula la distancia de la geodésica que los conecta a través de la superficie de la Tierra. En Geometría, el geodésico es el camino de distancia mínima entre puntos en un dado espacio métrico. En nuestro familiar espacio euclidiano, lineas rectas son las geodésicas. En un espacio esférico, grandes círculos son. El “espacio” subyacente que Geopy geodesic La función considera que es una modelo elipsoide preciso de la Tierra.
👁 Un círculo máximo es genial, pero una elipse es aún mayor
Antes dije que consideraríamos la Tierra como una esfera, porque era la aproximación viable más simple. En realidad, la Tierra no es una esfera, sino un elipsoide, un sólido con una geometría más compleja. Ahora eso
geopynos evitará codificar nuestras propias funciones para geometrías no euclidianas, podremos mejorar nuestra aproximación de la Tierra y emplear la más precisa distancia elipsoidal entre dos puntos, en lugar de la distancia del gran círculo. Un mejor modelo de la Tierra para las mismas líneas de código. De hecho, esto es precisión gratuita, así que ¿por qué no tomarlo?
Aquí hay una función que calcula la distancia elipsoidal entre el punto 1 y el punto 2, en metros:
from geopy.distance import geodesicdef ellipsoidal_distance(p1, p2) -> float:
""" Calculate distance (in meters) between p1 and p2, where
each point is represented as a tuple (lat, lon) """
return geodesic(p1, p2).meters
¿Cuál es la distancia entre la Torre Eiffel y el Louvre?
p1 = df_sites.loc['Tour Eiffel']
p2 = df_sites.loc['Louvre']ellipsoidal_distance(p1, p2) # output: 3173.119635531859
3173 metros, unos 3,2 km. Google Maps dice que son 3,5 km. El calculado La distancia es un 8,6 % inferior a la “real” distancia. A nuestras piernas solo les importa errores absolutos en distancia, que en este caso equivale a sólo 330 metros adicionales a caminar, en comparación con la distancia estimada. No parece un error significativo para un turista que espera estar todo el día paseando por una gran ciudad.
¿Y entre la Torre Eiffel y el Puerto de Suffren?
ellipsoidal_distance(
df_sites.loc['Tour Eiffel'],
df_sites.loc['Port de Suffren']
) # output: 328.3147101635456
328 metros, esta vez un 6% menos (sólo 22 metros menos) que los 350 metros que proporciona Google Maps. No está tan mal para aplicar una fórmula. Como era de esperar, cuanto más cerca estén los puntos, menos posibilidades habrá de que las calles zigzagueen y aparezcan curvas y, por tanto, menor será el error en el que incurre el modelo elipsoide. Aspecto suficientemente bueno para nuestros propósitos actuales.
Ahora debemos aplicar esta función a todos los pares de ubicaciones, obteniendo así la matriz de distancias que necesita el modelo TSP.
3.4. De coordenadas a matriz de distancias
Esta es la parte fácil, donde sólo tenemos que recorrer todos los sitios dos veces y calcular y almacenar la distancia entre cada par. La siguiente función hace eso. Tenga en cuenta que la métrica de distancia se pasa como argumento opcional, siendo la distancia elipsoidal que usamos antes la predeterminada. Dejamos la puerta abierta a que en el futuro se aprueben mejores métricas de distancia.
def compute_distance_matrix(df_sites, dist_metric=ellipsoidal_distance):
""" Creates an N x N distance matrix from a dataframe of N locations
with a latitute column and a longitude column """
df_dist_matrix = pd.DataFrame(index=df_sites.index,
columns=df_sites.index)for orig, orig_loc in df_sites.iterrows(): # for each origin
for dest, dest_loc in df_sites.iterrows(): # for each destination
df_dist_matrix.at[orig, dest] = dist_metric(orig_loc, dest_loc)
return df_dist_matrix
df_distances = compute_distance_matrix(df_sites)
display(df_distances)
¡Y ahí lo tenemos! Como se esperaba, la diagonal de la matriz es cero y la matriz es simétrica. El índice y las columnas del marco de datos de salida contienen los nombres de los sitios de entrada.
Funcionalidad demostrada. Ahora podemos hacerlo mejor para facilitar el uso de esta función. Resumamos esta funcionalidad dentro de una clase de una manera conveniente, para una fácil reutilizacióny lo más importante, para integración más fácil con el modelo de optimización del TSP que construimos en el sprint anterior.