An algorithm based on granular tabu search for the problem of balancing public bikes by using multiple vehicles

Un algoritmo basado en búsqueda tabú granular para el problema de balanceo de bicicletas públicas usando múltiples vehículos

The use of public bicycle systems has gained great importance in European countries and around the globe; this has led to the need to seek advanced techniques to help decision making. A public bicycle system consists of a set of points where you can pick up and deliver bicycles; a headquarters where a group of vehicles taking leftover bikes and transported to the points where a deficit (the demand exceeds supply) exists. One of the major problems that arise in systems of public bike is balanced, which involves sending bikes from the point where an offer (bicycles left over) to the point where there is a demand (bikes missing) occurs. The way to model this problem is with an adaptation of the vehicle routing problem with pickup and delivery (VRPPD), allowing each route make partial deliveries to customers and limiting the number of customers to visit by each route. In this paper an integer linear programming model is introduced and a metaheuristic based on granular tabu search to find a local optimum. Instances from 15 to 500 customers adapted from the literature are used. The computational results show that the proposed algorithm finds solutions in short computational time.

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.