Aplicació d'un algoritme genètic per a l'optimització de les estacions de xarxes de bicis urbanes

Abstract

Les xarxes de bici urbanes són un punt central en moltes ciutats, grans o petites, per tal de reduir la contaminació ja que permeten fer recorreguts curts i mitjans de forma còmode sense necessitat del vehicle privat o el transport públic. És per aquest motiu que esdevé molt important tenir una bona xarxa que permeti que els usuaris puguin realitzar els seus desplaçament i en facin ús. En aquest treball s'analitza una xarxa ja existent i es desenvolupa i s'aplica un algoritme genètic que permet optimitzar les diferents estacions o punts de servei. Es creuen dades reals de les estacions d'una ciutat amb els viatges que s'hi van realitzar en un període de temps. La funció objectiu que es minimitza són els viatges fallits, que poden ser viatges que no s'haurien pogut realitzar perquè en aquell moment no hi havia bicis a l'estació o els viatges que no s'haurien pogut finalitzar perquè no hi havia espais lliures. Els cromosomes de la població tenen dos al·lels, un amb els espais de l'estació i l'altre amb el nombre de bicis a l'iniciar el dia. Es tracta d'un problema complex de resoldre els resultats del qual han estat molt bons, ja que, tot i executar-se amb poques generacions i una població inicial no gaire gran, s'ha millorat molt el resultat si es fa servir la xarxa real. Per aquest motiu es podria considerar que es tracta d'un bon algoritme per resoldre aquest tipus de problemes d'optimització.

Urban bike-sharing is a central point in many cities in order to reduce pollution because it allows citizens to travel medium and short distances without using private car or public transport. For that reason, is important to have a good network to carry user's travels to make it useful. This work analyses an existent network and develops and applies a genetic algorithm to optimize all the bike stations. Real data of the trips and the stations are joined in a period to evaluate the algorithm. The Objective function is to minimize failed trips, which means that a user could not start because there is not a bike at that station or that a user could not finish because there are not empty docks. Chromosomes have two alleles, one with docks at station and the other with the number of bikes at the beginning of the day. The results of the algorithm applied to these complex problems are quite good because even executing with a few generations and small initial population it improves the real network results. Therefore, we could consider that a genetic algorithm is a good choice to resolve that kind of optimization problems.

Las redes de bici urbanas son un punto central en muchas ciudades, grandes o pequeñas, para reducir la contaminación puesto que permiten hacer recorridos cortos y medianos de forma cómodo sin necesidad del vehículo privado o el transporte público. Es por este motivo que acontece muy importante tener una buena red que permita que los usuarios puedan realizar sus desplazamiento y hagan uso. En este trabajo se analiza una red ya existente y se desarrolla y se aplica un algoritmo genético que permite optimizar las diferentes estaciones o puntos de servicio. Se creen datos reales de las estaciones de una ciudad con los viajes que se realizaron en un periodo de tiempo. La función objetivo que se minimiza son los viajes fallidos, que pueden ser viajes que no se habrían podido realizar porque en aquel momento no había bicis a la estación o los viajes que no se habrían podido finalizar porque no había espacios libres. Los cromosomas de la población tienen dos alelos, uno con los espacios de la estación y otro con el número de bicis al iniciar el día. Se trata de un problema complejo de resolver los resultados del cual han estado muy buenos, puesto que, a pesar de ejecutarse con pocas generaciones y una población inicial no muy grande, se ha mejorado mucho el resultado si se usa la red real. Por este motivo se podría considerar que se trata de un buen algoritmo para resolver este tipo de problemas de optimización.