Diseño de una ruta turística, con inclusión de arcos, ventanas de tiempo y congestión

Abstract

In this thesis, the Tourist Trip Design Problem (TTDP) is studied, considering the time windows of the POIs (points of interest), the different modes of transport to go from one POI to another, the moments of congestion in each of them and the tourist arcs that may belong to the route, with the objective of maximizing customer satisfaction. We propose a mathematical model of linear enter-mixed programming and a heuristic method with a VND for local search, including an exact method for selection of arrival times and a method with multiple starts as a measure of diversification. A computational comparison is made between these two methods using instances built with actual POI information from the city of Bogotá. The computational experiments evaluate the performance of both methods in terms of the objective function and the resolution time in seconds. The results show a good performance of the heuristic method, reaching the optimum for the smallest instances and with a gap of less than 1% for those who do not. For bigger instances, the heuristic method finds good solutions in a reasonable time of computation.