Research On Heuristic Optimization Algorithms For Several Vehicle Routing Problems

The vehicle routing problem is a classic optimization problem that involes finding a set of routes with the lowest total distance under certain constraints.The vehicle routing problem was first proposed in 1959,as optimization theory has progressed,the solution is from the exact alogirthm to the meta heuristic algorithm,more and more algorithms can be used to solve the vehicle routing problem.The paper studies three variants of the vehicle routing problem,namely the capacitated vehicle routing problem,the capacitated vehicle routing problem with time window and the distance constrained capacitated vehicle routing problem,all of these problems are NP-hard problems,so we propose an efficient heuristic algorithm for each problem:(1)For the capacitated vehicle routing problem,this paper proposes a new variable neighborhood search,by integrating a randomized variable neighborhood descent method as its local search method.This algorithm combines the framework of simulated annealing and metropolis acceptance criterion.The experimental results show that the proposed algorithm is efficient.(2)For the capacitated vehicle routing problem with time windows,this problem is a variant of the CVRP.For this problem,we also propose the new variable neighborhood search algorithm,this algorithm expand the neighborhood structure by increasing the number of neighborhoods,thereby improving the performance of the algorithm.Numerous experiments have shown that the algorithm is efficient.(3)For the distance constrained capacitated vehicle routing problem,this problem is a variant of the CVRP,this paper proposes a randomized variable neighborhood search including the swap neighborhood,the insertion neighborhood and the swap-cross neighborhood,and the solution jump out of the local optimal traps by perturbation procedure.The experimental results show that the proposed algorithm has good efficiency.This paper improved the LKH algorithm which can solve the above problems.The LKH algorithm is currently one of the most effective algorithms for the vehicle routing problem.(4)For the LKH algorithm,this paper proposes an accelerated optimization operation to increase the computational efficiency of the LKH algorithm.The experimental results show that the improved LKH algotirhm is efficient.