Research On The Modeling And Algorithm Of Veihcle Routing Problem With Roaming Delivery Location In Delivery-to-trunk Mode

With the rapid development of e-commerce,there is a large booming in express delivery business,whose terminal delivery,as the direct contact with the customer,affecting their online shopping experience,is stepping to a vital edge.The need for flexibility of "last mile" receiving location and protection awareness of private information is getting more and more attention.As a result,combining with the weakness of insufficient density and random charges of self-contained cabinet,express delivery companies are looking at some social idle resources to innovate the terminal distribution mode,hoping to cope with the difficulty in receiving.Facing with the ownership of more than 100 million private cars nationwide,a new mode of delivery-to-vehicle delivering customer's packages to their car trunks rather than to customer's home emerged,and was j oined by Amazon and Volvo,Audi,DHL,and Jingdong Logistics and Weilai The application of delivery-to-vehicle mode can effectively solve the problem of time and space conflicts in distribution and reduce the failure rate of one delivery,thereby reducing the terminal distribution cost and improving the phenomenon of "receiving goods".However,due to the roaming characteristics of the delivery objects delivered to the car,a new VRP with roaming distribution is caused,called vehicle routing problem with roaming delivery location(VRPRDL).Based on the analysis of the operation process of the mode,this paper focuses on the application of the VRPRDL to the delivery mode,with establishing the model and designing the intelligent algorithm.Considering the dependency between roaming problem and driving environment,this paper adds time-dependent function to the model to further analyze the model and algorithm design of time-dependent VRPRDL.Based on all the above work,the significance of this paper lies in providing a new direction for the innovation of the end-of-sale mode,providing new ideas for the end-distribution cost reduction strategy,and enriching the research of vehicle routing problem models and algorithms.In the second chapter,there is an analysis about the target customer and the operation process of the mode,which comes to conclusions that the mode is especially suitable for customers who don't have a fixed point to receive,and need to sign some intimate parcels,meanwhile 5 applicable consumption scenarios are proposed.Furthermore,the more conclusion is that it can be divided into two period path pre-planning and distribution.Based on the path pre-planning period,this paper analyzes how are the two vehicle routing problems:VRPDL and Time-dependent VRPRDL applied in the mode's vehicle routing problem solutions.In the third chapter,this paper abstracts VRPRDL as a vehicle routing problem with roaming delivery location and accessing point groups with non-overlapping time window groups.Combining with the characteristics of the non-Hamilton,this paper establish a VRPRDL model and design a genetic-taboo-search hybrid algorithm with the feature of a two-layer chromosome containing customer ranking information and customer delivery location information,as well as two neighborhood structures and two taboo tables.Based on the model and algorithm,there are some tests on the problem,and the results are that the hybrid algorithm could efficiently and stably solve the problem.Compared to VRPHRDL,the solution of VRPRDL saves an average cost of more than around 34%in each study.In the fourth chapter,there is a study about VRPRDL as the driving time varies by departure time under the dynamic traffic network,and a TDVRPRDL model including the factors of customers' travel time and delivery vehicles' travel time was established to solve it.Immediately,a related algorithm improved from the genetic-taboo-search hybrid algorithm in VRPRDL was designed based on the principle of high-speed priority distribution.Finally,through comparison experiments and stability analysis of different scale examples,the improved genetic tabu search hybrid algorithm designed in this paper can effectively and stably solve the TDVRPRDL model,and for large-scale TDVRPRDL,the running time of the algorithm is still acceptable.Furthermore,the comparison with the VRPRDL shows that the closer the model is to the actual conditions,the more relevant the delivery efficiency is to the optimization of the routing solutions,and the less correlated is that how far the customers are or how far the delivery vehicles could deliver.