Abstract

Let GdV,Ed be an input disk graph with a set of facility nodes V and a set of edges Ed connecting facilities in V. In this paper, we minimize the total connection cost distances between a set of customers and a subset of facility nodes S subset of V and among facilities in S, subject to the condition that nodes in S simultaneously form a spanning tree and an independent set according to graphs G over bar d and Gd, respectively, where G over bar d is the complement of Gd. Four compact polynomial formulations are proposed based on classical and set covering p-Median formulations. However, the tree to be formed with S is modelled with Miller-Tucker-Zemlin (MTZ) and path orienteering constraints. Example domains where the proposed models can be applied include complex wireless and wired network communications, warehouse facility location, electrical power systems, water supply networks, and transportation networks, to name a few. The proposed models are further strengthened with clique valid inequalities which can be obtained in polynomial time for disk graphs. Finally, we propose Kruskal-based heuristics and metaheuristics based on guided local search and simulated annealing strategies. Our numerical results indicate that only the MTZ constrained models allow obtaining optimal solutions for instances with up to 200 nodes and 1000 users. In particular, tight lower bounds are obtained with all linear relaxations, e.g., less than 6% for most of the instances compared to the optimal solutions. In general, the MTZ constrained models outperform path orienteering ones. However, the proposed heuristics and metaheuristics allow obtaining near-optimal solutions in significantly short CPU time and tight feasible solutions for large instances of the problem.