Difference between revisions of "Facility location problems"

From optimization
Jump to: navigation, search
Line 13: Line 13:
 
"''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.''" [1]
 
"''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.''" [1]
  
In 1909 Alfred Weber used a three point version to model possible industrial locations in order to minimize transportation costs from two sources to a single customer. [2] This is one the simplest continuous facility location models.
+
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 market. [2] This formulation is one the simplest continuous facility location models.
  
  
Line 20: Line 20:
 
A modern day engineering interpretation could be as follows:<br>
 
A modern day engineering interpretation could be as follows:<br>
 
"''Find the best location for a refining plant between three cities in such a way that the sum of the connections between the plant and the cities in minimal.''"
 
"''Find the best location for a refining plant between three cities in such a way that the sum of the connections between the plant and the cities in minimal.''"
 +
 +
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! [4]
  
  
Line 35: Line 37:
  
  
Applications in physics, solution to Fermat-Weber problem allowing for "repulsion" or negative distances.
+
 
  
 
===Applications in Industry===
 
===Applications in Industry===
 +
 +
applications in diverse �elds including public policy (e.g., locating �re stations in a city), telecommunications
 +
(e.g., locating base stations in wireless networks), and information retrieval (e.g., clustering
 +
of documents)
 +
 +
 +
http://www.researchgate.net/profile/C_Plaxton/publication/222936253_Analysis_of_a_Local_Search_Heuristic_for_Facility_Location_Problems/links/0912f51084571496af000000.pdf
 +
 +
Applications in physics, solution to Fermat-Weber problem allowing for "repulsion" or negative distances.
 +
 +
 +
Many economical decision problems concern selecting and/or placing certain facilities
 +
to serve given demands efficiently. Examples are manufacturing plants,
 +
storage facilities, depots, warehouses, libraries, fire stations, hospitals, base stations
 +
for wireless services (like TV broadcasting or mobile phone service), etc.
 +
The problems have in common that a set of facilities, each with a certain position,
 +
has to be chosen, and the objective is to meet the demand (of customers,
 +
users etc.) best. Facility location problems, which occur also in less obvious
 +
contexts, indeed have numerous applications.
 +
 +
http://www.or.uni-bonn.de/~vygen/files/fl.pdf
  
 
==Conclusion==
 
==Conclusion==
Line 47: Line 70:
  
 
[2] Drezner, Z & Hamacher. H. W. (2004). Facility location: applications and theory. New York, NY: Springer.
 
[2] Drezner, Z & Hamacher. H. W. (2004). Facility location: applications and theory. New York, NY: Springer.
 +
 +
[3] Weisstein, E. W. Fermat Points. Mathworld-- A wolfram web resource. http://mathworld.wolfram.com/FermatPoints.html
 +
 +
[4] Kuhn, H. W. and Kuenne, R. E. (1962). An efficient algorithm for the numerical solution of the generalized weber problem in spatial economics. Journal of Regional Science, 4.
 +
 +
 +
  
  

Revision as of 20:22, 24 May 2015

Author: Aaron Litoff
Stewards: Dajun Yue and Fengqi You

MILP [1]


The facility location problem deals with selecting the placement of a facility (often from a list of integer possibilities) to best meet the demanded constraints. The problem consists of finding the location to build a factory 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 customers.

Contents

History

The Fermat-Weber problem was one of the first facility location problems every 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." [1]

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 market. [2] This formulation is one the simplest continuous facility location models.


Alt text
The Fermat Point, or Torricelli Point, is the solution that minimizes distances from A, B, and C (the three corners of the black triangle).[3]

A modern day engineering interpretation could be as follows:
"Find the best location for a refining plant between three cities in such a way that the sum of the connections between the plant and the cities in minimal."

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! [4]


Description and Formulation

Binary decision variables

Examples and Applications

A Real World Example

Suppose you are a manager at a company that builds Warehouse needs to be built in a central location so that the transportation costs are minimized



Applications in Industry

applications in diverse �elds including public policy (e.g., locating �re stations in a city), telecommunications (e.g., locating base stations in wireless networks), and information retrieval (e.g., clustering of documents)


http://www.researchgate.net/profile/C_Plaxton/publication/222936253_Analysis_of_a_Local_Search_Heuristic_for_Facility_Location_Problems/links/0912f51084571496af000000.pdf

Applications in physics, solution to Fermat-Weber problem allowing for "repulsion" or negative distances.


Many economical decision problems concern selecting and/or placing certain facilities to serve given demands efficiently. Examples are manufacturing plants, storage facilities, depots, warehouses, libraries, fire stations, hospitals, base stations for wireless services (like TV broadcasting or mobile phone service), etc. The problems have in common that a set of facilities, each with a certain position, has to be chosen, and the objective is to meet the demand (of customers, users etc.) best. Facility location problems, which occur also in less obvious contexts, indeed have numerous applications.

http://www.or.uni-bonn.de/~vygen/files/fl.pdf

Conclusion

References

[1] Dorrie, H. (1965) 100 great problems of elementary mathematics: their history and solution. New York, NY: Dover Publications.

[2] Drezner, Z & Hamacher. H. W. (2004). Facility location: applications and theory. New York, NY: Springer.

[3] Weisstein, E. W. Fermat Points. Mathworld-- A wolfram web resource. http://mathworld.wolfram.com/FermatPoints.html

[4] Kuhn, H. W. and Kuenne, R. E. (1962). An efficient algorithm for the numerical solution of the generalized weber problem in spatial economics. Journal of Regional Science, 4.



Author, A. A., & Author, B. B. (Date of publication). Title of article. Title of Online Periodical, volume number(issue number if available). Retrieved from http://www.someaddress.com/full/url/

Last, F. M. (Year Published) Book. City, State: Publisher.