Desarrollo teórico de técnicas meta-heurísticas para resolver problemas de optimización "TN" (Transit Networks) en entornos dinámicos

Abstract

El objetivo general de esta tesis fue desarrollar técnicas meta-heurísticas híbridas para el tratamiento de problemas NP-Hard relacionados con el problema de la red de tránsito (Transit Network Problem: TNP). Estas técnicas están orientadas, en particular, a las dos etapas más importantes del TNP: el diseño y la planificación (Transit Network Design and Scheduling Problem: TNDSP) de la red. El objetivo principal fue proveer una herramienta automatizada para la creación tanto de las rutas de las líneas de la red de tránsito como de la frecuencia de los móviles. Como resultado colateral de esta tesis se logró además subsanar una deficiencia de los trabajos existentes sobre TNP: su incapacidad para obtener resultados que reflejen la dinámica de las variables que dependen de los tiempos consumidos por el usuario en su espera, acceso y viaje dentro de la red. Esta tesis analiza dichas falencias y presenta como solución la posibilidad de incorporar un elemento dinámico dentro de la resolución del TNDSP. De este modo, se han podido obtener resultados realistas tanto desde el punto de vista del operador del servicio como así también del cliente. En base a nuestras investigaciones, se obtuvo un algoritmo híbrido evolutivo dinámico multi-objetivo de dos etapas que tiene en cuenta tanto al operador como a los clientes de la red. La primera es una etapa de inicialización de distancias y rutas entre paradas a través de un novedoso procedimiento GRASP (Greedy Randomized Adaptive Search Procedure). La segunda es una etapa que implementa un nuevo algoritmo evolutivo que contiene un procedimiento de simulación para el cálculo de la función de aptitud (fitness) de los individuos. Finalmente, se estudiaron algunas ciudades hipotéticas estableciendo la mejor configuración de parámetros para las fases del algoritmo híbrido y se analizó un caso real utilizado en la literatura para comparar nuestra metodología con los procedimientos más conocidos sobre el tema, mostrando resultados altamente satisfactorios.

The general purpose of this thesis was to develop meta-heuristic hybrid techniques for the treatment of NP-hard problems related to the Transit Network Problem (TNP). These techniques are particularly oriented to the most important TNP stages: the design and planning of the network (Transit Network Design and Scheduling Problem: TNDSP). The main goal was to provide a tool for the creation of both the routes for the transit network lines and the mobile frequency. Also, the work performed in this thesis contributes to eliminate a deficiency in the existing work about TNP: the inability to yield results that reflect the dynamics of the variables that depend on the time taken by the users while they are waiting, accessing and tripping within the network. This thesis analyses this dearth and proposes as a solution the possibility of incorporating a dynamic element to the manner of solving the TNDSP. In this way, realistic results could be obtained from the viewpoint of both the service operator and the client as well. On the basis of our research, a hybrid dynamic two-stage evolutionary algorithm was obtained. In the network, it takes into account both the operator and the clients as well. The first stage is an initialization of the distances and routes between stops through a GRASP (Greedy Randomized Adaptive Search Procedure). The second stage implements an evolutionary algorithm that contains a simulation procedure for the calculation of the individuals fitness. Finally, some hypothetical cities were studied by establishing the best parameter configuration for the phases of the hybrid algorithm. A real case, which is classic in the literature, was analyzed in order to compare our method against the well-known approaches used to solve these problems. The results of this analysis were highly satisfactory.