oga

oga logo
LinkedIn
mail

900 848 508

The Facility Location Problem

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:

  1. How many logistics centers do we install?
  2. Where do we locate them? And with what capacity?
  3. What are the benefits for both the logistics operator and the end customers between installing 1, 2 or more?
  4. 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)?
El problema de la localización de instalaciones

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

  • Station locations, e.g., bicycle for a new system, metro, for a new network or extension of an existing one. From a broad set of candidate locations and depending on the available budget, we ask ourselves what are the 25, 50 or 100 best locations for bike stations?
  • Locations of hospitals, police stations, schools.
  • Locations of stores or shopping centers.
  • Location of landfills, incinerators, recycling points or similar.
  • Location of lockers where to leave and pick up packages.
  • Location of electric vehicle or drone charging points.

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:
El problema de la p mediana. Variables

These are INTEGER OR COMBINATORIAL LINEAR OPTIMIZATION PROBLEMS and, due to the binary character (xi∈{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:

Example simulated problem of 50 nodes

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.
Artificial bee colony algorithm applied to WiMAX network planning problem. Victor Berrocal

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.

Categories

Latests articles

Acerca del autor

Autor
Alfredo García CÁTEDRA Group OGA
Alfredo García
Senior Optimization Consultant en OGA

Professor at the Pablo de Olavide University (UPO) and PhD in Mathematics from the University of Seville. Senior Optimization Consultant at oga.

Passionate about Mathematics, as a fundamental science, but especially about Applied Mathematics. What motivates him most is solving real problems and that is why, after more than 20 years of experience, he has worked in Pure Mathematics, Operations Research, Multiobjective Optimization, Evolutionary Computation and finally in Machine Learning and Business Analytics.

También podría interesarte