Acercamientos de inteligencia artificial para el problema de diseño de rutas de turismo con ventanas de tiempo y restricciones de categorías, obligatoriedad, precedencia, implicancia y exclusión

Abstract

En este trabajo de memoria se estudia una extensión al problema bien conocido de diseño de rutas de turismo. A la versión original del problema le fueron integradas una serie de restricciones basadas en ventanas de tiempo, categorías de tipos de puntos de interés, puntos de interés obligatorios, y de precedencia, implicancia y exclusión entre punto de interés. Para resolver el problema se presentan dos propuestas de solución. La primera basada en la implementación del modelo matemático del problema en una herramienta basada en técnicas de resolución basadas en programación de restricciones proporcionada por Google llamada OR-Tools y una adaptación del algoritmo heurístico conocido como GRASP. Para evaluar la calidad de los acercamientos propuestos se compararon los resultados de las técnicas propuestas con la resolución mediante Gurobi de la implementación del modelo en AMPL. La comparación fue realizada sobre 113 instancias distintas organizadas en tres conjuntos de pruebas. Se obtuvo como resultado una mejora en los resultados de OR-Tools con respecto a AMPL. Por otro lado el algoritmo GRASP obtuvo resultados positivos en comparación con OR-Tools, sin perder mucha calidad y consiguiendo tiempos de ejecución significativamente menores.

In this work, an extension to the well-known tourism route design problem is studied. A series of restrictions based on time windows, categories of interest point types, mandatory interest points, and precedence, implication and exclusion between interest points were integrated into the original version of the problem. To solve the problem, two solution proposals are presented. The first one is based on the implementation of the mathematical model of the problem in a tool based on resolution techniques based on constraint programming provided by Google called OR-Tools and an adaptation of the GRASP heuristic algorithm. To evaluate the quality of the proposed approaches, the results of the proposals were compared with the resolution using Gurobi of the model implementation in AMPL. The comparison was carried out on 113 different instances organized into three test sets. The iii results show an improvement in the quality of solutions obatained by of OR-Tools with respect to AMPL. On the other hand, the GRASP algorithm obtained positive results compared to OR-Tools, without losing much quality and achieving significantly shorter execution times.