A heuristic algorithm for constrained multi-source location problem with closest distance under gauge: the variational inequality approach. (English) Zbl 1470.90041

Jiang, Jian-Lin; Assani, Saeed; Cheng, Kun; Zhu, Xiao-Xing

Abstr. Appl. Anal. 2013, Article ID 624398, 15 p. (2013).

Summary: This paper considers the locations of multiple facilities in the space \(R^p\), with the aim of minimizing the sum of weighted distances between facilities and regional customers, where the proximity between a facility and a regional customer is evaluated by the closest distance. Due to the fact that facilities are usually allowed to be sited in certain restricted areas, some locational constraints are imposed to the facilities of our problem. In addition, since the symmetry of distances is sometimes violated in practical situations, the gauge is employed in this paper instead of the frequently used norms for measuring both the symmetric and asymmetric distances. In the spirit of the Cooper algorithm [L. Cooper, SIAM Rev. 6, 37–53 (1964; Zbl 0956.90014)], a new location-allocation heuristic algorithm is proposed to solve this problem. In the location phase, the single-source subproblem with regional demands is reformulated into an equivalent linear variational inequality (LVI), and then, a projection-contraction (PC) method is adopted to find the optimal locations of facilities, whereas in the allocation phase, the regional customers are allocated to facilities according to the nearest center reclassification (NCR). The convergence of the proposed algorithm is proved under mild assumptions. Some preliminary numerical results are reported to show the effectiveness of the new algorithm.

MSC:

90B80	Discrete location and assignment
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Citations:

Zbl 0956.90014

References:

[1]	Weber, A., UBer Den Standort Der Industrien, 1. Teil: Reine Theorie Des Standortes (1909), Tübingen, Germany: Mohr Siebeck, Tübingen, Germany
[2]	Weiszfeld, E., Sur le point pour lequel la somme des distances de n points donnes est minimum, Tohoku Mathematical Journal, 43, 355-386 (1937) · JFM 63.0583.01
[3]	Love, R. F.; Morris, J. G.; Wesolowsky, G. O., Facilities Location: Models and Methods,, 7 (1988), Amsterdam, Netherlands: North-Holland Publishing, Amsterdam, Netherlands · Zbl 0685.90036
[4]	Plastria, F.; Drezner, Z., Continuous location problems: research, results and questions, Facility Location: A Survey of Applications and Methods, 225-260 (1995), New York, NY, USA: Springer, New York, NY, USA
[5]	Bennett, C. D.; Mirakhor, A., Optimal facility location with respect to several regions, Journal of Regional Science, 14, 1, 131-136 (1974)
[6]	Brimberg, J.; Wesolowsky, G. O., Minisum location with closest Euclidean distances, Annals of Operations Research, 111, 151-165 (2002) · Zbl 1040.90020
[7]	Drezner, Z.; Weslowsky, G. O., Optimal location of a facility relative to area demands, Naval Research Logistics Quarterly, 27, 2, 199-206 (1980) · Zbl 0443.90028
[8]	Jiang, J.; Yuan, X., A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand, Computational Optimization and Applications, 51, 3, 1275-1295 (2012) · Zbl 1243.90097
[9]	Suzuki, A.; Drezner, Z., The \(p\)-center location problem in an area, Location Science, 4, 1-2, 69-82 (1996) · Zbl 0917.90233
[10]	Wesolowsky, G. O.; Love, R. F., Location of facilities with rectangular distances among point and area destinations, Naval Research Logistics Quarterly, 18, 83-90 (1971) · Zbl 0216.54202
[11]	Carrizosa, E.; Muñoz-Márquez, M.; Puerto, J., The weber problem with regional demand, European Journal of Operational Research, 104, 2, 358-365 (1998) · Zbl 0955.90063
[12]	Stone, R. E., Some average distance results, Transportation Science, 25, 1, 83-91 (1991)
[13]	Puerto, J.; Rodríguez-Chía, A. M., On the structure of the solution set for the single facility location problem with average distances, Mathematical Programming, 128, 1-2, 373-401 (2011) · Zbl 1279.90106
[14]	Drezner, Z.; Wesolowsky, G. O., Location models with groups of demand points, INFOR Journal, 38, 4, 359-372 (2000) · Zbl 07677627
[15]	Berman, O.; Drezner, Z.; Wesolowsky, G. O., Location of facilities on a network with groups of demand points, IIE Transactions, 33, 8, 637-648 (2001)
[16]	Brimberg, J.; Wesolowsky, G. O., Note: facility location with closest rectangular distances, Naval Research Logistics, 47, 1, 77-84 (2000) · Zbl 0953.90033
[17]	Nickel, S.; Puerto, J.; Rodriguez-Chia, A. M., An approach to location models involving sets as existing facilities, Mathematics of Operations Research, 28, 4, 693-715 (2003) · Zbl 1082.90059
[18]	Love, R. F.; Morris, J. G., Mathematical models of road travel distances, Management Science, 25, 2, 130-139 (1979) · Zbl 0419.90053
[19]	Ward, J. E.; Wendell, R. E., A new norm for measuring distance which yields linear location problems, Operations Research, 28, 836-844 (1980) · Zbl 0443.90029
[20]	Ward, J. E.; Wendell, R. E., Using block norms for location modeling, Operations Research, 33, 5, 1074-1090 (1985) · Zbl 0582.90026
[21]	Witzgall, C., Optimal location of a central facility, mathematical models and concepts, Report, 8388 (1964), Washington, DC, USA: National Bureau of Standards, Washington, DC, USA
[22]	Michelot, C.; Lefebvre, O., A primal-dual algorithm for the Fermat-Weber problem involving mixed gauges, Mathematical Programming, 39, 3, 319-335 (1987) · Zbl 0641.90034
[23]	Durier, R., On Pareto optima, the Fermat-Weber problem, and polyhedral gauges, Mathematical Programming, 47, 1, 65-79 (1990) · Zbl 0706.90066
[24]	Carrizosa, E.; Conde, E.; Munoz-Márquez, M.; Puerto, J., Simpson points in planar problems with locational constraints. The polyhedral-gauge case, Mathematics of Operations Research, 22, 2, 291-300 (1997) · Zbl 0883.90076
[25]	Nickel, S., Restricted center problems under polyhedral gauges, European Journal of Operational Research, 104, 2, 343-357 (1998) · Zbl 0955.90071
[26]	Cera, M.; Mesa, J. A.; Ortega, F. A.; Plastria, F., Locating a central hunter on the plane, Journal of Optimization Theory and Applications, 136, 2, 155-166 (2008) · Zbl 1146.90462
[27]	Plastria, F., Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Annals of Operations Research, 167, 121-155 (2009) · Zbl 1163.90038
[28]	Norman Katz, I.; Vogl, S. R., A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Computers & Mathematics with Applications, 59, 1, 399-410 (2010) · Zbl 1189.90086
[29]	Minkowski, H., Theorie der Konvexen Körper (1911), Teubner, Berlin: Gesammelte Abhandlungen, Teubner, Berlin
[30]	Drezner, Z., Facility Location: A Survey of Applications and Methods (1995), New York, NY, USA: Springer, New York, NY, USA
[31]	Ghosh, A.; Rushton, G., Spatial Analysis and Location-Allocation Models (1987), New York, NY, USA: Van Nostrand Reinhold, New York, NY, USA
[32]	Cooper, L., Solutions of generalized location equilibrium models, Journal of Regional Science, 7, 1-18 (1967)
[33]	Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM Journal on Computing, 13, 1, 182-196 (1984) · Zbl 0534.68032
[34]	Cooper, L., Heuristic methods for location-allocation problems, SIAM Review, 6, 37-53 (1964) · Zbl 0956.90014
[35]	Jiang, J.-L.; Yuan, X.-M., A heuristic algorithm for constrained multi-source Weber problem: the variational inequality approach, European Journal of Operational Research, 187, 2, 357-370 (2008) · Zbl 1149.90091
[36]	Jiang, J.-l.; Cheng, K.; Wang, C.-C.; Wang, L.-p., Accelerating the convergence in the single-source and multi-source Weber problems, Applied Mathematics and Computation, 218, 12, 6814-6824 (2012) · Zbl 1241.90076
[37]	Levin, Y.; Ben-Israel, A., A heuristic method for large-scale multi-facility location problems, Computers & Operations Research, 31, 2, 257-272 (2004) · Zbl 1088.90036
[38]	Fukunaga, K., Introduction to Statistical Pattern Recognition (1990), Boston, Mass, USA: Academic Press, Boston, Mass, USA · Zbl 0711.62052
[39]	Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems (2004), New York, NY, USA: Springer, New York, NY, USA
[40]	Ferris, M. C.; Kanzow, C., Engineering and economic applications of complementarity problems, SIAM Review, 39, 4, 669-713 (1997) · Zbl 0891.90158
[41]	Addi, K.; Brogliato, B.; Goeleven, D., A qualitative mathematical analysis of a class of linear variational inequalities via semi-complementarity problems: applications in electronics, Mathematical Programming, 126, 1, 31-67 (2011) · Zbl 1229.90224
[42]	Bnouhachem, A.; Benazza, H.; Khalfaoui, M., An inexact alternating direction method for solving a class of structured variational inequalities, Applied Mathematics and Computation, 219, 14, 7837-7846 (2013) · Zbl 1293.49071
[43]	Barbagallo, A.; Mauro, P., Time-dependent variational inequality for an oligopolistic market equilibrium problem with production and demand excesses, Abstract and Applied Analysis, 2012 (2012) · Zbl 1246.91073
[44]	Gwinner, J., Three-field modelling of nonlinear nonsmooth boundary value problems and stability of differential mixed variational inequalities, Abstract and Applied Analysis, 2013 (2013) · Zbl 1277.35183
[45]	Zhao, Y.-B.; Yuan, J.-Y., An alternative theorem for generalized variational inequalities and solvability of nonlinear quasi-\(P_x^M 2 a;\)-complementarity problems, Applied Mathematics and Computation, 109, 2-3, 167-182 (2000) · Zbl 1021.49009
[46]	Uzawa, H.; Arrow, K. J.; Hurwicz, L.; Uzawa, H., Iterative methods for concave programming, Studies in Linear and Nonlinear Programming, 154-165 (1958), Stanford, Calif, USA: Stanford University Press, Stanford, Calif, USA
[47]	He, B. S., A new method for a class of linear variational inequalities, Mathematical Programming, 66, 2, 137-144 (1994) · Zbl 0813.49009
[48]	He, B. S., A modified projection and contraction method for a class of linear complementarity problems, Journal of Computational Mathematics, 14, 1, 54-63 (1996) · Zbl 0854.65047
[49]	Xiu, N.; Wang, C.; Zhang, J., Convergence properties of projection and contraction methods for variational inequality problems, Applied Mathematics and Optimization, 43, 2, 147-168 (2001) · Zbl 0980.90093
[50]	Eaves, B. C., On the basic theorem of complementarity, Mathematical Programming, 1, 1, 68-75 (1971) · Zbl 0227.90044