Article Preview
TopIntroduction
In this paper, a hybrid algorithm to solve uncapacitated planar multi-facility location problems is proposed. The multi-facility location problem (MFLP) is the problem of placing a number of facilities to serve a group of customers such a way that the total cost is minimized. German engineer Alfred Weber gave the first example of MFLP problems in his famous book “On the Location of Industries” in 1909. In his book, Weber emphasized that the locations of industries are crucial for optimizing the costs (Weber, 1909).
Weber (1909) used and generalized the Fermat problem in order to minimize the costs. The Fermat problem is about finding a special point in a triangle so that the sum of its distances to the corners is minimized. The problem introduced first in a letter from Fermat to Torricelli in the 17th century. Since then the same question arose and was answered in several forms. Weber (1909) reformulated the question by increasing the number of points from three to any number, and used the idea of “a weight” which is in fact firstly discussed in Steiner in 19th century (Beck & Sabach, 2015).
Hence, the problem is being now called the Fermat-Weber problem, or just the Weber Problem. Here, the aim is to find the optimum locations of facilities serving all the demand points whose locations are known, with condition that the sum of the distances from each demand point to the facility is minimized. In the original problem there is only one facility, and therefore it is also called “the single facility location problem”. On the other hand, Multi-Facility Location Problem is a generalization of Weber problem. In MFLP there is more than one facility. (Iyigun & Ben-Israel, 2010)
The location problem and its solutions have a rich literature. Since the 1960s the problem is studied more thoroughly, and many different forms have been produced and many solution methods are proposed. Daskin (1995) gives a detailed classification which contains more than ten types of classes for the problem. Similarly, Sule (2001) gives 5 steps of classification. The diversity is due to the richness of the variety of constraints in different applications.
The solution methods first primarily depend on the number of facilities and classified as the Single Facility Location Problem (SFLP) and Multi-Facility Location Problem (MFLP). In this paper, Multi-Facility Location Problems are in focus. In many applications of MFLP, decomposing the problem into a single facility location is very common because these problems are NP-hard (Esnaf and Küçükdeniz, 2013).
Another important factor in solving MFLP is the structure of the facility and demand points: Continuous (planar), network or discrete structures. In this study the assumption is that the solution has a continuous structure, that is, facilities can be placed anywhere on the plane.
One another factor in constructing solutions for MFLP is the capacity of the facilities. The facilities can have limited or unlimited sources. The facilities have an unlimited capacity for the problems solved in this study.
Besides, other factors are static or dynamic structures of the facility, ownership of the facility as public or private, deterministic or probabilistic characteristics of the demand, the addition of facilities to the existing system or facility closure, and fixed and variable costs.
In this paper, it is focused on determining locations of uncapacitated facilities in a d-dimensional plane. The authors will suggest a combination of two previously known algorithms for the solution. The first algorithm is the revised weighted version of fuzzy c-means and the second is the empowered version of the Weiszfeld algorithm (Weiszfeld,1963) called Fortified Weiszfeld proposed by Drezner (2015).