Efficient Geometric Algorithms for Resource Location Models

Abstract

Facility Location has been the most studied problem in the field of operation research and optimization during the past few decades. Given a set of candidate locations, the facility location problem focuses on finding an optimal set of locations to open facilities. The location of facilities is selected with an intention to minimize the total cost. This cost includes the facility opening cost of facilities along with connection cost (assignment cost) of clients (demand nodes) to facilities. This connection cost is often modeled as the weighted sum of metric distances among clients and allocated facilities. Thus Facility Location Problem aims to optimize the distance in order to minimize the assignment cost. This basic Facility Location Problem has evolved in order to address realistic issues over time. This evolution helps in implementation of FLP to real-life applications. For instance, facilities may have some limited capacity in real life, thus limiting the number of demand nodes it can serve to. Few other examples of evolved FLP model are constrained FLP, Multifacility Location problem etc. FLP can be classified based on the objective functions mainly into median problems and center problem. k-median problem, the most researched variant of FLP minimizes the assignment cost allowing at most k facilities. k-median problem is generally used for transport applications and thus has widespread application ranging from network design to data warehousing etc. kcenter problem is mainly used for location of emergency services like ambulance station, fire brigade service etc. In k-center model, the aim is to minimize the distance of each facility to its farthest demand node. This aim ensures that even the farthest demand site will receive service within some stipulated time. These location problems are NP-hard and thus have been widely studied by various researchers. Various popular approaches for FLP include metaheuristics, approximation algorithms, and Computational geometry etc.