Facility location problem

Authors: Liz Cantlebary, Lawrence Li (CHEME 6800 Fall 2020)

Stewards: Allen Yang, Fengqi You

Introduction

The Facility Location Problem (FLP) is a classic optimization problem that determines the best location for a factory or warehouse to be placed based on geographical demands, facility costs, and transportation distances. These problems generally aim to maximize the supplier's profit based on the given customer demand and location. FLP can be further broken down into capacitated and uncapacitated problems, depending on whether the facilities in question have a maximum capacity or not.

Theory and Formulation

Weber Problem

The Weber Problem is a simple FLP that consists of locating the geometric median between three points with different weights. The geometric median is a point between three given points in space such that the sum of the distances between the median and the other three points is minimized. It is based on the premise of minimizing transportation costs from one point to various destinations, where each destination has a different associated cost per unit distance.

Given $N$ points $(a_{1},b_{1})...(a_{N},b_{N})$ on a plane with associated weights $w_{1}...w_{N}$ , the 2-dimensional Weber problem to find the geometric median $(x,y)$ is formulated as⁽¹⁾

$\min {\begin{aligned}W(x,y)=\sum _{i=1}^{N}w_{i}d_{i}(x,y,a_{i},b_{i})\\\end{aligned}}$

where

$d_{i}(x,y,a_{i},b_{i})={\sqrt {(x-a_{i})^{2}+(y-b_{i})^{2}}}$

Capacitated and Uncapacitated FLPs

FLPs can often be formulated as mixed-integer programs (MIPs), with a fixed set of facility and customer locations. Binary variables are used in these problems to represent whether a certain facility is open or closed and whether that facility can supply a certain customer. Capacitated and uncapacitated FLPs can be solved this way by defining them as integer programs.

A capacitated facility problem applies constraints to the production and transportation capacity of each facility. As a result, customers may not be supplied by the most immediate facility, since this facility may not be able to satisfy the given customer demand.

In a problem with $N$ facilities and $M$ customers, the capacitated formulation defines a binary variable $x_{i}$ and a variable $y_{ij}$ for each facility $i$ and each customer $j$ . If facility $i$ is open, $x_{i}=1$ ; otherwise $x_{i}=0$ . Open facilities have an associated fixed cost $f_{i}$ and a maximum capacity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_i} . Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}} is the fraction of the total demand Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_j} of customer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} that facility Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} has satisfied and the transportation cost between facility Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and customer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} is represented as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{ij}} . The capacitated FLP is therefore defined as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \begin{array}{rl} \min & \displaystyle\sum_{i=1}^N\sum_{j=1}^M d_j t_{ij} y_{ij}+\sum_{i=1}^Nf_ix_i \\ \text{s.t.} & \displaystyle\sum_{i=1}^Ny_{ij}=1 \text{ for all }j=1,\dots,M \\ & \displaystyle \sum_{j=1}^Md_jy_{ij}\leq k_ix_i\text{ for all }i=1\dots,N \\ &y_{ij}\geq0\text{ for all }i=1,\dots,N \text{ and }j=1,\dots,M\\ &x_i\in\{0,1\}\text{ for all } i=1,\dots,N \end{array}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\sum_{i=1}^N\sum_{j=1}^Md_jt_{ij}y_{ij}+\sum_{i=1}^Nf_ix_i}

In an uncapacitated facility problem, the amount of product each facility can produce and transport is assumed to be unlimited, and the optimal solution results in customers being supplied by the lowest-cost, and usually the nearest, facility. Using the above formulation, the unlimited capacity means Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_i} can be assumed to be a sufficiently large constant, while Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}} is now a binary variable, because the demand of each customer can be fully met with the nearest facility. If facility Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} supplies customer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}=1} ; otherwise Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}=0} .

Numerical Example

Suppose a paper products manufacturer has enough capital to build and manage an additional manufacturing plant in the United States in order to meet increased demand in three cities: New York City, NY, Los Angeles, CA, and Topeka, KS. The company already has distribution facilities in Denver, CO, Seattle, WA, and St. Louis, MO, and due to limited capital, cannot build an additional distribution facility. So, they must choose to build their new plant in one of these three locations. Due to geographic constraints, plants in Denver, Seattle, and St. Louis would have a maximum operating capacity of 400tons/day, 700 tons/day, and 600 tons/day, respectively. The cost of transporting the products from the plant to the city is directly proportional, and an outline of the supply, demand, and cost of transportation is shown in the figure below.

To solve this problem, we will assign the following variables:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} is the factory location

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} is the city destination

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{ij}} is the cost of transporting one ton of product from the factory to the city

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{ij}} is the amount of product transported from the factory to the city in tons

To determine where the company should build the factory, we will carry out the following optimization problem for each location:

min Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j\epsilon J}C_{ij}x_{ij} }

subject to

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j\epsilon J}x_{ij}\leqA_i }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{ij} \geq 0 for all i,j }

Applications

Facility location problems are utilized in many industries to find the optimal placement of various facilities, including warehouses, power plants, and public transportation terminals, to maximize efficiency and profit. In more unique applications, extensive research has been done in applying FLPs to waste management, for example. A case study by Nigerian researchers discussed the application of mixed-integer FLPs in optimizing the locations of waste collection centers to provide sanitation services in crucial communities. More effective waste collection systems could combat unsanitary practices and environmental pollution, which are major concerns in many developing nations [cite].

Conclusion

References

http://www.pitt.edu/~lol11/ie1079/notes/ie2079-weber-slides.pdf
Drezner, Z; Hamacher. H. W. (2004), Facility Location Applications and Theory. New York, NY: Springer.
Eiselt, H.A.; Marianov, V. (2019), Contributions to Location Analysis. Cham, Switzerland: Springer.