Modeling And Algorithm Research On Extensions Of Open Multi-Depot Vehicle Routing Problem

With the further research of Vehicle Routing problem,researchers add more and more constraints to the basic VRP,and many problems of VRP expansion are arised which make the problem more practical.Multi-Depot VRP is based on the problem of VRP which introduces multiple-depots and is a hotspot in the research of VRP problem.It is more in line with the operation of current logistics distribution system.Some scholars have extended research on this problem,such as the open VRP problem with Multi-Depot,its characteristics of distribution center opening and resource sharing can realize the joint distribution of vehicle.And the distribution vehicle cannot return to the original distribution center after completing the distribution task which can be parked in the nearest distribution center.Sometimes even the distribution center does not provide parking services.The core objective of this research is to improve the efficiency of distribution centers and vehicles,and to reduce service costs.At present,the research on the problem of Multi-Depot open VRP is in the process of deepening and expanding,the paper studies the following 4 expansion problems,and obtains the following innovative results:(1)For the Multi-Depot open VRP with fuzzy time Windows,the time Windows fuzzy processing method is adopted which assuming that the time Windows is a trapezoidal fuzzy number.The paper defines the customer satisfaction function and time penalty cost function,and then constructs a Multi-Depot open VRP robust optimization model with fuzzy time Windows considering transportation cost,vehicle dispatch cost and time penalty cost caused by fuzzy time Windows constraints.Based on the assumption of virtual distribution center,a single distribution center network is designed.And then an improved ant colony algorithm is designed to solve the problem.The experiments on instances verify the effectiveness of the algorithm and model.(2)Based on the scientific characterization and demonstration of the vehicle routing problem of the resource-sharing distribution network,the paper puts forward the Multi-Depot open vehicle routing problem with simultaneous delivery and pickup and Fuzzy Time Windows.An optimization model of this problem is constructed.According to the characteristic of the problem,the chaos genetic variable neighborhood search algorithm is designed,the pseudo-randomness of chaos is introduced to ensure the diversity of the initial solution.And applying the variable neighborhood search algorithm to the search strategy of genetic algorithm to enhance the search ability of population.The presentation and scientific argumentation of the problem,the model and the design of the algorithm all reflect strong innovations.(3)For the Multi-Depot open vehicle routing problem considering cargo damage,the paper presents the open vehicle routing problem with time Windows for the Multi-Depot joint distribution mode of fresh products.Considering the distribution cost,dispatch cost,time penalty cost and damage cost,a Multi-Depot open joint dispatch VRP model considering cargo damage is constructed and an ant colony algorithm is designed to solve the problem.Through the comparison and analysis of the instances and different distribution modes,the validity of the algorithm and the model is verified.The research results can provides a good idea for the development of cold chain logistics and distribution of fresh electric business.(4)For the Multi-Depot open vehicle routing problem with fuzzy demand,the triangular fuzzy number is used to characterize the fuzzy demand.Based on the theory of credibility,the conservative degree value of decision-making is characterized by describing the risk preference of decision-makers.And the "first-path-after-grouping" strategy is adopted for the Multi-Depot constraint.The corresponding mathematical model is established according to the above assumption.Then the two-stage tabu search algorithm is designed to solve the problem.The 1th phase of the algorithm solves the traveling salesmen problem,the results will be used as the initial solution of the 2nd phase.And the appropriate coding method is used to ensure the compatibility of the two-phase solution.The results of the instance experiments show that the designed two-stage tabu search algorithm can solve the problem effectively in acceptable time,and its 1th stage can significantly improve the solution quality of the algorithm.In conclusion,the results of this study can not only enrich and expand the related theory research of Multi-Depot VRP and open VRP,but also provide guidance for improving the vehicle dispatching and production decision-making in actual logistics distribution enterprises.