A Dynamic Capacitated Facility Location Problem With Modular Capacities and Best Service Assignment: A Comparison of Formulations

ABSTRACT This paper introduces a variant of the dynamic Facility Location Problem with modular capacities. Inspired by the challenges faced by cellular telecommunication networks, the problem seeks to optimize the placement and equipment of facilities to meet the fluctuating demand of clients while minimizing installation and operational costs. Selected facilities must provide coverage to the whole considered area. In addition, clients must be served by the active facility that provides the best quality of service. We propose two integer linear programming formulations and analyze their theoretical properties in terms of lower bound. Furthermore, we propose a reinforcement for one formulation and valid inequalities. To evaluate the performance of the proposed formulations, we performed computational experiments with a commercial solver on instances with up to 20 candidate sites and 60 clients. The formulations proved to be very sensitive to the size of the instances. The analysis, both theoretical and numerical, provides meaningful insights on the formulations performance, and it constitutes a key starting point for developing further approaches, either exact methods or heuristics.