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

Abstract

The Capacitated Multi-facility Weber Problem (CMWP) tries to determinethe location of I capacitated facilities in the plane and to satisfy demand of Jcustomers so as to minimize the total transportation cost. The CMWP assumesthat the facilities can be located anywhere on the plane and customers aredirectly connected to them. This study considers an extension of the CMWPwhere there exist convex polyhedral barriers blocking passage and locatingfacilities inside. As a result, the distances between facilities and customershave to be measured by taking into account the polyhedral barriers. TheCMWP with convex polyhedral barriers (CMWP-B) is a non-convex problemthat is difficult to solve. We propose specially tailored discretization basedheuristic procedures. Since CMWP-B is novel to the literature, a new set oftest problems is randomly generated. Then, the performance of the suggestedmethods are tested on the test instances. Our results imply that the suggestedheuristics yield quite accurate and efficient solutions for the CMWP-B.