Locating a Minisum Annulus

Abstract

The problem is to find the best location of a minisum annulus with given width using the partial coverage distance model. The concept of partial coverage distance is that given demand points in the covering area are covered at no cost, while for uncovered demand points there will be additional costs proportional to their distances to the covering area. The objective of the problem is to locate the annulus such that the sum of distances from the uncovered demand points to the annulus (covering area) is minimized. The distance is measured by the Euclidean norm. We discuss the cases where the radius of the inner circle of the annulus is variable and given. For the variable radius, we prove that at least two demand points must be on the boundary of any optimal annulus. Based on that, an algorithm to solve the problem is introduced. In the case of given radius, we introduce the model and show its usefulness in locating undesirable facilities.

Le problème est de repérer le meilleur emplacement d’un espace annulaire avec des données de la largeur en utilisant le critère mini-somme et un modèle à distance avec couverture partielle. La notion de distance avec couverture partielle est que les points dans la zone de couverture sont servis sans pénalité, mais il y aura, pour la découverte des points, un surcoût proportionnel à leur distance de la zone de couverture. L’objectif du problème est de localiser l’espace annulaire tel que la somme des distances comprises entre les points non couverts par l’espace annulaire (superficie) réduit au minimum. La distance est mesurée par la norme euclidienne. Nous discutons les cas où le rayon du cercle intérieur de l’espace annulaire est variable et donné. Pour le rayon variable, nous avons prouvé qu’au moins deux points devaient être sur la limite d’un anneau optimale. Sur cette base, un algorithme pour résoudre le problème est introduit. Dans le cas d’un rayon donné, nous introduisons le modèle et nous prouvons son utilité en localisant des installations indésirables.