Research on Delivery Order Scheduling and Delivery Algorithms

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.