On algebraic solution of the rawls location problem on the plane with rectilinear metric

Abstract

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 the cities with straight rectangular streets. In terms of idempotent algebra, the problem is reduced to minimizing a functional, given on the set of threedimensional 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 algebra. The solution obtained is then used to derive a complete solution to the Rawls location problem, which extends a known particular solution of the problem under consideration. Refs 16.

Keywords:

idempotent semifield, spectral radious of matrix, complete solution, rectilinear metric, the Rawls location problem