Mobile Crowd Computing Based Trip Planning Algorithm And Implementation For Public Bike System

With the increasing awareness of environmental protection and green commuting,people all over the world prefer to use the public bike system(PBS)as a means of transportation for short-distance travel.However,the rapid increase of user quantity and their usage has made PBS overwhelmed.As a result,there may no available bikes to borrow or docks to return.From the perspective of public bike users,trip planning is more valuable than resources prediction or redistribution since they can complete the trip by knowing exactly where to borrow or return bikes.Furthermore,the user behavior information collected by the public bike company is not comprehensive and there may exist delays.It makes the dataset not updated in time,which leads to some difficulties in the usage of PBS.As a core technology of urban data sensing and collection,crowd sensing and computing can alleviate the drawbacks caused by the above problems effectively.This thesis applies mobile crowd computing and combines the widespread smartphone to enable users to upload the information actively during their trips,which effectively reduces the bother of incomplete information.To plan rational trips for users while improving the service quality of PBS,this thesis designs static algorithms and online algorithms to address the trip planning problem from the system-wide resources.With these algorithms,a crowd computing based public bike guiding system is constructed.The main work and contributions of this thesis are as follows:(1)The mobile crowd computing method used in this thesis can obtain more information than traditional techniques.And this is the first work that addresses the trip planning problem in PBS which considers three segments including two walking segments and a cycling segment.(2)This thesis formulates the static trip planning problem in PBS as the well-known weighted k-set packing problem which is known to be NP-hard.A Greedy Trip Planning algorithm(GTP)and a Humble Trip Planning algorithm(HTP)are designed in this thesis to solve this problem.Extensive simulations are conducted based on the real dataset of Hangzhou PBS.The results reveal that GTP and HTP shorten the average trip time(ATT)by 39.2% and 17.6% respectively.The allocated trips(AT)could reach the upper limit of 82.8% and 83.7% respectively.(3)With the consideration of the real-world usage of the PBS,this thesis designs an Online Matching Trip Planning algorithm(OMTP)and an Online Flowing Sequence Trip Planning algorithm(OFSTP)respectively based on the online matching model and the dynamic network-flow model.It has been proved in this thesis that the bound of OMTP is 1-1/ e.To evaluate the performance of the online algorithms,the thesis conducts extensive simulations based on the dataset of Citi Bike in New York City.It shows that the the average successful service ratio(SSR)of OMTP is 81.1%,which is lower than the static algorithm by 4.2%.The SSR of OFSTP is 91.9%,which outperforms OMTP.(4)This thesis constructs a mobile crowd computing based public bike guiding system.Users could upload the behavior or station information with their smartphones while using PBS.The server of the system updates the dataset in real-time and generates a complete trip with three segments when receiving the trip planning requests.It is the first work who offers users the complete trip in PBS.To sum up,the guiding system and the work of static and online algorithms designed in this thesis are state-of-the-art and worthy.It can minimize the trip time of users while maximizing the served quantity and improve the service quality of PBS.