مقایسه عملکرد تجزیه بندرز بهبودیافته و الگوریتم ژنتیک در مسئله میانه هاب-p تخصیص یگانه بدون ظرفیت

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

کلیدواژه ها:

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