Discrete Location Problems ballred.gif (861 bytes) Benchmarks Library
line.jpg (1129 bytes)

Simple Plant
Location Problem

ballred.gif (861 bytes)  Home Benchmarks Library  

ballred.gif (861 bytes)  Optimization Algorithms

ballred.gif (861 bytes)  Benchmarks

ballred.gif (861 bytes)  Demo software


There are different titles for the simple plant  location problem: 

  • the problem of a nonrecoverable tools optimal system [1];

  • the standartization and unification problem [2];

  • the optimal parameter problem for the uniform technical system [3];

  • the location of bank accounts problem [4];

  • warehouse location problem [5];

  • uncapacitated facility location problem [6] etc.

Because of the academical interest to one investigation this problem has different interpretations as for many mathematical models. We will use the most popular terminology of discrete location problem to describe the model although the others interpretations will possible too.

Let a set I ={1N} give potential facility locations by production some uniform product. A facility can be opened in any location i  I, opening a facility at location i has nonnegative cost. Each open facility can provide an unlimited amount of commodity.

Let a set J ={1M} assign customers that require service. For each pair i, j is given the process or transportation costs gij0. The goal is to determine a subset of the set of potential facility locations , at which to open facilities and an assigment of all clients to these facilities so as to minimize the overall total cost. The problem can be write as the following:

Stated problem is the generalization of the well-known set covering problem and, therefore, it is NP-hard problem in the strongly sense. Exact algorithms, approximation algorithms with constant performance guarantee, Lagrangian heuristics, randomized iteration algorithms of local search were developed for solving simplest location problem. Polynomially solvable classes of problem were found. The reader can find the review of results for this problem, for example, in [7].

 REFERENCES

  1. Beresnev V. L., Gimady Ed. H., Dementev V. T. Extremal problems of standartization. Novosibirsk : Science, 1978.

  2. Gimady Ed. H. The choice of optimal scales in one problem class of location or standartization. Manage systems. Edition 6 (1970) Novosibirsk, Sobolev Institute of mathematics of the Siberian branch of the Academy of Science of the Soviet Union, pages 57-70.

  3. Beresnev V. L. About one class of problems of parameter optimization of similar technical system. Manage systems. Edition 9 (1971) Novosibirsk, Sobolev Institute of  mathematics of the Siberian branch of the Academy of Science of the Soviet Union, pages 65-74.

  4. Cornuejols G., Fisher M.L., Nemhauser G.L. Location of bank accounts to optimize float. Management Science. v22 (1977), pp 789-810.

  5. Khumawala B.M. An Efficient Branch-Bound Algorithm for the Warehouse Location Problem. Management Science. v18 (1972), pp 718-731.

  6. Krarup J., Pruzan P.M. The simple plant location problem: Survey and synthesis. European Journal of Operational Research. v12 (1983),  pp 36-81.

  7. Mirchandani P.B., Francis R.L. Discrete Location Theory. John Wiley & Sons, 1990.

  8. M.R. Garey and D.S. Johnson Computers and Interactability. W.H. Freeman and Company. San Francisco 1979.


ballred.gif (861 bytes) Home ballred.gif (861 bytes)