Este proyecto aborda el problema de optimización de la distribución de bicicletas en el sistema de Bicing. El objetivo principal es mejorar la forma en que las bicicletas se distribuyen en las estaciones para garantizar que los usuarios siempre tengan acceso a ellas cuando las necesiten. Para lograr esto, hemos implementado y evaluado varias estrategias utilizando algoritmos de búsqueda local.
El estado se representa como una asignación de rutas a furgonetas que pasan por estaciones recogiendo o dejando bicicletas en ellas. Utilizamos las siguientes estructuras de datos:
- Estaciones: Información sobre las estaciones de la ciudad.
- Rutas: Array de recorridos para cada furgoneta, representados como tripletas de paradas.
- Paradas: Información sobre cada parada en una ruta.
- Vectores Auxiliares:
startStationsyimpactStationspara optimización rápida. - Matriz de Distancias: Distancias pre-calculadas entre estaciones para eficiencia.
Hemos implementado cuatro operadores esenciales para la modificación de las rutas:
- addStop(int van, int station): Añade una estación al final de la ruta de una furgoneta.
- removeStop(int van): Elimina la última estación de la ruta de una furgoneta.
- switchStop(int van, int pos, int newStation): Sustituye una estación en una posición específica de la ruta de una furgoneta.
- jumpStartRoute(int van, int origStation, int destStation): Inicia una nueva ruta desde una estación de origen a una de destino.
Para encontrar una solución inicial, hemos desarrollado una estrategia basada en criterios heurísticos que permiten una aproximación rápida y eficiente al problema.
Implementamos varias funciones heurísticas para evaluar y mejorar las soluciones obtenidas. Estas funciones consideran factores como la distancia, la demanda de bicicletas en cada estación y las capacidades de carga de las furgonetas.
Realizamos diversos experimentos para determinar el conjunto óptimo de operadores. Evaluamos combinaciones de operadores para encontrar las que ofrecen los mejores resultados en términos de eficiencia y calidad de la solución.
Probamos diferentes estrategias para establecer la solución inicial y comparamos su efectividad.
Ajustamos y evaluamos los parámetros para el algoritmo de Simulated Annealing, optimizando su rendimiento para nuestro problema específico.
Analizamos cómo varía el tiempo de ejecución del algoritmo en función del tamaño del problema, considerando el número de estaciones y furgonetas involucradas.
Comparamos distintos heurísticos para determinar cuál ofrece los mejores resultados en diferentes escenarios.
Evaluamos la efectividad de las soluciones durante las horas punta, cuando la demanda de bicicletas es máxima.
Determinamos el número óptimo de furgonetas necesario para cubrir la demanda de bicicletas en la ciudad de manera eficiente.
Nota: Para más detalles sobre la implementación y los resultados de los experimentos, consulte el documento completo adjunto.