×

Solving a maximin location problem on the plane with given accuracy. (English. Russian original) Zbl 1325.49049

Autom. Remote Control 75, No. 7, 1221-1230 (2014); translation from Avtom. Telemekh. 2014, No. 7, 75-86 (2014).
Summary: We consider the optimal placement problem in a bounded region on a plane with fixed objects. We specify minimal admissible distances between placed and fixed objects. The optimization criterion is to maximize the minimal weighted distances from placed objects to fixed ones. We propose a quasipolynomial combinatorial algorithm to solve this problem with a given accuracy. We show the results of a computational experiment with the integer programming model and the IBM ILOG CPLEX suite.

MSC:

49N90 Applications of optimal control and differential games
93A30 Mathematical modelling of systems (MSC2010)
90C10 Integer programming
90C27 Combinatorial optimization

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beresnev, V.L., Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh (Discrete Location Problems and Polynomials of Boolean Variables), Novosibirsk: Inst. Mat. Sib. Otd. Ross. Akad. Nauk, 2005.
[2] Panyukov, A.V. and Pelzwerger, B.V., Optimal Location of a Tree in a Finite Set, Zh. Vychisl. Mat. Mat. Fiz., 1988, vol. 28, pp. 618-620. · Zbl 0662.90082
[3] Panyukov, A.V. and Pelzwerger, B.V., Polynomial Algorithms to Finite Veber Problem for a Tree Network, J. Comput. Appl. Math., 1991, vol. 35, pp. 291-296. · Zbl 0746.05034
[4] Ageev, A.A., Gimadi, E.Kh., and Kurochkin, A.A., A Polynomial Algorithm for the Location Problem on a Chain with Identical Industrial Capacities of Plants, Diskret. Anal. Issled. Oper., 2009, vol. 16, no. 5, pp. 3-18. · Zbl 1249.90295
[5] Zabudskii, G.G., Model Building and Location Problem Solving in a Plane with Forbidden Gaps, Autom. Remote Control, 2006, vol. 67, no. 12, pp. 1986-1990. · Zbl 1194.90056
[6] Zabudskii, G.G. and Amzin, I.V., Search Region Contraction of the Weber Problem Solution on the Plane with Rectangular Forbidden Zones, Autom. Remote Control, 2012, vol. 73, no. 5, pp. 821-830. · Zbl 1255.49068
[7] Kochetov, Yu.A., Pashchenko, M.G., and Plyasunov, A.V., On the Complexity of Local Search for the p-Median Problem, Diskret. Anal. Issled. Oper., Ser. 2, 2005, vol. 12, no. 2, pp. 44-71. · Zbl 1249.90344
[8] Farahani, R.Z. and Hekmatfar, M., Facility Location: Concepts, Models, Algorithms and Case Studies, Heidelberg: Physica-Verlag Heidelberg, 2009.
[9] Nickel, S. and Puerto, J., Location Theory, Heidelberg: Springer-Verlag, 2005. · Zbl 1229.90001
[10] Zabudskii, GG; Koval’, AA, Object Location on a Plane with Maximin Criterion and Minimal Admissible Distances, 88 (2011), Yekaterinburg
[11] Zabudskii, G.G. and Markhotskaya, N.V., Solving the Maximin Location Problem on a Plane with Minimal Admissible Distances, Proc. XIV Baikal Int. School-Seminar “Optimization Methods and Their Applications,” Irkutsk: Inst. Sist. Energ. Sib. Otd. Ross. Akad. Nauk, 2008, vol. 1, pp. 380-387.
[12] Brimberg, J. and Mehrez, A., Multi-Facility Location Using a Maximin Criterion and Rectangular Distances, Location Sci., 1994, vol. 2, no. 1, pp. 11-19. · Zbl 0929.90045
[13] Katz, MJ; Kedem, K.; Segal, M., Improved Algorithms for Placing Undesirable Facilities, 1859-1872 (2002) · Zbl 1259.90060
[14] Tamir, A., Locating Two Obnoxious Facilities Using the Weighted Maximin Criterion, 97-105 (2006) · Zbl 1080.90053
[15] Levin, G.M. and Tanaev, V.S., Dekompozitsionnye metody optimizatsii proektnykh reshenii (Decomposition Optimization Methods for Design Solutions), Minsk: Nauka i Tekhnika, 1978.
[16] Tanaev, V.S., Dekompozitsiya i agregirovanie v zadachakh matematicheskogo programmirovaniya (Decomposition and Aggregation in Mathematical Programming Problems), Minsk: Nauka i Tekhnika, 1987. · Zbl 0618.90053
[17] Preparata, F.P. and Shamos, M.G., Computational Geometry. An Introduction, New York: Springer, 1985. Translated under the title Vychislitel’naya geometriya. Vvedenie, Moscow: Mir, 1988. · Zbl 0744.68131
[18] Dearing, P.M. and Francis, R.L., A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances, Transportat. Sci., 1974, vol. 8, pp. 126-141.
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.