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.

References

[1] Alata M., Molhim M., and Ramini A., “Optimizing of Fuzzy C-Means Clustering Algorithm Using GA,” International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 2, no. 3, pp. 670- 675, 2008.

[2] Archetti C., Speranza M., and Hertz A., “A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem,” Transportation Science, vol. 40, no. 1, pp. 64-73, 2006.

[3] Augerat P., Approche Polyèdrale Du Problème De Tournées De Véhicules, Doctoral dissertation, Algorithm Total Deviation Average Deviation FCM 6.5% 8.31% Modified FCM 3.7% 3.09% K-means initialization 6.6% 7.50% SED initialization 8.2% 7.59% DWCM initialization 6.7% 5.88% 460 The International Arab Journal of Information Technology, Vol. 18, No. 3A, Special Issue 2021 Institut National Polytechnique de Grenoble- INPG, 1995.

[4] Barreto S., Ferreira C., Paixão J., and Santos B., “Using Clustering Analysis in A Capacitated Location-Routing Problem,” European Journal of Operational Research, vol. 179, no. 3, pp. 968- 977, 2007.

[5] Bellman R. and Zadeh L., “Decision-Making in a Fuzzy Environment,” Management Science, vol. 17, no. 4, pp. 141-164, 1970.

[6] Bezdek J., Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum,1981.

[7] Bi X., Han Z., and Tang W., “Evolutionary Multi- Objective Optimization for Multi-depot Vehicle Routing in Logistics,” International Journal of Computational Intelligence Systems, vol. 10, no. 1, pp. 1337-1344, 2017.

[8] Bora D. and Gupta A., “Impact of Exponent Parameter Value for the Partition Matrix on the Performance of Fuzzy C Means Algorithm,” Computer Vision and Pattern Recognition, vol. 3, no. 3, 2014.

[9] Bramel J. and Simchi-Levi D., The Logic of Logistics: Theory, Algorithms, and Applications for Logistics and Supply Chain Management, Springer, 2014.

[10] Choe H. and Jordan J., “On The Optimal Choice of Parameters in A Fuzzy C-Means Algorithm,” inProceedings of The International Conference on Fuzzy Systems, San Diego, pp. 349-354, 1992.

[11] Christofides N. and Eilon S., “Expected Distances in Distribution Problems,” Journal of the Operational Research Society , vol. 20, no. 4, pp. 437-443, 1969.

[12] Christofides N., Mingozzi A., and Toth P., “The Vehicle Routing Problem,” Combinatorial Optimization, pp. 315-338, 1979.

[13] Cordeau J., Gendreau M., Hertz A., Laporte G., and Sormany J., “New Heuristics for the Vehicle Routing Problem,” Logistics Systems: Design and Optimization, pp. 279-297, 2005.

[14] Cruijssen F., Bräysy O., Dullaert W., Fleuren H., and Salomon M., “Joint Route Planning Under Varying Market Conditions,” The International Journal of Physical Distribution and Logistics Management, vol. 37, no. 4, pp. 287-04, 2007.

[15] Cui J., Li Q., Wang J., and Zong D., “Research on Selection Method of the Optimal Weighting Exponent and Clustering Number in Fuzzy C- Means Algorithm,” in Proceedings of The International Conference on Intelligent Computation Technology and Automation, Changsha, pp. 104-107,2010.

[16] Dantzig G. and Ramser J., “The Truck 'LVSDWFKLQJ3UREOHP´Management Science, vol. 6, no. 1, pp. 80-91, 1959.

[17] Dunn J., “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well- Separated Clusters,” Journal of Cybernetics, vol. 3, no. 3, pp. 32-57, 1973.

[18] Dunn J., “Well-Separated Clusters and Optimal Fuzzy Partitions,” Journal of Cybernetics, vol. 4, no. 1, pp. 95-104, 1974.

[19] Embaby A., Shalaby M., and Elsayed K., “FCM- Based Approach for Locatingvisible Video Watermarks,” Symmetry, vol. 12, no. 3, pp. 339- 57, 2020.

[20] Ewbank H., Wanke P., and Hadi-Vencheh A., “An Unsupervised Fuzzy Clustering Approach to The Capacitated Vehicle Routing Problem,” Neural Computing and Applications, vol. 27, no. 4, pp. 857-867, 2016.

[21] Ewbank H., Wanke P., Correa H., and Figueiredo O., “The Capacitated Vehicle RoutingProblem Revisited: Using Fuzzy C-Means Clustering,” International Journal of Logistics Systems and Management, vol. 34, no. 4, pp. 411, 2019.

[22] Fisher M., “Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees,” Operations Research, vol. 42, no. 4, pp. 626-642, 1994.

[23] Gansterer M. and Hartl R., “Collaborative Vehicle Routing: A Survey,” European Journal of Operational Research, vol. 268, no. 1, pp. 1-12, 2018.

[24] Gen-Yuan D., Fang M., Sheng-Li T., and Ye L., “A Modified Fuzzy C-means Algorithm in Remote Sensing Image Segmentation,” in Proceedings of The International Conference on Environmental Science and Information Application Technology, Wuhan, pp. 447-450, 2009.

[25] Golden B., Assad A., Levy L., and Gheysens F., “The Fleet Size and Mix Vehicle Routing Problem,” Computers and Operations Research, vol.11, no. 1, pp. 49-66, 1984.

[26] Golden B., Wasil E., Kelly J., and Chao I., “The Impact of Metaheuristics on Solving The Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results,” Fleet Management and Logistics, pp. 33-56, 1998.

[27] Guajardo M. and Rönnqvist M., “A Review on Cost Allocation Methods in Collaborative Transportation,” International Transactions in Operational Research, vol. 23, no. 3, pp. 371-392, 2015.

[28] Irnich S., Schneider M., and Vigo D., “Chapter 9: Four Variants of the Vehicle Routing Problem,” Vehicle Routing, pp. 241-271, 2014.

[29] Jacobs-Blecha C. and Goetschalckx M., “The Vehicle Routing Problem with Backhauls: Properties and Solution Algorithms,” Georgia Institute of Technology, Technical Report MHRC- TR-88-13, 1993.

[30] Jayasuriya S. and Liew A., “A Modified Fuzzy C- Means Algorithm with Symmetry Information for MR Brain Image Segmentation,” in Proceedings Supervised Fuzzy C-Means Techniques to Solve the Capacitated Vehicle Routing Problem 461 of The 9th International Conference on Information, Communications and Signal Processing, Tainan, pp. 1-5, 2013.

[31] Jiuh-Biing S., “A Hybrid Fuzzy-Optimization Approach to Customer Grouping-Based Logistics Distribution Operations,”Applied Mathematical Modelling, vol. 31, no. 6, pp. 1048-1066, 2007.

[32] Kagay S., Kikuchi S., and Donnelly R., “Use of A Fuzzy Theory Technique for Grouping of Trips in The Vehicle Routing and Scheduling Problem,” European Journal of Operational Research, vol. 76, no. 1, pp. 143-154, 1994.

[33] Karakatič S. and Podgorelec V., “A Survey of Genetic Algorithms For Solving Multi Depot Vehicle Routing Problem,” Applied Soft Computing, vol. 27, pp. 519-532, 2015.

[34] Karp R., “Reducibility Among Combinatorial Problems,” in Proceedings of a symposium Complexity of Computer Computations, New York, pp. 219-241, 2009.

[35] Kassem S. and Mingyuan C., “A Heuristic Method For Solving Reverse Logistics Vehicle Routing Problems with Time Windows,” International Journal of Industrial and Systems Engineering, vol. 12, no. 2, pp. 207-222, 2012.

[36] Kassem S., Korayem L., Khorshid M. and Tharwat A., “A Hybrid Bat Algorithm To Solve The Capacitated Vehicle Routing Problem,” in Proceedings of The Novel Intelligent and Leading Emerging Sciences Conference, Giza, pp. 222- 225, 2019.

[37] Khaled K., Shalaby M., and El Sayed K., “Automatic Fuzzy-Based Hybrid Approachfor Segmentation, and Centerline Extraction of Main Coronary Arteries,” International Journal of Advanced Computer Science and Applications, vol. 8, no. 6, pp. 258-64, 2017.

[38] Koç Ç. and Laporte G., “Vehicle Routing with Backhauls: Review and Research Perspectives,” Computers and Operations Research, vol. 91, pp. 79-91, 2018.

[39] Korayem L., Khorsid M., and Kassem S., “A Hybrid K-Means Metaheuristic Algorithm to Solve A Class of Vehicle Routing Problems,” Advanced Science Letters, vol. 21, no. 12, pp. 3720-3722, 2015.

[40] Korayem L., Khorsid M., and Kassem S., “Using Grey Wolf Algorithm to Solve the Capacitated Vehicle Routing Problem,” IOP Conference Series: Materials Science and Engineering, vol. 83, pp.1-10, 2015.

[41] Kumar S., and Panneerselvam R., “A Survey on the Vehicle Routing Problem and Its Variants,” Intelligent Information Management, vol. 4, no. 3, pp. 66-74, 2012.

[42] Lenstra J. and Kan R., “Complexity of Vehicle Routing and Scheduling Problems,” Networks, vol. 11, no. 2, pp. 221-227, 1981.

[43] Marinelli M., Colovic A., and DellOrco M., “A Novel Dynamic Programming Approach for Twoechelon Capacitated Vehicle Routing Problem in City Logistics with Environmental Considerations,” Transportation Research Procedia, vol. 30, pp. 147-156, 2018.

[44] Mcbratney A. and Moore A., “Application of Fuzzy Sets to Climatic Classification,” Agricultural and Forest Meteorology, vol. 35, no. 1-4, pp. 165-185, 1985.

[45] Mingozzi A., Prins C., and Calvo R., “Capacitated Depot Location for the Vehicle Routing Problem,” in Proceedings of the International Conference on Service Systems and Service Management, Troyes, pp. 1547-1551, 2006.

[46] Mirjalili S., Mirjalili S., and Lewis A., “Grey Wolf Optimizer,” Advances in Engineering Software, vol. 69, pp. 46-61, 2014.

[47] Montoya-Torres J., Franco J., Isaza N., Jiménez H., and Herazo-Padilla N., “A Literature Review on The Vehicle Routing Problem with Multiple Depots,” Computers and Industrial Engineering, vol. 79, pp. 115-129, 2015.

[48] MurugasamyK. and Mathaiyan N., “Performance Analysis of Data ClusteringAlgorithms Using Various Effectiveness Measures,” The International Arab Journal of Information Technology, vol. 13, no. 6B, pp. 1084-1091, 2016.

[49] Naddef D. and Rinaldi G., “Branch-and-Cut Algorithms for the Capacitated VRP,” The Vehicle Routing Problem, pp. 53-84, 2002.

[50] Narayanan S., “Travelling Salesman Problem,” https://www.mathworks.com/matlabcentral/fileex change/64654-travellingsalesman-problem, Last Visited, 2020.

[51] Nasraoui O. and N'Cir C., Clustering Methods for Big Data Analytics: Techniques, Toolboxes and Applications, Springer International Publishing, 2019.

[52] Okeke F. and Karnieli A., “Linear Mixture Model Approach for Selecting Fuzzy Exponent Value in Fuzzy C-Means Algorithm,” Ecological Informatics, vol. 1, no. 1, pp. 117-124, 2006.

[53] Oyola J., Arntzen H., and Woodruff L., “The Stochastic Vehicle Routing Problem, A Literature Review, Part I: Models,” EURO Journal on Transportation and Logistics, vol. 7, no. 3, 193- 221, 2018.

[54] Papadimitriou C. and Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Mineola: Dover Publications, 2014.

[55] Pei J., Yang X., Gao X., and Xie W.,“Weighting Exponent M in Fuzzy C-Means (FCM) Clustering Algorithm,” Object Detection, Classification, and Tracking Technologies International Society for Optics and Photonics, vol. 4554, pp. 246-251, 2001. 462 The International Arab Journal of Information Technology, Vol. 18, No. 3A, Special Issue 2021

[56] Qi C. and Sun Y., “An Improved Ant Colony Algorithm for VRPTW,” in Proceedings of the International Conference on Computer Science and Software Engineering, Wuhan, pp. 455-458, 2008.

[57] Sathyanarayanan S. and Joseph K., “A Survey on Stochastic Vehicle Routing Problem,” in Proceedings of theInternational Conference on Information Communication and Embedded Systems,Chennai, 2014.

[58] Shalaby M., Mohammed A., and Kassem S., “Modified Fuzzy C-Means Clustering Approach to Solve the Capacitated Vehicle Routing Problem,” in Proceedings of The 21st International Arab Conference on Information Technology, 6th of October city, pp. 1-7, 2020.

[59] Shalaby M., “Fingerprint Recognition: A Histogram Analysis Based Fuzzy C-Means Multilevel Structural Approach,” Ph.D. Theses, Concordia University, 2012.

[60] Thinkaran N., Jayaprakash J., and Elanchezhian C., “Optimization of Total Cost in Inventory Routing Problem with Homogenous Type of Vehicles Using Metaheuristic Algorithm-A Review,” Materials Today: Proceedings, vol. 16, pp. 1043-1047, 2019.

[61] Toth P. and Vigo D., “Models, Relaxations and Exact Approaches for The Capacitated Vehicle Routing Problem,” Discrete Applied Mathematics, vol. 123, no. 1-3, pp. 487-512, 2002.

[62] Toth P. and Vigo D., The Vehicle Routing Problem, Philadelphia: Society for Industrial and Applied Mathematics, 2002.

[63] Vattani A., “K-Means Requires Exponentially Many Iterations Even in The Plane,” Discrete and Computational Geometry, vol. 45, no. 4, pp. 596- 616, 2011.

[64] Vidal T., Crainic T., Gendreau M., Lahrichi N., and Rei W., “A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems,” Operations Research, vol. 60, no. 3, pp. 611-624, 2012.

[65] Wolsey L., Integer Programming, Wiley, 1998.

[66] Xu X., Lin Z., and Zhu J., “DVRP with Limited Supply and Variable Neighborhood Region in Refined Oil Distribution,” Annals of Operations Research, 2020.

[67] Yalcın G. and Erginel N., “Fuzzy Multi-Objective Programming Algorithm for Vehicle Routing Problems with Backhauls,” Expert Systems with Applications, vol. 42, no. 13, pp. 5632-5644, 2015.

[68] Yang M., “A Survey of Fuzzy Clustering,” Mathematical and Computer Modelling, vol. 18, no. 11, pp. 1-16, 1993.

[69] Yang W., Mathur K., and Ballou R., “Stochastic Vehicle Routing Problem with Restocking,” Transportation Science, vol. 34, no. 1, pp. 99-112, 2000.

[70] Yong W., Ma X., Xu M., Wang Y., and Liu Y., “Vehicle Routing Problem Based on A Fuzzy Customer Clustering Approach for Logistics Network Optimization,” Journal of Intelligent and Fuzzy Systems, vol. 29, no. 4, pp. 1427-1442, 2015. Mohamed Shalaby is an IEEE member, he received the PhD degree in electrical and computer engineering from Concordia University, Canada in 2012. Starting from 2013 till 2017, he was a full-time assistant professor in the fields of robotics, image and video processing at the information technology department, faculty of computers and artificial intelligence, Cairo University, Giza, Egypt. Then he joined the mechatronics program at faculty of engineering and applied sciences, Nile University, Giza, Egypt. His research interests include robotics, artificial intelligence, deep learning, biometrics, image processing, pattern recognition, and Supervised Fuzzy C-Means Techniques to Solve the Capacitated Vehicle Routing Problem 463 computer vision. Dr. Shalaby has been an associate editor of the Egyptian Informatics Journal, Elsevier, since 2015. Recently, Dr. Shalaby has been a founding member of the multi-disciplinary Smart Engineering Systems Research Center (SESC) at Nile University, Giza, Egypt. Ayman Mohammed is a young researcher who obtained his BSc in Industrial Engineering from the school of engineering and applied sciences, Nile University in 2020. During his undergraduate studies at Nile University, he has understood and practiced the basics of scientific research in the field of industrial engineering and management. He is currently a MSc Mechatronics engineering student and works as a research assistant at Smart Engineering Systems Research Center (SESC). Sally Kassem obtained her B.Sc. degree from mechanical design and production department, Faculty of Engineering, Cairo University in 1998. She earned her MSc. Degree in industrial engineering at the same affiliation, and the Ph.D. degree in industrial engineering in 2011 at the Department of Mechanical and Industrial Engineering, Concordia University, Montreal, Canada. Dr. Kassem has been an assistant professor at the Department of Operations Research and Decision Support, Faculty of Computers and Information, Cairo University since 2013. Currently, Dr. Kassem is an assistant professor at the School of Engineering and Applied Sciences, Industrial and Service Engineering Program, Nile University, Egypt. Dr. Sally Kassem co-authored several research papers that have been published in reputable journals and conferences, in diverse fields, for example, logistics and supply chain, IOT monitoring optimization, design for sustainability, modeling and simulation. She served as a reviewer for a number of international conferences and journals of well-recognized publishers and organizations, like Elsevier, IEEE, and Inderscience.