حل مساله p-median ظرفیت دار با استفاده از الگوریتم ژنتیکت اصلاح شده

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

Keywords:

مساله جانمایی - تخصیصی , مساله p-median ظرفیت دار , الگوریتم ژنتیک