Solving the Obnoxious p-median Problem by the Particle Swarm Optimization Method

Abstract

In this paper the Particle Swarm Optimization (PSO) method is implemented to solve the Obnoxious p-median problem (Op-med). The goal of the Op-med problem is to find locations of p-centers such that the sum of the distances from the users to their closest centers is maximized. In order to improve the basic PSO, two new ideas are introduced: adding random matrices which additionally diversify the exploration of the solution space, as well as an exploitation loop. Adding the random matrices adds to the diversification of the solution by randomizing the social and cognitive aspect of the method. The exploitation loop explores the region identified as the best in detail with a PSO method that doesn’t have a social aspect. Testing was done on modified p-med instances from the ORLIB library, which include up to 200 nodes, and the results of the proposed method are compared to ones obtained by the CPLEX solver. The paper additional explores the behavior of the method when the swarm is enlarged, as well as when more PSO iterations are added. Testing has shown that a larger swarm gives much better improvements than adding additional iterations.