The multi-facility min-max Weber problem. (English) Zbl 0542.90033

Summary: An algorithm is presented to solve the problem of locating a given number of facilities on the plane amongst given customers so that the maximum weighted distance from any facility to the customers it services is minimised. The algorithm successfully overcomes the allocation aspects of this problem by generating partitions of customers using a method originally designed for graph colouring embedded within a modified bisection search. Problems of 50 customers and three facilities can be solved in entirely acceptable computer times.


90B05 Inventory, storage, reservoirs
Full Text: DOI


[1] Brown, J.R., Chromatic scheduling and the chromatic number problem, Management science, 19, 4, 456-463, (1972) · Zbl 0247.90028
[2] Christofides, N., Graph theory: an algorithmic approach, (1975), Academic Press New York and London · Zbl 0321.94011
[3] Drezner, Z.; Wesolowsky, G.O., Single facility lp-distance MIN-MAX location, SIAM journal of algebraic and discrete mathematics, 1, 315-321, (1980) · Zbl 0501.90031
[4] Eilon, S.; Watson-Gandy, C.D.T.; Christofides, N., Distribution management: mathematical modelling and practical analysis, (1971), Griffin, High Wycombe Bucks, England
[5] Elzinga, D.J.; Hearn, D.W., Geometrical solutions for some minimax location problems, Transportation science, 6, 4, 379-394, (1972)
[6] Elzinga, D.J.; Hearn, D.W.; Randolph, W.R., Minimax multi-facility location with Euclidean distances, Transportation science, 10, 4, 321-336, (1976)
[7] Francis, R.L.; White, J.A., Facility layout and location, (1974), Prentice-Hall Englewood Cliffs, NJ
[8] Jacobsen, S.K., An algorithm for the MIN-MAX Weber problem, European journal of operational research, 6, 2, 144-148, (1981) · Zbl 0452.90024
[9] Rademacher, H.; Toeplitz, D., The enjoyment of mathematics, (1957), Princeton University Press Princeton, NJ · Zbl 0078.00114
[10] Revelle, C.; Marks, D.; Liebman, J.C., An analysis of private and public sector location models, Management science, 16, 11, 692-707, (1970) · Zbl 0195.21901
[11] Hansen, P.; Peeters, D.; Thisse, J.F., Public facility location models: a selective survey, () · Zbl 0469.90027
[12] Watson-Gandy, C.D.T., The solution of distance constrained mini-sum location problems, () · Zbl 0569.90020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.