ALGORITMO GENÉTICO DE MODELO ISLAS PARA EL PROBLEMA DE RUTAS DE TRÁNSITO URBANO

Abstract

Urban Transit Routing Problem es un problema de optimización combinatoria que consisteen encontrar un conjunto de rutas para una ciudad que permita a sus habitantes transportarserápida y cómodamente, mientras se mantiene un bajo costo de mantenimiento parael sistema. Es un problema NP-Duro altamente complejo. La dificultad viene en las restriccionesde número y largo de rutas que dificultan encontrar una buena solución factible. Elproblema además es de naturaleza multi-objetivo por lo que no existe una única soluciónóptima. Si no que existe un conjunto de soluciones conocido como frente de Pareto de solucionesmutuamente no dominantes.El problema ha sido abordado en el pasado con diversos enfoques: Búsqueda Local,Algoritmos Gen éticos, Colonias de Hormigas y Optimización por Enjambre de Partículas.De estos enfoques aquellos que dan mejores resultados vienen a ser algoritmos gen éticos yoptimización por enjambre de partículas.En este trabajo se presenta un Algoritmo Genético Modelo de Islas. Este es un algoritmoque trabaja sobre una población de soluciones que atraviesan fases de selección, mutación,selección y elitismo. El modelo de islas subdivide esta población en islas que funcionancomo algoritmos genéticos independientes que intercambian cada cierto tiempo un ciertonúmero de soluciones.Los parámetros del algoritmo fueron sintonizados mediante ParamILS, una técnica automática que busca obtener el mejor conjunto de valores para parámetros definidos. Otrascaracterísticas del algoritmo fueron probadas y ajustadas manualmente.El rendimiento se evaluó por medio de la comparación con un algoritmo genético equivalentey con trabajos previos. En general, se obtuvieron soluciones de buena calidad para lasinstancias más pequeñas, sin embargo para instancias más grandes del problema el algoritmopuede requerir más recursos o rediseñar ciertas características.Urban Transit Routing Problem is a combinatorial optimization problem that consistsof finding a set of routes for a city allowing their citizens to transport fast and comfortablymaintaining low operational system costs. It’s an NP-Hard problem highly complex. Its difficultycomes from restrictions of the number and length of the routes making hard to finda good feasible solution. Moreover, the problem is multi-objective hence there isn’t a singleoptimal solution. There is a set of non-dominated solutions known as the Pareto Front.The problem has been solved with different techniques: Local Search, Genetic Algorithms,Ant Colony Optimization and Particle Swarm Optimization. The best results havebeen achieved using Genetic Algorithm and Particle Swarm Optimization techniques.In this work a Genetic Algorithm Island Model was implemented. A genetic algorithmhas a population of solutions that go through phases of selection, crossover, mutation andelitism. The island model subdivides this population in islands and each one of them worksas an independent genetic algorithm. Migrations between individuals allow the exchange ofindividuals among them.The algorithm parameters were tuned with ParamILS, an automatic technique that seeksthe best set of values for the defined parameters. Other characteristics were manually testedand tuned.The performance was evaluated by comparing our approach with an equivalent geneticalgorithm and with previous works. In general, solutions of good quality were obtained forsmaller instances, however for bigger instances the algorithm might require more resourcesor redesign certain features.