Optimización de rutas de distribución de bicicletas entre las estaciones de BiciMAD aplicando el algoritmo de la colonia de hormigas

Abstract

La finalidad del presente trabajo es optimizar la ruta de reposición de bicicletas entre las estaciones del servicio BiciMAD. Para ello se elige implementar el algoritmo de optimización de la colonia de hormigas, ya que este algoritmo ha demostrado su eficacia para la resolución de problemas similares de optimización de rutas. La implementación de esta solución, así como de otras soluciones alternativas no basadas en este algoritmo que se utilizarán para evaluar su eficacia por comparación, se ha desarrollado en Python, tomando como conjunto de pruebas un archivo CSV que contiene todas las estaciones de BiciMAD correspondientes a junio de 2018. El estudio de los resultados obtenidos mediante este algoritmo comparados con otros no basados en la colonia de hormigas, demuestra que se obtienen rutas más cortas y, por lo tanto, mejores. En conclusión, el algoritmo desarrollado en el presente trabajo es adecuado y efectivo para la resolución de este problema.

The main purpose of this research paper is to find the best route for restoring the bicicles in all of the BiciMAD stations. In order to do so, the Ant Colony Optimization algorithm is chosen, on the grounds that it's known to work well with route optimization problems. This algorithm, as well as other non ACO solutions developed for evaluation purposes, is coded in Python using as a data set a CSV file containing all the BiciMAD stations for June 2018. The comparative analysis of the results of both, ACO and non ACO solutions, shows that the Ant Colony Optimization algorithm finds shorter and thus, better routes. In conclusion, the ACO algorithm developed for this paper proves to be suitable and effective to solve this problem.

La finalitat del present treball és optimitzar la ruta de reposició de bicicletes entre les estacions del servei BiciMAD. Per a això es tria implementar l'algorisme d'optimització de la colònia de formigues, ja que aquest algorisme ha demostrat la seva eficàcia per a la resolució de problemes similars d'optimització de rutes. La implementació d'aquesta solució, així com d'altres solucions alternatives no basades en aquest algorisme que s'utilitzaran per a avaluar la seva eficàcia per comparació, s'ha desenvolupat en Python, prenent com a conjunt de proves un arxiu CSV que conté totes les estacions de BiciMAD corresponents a juny de 2018. L'estudi dels resultats obtinguts mitjançant aquest algorisme comparats amb uns altres no basats en la colònia de formigues, demostra que s'obtenen rutes més curtes i, per tant, millors. En conclusió, l'algorisme desenvolupat en el present treball és adequat i efectiu per a la resolució d'aquest problema.