Research On Multi-objective Vehicle Routing Optimization Problem With Soft Time Window Constraints

With the constant innovation of information technology and the fast development of the e-commerce industry,modern logistics and distribution have become the linchpin to the development of the new real economy.In real life,the vehicle routing problem(VRP)is one of the core problems of logistics distribution.According to the actual distribution situation,a variety of VRP expansion problems are extended by adding constraints.Among them,simultaneous pickup and delivery VRP(VRPSPD)and multi-center semi-open VRP(MDHOVRP)have become the hotspot of VRP research because they are more in line with the current actual logistics distribution system operation.Based on the actual distribution background,this paper studies the VRPSPD(VRPSPDSTW)with soft time window constraint under single-center static road network and MDHOVRP with soft time window constraint(MDHOVRPSTW)under multi-center dynamic road network.Firstly,in order to meet the customer’s timeliness requirements for service time in VRPSPD,this paper considers the soft time window constraints in VRPSPD.The model is established with the optimization goals of maximizing average customer satisfaction,the shortest delivery distance and the smallest delivery cost,and a hybrid simulated annealing particle swarm algorithm is designed based on particle swarm and simulated annealing algorithm.This algorithm not only enhances the ability of the particle swarm algorithm to jump out of the local optimum in iterations,but also improves the convergence speed of the simulated annealing algorithm and the probability of obtaining the global optimum solution.The simulation experiment was carried out by extending the Solomon standard calculation example,and compared with the experimental results of related literatures,which proved the effectiveness of the hybrid algorithm in solving VRPSPDSTW.Secondly,in view of the MDHOVRPSTW problem,considering the timeliness requirements of customers for distribution services,the time-varying characteristics of vehicle speeds and the uncertainty of traffic conditions in actual distribution activities,constraints such as road types and traffic congestion are added to MDHOVRPSTW.A time-dependent function with acceleration is used to characterize the time-varying speed,and the optimization goal is to maximize the average customer satisfaction,the shortest delivery distance and the smallest delivery cost,and construct the MDHOVRPSTW mathematical model of the time-varying speed.Finally,based on the characteristics of the MDHOVRPSTW mathematical model with time-varying speed,a two-stage solution algorithm is designed.In the first stage,the fast convergence ability of the multi-objective particle swarm algorithm is used to optimize multiple objectives at the same time to obtain an initial feasible solution.Adaptive grid density method and neighborhood crowding density method are used to maintain external archives.The crowding density and the inverse generation distance are used as the selection criteria of the global optimal particles to improve the convergence of the algorithm and improve the population distribution.In the second stage,the variable neighborhood search algorithm is used to optimize the initial feasible solution without reducing the average customer satisfaction,reduce the delivery distance,and reduce the delivery cost.The classic MDVRPTW calculation example has been expanded.In the case of the same model,it is compared with the solution results of other documents to verify the effectiveness of the two-stage solution algorithm design.Then compare the solution results under the conditions of time-varying speed and constant speed,and analyze the influence of the time-varying road network on the solution effect of the model to verify the rationality of the model establishment.