دانلود رایگان ترجمه مقاله مشکلات مکانی در هاب میانی اختصاصی (ساینس دایرکت – الزویر ۲۰۱۱)

مشکلات مکانی در هاب میانی اختصاصی

مبتدی (مناسب برای درک مفهوم کلی مطلب)

F2126

– فرمول بندی سه شاخصه

 راه حل معمول برای به دست آوردن فرمول بندی مدل بالا، استفاده از متغیر هایی است که در هزینه انتقال از هر مرجع به هاب مختص به آن، از الگوی مشخصی پیروی کند. این شیوه موجب فرمول بندی متغیرهایی با ۵ شاخص، یکی برای سفارش و ۴ تای دیگر برای سایر موارد خواهد شد. در واقع با توجه به این امر که مسیر مرجع به مقصد نمی تواند برعکس باشد،  می توانیم از این امر برای تعریف الگوی جریان استفاده کنیم. شاخص های اول و چهارم مربوط به مرجع و مقصد می باشند در حالی که شاخص های دوم و چهارم نشانگر هاب های میانی هستند. به جای این فرمول بندی، مدل ما می تواند الگوها را دسته بندی کرده و فرمول جدیدی با ۳ شاخص ارایه کند. برای فرمول بندی این مدل، دسته ای از λ ها را در نظر می گیریم که λi ضریب تصحیح برای موقعیت i ام خواهد بود. به علاوه متغیرهایی به صورت زیر نیز تعریف می شوند.

تابع هدف، مربوط به برآیند سه جزو هزینه حمل و نقل، به خصوص از سایت مرجع به هاب اول، اتصالات داخلی هاب و هاب آخر به مقصد نهایی می شود. اولین هزینه های حمل و نقل بعد از فرآیند جبران، با استفاده از پارامتر λ محاسبه می شوند در حالی که سایر هزینه ها به کمک پارامترهای α و δ محاسبه خواهند شد. قیدهای ۲ تضمین می کنند که هر سایت مرجع دقیقا به یک مکان در زنجیره هزینه های انتقال اختصاص داده می شود و تمامی جریان از طریق سایت مرجع با اولین هاب مرتبط خواهد بود. قید های ۳ تضمین می کنند که هر موقعیت در بردار هاب اول، به حداکثر یک مورد اختصاص داده می شود.  قیدهای ۴ تضمین می کنند که یک مرجع ممکن است فقط به هاب اول اختصاص داشته باشد. این قید ها به صورت تفکیکی در رابطه زیر نشان داده می شوند.

نتایج محاسباتی نشان می دهند که استفاده از فرم تفکیکی به لحاظ زمان انجام محاسبات، نسب به قیدهای ۳، دارای بدترین شرایط می باشد. قیدهای ۵ بیان می کنند که اگر یک مرجع خود یک هاب باشد، اولین هاب در مسیر مرجع به مقصد، باید j باشد.

وظیفه قیدهای ۶ قیدهای حفظ جریان بوده و تضمین می کنند جریانی که وارد هاب k می شود، همان جریانی است که از هاب k به مقصد m خواهد رفت. قیدهای ۷ ارتباط بین هزینه های حمل و نقل با هاب سایت مرجع را مشخص می کنند. قیدهای ۸ تضمین می کنند که اگر مقصد نهایی یک هاب باشد، جریان از هاب دیگری نیز عبور خواهد کرد. قیدهای ۹ و ۱۰ بیان می کنند که گره های میانی در هر مسیر باید به صورت هاب باشند. در نتیجه قید ۱۱، تعداد هاب ها را برای جاگذاری ثابت می کند.

توسط قیدهای ۵، متغیرهای y_k می توانند به صورت پیوسته تعریف شوند در حالی که متغیرهای r آنها را مجبور می کنند تا مقادیری به صورت ۰ و ۱ داشته باشند. در حقیقت متغیرهای y را می توان با استفاده از قیدهای ۵ از این معادله حذف کرد اما به منظور تشخیص متغیرهای مکانی این کار انجام نشده است.

توجه داشته باشید قیدهای ۵ و ۸ در صورتی که نامساوی مثلث ارضاء شود کاربردی نخواهند داشت، و فقط در کاهش زمان حل موثر خواهند بود. ( برای جزییات بیشتر به ضمایم مراجعه شود).

۳- فرمول بندی جایگزین بر پایه پوشش متغیرها ; پوشش فرمول بندی سه شاخصه

در این بخش فرمول بندی جدیدی را بر اساس پوشش متغیرها ارایه می کنیم. برای این منظور ابتدا G را به عنوان تعداد المان های غیر صفر تعریف می کنیم. اگر تابع هزینه به صورت  باشد در نتیجه می توان مقادیر این زنجیره را به صورت غیر افزایشی مرتب کرد.

با استفاده از این زنجیره می توانیم تمامی هزینه های تخصیصی را مرتب کنیم. این را می توان با استفاده از متغیرهای زیر انجام داد.

– مقایسه روابط

به منظور بهبود عملکرد روابط سه شاخصه، ابتدا باید توسط بررسی محاسباتی، آنها را مقایسه کنیم. روابط به همان صورت که در بخش قبلی نشان داده شده اند در نرم افزار Xpress IVE 1.19.01 و بر روی سیستمی با مشخصات ۲٫۴GHz و ۲GRAM مورد استفاده قرار می گیرند. در این مقاله روابط اشاره شده در بخش قبل مقایسه شده است.

برای تهیه نمونه های آزمایش، داده ها را با دو روش متفاوت ایجاد کردیم. در نمونه های اولیه، هزینه ها و جریان مرجع به مقصد را مشخص کرده و در نمونه های دوم، هزینه های اتفاقی را نیز در نظر گرفتیم. در این طراحی، هدف بررسی اختلاف بیK حالت های مختلف داده می باشد. هر مقدار که فاصله بخش بندی ها کوچک تر باشد، تعداد تکرار بیشتر خواهد بود. با استفاده از این داده ها می خواهیم بررسی کنیم که آیا اندازه پارامتر G در حل مسئله با فرمول بندی سه شاخصه مهم می باشد. روابط را در حالت های (i) ماتریس های هزینه (ii) N در {۱۰ و ۱۵ و ۲۰} (iii) مقادیر مختلف p (iv) α=۷٫ و δ=۱٫۲α و شش حالت مختلف بردارهای v بررسی کردیم.

جداول ۲ و ۳ نشان دهنده نتاج برای این نمونه ها می باشند. اولین ستون جدول نشان دهنده انواع مختلف مسایل در این بررسی خواهد بود. ستون های nodes، R-GAP،GAP و time نشانگر مقدار میانگین، میزان Gap، Gap نهایی بعد از یک ساعت و زمان cpu در واحد ثانیه می باشند. مقادیر بزرگتر از ۳۶۰۰ در ستون زمان نشان می دهند که برای حل مسئله نیاز به زمان بیشتر از ۱ ساعت بوده و علامت * نشان می دهد که حداقل یک مورد از ۵ نمونه مورد نظر، حل نشده است. در این موارد ستون Gap نشان دهنده این مقدار در زمان توقف خواهد بود.

با بررسی جداول مشخص می شود که در اغلب موارد، فرمول بندی پوششی به فرمول بندی سه شاخصه ارجحیت دارد. به علاوه این ارجحیت با کاهش میزان G افزایش می یابد.

این قضیه را می توان با توجه به رفتار متغیر های سه شاخصه پوششی در نمونه های جدول ۲ مشاهده کرد که تعداد تکرار بیشتر از نمونه های جدول ۳ بوده و در نتیجه مقدار G کمتر خواهد بود. در واقع می توان گفت زمانی که G کاهش یابد شرایط بهتر خواهد شد. توجه داشته باشید که در این رابطه تعداد متغیرها و قیدها به G وابسته می باشند. (تعداد متغیرها و قید ها برای متغیرهای سه شاخصه برابر با  و  می باشد در حالی که برای متغیر های پوششی برابر با و  خواهد بود. جدول ۵ مشاهده شود.) با مشاهده GAP در گره ریشه مشخص می شود که در هر دو رابطه این میزان در گره یکسان خواهد بود.

به علاوه جداول ۲ و ۳ نشان می دهند که برای بردار λ، با بزرگ تر شدن اندازه نمونه، زمان تحلیل افزایش می یابد. فرمول بندی سه شاخصه قادر به رسیدن به حالت بهینه برای نمونه هایی با سایز N=20 نمی باشد به جز حالتی که P=10 و λ به صورت غیر افزایشی باشد. انتخاب صحیح λ موجب ساده سازی مسئله خواهد شد. این تاثیر ناشی از این است که اجزاء λ متفاوت بوده و در نتیجه از انحطاط جلوگیری می شود. رفتار مشابهی نیز در رابطه سه شاخصه پوششی قابل مشاهده است. گرچه در این حالت مقادیر GAP بسیار کوچک تر هستند.

این آنالیز را برای α=۲٫ و δ= ۸۴٫ نیز انجام دادیم که نتایج مشابهی به دست آمد. اگرچه این مدل نیاز به زمان بیشتری برای حل داشت. به علاوه به دلیل اینکه در این حالت هزینه انتقال بین هاب ها مقدار قابل توجهی می باشد،این است که تعداد مسیرهای عبوری از ۲ هاب مختلف به میزان حدود ۸ درصد افزایش خواهد یافت.