A Metaheuristic to Solve the Capacitated Clustering Problem

One of the most important combinatorial optimisation problems (COPs) is the capacitated clustering problem (CCP). This sort of problem involves dividing a set of nodes into a predefined number of clusters within specific limits (upper and lower); for each node in the cluster, a pair of nodes is defined that has a benefit value, and the total values of these benefits in the cluster must be maximised.
The CCP is of a non-deterministic polynomial-time hard (NP-hard) nature. Such problems cannot be practically solved by exact optimisation algorithms, so we must choose one of the metaheuristic algorithms to solve them. The CCP has many applications in a variety of domains.
This paper aims to design a metaheuristic method that solves the CCP, with an artificial bee colony (ABC) as the metaheuristic algorithm.
The effectiveness of the proposed ABC based algorithm was confirmed through several computational experiments. The results demonstrate that the proposed algorithm produced competitive outcomes compared to the state-of-the-art metaheuristics developed for the CCP.
 
مشكلة التجميع مقيد السعه واحد من اهم مسائل الاستمثال التوافقى ، هذا النوع من المشكلات ترتكز على تقسيم مجموعة من الكائنات الى مجموعات منفصلة بحيث تكون الاوزان الاجمالية لهذه الكائنات ضمن حدود معينة (حد علوى وسفلى) ، وفى نفس الوقت يتم تحقيق اقصى قدر من اجمالى اوزان الاضلاع بين ازواج الكائنات فى نفس المجموعة.
هذه المسشكلة تعد مسالة كثيرة الحدود وغير قطعية ومعقدة وبالتالى فان خوارزميات التحسن الدقيقة غير عملية لحل مثل هذه المشكلات لذلك توجب علينا اختيار احدى خوارزميات الاسترشاد. وتوجد العديد من التطبيقات لحل مشكلة التجميع مقيد السعة والتى يمكن تطبيقها فى مجالات ومشكلات مختلفة.
إن الهدف الرئيسى من هذا البحث هو تصميم خوارزمية استرشادية فعالة لحل مشكلة التجميع مقيد السعة باستخدام خوارزمية مجتمع النحل الاصطناعى كخوارزمية استرشادية.
خوازمية البحث المحلى لها اثر ملموس على قيمة دالة الهدف، وهذا يحدث عند مقارنة النتائج الحسابية مع بعض نتائج الدراسات السابقة، وهذة المقارنة تبين ان خوارزمية النحل الاصطناعى هى خوارزمية منافسىة لخوارزميات الاسترشاد الاخرى بخصوص حل مشكلة التجميع مقيد السعه.