Facility Location Problem
Introduction
Facility location problems deal with selecting the placement of a facility (often from a list of
integer possibilities) to best meet the demanded constraints. The problem often consists of
selecting a factory location that minimizes total weighted distances from suppliers and
customers, where weights are representative of the difficulty of transporting materials. The
solution to this problem gives the highest profit choice that most efficiently serves the needs of
all consumers.
Background and History
The Fermat-Weber problem was one of the first facility location problems ever proposed, and was done
so as early as the 17th century. This "geometric median of three points" can be thought of as a version of
the facility location problem where the assumption is made that transportation costs per distance are the
same for all destinations. It was put forth by the French mathematician Pierre de Fermat to the Italian
physicist Evangelista Torricelli as follows:
"Given three points in a plane, find a fourth point such that the sum of its distances to the three given
points is as small as possible."
In 1909 Alfred Weber used a three point version to model possible industrial locations in order to
minimize transportation costs from two sources of materials to a single customer or market. This
formulation is one the simplest continuous facility location models.
Background and History contd.
The Fermat-Weber problem is defined as:
Given finitely many distinct points A 1, A2, ..., Am and positive
multipliers w1, w2, ..., wm find a point P ∈ R n that minimizes
f(P) = ∑wi ||P - Ai|| (i varies from 1 to m)
where ||X|| denotes the Euclidean norm of X ∈ N
i.e. ||(x1, …, xn)|| = (x12 + … + xn2). The simplest version of this
problem with all w=1 and n=2 gives the minimum distance in a
flat plane. A modern day engineering interpretation of Fermat's
formulation could be as follows: "Find the best location for a
refining plant between three cities in such a way that the sum of
The Fermat Point, or Torricelli Point, is the solution that the connections between the plant and the cities in minimal."
minimizes distances from the three corners of the black
triangles Although this problem was first solved geometrically by
Torricelli in 1645 it did not have a direct numerical solution until
Kuhn and Kuenne's iterative method was published over 300
years later in 1962!
Description and Formulation
In the basic formulation of the facility location problem, the number of possible locations is now finite as
we have discrete choices of where to build. These choices are governed by binary decision variables y.
The problem is often defined as a set of customers D, a set of facilities F, a fixed cost for opening each
facility, and a variable cost for each facility. We are looking for the subset S of facilities that we should
open and an assignment of S to D such that all customers will be serviced by a facility and such that the
sum of fixed costs, variable costs, and transportation costs (modeled by distance) are minimized.
These problems have been studied extensively in the literature and are often solved using an
approximation algorithm. The approximation algorithm looks for a feasible solution where:
A: The algorithm will stop after a given number of steps (e.g. number of customers and facilities)
B: There is an approximation ratio such that the calculated solution is within some small amount of the
optimal solution
Minisum and Minimax Location Problems
Facility location problems are often formulated in one of two ways, minisum and minimax.
A minisum FLP looks to place a new facility in the location that minimizes the sum of the weighted distances
between the new facility and the already existing facilities. The minisum location problem is as follows:
min f(x) = ∑ wi d(X, Pi) ( i varies from 1 to m)
Where,
X is the location of the new facility
P are the locations of existing facilities
wi is the weight associated with travelling between the new facility and facility i
d is the the distance between the new facility and facility i
The minimax FLP, by contrast, looks for the optimal location to place a facility with the goal of minimizing the
maximum distance between the newly placed facility and all existing facilities.
Other Variations in facility location problems
Capacitated vs. Uncapacitated Facility Location Problems:
An additional variation on the facility location problem is whether a problem is capacitated or
uncapacitated. In a capacitated model the capacity of each facility is known and accounted for.
For a uncapacitated model however, the assumption is made that each facility can produce and
ship unlimited quantities of the commodity under consideration.
Continuous vs. Discrete Facility Location Problems:
In a continuous FLP the selection for the new facility can be any location within the space,
whereas for a discrete FLP there are given set of choices for the facility's location.
Example Problem
Applications in Industry
The figure at the right demonstrates an example of how the
facility location problem may be used in industry to
determine the locations for natural gas transmission
equipment.
This map illustrates facility locations for natural gas
processing, natural gas transmission, underground natural gas
storage, LNG storage, and LNG import and export. The
locations selected depend heavily on minimizing the distance
to the nearest natural gas pipeline shown in grey.
Applications in Industry contd.
Another case study that has been analyzed in the
literature was the determination of quantity and
location of distribution centers of steel facilities in
Latin America. This figure gives the result after
optimization for the location of steel production
facilities in Brazil.
Other Applications
Healthcare
In healthcare, incorrect facility location decisions have a serious impact on the community beyond simple
cost and service metrics; for instance, hard-to-access healthcare facilities are likely to be associated with
increased morbidity and mortality. From this perspective, facility location modeling for healthcare is more
critical than similar modeling for other areas.
Solid waste management
Municipal solid waste management still remains a challenge for developing countries because of
increasing waste production and high costs associated with waste management. Through the formulation
and exact resolution of a facility location problem it is possible to optimize the location of landfills for
waste disposal.
Clustering
A particular subset of cluster analysis problems can be viewed as facility location problems. In a centroid-
based clustering problem, the objective is to partition {\displaystyle n}n data points (elements of a
common metric space) into equivalence classes—often called colors—such that points of the same color
Conclusion
Facility location problems seek to optimize the placement of facilities such that the demands of
consumers can be met at the lowest cost and/or shortest distance. The minisum formulation
minimizes the sum of the weighted distances between facilities while the maxisum formulation
minimizes the overall maximum distance between facilities. The study of these problems has
numerous applications in the fields of mathematics, economics, physics, and engineering.
References
Facility location problem diagram
Facility location problem diagram 2
Facility location problems
Facility location problem wikipedia
