Local Ratio based Distributed Bike-dock Pair Allocation in Public Bike System

摘要：

　　Public bike system(PBS)is widely deployed in the world because of relieving city last-mile problem and offering con-venient short trip service.However,as PBS getting popular,the phenomenon of resources imbalance shows the trend of increasing gradually at recent years.This problem means that users will not able to rent or return bikes when they come to empty or full stations.Furthermore,this terrible problem is against to the PBS operators'targets—offering service to as much users as possible and saving users'trip time.We formu-late above problem with two practical targets as a bike-dock pair allocation(BDA)problem.In this problem,we allocate bike-dock pair to users to fulfill above two targets.We design a BDA algorithm with the local ratio technique and prove that is 3-approximated for BDA problem.Furthermore,we propose the distributed version of the BDA algorithm.The real data experiment shows our distributed bike-dock pair allocation(DBDA)algorithm can save 29.44%of time for each trip in average and help 98.05%of users successfully use PBS service.

关键词： Station Pair Allocation Public Bike System Local Ratio Technique

作者: Pengqian Lu Jianhui Zhang Siwen Zheng Tianyu Zhang

作者单位: College of Computer Science&Tech.,Hangzhou Dianzi University,Hangzhou 310018 China.

会议类型: 国际会议

会议名称: 2019国图灵大会(ACM Turing Celebration conference-China 2019 )

会议地点: 成都

会议语种:英文

页码: 463-467

在线出版日期: 2019-05-17（万方平台首次上网日期，不代表论文的发表时间）