Facility location problems on graphs with non-convex neighborhoods
研究了图上顾客和设施都位于非凸邻域中的p-中位、p-中心和p-最大覆盖问题，提出了混合整数非线性规划模型及预处理方法，并通过计算实验验证了效果。
In this paper, we deal with some variants of classical facility location problems on graphs in which both the customers and the facilities belong to a non-necessarily convex neighborhood. Therefore, a point in each neighborhood representing the customer/facility has to be determined, and the customers have to be assigned to the facilities depending on a criterion. In particular, the p-median, the p-center, and the p-maximal covering versions of this problem on graphs are analyzed. An important difference with respect to their classical versions is that the lengths of the arcs depend on the location of the points chosen in the neighborhoods. Therefore, the lengths are not part of the input but part of the decision process. Assuming that the neighborhoods are Mixed-Integer Second Order Cone representable, different mixed-integer non-linear programming formulations are proposed for each one of the considered problems. Moreover, solution procedures providing bounds and a preprocessing phase are developed to reduce the number of variables and constraints of the proposed formulations. The results of an extensive computational experience are reported.