Supervised Fuzzy C-Means Techniques
to Solve the
Capacitated Vehicle Routing Problem
Mohamed Shalaby1,2, Ayman Mohammed1, and Sally Kassem1,2
1Smart Engineering Systems Research Center, Nile
University, Egypt
2Faculty of computers and Artificial Intelligence,
Cairo University, Egypt
Abstract: Fuzzy C-Means (FCM) clustering
technique is among the most effective partitional clustering algorithms
available in the literature. The Capacitated Vehicle Routing Problem (CVRP) is
an important industrial logistics and managerial NP-hard problem. Cluster-First
Route-Second Method (CFRS) is one of the efficient techniques used to solve
CVRP. In CFRS technique, customers are first divided into clusters in the first
phase, then each cluster is solved independently as a Traveling Salesman
Problem (TSP) in the second phase. This research is concerned with the
clustering phase of CFRS, and TSP is then solved using a traditional
optimization method. Three supervised FCM based techniques are proposed to
solve the clustering phase at reduced cost via centroids (pre-FCM) initialization
phase. The proposed pre-FCM initialization techniques
are developed to be problem dependent. Hence, three initialization techniques
are first developed using K-means technique, spatially equally distributed, and demand
weighted center of mass.
Then, a modified demand weighted fuzzy c-means objective function is employed to
assign customers to clusters. To compare the performance of the proposed
supervised FCM techniques, forty-two CVRP benchmark problems are solved using
the traditional fuzzy C-means algorithm and the developed algorithms. Extensive
comparisons are conducted between the traditional fuzzy C-means algorithm, the
three proposed initialization techniques, and other fuzzy C-means techniques
available in the literature. Results show that the proposed three
initialization techniques are efficient in terms of solution quality and
computational cost.
Keywords:
Capacitated vehicle routing
problem, supervised fuzzy c-means, fuzzy clustering.
Received February 20,
2021; accepted March 7, 2021
https://doi.org/10.34028/iajit/18/3A/9