Research And Implementation Of Mobile Route Recommendation Algorithm For Vehicle Sharing

With the accelerating of urban modernization and the growing of urban population.People often encounter traffic jams during rush hours and difficulty in taking a taxi in the morning and evening of our daily life.However,with the popularity of wireless intelligent devices such as GPS,Wi-Fi,RFID and Bluetooth,mobile trajectory data are collected by the information system of industry continuously.Thus the big data collection and analysis are of great help to cities facing troubles and challenges.The decisions that the urban traffic management has made are of importance to the public transportation.This thesis focuses on the recommendation of the mobile route planning on vehicle sharing.And the purpose is to maximize the driver's profits by combining passengers from different locations and at the same time according with specified conditions as one request group.Solving this besetting problem is of practical significance for the alleviation of taxi-hailing difficulty,low utilization of car seats,environmental pollution and traffic jam.In this thesis,two methods are designed to solve this problem,which are exact algorithm and the approximate algorithm based on simulated annealing.In the exact algorithm,Three stage are included to solve this problem which are combination and pruning,compatibility and pruning,calculation and recommendation The first stage calculates all the combination of passenger's requests and pruning the request groups based on the capacity of vehicle.The capacity of the vehicle means that the sum of the passenger in a request group should be less than the capacity of the vehicle.The second stage judges whether a request group satisfies the condition of compatibility.The compatibility means that all the path sequence in a request group can link to one common path.Thus,the Match algorithm and Compatibility algorithm are designed.The third stage calculates the profit of each request group based on the profit function and recommends the max profit group to the driver.So the Scanning algorithm comes into use.In addition,a method named SA Group Search is proposed through analyzing the procedures of simulated annealing algorithm.The key of this method is to solve how to produce a new feasible solution.Therefore,we design the Produce algorithm to produce a new feasible solution according to the constraints.Experimental results on two real and one synthetic data sets shows that two methods proposed in this thesis can solve the problem of the recommendation of mobile route planning on carpooling.And it has great effect on improving the utilization rate of vehicle seats and increasing the driver's income.Also,by comparing the distance between two shared vehicles,the environmental pollution is mitigated.In the case of a large number of user requests,approximate algorithm proves to be effective.