En un artículo anterior, describí un algoritmo que le permite construir rutas a pie más interesantes (en lugar de más cortas, como todas las marcas Yandex-Google) entre dos puntos. El algoritmo cargó vistas, parques y otros objetos agradables e interesantes para los peatones del Open Street Map y estableció una ruta a través de ellos. Como resultado, el camino podría ser 10-20% más largo, pero mucho más pintoresco e interesante.
Fotos de la ciudad - Alex 'Florstein' Fedorov
En los comentarios, muchos escribieron que, además de las rutas entre dos puntos, estarían interesados en construir rutas circulares que comenzarían y terminarían en el mismo punto y encajarían en un límite de tiempo dado. Por ejemplo, si tiene dos horas para ir al tren o encontrarse con amigos, no tendrá tiempo de ir a algún lugar lejos durante este tiempo, pero es muy posible caminar y ver la belleza cercana.
Después de varios experimentos, compuse un algoritmo genético que construye rutas bastante buenas (para mí) en esta situación. Bajo cat descripción del principio de funcionamiento y algunos ejemplos.
Por lo tanto, los usuarios desean poder hacer un breve recorrido por el área circundante y regresar al punto de inicio en el tiempo especificado (generalmente de 1 a 2 horas). Al final resultó que, este tipo de caminata es bastante demandada. Por ejemplo, el artículo "Patrones de movimiento de los turistas dentro de un destino" describe el estudio de las pistas de 250 turistas en Hong Kong, mientras que el 40% de los turistas comenzaron a explorar la ciudad desde una ruta circular dentro de un radio de 500 metros del hotel. Sin embargo, a menudo las personas simplemente andan por ahí, sin saber qué es interesante se puede ver cerca.
La tarea es complicada si no se encuentra en el centro turístico (donde quiera que vaya, encontrará algo interesante en todas partes), sino en algún lugar de las afueras donde necesita buscar lugares de interés.
Radio y selección de atracciones
Para construir una ruta, primero debemos seleccionar las atracciones que queremos visitar. Y para esto necesita determinar el área de su búsqueda alrededor del punto de partida. Si el usuario define el tiempo máximo de caminata en M minutos, entonces el punto más distante al que puede llegar y tener tiempo para regresar es el punto a distancia (V * M / 2), donde V es la velocidad del peatón.
La velocidad promedio preferida de un peatón puede considerarse 1.4 metros por segundo. Sin embargo, al hacer turismo, una persona va un poco más despacio, ya que pasa más tiempo en una gira. Construí algunas rutas alrededor de la ciudad y caminé a lo largo de ellas, comparando el tiempo de la caminata con lo que predijo la aplicación. Como resultado, resultó que mi velocidad promedio de caminata era aproximadamente un 20% menor, es decir aproximadamente 1.1 m / s. Como me detenía periódicamente para tomar fotos, consulte con el mapa, a veces cruzaba la carretera una vez más para elegir el mejor ángulo o comprar helado.
Realicé experimentos en áreas desconocidas de la ciudad, usando mi algoritmo allí puedes encontrar todo tipo de cosas interesantes sobre las que no había escuchado antes. Por ejemplo, un monumento al primer folleto.
Elegir un punto de interés a una distancia máxima conducirá a la construcción de una ruta circular degenerada. Dado que el peatón ya no tendrá tiempo para salir del camino más corto en línea recta, podrá visitar solo esta atracción, ir a ella y regresar por la misma calle, como lo muestra la flecha roja.
Aquí podemos ir al parque más lejos o visitar varios puntos a la vez más cerca
Pero esta situación contradice la idea de rutas circulares interesantes, porque de hecho solo vimos una calle y un objeto, pero quiero ver más. Por lo tanto, de acuerdo con los resultados de los experimentos, se eligió un radio igual a un tercio de la distancia máxima. Con este radio de búsqueda, el peatón tendrá tiempo suficiente para alcanzar el punto de interés más distante a lo largo del radio, luego, si es necesario, camine la misma distancia a lo largo del acorde en busca de otros objetos interesantes y luego regrese a tiempo.
Problemas de abordaje frontal
Bien, hemos reunido una lista de atracciones candidatas. Ahora queda elegir cuál de ellos y en qué orden queremos inspeccionar. Lo más probable es que no tengamos tiempo para visitarlos, por lo que debemos elegir el subconjunto más interesante de ellos.
Primero, intenté formular y construir un algoritmo secuencial simple. Sin embargo, rápidamente me encontré con una serie de problemas.
Si consideramos la situación de la figura anterior, no está claro dónde comenzar a construir la ruta. Si el parque es la atracción más importante, pero la más distante, entonces comenzando con él obtendremos una versión degenerada, sobre la cual escribimos anteriormente.
La siguiente solución obvia es agrupar las vistas e intentar buscar el camino hacia el grupo más rentable, y luego caminar dentro de él. Pero aquí nuevamente, no todo está claro: desde qué grupo comenzar, qué camino seguir. Siempre puede caer en la trampa del tipo en el que fuimos por el camino equivocado y nos encontramos con el "desierto", un área sin vistas que no tenemos suficiente tiempo para ir y volver al punto de partida.
En algún momento, se hizo evidente para mí que prácticamente estaba haciendo el trabajo del algoritmo genético: dibujo diferentes rutas en el mapa y trato de determinar cuánto me gustaría personalmente.
Algoritmo genético
Después de recibir una lista numerada de atracciones, el algoritmo debe elegir un subconjunto ordenado, que formará la base de la ruta circular. La ruta final en este caso es una de las ubicaciones de muchas atracciones clave (no queremos repeticiones y no estamos obligados a usar todos los objetos posibles).
Conociendo la fórmula para el número de ubicaciones de n a k, podemos estimar el número posible de opciones. Si consideramos la ruta de una hora alrededor de la Plaza del Palacio en San Petersburgo, habrá 54 candidatos para atracciones clave después de filtrar y agrupar en un radio de 1320 metros (que se define como se describe anteriormente).
Gachas infernales de un montón de vistas en el centro, una salida de depuración de áreas de visibilidad calculadas de acuerdo con el algoritmo del artículo anterior
El principio de selección y clasificación se describe en un artículo anterior, además eliminamos objetos con un interés de menos de 3 (por el bien de tales objetos menores, es poco probable que una persona esté lista para llegar lejos, a menos que no haya nada más cerca). Por lo tanto, el número posible de rutas se puede calcular mediante la fórmula del número de ubicaciones de 54 a 5, es 379501200. Para una ruta de 2 horas, dentro del radio de los cuales ya caen 151 puntos de interés, este número será igual a 73423236600. Bueno, un poco demasiado para una búsqueda simple.
Cromosomas y operadores genéticos.
Los cromosomas en este caso son una línea en la que cada elemento es el número de la atracción clave correspondiente. Para tales tareas en las que los cromosomas son permutaciones o arreglos, existen variantes optimizadas especiales de operadores genéticos. Dichos operadores conservan la propiedad del cromosoma para seguir siendo una permutación o colocación del conjunto inicial de elementos.
- Crossover parcialmente mapeado (PMX) se utiliza para cruzar.
- Para la mutación, se utiliza el intercambio de lugares de dos genes aleatorios (Swap Mutator).
Se puede encontrar una descripción del funcionamiento de estos operadores con ejemplos, por ejemplo, en el trabajo "Algoritmos genéticos para el problema del vendedor ambulante: una revisión de representaciones y operadores".
Función de la aptitud
La función fitness debe tener en cuenta los siguientes factores para construir una ruta circular interesante:
- El interés total de todas las atracciones clave visitadas debe ser lo más grande posible.
- El tiempo total de viaje debe ser lo más cercano posible al especificado por el usuario, la ruta no debe ser mucho más larga o más corta. Solo se permiten rutas cortas cuando no hay suficientes atracciones cercanas.
- La ruta no debe cruzarse. Para cada auto-intersección, agregamos porcentajes de penalización al valor total de la función.
- La forma de la ruta debe estar cerca del círculo, debe capturar el área más grande posible de la ciudad y evitar casos degenerados. Para hacer esto, ponemos en la función la relación del área de la figura descrita por la ruta al área del círculo en el que se buscaron las vistas.
Aquí hay un ejemplo de un buen viaje de ida y vuelta. Pasa por dos parques y nunca visita el mismo lugar dos veces.
Aquí hay un ejemplo de una ruta claramente fracasada. Contiene ramas sin salida, donde el peatón tendrá que regresar a lo largo del camino examinado, y auto intersecciones. En las intersecciones, generalmente se pierde el tiempo en vano para volver a examinar secciones de la ciudad ya vistas.
La mala ruta se obtuvo realmente por la genética, en la cual los puntos 3 y 4 fueron deshabilitados para la función de condición física (multas por autocruzamiento y para un área pequeña)
Matices
Durante las pruebas, surgieron algunos matices más.
Límite de tiempo excedido
Durante el trabajo de la genética, contamos la longitud de la ruta a lo largo de líneas rectas entre puntos. Y después de que hayamos seleccionado objetos para la comunicación usando el algoritmo genético, estamos buscando el camino entre ellos usando el algoritmo del artículo anterior. En este caso, el camino puede alargarse y arrastrarse sin tiempo. Después de todo, en la ciudad, a menudo, el camino más corto a lo largo de la calle puede ser muchas veces más largo que una línea recta.
En promedio, la diferencia generalmente es de aproximadamente 10-20% y la ponemos en la función de aptitud física (es decir, la genética busca una ruta con un margen de tiempo, que luego se come al establecer una ruta detallada). A veces no es suficiente: debe volver a calcular la ruta nuevamente. Tenemos tales lugares en ciudades donde la diferencia entre las rutas "como un pájaro" y "como un peatón" es kilómetros.
Entre los puntos de 50 metros en línea recta, pero un kilómetro y medio a lo largo de las aceras y los pasos que pasan por alto.
Sin embargo, de todos modos, el algoritmo a veces excede el tiempo establecido por el usuario, pero luego cada uno puede decidir por sí mismo si tiene 10-15 minutos adicionales o si tiene que completar la caminata antes.
Venecia
Cuando el algoritmo estuvo listo, decidí agregar las principales ciudades turísticas de Europa por diversión. Resultó interesante: las ciudades son diferentes en todas partes, las características de mapeo en OSM también, como resultado, constantemente tuve que terminar algo.
Específicamente, la búsqueda de rutas circulares se rompió en Venecia. Dado que este es un ejemplo único de una ciudad con áreas no relacionadas, las islas están separadas por el Gran Canal, a través del cual no hay puentes, solo es posible cruzar en ferry.
Como resultado, el algoritmo seleccionó parte de los objetos en un lado del estrecho, parte en el otro, luego no pudo encontrar un camino de tierra entre ellos y cayó. Tuve que agregar un control sobre la accesibilidad de todas las atracciones desde el punto de partida.
A veces todavía tienes que volver de la misma manera.
En el ejemplo con el parque de arriba, hay una parte de la ruta a la que debes regresar de la misma manera: esta es una pequeña península en la que se encuentra un monumento con un avión. El único camino conduce a esta península, y será necesario regresar por ella. Por lo tanto, dichos reembolsos no se pueden prohibir por completo. El algoritmo para esto aumenta el peso de todos los bordes que ya se han recorrido, reduciendo la probabilidad de un retorno a lo largo de ellos, pero aún así lo hace posible.
Aunque a veces todavía funciona mal. Por ejemplo, se quejan de la catedral principal de Kaliningrado. Se encuentra en una isla en medio del río por donde pasa el puente. Desde este puente hay un descenso y un camino a la catedral, aparentemente el algoritmo aumenta demasiado el peso de este único camino, lo que hace que regresar no sea rentable. Como resultado, casi nunca conduce a la catedral, aunque esta es una de las atracciones clave de la ciudad. Todavía requiere algún tipo de refinamiento.
Resultados
El algoritmo genético es algo poco impredecible, por lo que a veces tiene errores y dibuja zigzags extraños. Pero en general, estoy satisfecho con el resultado. Lo que es especialmente bueno, el algoritmo funciona no solo en el centro turístico (donde no es un problema divertirse), sino también en las afueras de la ciudad. Donde, a menudo, sin pistas, encontrar algo interesante es muy difícil.
Incluso en los sacos de dormir del suroeste de San Petersburgo, puedes encontrar suficientes monumentos para una caminata de dos horas.
Puede probar el algoritmo usted mismo en una de las 77 ciudades compatibles en nuestro sitio web Sight Safari o en nuestra aplicación de Android (sí, finalmente lo completamos).
Es especialmente interesante cómo funcionará el algoritmo en ciudades con terrenos y elevaciones complejas. Agregamos soporte para análisis de elevación a la biblioteca Graphopper pathfinder, pero no podemos verificar cómo debería ser: Peter es una ciudad demasiado plana.
En general, intente, escriba reseñas, son las rutas que se construyen correctamente. Puede solicitar de inmediato la incorporación de nuevas ciudades.