Planificación personalizada de excursiones de un día: un enfoque multimodal de optimización multicriterio basado en TSP-TW
por Ernesto Galvan Papel
1. Conceptos
1.1. Geocodificación
1.1.1. Proceso de convertir direcciones de actividades en coordenadas geográficas
1.2. Multimodal
1.2.1. Uso combinado de diferentes modos o medios para un mismo fin.
1.3. Crowdsourcing
1.3.1. Modelo de colaboración donde una gran cantidad de personas (la "multitud") contribuyen voluntariamente con ideas, información o trabajo a un proyecto, generalmente a través de plataformas digitales.
1.4. Ventanas de tiempo
1.4.1. Se refiere a los intervalos de tiempo específicos durante los cuales se deben realizar ciertas actividades
1.5. Problema del Viajante de Comercio con Ventanas de Tiempo (TSP-TW)
1.5.1. Marco central utilizado para modelar y resolver el problema de planificación de itinerarios, extendido para incorporar múltiples modos de transporte y preferencias individuales
2. Resumen
2.1. En este artículo, presentamos un nuevo enfoque para calcular itinerarios personalizados para planes de viaje individuales a lo largo de un día, teniendo en cuenta la amplia variedad de preferencias de movilidad que los individuos consideran a la hora de elegir su itinerario.
2.1.1. Ampliamos el problema del viajante de comercio con ventanas de tiempo (TSP-TW) integrando técnicas de optimización multicriterio, actividades flexibles, opciones de aparcamiento y transporte, y varios modos de transporte para proporcionar una representación más completa de las opciones de transporte.
2.1.1.1. Evaluamos las preferencias de movilidad de los viajeros, seleccionando un subconjunto relevante para un escenario de optimización de itinerarios en el mundo real, y empleamos experimentos de elección para identificar la importancia de estas preferencias para los responsables individuales de la toma de decisiones.
2.1.1.1.1. Las funciones de utilidad derivadas de estos se utilizan después para la optimización de itinerarios. Validamos nuestro método mediante simulaciones en una ciudad alemana de tamaño medio, que demostraron una mejora significativa del 16,19% en la utilidad del viaje al incorporar una función de utilidad a la optimización del itinerario en comparación con los planes basados únicamente en el tiempo de viaje.
3. Introducción y trabajos relacionados
3.1. El transporte multimodal, que incluye el transporte público, los desplazamientos a pie, en bicicleta y en coche, puede ofrecer una mayor eficiencia en términos de tiempo, costes y medio ambiente en comparación con la dependencia de un úinico modo de transporte, como el coche.
3.1.1. Los planificadores actuales se centran principalmente en la optimización de las rutas en función del tiempo y el coste del viaje y tienden a optimizar sólo un modo de transporte a la vez.
3.1.1.1. Para abordar este problema, proponemos un nuevo enfoque para generar planes de viaje personalizados que optimicen la secuencia y el calendario de las actividades diarias minimizando la desutilidad del viaje. Esto implica planificar tanto las actividades como las rutas entre ellas.
3.1.1.1.1. Utilizamos funciones de utilidad para modelar las preferencias individuales de movilidad de los usuarios. En cuanto a los métodos de optimización empleados en este campo, el Algoritmo Genético (AG) es una técnica comúnmente utilizada. En nuestro enfoque, hemos integrado el solucionador GLKH, un algoritmo de última generación de alto rendimiento para resolver TSP generalizados
4. Metodo
4.1. Flujo
4.1.1. Integración de preferencias
4.1.1.1. El planificador de itinerarios permite a los usuarios crear múltiples perfiles de preferencias que representan distintos contextos de viaje. La bibliografia de preferencias describe una amplia gama de preferencias de movilidad integradas en plataformas de movilidad, planificadores de viajes y servicios de itinerario existentes. Incluir una preferencia en el planificador de itinerarios sólo tiene sentido si puede evaluarse en un escenario de optimización real.
4.1.1.1.1. las preferencias se pueden integrar utilizando diferentes tipos de enfoques, como las restricciones basadas en reglas (RBC) y los servicios de enrutamiento como OpenTripPlanner (OTP).
4.1.2. Cuantificación de las preferencias mediante experimentos de elección
4.1.2.1. Los experimentos de elección permiten estimar la función de utilidad, que es un método cuantitativo para medir el valor percibido por el usuario de un itinerario. La utilidad total de un itinerario se calcula como la suma de las utilidades ponderadas para cada preferencia de movilidad
4.1.2.1.1. Para llevar a cabo estos experimentos, se utilizan diseños estadísticamente eficientes que permiten recopilar y modelar las elecciones individuales de los usuarios. Para personalizar las funciones de utilidad, se da a los usuarios la opción de participar en experimentos de elección generados en el paso anterior. Aplicando el software NGENE y el Algoritmo de Fedorov para generar diseños eficientes que comprenden conjuntos de elección con varias alternativas para rutas de corta y media distancia.
4.1.3. Optimización de itinerarios
4.1.3.1. El problema descrito de optimización de la cadena de actividades diurnas basado en funciones de utilidad se modela como una extensión del TSP, que es uno de los problemas de optimización combinatoria más investigados. Más concretamente, modelamos el problema como TDEGATSP-TW,
4.1.3.1.1. Definición como modelo matematico de TDEGATSP-TW
5. Resultados
5.1. Diagrama de flujo de datos
5.1.1. Al integrar funciones de utilidad basadas en las preferencias individuales de movilidad, el método logró un aumento del 16.19% en la utilidad de viaje en comparación con los métodos tradicionales que se enfocan únicamente en el tiempo de viaje. Este enfoque fue evaluado mediante simulaciones en una ciudad alemana de tamaño medio, demostrando su efectividad en mejorar la experiencia de viaje al optimizar la secuencia y el tiempo de las actividades. Además, el estudio sugiere que futuras mejoras podrían incluir la integración de datos en tiempo real y evaluaciones de escalabilidad para ampliar su aplicación.
6. Conclusiones
6.1. El planteamiento optimiza la secuencia y el calendario de las actividades diarias, incorpora diversos modos de transporte, opciones de aparcamiento y transporte altemativo y preferencias de movilidad individuales. el objetivo es ofrecer planes de viaje personalizados y eficientes que mejoren la accesibilidad y el atractivo del transporte multimodal. La simulación realizada a partir de datos reales de transporte en una ciudad alemana de tamaño medio demostró que, por término medio, nuestro método aumenta la utilidad de los desplazamientos en un 16,19%.
7. TSP-TW (Problema del Viajante de Comercio con Ventanas de Tiempo)
7.1. Visite un conjunto de n ciudades exactamente una vez
7.2. Y regrese a su ciudad de origen.
7.3. cada ciudad tiene un intervalo durante el cual debe ser visitado
8. técnicas de optimización multicriterio
8.1. se refieren a métodos que buscan optimizar simultáneamente múltiples objetivos que pueden ser conflictivos entre sí. implica considerar diversos criterios como el tiempo de viaje, el costo, las preferencias de movilidad del usuario y la utilización de diferentes modos de transporte.
9. preferencias de movilidad de los viajeros
9.1. se refieren a las elecciones y prioridades individuales que las personas tienen al planificar sus desplazamientos. Pueden incluir factores como la comodidad, el costo, el tiempo de viaje, la seguridad, la accesibilidad y la sostenibilidad ambiental.
10. experimentos de elección
10.1. se refieren a un método utilizado para cuantificar las preferencias de los usuarios al presentarles un conjunto de opciones y pedirles que elijan entre ellas
11. Las funciones de utilidad
11.1. fórmulas matemáticas utilizadas para cuantificar el valor o la satisfacción que un usuario obtiene de diferentes opciones de viaje.
12. asd
13. RBC (enfoque basado en restricciones de reglas)
13.1. se utiliza para integrar las preferencias de movilidad de los usuarios al eliminar ciertas opciones de viaje antes de calcular el itinerario. Por ejemplo, los usuarios pueden establecer reglas para evitar caminar o andar en bicicleta bajo ciertas condiciones climáticas.
14. OpenTripPlanner (OTP)
14.1. es una plataforma de planificación de rutas multimodales de código abierto, que se utiliza para ayudar a los usuarios a desplazarse de un punto a otro dentro de una ciudad o región
15. Función de utilidad
16. utilidad total
16.1. se refiere a una medida cuantitativa del valor percibido por un usuario para un itinerario específico.
17. contextos de viaje
17.1. se refiere a las circunstancias y condiciones bajo las cuales se planifican y realizan los viajes de los individuos por ejemplo los usuarios pueden crear un perfil para viajes de ocio, especificando una preferencia por rutas panorámicas, y otro para viajes de trabajo, favoreciendo rutas más cortas y cómodas.
18. Itineraios
18.1. plan detallado que indica las actividades, lugares, tiempos y medios de transporte programados durante un viaje.
19. diurnas
19.1. actividades realizadas durante el día
20. GLKH solver
20.1. Se refiere a un solucionador basado en el algoritmo Lin-Kernighan-Helsgaun (LKH) que se usa para resolver variantes del problema del viajante (TSP)
21. 1. Construcción del Problema TDEGATSP-TW : Inicialmente, se construye el problema TDEGATSP-TW, que considera las ventanas de tiempo, los clústeres de vértices y los modos de transporte disponibles. 2. Expansión temporal : Cada ventana de tiempo se expande en instantes de tiempo discretos, creando un vértice para cada posible instancia de tiempo. Esto permite considerar todas las posibles instancias de tiempo en las que se puede visitar un vértice. 3. Simplificación del Gráfico : Se crea un gráfico auxiliar que simplifica la representación antes de la expansión temporal, considerando solo algunos modos de transporte, como el automóvil y el transporte público 4. Aplicación del algoritmo GLKH : Una vez que el problema se ha reducido a EGATSP, se utiliza el GLKH Solver, un algoritmo de vanguardia para resolver el problema resultante. Este algoritmo busca identificar la ruta más eficiente en términos de costo total
22. algoritmo genetico
22.1. Técnica de optimización inspirada en la evolución biológica que se usa para encontrar el mejor itinerario posible (secuencia de actividades) entre muchas combinaciones posibles.
23. Open Cage API
23.1. Servicio de geocodificación y geocodificación inversa que se utiliza para convertir direcciones en coordenadas GPS y viceversa.
24. Overpass API
24.1. Es una herramienta clave para consultar y extraer datos geoespaciales detallados desde OpenStreetMap (OSM)
25. TomTom
25.1. se refiere al uso de los servicios de mapas y datos de movilidad proporcionados por TomTom, una empresa especializada en navegación GPS, tráfico en tiempo real, mapas digitales y APIs de localización
26. BreezoMeter API
26.1. Se utiliza para obtener información en tiempo real sobre la calidad del aire, el clima y otros factores ambientales, con el objetivo de mejorar la experiencia del viajero y optimizar la planificación del itinerario según condiciones externas.
27. (EGATSP): Problema del Viajante Asimétrico Generalizado con Selección Exacta por Grupo
27.1. es una variación avanzada del clásico problema del viajante (TSP), adaptada para itinerarios turísticos personalizados donde hay grupos de lugares equivalentes y restricciones específicas.
28. FEDOROV ALGORITHM
28.1. Selecciona un conjunto pequeño de elementos (por ejemplo, actividades turísticas) que, combinados, maximizan el valor total de la experiencia del usuario o cubren mejor sus preferencias.
29. TDEGATSP-TW: Problema del Viajante Generalizado Asimétrico con Igualdad Dependiente del Tiempo con Ventanas de Tiempo
29.1. Este modelo se utiliza para la planificación de itinerarios personalizados, considerando múltiples modos de transporte y preferencias de movilidad
30. TSP
30.1. Problema del viajante de comercio
31. Los autores son: Alexandra Wins, Lukas Barthelmes, Sascha Alpers, Christoph Becker, Martin Kagerbauer y Andreas Oberweis. El artículo fue publicado por Elsevier BV en la revista Procedia Computer Science La investigación se presentó en la 15ª Conferencia Internacional sobre Sistemas, Redes y Tecnologías Ambientales (ANT) que tuvo lugar del 23 al 25 de abril de 2023 en Hasselt, Bélgica El proyecto "MobAPlan - Mobility and Activity-based Planning Assistant" financió esta investigación, con el apoyo de la Vector Stiftung (Vector Foundation)
