Abstract
The single facility location problem with general attraction and repulsion functions is considered. An algorithm based on a representation of the objective function as the difference of two convex (d.c.) functions is proposed. Convergence to a global solution of the problem is proven and extensive computational experience with an implementation of the procedure is reported for up to 100,000 points. The procedure is also extended to solve conditional and limited distance location problems. We report on limited computational experiments on these extensions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chen, R. (1988), Conditional minisum and minimax location-allocation problems in Euclidean space,Transportation Science 22, 157–160.
Chen, P., Hansen, P., Jaumard B. and Tuy, H. (1992), Weber's problem with attraction and repulsion,Journal of Regional Science 32, 467–486.
Chen, P., Hansen, P., Jaumard, B. and Tuy, H. (1994), Solution of the multisource Weber and Conditional Weber Problems by D.-C. Programming, Technical Report # G-92-35, Revised March 1994, GERAD, University of Montreal, Montreal, Canada.
Drezer, Z., Mehrez, A. and Wesolowsky, G.(1991), The facility location problem with limited distances,Transportation Science 25, 183–187.
Drezner, Z., and Wesolowsky, G. (1990), The Weber problem on the plane with some negative weights,INFOR 29, 87–99.
Horst, R. and Tuy, H. (1993),Global Optimization, Kluwer Academic Press, second edition, Dordrecht, The Netherlands.
Idrissi, H., Loridan, P. and Michelot, C. (1988), Approximation of solutions for location problems,Journal of Optimization Theory and Applications 56, 127–143.
Love, R. E., Morris, J. G. and Wesolowsky, G. O. (1988)Facilities Location: Models and Methods, North-Holland, Amsterdam.
Maranas, C. D. and Floudas, C. A. (1994) A global optimization method for Weber's problem with attraction and repulsion, inLarge Scale Optimization: State of the Art, eds. W. W. Hager, D. W. Hearn and P.M. Pardalos, Kluwer Academic Publishers, Dordrecht, The Netherlands, 259–293.
Rockafellar, R. T. (1970),Convex Analysis, Princeton University Press, Princeton, NJ.
Tuy, H. (1987), Global minimization of a difference of convex functions,Mathematical Programming Study 30, 150–182.
Tuy, H. (1990), On a polyhedral annexation method for concave minimization, inFunctional Analysis, Optimization and Mathematical Economics, eds. L.J. Leifman and J.B. Rosen, Oxford University Press, Oxford, 248–260.
Tuy, H. (1991), Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms,Journal of Global Optimization 1, 23–36.
Tuy, H. (1991), Polyhedral annexation, dualization and dimension reduction technique in global optimization,Journal of Global Optimization 1, 229–244.
Tuy, H. (1992), On nonconvex optimization problems with separated nonconvex variables,Journal of Global Optimization 2, 133–144.
Tuy, H. (1993), D.C. Optimization: theory, methods and algorithms, Preprint, Institute of Mathematics, Hanoi.
Tuy, H. (1994), A general d.c. approach to location problems, Preprint, Institute of Mathematics, Hanoi.
Tuy, H. and Al-Khayyal, F. A. (1992), Global optimization of a nonconvex single facility problem by sequential unconstrained convex minimization,Journal of Global Optimization 2, 61–71.
Tuy, H. and Thuong, N. V. (1988), On the global minimization of a convex function under general nonconvex constraints,Applied Mathematics and Optimization 18, 119–142.
Weber, A. (1909),Ueber den Standort der Industrien, Tübingen (English translation: C.J Friedrich (translator), 1929, Theory of the Location of Industries, University of Chicago Press, Chicago.
Weiszfeld, E. (1937), Sur le point pour lequel la somme des distances den points donnés est minimum,Tôhoku Mathematical Journal 43, 355–386.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation Grant DDM-91-14489.
Rights and permissions
About this article
Cite this article
Tuy, H., Al-Khayyal, F. & Zhou, F. A D.C. optimization method for single facility location problems. J Glob Optim 7, 209–227 (1995). https://doi.org/10.1007/BF01097061
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01097061