The capacitated multi-facility weber problem with polyhedral barriers: Efficient heuristic methods

- Introduces a new problem: Capacitated Multi-facility Weber Problem with polyhedral barriers (CMWP-B).
- Two alternate location-allocation type heuristics are offered for the CMWP-B.
- An approximating mixed integer linear programming formulation is developed for the CMWP-B.
- Two discrete approximation heuristics are implemented for the CMWP-B.
- Suggested solution procedures are very efficient and yield promising outcomes.

The Capacitated Multi-facility Weber Problem investigates the optimal locations of I capacitated facilities in the plane to satisfy the demand of J customers so that the total transportation cost is minimized. Facilities can be placed without any restrictions and customers are directly served without interruptions. In this work, we focus on the case with polyhedral barriers in which neither locating a facility nor travelling is permitted. Then, the transportation costs are dependent not only on the direct distances between facilities and customers but also on the location and size of the polyhedral barriers in presence. This results in a non-convex optimization problem which is difficult to solve. We offer two alternate location-allocation heuristics and two discrete approximation heuristics that are specially tailored for this problem. An extensive set of computational experiments are performed on the randomly generated test instances. Our results indicate that suggested heuristic methods are very efficient and yield promising results for this difficult problem.