Design and Simulation of Algorithm for the K-Centre Problem

Abstract

Facility location problem addresses the appropriate allocation of facilities in a given region. Facility location problem has become a challenge for public and private sectors. Since, both public and private agencies are committed to provide specified services to their respective customers/clients; within particular range of distance and time. Therefore an appropriate location of facility is matter of priority for all service providers indeed. Facilities may be of various kinds such as Static Facilities (e.g. Schools, Hospitals, Automobile workstations, College, & Fire Stations etc) and Mobile Facilities (e.g. PCR vans, & Ambulance etc). There are so many important parameters (such as distance, cost, time and demand); which are essential to consider during the allocation of a facility. In this thesis, we present an approach that is known as Anticipatory Bound Selection Procedure (ABSP). ABSP is utilized in collaboration of Jump Based Scheme (JBS) to provide an efficient way to solve the vertex k-center problem. This collaboration of these two methods has proven its significance by providing exciting results over the performance of other existing algorithms. It has reduced the number of iterations (which are required to allocate k-facilities) drastically. Consequently the time required to determine the appropriate locations for allocating facilities has reduced considerably. Moreover the presented framework provides an algorithm for obnoxious facility location problem (OFLP). The obnoxious material management is v really a considerable issue, since it has adverse effects on environment as well as the health of human being. This simplified method shown wonderful results during the simulation. Further as the results suggest that there is a slight increase in execution time with the increased number of nodes. Finally this thesis presents an improved approach for the incremental variant of mobile facility location problem. It undertakes the study of increased demand with the passage of time and its impact on existing facilities as well as requirement of new facilities. Presented approach provides an efficient method to solve all the related issues of mobile facility location problem in a dynamic environment