Hierarchical Clustering and Multilevel Refinement for the Bike-Sharing Station Planning Problem

We investigate the Bike-Sharing Station Planning Problem (BSSPP). A bike-sharing system consists of a set of rental stations, each with a certain number of parking slots, distributed over a geographical region. Customers can rent available bikes at any station and return them at any other station with free parking slots. The initial decision process where to build stations of which size or how to extend an existing system by new stations and/or changing existing station configurations is crucial as it actually determines the satisfiable customer demand, costs, as well as the rebalancing effort arising by the need to regularly move bikes from some stations tending to run full to stations tending to run empty. We consider as objective the maximization of the satisfied customer demand under budget constraints for fixed and variable costs, including the costs for rebalancing. As bike-sharing stations are usually implemented within larger cities and the potential station locations are manifold, the size of practical instances of the underlying optimization problem is rather large, which makes a manual decision process a hardly comprehensible and understandable task but also a computational optimization very challenging. We therefore propose to state the BSSPP on the basis of a hierarchical clustering of the considered underlying geographical cells with potential customers and possible stations. In this way the estimated existing demand can be more compactly expressed by a relatively sparse weighted graph instead of a complete matrix with mostly small non-zero entries. For this advanced problem formulation we describe an efficient linear programming approach for evaluating candidate solutions, and for solving the problem a first multilevel refinement heuristic based on mixed integer linear programming. Our experiments show that it is possible to approach instances with up to 2000 geographical cells in reasonable computation times.