| Since 2016,the market structure of Chinese takeout industry has initially taken shape,face to the macro background of the country's continuous deepening of supply side structural reform.The major takeout platforms have gradually turned the core competition field to the establishment of an efficient takeout distribution scheduling system to improve the order delivery efficiency and service quality of riders and reduce operating costs.However,there are still many pain points in the actual operation of the delivery site,which restricts the development of the delivery industry.For examples,1)through the field investigation of a delivery station in a certain area of Chongqing,it is found that during the peak meal period the influx of orders makes the system lack of effective algorithm mechanism for order consolidation and rider allocation.2)Under the high turnover rate of riders,the delivery efficiency of new and old riders is quite different,and there are also differences in service quality between dedicated riders and crowdsourcing riders.Therefore,the heterogeneity of riders is an important factor which affecting on-time delivery of orders and customer satisfaction.On the other hand,through the analysis of the research results of domestic and foreign scholars in recent years,it is found that the existing research is rarely based on the actual geographic information data,and the model is not enough to map the actual road network structure.In particular,the research on the heterogeneous characteristics of riders in the delivery model is still blank.To sum up,this paper mainly studies from the following four aspects.(1)The complete path planning and task assignment model for the heterogeneous characteristics of riders are constructed.(2)A three-stage solution strategy is designed to solve the proposed model.In the first stage,the proposed algorithms are used to merge the orders and evaluate the results.In the second stage,a special Adaption large-scale Neighborhood Search algorithm(ALNS)is designed to optimize the path of the task.Hungarian algorithm is used to assign tasks in the third stages.(3)Two efficient order merging algorithms,PCA + K-means clustering algorithm and heuristic merging algorithm based on path similarity,are proposed.the evaluation model of order consolidation results to quantify is constructed to evaluate the pros and cons of consolidation results.(4)Based on map lab,the road information of the actual road network is extracted,and the network diagram is constructed for theoretical research.Dijkstra algorithm is used to solve the shortest path between two points.(5)Based on the actual delivery site data,three scale test data sets are produced to test the effectiveness of the algorithm and model.According to the historical and practical data of the takeout delivery site,this paper generates different scale test data instances.The test results show that the solution performance of two merging algorithms and ALNS and Hungarian algorithms in different data scales.The results show that under the premise of ensuring that the customer satisfaction is "very satisfied",the order delay rate is less than 10%,the cost of single delivery is not higher than 2 yuan,and the average delivery time is less than10 minutes,thus the validity of the model and algorithm is verified.In addition,based on the optimal number of riders and the distribution proportion of different riders under different scales,it can also be used as reference for the optimization scheme of the manpower allocation of the existing takeout sites. |
PDF Full Text Request