Solve The Capacity P-Median Problem By Ant Colony Algorithm

Capacitated p —median problem (CPMP) can be viewed as a special embranchment of the Facility Location Problem (FLP). The CPMP arises in many practical situations. It has been researched widely in location theory and clustering theory. It is an important complex combination optimization problem and has been proved to be NP-hard. Many heuristics are devised to solve this problem.Ant colony algorithm (ACO) enjoys a rapidly growing popularity for its good optimal performance. In ACO, ants communicate each other in order to optimize the pheromone expression' of problem state step by step. The learning experience instructs ant colony to search optimum of problem. It is the primary purpose of our thesis that how to use the ACO to solve CPMP effectively and devising good executing strategies in order to improve performance of algorithm. The important research works include:1. A new median learning algorithm-MLA is proposed to solve CPMP based on the characteristic of CPMP. It utilizes the pheromone learning mechanism of ACO. Reasonable allocation method of customers is devised in view of the structure of CPMP. MLA integrates the pheromone mechanism of ACO with local search strategy so that both the global and local search ability of the algorithm is reinforced. Computational results indicate that the MLA outperforms alternative methods developed for solving this kind of problem.2. The projection method of Fitness Landscape is devised. The structure characteristic of CPMP's Fitness Landscape is researched detailed in base of the projection plot combined with the characteristic index of Fitness Landscape. Distributing characteristic of solution space is depicted and problems are sorted hereby. Moreover, we analyze the primary factors which affect the algorithm performance. They include of problem structure, the selecting strategy of initial medians, the assigning order and method of customers, the parameters setting and so on. These researching results provide theory instruction for...