A Matching Algorithm with Reinforcement Learning and Decoupling Strategy for Order Dispatching in On-Demand Food Delivery

The on-demand food delivery(OFD)service has gained rapid development in the past decades but meanwhile encounters challenges for further improving operation quality.The order dispatching problem is one of the most concerning issues for the OFD platforms,which refer to dynamically dispatching a large number of orders to riders reasonably in very limited decision time.To solve such a challenging combinatorial optimization problem,an effective matching algorithm is proposed by fusing the reinforcement learning technique and the optimization method.First,to deal with the large-scale complexity,a decoupling method is designed by reducing the matching space between new orders and riders.Second,to overcome the high dynamism and satisfy the stringent requirements on decision time,a reinforcement learning based dispatching heuristic is presented.To be specific,a sequence-to-sequence neural network is constructed based on the problem characteristic to generate an order priority sequence.Besides,a training approach is specially designed to improve learning performance.Furthermore,a greedy heuristic is employed to effectively dispatch new orders according to the order priority sequence.On real-world datasets,numerical experiments are conducted to validate the effectiveness of the proposed algorithm.Statistical results show that the proposed algorithm can effectively solve the problem by improving delivery efficiency and maintaining customer satisfaction.

Cloaking Region Based Passenger Privacy Protection in Ride-Hailing Systems

With the quick development of the sharing economy,ride-hailing services have been increasingly popular worldwide.Although the service provides convenience for users,one concern from the public is whether the location privacy of passengers would be protected.Service providers(SPs)such as Didi and Uber need to acquire passenger and driver locations before they could successfully dispatch passenger orders.To protect passengers’privacy based on their requirements,we propose a cloaking region based order dispatch scheme.In our scheme,a passenger sends the SP a cloaking region in which his/her actual location is not distinguishable.The trade-off of the enhanced privacy is the loss of social welfare,i.e.,the increase in the overall pick-up distance.To optimize our scheme,we propose to maximize the social welfare under passengers’privacy requirements.We investigate a bipartite matching based approach.A theoretical bound on the matching performance under specific privacy requirements is shown.Besides passengers’privacy,we allow drivers to set up their maximum pick-up distance in our extended scheme.The extended scheme could be applied when the number of drivers exceeds the number of passengers.Nevertheless,the global matching based scheme does not consider the interest of each individual passenger.The passengers with low privacy requirements may be matched with drivers far from them.To this end,a pricing scheme including three strategies is proposed to make up for the individual loss by allocating discounts on their riding fares.Extensive experiments on both real-world and synthetic datasets show the efficiency of our scheme.