Sequential location-allocation problems on chains and trees with probabilistic link demands. (English) Zbl 0569.90019

Cavalier, Tom M.; Sherali, Hanif D.

Math. Program. 32, 249-277 (1985).

We consider multiperiod minisum location problems on networks in which demands can occur continuously on links according to a uniform probability density function. In addition, demands may change dynamically over time periods and at most one facility can be located per time period. Two types of networks are considered in conjunction with three behavioral strategies. The first type of network discussed is a chain graph. A myopic strategy and long-range strategy for locating p- facilities are considered, as is a discounted present worth strategy for locating two facilities. Although these problems are generally nonconvex, effective methods are developed to readily identify all local and global minima. This analysis forms the basis for similar problems on tree graphs. In particular, we construct algorithms for the 3-facility myopic problem and the 2-facility long-range and discounted cost problems on a tree graph. Extensions and suggestions for further research on problems involving more general networks are provided.

MSC:

90B05	Inventory, storage, reservoirs
90C90	Applications of mathematical programming

Keywords:

sequential location-allocation; probabilistic link demands; dynamic location; p-median; multiperiod minisum location problems on networks; chain graph; myopic strategy; long-range strategy; tree graphs

References:

[1]	T.M. Cavalier and H.D. Sherali, ”Network location problems with continuous link demands:p-medians on a chain, 2-medians on a tree, and 1-median on isolated cycle graphs”, working paper, Department of Industrial Engineering and Operations Research, Virginia Polytechnic Institute and State University (1983).
[2]	Samuel S. Chiu, ”The minisum location problem on an undirected network with continuous link demands”, Presented at the Joint National ORSA/TIMS Meeting, San Diego (November, 1982). · Zbl 0625.90025
[3]	J.W. Chrissis, R.P. Davis and D.M. Miller, ”The dynamic set covering problem”, paper presented at the TIMS/ORSA Joint National Meeting, New York (1978).
[4]	J.W. Chrissis, ”Locating emergency service facilities in a developing area”,Fire Technology 16(1) (1980) 63–69.
[5]	D. Erlenkotter, ”A dual-based procedure for uncapacitated facility location”,Operations Research 26(6) (1978) 992–1009. · Zbl 0422.90053
[6]	D. Erlenkotter, ”A comparative study of approaches to dynamic location problems”,European Journal of Operational Research 6 (1981) 133–143. · Zbl 0451.90038
[7]	C.O. Fong and V. Srinivasan, ”The multiregion dynamic capacity expansion problem, part I”,Operations Research 29(4) (1981a) 787–799. · Zbl 0463.90037
[8]	C.O. Fong and V. Srinivasan, ”The multiregion dynamic capacity expansion problem, part II”,Operations research 29(4) (1981b) 800–816. · Zbl 0463.90038
[9]	A.J. Goldman, ”Optimal center location in simple networks”,Transportation Science 5(2) (1971) 212–221.
[10]	S.L. Hakimi, ”Optimum locations of switching centers and the absolute centers and medians of a graph”,Operations Research 12 (1964) · Zbl 0123.00305
[11]	S.L. Hakimi, ”Optimum distribution of switching centers in a communication network and some related graph theoretic problems”,Operations Research 13 (1965) 462–475. · Zbl 0135.20501
[12]	G.Y. Handler and P.B. Mirchandani,Location on networks (The MIT Press, Cambridge, Massachusetts, 1979). · Zbl 0533.90026
[13]	V.R. Khachaturov and N.B. Astakhov, ”Dynamic location problems (models and solution methods)”,Matekon 13(1976) 68–93.
[14]	E. Minieka, ”The centers and medians of a graph”,Operations Research 25(4) (1977) 641–650. · Zbl 0383.90046
[15]	E. Minieka, ”Conditional centers and medians of a graph”,Networks 10(3) (1980) 265–272.
[16]	R.C. Rao and D.P. Rutenberg, ”Multilocation plant sizing and timing”,Management Science 23(11) (1977) 1187–1198. · Zbl 0368.90095
[17]	R.E. Rosenthal, J.A. White and D. Young, ”Stochastic dynamic location analysis”,Management Science 24(6) (1978) 645–653. · Zbl 0381.90097
[18]	A.J. Scott, ”Location-allocation systems: a review”,Geographical Analysis 2(2) (1970) 95–119.
[19]	D.J. Sweeny and T.L. Tatham, ”An improved long-run model for multiple warehouse location”,Management Science 22(7) (1976) 748–758. · Zbl 0327.90029
[20]	C.S. Tapiero, ”Transportation-location-allocation problems over time”,Journal of Regional Science 11(5) (1971) 377–384.
[21]	W.G. Truscott, ”Timing market entry with a contribution-maximization approach to location-allocation decisions”,European Journal of Operational Research 4 (1980) 95–106. · Zbl 0421.90011
[22]	T.J. Van Roy and D. Erlenkotter, ”A dual based procedure for dynamic facility location”,Management Science 28(10) (1982) 1091–1105. · Zbl 0495.90033