Study Of Modern Heuristic Algorithm For The Vehicle Routing Problem With Constraints

Vehicle Routing Problem (VRP) is one of the hot issues in field of OperationsResearch, Applied Mathematics and Computer Applications, mainly on how to design areasonable route to reduce cost. After more than half a century of development, it hasbeen widely used in telecommunications, manufacturing, defense, biological and otherfields. VRP is a typical NP-hard problem in Combinatorial Optimization. When thescale of the problem is large, the computational time required to solve the problem hasexponential growth, it is difficult to get the problem exact solution. Because of thecomplexity of the NP problem, the method for solving VRP is mainly heuristicalgorithm.This paper focuses on two types of model and algorithms for VRP. The main workis as follows:1. For the capacitated vehicle routing problem, a hybrid discrete artificial bee colonyalgorithm is presented, which gives the the nectar location of the discrete encodingmethod and adopts neighborhood search to generate candidate nectar andintroduces local search to enhance exploitation capacity. The experimental resultsshow that this algorithm is better than other algorithms.2. An improved firefly algorithm is presented for vehicle routing problem with timewindows. A discrete mechanism which turns continuous coding to discrete vehicleposition is designed. Local search operator is used to enhance local searchingperformance. Experimental results show that the improved firefly algorithm caneffectively find out the optimal solution.