Algoritmos heurísticos para un SaaS de planificación de viajes multidestino

Abstract

El crecimiento del mercado aéreo y la accesibilidad al turismo en las últimas décadas han planteado nuevas oportunidades y desafíos. Poder cotizar viajes de forma gratuita y desde la comodidad del hogar ha cambiado la manera en que las personas planifican sus viajes, adecuándolos a sus necesidades y preferencias. Esto ha impulsado el deseo de encontrar la mejor combinación de boletos para viajes multidestino, como aquellos con el menor precio o tiempo de vuelo. Mas, aún cuando se disponga de herramientas de búsqueda inteligentes, encontrar los boletos requeridos entre un mar de opciones resulta una tarea abrumadora, donde difícilmente se encuentra el itinerario idóneo. En este contexto, Trip Optimizer se presenta como una plataforma diseñada para ir más allá en esta labor, resolviendo el problema de optimización de planificación de viajes en cuestión de minutos. Dicho esto, aunque encontrar itinerarios optimizados con tal velocidad parezca ser una proeza insuperable, el trabajo a continuación propone encontrar recomendaciones igualmente buenas en tan solo segundos.

El enfoque central de esta tesis se basó en presentar dos familias de algoritmos heurísticos dedicadas a la recomendación de itinerarios de viaje. Para estas se han definido rutinas de construcción agilizadas, basadas en la generación de nuevas soluciones a partir de la última construida, con objetivo de reducir la redundancia en el modelo. Asimismo, los métodos incorporan procesos de mejora iterativa basados en Simulated Annealing, los que permiten sobreponerse a mínimos locales y generalizar la exploración de soluciones. Dentro de este espacio de diseño, se tomó la oportunidad de modificar el criterio por el cual un boleto de viaje es seleccionado, pasando de una metodología Greedy de la métrica de interés a un criterio relajado, basado en el incumpliendo de la duración de estadía en destino. A pesar que esto podría generar soluciones ligeramente infactibles, en la práctica este proceso ha demostrado mejoras para alcance del espacio de solución, permitiendo acceder a itinerarios considerablemente mejores sin perjudicar la experiencia del usuario. Esto es evidenciado con lo obtenido de un conjunto de instancias de casos reales, donde los métodos diseñados alcanzan resultados sobresalientes en términos de consistencia, exactitud con respecto al valor óptimo y tiempo necesario para llegar a estos.

Complementariamente, se puso a prueba la capacidad de los algoritmos para resolver itinerarios artificiales con un mayor número de destinos que en las instancias anteriores, con el objetivo de evidenciar los límites de cada método y el impacto real de las reglas de diseño de las nuevas heurísticas. Los resultados obtenidos contrastaron el desempeño de los diferentes métodos de prefactibilidad y resolución, permitiendo resolver casos de hasta 10 destinos sin comprometer la calidad de solución ni los recursos necesarios para llegar a estos, confirmando que las heurísticas creadas para este trabajo tienen el potencial de escalar la cantidad de destinos que Trip Optimizer puede contemplar.

El documento finaliza recapitulando lo presentado a lo largo del proyecto de tesis, planteando el beneficio de implementar las heurísticas desarrolladas en el sistema y presentando las oportunidades de innovación a partir del trabajo futuro surgidas de este mismo.