Full-load route planning for balancing bike sharing systems by logic-based benders decomposition

Public bike sharing systems require some kind of rebalancing to avoid too many rental stations of running empty or entirely full, which would make the system ineffective and annoy customers. Most frequently, a fleet of vehicles with trailers is used for this purpose, moving bikes among the stations. Previous works considered different objectives and modeled the underlying routing problem in different ways, but they all allow an arbitrary number of bikes to be picked up at some stations and delivered to other stations, just limited by the vehicles’ capacities. Observations in practice, however, indicate that in larger well‐working bike sharing systems drivers almost never pickup or deliver only few bikes, but essentially always approximately full vehicle loads. Many stations even require several visits with full loads. Due to budgetary reasons, typically only just enough drivers and vehicles are employed to achieve a reasonable balance most of the time, but basically never an ideal one where single bikes play a substantial role. Consequently, we investigate here a simplified problem model, in which only full vehicle loads are considered for movement among the rental stations. This restriction appears to have only a minor impact on the achieved quality of the rebalancing in practice but eases the modeling substantially. More specifically, we formulate the rebalancing problem as a selective unit‐capacity pickup and delivery problem with time budgets on a bipartite graph and present a compact mixed integer linear programming model, a logic‐based Benders decomposition and a variant thereof, namely branch‐and‐check for it. For the general case, instances with up to 70 stations, and for the single‐vehicle case instances with up to 120 stations are solved to proven optimality. A comparison to leading metaheuristic approaches considering flexible vehicle loads indicates that indeed the restriction to full loads has only a very small impact on the finally achieved balance in typical scenarios of Citybike Wien.