Nearest Facility Location for Multiple Customers using Voronoi Diagram

Abstract

In present world it is hard to survive without new technologies and internet. New technologies and applications have made our life much comfortable and luxurious. Searching for a facility near to many customers is such a problem that even an approximately correct answer can save lot of labor, time and money. The essence of all the facility location problems is to determine the location of the facility and the allocation of the demands of customers, under the condition of the minimum of the cost. This work presents a possible solution for decision makers to reach facility approximately nearer to all customers. In this thesis work an algorithm to tackle nearest facility location for multiple customers has been proposed. It tackles the problem by considering not only the aggregate distances of all customers but also the maximum difference between the farthest customer and nearest customer. It takes time of order O(n log n) as it is based on voronoi diagram of order O(n log n) and its own time is of linear order. The proposed algorithm tackles the problem of finding the nearest facility for multiple customers by considering two criteria. The first one is minimizing the aggregate distances i.e. sum of total distances covered by all the customers. The second one is minimizing the maximum difference i.e. the difference between the farthest customer and the nearest customer. The approach given here uses voronoi diagram construction algorithm as its base algorithm. To find the voronoi diagram of a given space Plane sweep algorithm or Fortune’s algorithm named after its inventor is used which computes voronoi diagram in O(n log n) and is one the most efficient algorithm known for computing voronoi diagram. The proposed algorithm is tested for various test cases and the result is in accordance with the expected answer for the problem. In future this application can be implemented using hybrid techniques which are the combination of techniques to find the nearest facility. The ultimate goal is to find the nearest facility as per the situation and requirement in a fast and efficient manner.