# Difference between revisions of "Facility location problems"

Aaronlitoff (Talk | contribs) |
Aaronlitoff (Talk | contribs) |
||

Line 37: | Line 37: | ||

In the uncapacitated 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. | In the uncapacitated 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 defined as a set of customers D, a set of facilities | + | 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 D to S customers that will be serviced by each facility such that the sum of facility costs and variable costs 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: <br> | ||

− | + | <br>A: The algorithm will stop after a given number of steps (e.g. number of customers and facilities) | |

+ | <br>B: There is an approximation ratio k such that the cost of the solution can not exceed k multiplied the optimum cost in any instance | ||

+ | |||

+ | the algorithm terminates after a number of steps that is bounded by a polynomial | ||

+ | in the instance size (e.g. in the number of customers and facilities). | ||

+ | There is a constant k such that the cost of the computed solution does not | ||

+ | exceed k times the optimum cost for any instance. | ||

==Examples and Applications== | ==Examples and Applications== | ||

Line 52: | Line 59: | ||

For example: | For example: | ||

− | [[File:AppleModel.png|thumb|left|upright= | + | [[File:AppleModel.png|thumb|left|upright=1.6|]] <br> <br> |

Define decision variables i=1,2,3,4 such that [[File:x21.png|350px|]]. <br> Then the total expected benefit is: [[File:x22.png|250px|]] <br> and the total capital needed is: [[File:x23.png|200px|]]<br> | Define decision variables i=1,2,3,4 such that [[File:x21.png|350px|]]. <br> Then the total expected benefit is: [[File:x22.png|250px|]] <br> and the total capital needed is: [[File:x23.png|200px|]]<br> | ||

Line 59: | Line 66: | ||

− | Additional constrains are that the total available capital is $16M, and the number of new stores should not be more than two. Solving this model using GAMS gives us the maximum when y2=y4=1 | + | Additional constrains are that the total available capital is $16M, and the number of new stores should not be more than two. Solving this model using an MILP solver in GAMS gives us the maximum when y2=y4=1. This indicates that the Logan Square and Hyde Park Apple stores should both be built in order to maximize profit. |

Note that in another formulation of this problem you could minimize distance for customers to travel to the store regardless of profit. | Note that in another formulation of this problem you could minimize distance for customers to travel to the store regardless of profit. | ||

Line 68: | Line 75: | ||

===Applications in Industry=== | ===Applications in Industry=== | ||

− | Facility location problems have applications in a wide variety of fields and projects. | + | Facility location problems have applications in a wide variety of fields and projects. As examined it can be used to find the optimal location for a store, plant, warehouse, etc. but these formulation methods can also be used is less obvious ways. Applications range from public policy (e.g. locating police officers in a city), telecommunications (e.g. cell towers in a network), and even particle physics (e.g. separation distance between repulsive charges).[] All of these problems have in common that discrete locations must be chosen and the objective is to meet the demand of consumers or users in the most efficient way. [5] |

− | + | ||

− | (e.g. | + | |

− | + | ||

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

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

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

Line 103: | Line 95: | ||

[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. | [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. | ||

− | + | [5] Vygen, J. (2005). Approximation algorithms for facility location problems. Bonn, Germany: Research Institute for Discrete Mathematics. | |

## Revision as of 22:39, 24 May 2015

Author: Aaron Litoff

Stewards: Dajun Yue and Fengqi You

The 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 consists of selection 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 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.

The Fermat-Weber Problem given mathematically:

Given a finite number of distinct points File:Example.jpg and positive multipliers File:Example.jpg find a point File:Example.jpg
that minimizes File:Example.jpg

.
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 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

In the uncapacitated 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 D to S customers that will be serviced by each facility such that the sum of facility costs and variable costs 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 k such that the cost of the solution can not exceed k multiplied the optimum cost in any instance

the algorithm terminates after a number of steps that is bounded by a polynomial in the instance size (e.g. in the number of customers and facilities). There is a constant k such that the cost of the computed solution does not exceed k times the optimum cost for any instance.

## Examples and Applications

### A Real World Example

Suppose you are a manager at Apple and you are identifying locations to sell computers and iPhones in a new location in Chicago. You would start by identifying potential sites in a variety of neighborhoods throughout the city and finding the demand for Apple products in each neighborhood. Then to construct your model you could create a table of neighborhoods, the cost of building a new Apple store in each one and the expected profit. Your goal now is to select which facilities should be built in order to maximize profit.

For example:

Define decision variables i=1,2,3,4 such that .

Then the total expected benefit is:

and the total capital needed is:

In total, the model can be given as:

Additional constrains are that the total available capital is $16M, and the number of new stores should not be more than two. Solving this model using an MILP solver in GAMS gives us the maximum when y2=y4=1. This indicates that the Logan Square and Hyde Park Apple stores should both be built in order to maximize profit.

Note that in another formulation of this problem you could minimize distance for customers to travel to the store regardless of profit.

### Applications in Industry

Facility location problems have applications in a wide variety of fields and projects. As examined it can be used to find the optimal location for a store, plant, warehouse, etc. but these formulation methods can also be used is less obvious ways. Applications range from public policy (e.g. locating police officers in a city), telecommunications (e.g. cell towers in a network), and even particle physics (e.g. separation distance between repulsive charges).[] All of these problems have in common that discrete locations must be chosen and the objective is to meet the demand of consumers or users in the most efficient way. [5]

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.

[5] Vygen, J. (2005). Approximation algorithms for facility location problems. Bonn, Germany: Research Institute for Discrete Mathematics.

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.