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

محورهای موضوعی : آمار

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

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

تاریخ دریافت : 1394/07/19 تاریخ پذیرش : 1395/09/21 تاریخ انتشار : 1394/11/12

کلید واژه: Capacitated Clustering Problem, NP-hard Problems, Imperialist Competitive Algori, Swap Move, Insert Move,

چکیده مقاله :

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

چکیده انگلیسی:

The capacitated clustering problem (CCP) is a data mining technique utilized to categorize a number of objects with known demands into k distinct clusters such that the capacity of each cluster is not violated, every object is allocated to exactly one cluster and sum of distances from all cluster centers to all other nodes is minimized. The CCP is an NP-hard combinatorial optimization problem. Therefore, practical large-scale instances of this problem cannot be solved by exact solution methodologies within acceptable computational time. Our interest was therefore focused on meta-heuristic solution approaches. For this reason, a modified imperialist competitive algorithm (MICA) is proposed for the CCP In this paper. The proposed MICA iterates steps between three basic phases, i.e., the random assignment phase to form clusters, the seed relocation phase to find a better median, and the local improvement phase to make a revision of the solution. The proposed algorithm is tested on several standard instances available from the literature. The computational results confirm the effectiveness of the presented algorithm and show that the proposed algorithm is competitive with other meta-heuristic algorithms for solving the 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.