×

Heuristic algorithms for delivered price spatially competitive network facility location problems. (English) Zbl 0751.90045

Summary: We review previous formulations of models for locating a firm’s production facilities while simultaneously determining production levels at those facilities so as to maximize the firm’s profit. We enhance these formulations by adding explicit variables to represent the firm’s shipping activities and discuss the implications of this revised approach. In these formulations, existing firms, as well as new entrants, are assumed to act in accordance with an appropriate model of spatial equilibrium. The firm locating new production facilities is assumed to be a large manufacturer entering an industry composed of a large number of small firms. Our previously reported proof of existence of a solution to the combined location-equilibrium problem is briefly reviewed. A heuristic algorithm based on sensitivity analysis methods which presume the existence of a solution and which locally approximate price changes as linear functions of production perturbations resulting from newly established facilities is presented. We provide several numerical tests to illustrate the contrasting locational solutions which this paper’s revised delivered price formulation generates relative to those of previous formulations. An exact, although computationally burdensome, method is also presented and employed to check the reliability of the heuristic algorithm.

MSC:

90B80 Discrete location and assignment
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90B10 Deterministic network models in operations research

Software:

MINOS
Full Text: DOI

References:

[1] G.S. Chao and T.L. Friesz, Spatial price equilibrium sensitivity analysis, Transport. Res. 18B(1984)423–440. · doi:10.1016/0191-2615(85)90010-4
[2] S. Dafermos and A. Nagurney, Sensitivity analysis for the general spatial economic equilibrium problem, Oper. Res. 32(1984)1069–1086. · Zbl 0562.90009 · doi:10.1287/opre.32.5.1069
[3] S. Dafermos and A. Nagurney, Oligopolistic and competitive behavior of spatially separated markets, Regional Sci. Urban Econ. 17 (1987).
[4] D. Erlenkotter, Facility location with price-sensitive demands: Private, public and quasi-public, Manag. Sci. 24(1977)378–386. · Zbl 0383.90082 · doi:10.1287/mnsc.24.4.378
[5] T.L. Friesz, P.T. Harker and R.L. Tobin, Alternative algorithms for the general network spatial price equilibrium problem, J. Regional Sci. 24(1984)475–507. · doi:10.1111/j.1467-9787.1984.tb01043.x
[6] T.L. Friesz, T.C. Miller and R.L. Tobin, Algorithms for spatially competitive network facility location, Environ. Planning B15(1988)191–203. · doi:10.1068/b150191
[7] T.L. Friesz, R.L. Tobin, H.-J. Cho and N.J. Mehta, Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints, Math. Progr. (1990), to appear. · Zbl 0723.90070
[8] T.L. Friesz, R.L. Tobin and T.C. Miller, Existence theory for spatially competitive network facility location models, Ann. Oper. Res. 18(1988)267–276. · Zbl 0707.90065 · doi:10.1007/BF02097808
[9] T.L. Friesz, R.L. Tobin, T.E. Smith and P.T. Harker, A nonlinear complementarity formulation and solution procedure for the general derived demand network equilibrium problem, J. Regional Sci. 23(1983)337–359. · doi:10.1111/j.1467-9787.1983.tb00994.x
[10] P. Hanjoul and J.-F. Thisse, The location of a firm on a network. in:Applied Decision Analysis and Economic Behaviour, ed. A.J. Hughes Hallett (Martinus Nijhoff, New York, 1984).
[11] P. Hansen and J.-F. Thisse, Multiplant location for profit maximization, Environ. Planning A9(1977)63–73. · doi:10.1068/a090063
[12] P.T. Harker, A variational inequality approach for the determination of oligopolistic market equilibrium, Math. Progr. 30(1984)105–111. · Zbl 0559.90015 · doi:10.1007/BF02591802
[13] P.T. Harker (ed.),Spatial Price Equilibrium: Advances in Theory, Computation and Application (Springer, New York, 1984).
[14] P.T. Harker, Alternative models of spatial competition, Oper. Res. 34(1986)410–425. · Zbl 0602.90018 · doi:10.1287/opre.34.3.410
[15] P.T. Harker,Predicting Intercity Freight Flows (V.N.V. Science Press, Urecht, The Netherlands, 1987).
[16] D. Kinderlehrer and G. Stampacchia,An Introduction to Variational Inequalities and the Applications (Academic Press, 1980). · Zbl 0457.35001
[17] T.C. Miller, Competitive facility location modelling: Heuristic algorithms based on sensitivity analysis, Dissertation, University of Pennsylvania (1987), unpublished.
[18] B. Murtagh and M. Saunders, MINOS 5.0 User’s Guide, Systems Optimization Laboratory, Stanford University (1983).
[19] A. Nagurney, Computational comparisons of spatial price equilibrium methods, J. Regional Sci. 27(1987)55–76. · doi:10.1111/j.1467-9787.1987.tb01144.x
[20] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, 1970). · Zbl 0241.65046
[21] J. Pang and D. Chan, Iterative methods for variational and complementarity problems, Math. Progr. 24(1982)284–313. · Zbl 0499.90074 · doi:10.1007/BF01585112
[22] P.A. Sanuelson, Spatial price equilibrium and linear programming, Amer. Econ. Rev. 42(1952)283–303.
[23] H.D. Sherali, A.L. Soyster and F.H. Murphy, Stackelberg-Nash-Cournot equilibria: Characterizations and computations, Oper. Res. 31(1983)253–276. · Zbl 0506.90011 · doi:10.1287/opre.31.2.253
[24] T. Takayama and G.C. Judge,Spatial and Temporal Price and Allocation Models (North-Holland, New York, 1971).
[25] R.L. Tobin, Sensitivity analysis for variational inequalities. J. Optim. Theory Appl. 48(1986)191–204. · Zbl 0557.49004
[26] R.L. Tobin and T.L. Friesz, Spatial competition facility location models: Definition, formulation and solution approach, Ann. Oper. Res. 6(1986)49–74. · doi:10.1007/BF02023794
[27] R.L. Tobin, Sensitivity analysis for general spatial price equilibria. J. Regional Sci. 27(1987)77–102. · doi:10.1111/j.1467-9787.1987.tb01145.x
[28] J.L. Wagner and L.M. Falkson, The optimal nodal location of public facilities with price-sensitive demand. Geograph. Anal. 7(1975)69–83. · doi:10.1111/j.1538-4632.1975.tb01024.x
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.