A Novel Approach for Solving Large-Scale Bike Sharing Station Planning Problems

In large cities all around the world, individual and motorized traffic is still prevalent. This circumstance compromises the quality of living, and moreover, space inside cities for parking individual vehicles for movement is scarce and is becoming even scarcer. Thus, the need for a greener means of transportation and less individual vehicles inside the cities is demanded and rising. An already accepted and established solution possibility to these problems are public bike sharing systems (PBS). Such systems are often freely available to people for commuting within the city and utilize the available space in the city more efficiently than individual vehicles. When building or extending a PBS, a certain optimization goal is to place stations inside a city or a part of it, such that the number of bike trips per time unit is maximized under certain budget constraints. In this context, it is also important to consider rebalancing and maintenance costs as they introduce substantial supplementary costs in addition to the fixed and variable costs when building or extending a PBS. In contrast to the literature, this work introduces a novel approach which is particularly designed to scale well to large real-world instances. Based on our previous work, we propose a multilevel refinement heuristic operating on hierarchically clustered input data. This way, the problem is coarsened until a manageable input size is reached, a solution is derived, and then step by step extended and refined until a valid solution for the whole original problem instance is obtained. As an enhancement to our previous work, we introduce the following extensions. Instead of considering an arbitrary integral number of slots for stations, we now use sets of predefined station configurations. Moreover, a local search is implemented as refinement step in the multilevel refinement heuristic and we now consider real-world input data for the city of Vienna.