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.
| Identifer | oai:union.ndltd.org:uns.edu.ar/oai:repositorio.bc.uns.edu.ar:123456789/1979 |
| Date | 09 October 2009 |
| Creators | Olivera, Ana Carolina |
| Contributors | Brignole, Nélida Beatriz |
| Publisher | Universidad Nacional del Sur |
| Source Sets | Universidad Nacional del Sur |
| Language | Spanish |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation, Text |
| Rights | 0 |
Page generated in 0.0025 seconds