Energy Station Deployment Plan For City Public Bike System

As a kind of city public transportation,Public Bike System(PBS)is popular in major cities recently,due to its advantages of environmental protection,convenience,economy and so on.Therefore,it becomes a hot research topic.Due to the physical limitations of users,PBS is still limited to short trips and "solve the last kilometer"service.Most of the existing research works focus on the trip optimization and resource allocation.There is still a lack of research on the function optimization of PBS.In recent years,Hangzhou is trying to provide power services for PBS users,using rechargeable batteries to provide power for public bikes,so as to save manpower and expand users' trip range.PBS users can go to energy stations to rent batteries and use public bikes for medium and long distance rides.The energy stations deploy cabinets,which can store and charge a certain number of batteries and provide battery leasing services for users.Due to the limited budget,how to determine the number of energy stations and the deployment locations are summarized as the energy station deployment problem,which need to be solved in this paper.In order to deploy energy stations reasonably in the city to provide assistance to PBS users,the sensor network optimization theory,graph theory and operational research theory in the Internet of things are used as research tools to formalize the energy station deployment problem and design the energy station deployment plans which based on sensor network optimization and city voronoi diagram,to solve the energy station deployment problem.The research content and innovation of this paper include the following aspects:(1)This paper analyzes the operation data of Hangzhou PBS.Two station attributes are introduced firstly:user visit frequency and resource balance deviation coefficient.Then,a spatial Density based station Attribute Clustering algorithm(DAC)is used to select the public bike stations with good attributes.(2)This paper proposes an energy station deployment plan based on sensor network optimization.Under the definition of different Quality of Service(QoS)models,the energy station deployment problem is mapped to set cover problem and sensor selection problem respectlively,and these two problems are proved to be NP-hard theoretically.To solve these problems,the Greedy based Station Coverage algorithm(GSC)and Distributed Station Selection algorithm(DSS)are designed.The time and space complexity of two algorithms are analyzed theoretically.The experimental results show that the plan is feasible to be deployed in real cities.Under different parameter settings,the coverage ratio achieved by the plan and the required deployment cost are both better than the Random Placement Strategy(RPS).(3)In order to make the energy station deployment plan more consistent with the real traffic scenarios,this paper proposes the energy station deployment plan based on the city voronoi diagram.Based on map data of Hangzhou,First,the city voronoi diagram of Hangzhou is constructed,and the QoS model is designed.Then,this paper formalizes the energy station deployment problem.Finally,this paper proposes the GA-based energy station Search algorithm(GAS)to determine locations and the number of energy stations.The time and space complexity of the GAS algorithm are analyzed in theory.Experimental analysis is made on the change of the deployment cost and running time of the GAS algorithm under different parameters design.The experimental results show that the plan is feasible to be deployed in real cities.To sum up,in order to solve the energy station deployment problem for city PBS,this paper proposes energy station deployment plans based on sensor network optimization and city voronoi diagram.The designed energy deployment plans are feasible and perform well in coverage,deployment cost,algorithm running time and some other indicators.The research content of this paper has strong practical application value and is one of the directions worth exploring in the future.