TY - JOUR

T1 - On an algebraic solution of the Rawls location problem in the plane with rectilinear metric

AU - Krivulin, N.K.

AU - Plotnikov, P.V.

PY - 2015

Y1 - 2015

N2 - A minimax single-facility location problem with rectilinear metric is examined by using methods of tropical (idempotent) mathematics. This problem, known as the Rawls problem or the messenger problem, appears in the location of emergency services (hospitals, fire stations) in cities with straight rectangular streets. In terms of idempotent algebra, the problem is reduced to minimizing a functional given on the set of three-dimensional vectors by an appropriately constructed matrix and calculated by using the multiplicative conjugate transposition. The minimum of the objective function is found subject to constraints in the form of a relation that holds between components of the vectors. A new result of the spectral theory of matrices in idempotent algebra is applied, which offers a general solution to the problem of minimizing such functionals without additional constraints. Based on the result, a general solution to the problem with constraints on the feasible solution is given in terms of the tropical algeb

AB - A minimax single-facility location problem with rectilinear metric is examined by using methods of tropical (idempotent) mathematics. This problem, known as the Rawls problem or the messenger problem, appears in the location of emergency services (hospitals, fire stations) in cities with straight rectangular streets. In terms of idempotent algebra, the problem is reduced to minimizing a functional given on the set of three-dimensional vectors by an appropriately constructed matrix and calculated by using the multiplicative conjugate transposition. The minimum of the objective function is found subject to constraints in the form of a relation that holds between components of the vectors. A new result of the spectral theory of matrices in idempotent algebra is applied, which offers a general solution to the problem of minimizing such functionals without additional constraints. Based on the result, a general solution to the problem with constraints on the feasible solution is given in terms of the tropical algeb

KW - idempotent semifield

KW - spectral radius of a matrix

KW - complete solution

KW - rectilinear metric

KW - Rawls location problem

U2 - 10.3103/S1063454115020065

DO - 10.3103/S1063454115020065

M3 - Article

VL - 48

SP - 75

EP - 81

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -