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

• We consider the vehicles scheduling problem in bicycle sharing systems.
• We define and formulate a mathematical model to minimize both the operational cost and the waiting times of the stations in disequilibrium states.
• Several lower and upper bounds were proposed and incorporated in a branch-and-bound algorithm.
• The obtained results are optimal up to 30 stations within a reasonable amount of computation time.
• The branch-and-bound algorithm can be converted into a fast greedy search heuristic suitable for large instances.

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.