Difference between revisions of "Facility location problem"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 24: Line 24:
 
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.
 
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 <math>N</math> facilities and <math>M</math> customers, the capacitated formulation defines a binary variable <math>x_i</math> and a variable <math>y_{ij}</math> for each facility <math>i</math> and each customer <math>j</math>. If facility <math>i</math> is open, <math>x_i=1</math>; otherwise <math>x_i=0</math>. <math>y_{ij}</math> is the fraction of the total demand <math>d_j</math> from customer <math>j</math> that facility <math>i</math> has satisfied. The transportation cost between facility <math>i</math> and customer <math>j</math> is represented as <math>c_{ij}</math>. The capacitated FLP is therefore defined as
+
In a problem with <math>N</math> facilities and <math>M</math> customers, the capacitated formulation defines a binary variable <math>x_i</math> and a variable <math>y_{ij}</math> for each facility <math>i</math> and each customer <math>j</math>. If facility <math>i</math> is open, <math>x_i=1</math>; otherwise <math>x_i=0</math>. <math>y_{ij}</math> is the fraction of the total demand <math>d_j</math> from customer <math>j</math> that facility <math>i</math> has satisfied. The transportation cost between facility <math>i</math> and customer <math>j</math> is represented as <math>c_{ij}</math> and each  facility <math>i</math> has a maximum capacity <math>k_i</math>. The capacitated FLP is therefore defined as
  
 
<math display="inline">\begin{array}{rl}
 
<math display="inline">\begin{array}{rl}
 
\min & \displaystyle\sum_{i=1}^N\sum_{j=1}^Mc_{ij} d_j y_{ij}+\sum_{i=1}^Nf_ix_i \\
 
\min & \displaystyle\sum_{i=1}^N\sum_{j=1}^Mc_{ij} d_j 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 \\
 
\text{s.t.} & \displaystyle\sum_{i=1}^Ny_{ij}=1 \text{ for all }j=1,\dots,M \\
& \displaystyle \sum_{j=1}^Md_jy_{ij}\leqslant u_ix_i\text{ for all }i=1\dots,N \\
+
& \displaystyle \sum_{j=1}^Md_jy_{ij}\leqslant k_ix_i\text{ for all }i=1\dots,N
&y_{ij}\geqslant0\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}</math>
 
\end{array}</math>
  

Revision as of 20:01, 14 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 points on a plane with associated weights , the 2-dimensional Weber problem to find the geometric median is formulated as(1)

where

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 facilities and customers, the capacitated formulation defines a binary variable and a variable for each facility and each customer . If facility is open, ; otherwise . is the fraction of the total demand from customer that facility has satisfied. The transportation cost between facility and customer is represented as and each facility has a maximum capacity . The capacitated FLP is therefore defined as

Applications

Conclusion

References

  1. http://www.pitt.edu/~lol11/ie1079/notes/ie2079-weber-slides.pdf