Discretization based heuristics for the capacitated multi-facility Weber problem with convex polyhedral barriers

The Capacitated Multi-facility Weber Problem (CMWP) tries to determine the location of I capacitated facilities in the plane and to satisfy demand of J customers so as to minimize the total transportation cost. The CMWP assumes that the facilities can be located anywhere on the plane and customers are directly connected to them. This study considers an extension of the CMWP where there exist convex polyhedral barriers blocking passage and locating facilities inside. As a result, the distances between facilities and customers have to be measured by taking into account the polyhedral barriers. The CMWP with convex polyhedral barriers (CMWP-B) is a non-convex problem that is difficult to solve. We propose specially tailored discretization based heuristic procedures. Since CMWP-B is novel to the literature, a new set of test problems is randomly generated. Then, the performance of the suggested methods are tested on the test instances. Our results imply that the suggested heuristics yield quite accurate and efficient solutions for the CMWP-B.