A hybrid binary particle swarm optimization for the obnoxious p-median problem

The obnoxious p-median problem can be formulated as a constrained binary linear program. It is NP-hard, and has a lot of real world applications. In this paper, a hybrid binary particle swarm optimization is proposed to solve the obnoxious p-median problem. A new position updating rule is presented to inherit the good structure of previous high quality solutions. Furthermore, two tabu based mutation operators are used to avoid the premature convergence and guide the search to a promising area. A greedy repair procedure is developed to repair infeasible solutions. In addition, an iterated greedy local search procedure is utilized to enhance the exploitation ability. Extensive experiments are done on a set of 72 benchmark instances from the literature. Experimental results and comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm. In particular, the proposed algorithm finds new best solutions for 15 instances. Compared with existing algorithms, the proposed algorithm is able to find better average objective function value in a short average computing time.