A branch-and-cut method for the obnoxious p-median problem |
| |
Authors: | Pietro Belotti Martine Labbé Francesco Maffioli Malick M. Ndiaye |
| |
Affiliation: | (1) Electronics and Computer Science Department, Politecnico di Milano, Milano, Italy;(2) Computer Science Department, Université Libre de Bruxelles, Brussels, Belgium;(3) System Engineering Department, KFUPM, Dharan, 31261, Saudi Arabia |
| |
Abstract: | The obnoxious p-median (OpM) problem is the repulsive counterpart of the ore known attractive p-median problem. Given a set I of cities and a set J of possible locations for obnoxious plants, a p-cardinality subset Q of J is sought, such that the sum of the distances between each city of I and the nearest obnoxious site in Q is maximised. We formulate (OpM) as a {0,1} linear programming problem and propose three families of valid inequalities whose separation problem is polynomial. We describe a branch-and-cut approach based on these inequalities and apply it to a set of instances found in the location literature. The computational results presented show the effectiveness of these inequalities for (OpM). The work of the first author has been partially supported by the Coordinated Project C.A.M.P.O. and that of the third author by a short mobility grant, both of the Italian National Research Council. |
| |
Keywords: | Obnoxious facility location Branch-and-cut p-Median |
本文献已被 SpringerLink 等数据库收录! |
|