Large neighborhood search for the multi-vehicle bike-repositioning problem

Abstract

Traffic congestion and emissions are major problems in many urban cities around the world. To alleviate these problems, many cities have introduced bike-sharing systems. Bike-sharing makes it possible for people to use shared bikes for “first-mile” and “last-mile” trips, where bikes are retrieved and parked at any of the stations within the bike-sharing network. One major challenge with these systems is that they cannot keep up with overwhelming demand of vacant bikes and/or vacant parking slots. Hence, vehicles are used to pick-up bikes from surplus stations and transport them to deficit stations in order to satisfy a certain service level. This operation is called a bike-repositioning problem. In this paper, we propose a large neighborhood search for the bikerepositioning problem. Several ruin and recreate operators are proposed to diversify the search. A simple tabu search is further applied to the most promising solutions. The heuristic was tested on two sets of instances up to 200 stations and three vehicles. Preliminary results show that this heuristic outperforms both CPLEX and a math heuristic using much less computing time.