Solving a two-facility location problem in a space with Chebyshev metric
DOI:
https://doi.org/10.21638/spbu01.2022.405Abstract
A minimax two-facility location problem in multidimensional space with Chebyshev metric is examined subject to box constraints on the feasible location area. In the problem, there are two groups of points with known coordinates, and one needs to find coordinates for optimal location of two new points under the given constraints. The location of the new points is considered optimal if it minimizes the maximum of the following values: the distance between the first new point and the farthest point in the first group, the distance between the second new point and the farthest point in the second group, and the distance between the first and second new points. The location problem is formulated as a multidimensional optimization problem in terms of tropical mathematics that studies the theory and applications of algebraic systems with idempotent operations. A direct analytical solution to the problem is derived based on the use of methods and results of tropical optimization. A result is obtained which describes the set of optimal location of the new points in a parametric form ready for formal analysis of solutions and straightforward calculation.Keywords:
tropical optimization, idempotent semifield, minimax optimization problem, two-facility location problem
Downloads
Download data is not yet available.
References
Литература
1. Eiselt H.A., Marianov V. Pioneering developments in location analysis. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 3-22. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-1
2. Moradi E., Bidkhori M. Single facility location problem. In: Facility Location. Contributions to Management Science, 3-22. Heidelberg, Physica-Verlag (2009). https://doi.org/10.1007/978-3-7908- 2151-2-3
3. Drezner Z. Continuous center problems. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 63-78. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-4
4. Kolokoltsov V.N., Maslov V.P. Idempotent Analysis and Its Applications. In Ser.: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
5. Golan J.S. Semirings and Affine Equations Over Them. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
6. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. In Ser.: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
7. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In Ser.: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
8. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. In: Relational and Algebraic Methods in Computer Science. Lecture Notes in Computer Science, vol. 8428, 362-378. Cham, Springer (2014). https://doi.org/10.1007/978-3-319-06251-8-22
9. Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance. Comput. Manag. Sci. 14 (4), 493-518 (2017). https://doi.org/10.1007/s10287-017-0289-2
10. Krivulin N. Algebraic solution of minimax single-facility constrained location problems with Chebyshev and rectilinear distances. J. Log. Algebr. Methods Program. 115, 100578 (2020). https://doi.org/10.1016/j.jlamp.2020.100578
11. Krivulin N. Algebraic solutions of tropical optimization problems. Lobachevskii J. Math. 36 (4), 363-374 (2015). https://doi.org/10.1134/S199508021504006X
12. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
13. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211-232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
References
1. Eiselt H.A., Marianov V. Pioneering developments in location analysis. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 3-22. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-1
2. Moradi E., Bidkhori M. Single facility location problem. In: Facility Location. Contributions to Management Science, 3-22. Heidelberg, Physica-Verlag (2009). https://doi.org/10.1007/978-3-7908- 2151-2-3
3. Drezner Z. Continuous center problems. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 63-78. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-4
4. Kolokoltsov V.N., Maslov V.P. Idempotent Analysis and Its Applications. In Ser.: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
5. Golan J.S. Semirings and Affine Equations Over Them. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
6. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. In Ser.: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
7. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In Ser.: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
8. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. In: Relational and Algebraic Methods in Computer Science. Lecture Notes in Computer Science, vol. 8428, 362-378. Cham, Springer (2014). https://doi.org/10.1007/978-3-319-06251-8-22
9. Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance. Comput. Manag. Sci. 14 (4), 493-518 (2017). https://doi.org/10.1007/s10287-017-0289-2
10. Krivulin N. Algebraic solution of minimax single-facility constrained location problems with Chebyshev and rectilinear distances. J. Log. Algebr. Methods Program. 115, 100578 (2020). https://doi.org/10.1016/j.jlamp.2020.100578
11. Krivulin N. Algebraic solutions of tropical optimization problems. Lobachevskii J. Math. 36 (4), 363-374 (2015). https://doi.org/10.1134/S199508021504006X
12. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
13. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211-232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
Downloads
Published
2022-12-26
How to Cite
Krivulin, N. K., & Briushinin, M. A. (2022). Solving a two-facility location problem in a space with Chebyshev metric. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 9(4), 625–635. https://doi.org/10.21638/spbu01.2022.405
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
