When deterministic assumptions in ‘classical’ location problems are relaxed some new theoretical and algorithmic problems arise. In this paper, the definition of medians is generalized to the cases: (1) when generated demands and travel costs are random, and (2) when the demand induced at the facilities is random because of competition. Under a particular set of assumptions, the well-known theorems on ‘optimality of node locations' hold for the underlying ‘probabilistic networks’.
For case (1) the model is shown to be a generalization of the probabilistic and deterministic median location problems on networks. The relationship of the model to a multicommodity location problem is also pointed out. Additionally, within the framework of the problem formulation, certain parallels with multiobjective location problems are drawn. For case (2), the competitive median location problem is formulated, and some results presented.
For the special structure of probabilistic tree networks some interesting localization properties for the 1-median and 2-median are discussed.
Get full access to this article
View all access options for this article.
References
1.
AkincU, 1978“Multi-product capacitated facility location” WP-79-02, School of Management, State University of New York at Binghamton, Binghamton, NY
2.
BermanO, 1977Dynamic Positioning of Mobile Servers on Networks doctoral dissertation, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA
3.
BermanOLarsonR COdoniA R, 1981“Developments in network location with mobile and congested facilities”European Journal of Operations Research6104–116
4.
CharnesACooperW, 1961Management Models and Industrial Applications of Linear Programming, Volume 1 (John Wiley, New York)
5.
CochraneJ LZelenyH (Eds), 1973Multicriteria Decision Making (University of South Carolina Press, Columbia, SC)
6.
CoelhoJ DWilsonA G, 1976“The optimum location and size of shopping centers”Regional Studies10413–421
7.
CohonJ L, 1978Multiobjective Programming and Planning (Academic Press, New York)
8.
CornuejolsGFisherM LNemhauserG L, 1977“Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms”Management Science23789–810
9.
DearingP MFrancisR LLoweT J, 1976“Convex location problems on tree networks”Operations Research24628–641
10.
ErlenkotterDLeonardiG, 1981“Facility location with spatially-interactive travel behavior” working paper, Western Management Science Institute, University of California at Los Angeles, Los Angeles, CA; also presented at the Second International Symposium on Locational Decisions, Denmark, June 1981
11.
FrankH, 1966“Optimum locations on a graph with probabilistic demands”Operations Research14409–421
12.
GeoffrionA MGravesG W, 1974“Multicommodity distribution system design by Benders decomposition”Management Science20822–844
13.
GoldmanA J, 1971“Optimal center location in simple networks”Transportation Science5212–221
14.
HakimiS L, 1964“Optimum location of switching centers and the absolute centers and medians of a graph”Operations Research12450–459
15.
HakimiS L, 1965“Optimum distribution of switching centers in a communication network and some related graph theoretic problems”Operations Research13462–475
16.
HakimiS L, 1981“On locating new facilities in a competitive environment” paper presented at the Second International Symposium on Locational Decisions, Denmark, June; available from S L Hakimi, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60201, USA
17.
HakimiS LMaheshwariS N, 1972“Optimum locations of centers in networks”Operations Research20967–973
18.
HalpernJ, 1976“The location of a center-median convex combination on an undirected tree”Journal of Regional Science16237–245
19.
HandlerG Y, 1973“Minimax location of a facility in an undirected tree graph”Transportation Science7287–293
20.
HandlerG YMirchandaniP B, 1979Location on Networks: Theory and Algorithms (MIT Press, Cambridge, MA)
21.
HodgsonM J, 1978“Toward more realistic allocation in location-allocation models: an interaction approach”Environment and Planning A101273–1285
22.
HodgsonM J, 1981“An interaction-based location-allocation model” paper presented at the Second International Symposium on Locational Decisions, Denmark, June; available from M J Hodgson, Department of Geography, University of Alberta, Edmonton, Canada T6G 2H4
23.
JarvisJ P, 1975“Optimization in stochastic service systems with distinguishable servers” IRP-TR-19-75, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA
24.
KarivQHakimiS L, 1979“An algorithmic approach to network location problems. Part 2: the p-median”SIAM Journal of Applied Mathematics37539–560
25.
LarsonR C, 1974“A hypercube queuing model for facility location and redistricting in urban emergency services”Computers and Operations Research167–95
26.
LeaA C, 1978“A model taxonomy and a view of research frontiers in normative locational modeling” paper presented at the First Symposium on Locational Decisions, Banff, Alberta, Canada, April; available from A C Lea, Department of Geography, University of Minnesota, Minneapolis, MN 55455, USA
27.
LeonardiG, 1978“Optimum facility location by accessibility maximizing”Environment and Planning A101287–1305
28.
LoweT J, 1978“Efficient solutions in multiobjective tree network location problems”Transportation Science12298–316
29.
MirchandaniP B, 1980“Locational decisions on stochastic networks”Geographical Analysis12173–183
30.
MirchandaniP BOdoniA, 1979“Location of medians on stochastic networks”Transportation Science1385–97
31.
MirchandaniP BOudjitA, 1980“Localizing 2-medians on probabilistic and deterministic tree networks”Networks10329–350
32.
MirchandaniP BOudjitAWongR T, 1981“Locational decisions on stochastic multidimensional networks” CPS-8105, Laboratory for Large Scale Systems, Rensselaer Polytechnic Institute, Troy, NY; also presented at the Second International Symposium on Locational Decisions, Denmark, June 1981
33.
NeebeA WKhumawalaB M, 1981“An improved algorithm for the multicommodity location problem”Journal of Operation Research Society32143–149
34.
OudjitA, 1981Median Locations on Probabilistic and Deterministic Multidimensional Networks PhD dissertation, Rensselaer Polytechnic Institute, Troy, NY
35.
RaiffaH, 1968Decision Analysis: Introductory Lectures on Choices under Uncertainty (Addison-Wesley, Reading, MA)
36.
SeniorM LWilsonA G, 1974“Exploration and syntheses of linear programming and spatial interaction models of residential location”Geographical Analysis6209–238
37.
WarszawskiA, 1973“Multidimensional location problems”Operations Research Quarterly24165–169
38.
WendellR EHurterA P, 1973“Optimal locations on a network”Transportation Science718–33
39.
WendellR EMcKelveyR D, 1981“New perspectives in competitive location theory”European Journal of Operations Research6174–182
40.
WilsonA G, 1970“The use of the concept of entropy in system modeling”Operational Research Quarterly21247–265
41.
WilsonA G, 1976“Retailers' profits and consumers welfare in a spatial interaction shopping model” in London Papers in Regional Science 6: Theory and Practice in Regional Science Ed. MasserI (Pion, London) pp 42–59
