A Heuristic Constraint Programming Approach to the p-median Problem with Distance Constraints

In facility location problems we seek to locate a set of facilities in an area, where clients may be present, so that some criterion is optimized. In the p-median problem we seek to minimize the sum of distances between demand points and their nearest facility, whereas in the p-dispersion problem we seek to maximize the closest distance between any two facilities. Recently, a variant of p-dispersion where distance constraints exist between facilities was studied from a Constraint Programming (CP) and Integer Linear Programming (ILP) perspective. An incomplete CP solver that uses a greedy heuristic to prune branches during search was shown to significantly outperform the ILP solver Gurobi and the CP solver OR-Tools in terms of execution time. Following that work, 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 ILP and CP models and implement them in Gurobi and OR-Tools. Then, we demonstrate how a heuristic CP solver can be developed and applied on the p-median problem with distance constraints, comparing it to Gurobi and OR-Tools.