Research On Some Models And Algorithms In Network Location Field

Location problem is one of classical problems in the operational research, which is widely used in our production, daily life and even military. Network is carrier of most of the location decisions, and therefore the study on network location problem is more meaningful than other location problems. This paper mainly studies about the application of improved meta-heuristic algorithms for some network location problems, which are NP-hard. The whole paper is organized as follows: Chapter 1 introduces the background of subject research and the current research state, followed by the main research of this paper. Chapter 2 introduces some typical network problems. Chapter 3 introduces some meta-heuristic algorithms.Chapter 4 presents an improved genetic algorithm for large-scale set covering problem. The improvements for genetic algorithm include the following aspects: first, this algorithm designs a new way to generate initial population; second, it proposes a technology for infeasible solutions and overlapping individuals; third, it designs a new crossover operator and two types of adaptive multi-bit mutation operators. Finally, in numerical experiments, this algorithm is compared with other algorithms and then this paper analysis the effectiveness of this improved algorithm.Chapter 5 presents a new hybrid algorithm for solving the large-scale vertex p-center problem by combining the advantages of partheno-genetic algorithm and simulated annealing algorithm. It designs an adaptive selection and an adaptive gene recombination operator. Experimental results show that this algorithm is more effective than the other three algorithms.Chapter 6 presents a multi-objective anti p-center problem and translates it into a single objective problem by using the linear weighted sum method. Then, its integer programming model is established and partheno-genetic simulated annealing algorithm is proposed to solve this problem. At last, we carry out the numerical experiments for different weights and experimental results show that this algorithm is efficient.Chapter 7 designs two improved meta-heuristic algorithms to solve generalized minimum spanning tree problem. This paper designs two kinds of neighborhood search to avoid falling into local optimum in the improved tabu search algorithm. Finally, the two algorithms are compared with each other in numerical experiments and experimental results show that both algorithms are efficient.Finally, we summarize and point out some possible directions of future research.