The Facility Location Problem

We are all familiar with the problem of distribution, be it medium or long distance or even last mile and the need to consolidate goods in logistics centers as an intermediate step between manufacturing points and final demand points: We have a set of customers (nodes) that we must visit to deliver or pick up certain goods (figure on the left) and these demands are satisfied from one or more logistics centers. There are several issues to resolve:

How many logistics centers do we install?
Where do we locate them? And with what capacity?
What are the benefits for both the logistics operator and the end customers between installing 1, 2 or more?
What optimization criteria do we use: average distance, maximum distance, coverage…? Or, can we answer the above questions using a cost model/criteria (in addition to the cost associated with transportation, is there an additional fixed cost for each logistics center we use/install)?

Before looking at the methodological approach, it is important to highlight other scenarios where very common and crucial location problems arise:

The p-median problem

DEFINITION. The plant location problem, also known as the facility location problem, deals with the optimal placement of facilities to minimize, for example, transportation costs while taking into account other factors or constraints (e.g., avoiding the placement of hazardous materials near housing or other competitors).

The problem is therefore to determine the best p locations among a set of candidate locations. In this case, the following variables are required:

Variables:

These are INTEGER OR COMBINATORIAL LINEAR OPTIMIZATION PROBLEMS and, due to the binary character (x_i∈{0,1}) of the decision variables, they are, computationally speaking, NP-hard. This means that their complexity increases at an exponential rate as a function of the problem size. For this reason, obtaining the optimal solution is not an easy task when the problem is large.

Variants of the classic problem

The p-center or minmax problem, when we must determine the best p locations among a set of candidate locations that minimizes the maximum of the distances, i.e., to leave the best possible position to the farthest node of all.
The p-next center problem. This problem is an extension or variant of the p-center problem in which it is desired to minimize the distance to the second nearest node. This problem is of great interest in disaster situations where one of the key nodes (hospital for example) is disabled and the distance that the inhabitants had to travel to reach it is no longer such, but now they travel the distance to the second nearest hospital.
The maximin problem. The maximin location problem searches for locations that maximize the minimum distance to customers (as we locate, for example, a landfill).
The problem with capacities. If we are faced with a p-median problem but the nodes/customers have demands H={h1,…,hn} and each plant has a maximum capacity C, we add certain restrictions that guarantee this demand.
El problema de la cobertura. Problema de la localización de un conjunto de, por ejemplo, estaciones de bicicleta maximizando la cobertura a los ciudadanos.
The coverage problem. Problem of locating a set of, for example, bicycle stations maximizing coverage to citizens.

Let’s analyze an example

Let’s finish the post with a comparative table of average (p-median) and maximum (p-center) distances for a simulated problem of 50 nodes in the province of Jaén that we want to be served from p logistic centers chosen among those same 50 locations:

The results of 8 simulations for p = 1, 2, 3 and 5 log centers, for both the p-median and p-center approaches are as follows (in bold the values that the algorithm has minimized):

Alternative	Avg (km)	Max (km)
1-median	2458,249	136,596
2-median	1595,220	99,420
3-median	1190,154	99,415
5-median	799,090	50,582
1-center o minmax	2796,361	99,415
2-centers o minmax	1777,901	74,632
2-centers o minmax	1409,061	57,184
5-centers o minmax	969,633	39,725

Thus, if we wish to minimize the average distance traveled by the fleet, there is a saving in this average distance between locating a single center (1-medium) and locating 5 centers (5-medium) of 67.49%. Or simply a saving of 35.11 % between locating 1 or 2 logistics centers. We also see that it is recommended to locate in the Linares area for a single center or in Úbeda and Andújar for 2 centers.

But, in the images above, aren’t there customers too far away from the logistics centers? Indeed, for one center there are customers up to 136.596 km away. Well, if we focus on minimizing the maximum of the distances (p-center approach) we see a saving in this average distance between the 1-center and the 5-center of 60.04 % (from 99.415 km to 39.725 km). Or a saving of 24.93 % between locating 1 or 2 logistic centers, locating in the area of Úbeda for a single center or locating in Jaén and Villacarrillo for 2 centers, so that the farthest nodes are as close as possible (sacrificing, as can be seen in the table, the average distance)..

Antenna location

Our colleague Victor Berrocal has previously worked on this problem for the location of telecommunication antennas. Due to its complexity, he proposed an ABC (Artificial Bee Colony algorithm). Here is the reference and a couple of images of the proposed solutions:

Berrocal-Plaza, V., Vega-Rodríguez, M. A., Gómez-Pulido, J. A., & Sánchez-Pérez, J. M. (2011, November). Artificial bee colony algorithm applied to WiMAX network planning problem. In 2011 11th International Conference on Intelligent Systems Design and Applications (pp. 504-509). IEEE.

If you have faced this problem before, have worked with other approaches, want to know the most used heuristics in OGA to solve it or any other question, do not hesitate to contact us.

The Facility Location Problem - oga (2024)