The International Arab Journal of Information Technology (IAJIT)


Solving Capacitated Vehicle Routing Problem Using Meerkat Clan Algorithm

Noor Mahmood, ,
Capacitated Vehicle Routing Problem (CVRP) can be defined as one of the optimization problems where customers are allocated to vehicles to minimize the combined travel distances regarding all vehicles while serving customers. From the many CVRP approaches, clustering or grouping customers into possible individual vehicles' routes and identifying their optimal routes effectively. Sweep is considered a well-studied clustering algorithm to group customers, while various Traveling Salesman Problem (TSP) solving approaches are mainly applied to generate optimal individual vehicle routes. The Meerkat Clan Algorithm (MCA) can be defined as a swarm intelligence algorithm derived from careful observations regarding Meerkat (Suricata suricatta) in southern Africa's the Kalahari Desert. The animal demonstrates tactical organizational skills, excellent intelligence, and significant directional cleverness when searching for food in the desert. In comparison to the other swarm intelligence, MCA was suggested for solving optimization problems via reaching the optimal solution effects. MCA demonstrates its ability to resolve CVRP. It divides the solutions into subgroups based on meerkat behavior, providing a wide range of options for finding the best solution. Compared to present swarm intelligence algorithms for resolving CVRP, it was demonstrated that the size of the solved issues can be increased by using the algorithm suggested in this work.

[1] Akhand M., Jannat Z., Sultana T., and Hafizur Rahman M., “Solving Capacitated Vehicle Routing Problem Using Variant Sweep and Swarm Intelligence,” Journal of Applied Science and Engineering, vol. 20, no. 4, pp. 511-524 2017.

[2] Abd-ElAziz M., El-Ghareeb H., and Ksasy M., “Hybrid Heuristic Algorithm for solving Capacitated Vehicle Routing Problem,” International Journal of Computers and Technology, vol. 12, no. 9, pp. 3845-3851, 2014.

[3] Al-Obaid A., Abdullah H., and Ahmed Z., “Meerkat Clan Algorithm: a New Swarm Intelligence Algorithm,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 10, no. 1, pp. 354-360, 2018.

[4] Chen A., Yang G., and Wu Z., “Hybrid Discrete Particle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem,” Journal of Zhejiang University SCIENCE A, vol. 7, no. 4, pp. 607-614, 2006.

[5] Darani N., Ahmadi V., Eskandari Z., and Yousefikhoshbakht M., “Solving the Capacitated Clustering Problem by a Combined Meta- Heuristic Algorithm,” Journal of Advances in Computer Research, vol. 4, no. 1, pp. 89-100, 2013.

[6] Kanthavel K. and Prasad P., “Optimization of CVRP by Nested Particle Swarm Optimization,” American Journal of Applied Sciences, vol. 8, pp. 107-112, 2011.

[7] Kao Y., Chen M., and Huang Y., “A Hybrid Algorithm based on ACO and PSO for CVRP,” Research Article, Mathematical Problems in Engineering, vol. 2012, 2012.

[8] Large Capacitated Vehicle Routing Problem Instances. Available: http://www.vrp-, Last Visited, 2022.

[9] Mutar M., Burhanuddin M., Hameed A., Yusofa N., and Mutasharb H., “An Efficient Improvement of Ant Colony System Algorithms for Handling Capacity Vehicle Routing Problem,” International Journal of Industrial Engineering Computations, vol. 11, no. 4, pp. 549-564, 2020.

[10] Nazif H. and Lee L., “Optimized Crossover GA for Capacitated Vehicle Routing Problem,” Elsevier, vol. 36, no. 5, pp. 2110-2117, 2012.

[11] Niazy N., El-Sawy A., and Gadallah M., “A Hybrid Chicken Swarm Optimization with Tabu Search Algorithm for Solving Capacitated Vehicle Routing Problem,” International Journal of Intelligent Engineering and Systems, vol. 13, no. 4, pp. 237- 247, 2020.

[12] Nurcahyo G., Alias R., Shamsuddin S., and Sap M., “Sweep Algorithm in Vehicle Routing Problem for Public Transport,” Asia-Pacific Journal of Information Technology and Multimedia, vol. 2, pp. 51-64, 2002.

[13] Peya Z., Murase K., and Akhand M., “Capacitated Vehicle Routing Problem Solving through Adaptive Sweep based Clustering plus Swarm Intelligence based Route Optimization,” Oriental Journal of Computer Science and Technology, vol. 11, no. 2, pp. 88-102, 2018.

[14] Pornsing C., A Particle Swarm Optimization for the Vehicle Routing Problem, PhD. Thesis, University of Rhode Island, 2014.

[15] Sadiq A., Abdullah H., and Ahmed Z., “Solving Flexible Job Shop Scheduling Problem Using Meerkat Clan Algorithm,” Iraqi Journal of Science, vol. 59, no. 2a, pp. 753-761, 2018.

[16] Shalaby M., Mohammed A., Kassem S., “Supervised Fuzzy C-Means Techniques to Solve the Capacitated Vehicle Routing Problem,” The International Arab Journal of Information Technology, vol. 19, no. 3, pp. 452-463, 2022.

[17] Suthikarnnarunai N., “A Sweep Algorithm for the Mix Fleet Vehicle Routing Problem,” in Proceedings of the International 694 The International Arab Journal of Information Technology, Vol. 19, No. 4, July 2022 MultiConference of Engineers and Computer Scientists, Hong Kong, pp. 19-21, 2008.

[18] Szeto W., Wu Y., and Ho S., “An Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem,” European Journal of Operational Research, vol. 215, no. 1, pp. 126- 135, 2011.

[19] Tan W., Lee L., Majid Z., and Seow H., “Ant Colony Optimization for CVRP,” Journal of Computer Sciences, vol. 8, no. 6, pp. 846-852, 2012.

[20] Tavakoli M. and Sami A., “Particle Swarm Optimization in Solving Capacitated Vehicle Routing Problem,” Bulletin of Electrical Engineering and Informatics, vol. 2, no. 4, pp. 252-257, 2013.

[21] Venkatesan R., Logendran D., and Chandramohan D., “Optimization Of Capacitated Vehicle Routing Problem Using Pso,” International Journal of Engineering Science and Technology, vol. 3 no.10, pp. 7469-7477, 2011

[22] Yen L., Ismail W., Omar K., and Zirour M., “Vehicle Routing Problem: Models and Solutions,” Journal of Quality Measurement and Analysis, vol. 3, no. 1, pp. 205-218, 200.

[23] Yousefikhoshbakht M. and Khorram E., “Solving The Vehicle Routing Problem by A Hybrid Meta-Heuristic Algorithm,” Journal of Industrial Engineering International, vol. 8, no. 11, 2012. Noor Mahmood received a bachelor’s degree in computer Science from Mustansiriyah University, Iraq, in 2002; and a Master of Science (MS) in Computer Science from Baghdad University, Iraq, in 2014, and I now study Ph.D. degree in Computer Science from Mustansiriyah University, Iraq. Her research interests include Artificial Intelligent.