A CP/LS heuristic method for maxmin and minmax location problems with distance constraints

Abstract

Panteleimon Losif from the University of Western Macedonia, in Greece, tells that in facility location problems we seek to locate a set of facilities so that some criterion is optimized. In the p-center problem we minimize the maximum distance between clients and their closest facilities, whereas in p-dispersion we maximize the minimum distance between facilities. Recently, a variant of p-dispersion with distance constraints between facilities was studied, and an incomplete CP solver that heuristically prunes branches was shown to be faster than Gurobi and OR-Tools, but often failed to discover optimal/near-optimal solutions. We enhance this work in two directions, regarding effectiveness and applicability. We first show how local search can be used to achieve more focused branch pruning with little extra cost, resulting in optimal or near-optimal solutions being discovered in many more instances. Then, we demonstrate how the framework can be applied on the p-center problem with distance constraints, comparing it to ILP and CP models implemented in Gurobi and OR-Tools