Solucionando problemas de Vendedor Viajero Geográfico utilizando Python

Soluciona problemas de Vendedor Viajero Geográfico con Python

Usando pyconcorde para encontrar soluciones óptimas a problemas de enrutamiento del mundo real

El famoso Problema del Viajante de Comercio (TSP, por sus siglas en inglés) consiste en encontrar una ruta óptima entre una colección de nodos (ciudades) y regresar al punto de partida. Parece sencillo, pero es imposible resolverlo por fuerza bruta para un gran número de nodos, ya que el número de posibles ordenamientos de n ciudades es n!. Esto significa que incluso para solo 30 ciudades, el número de recorridos que tendrías que verificar es de 265,252,859,812,191,058,636,308,480,000,000. Los problemas grandes de TSP son impracticables de resolver por fuerza bruta, incluso para computadoras potentes.

Afortunadamente, se han desarrollado algunos algoritmos que reducen drásticamente la cantidad de cálculos necesarios para resolver TSP grandes. Uno de estos programas informáticos, Concorde, fue desarrollado hace un par de décadas para su uso en la comunidad académica. Aunque es bastante técnico de usar como software independiente, y está destinado solo a especialistas, se ha desarrollado pyconcorde como un envoltorio de Python para Concorde. Una explicación de los algoritmos utilizados en Concorde está fuera del alcance de este artículo. Sin embargo, nos adentraremos en el código necesario para reproducir estos problemas y sus soluciones en Python.

TSP geográfico del mundo real

¿Cómo resolvería alguien un problema del viajante de comercio del mundo real y geográfico? Los puntos del mundo real no están conectados por simples líneas 2D como en la imagen anterior. En su lugar, las características geográficas están conectadas por varias rutas posibles, y esas rutas cambiarán dependiendo de si alguien está caminando, montando en bicicleta o conduciendo.

¿Por qué un científico de datos o un ingeniero de software querrían resolver un TSP del mundo real? Aquí tienes algunos ejemplos de casos de uso:

1. Una empresa que emplea mensajeros necesita una forma de calcular rutas óptimas a través de una ciudad, minimizando el tiempo que cada uno de sus conductores pasa en la carretera.
2. Un operador turístico necesita encontrar la ruta más corta que conecta un conjunto de destinos, dentro de una cantidad de tiempo limitada.
3. Una empresa de recolección de residuos o una autoridad local necesita asignar sus recursos para garantizar que las recogidas se realicen de la manera más eficiente posible.

Para resolver un TSP del mundo real, se puede utilizar la biblioteca routingpy para encontrar rutas, distancias (en metros) y duraciones (en segundos) entre puntos geográficos en pares de [longitud, latitud]. En este artículo describiremos el método que se puede utilizar para este tipo de problema.

• AI Generativa y MLOps Una Combinación Poderosa para el Desarrollo E...
• Una nueva forma de ver la privacidad de los datos
• 8 Técnicas para Modelar la Estacionalidad

Recorrido del código

Aquí se describe una guía para resolver un TSP geográfico utilizando Python. La estructura general del proceso de resolución del problema es la siguiente:

1. Obtener una lista de n coordenadas en pares [longitud, latitud].
2. Utilizar un servicio de enrutamiento para obtener una matriz (n x n) de duraciones del mundo real entre cada una de estas coordenadas, para el perfil apropiado (caminar, montar en bicicleta, conducir un coche, conducir un camión, etc.). Esta matriz será asimétrica (conducir de A a B no es exactamente lo mismo que de B a A).
3. Transformar la matriz (n x n) en una matriz simétrica (2n x 2n).
4. Alimentar esta matriz en el solucionador de Concorde para encontrar un ordenamiento óptimo de las coordenadas.
5. Crear la ruta del mundo real utilizando el servicio de enrutamiento.
6. Visualizar los resultados en un mapa.
7. Opcionalmente, crear un archivo GPX de la ruta final.

Cada uno de estos pasos se explicará en detalle.

Paso 1: Obtención de coordenadas

Para nuestro ejemplo, consideraremos el problema de conducir un automóvil entre 79 ciudades en el Reino Unido. A continuación se muestra un mapa de las ciudades del Reino Unido en azul. Un científico de datos puede encontrar coordenadas de varias formas. Si es necesario, se pueden encontrar manualmente utilizando Google Maps o Google Earth.

La estructura del código y los datos utilizados en este ejemplo también están disponibles en este repositorio de GitHub.

Aquí hay un archivo CSV que contiene las coordenadas de las ciudades (gb_cities.csv en el repositorio), y debajo de él el código necesario para importarlo utilizando pandas.

Nombre del lugar,Latitud,LongitudAberdeen,57.149651,-2.099075Ayr,55.458565,-4.629179Basildon,51.572376,0.470009Bath,51.380001,-2.36Bedford,52.136436,-0.460739...

import pandas as pddf = pd.read_csv('gb_cities.csv')coordinates = df[['Longitud', 'Latitud']].valuesnames = df['Nombre del lugar'].values

Paso 2: Utilizar un servicio de enrutamiento para obtener una matriz de duración

Hay varios servicios de enrutamiento disponibles a través de la biblioteca routingpy. La API de Graphhopper incluye un nivel gratuito que permite su uso con limitación de velocidad. Otros enrutadores disponibles a través de routingpy se enumeran en la documentación.

import routingpy as rpimport numpy as npapi_key = # obtén una clave gratuita en https://www.graphhopper.com/api = rp.Graphhopper(api_key=api_key)matrix = api.matrix(locations=coordinates, profile='car')durations = np.matrix(matrix.durations)print(durations)

Aquí está durations, una matriz de 79 x 79 del tiempo de conducción en segundos entre las coordenadas:

matrix([[    0, 10902, 30375, ..., 23380, 25233, 19845],        [10901,     0, 23625, ..., 16458, 18312, 13095],        [30329, 23543,     0, ...,  8835,  9441, 12260],        ...,        [23397, 16446,  9007, ...,     0,  2789,  7924],        [25275, 18324,  9654, ...,  2857,     0,  9625],        [19857, 13071, 12340, ...,  8002,  9632,     0]])

El tiempo de conducción entre ciudades se puede determinar de la siguiente manera:

1. Cada fila y columna corresponde a una ciudad: Aberdeen es la primera fila y columna, Ayr la segunda, Basildon la tercera, y así sucesivamente.
2. Para encontrar el tiempo entre Aberdeen y Ayr, mira la primera fila, segunda columna: 10,902 segundos. El tiempo inverso (Ayr a Aberdeen) es de 10,901 segundos.
3. En general, el tiempo desde la i-ésima hasta la j-ésima ciudad está en la intersección entre la i-ésima fila y la j-ésima columna.

Observa que la matriz, como era de esperar, tiene ceros en la diagonal, ya que cada punto está conectado consigo mismo con una distancia o duración cero. Además, la matriz no es completamente simétrica: las duraciones de conducción entre ciudades probablemente no sean idénticas en direcciones opuestas debido a diferentes diseños de carreteras y puntos de congestión de tráfico. Sin embargo, son ampliamente similares, como se esperaría.

Paso 3: Transformar una matriz asimétrica en simétrica

Antes de usar esta matriz para generar un ordenamiento óptimo en pyconcorde, debemos hacer que la matriz sea simétrica. Un método para transformar un TSP asimétrico en un TSP simétrico se describe en el artículo de Jonker y Volgenant (1983): Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters, 2(4), 161–163. A continuación se presenta la teoría detrás de esta transformación. Si se desea, esta sección se puede omitir (desplázate hacia abajo hasta la sección titulada Transformando el TSP asimétrico geográfico).

Transformación asimétrica a simétrica de Jonker/Volgenant

A continuación se muestra una visualización de un Problema del Agente Viajero asimétrico con 3 nodos y su matriz de distancias.

matrix([[0, 5, 2],        [7, 0, 4],        [3, 4, 0]])

Aquí hay un esquema del método utilizado para transformarlo en un Problema del Agente Viajero simétrico:

1. Crear nuevos nodos ficticios, A’, B’ y C’. Unir A con A’, B con B’ y C con C’ con una distancia cero.
2. Conectar los nodos con pesos de la siguiente manera: A a B ahora se representa como A’ a B; B a A ahora es B’ a A. B a C ahora es B’ a C; C a B ahora es C’ a B. C a A ahora es C’ a A; A a C es A’ a C.
3. Establecer todos los demás pesos de las aristas como infinitos, para que ningún algoritmo intente viajar entre ellos. Dado que esto será impráctico más adelante al usar pyconcorde, en su lugar se establecerán todos los demás pesos en un valor mucho mayor que el peso más alto que tenemos. En este caso, los estableceremos en 99.

Aquí está la matriz de distancias resultante. El orden de los nodos en la matriz es: A, B, C, A’, B’, C’.

matrix([[ 0, 99, 99,  0,  7,  3],        [99,  0, 99,  5,  0,  4],        [99, 99,  0,  2,  4,  0],        [ 0,  5,  2,  0, 99, 99],        [ 7,  0,  4, 99,  0, 99],        [ 3,  4,  0, 99, 99,  0]])

De nuevo, observe que la diagonal es cero, como se esperaría, y que la matriz ahora es simétrica. La matriz original está en la esquina inferior izquierda de la nueva matriz, y su transpuesta está en la esquina superior derecha. Mientras tanto, las partes superior izquierda e inferior derecha contienen pesos muy altos entre los nodos.

A, B y C (parte superior izquierda) ya no están conectados entre sí (estrictamente hablando, están conectados pero con un peso muy alto en lugar de infinito, por razones prácticas). Esto significa que ningún algoritmo buscará encontrar un camino entre estos nodos. Del mismo modo, A’, B’ y C’ (parte inferior derecha) no están conectados entre sí. En su lugar, la naturaleza direccional de la red asimétrica original se representa aquí mediante los pesos de los nodos originales A, B y C, junto con sus nodos ficticios A’, B’ y C’.

Existe una correspondencia uno a uno entre las soluciones del problema asimétrico original y el nuevo Problema del Agente Viajero simétrico:

• A — B — C — A corresponde a A — A’ — B — B’ — C — C’ — A
• A — C — B — A corresponde a A — A’ — C — C’ — B — B’ — A

En cada caso, los nodos ficticios A’, B’ y C’ alternan con los nodos originales A, B y C, y cada nodo original es adyacente a su nodo ficticio “pareja” (A es adyacente a A’, y así sucesivamente).

Transformando el Problema del Agente Viajero asimétrico geográfico

Volviendo a nuestro ejemplo práctico. Podemos crear una función para transformar una matriz de Problema del Agente Viajero asimétrica en una simétrica:

def symmetricize(m, high_int=None):        # si no se proporciona high_int, hacerlo igual a 10 veces el valor máximo:    if high_int is None:        high_int = round(10*m.max())            m_bar = m.copy()    np.fill_diagonal(m_bar, 0)    u = np.matrix(np.ones(m.shape) * high_int)    np.fill_diagonal(u, 0)    m_symm_top = np.concatenate((u, np.transpose(m_bar)), axis=1)    m_symm_bottom = np.concatenate((m_bar, u), axis=1)    m_symm = np.concatenate((m_symm_top, m_symm_bottom), axis=0)        return m_symm.astype(int) # Concorde requiere pesos enteros

symmetricize(durations) devuelve:

matriz([[     0, 461120, 461120, ...,  23397,  25275,  19857],        [461120,      0, 461120, ...,  16446,  18324,  13071],        [461120, 461120,      0, ...,   9007,   9654,  12340],        ...,        [ 23397,  16446,   9007, ...,      0, 461120, 461120],        [ 25275,  18324,   9654, ..., 461120,      0, 461120],        [ 19857,  13071,  12340, ..., 461120, 461120,      0]])

Esta matriz de 158 x 158 contiene una copia de durations en la parte inferior izquierda y una copia transpuesta en la parte superior derecha. El valor alto de 461,120 (10 veces el valor máximo en durations) significa que, para fines prácticos, los nodos con esta duración no están conectados.

Esta matriz finalmente se puede alimentar a pyconcorde para calcular una ruta óptima.

Paso 4: Usando el solucionador Concorde

Instalando pyconcorde

Ejecuta los siguientes comandos para instalar pyconcorde (la instalación está disponible en Linux o Mac OS, pero no en Windows en la actualidad):

virtualenv venv                                  # crear entornos virtualessource venv/bin/activate                         # activarlogit clone https://github.com/jvkersch/pyconcorde # clonar el repositoriocd pyconcorde                                    # cambiar de directoriopip install -e .                                 # instalar pyconcorde

Resolviendo el TSP en Python

Ahora podemos importar de concorde en un script de Python.

from concorde.problem import Problemfrom concorde.concorde import Concordedef solve_concorde(matrix):    problem = Problem.from_matrix(matrix)    solver = Concorde()    solution = solver.solve(problem)    print(f'Recorrido óptimo: {solution.tour}')    return solution

Nuestra matriz simétrica de duraciones se puede alimentar a solve_concorde().

durations_symm = symmetricize(durations)solution = solve_concorde(durations_symm)

Este es el resultado de la impresión:

Recorrido óptimo: [0, 79, 22, 101, 25, 104, 48, 127, 68, 147, 23, 102, 58, 137, 7, 86, 39, 118, 73, 152, 78, 157, 36, 115, 42, 121, 62, 141, 16, 95, 20, 99, 51, 130, 40, 119, 19, 98, 59, 138, 50, 129, 54, 133, 27, 106, 10, 89, 4, 83, 66, 145, 33, 112, 14, 93, 2, 81, 45, 124, 32, 111, 11, 90, 29, 108, 34, 113, 24, 103, 8, 87, 17, 96, 56, 135, 64, 143, 61, 140, 75, 154, 52, 131, 71, 150, 18, 97, 3, 82, 9, 88, 74, 153, 55, 134, 72, 151, 28, 107, 12, 91, 70, 149, 65, 144, 35, 114, 31, 110, 77, 156, 63, 142, 41, 120, 69, 148, 6, 85, 76, 155, 67, 146, 15, 94, 44, 123, 47, 126, 60, 139, 57, 136, 38, 117, 13, 92, 5, 84, 43, 122, 49, 128, 46, 125, 21, 100, 1, 80, 30, 109, 53, 132, 37, 116, 26, 105]

Esta solución muestra el orden de los nodos en el recorrido óptimo. Tenga en cuenta que esta solución, como se esperaba anteriormente, contiene nodos originales (numerados del 0 al 78) alternando con sus nodos fantasma asociados (del 79 al 157):

• 0 está asociado con 79,
• 22 con 101,
• 25 con 104, y así sucesivamente…

Esto sugiere que la solución ha funcionado correctamente.

Paso 5: Creación de la ruta del mundo real

El siguiente paso es seleccionar elementos alternos de la solución (los nodos correspondientes a las 79 ciudades originales), y luego ordenar las coordenadas en consecuencia.

# seleccionar elementos alternos: estos corresponden a los nodos originalesstour = solution.tour[::2]# ordenar las coordenadas y los nombres originalescoords_ordered = [coordinates[i].tolist() for i in tour]names_ordered = [names[i] for i in tour]

Aquí están los primeros nombres de ciudad en names_ordered, (el orden real de las ciudades en el recorrido óptimo):

['Aberdeen', 'Dundee', 'Edimburgo', 'Newcastle Upon Tyne', 'Sunderland', 'Durham', ...]

Ahora agregamos de nuevo la primera ciudad para completar un recorrido circular, y finalmente obtenemos la ruta final utilizando la API de direcciones de Graphhopper.

# agregar de nuevo la primera ciudad para completar un recorrido completocoords_ordered_return = coords_ordered + [coords_ordered[0]]# obtener direcciones de manejo completas para el recorrido ordenadodirections = api.directions(locations=coords_ordered_return, profile='car')

Paso 6: Visualización en un mapa

Ver la ruta final en un mapa nos permitirá tener confianza en el resultado, además de permitirnos utilizar la solución en un entorno práctico. El siguiente código mostrará un mapa de folium que se puede guardar en HTML.

import foliumdef generate_map(coordinates, names, directions):    # folium necesita latitud, longitud    coordinates = [(y, x) for (x, y) in coordinates]    route_points = [(y, x) for (x, y) in directions.geometry]    lat_centre = np.mean([x for (x, y) in coordinates])    lon_centre = np.mean([y for (x, y) in coordinates])    centre = lat_centre, lon_centre    m = folium.Map(location=centre, zoom_start=1, zoom_control=False)    # trazar la línea de la ruta    folium.PolyLine(route_points, color='red', weight=2).add_to(m)        # trazar cada punto con un tooltip de información al pasar el ratón      for i, (point, name) in enumerate(zip(coordinates, names)):        folium.CircleMarker(location=point,                      tooltip=f'{i}: {name}',                      radius=2).add_to(m)    custom_tile_layer = folium.TileLayer(        tiles='http://{s}.basemaps.cartocdn.com/light_all/{z}/{x}/{y}.png',        attr='CartoDB Positron',        name='Positron',        overlay=True,        control=True,        opacity=0.7  # Ajustar la opacidad para controlar el nivel de desvanecimiento    )    custom_tile_layer.add_to(m)    folium.LayerControl().add_to(m)    sw = (np.min([x for (x, y) in coordinates]), np.min([y for (x, y) in coordinates]))    ne = (np.max([x for (x, y) in coordinates]), np.max([y for (x, y) in coordinates]))    m.fit_bounds([sw, ne])    return mgenerate_map(coords_ordered, names_ordered, directions).save('gb_cities.html')

El resultado se muestra en la parte superior de este artículo. Haga clic aquí para verlo como un mapa interactivo. Es posible hacer zoom en el mapa para ver más detalles y pasar el cursor sobre ciudades individuales para revelar su número en la secuencia del recorrido. A continuación se muestra una parte ampliada del mapa que muestra la ruta pasando por Sheffield (entre Lincoln y Chesterfield en el recorrido óptimo).

Paso 7: Opcional: Crear un archivo GPX

Si la ruta calculada necesita ser seguida en la vida real, por ejemplo en un dispositivo con GPS (como un teléfono o sistema de navegación para automóviles), se puede crear un archivo GPX. Esto no forma parte del problema de optimización, pero es un paso adicional opcional disponible si deseas guardar la ruta en un archivo. El archivo GPX se crea a partir de la variable directions:

def generar_archivo_gpx(directions, nombre_archivo):    plantilla_gpx = """<?xml version="1.0" encoding="UTF-8"?>    <gpx version="1.1" xmlns="http://www.topografix.com/GPX/1/1"        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"        xsi:schemaLocation="http://www.topografix.com/GPX/1/1        http://www.topografix.com/GPX/1/1/gpx.xsd">        <trk>            <name>Ruta</name>            <trkseg>{}</trkseg>        </trk>    </gpx>    """    plantilla_trkseg = """        <trkpt lat="{}" lon="{}"/>    """    elementos_trkseg = ""    for punto in directions.geometry:        elementos_trkseg += plantilla_trkseg.format(punto[1], punto[0])    datos_gpx = plantilla_gpx.format(elementos_trkseg)    with open(nombre_archivo, 'w') as archivo:        archivo.write(datos_gpx)generar_archivo_gpx(directions, 'gb_ciudades.gpx')

El archivo GPX para este problema se puede descargar aquí.

Conclusión

Hemos visto cómo podemos combinar los siguientes elementos para resolver problemas del viajante de comercio geográficos del mundo real:

1. Matrices de direcciones y duración de la biblioteca routingpy, especificando un perfil adecuado (modo de transporte).
2. Un solucionador eficiente y poderoso de Concorde a través del envoltorio pyconcorde, para proporcionar una ruta óptima.
3. Visualización utilizando folium para crear un mapa.

El recorrido en automóvil mostrado anteriormente es una solución convincente para el problema del viajante de comercio de 79 ciudades, y según el solucionador de Concorde, es ‘óptima’ de manera comprobada. Sin embargo, como estamos trabajando con datos del mundo real, el resultado final es tan bueno como la entrada. Estamos confiando en que la matriz de duraciones de punto a punto obtenida de routingpy sea representativa del mundo real. En realidad, el tiempo que lleva caminar, andar en bicicleta o conducir entre puntos dependerá de la hora del día o del día de la semana. Esta es una limitación del método que hemos utilizado. Una forma de tener más confianza en el resultado final sería probar el mismo método con un servicio de enrutamiento alternativo. Cada servicio de enrutamiento (Graphhopper, ORS, Valhalla, etc.) tiene su propia API que se podría utilizar para un problema de TSP como el descrito aquí, y los resultados podrían compararse entre diferentes servicios.

A pesar de las limitaciones del mundo real para resolver un problema como este, la metodología mencionada anteriormente proporciona un buen punto de partida para un vendedor o mensajero que necesita moverse por una ciudad de la manera más eficiente posible o para un turista que desea visitar la mayor cantidad de lugares posibles en su recorrido. Al visualizar los resultados en un mapa interactivo y almacenar la ruta como un archivo GPX, la solución es útil tanto para el usuario final como para el científico de datos que implementó el código.

---

• Deep Dives
• Geo
• Operations Research
• Routing
• Travelling Salesman