Extended Single-Iteration Fuzzy C-Means, and Gustafson-Kessel Algorithms for Medium-Sized (106) Multisource Weber Problem

Extended Single-Iteration Fuzzy C-Means, and Gustafson-Kessel Algorithms for Medium-Sized (106) Multisource Weber Problem

Tarik Kucukdeniz (Department of Industrial Engineering, Istanbul University-Cerrahpasa, Istanbul, Turkey), Sakir Esnaf (Department of Industrial Engineering, Istanbul University-Cerrahpasa, Istanbul, Turkey) and Engin Bayturk (American College of the Middle East, Eqaila, Kuwait)
DOI: 10.4018/IJORIS.2019070101

Abstract

An uncapacitated multisource Weber problem involves finding facility locations for known customers. When this problem is restated as finding locations for additional new facilities, while keeping the current facilities, a new solution approach is needed. In this study, two new and cooperative fuzzy clustering algorithms are developed to solve a variant of the uncapacitated version of a multisource Weber problem (MWP). The first algorithm proposed is the extensive version of the single iteration fuzzy c-means (SIFCM) algorithm. The SIFCM algorithm assigns customers to existing facilities. The new extended SIFCM (ESIFCM), which is first proposed in this study, allocates discrete locations (coordinates) with the SIFCM and locates and allocates continuous locations (coordinates) with the original FCM simultaneously. If the SIFCM and the FCM, show differences between the successive cluster center values are still decreasing, share customer points among facilities. It is simply explained as single-iteration fuzzy c-means with fuzzy c-means. The second algorithm, also proposed here, runs like the ESIFCM. Instead of the FCM, a Gustafson-Kessel (GK) fuzzy clustering algorithm is used under the same framework. This algorithm is based on single-iteration (SIGK) and the GK algorithms. Numerical results are reported using two MWP problems in a class of a medium-size-data (106 bytes). Using clustering algorithms to locate and allocate the new facilities while keeping current facilities is a novel approach. When applied to the big problems, the speed of the proposed algorithms enable to find a solution while mathematical programming solution is not doable due to the great computational costs.
Article Preview

Introduction

Arabani and Farahani (2012) divided application of fuzzy approaches in facility location problems into two categories, which are selection of facility location (a decision-making problem), and the location-allocation problem (an optimization problem). For the first category, multi-criteria decision-making methods such as Fuzzy Analytical Hierarchy Process (AHP), Fuzzy TOPSIS (The Technique for Order Preference by Similarity to Ideal Solution) are applied (Kahraman et al., 2010; Temur et al., 2014). These approaches are fuzzy extension to the well-known classical decision-making methods. A recent study with the classical methods employs DEMATEL-ANP integrated method for location decision problem (Sharma et al., 2018). Problems in the second category can be also categorized as continuous or discrete, capacitated or uncapacitated, and single and multi-facility problems. Mathematical programming, heuristics and metaheuristics are the most common methods used for the second category problems. Statistical methods can also be applied to this category (Kuruvilla et al., 2011). If problem is discrete, facility must be located in a specific point. However, in continuous problems the required number of facilities can be located anywhere in a plane. Metaheuristics, of which handles values in real number space, can be applied to both discrete and continuous problem spaces. Nevertheless, Samanta and Jha (2012) applied genetic and ant colony algorithms, which are combinatorial in their nature, to the continuous search spaces, too.

In this study a new type of facility location problem, which is in between the discrete and the continuous are defined. Here, existing facilities are handled with a discrete fashion, allocation of customers to the existing facilities is under consideration and at the same time a predefined number of new facilities are to be opened on a planar space. This type of problem has not been defined and solved in the literature.

In multisource Weber problems (MWP), also known as location-allocation problem, we are interested in finding the location of p facilities in continuous space in order to serve customers at n fixed points as well as the allocation of each customer to the facilities so that total transportation costs are minimized (Salhi and Gamal, 2003). Solving the MWP and its variants such as uncapacitated or capacitated, weighted or unweighted, continuous or discrete are much studied problem in facility location literature (Brimberg et al., 2008). Optimization skills of exact solution algorithms are not sufficient to find an optimal solution due to NP-hard nature. In real world problems, especially when struggling with very large data (classified by Hathaway and Bezdek (2006) as in Table 1), it is very complicated to find optimum solutions. This evokes hybrid and heuristics-based solution approaches to these types of problems. Li et al. (2012) proposed a two staged approach to solve the p-median problem. The first part uses a greedy search method to find an initial solution; the second part sequentially substitutes medians in the initial solution with additional vertices to reduce the total travel cost. In recent years one may find numerous papers related to the MWP but only few of them involves with large data sets. Taillard (2003) proposes three heuristic algorithms to solve p-median, sum of squares and the MWP problems including PLA85900, largest data set in all classes investigated, consists of 85900 customer points and 15000 facilities but there is no information that which category this dataset falls into according to Table 1. Küçükdeniz and Esnaf (2016) used the same data with 1000 facilities in medium to large data with 1.7 x 106 bytes, to compare new focal particle swarm optimization (FPSO) with K-means, the FCM-based clustering and classical PSO algorithms.

Table 1.
Size of the data sets after Huber (1996) (Adapted from Hathaway and Bezdek, 2006)
Bytes
“sizes”
(102)
tiny
(104)
small
(106)
medium
(108)
large
(1010)
huge
(1012)
monster
(10n>12)
VL(very large)

infinite

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2019): 3 Released, 1 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing