The Capacitated P-Median Problem Based On Multi-strategy Discrete Particle Swarm Optimization

The Capacitated P-Median Problem(CPMP)is a class of combinatorial optimization problems evolved from graphs.CPMP has a wide application background in actual production,and it has been proved to be an intractable problem with NP-hard features.As the scale of the problem increases,its time calculation complexity increases exponentially.The exact mathematical method can only solve the small-scale CPMP,while heuristic algorithm based on group search has advantages in solving large-scale CPMP.The Particle Swarm Optimization(PSO)algorithm is a random search algorithm that simulates natural bird population activity and swarm intelligence.The algorithm has the advantages of simple operation,easy implementation and fast convergence.This paper analyzes the CPMP and its characteristics,performs discretization improvement based on the standard particle swarm optimization algorithm,and adds different heuristic strategies to the algorithm to form two new discrete particle swarm optimization algorithms.In order to verify the performance of the proposed algorithm,the algorithm was used to solve some public CPMP data sets,and compared with some well-known algorithm test data.The main work of this article includes:(1)An improved discrete particle swarm optimization algorithm(IDPSO)is proposed to solve CPMP.In the proposed algorithm,considering that the solution of CPMP can be decomposed into two stages:selection of medians points position and distribution of demand points,the speed update operation is eliminated in the algorithm.The introduction of crossover and mutation operator operations of genetic algorithms has increase the recombination of particle median points in a global search range.In the algorithm,a variable neighborhood local search process is added to improve the particle quality.The simulated annealing acceptance mechanism is designed to maintain the diversity of the population.Finally,the proposed algorithm is applied to 20 public CPMP test cases for testing,and the experimental data is compared with the data obtained by several literature heuristic algorithms.(2)A multiheuristic Discrete Particle Swarm Optimization(MDPSO)algorithm is proposed.In the proposed algorithm,the particle velocity and position update method were redefined.The difficulty in solving CPMP's solution lies in the adjustment and change of the midpoint.In the algorithm,the middle locus search uses global median selection,local median adjustment,and deep-neutral adjustment.The operation of assigning and adjusting local search operators to the demand points is added in the algorithm,so that the algorithm can optimize the selection and distribution of the sites and demand points in the particles from multiple dimensions.Finally,the proposed algorithm is applied to solve the public 20 small-scale test cases and 6 large-scale test cases,and compared with the well-known algorithm test data.In summary,by analyzing the characteristics of CPMP in the solution,two discrete heuristics based on different heuristic information are designed.Theoretical analysis and experimental tests verify the correctness and effectiveness of the proposed algorithm.