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 con...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.展开更多
Online takeout has become the dining style of most urban residents.With the development of takeout industry,takeout delivery efficiency and cus-tomer satisfaction have attracted more and more attention from the industr...Online takeout has become the dining style of most urban residents.With the development of takeout industry,takeout delivery efficiency and cus-tomer satisfaction have attracted more and more attention from the industry and academia.The essence of takeout delivery problem is a vehicle routing problem under various constraints.Designing reasonable order dispatching and routing algorithms will help to improve the delivery efficiency and service quality for takeout platform.Firstly,by analyzing the order dispatching and delivery problem itself,we summarize the characteristics of the problem,compare the theoretical research of related problems,and describe it as a problem with the characteristics of soft time window,vehicle capacity limitation,dynamic order and 1–1 pick-up and delivery.Secondly,the problem scenario is described in detail,and the main elements and constraints of the problem are explained.Based on this,aiming at minimizing the overdue time,we divide the problem into two subtasks:order dispatching and routing,and propose an order dispatching strategy considering couriers’route and a two-stage routing algorithm.Specifically,this paper improves the calculation the cost in the previous heuristic algorithm based on the cost,that is,when dispatching an order,we consider whether there are orders close enough to the source location or destination location of the new order in every courier’s route,and if so,he can pickup and delivery the new order incidentally.In addition,it is also necessary to punish the courier who have long routes and whose orders have large overdue time;When planning the path for each order,wefirstly apply the nearest neighbor greedy algorithm for initial routing,which means iterativelyfind the time-consuming nearest feasible node in the remaining unplanned nodes,and then apply the tabu search algorithm to optimize the initial path.Finally,the static scenario and dynamic scenario are designed to verify the above algorithm.The static problem scenario solution verifies the effectiveness of the two-stage routing algorithm.The dynamic problem scenario proves the effectiveness of the order dispatching strategy considering couriers’route.We also analyze the ratio of the number of orders and couriers’influence on the performance of the algorithm,and recommend the quantity of couriers under the demand of orders with specific quantity.The experimental results can provide suggestions for the management of courier under the background of epidemic prevention measures such as closing-down due to the COVID-19.In addition,we propose that in a specific scenario,the order re-dispatching can make great improvement at small cost of computing resources.展开更多
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 ...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.展开更多
基金supported in part by the National Natural Science Foundation of China(No.62273193)Tsinghua University-Meituan Joint Institute for Digital Life,and the Research and Development Project of CRSC Research&Design Institute Group Co.,Ltd.
文摘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.
文摘Online takeout has become the dining style of most urban residents.With the development of takeout industry,takeout delivery efficiency and cus-tomer satisfaction have attracted more and more attention from the industry and academia.The essence of takeout delivery problem is a vehicle routing problem under various constraints.Designing reasonable order dispatching and routing algorithms will help to improve the delivery efficiency and service quality for takeout platform.Firstly,by analyzing the order dispatching and delivery problem itself,we summarize the characteristics of the problem,compare the theoretical research of related problems,and describe it as a problem with the characteristics of soft time window,vehicle capacity limitation,dynamic order and 1–1 pick-up and delivery.Secondly,the problem scenario is described in detail,and the main elements and constraints of the problem are explained.Based on this,aiming at minimizing the overdue time,we divide the problem into two subtasks:order dispatching and routing,and propose an order dispatching strategy considering couriers’route and a two-stage routing algorithm.Specifically,this paper improves the calculation the cost in the previous heuristic algorithm based on the cost,that is,when dispatching an order,we consider whether there are orders close enough to the source location or destination location of the new order in every courier’s route,and if so,he can pickup and delivery the new order incidentally.In addition,it is also necessary to punish the courier who have long routes and whose orders have large overdue time;When planning the path for each order,wefirstly apply the nearest neighbor greedy algorithm for initial routing,which means iterativelyfind the time-consuming nearest feasible node in the remaining unplanned nodes,and then apply the tabu search algorithm to optimize the initial path.Finally,the static scenario and dynamic scenario are designed to verify the above algorithm.The static problem scenario solution verifies the effectiveness of the two-stage routing algorithm.The dynamic problem scenario proves the effectiveness of the order dispatching strategy considering couriers’route.We also analyze the ratio of the number of orders and couriers’influence on the performance of the algorithm,and recommend the quantity of couriers under the demand of orders with specific quantity.The experimental results can provide suggestions for the management of courier under the background of epidemic prevention measures such as closing-down due to the COVID-19.In addition,we propose that in a specific scenario,the order re-dispatching can make great improvement at small cost of computing resources.
基金This research was supported in part by the National Science Foundation of USA under Grant Nos.CNS 1824440,CNS 1828363,CNS 1757533,CNS 1618398,CNS 1651947,and CNS 1564128the National Natural Science Foundation of China under Grant Nos.61872330,61572457,61379132the National Natural Science Foundation of Jiangsu Province of China under Grant Nos.BK20191194 and BK20131174.
文摘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.
