Facility Location
- PDF / 281,250 Bytes
- 6 Pages / 547.087 x 737.008 pts Page_size
- 100 Downloads / 223 Views
F
F
Facility Location 1997; Shmoys, Tardos, Aardal KAREN AARDAL1,2 , JAROSLAW BYRKA 1,2 , MOHAMMAD MAHDIAN3 1 CWI, Amsterdam, The Netherlands 2 Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands 3 Yahoo! Research, Santa Clara, CA, USA Keywords and Synonyms Plant location; Warehouse location Problem Definition Facility location problems concern situations where a planner needs to determine the location of facilities intended to serve a given set of clients. The objective is usually to minimize the sum of the cost of opening the facilities and the cost of serving the clients by the facilities, subject to various constraints, such as the number and the type of clients a facility can serve. There are many variants of the facility location problem, depending on the structure of the cost function and the constraints imposed on the solution. Early references on facility location problems include Kuehn and Hamburger [35], Balinski and Wolfe [8], Manne [40], and Balinski [7]. Review works include Krarup and Pruzan [34] and Mirchandani and Francis [42]. It is interesting to notice that the algorithm that is probably one of the most effective ones to solve the uncapacitated facility location problem to optimality is the primal-dual algorithm combined with branch-and-bound due to Erlenkotter [16] dating back to 1978. His primaldual scheme is similar to techniques used in the modern literature on approximation algorithms. More recently, extensive research into approximation algorithms for facility location problems has been carried out. Review articles on this topic include Shmoys [49,50]
and Vygen [55]. Besides its theoretical and practical importance, facility location problems provide a showcase of common techniques in the field of approximation algorithms, as many of these techniques such as linear programming rounding, primal-dual methods, and local search have been applied successfully to this family of problems. This entry defines several facility location problems, gives a few historical pointers, and lists approximation algorithms with an emphasis on the results derived in the paper by Shmoys, Tardos, and Aardal [51]. The techniques applied to the uncapacitated facility location (UFL) problem are discussed in some more detail. In the UFL problem, a set F of nf facilities and a set C of nc clients (also known as cities, or demand points) are given. For every facility i 2 F , the facility opening cost is equal to f i . Furthermore, for every facility i 2 F and client j 2 C , there is a connection cost cij . The objective is to open a subset of the facilities and connect each client to an open facility so that the total cost is minimized. Notice that once the set of open facilities is specified, it is optimal to connect each client to the open facility that yields smallest connection cost. Therefore, the objective is to find a set P P S F that minimizes i2S f i + j2C min i2S fc i j g. This definition and the definitions of other variants of the facility location prob
Data Loading...
