Design And Implementation Of A Multi-queue Model Based Order Dispatching Algorithm For Ride Sharing

Mobile taxi-hailing services,such as Didi,Uber and Lyft,have been widely welcomed at home and abroad due to their convenience and real-time responsiveness,which have significantly reduced passenger’s waiting time and driver’s cruising time.The key component module of mobile taxi-hailing service is order dispatching,which provides the best matching mode for drivers and passengers in the form of one-to-one order riding and one-to-many order carpooling.The traditional order dispatching methods focus on individual passengers,and find the most suitable driver for the current passenger at each time.Although the traditional methods can achieve the immediate optimal matching between a single passenger and a driver,for all drivers and passengers in the system,it may lead to the decrease of the overall revenue and matching rate in the system.At the same time,from a long-term perspective,it may lead to the reduction of the total cumulative revenue of the system over a long period of time.In recent years,many order dispatching methods based on reinforcement learning have emerged.They usually focus on multiple optimization objectives at the same time and can achieve the overall optimal matching of the system from a long-term perspective.However,they usually need to go through a long-term and complex training process,and when agents overfit the extrinsic reward,it will lead to poor generalization ability and can not obtain the expected effect.In addition,the traditional order dispatching usually adopts centralized matching,and the data,operation and processing tasks are completed in a centralized way.When the order demand is too large,it will lead to computational overload and low dispatching efficiency due to the high complexity of computing tasks.Although the existing order dispatching based on reinforcement learning can alleviate this problem to a certain extent by using multiple processors to realize distributed processing of orders,it is difficult to efficiently match some orders due to the load imbalance among processors.Based on the above problems,this thesis proposes a lightweight and efficient method to realize the best matching of local resources and dynamic allocation of global resources,which can maximize the overall system receiving revenue and order matching rate,and reduce driver’s cruising cost and passenger’s waiting time.Initially,this thesis regards the order dispatching as an online bipartite graph matching problem,and constructs a multi-queue model based on it.The model geographically partitions the map into multiple regions,and each region employs a separate queue.Idle drivers and order requests are put into the queue to be matched,and successful matched drivers and passengers are put into the matching pool.Then,the Ridis algorithm and Cardis algorithm proposed in this thesis construct dynamic network flow graphs for the queue to be matched,to find the minimum cost and maximum flow in the network flow graph,and achieve the best matching in each region.At the same time,in order to achieve the global allocation of resources,this thesis designs a vehicle guidance strategy based on the incremental K-means algorithm,so that drivers located at the boundaries of multiple regions and idle drivers waiting for a long time will go to the region with more orders,so as to achieve the balance of orders and drivers.In order to verify the effect of the proposed method in this thesis,this thesis builds an online order dispatching system.Then through the indicators such as the total revenue of system per day,order matching rate per day and average waiting time of passengers,and using the data provided by Didi Gaia platform,this thesis compares the effect of the proposed method with the common task processing algorithms such as Greedy,First Come First Serve（FCFS）and Random,and the effect of regional processing and centralized processing of order requests,the effect when a driver can only serve one order at the same time and can serve multiple orders with similar travel information at the same time,as well as the effect with global resource allocation and without resource allocation.The results show that compared with Greedy,FCFS and Random,the total revenue per day of the proposed method is increased by 20.3%,20.7% and 19.7% respectively,the matching rate per day is increased by 21.1%,20.7% and 20.7%,and the average waiting time of passengers is decreased by 53.4%,53.5% and 6.2%;compared with centralized processing,the total revenue per day of regional processing is increased by40.1%,the matching rate per day is increased by 27.2%,and the average waiting time of passengers is decreased by 21.2%;compared with serving a single order,when a driver can serve multiple orders at the same time,the total revenue per day is increased by82.1%,the matching rate per day is increased by 41.3%,and the average waiting time of passengers is decreased by 61.3%;compared with the case without resource allocation,the total revenue per day received with resource allocation is increased by 4.4%,the matching rate per day is increased by 4.2%,and the average waiting time of passengers is decreased by 8.4%.The method proposed in this thesis focuses on multiple optimization objectives,and realizes a lightweight riding and carpooling method based on network flow,so as to achieve the best matching between drivers and orders in each region.At the same time,dynamic resource allocation based on incremental K-means pays attention to the dynamic balance between drivers and orders in various regions,and encourages idle drivers to move to the region with the most orders,so as to improve vehicle utilization and further improve the efficiency of order dispatching.Therefore,the proposed method realizes a lighter and more efficient order dispatching method in complex environment.