Facility location problems with neighborhoods

Resumen

This work addresses various extensions of classical facility location problems on graphs where both customers and facilities belong to neighborhoods. Consequently, it becomes necessary to determine a point in each neighborhood to represent the customer/facility, and customers must be assigned to facilities based on certain criteria. In particular, we study the p-median, p-center, and p-maximal covering versions of this problem. An important difference with their classical versions is that the lengths of the arcs depend on the location of the points in the neighborhoods. Therefore, the lengths are not inputs, but part of the decision variables. Assuming that the neighborhoods, non-necessarily convex, can be represented as mixed-integer second order cone constraints, different mixed-integer non-linear programming formulations are proposed for each of the problems. In addition, a preprocessing phase was developed to provide bounds and reduce the number of variables in the formulations.