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.