UN ALGORITMO BASADO EN BúSQUEDA TABú GRANULAR PARA EL PROBLEMA DE BALANCEO DE BICICLETAS PúBLICAS USANDO MúLTIPLES VEHíCULOS

摘要

El uso de sistemas de bicicletas públicas ha cobrado gran importancia en países europeos y alrededor de todo el planeta; esto ha llevado a la necesidad de buscar técnicas avanzadas que ayuden a la toma de decisiones. Un sistema de bicicletas públicas consiste en un conjunto de puntos donde se pueden recoger y entregar bicicletas; un depósito central donde existe un conjunto de vehículos que toma las bicicletas sobrantes y las transportan a los puntos donde exista un déficit (es decir que la demanda supera la oferta). Una de las grandes problemáticas que se presentan en los sistemas de bicicletas públicas es el balanceo, que consiste en enviar bicicletas desde los puntos donde se produce una oferta (bicicletas que sobran) hacia los puntos donde existe una demanda (bicicletas que faltan). La forma de modelar este problema es con una adaptación del problema de ruteo de vehículos con recolección y entrega de mercancías (VRPPD), permitiendo que cada ruta realice entregas parciales a los clientes y limitando el número de clientes a visitar por ruta. En este artículo se introduce un modelo de programación lineal entera mixta y una metaheurística basada en una búsqueda tabú granular para encontrar soluciones. Se usan instancias desde 15 a 500 clientes adaptadas de la literatura. Los resultados computacionales evidencian que el algoritmo propuesto encuentra soluciones en tiempos acotados de cómputo.