شماره ركورد كنفرانس :
5432
عنوان مقاله :
مقايسه عملكرد تجزيه بندرز بهبوديافته و الگوريتم ژنتيك در مسئله ميانه هاب-p تخصيص يگانه بدون ظرفيت
پديدآورندگان :
حداد رضا reza_haddad@ie.sharif.edu دانشجوي كارشناسي ارشد مهندسي صنايع، دانشگاه صنعتي شريف , بيشه نياسر محمدامير ma_bishehniasar@ie.sharif.edu دانشجوي كارشناسي ارشد مهندسي صنايع، دانشگاه صنعتي شريف , ورمرزيار محسن varmazyar@sharif.edu استاديار دانشكده مهندسي صنايع، دانشگاه صنعتي شريف
كليدواژه :
مكان‌يابي هاب , ميانه هاب-p , تجزيه بندرز , الگوريتم ژنتيك , مسئله ميانه هاب-p تخصيص يگانه بدون ظرفيت
عنوان كنفرانس :
شانزدهمين كنفرانس بين المللي انجمن ايراني تحقيق در عمليات
چكيده فارسي :
هاب‌ها تسهيلات ويژه‌اي هستند كه براي تجميع، مرتب‌سازي و تغيير جهت جريان‌هاي تقاضا در بسياري از شبكه‌هاي حمل‌ونقل و مخابرات وجود دارند. معمولاً اين تسهيلات به دليل صرفه‌جويي در مقياس از هزينه‌هاي تنزيلي در حين انتقال جريان‌هاي تلفيقي بهره‌مند مي‌شوند. مسائل مكان‌يابي هاب (HLP) با تعيين گره هاب‌ها و تخصيص گره‌هاي غيرهاب به هاب‌ها سروكار دارد. انواع مختلفي از مسائل مكان‌يابي هاب بر اساس ويژگي‌هاي يك شبكه هاب خاص وجود دارد. در اين مقاله به بررسي يك طرح مكان‌يابي هاب با طرح تخصيص يگانه بدون ظرفيت و تعداد گره هاب ثابت پرداخته مي‌شود. سپس با توجه به كلاس NP-hard اين مسائل در ابعاد بزرگ، اين مسئله با دو روش حل دقيق بندرز بهبود يافته و روش حل با الگوريتم ژنتيك بررسي مي‌گردد. سپس نتايج روش حل الگوريتم دقيق مبتني بر تجزيه بندرز بهبود يافته براي حل نمونه‌هاي مقياس بزرگ مسئله مكان‌يابي هاب-p با طرح تخصيص يگانه بدون ظرفيت با روش الگوريتم ژنتيك از نظر عملكرد آن در كيفيت جواب‌ها و پيچيدگي زماني حل مقايسه شده است. نتايج نشان مي‌دهد كه الگوريتم ژنتيك زمان حل پايين‌تري به ازاي هر تكرار نسبت به الگوريتم تجزيه بندرز مورد استفاده دارد.
