Imporved Variable Neighborhood Seacrh Algorithm For DVRP

Logistics scheduling plays a more and more important role in modern social andeconomic activities. As the proportion of logistics activities in the economic activities isincreasingly growing, to reduce logistics cost has become a core of enterprises to reduceoperating costs. Vehicle routing Problem (VRP, Vehicle Route Problem) by the travelingSalesman Problem (TSP, Travelling Salesman Problem) and since put forward, it causesthe extensive concern and intensive research of many scholars. Through the research workfor decades, many models of vehicle routing problems and their solving algorithms havebeen put forward.Vehicle routing Problem is a typical NP-Hard in the field of combinatorialoptimization (NP-Hard, non-deterministic polynomial Hard), it can be divided into theStatic Vehicle routing Problem (SVRP, Static Vehicle Route Problem) and the DynamicVehicle routing Problem (DVRP, Dynamic Vehicle Route Problem). Dynamic vehiclerouting problem, its demand need to be required in time, and it is developed by the staticvehicle routing problem, is a new model of vehicle routing problem and a more realisticabstraction of the logistics. Dynamic vehicle routing problem is kind of a NP-hardproblem and is more complex than static vehicle routing problem. Present computers anddeterministic algorithms can’t get the optimal solution of the vehicle routing problemwithin a reasonable time. Therefore, the study of vehicle route problem mainly focuses itsapproximate solution on using the heuristic algorithm nowadays.Almost most of the heuristic algorithms are in seeking a balance between globalsearch and local search, in order to make the efficiency of the algorithm and performanceoptimization as much as possible. Variable neighborhood search algorithm is a fast andefficient heuristic algorithm, but easy to fall into local optimization. Use the variableneighborhood search algorithm to solve the dynamic vehicle routing problem, that isexploring a kind of balance of global search and local search to make the objectivefunction of the dynamic vehicle routing problem as low as possible, and keep anacceptable speed. The neighborhood structures of variable neighborhood search algorithm represent the search space or solution space of the problem, the expression ofneighborhood structures is the core of variable neighborhood search algorithm. When itcomes to searching the solutions of the solution space, the search strategy has a greatinfluence on the efficiency of the algorithm. In local search algorithm, more adoptingmountain climbing method (hill climbing method) in order to find the optimizationsolution as soon as possible, however this method is easily to fall into local optimum. Andon this basis, this article has put forward to improve the neighborhood structures of thebasic variable neighborhood search algorithm, to assure the problem of optimal solutionsincluded in the search space. In addition, adjusting the search strategy in order to adjust thelocal search method of variable neighborhood search algorithm, and let algorithm find theoptimal solution as soon as possible. Implicating the improved variable neighborhoodsearch algorithm to solve the dynamic vehicle routing problem, in order to accelerate thesearch speed, based on the characteristics of dynamic vehicle routing problem itself, in thesearch process to join the "granularity search". Experimental results show that theimproved algorithm to solve the dynamic vehicle routing problem is effective.The main research work of this paper as follows:(1) Review the vehicle routing problem model, analyzes its characteristic, andintroduces in detail the dynamic vehicle routing problem model;(2) Introduce the basic structure and characteristics of the variable neighborhoodsearch algorithm, and analyze their advantages and disadvantages, and propose someadvices on the improvement of VNS;(3) Aiming at the problem of the basic variable neighborhood search algorithm,proceed from the neighborhood structure and local search of the algorithm, the improvedvariable neighborhood search algorithm;(4) Apply the improved algorithm for dynamic vehicle routing problem, according tothe characteristics of the vehicle routing problem, and efficiency is improved incombination with granularity search algorithm;(5) At last, the result of the experiment are analyzed and summarized.