Facility location problem: Difference between revisions
Lawrenceli (talk | contribs) |
Lawrenceli (talk | contribs) |
||
| Line 28: | Line 28: | ||
<math display="inline">\begin{array}{rl} | <math display="inline">\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 \\ | \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{ | \text{s.t.} & \displaystyle\sum_{i=1}^Ny_{ij}=1\forall j\in\text {1,...,M}\1,\dots,M \\ | ||
& \displaystyle \sum_{j=1}^Md_jy_{ij}\ | & \displaystyle \sum_{j=1}^Md_jy_{ij}\leq k_ix_i\text{ for all }i=1\dots,N \\ | ||
&y_{ij}\ | &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 | &x_i\in\{0,1\}\text{ for all } i=1,\dots,N | ||
\end{array}</math> | \end{array}</math> | ||
<math>\min\sum_{i=1}^N\sum_{j=1}^ | <math>\min\sum_{i=1}^N\sum_{j=1}^Md_jt_{ij}y_{ij}+\sum_{i=1}^Nf_ix_i</math> | ||
== Applications == | == Applications == | ||
Revision as of 15:00, 15 November 2020
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 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 N} points 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 (a_1,b_1)...(a_N,b_N)} on a plane with associated weights 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 w_1...w_N} , the 2-dimensional Weber problem to find the geometric median 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,y)} is formulated as(1)
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 \underset{x,y}{min}\{W(x,y)=\sum_{i=1}^Nw_id_i(x,y,a_i,b_i)\}}
where
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_i(x,y,a_i,b_i)=\sqrt{(x-a_i)^2+(y-b_i)^2}}
Uncapacitated and Capacitated FLPs
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.
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 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 N} facilities and 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 M} customers, the capacitated formulation defines a binary variable 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_i} and a variable 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}} for each 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 each 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} . 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} is open, 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_i=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 x_i=0} . Open facilities have an associated fixed cost 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 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\forall j\in\text {1,...,M}\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}