A Heuristic Constraint Programming Method for the p-Median Problem With Distance Constraints

Abstract

In a facility location problem, we seek to locate a set of facilities in an area, where demand points (clients) may be present, so that some criterion is optimized. A well-known facility location problem is the p-median problem, where we seek to minimize the sum of distances between demand points and their nearest facility. We consider a variant of the p-median problem where distance constraints exist between facilities and between facilities and demand points. This problem can be used to model the requirements that arise when locating semi-obnoxious facilities. We first introduce integer linear programming and constraint programming (CP) models and implement them in Gurobi and OR-Tools, respectively. Then, we describe a greedy heuristic that can be used to prune branches during a search within an incomplete CP solver. We also introduce a number of domain-specific value ordering heuristics that can be applied within such a solver. The developed method is evaluated under different problem generation models, and compared to Gurobi and OR-Tools. The results demonstrate that our method is more robust than the two complete solvers, significantly outperforming either of them in certain classes of problems, both in terms of run times and the quality of the solutions found.