یک الگوریتم کارا برای حل مساله کلاستر بندی ظرفیت دار

الموضوعات :

نرگس محمودی دارانی ¹ , پیام بصیری ² , مجید یوسفی خوشبخت ³

1 - استادیار، گروه ریاضی، دانشکده علوم دانشگاه بوعلی سینا، همدان، ایران
2 - مربی، دانشکده ریاضی، دانشگاه آزاد اسلامی واحد رباط کریم، باشگاه پژوهشگران جوان و نخبگان، رباط کریم، ایران
3 - مربی، دانشکده ریاضی، دانشگاه آزاد اسلامی واحد رباط کریم، باشگاه پژوهشگران جوان و نخبگان، رباط کریم، ایران

تاريخ الإرسال : 28 الأحد , ذو الحجة, 1436 تاريخ التأكيد : 12 الأحد , ربيع الأول, 1438 تاريخ الإصدار : 22 الإثنين , ربيع الثاني, 1437

الکلمات المفتاحية: Capacitated Clustering Problem, NP-hard Problems, Imperialist Competitive Algori, Swap Move, Insert Move,

ملخص المقالة :

مساله کلاستر بندی ظرفیت­دار (CCP) یک تکنیک داده کاوی برای دسته‌بندی تعدادی اشیا با ظرفیت مشخص به k کلاستر مجزا است به­طوری که ظرفیت هر کلاستر نقض نشود، هر شی دقیقاً به یک کلاستر نسبت داده شود و مجموع فاصله­های همه مراکز کلاسترها به همه اشیا مینیمم شود. مساله CCP یک مساله NP سخت است. بنابراین مسائل بزرگ این مساله را نمی‌توان در یک زمان قابل قبول حل کرد. بنابراین ما علاقمند هستیم که از روش‌های فراابتکاری برای حل این مساله استفاده کنیم. به­همین علت یک روش اصلاحی رقابت استعماری برای حل مساله CCP در این مقاله ارائه می‌شود. روش پیشنهادی MICA سه فاز اساسی تخصیص­تصادفی برای تشکیل دادن کلاسترها، تعویض مراکز کلاسترها برای بهبود بیشتر حل مساله و استفاده از الگوریتم های بهبود محلی برای اصلاح جواب را تکرار می­کند. روش پیشنهادی روی چندین مثال استاندارد در ادبیات موضوع مورد ازمایش واقع شده است. نتایج محاسباتی نه تنها نشان دهنده کارایی الگوریتم پیشنهادی است، یلکه دارای رقایت مناسبی برای حل مساله CCP با دیگر الگوریتم های فرا ابتکاری است.

المصادر:

[1] Baldacci, R., Hadjiconstantinou, E. and Mingozzi, A. “An exact algorithm for the capacitated vehicle routing problem based on a two commodity network flow formulation,” Operations Research, 2004.

[2] Ralphs, T.K., “Parallel branch and cut for capacitated vehicle routing,” Parallel Computing, 2003.

[3] Negreiros, M. and Palhano, A. “The capacitated centered clustering problem,” Computers and Operations Research, 2006.

[4] Fisher, M. L. and Jaikumar, R. “A generalized assignment heuristic for vehicle routing,” Networks, 11, 109-124, 1981.

[5] Chaves, A. A., de Assis Correa, F. and Lorena, L.A.N. “Clustering search heuristic for the capacitated p-median problem,” Advances in Software Computing Series, 2007.

[6] Mehrotra, A. and Trick, M. A. “Cliques and clustering: A combinatorial approach,” Operations Research Letters, 1998.

[7] Baldacci, R., Hadjiconstantinou, E., Maniezzo, V. and Mingozzi A., “A new method for solving capacitated location problems based on a set partitioning approach,” Computers & Operations Research, 2002.