Algoritmo para optimizar rutas de senderismo en una sola pasada

Fuentes: Algorithm for optimizing single-pass hiking routes

El trazado óptimo (o redlining) consiste en recorrer todas las rutas de un área específica en una sola sesión, un desafío que nace de la comunidad de senderismo de las Montañas Blancas. Para completar el trazado de la Isla de los Ángeles en San Francisco, que abarca 19,4 millas de senderos únicos, el autor desarrolló un software especializado para planificar y ejecutar estas rutas de manera eficiente, evitando la fatiga de un ultramaratón.

El proceso de planificación requiere una fase de escrutinio riguroso para identificar senderos existentes y transitables, utilizando mapas de OpenStreetMap, mapas de calor de popularidad de Strava, imágenes satelitales y mapas oficiales de parques. En el caso de la Isla de los Ángeles, el autor detectó errores en la planificación inicial, como la inclusión de senderos inexistentes o la omisión de rutas cerradas, corrigiéndolos durante la ejecución.

Técnicamente, el sistema utiliza la API de Overpass para extraer datos de OpenStreetMap y los elimina manualmente para eliminar nodos innecesarios o ramales no transitables. La optimización de la ruta se basa en el problema del postman chino, un problema de optimización combinatoria que busca minimizar la distancia total o la elevación ganada. El software implementa un solucionador para este problema, considerando tanto la distancia como la elevación (usando datos de la API USGS 3DEP y la función de senderismo de Tobler) para generar la ruta más eficiente. En la prueba final, la ruta optimizada para minimizar distancia resultó en 23,8 millas, completada en aproximadamente cinco horas.