The Model And Algorithm Research Of Multi-category Two-Echelon Split Delivery Vehicle Routing Problem

With the booming development of e-commerce,logistics has become the"cake"of all e-commerce enterprises with its huge demand and stable growth potential.With the increasing variety of goods sold on e-commerce platforms,the competition among e-commerce platforms is becoming more and more focused on how to achieve high-quality services at a lower cost.Based on this,large e-commerce enterprises represented by Jing Dong set up a multi-level network logistics distribution system,aiming to achieve the purpose of reducing costs and increasing efficiency through the seamless connection of logistics networks at all levels.Under this background,the two-echelon vehicle routing problem,as the pillar of multi-level distribution network,has gradually attracted the common attention of enterprises and academia.In the actual operation of e-commerce enterprises,suppliers supply goods to each regional central warehouse according to a fixed period,and carry out inventory layout of regional central warehouse.Based on end-customer demand prediction,each transit warehouse reports the demand quantity and time of each commodity to the regional central warehouse that provides its supply service.At this time,enterprises usually use mutual allocation and replenishment between regional central warehouses and transfer from regional central warehouse to transit warehouse to complete the inventory layout of the transit warehouse.In this paper,the inventory layout process of transit warehouse is completed through the secondary linkage of trunk distribution link and branch distribution link in the multi-level distribution system,and a two-stage vehicle routing problem with split multi-commodity demand is extracted and studied.The goal is how to meet all commodity needs at the lowest cost through coordinated two-stage distribution decisions.In the problem studied in this paper,in the first stage,it is necessary to make supply-demand matching decisions and access path decisions among regional central warehouses.These two decisions interact with each other and further increase the complexity of problem solving.The second stage involves making decisions about access paths between customers.To solve this problem,a mixed integer mathematical programming model was established,and the effectiveness of the model was verified by the optimization software CPLEX.Secondly,by exploring the characteristics of the problem,a series of accelerated solving strategies are proposed to improve the performance of the model,so as to obtain the optimal solution or high-quality lower bound for small to medium scale examples in a reasonable time.Thirdly,according to the characteristics of the problem,an iterative local search algorithm based on large-scale neighborhood search is designed to quickly obtain high-quality feasible solutions for large-scale problems.In this algorithm,high quality initial solution is obtained quickly by greedy thought,and then the initial solution is improved by iterative local search algorithm,that is,by introducing five neighborhood disturbance operators,greedy repair operators,parking adjustment strategy and small truck departure time adjustment strategy to enhance the optimization ability and obtain the improved solution.Finally,a series of numerical experiments were conducted based on 180 randomly generated examples of 36 groups of different sizes.The experimental results show that:1)the introduction of acceleration strategy can help the model to obtain more optimal solutions or tighter lower bounds;2)The iterative local search algorithm performs well in terms of solving quality and efficiency;3)Compared with the algorithm designed by Li et al.^[87],the iterative local search algorithm proposed in this paper has obvious advantages in solving quality and efficiency.Based on the experimental results,the following enlightenments are obtained in this paper:1)The proposed acceleration strategy of the model can provide new ideas for future research on vehicle routing problems;2)The algorithm designed in this paper can greatly shorten the solution time and improve the solution quality,which can lay a foundation for the subsequent design of more efficient operators;3)Considering the two-stage vehicle routing problem globally and optimizing the overall layout can maximize the operation efficiency of the two-stage logistics system and reduce operating costs;4)The overall layout of vehicle scheduling in two-echelon logistics network based on model and algorithm can assist enterprises to realize intelligent decision of distribution scheme,thus laying a foundation for the construction of intelligent logistics system.In this paper,the research of multi-commodity demand splitting two-stage vehicle routing problem not only enrich the existing theory of two-stage vehicle routing problem to some extent,but also provides decision support for the operation of two-stage collaborative distribution network of enterprises.