A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems

Bicycle sharing systems are transportation systems that allow the users to rent a bicycle at one of many automatic rental stations scattered around the city, use them for a short travel and return them at any station. A crucial factor for the success of such a system is its ability to ensure a good quality of service to users. It means the availability of bicycles for pick-up and free places to return them. This is performed by means of a rebalancing operation, which consists in removing bicycles from some stations and transferring them to other stations, using dedicated vehicles. In this paper, we study the rebalancing vehicles routing problem by considering the static case. Vehicles conduct tours between stations to return them to their desired levels, which are known in advance, and each station must be visited exactly once and only once by a vehicle. This problem is similar to the traveling salesman problem with additional constraints. The aim is to find an optimal scheduling of the vehicle that minimizes the total waiting time of the stations in disequilibrium states. We propose several lower and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method. (C) 2016 Elsevier Ltd. All rights reserved.