Research And Implementation Of Online Balanced Assignment Algorithms For Online Car-hailing Services

With the widespread adoption of wireless network technologies and sensor devices,such as GPS,Wi-Fi,RFID,and Bluetooth,more and more vehicle recommendation systems have emerged.The historical trajectory data of vehicles can be continuously collected.By analyzing and mining these historical trajectory data,we can better improve the vehicle recommendation system.The vehicle recommendation system can better schedule between users and vehicles,perform more accurate vehicle recommendation and route planning,reduce blind driving of vehicles,increase the income of vehicles,reduce the waiting time of users,ease traffic congestion,and reduce environmental pollution.All of these have a strong practical significance.The traditional vehicle recommendation systems mainly focus on the satisfaction of users,which means that the waiting time of users is reduced as much as possible.Generally speaking,these systems tend to recommend the nearest vehicle to the user,while they ignore the fair assignment of vehicles.In this paper,by analyzing the real historical trajectory data,we find that as the number of recommendations increases,the difference in income between vehicles becomes larger.Different from the traditional vehicle recommendation system,the purpose of this paper is to recommend the request to the vehicle according to some strategies for continuously generated user requests.So that the recommendation result can not only ensure the fair assignment of vehicles,but also guarantee a short waiting time for users.However,through analysis,we found that both of them actually a trade-off problem and cannot be optimal at the same time.Aiming at the deficiencies of Brute-force algorithm and Greedy algorithm in solving this problem,this paper proposes an efficient RRA-LSP algorithm.Brute-force algorithm is a violent algorithm.For each user request,the optimal vehicle is directly searched from the entire city.This algorithm will bring a great time overhead,but it can guarantee an optimal solution.Greedy algorithm belongs to the approximate algorithm,which find a local optimal vehicle in a local range,which is centered on the request,and has a radius of 3000 meters.The algorithm is relatively fast,but it is difficult to obtain optimal results.RRA-LSP algorithm is an efficient algorithm,and it can obtain accurate solutions consistent with Brute-force.RRA-LSP algorithm first continuously narrows the search range until a certain condition is reached,and gets the final search range.Through rigorous proof,it is found that the optimal vehicle must be within the final range.Finally,we just need to find the optimal vehicle within this range,and recommend it to the passenger.For the conflict problem under the multi-user request scenario,we propose two conflict handling rules to solve the problem,and design a balanced scheduling mechanism for the allocation of multi-user requests.By comparing the experimental results on two real road network datasets,we find that the proposed algorithm can not only reduce the income difference between vehicles,but also guarantee a short waiting time for passengers.Moreover,we further validate the efficiency of RRA-LSP algorithm.Compared with the traditional vehicle recommendation algorithm,the experimental results show that the proposed algorithm can achieve a more fair recommendation result.