Metaheurísticas aplicadas a problemas de transporte

Abstract

La idea central de esta tesis consiste en aprovechar las técnicas metaheurísticas para resolver problemas reales asociados al transporte. Por ende, en esta investigación hemos incluido el desarrollo de algoritmos metaheurísticos, su diseño, aplicación y testeo del software. Los problemas de transporte se caracterizan por su difícil tratamiento, con respecto a su modelado. En particular, en Argentina, la calidad del servicio de transporte público ha sido considerada históricamente como inadecuada, encontrándose típicamente asociada a un reclamo continuo por parte de la sociedad. Por lo tanto, la principal línea de investigación aquí tratada se relaciona con el transporte público de pasajeros, particularmente concentrándose en las localizaciones de las paradas de colectivos y en el establecimiento de las rutas que servirán para prestar un mejor servicio, minimizando los costos globales. Como última parte de nuestras investigaciones, creamos una hiperheurística eficiente basada en el análisis de desempeño de distintas metaheurísticas, cuyos algoritmos individuales desarrollamos y testeamos en primera instancia. Se consideraron las siguientes metaheurísticas: Algoritmos Genéticos, Recocido Simulado y Optimización por Colonia de Hormigas. Como resultado hemos obtenido una técnica hiperheurística que resuelve exitosamente el problema de localización y ruteo para el transporte público. El algoritmo propuesto selecciona y aplica la metaheurística apropiada para cada momento, a fin de obtener un proceso de búsqueda exitoso. Comparaciones con procedimientos bien establecidos reflejan el impacto de un procedimiento hiperheurístico sobre la optimización completa. Las principales contribuciones de esta tesis se pueden resumir como sigue: * Nuevas propuestas para el tratamiento de un problema que aqueja a gran parte de la población mundial como lo es el transporte público. * Aplicación exitosa del enfoque en problemas de transporte no relacionado a las personas, tal como la localización de cañerías. * Técnicas que reducen el número de evaluaciones improductivas mediante la implementación de una memoria interna. * Novedosa selección de vecinos que acelera el proceso de búsqueda. * La capacidad de enlazar nuestra propuesta con software externo. * Estrategia paralela que ofrece notables mejoras en cuanto al tiempo de cómputo a la vez que optimiza los recursos disponibles

The thesis statement concerns taking advantage of metaheuristic techniques as a means to solve realistic problems associated to transport. Then, in this research we have included the development of metaheuristic algorithms, their design, application and software testing. Transport problems are characterized by their difficult treatment, as regards their modeling. In particular, in Argentina, the quality of public transport service has historically been deemed inadequate, being typically marked by continual social demands. Therefore, the main points that this research covered is related to public transport of passengers, particularly concentrating on bus-stop locations and bus-route design so as to offer a better service while minimizing global costs. As the last part of our research work, an efficient hyper-heuristics was created on the basis of the performance analysis of various meta-heuristics, whose individual algorithms were firstly developed and tested. The following meta-heuristics were considered: Genetic Algorithms, Simulated Annealing and Ant Colony Optimization. As a result, we have obtained a hyperheuristic technique that succeeds in solving the location and routing problem for the public transport. The proposed algorithm chooses and applies the most adequate metaheuristic at any time instance, in order to obtain a successful search process. The comparisons with the well-established procedures reflect the impact of a hyperheuristic procedure on the optimization as a whole. The main contributions of this thesis can be summarized as follows: * New proposals for the treatment of a problem that concerns a wide amount of the world population, like the public transport. * Successful application of this approach to transport problems unrelated to persons, like pipeline routing. * Techniques that reduce the number of unproductive evaluations by means of an internal memory implementation. * Novel neighbour choice that speeds up the search process. * The capacity to link our proposal with external software. * Parallel strategy that offers noteworthy improvements as regards computing times, while optimizing the available resources