Beta
324294

A Metaheuristic to Solve the Capacitated Clustering Problem

Article

Last updated: 03 Jan 2025

Subjects

-

Tags

Electrical engineering

Abstract

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.   مشكلة التجميع مقيد السعه واحد من اهم مسائل الاستمثال التوافقى ، هذا النوع من المشكلات ترتكز على تقسيم مجموعة من الكائنات الى مجموعات منفصلة بحيث تكون الاوزان الاجمالية لهذه الكائنات ضمن حدود معينة (حد علوى وسفلى) ، وفى نفس الوقت يتم تحقيق اقصى قدر من اجمالى اوزان الاضلاع بين ازواج الكائنات فى نفس المجموعة. هذه المسشكلة تعد مسالة كثيرة الحدود وغير قطعية ومعقدة وبالتالى فان خوارزميات التحسن الدقيقة غير عملية لحل مثل هذه المشكلات لذلك توجب علينا اختيار احدى خوارزميات الاسترشاد. وتوجد العديد من التطبيقات لحل مشكلة التجميع مقيد السعة والتى يمكن تطبيقها فى مجالات ومشكلات مختلفة. إن الهدف الرئيسى من هذا البحث هو تصميم خوارزمية استرشادية فعالة لحل مشكلة التجميع مقيد السعة باستخدام خوارزمية مجتمع النحل الاصطناعى كخوارزمية استرشادية. خوازمية البحث المحلى لها اثر ملموس على قيمة دالة الهدف، وهذا يحدث عند مقارنة النتائج الحسابية مع بعض نتائج الدراسات السابقة، وهذة المقارنة تبين ان خوارزمية النحل الاصطناعى هى خوارزمية منافسىة لخوارزميات الاسترشاد الاخرى بخصوص حل مشكلة التجميع مقيد السعه.

DOI

10.21608/auej.2023.235083.1420

Keywords

Capacitated clustering problem (CCP), Local Search, Neighbouring operators, Constraints handling, Artificial bee colony (ABC). مشكلة التجمع مقيد السعه، البحث المحلي، العوامل المجاورة، التعامل مع القيود، مستعمرة النحل الاصطناعية

Authors

First Name

Banan

Last Name

AlTuwaim

MiddleName

N.

Affiliation

Department of Computer Science, College of Computer & Information Sciences, Al Imam Mohammad Ibn Saud Islamic University, Riyadh, Saudi Arabia

Email

banan2746@gmail.com

City

-

Orcid

-

Volume

18

Article Issue

69

Related Issue

44187

Issue Date

2023-10-01

Receive Date

2023-08-09

Publish Date

2023-10-01

Page Start

884

Page End

899

Print ISSN

1687-8418

Online ISSN

3009-7622

Link

https://jaes.journals.ekb.eg/article_324294.html

Detail API

https://jaes.journals.ekb.eg/service?article_code=324294

Order

324,294

Type

Original Article

Type Code

706

Publication Type

Journal

Publication Title

Journal of Al-Azhar University Engineering Sector

Publication Link

https://jaes.journals.ekb.eg/

MainTitle

A Metaheuristic to Solve the Capacitated Clustering Problem

Details

Type

Article

Created At

24 Dec 2024