A Cluster-First Route-Second Approach for Balancing Bicycle Sharing Systems

Public Bicycle Sharing Systems are booming all over the world as they provide a green way of commuting in cities. However, itis a challenging task to keep such systems in a balanced state, which means that people can rent and return bikes where and when they want. Usually, operators of these systems rebalance them actively by moving bikes using vehicles with trailers. They plan routes around the city so that technicians can move bikes from full stations to empty ones. In contrast to previous work we address this issue by a novel simpli ed Problem de nition in conjunction with a Cluster-First Route-Second approach. It is an exact algorithm utilizing logic-based Benders decomposition where we solve an Assignment Problem as master problem and Traveling Salesman Problems as subproblems. Results show that we are able to solve instances with up to 60 stations which was not possible with previous problem de nitions.