A location–allocation problem with concentric circles

Abstract

We consider a continuous location problem for p concentric circles serving a given set of demand points. Each demand point is serviced by the closest circle. The objective is to minimize the sum of weighted distances between demand points and their closest circle. We analyze and solve the problem when demand is uniformly and continuously distributed in a disk and when a finite number of demand points are located in the plane. Heuristic and exact algorithms are proposed for the solution of the discrete demand problem. A much faster heuristic version of the exact algorithm is also proposed and tested. The exact algorithm solves the largest tested problem with 1000 demand points in about 3.5 hours. The faster heuristic version solves it in about 2 minutes.

Keywords:

• Facility location
• concentric circles
• location-allocation

Additional information

Notes on contributors

Jack Brimberg

Jack Brimberg is a Professor of Operations Research in the Department of Mathematics and Computer Science of the Royal Military College of Canada. His research interests are in facilities location theory, mathematical programming, and applied operations research. He is also a member of the Groupe d’Études et de Recherche en Analyse des Décisions (GERAD), an adjunct professor at the École des Hautes Études Commerciales of the University of Montreal, and a registered professional engineer in the Province of Ontario.

Zvi Drezner

Zvi Drezner received his B.Sc. in Mathematics and Ph.D. in Computer Science from the Technion, Israel Institute of Technology. His research interests are in location theory, metaheuristics, computer networks, and computational statistics. He has edited two books and published over 280 articles in refereed journals such as Operations Research, Management Science, IIE Transactions, Naval Research Logistics, and others.