Solution of minimax location problem in three-dimensional space with rectilinear metric
Abstract
A minimax single-facility location problem in three-dimensional space with rectilinear metric ($l_1$-metric) is examined, and a direct, explicit solution of the problem is obtained using methods of tropical (idempotent) mathematics. In this article the problem is represented in terms of tropical mathematics as a tropical optimization problem. Then a parameter is introduced to represent the minimum value of the objective function, and the problem is reduced to a parameterized system of inequalities. This system is solved for one variable, and the existence conditions of solution are used to obtain optimal values of the second parameter by using an auxiliary optimization problem. Then the auxiliary problem is solved in the same way and the value of the third variable is evaluated. The obtained general solution is transformed into a set of direct solutions written in a compact form for different cases of relationships between the initial parameters of the problem.
References
Sule D. R. Logistics of Facility Location and Allocation / New York: Marcel Dekker, 2001.
Farahani R. Z., Hekmatfar M. Facility Location / Contributions to Management Science. Heidelberg: Physica-Verlag, 2009.
Eiselt H. A., Marianov V. Foundations of Location Analysis / New York: Springer, 2011. Vol. 155 of International Series in Operations Research and Management Science.
Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance // Computational Management Science, 2017. Vol. 1, № 4. P. 493–518.
Francis R. L. A geometrical solution procedure for a rectilinear distance minimax location problem // AIIE Transactions, 1972. Vol. 4. № 4. P. 328–332.
Hansen P., Peeters D., Thisse J. F. Constrained location and the Weber-Rawls problem // North-Holland Mathematics Studies, 1981. Vol. 59. P. 147–166.
Zabudskii G. G. A minimax planar location problem with forbidden zones: its solution algorithm // Automation and Remote Control, 2004. Vol. 65. № 2. P. 241–247.
Nobakhtian S., Dehkordi A. R. A fast algorithm for the rectilinear distance location problem // Mathematical Methods of Operations Research, 2018. Vol. 87. № 1. P. 1–18.
Cuninghame-Green R. A. Minimax algebra / Berlin: Springer-Verlag, 1979.
Baccelli F., Cohen G., Olsder G. J., Quadrat J. P. Synchronization and Linearity. Wiley Series in Probability and Statistics / Chichester: Wiley, 1993.
Маслов В. П., Колокольцов В. Н. Идемпотентный анализ и его применение в оптимальном управлении / М.: Физматлит, 1994.
Cuninghame-Green R. A. Minimax algebra and applications // Advances in Imaging and Electron Physics, Vol. 90 / Ed. by P. W. Hawkes. San Diego: Academic Press, 1994. P. 1–121.
Golan J. S. Semirings and Affine Equations Over Them / New York: Springer, 2003. Vol. 556 of Mathematics and Its Applications.
Heidergott B, Olsder G. J., van der Woude J. Max Plus at Work / Princeton Series in Applied Mathematics. Princeton: Princeton Univ. Press, 2006.
McEneaney W. M. Max-Plus Methods for Nonlinear Control and Estimation / Systems and Control: Foundations and Applications. Boston: Birkhauser, 2006.
Itenberg I., Mikhalkin G., Shustin E. I. Tropical Algebraic Geometry / Basel: Birkhauser, 2007. Vol. 35 of Oberwolfach Seminars. doi: 10.1007/978-3-7643-8310-7.
Gondran M., Minoux M. Graphs, Dioids and Semirings / New York: Springer, 2008. Vol. 41 of Operations Research/ Computer Science Interfaces.
Кривулин Н. К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем / СПб.: Издательство Санкт-Петербургского государственного университета, 2009. 255 с.
Butkovic P. Max-linear Systems. Springer Monographs in Mathematics / London: Springer, 2010.
Кривулин Н. К., Агеев В. А., Гладких И. В. Применение методов тропической математики для оценки альтернатив на основе парных сравнений // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2017. № 1. С. 27–41.
Krivulin N. K. Tropical optimization problems in time-constrained project scheduling // Optimization, 2017. Vol. 66. № 2. P. 205–224.
Krivulin N. K. An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem // Vestnik St. Petersburg Univ. Math, 2011. Vol. 44. № 4. P. 272–281.
Krivulin N. K. A new algebraic solution to multidimensional minimax location problems with Chebyshev distance // WSEAS Transactions on Mathematics, 2012. Vol. 11. № 7. P. 605–614.
Krivulin N. K. Complete solution of a constrained tropical optimization problem with application to location analysis // Relational and Algebraic Methods in Computer Science / Cham: Springer, 2014. Vol. 8428 of Lecture Notes in Computer Science. P. 362–378.
Krivulin N. K., Plotnikov P. V. On an algebraic solution of the Rawls location problem in the plane with rectilinear metric // Vestnik St. Petersburg University: Mathematics, 2015. Vol. 48. № 2. P. 75—81.
Krivulin N.K., Plotnikov P.V. Using tropical optimization to solve minimax location problems with a rectilinear metric on the line // Vestnik St. Petersburg University: Mathematics, 2016. Vol. 49. № 4. P. 340–349.
Krivulin N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints // Optimization, 2015. Vol. 64. № 5. P. 1107–1129.
Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems // Linear Algebra and its Applications, 2015. Vol. 468. P. 211–232.
Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling // Computational Management Science, 2017. Vol. 14. № 1. P. 91–113.
This work is licensed under a Creative Commons Attribution 4.0 International License.
