Premium
Optimal multifacility defensive location on planes with rectilinear distances
Author(s) -
Trietsch Dan
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230602
Subject(s) - euclidean geometry , euclidean distance , grid , facility location problem , service (business) , hexagonal crystal system , computer science , combinatorics , hexagonal tiling , mathematical optimization , mathematics , geometry , business , marketing , chemistry , crystallography
In this paper, we are concerned with the problem of optimally covering a large region with rectilinear distances by many service facilities. We assume that the number of customers is proportional to the area that they occupy and that each customer patronizes the nearest facility. Our objective is to locate the facilities in such a manner that the maximal area any future competitor facility can capture will be minimized. For Euclidean distances, it has been conjectured that the best arrangement is a triangular grid, yielding hexagonal service areas (honeycomb). In this paper, we show that an analogous arrangement is optimal for rectilinear distances. Furthermore, as in the Euclidean case, it minimizes both the average and the maximal distance for all customers to their nearest facilities. The service areas under the optimal solution are rectilinear circles—which are shaped as Euclidean squares tilted at 45° to the X ‐ and Y ‐axes. © 1993 by John Wiley & Sons, Inc.