Study On Models And Algorithms For Urban Vehicle Routing Problem Of Express Delivery

In the past ten years,benefiting from the vigorous development of e-commerce in China,especially the explosive growth of online shopping,the logistics and express industry in China have also developed rapidly.The State Post Bureau expects that the express in China will complete a business volume of 49 billion pieces and the express business revenue will reach 595 billion yuan in 2018.However,the situation of high logistics costs has not been improved and transportation costs are the main component of logistics costs.The study object of this paper is urban express delivery.At present,urban express delivery is not yet mature,so there is a huge space for optimization.First of all,through system analysis of express business,the problem is defined with mathematical symbols.After the pre-processing,the problem is transformed into an urban vehicle routing problem which combines inbound transport and outbound transport with the constraints of capacity,time windows and vehicle restrictions.Next,the one-way vehicle routing problem is studied.Two mixed integer programming models are established for inbound and outbound transport respectively,followed by the constructive heuristics,set-covering model and column generation algorithm.The heuristics provides initial columns for column generation.Then,the paper focuses on the global routing optimization with the integration of inbound and outbound transport.A complete mathematical model is established.A more complex set-covering model and column generation algorithm are designed,and there are two sub-problems in column generation that correspond to inbound and outbound transport respectively.Finally,vehicles are matched between inbound shifts and outbound shifts,after which the entire transport cycle is formed.An asymmetric assignment model based on vehicle types is established.Through application and analysis of examples,the performance and characteristics of algorithms are compared.The results show that the cost obtained by column generation is basically consistent with the optimal cost.At a large scale of 130 points,the running time is only 184 seconds.Compared with tabu search algorithm,column generation also has certain advantages.Being applied to the actual scene,this algorithm can not only greatly reduce the transport cost,but also improve the scheduling efficiency.