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. In this thesis, we particularly employ structures in computational geometry for Facility Location Problem. We use the spatial properties of the demand plane and facilities to solve location problems. Main contributions of this thesis in the field of facility location literature are as follows:  We consider the p-center problem in a non-convex polygonal region and present an algorithm for locating 𝑝 facilities in the demand plane such that the objective function of pcenter is accomplished. We prove that the proposed algorithm rapidly converges to the optimal solution in comparison to the traditional approach.  We undertake an allocation problem for capacitated resources and present an algorithm that utilizes various geometric structures for the same. We also incorporate the usage of residue ratio of the resources in the proposed algorithm for allocation. Finally, we observe that the proposed algorithm optimizes the average distance(𝑓𝑎𝑣𝑔 ). This improvement in 𝑓􀯔􀯩􀯚 becomes apparent as the total residue ratio of all resources lowers.  Subsequently, we propose layout planning using well-known structures in computational geometry. For the layout planning, we consider layout planning on a departmental store and exhibition hall. The proposed approach is independent of the travel path undertaken by the customers. Using t-test, it has been validated that the proposed algorithm outperforms the traditional approach.  Considering the widespread requirement of parking management with limited parking, we also propose an approach for an automated parking management system. The suggested approach takes information from sensors and suggests parking to the requesting vehicle. Various performance metrics have been discussed to validate parking management. The suggested approach is validated to achieve better performance metrics.