Abstract
We present a solution method for location-allocation problems involving thel p norm, where 1 <p < ∞. The method relaxes the {0, 1} constraints on the allocations, and solves for both the locations and allocations simultaneously. Necessary and sufficient conditions for local minima of the relaxed problem are stated and used to develop an iterative algorithm. This algorithm finds a stationary point on a series of subspaces defined by the current set of activities. The descent direction is a projection onto the current subspace of a direction incorporating second-order information for the locations, and first-order information for the allocations. Under mild conditions, the algorithm finds local minima with {0, 1} allocations and exhibits quadratic convergence. An implementation that exploits the special structure of these problems to dramatically reduce the computational cost of the required numerical linear algebra is described. Numerical results for thirty-six test problems are included.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.J. Bartholdi, III, and L.K. Platzman, “Heuristics based on spacefilling curves for combinatorial problems in Euclidean space,”Management Science 34 (1988) 291–305.
I. Bongartz, “A projection method forl p -norm location-allocation problems,” Ph.D. Thesis, University of Waterloo (Waterloo, Ontario, 1991).
I. Bongartz, P.H. Calamai and A.R. Conn, “A second-order algorithm for the continuous capacitated locationallocation problem,” in preparation.
J. Brimberg and R.F. Love, “Estimating travel distances by the weightedl p norm,”Naval Research Logistics 38 (1991) 241–259.
P.H. Calamai and A.R. Conn, “A projected Newton method forl p -norm location problems,”Mathematical Programming 38 (1987) 75–109.
R. Chen, “Solution of minisum and minimax location-allocation problems with Euclidean distances,”Naval Research Logistics Quarterly 30 (1983) 449–459.
A.R. Conn and G. Cornuéjols, “A projection method for the uncapacitated facility location problem,”Mathematical Programming 46 (1990) 273–298.
L. Cooper, “Location-allocation problems,”Operations Research 11 (1963) 331–343.
L. Cooper, “Heuristic methods for location-allocation problems,”SIAM Review 6 (1964) 37–53.
L. Cooper, “Solutions of generalized locational equilibrium models,”Journal of Regional Science 7 (1967) 1–18.
J.J. Dongarra, “Performance of various computers using standard linear equations software,” Technical Report CS-89-85, Oak Ridge National Laboratory, Oak Ridge, TN 37831, 1991.
S. Eilon, C.D.T. Watson-Gandy and N. Christofides,Distribution Management: Mathematical Modelling and Practical Analysis (Griffin, London, 1971).
A.M. El-Shaieb, “A new algorithm for locating sources among destinations,”Management Science 20 (1973) 221–231.
R. Fletcher,Practical Methods of Optimization (John Wiley & Sons, New York, 1987).
P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, New York, 1981).
R.E. Kuenne and R.M. Soland, “Exact and approximate solutions to the multisource Weber problem,”Mathematical Programming 3 (1972) 193–209.
H.W. Kuhn, “A note on Fermat's problem,”Mathematical Programming 4 (1973) 98–107.
H.W. Kuhn and R.E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,”Journal of Regional Science 4 (1962) 21–33.
R.F. Love and H. Juel, “Properties and solution methods for large location—allocation problems,”Journal of the Operational Research Society 33 (1982) 443–452.
C. Michelot, “Properties of a class of location-allocation problems,”Cahiers du C.E.R.O. 29 (1987) 105–114.
W. Miehle, “Link-length minimization in networks,”Operations Research 6 (1958) 232–243.
Wayne Morris, President, Kitchener-Waterloo Regional Ambulance Inc., private communication.
B.A. Murtagh and S.R. Niwattisyawong, “An efficient method for the multi-depot location-allocation problem,”Journal of the Operational Research Society 33 (1982) 629–634.
B.A. Murtagh and M.A. Saunders, “Large-scale linearly constrained optimization,”Mathematical Programming 14 (1978) 41–72.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (John Wiley & Sons, New York, 1988).
W.H. Press, B.P. Flannery, S.A. Teukolsky and W.T. Vetterling,Numerical Recipes: The Art of Scientific Computing (Cambridge University Press, Cambridge, 1986).
K.E. Rosing, “An optimal method for solving the (generalized) multi-Weber problem,”European Journal of Operational Research 58 (1992) 414–426.
S.Z. Selim and A.H. Al-Rabeh, “Determining dominant wind directions for oil spill trajectory models,” Department of Systems Engineering, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia (unpublished), 1992.
Author information
Authors and Affiliations
Additional information
This research was supported in part by Natural Sciences and Engineering Research Council (NSERC) of Canada grants A-5671 and A-8639, and by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.
Corresponding author.
Rights and permissions
About this article
Cite this article
Bongartz, I., Calamai, P.H. & Conn, A.R. A projection method forl p norm location-allocation problems. Mathematical Programming 66, 283–312 (1994). https://doi.org/10.1007/BF01581151
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581151