Planar Multi-Facility Location Problems with Polyhedral Gauges

Viac o knihe

Location science encompasses a diverse range of applications, including health care, security management, robotics, and telecommunications. It focuses on determining optimal sites for new facilities, such as hospitals, security cameras, or personnel like police officers. A common aspect of these problems is the need to serve existing demand points. This thesis addresses a general planar multi-facility location problem, emphasizing the median-objective, which seeks to minimize the sum of weighted distances between facilities and demand points. The analysis includes a bicriteria version of the objective, a restricted version requiring facilities to be outside predefined convex forbidden regions, and a constrained version where facilities must lie within specific convex sets. Key contributions include demonstrating that for a fixed number of facilities, the bicriteria problem has polynomially many extreme non-dominated points in the objective space, while the cardinality can be sub-exponential when the number increases. The restricted version is shown to be APX-hard, particularly with rectilinear distances and polyhedral forbidden regions, indicating it cannot be approximated in polynomial time unless P=NP. Additionally, a polynomial approximation algorithm is provided for certain instances, along with a finite dominating set for the constrained and restricted versions. Possible extensions to the center objective are also discuss