Rechargeable Battery Cabinet Deployment for Public Bike System

Public Bike Systems (PBSs) offer the popular service for the short distance in daily life. The battery powered bike is an interesting and feasible method to extend the bike trip length, which can promote the PBS service but faces the challenges caused by the limited budget for the battery cabinet deployment and user demand. Thus, the realistic problem is how to deploy the cabinets near a part of public bike stations by considering the challenges. This paper is the first to study the novel problem, Cabinet Deployment Problem (CDP) in PBS, based on the features extracted from the real dataset of PBS in Hangzhou China, and proposes our strategies in the case of the Euclidean space and Manhattan model. In the Euclidean space, CDP can be specified as the ${e}$ lectric-bike Set Cover problem (e-SC), and this paper proposes a Greedy Station Coverage algorithm (GSC). Its distributed version, called the Localized Greedy Selection algorithm (LGS), is also presented because of the large amount of bike stations. In many cities, the roads have Manhattan-type directions, i.e., either east-west or south-north. In order to close to the realistic scenario, this paper develops a Genetic Algorithm based Cabinet Search algorithm (GAS) to determine the locations for the cabinet deployment in the Manhattan model. The extensive numerical experiment is conducted for our strategies, which are compared to a straightforward method, the Random Placement Strategy (RPS) under the diverse parameter settings.