Approximation Clustering Algorithms for Facility Location Problems

Abstract

In data mining applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. The mathematical models are used to develop to ensure the robustness. In this thesis three new important parameters of FLP has investigated and implemented using a hybrid solution of clustering techniques and MILP. The conventional facility location models consider radius as a service area of the facility. Therefore, the conventional approach is appropriate for such facilities which fulfill their service in a radius. However, there are a number of applications which are failing to fulfill this condition and are facing topographical and road network barriers. As the problem is NP- hard, continuous efforts have been made to find more efficient techniques. The nature of the facility adds to its variety. A popular approach has been based on geometric solutions. Other methods have also been tried; one of them is based on density applied for large databases as in Spatial Data Mining and Geographic Information Systems. A novel approach is evolved using density in the work presented in this thesis wherein two stage solutions are proposed for Uncapacitated Facility Location Problem. In the same manner, apart from density, the profit is also the main area of concern, to earn the maximum profit facilities are allocated in such a manner to be more utilized and to earn more profit. In this real life aspect, a model for distance based facility location problem (FLP) is developed. In which the distance between customer and facility is incorporated in the form of constraints. It also provides the option of simultaneous opening of two locations. As this new constraint is effective, the solution for instant and quick services is also expected. Consider a scenario, where we have a limited service area, and also want to earn more profit. Here, the model for FLP is designed using a hybrid approach where one can find out the right location through pioneer clustering algorithm K-means and profit through MILP. W