Research Of Variable Neighborhood Search And Application In Combinatorial Optimization

This paper makes improvements to the variable neighborhood search algorithm, and presents a variable neighborhood search algorithm solving continuous optimization problems and a hybrid variable neighborhood search algorithm combining particle swarm optimization. Besides, the improved algorithm is also applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. The research results and innovations are as follows:Firstly, due to the problems which can not directly apply variable neighborhood search algorithm for characteristics of feasible solution space of the continuous optimization problems, combining SQP algorithm with variable neighborhood search algorithm, this article uses the SQP algorithm to solve local optimal solution, and uses variable neighborhood search algorithm to elect local optimal solution, then obtains the global optimal solution. Data simulation shows that the variable neighborhood search algorithm is better than the other heuristic algorithms in aspect of the global convergence.Secondly, general variable neighborhood search algorithm takes longer time, so drawing on the idea of Particle Swarm Optimization, this paper proposes a hybrid variable neighborhood search algorithm with combination of particle swarm. Adjust the disturbance process and the neighborhood transformation process of the variable neighborhood search algorithm, to reduce the number of local search of the variable neighborhood search algorithm and enhance the effects of disturbance process. Data simulation shows the effectiveness of hybrid algorithm.Thirdly, the improved algorithm is applied to the traveling salesman problems and the 0-1 mixed integer nonlinear programming problems. Among them, for the traveling salesman problems, this article introduces new PSO algorithms to get a hybrid variable neighborhood search algorithm which is appropriate for traveling salesman problems. The data simulation shows hybrid algorithm is better than the average variable neighborhood search algorithms and other heuristics. For the 0-1 mixed integer nonlinear programming problems, this paper firstly puts it into general optimization problems, and then solve them in the continuous space by the use of the penalty function method and variable neighborhood search algorithm. Finally, the examples prove this method is feasible.