مسعود یقینی - استادیار ، دانشکده مهندسی راه آهن ، دانشگاه علم و صنعت ایران
جواد لسان - دانشجوی کارشناسی ارشد ، دانشکده مهندسی راه آهن ، دانشگاه علم و صنعت ایران

خوشه بندی ظرفیت دار یکی از مسائلی است که از کاربرد گسترده ای در داده کاوی برخوردار است. این مساله به دنبال افراز یک مجموعه n تایی از عناصر به p خوشه ظرفیت دار است به طوری که تمامی اعضای یک خوشه به نقطه ای که به عنوان مرکز ثقل آن خوشه تعیین می شود ، تخصیص یابند . هدف از این مساله کمینه کردن عدم تشابه تمامی نقاط یک خوشه از مرکز ثقل خوشه با رعایت محدودیت ظرفیت در هر خوشه است ، به طوری که هر عنصر تنها به یک خوشه تخصیص یابد . در این مقاله دو روش حل متفاوت جهت حل مساله خوشه بندی ظرفیت دار ارائه شده است . روش نخست یک روش حل فرا ابتکاری مبتنی بر شبیه سازی تبریدی است که در سازوکار جستجوی جواب از ساختارهای مختلف همسایگی استفاده می کند. روش دوم مبتنی بر الگوریتم ژنتیک است که در آن از یک رویه ابتکاری جستجوی محلی استفاده شده است . روشهای ارائه شده با استفاده از مسائل نمونه ای مختلف مورد آزمون قرار گرفته اند . نتایج محاسباتی حاکی از کارایی و توانمندی روش های حل پیشنهادی است.

مساله خوشه بندی ظرفیت دار ، افراز مجموعه ای ، مساله p-median ظرفیت دار ، روش های فرا ابتکاری ، الگوریتم شبیه سازی تبریدی ، الگوریتم ژنتیک