Facility Location Problems

Problem Description

Facility Location Problems are a class of optimization problems that address where to place one or more facilities to serve a set of demand points in the most efficient way possible. These decisions are strategic and long-term in nature, as they involve high investment costs in acquisition and construction.

The objective varies depending on the application but commonly seeks to:

• Minimize total costs: The sum of the fixed costs of opening facilities and the variable transportation costs to meet demand.
• Maximize service coverage: Ensure that the largest possible amount of demand is within a maximum distance or time from a facility.
• Minimize response time: Especially critical in emergency services.
• Minimize environmental impact: Depending on the type of facilities being studied.

Most of these variants are NP-hard, which means that finding the optimal solution for large-scale instances is computationally infeasible, requiring the use of advanced heuristics and metaheuristics.

Industrial Context

Location decisions are fundamental in both the private and public sectors. Poor planning can result in high operating costs and a low level of service for decades.

• In the private sector: Manufacturers deciding on the location of factories and warehouses, retail chains selecting where to open new stores to maximize market share, or logistics companies planning their distribution centers.
• In the public sector: Municipalities determining the location of emergency services (fire stations, ambulances), schools, libraries, or health centers to ensure equitable access for citizens.
• Special facilities: This also includes the location of “noxious” or “undesirable” facilities such as landfills, waste treatment plants, or airports, where the objective is to maximize the distance from populated areas.

Common Challenges

Within this family of problems, there are multiple classic and specialized variants:

• Uncapacitated Facility Location Problem (UFLP): This is one of the most studied models. It seeks to determine which facilities to open from a set of candidate locations to serve all demand at a minimum cost, considering a fixed cost for opening each facility and a transportation cost. It is the basis for many other more complex problems.
• p-Median Problem: This consists of locating a fixed number P of facilities to minimize the total or average distance weighted by demand from customers to the nearest facility.
• Covering Problems: These aim to ensure that demand points are “covered,” i.e., within a standard service distance. Variants include the Set Covering Problem (minimizing the number of facilities to cover all demand) and the Maximal Covering Problem (maximizing the demand covered with a fixed number of facilities).
• Multiple Obnoxious Facility Location Problem (MOFLP): Unlike the previous ones, the objective is to locate several noxious facilities (e.g., chemical plants) by maximizing the distance to residential areas to minimize their negative impact. It is related to the anti-median and p-dispersion problems.
• Obnoxious Planar p-Median Problem with Variable Sizes (OPPMVS): This is a complex and specific variant where p undesirable facilities must be located on a plane (not necessarily on a network). The objective is to maximize some measure of distance (similar to an anti-median problem), and additionally, the size or capacity of each facility is a decision variable that influences its impact.

Solution Approaches

Given the computational complexity, various techniques are used to solve these problems:

• Exact Methods: Integer linear programming to solve small to medium-sized instances.
• Heuristics and Metaheuristics: These are the most common methods for real-world size problems. They include local search algorithms, such as vertex exchange (Teitz and Bart), Tabu Search (TS), Variable Neighborhood Search (VNS), and population-based algorithms like genetic algorithms or Ant Colony Optimization (ACO).

References

1. Owen, S. H., & Daskin, M. S. (1998). Strategic facility location: A review. European Journal of Operational Research, 111(3), 423-447.
2. Daskin, M. S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. Wiley.
3. Drezner, Z., & Hamacher, H. W. (Eds.). (2002). Facility location: Applications and theory. Springer Berlin Heidelberg.
4. Francis, R. L., McGinnis, L. F., & White, J. A. (1983). Locational analysis. European journal of operational research, 12(3), 220-252.
5. Salazar, S., Cordón, O., & Colmenar, J. M. (2025). Efficient heuristics for the obnoxious planar p-median problem with variable sizes. Applied Soft Computing, 113401.
6. Martín-García, L., Lozano-Osorio, I., Colmenar, J. M., & Melián-Batista, B. (2025). Búsqueda de vecindad variable para el problema de localización de instalaciones sin capacidad. In XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (pp. 179-188).

Acknowledgments

This summary was prepared by the RedHEUR4.0 network as part of its contribution to the digital transformation of the transportation and logistics sectors, supported by the Spanish Ministry of Science and Innovation.