Rapidly converging solution for p-centers in nonconvex regions

Authors: MONIKA MANGLA, DEEPAK GARG

Abstract: This paper aims to locate $p$ resources in a nonconvex demand plane having $n $demand points. The objective of the location problem is to find the location for these $p$ resources so that the distance from each of $n$ demand points to its nearest resource is minimized, thus simulating a $p$-center problem. We employ various geometrical structures for solving this location problem. The suggested approach is also capable of finding the optimal value of $p$ so that all demand points have at least one resource at a distance $\Delta $, where $\Delta $ is the maximum permissible distance for emergency services. Finally, an implementation of the proposed approach is presented and it is observed that the suggested approach rapidly converges towards the optimal location.

Keywords: Facility location, $p$-center, convex polygon, geodesic distance, nonconvex region, Delaunay triangulation

Full Text: PDF