Direct solution of a minimax location problem on the plane

P. V. Plotnikov ; N. K. Krivulin

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 14 (2018) no. 2, pp. 116-130

Résumé

A minimax single-facility location problem with rectilinear (Manhattan) metric is examined under constraints on the feasible location region, and a direct, explicit solution of the problem is suggested using methods of tropical (idempotent) mathematics. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. In the present article, a solution to the problem is investigated subject to constraints on the feasible region, which is given by a rectangular area. At first, the problem is represented in terms of tropical mathematics as a tropical optimization problem, a parameter is introduced to represent the minimum value of the objective function, and the problem is reduced to a parametrized 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 obtained general solution is transformed into a set of direct solutions, written in a compact closed form for different cases of relations between the initial parameters of the problem. Graphical illustrations of the solution are given for several positions of the feasible location region on the plane.

Détail

Keywords: Rawls location problem, constrained location, rectilinear metric, idempotent semifield, tropical optimization, complete solution.

Bibliographie

[1] Baccelli F., Cohen G., Olsder G. J., Quadrat J.-P., Synchronization and linearity, Wiley Series in Probability and Statistics, Wiley, Chichester, 1993, 514 pp. | MR

[2] Maslov V. P., Kolokol'tsov V. N., Idempotent analysis and its applications in optimal control, Fizmatlit Publ., M., 1994, 144 pp. (In Russian)

[3] Cuninghame-Green R. A., Minimax algebra and applications, Advances in Imaging and Electron Physics, 90, ed. P. W. Hawkes, Academic Press, San Diego, 1994, 121 pp. | DOI

[4] Golan J. S., Semirings and affine equations over them, Mathematics and its Applications, 556, Springer, New York, 2003, 256 pp. | DOI | MR

[5] Heidergott B., Olsder G. J., van der Woude J., Max plus at work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 2006, 226 pp. | MR | Zbl

[6] McEneaney W. M., Max-plus methods for nonlinear control and estimation, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 2006, 241 pp. | DOI | MR | Zbl

[7] Itenberg I., Mikhalkin G., Shustin E. I., Tropical algebraic geometry, Oberwolfach Seminars, 35, Birkhäuser, Basel, 2007, 104 pp. | DOI | MR | Zbl

[8] Gondran M., Minoux M., Graphs, dioids and semirings, Operations Research/Computer Science Interfaces, 41, Springer, New York, 2008, 383 pp. | DOI | MR | Zbl

[9] Butkovič P., Max-linear systems, Springer Monographs in Mathematics, Springer, London, 2010, 272 pp. | DOI | MR | Zbl

[10] Krivulin N. K., “A multidimensional tropical optimization problem with nonlinear objective function and linear constraints”, Optimization, 64:5 (2015), 1107–1129 | DOI | MR | Zbl

[11] Krivulin N. K., “Algebraic solutions to multidimensional minimax location problems with Chebyshev distance”, Recent Researches in Applied and Computational Mathematics, Intern. conference on Applied and Computational Mathematics (ICACM'11), WSEAS, 2011, 157–162

[12] Krivulin N. K., “Algebraic solution to a constrained rectilinear minimax location problem on the plane”, 2011 Intern. conference on Multimedia Technology (ICMT), IEEE, 2011, 6216–6220 | DOI

[13] Krivulin N. K., “A new algebraic solution to multidimensional minimax location problems with Chebyshev distance”, WSEAS Transactions on Mathematics, 11:7 (2012), 605–614

[14] Krivulin N. K., “An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem”, Vestnik of Saint Petersburg University. Mathematics, 44:4 (2011), 272–281 | DOI | MR | Zbl

[15] Krivulin N. K., Plotnikov P. V., “On an algebraic solution of the Rawls location problem in the plane with rectilinear metric”, Vestnik of Saint Petersburg University. Mathematics, 48:2 (2015), 75–81 | DOI | MR | Zbl

[16] Elzinga J., Hearn D. W., “Geometrical solutions for some minimax location problems”, Transport. Sci., 6:4 (1972), 379–394 | DOI | MR

[17] Francis R. L., “A geometrical solution procedure for a rectilinear distance minimax location problem”, AIIE Trans., 4:4 (1972), 328–332 | DOI | MR

[18] Krivulin N. K., Plotnikov P. V., “Using tropical optimization to solve minimax location problems with rectilinear metric on the line”, Vestnik of Saint Petersburg University. Mathematics, 3(61):4 (2016), 602–614 | DOI | MR