ISBN 9783843939249

978-3-8439-3924-9, Reihe Mathematik

Andrea Maier
Planar Multi-Facility Location Problems with Polyhedral Gauges

187 Seiten, Dissertation Technische Universität Kaiserslautern (2018), Softcover, A5

Zusammenfassung / Abstract

Location science is a very active research area with a variety of different models and their applications among which are health care, security management, robotics, telecommunication, economics and many more. Facility location deals with finding a location for one or multiple new "facilities", where the term facilities is used as a placeholder and can mean hospitals, security cameras, robots or even humans like police officers or first-aiders. The main similarity between the different kind of problems is that there are often some demand points, also called existing facilities, that the new facilities have to serve. This thesis deals with a very general planar multi-facility location problem which can be used in many applications as a starting point for new solution methods. The objective considered is the median-objective, which aims to minimize the sum of weighted distances between the facilities and the demand points. This objective is examined under different circumstances: first, a bicriteria version of the objective is analyzed. Secondly, a restricted version is investigated in which the facilities have to be placed outside predefined convex forbidden regions. Last, a constrained location problem is considered in which the facilities have to lie within given convex sets. The main contributions of this thesis are as follows: it is shown that for any fixed number of new facilities the bicriteria problem has polynomial many extreme non-dominated points in the objective space. As soon as this number can get arbitrarily large, it is proved that the cardinality of the extreme non-dominated points can be sub-exponential in the size of the input. Regarding the restricted version of the problem with a single objective, it is shown that the problem is APX-hard even when considering the rectilinear distance with polyhedral forbidden regions. As a consequence the problem cannot be approximated in polynomial time within a given factor unless P=NP. In addition, an approximation algorithm is derived which becomes polynomial for special problem instances. Another contribution is a finite dominating set, that is a finite set containing at least one optimal solution, for a constrained and restricted version of the problem having a special structure. In the end, possible extensions to the center objective are discussed.