نشریه تخصصی مهندسی صنایع، دوره 48، شماره 2، مهر ماه 1393، از صفحه 243 تا 255

حل م ئلة چندهدفة مکان یابی هاب با درنظرگرفت ویژگی های غیرقطعی نقاط بالقوه و م یرها با استفاده از روش تجریة بندرز

سعید عباسی پاریری1، مجید امی نیری2* و مهدی بشیری3
دانشآموختة کارشناسی ارشد مهندسی صنایع دانشکدة مهندسی صنایع و تحلیل سیستمهای دانشگاه امیرکبیر )پلی تکنیک تهران(
دانشیار گروه مهندسی صنایع دانشکدة مهندسی صنایع و تحلیل سیستم های دانشگاه امیرکبیر
)پلی تکنیک تهران(
دانشیار گروه مهندسی صنایع دانشکدة فنی و مهندسی دانشگاه شاهد

)تاریخ دریافت 25/3/92 ـ تاریخ دریافت روایت اصلاح شده 6/2/93 ـ تاریخ تصویب 26/7/93( چکیده
در این پژوهش مسسلة مکان یابی وندهدفة تسهیلات هاب با درنظرگرفتن ویژگی های ییر قطعی نقاط بالقوه و مسیر، با تابع هدا اوب، به صورت کمینه کردن مجموع هزینة ثابت استقرار تسهیلات هـاب، بـه عـلاوة هزینـة احتمـالی حمـل ونقـل، و تـابع هـدا دوم، بـه صـورتکمینه کردن معیارهای عدم ا مینان شبکه، مدب شده است. در این مطالعه، شاخص هایی از قبیل شرایو آب وهوایی، امنیـت، نـرخ تبـادبارز، و شرایو اضطراری مسیر به منزلة معیارهای ایجاد عدم ا مینان بر اساس سناریوهای احتمالی تعریف و در ادامه با تابع توزیع احتماب نرماب تقریب زده شد. همچنین، در مدب پیشنهادی، سطح سرویم1 برای معیارهای عدم ا مینان شبکه در قالب محدودیتهای احتمالی2 در نظر گرفته شد. الگوریتم تجزیة بندرز3 برای حل مدب پیشنهادی به کار رفت. برای ارزیابی عملکرد این روش، نتایج حاصل از حل مدب توسو الگوریتم تجزیة بندرز با حل آن توسو یک نرم افزار تجاری مقایسه شـد. نتـایج نشـان داد روش تجزیـة بنـدرز توانـایی حـل مـدبپیشنهادی با اندازه های مختلف را دارد؛ در حالی که این مدب فقو در اندازه های کووک با نرم افزار قابل حل است.

واژه های کلیدی: الگوریتم تجزیة بندرز، برنامه ریزی تصادفی دومرحله ای، محدودیت احتمالی، مسسلة مکان یابی
وندهدفة هاب.

مقدمه
مسائل مکان یابی هـاب نقشـی مـ ؤثر در بهبـود کـاراییسیستم های حمل ونقل دارنـد. نقـاط میـانی، کـه هـابنامیده مـی شـوند ، وظیفـ ة جمـع آوری، مرتـب سـازی ، و توزیع به نقاط مصرا را دارند؛ به گونه ای که حمل ونقل بین هاب ها هزینة بسیار کمتـری دا رد و عمـلاً سیسـتمحمل ونقل را به استفاده از هاب به جای انتقاب مستقیم تشویق می کند.
مسائل مکان یابی هاب را می توان به دو دستة کلـیمسائل تک هدفه و مسائل وندهدفه تقسیم کرد .مسائل وندهدفه4، برخلاا مسائل تـک هدفـه ، کمتـر مطالعـهشده اند؛ که در این پژوهش بیشتر بررسی می شـوند . در

نویسندة مسسوب: تلفن: 64545300، فاکم: 66954569
یکی از مطالعات انجام شده، رویکردی جدید در مواجهـهبا مسسلة مکان یابی شبکة هاب ظرفیت دار بـا تخصـیصیگانه اخا شد؛ به این صورت که تابع هـدا دومـی، بـاماهیت کمینه سازی زمان سرویم دهی هر گره هاب بـهواح د جری ان ورودی، ب ه م دب اض افه و ب ه ج ای آن محدودیت ظرفیت از مسـسله حـاا مـی شـود. گفتنـیاست این تابع هدا با دو رویکرد کمینه کـردن مجمـوعزمان های سرویم دهی و کمینه کردن بیشینة زمان های سرویم دهی تعریف می شود [1].
ایلب مدب هایی که عـدم قطعیـت در آن هـا لحـا شــده، بــه دلیــل نبــود ا لاعــات کامــل مســسله یــا Email: [email protected]
ییرقطعی بودن داده ها، مسسله را نسـبت بـه مـدب هـایقطعی کاراتر فرموب بندی می کنند. در مسائل مکان یابی ه اب نی ز ایل ب انتخ اب مک ان تس هیلات ه اب ی ک تصمیم گیری استراتژیک بلندمدت است کـه بـر اسـاسآن جهت انتخاب مسیر در گام بعـد تعیـین مـی شـود و لازم است تصمیم گیری دربارة مکان یابی دوباره به هنگام شود. معمولاً پارامترهایی مانند میـزان تقاضـا و هزینـة آماده سازی تسهیلات هاب مـی تواننـد بـه صـورت ییـر قطعی فرض شوند. مسائل ییر قطعی به دو دستة کلـیبهینه سـازی تصـادفی5 و بهینـهسـازی پایـدار6 تقسـیممی شوند. اگـر متلیرهـای تصـادفی از الگـوی تلییـراتخاص ی پی روی کنن د، در دس تة اوب و اگ ر داده ه ای تصادفی دارای تابع توزیع مشـخص نباشـند، در دسـت ة دوم ق رار م یگیرن د [2]. در ای ن خص ود، مطالع ات پیشین فرض هایی همچـون ظرفیـت تسـهیلات و نـوعتخصیص و مـوارد ی نظیـر آن را بررسـی کـرده انـد . در تحقیقی دیگر، مدلی با رویکرد مدیریت نامتمرکز جهت راحی شبکة هاب ارائـه شـد کـه در آن شـرکت هـایحمل ونقل، با توجه به معیارهای خـاد خـود، از جملـه هزینه و زمان و ترافیک، مسیر را انتخاب مـی کننـد . بـاتوجه به شرایو خـ اد هـر شـرکت، ایجـاد مسـیرهایمستقیم بین مبدأ و مقصد نیز مجاز اسـت . جهـت حـل مسسله لازم است هر شرکت احتماب انتخاب مسیر هاب به هاب را به منزلة پارامتر مشخص تعریف کند. گفتنـی است در مطالعة ماکور شاخص های تعریف شده در قالب هزینة مسیر، و نه به ور مستقیم، در مدب وارد شـد ند [3]. در مطالعه ای دیگر شبکة حمل ونقل هوایی مـد نظر قرار گرفت و فرودگاه ها هاب فرض شدند. سیستم صـفM/D/C در مــدب ســازی لحــا شــد و فرودگــاه هــا خدمت دهنده های سیستم در نظر گرفته شـدند . تعـدادهواپیماهایی که در این صف مـی تواننـد وجـود داشـتهباشند به صورت یک محدودیت احتمالی در نظر گرفتـهشدند. همچنین یک فرموب بنـدی برنامـه ریـزی خطـیمرکــب عــدد صــحیح معرفــی و یــک رویــة ابتکــاری )جست وجوی ممنوعه(7 به منزلـة روش حـل پیشـنهادشد [4]. در تحقیقی دیگر، زمان سـفر در مسـسلة هـابمیانه8 به صورت تصادفی فـرض شـد [5]. در پژوهشـی دیگر مسسلة مکان یابی تولید با تقاضای تصادفی در قالب مــدب تصــادفی دومرحلــه ای فرمــوب بنــدی شــد [6].
همچنین، در مطالعات صورت گرفته جهـت مواجهـه بـابحران و واکنش به آن در شبکة حمل ونقل، یـک مـدببرنام ه ری زی تص ادفی دومرحل ه ای ارائ ه ش د [7]. در پژوهشی دیگر، رویکردی مبتنی بر سناریو9 برای مسائل مکان یابی بررسی و تابع هدا به صـورت کمینـه کـردنمیانگین هزینه تعریف شد [8]. در پژوهش هـای بعـدیالگوریتمی برای مسسلة p- هاب میانـه ونـد سـناریویی ارائه شد. این الگوریتم به صورت الگـوریتم ی قطعـی بـا|S|×|I| مش تری ب ه جـای |I| مش تری مس سله را ح ل می کند [9، 10]. در مطالعه ای دیگر الگـوریت می بهینـه ، که از روش تجزیة L-Shape استفاده می کند، معرفی شد [11]. در ادامه مسسلة p- هاب مرکز تصادفی10 معرفـیو یک فرموب بندی محدودیت احتمالی جهت مدب سازی کمینه کردن زمان سفر کـل ارائـه شـد. دلیـل تصـادفیف رض ک ردن زم ان س فر ای ن ب ود ک ه مس یریابی در ولانی مدت به ور مکرر ادامه دارد و هماننـد اسـتقرارتسهیلات هاب یـک بـار صـورت نمـی پـایرد . بنـابراین ، می تواند الگـوی تلییـرات و تـابع توزیـع داشـته باشـد.همچنین مسسله، با فـرض اینکـه زمـان سـفر متلیـریتصادفی و مستقل با تابع توزیع نرمـاب اسـت، در قالـببرنامه ریزی خطی مرکب عدد صحیح فرموب بنـدی و در انتها الگوریتمی ابتکاری جهت پیداکردن جـواب شـدنیبرای فواصلی با بیش از بیست و پنج گره نیـز پیشـنهادشد [12]. در تحقیقی دیگر یـک مـدب تصـادفی بـرایمسسلة مکان یابی شبکة هاب هوایی و برنامه ریزی مسـیرهوایی، با درنظرگرفتن تقاضـ ای متلیـر فصـلی، ارائـه و مسسله در قالب یک برنامه ریزی دومرحله ای فرموب بندی شـد. تصـمیمات اسـتراتژیک مرحلـة اوب در ارتبـاط بـامکان یابی تسهیلات هاب هوایی و تصمیمات مرحلة دوم مس یریابی ش بکه ب ر اس اس تقاض ای متلی ر تعی ینمی شـود. عـدم قطعیـت در تقاضـا بـا فـاکتور تخفیـفتعریف شده روی یاب ها در نظر گرفته می شود. به عـلاوه ، مدب اجازه می دهد گره های ییر هاب به ـور مسـتقیمبه هم متصل شوند. مسسله در قالـب یـک برنامـه ریـزیخطی مرکب عدد صحیح، تحت شرایطی کـه تقاضـا بـاتوزیع گسسته شامل سه سناریوی احتمالی فرض شود، فرموب بندی شد [13]. در تحقیقی دیگر مدلی تصـادفیارائه شد که هزینة حمل را تصادفی فرض می کند. البته عاملی که باعث متلیربودن هزینه می شود فاصله است و عملاً می توان گفت فاصـله را تصـادفی فـرض مـی کنـد[14]. در مطالعه ای دیگر یک مدب احتمالی مکـان یـابیزنجیرة تأمین با ادیام ریسـک ، در حـالی کـه هزینـه و تصمیم تخصیص تحت سناریوهای گسسته است، ارائـهشد. هدا پیداکردن جوابی با کمترین متوسـو هزینـ ة کل بود؛ شامل هزینة ثابت استقرار، حمل کالا، نگهداری موجودی، و نگهـداری اخیـر ة ا مینـان. در ایـن مـدبهزینة حمل احتمالی و تحت سناریو است. در انتها یک روش آزادشدة لاگرانژ11 برای حل مـدب پیشـنهاد شـده است [15]. در مطالعات اخیر یک p- مـدب بـ ه صـورت کمینه کردن ریسک، وری که تقاضا به صورت احتمالی با تابع توزیع مشـخص فـرض شـود، توسـعه داده شـدهاست. همچنین مدب تک مرحله ای برنامـه ریـزی صـفر ویک12 قطعی معادلی با استفاده از استانداردسازی بـرایمسسله توسعه داده شـده اسـت . در انتهـا ایـن مـدب بـاالگوریتم شاخه و کران13 حل میشود [16]. در تحقیقی دیگر مسسلة مکان یابی شبکة هاب با تخصـیص یگانـه14 در حالت وجود ازدحـام در صـف بررسـی شـد . در ایـن مطالعه هزینة جابه جایی و تقاضا به صورت ییـر قطعـیفرض شده است. هزینه با دو ضابطه، که وابسته به افراد ورودی به صف است، افزایش یافته که ناشـی از میـزانورود تصادفی به صف است. افـزایش هزینـه بـا افـزایش نرخ ورود از دو ضابطه پیروی می کند که یکـی از آن هـا به صورت نمایی و دیگـری بـ ه صـورت خطـی افـزایش می یابد. با توجه به اینکه در تابع هدا هزینه به صورت تابعی از میزان ورود در نظر گرفته شده است، حل مدب با مشـکل مواجـه مـی شـود . بنـابراین ، از ترکیـب روش تجزیة بندرز و تقریب بیرونـی 15 جهـت جریمـه و حـل مدب بـرای فواصـل بـزرگ در زمـان منطقـی اسـتفادهمی شود [17]. در تحقیق دیگری مدب مکان یابی شـبک ة هاب تخصیص یگانه بـا درنظر گـرفتن سـطوح ظرفیتـی
مختل ف ب رای گ ره ه ای ه اب بررس ی ش د. جه ت کمین ه س ازی مجموع ة هزین ه ه ای ثاب ت اس تقرار و حمل ونقل، مدب در قالب برنامه ریـزی خطـی آزادشـده فرموب بندی و از برخی تکنیک هـا بـرای کـاهش حجـممدب استفاده می شود [18]. در مطالعه ای دیگر الگوریتم تجزیة بندرز برای حل مسسلة مکان یابی شبکة هـاب بـا مسافت های ولانی توسعه داده شـد [19]. در مطالعـ ة جدیدی مدب مکان یابی هاب، در حالت تخصیص یگانـه و وندگانه، با تقاضای احتمالی و وابسـته بـه سـناریو وهزینــة احتمــالی و وابســته بــه ســناریو بــا رویکــردکمینه کردن حـداکثر تأسـف هـا 16در نظـر گرفتـه شـد .
مسسله برای مقادیر فاکتورهای تخفیف مختلف بررسی و در انتها تصمیم گیرنده، با توجه بـه رونـد تلییـرات ایـن فاکتور، مدب را انتخاب می کند [20]. در تحقیقی دیگـرمسسلة مکان یابی هاب در فضای عـدم قطعیـت آمـاری، ناشی از تقاضا و هزینة جابه جایی، بررسی شـد. در ایـنپژوهش سه حالت بـرای مـدب مطـرح شـده اسـت. در حالت اوب تقاضا تصادفی و میانگین آن مشخص است. در حالت دوم هزینة جابه جایی تصادفی و ناشی از پـارامتریخاد است کـه بـا توجـه بـه ایـن موضـوع مـ یتـوان بـابه دست آوردن میانگین این پارامتر و جـای گـااری آن درروابو مسسله را حل کـرد. در حا لـت سـوم، کـه موضـوعاصلی پژوهش است، هزینة جابه جـایی وابسـته بـه هـی پارامتری نیست؛ بنابراین امکان به دسـت آوردن میـانگینبه راحتی وجود ندارد. باید ابتدا نمونه گیـری و سـنم بـراساس آن مدب حل شود .بـرای انتخـاب انـدازة نمونـه ازروش تخمین میانگین نمونه گیـری 17 اسـتفاده مـی شـود .
پم از انتخاب اندازة نمونـة مـدب، مسـسله بـا اسـتفاده ازروش تجزیة بندرز حل می شود [2]. تحقیقات دیگری نیز در ارتباط با مسائل مکان یابی، که در فضای عدم قطعیـتمدب سازی شده اند، وجود دارد )مراجعه شود به 21ـ 23(.
در جــدوب 1 خلاصــه ای از مشخصــات تحقیقــاتصورت گرفته در زمینة مسائل وندهدفه و ییر قطعی در حوزة مکان یـابی هـاب مـی آیـد و بـا مـدب پیشـنهادیمقایسه می شود.

با توجه به آنچه بیان شد، به نظر می رسد تـا کنـونمسسلة مکان یابی شبکة هاب در شـرایطی کـه هـر گـرهدارای ویژگی های ییر قطعی، ماننـد ظرفیـت و شـرا یو آب وهوایی و امنیت باشد ،بررسی نشده اسـت . در واقـع ، هدا این پژوهش راحی شبکة هاب در شرایطی است که هر گره و مسیر با توجه به ویژگی هـا ی ییـر قطعـیخاد آن امکان انتخاب به منزلة مکان استقرار هـاب رادارد.
در بخــش بعــد ی مقالــه برنامــه ریــزی تصــادفیدومرحله ای مدب می آیـد . پـم از آن روش حـل مـدبتشریح مـی شـود . در ادامـه نتـایج عـددی و در نهایـتنتیجه گیری می آید.
ف مول بند مدل توصیف م ئله
مــدب پیشــنهادی دو تــابع هــدا دارد بــه صــورتکمینه سازی مجموع هزینة ثابت استقرار تسهیلات هاب
جدول 1. تحقیق ت صو ت ا فته د زمینة مس ئل چندهدفه و غی قطعظ
رویکرد حل پارامتر غیر قطعی جنا تابع هدف نوع تابع هدف مرجع
رویکرد تصمیم گیری تعاملی18 – ك ه/ ك ز وندهدفه 1
– هزینة جابه جایی ك ه تک هدفه 3
رویة ابتکاری جست وجوی ممنوعه تعداد هواپیماهای ورودی به فرودگاه ها ك ه ’’ 4
Radial heuristic
&
Teitz–Bart heuristic زمان ك ز ’’ 12
رویکرد جواب ابتکاری تقاضا ك ه ’’ 13
روش تقریب حد ی تابع توزیع19 هزینة جابه جایی ك ه ’’ 14
روش آزادشدة لاگرانژ هزینة ثابت استقرار، جابه جایی، نگهداری
موجودی، نگهداری اخیرة ا مینان ك ه ’’ 15
روش شاخه و کران تقاضا بیشینه کردن سطح
سرویم هزینه ’’ 16
الگوریتم ترکیبی تجزیة بندرز و تقریب بیرونی هزینة جابه جایی و تقاضا ك ه ’’ 17
استفاده از تکنیک کاهش ابعاد مسسله20 – ك ه ’’ 18
الگوریتم تجزیة بندرز – ك ه ’’ 19
– تقاضا و هزینه ك ب ه ’’ 20
الگوریتم تجزیة بندرز تقاضا و هزینه جابجایی ك ه ’’ 2
الگوریتم تجزیة بندرز هزینه جابجایی و معیارهای مربوط به
نقاط استقرار تسهیلات هاب و مسیرها ك ه/ ك ر وندهدفه مدب پیشنهادی
ك ه: کمینه کردن هزینه، ك ز: کمینه کردن زمان، ك ر: کمینه کردن ریسک، ك ب ه: کمینه کردن بیشترین هزینه
و هزینة حمل ونقل و همچنـین کمینـه کـردن مجمـوعمعیارهای عدم ا مینان نقاط بالقوة هـاب و معیارهـایعدم ا مینان مسیر. گفتنی است مکان یـابی تسـهیلاتهاب با توجه به سطح سرویسی که برای میزان ریسـکهر بخش شبکه تعریف شده اسـت صـورت مـی پـایرد.
دلی ل اس تفاده از مح دودیت ه ای احتم الی، ب ه ری م پرداخت هزینة بیشتر، این است که ماهیـت مسـسله بـاریســک ارتبــاط دارد و از ــرا دیگــر جــواب هــایی مطمسن تر از دیگر حالات به دسـت مـی دهـد. در ادامـهساختار هر یک از این محدودیت ها تشریح می شود.
تع نش نه ه و پ امت ه و متغی ه
نشانه ها
i, j: شمارندة گره های بالقوة هاب؛ o: شمارندة گره های مبدأ؛ d: شمارندة گره های مقصد؛ k: شمارندة نوع کالا؛
s: شمارندة سناریو های مختلف.
مجموعهها N: کل گره ها، {N={1,…,n؛
H: گره های هاب؛ K: نوع کالاها؛ sπ: مجموعهحالات )سناریوها.( پارامتر ها
fi: هزینة قطعی استقرار تسهیل هاب در گره i؛
???????????????? ????: میزان جریان ییر قطعی کالای نوع k از مبدأ o به مقصد d تحت سناریوی s؛
ps: احتماب رخداد سناریوی ????∈???????? ???????? = 1) s∑)؛

: ریسک ییر قطعی گره هاب i تحت سناریوی s ؛
???????????????? ????: ریسک ییر قطعی مسیر مبدأ o به گره هاب i برای حمل محصوب k تحت سناریوی s؛
α: نرخ تخفیف 1(≤α≤0)؛
1ρ: ضریب شدت تابع هدا (1≤ρ1)؛
1ρ : ضریب شدت محدودیت احتمالی (ρ1≤ρz)؛
???????????????? ????: ریسک ییر قطعی مسیر گره هاب j به مقصد d برای حمل محصوب k تحت سناریوی s؛
1δ: حد بالای ریسک هر گره هاب؛
2δ: حد بالای ریسک مسیر مبدأ به هاب؛
3δ: حد بالای ریسک مسیر هاب به هاب؛
4δ: حد بالای ریسک مسیر هاب به مقصد؛
5δ: حد بالای ریسک مسیر کلی حمل؛
1β: سطح ا مینان ریسک هر گره هاب؛
2β: سطح ا مینان ریسک مسیر مبدأ به هاب؛
3β: سطح ا مینان ریسک مسیر هاب به هاب؛
4β: سطح ا مینان ریسک مسیر هاب به مقصد؛
5β: سطح ا مینان ریسک مسیر کلی حمل.
متغی ه تصمیم
متلیرهای تصمیم مرحلة اوب
zi: اگر تسهیل هاب در گره i استقرار یابد، مقـدار 1 می گیرد. در ییر این صورت مقدار 0 می گیرد.
متلیرهای تصمیم مرحلة دوم

: کسری از جریان کالای نوع k تحت سناریوی
???? که از مبدا o به مقصد d ا ز مسیر هـابi بـه هـابj مقداری مثبت به خود می گیرد 1( ≤ ???????????????????????? ???? ≤0).
???????????????? ????: اگر برای حمل کالای نوع k تحت سناریوی ???? گ ره مب دأ o ب ه گ ره ه اب i متص ل ش ود، مق دار 1 می گیرد. در ییر این صورت مقدار صفر می گیرد.
???????????????? ????: اگر برای حمل کالای نوع k تحت سناریوی ???? گره هاب i به گره هاب j متصل شود، مقدار 1 می گیرد .
در ییر این صورت مقدار 0 می گیرد.
???????????????? ????: اگر برای حمل کالای نوع k تحت سناریوی ???? گره هـابj بـه گـره مقصـدd متصـل شـود، مقـدار 1 می گیرد. در ییر این صورت مقدار صفر می گیرد.
مسائلة چندهدفااة مکاا ن ا بظ هاا ب باا د ن، ا فتن و ژاظ ه غی قطعاظ نقا ب لقوه و مسی ه
در ای ن بخ ش س اختار م دب ارائ ه م ی ش ود. م دب پیشــنهادی در قالــب یــک برنامــه ریــزی تصــادفیدومرحله ای فرموب بندی می شود. همان ـور کـه گفتـهشد ،در این نوع برنامه ریزی در مرحلة اوب تعداد و مکان تسهیلات هـاب تعیـین مـی شـود . ایـن کـار تصـمیم ی استراتژیک است که در کوتـاه مـدت تلییـر نمـی کنـد و ثاب ت ب اقی م ی مان د. گفتن ی اس ت فراین د اس تقرار تسهیلات هاب در ولانی مدت تعریف می شـود و فقـو یک بار رخ می دهد. بنابراین، تلییراتی برای هزینة ثابت استقرار تسهیلات هـاب در نظـر گرفتـه نشـده و ثابـتفرض شده است. در مرحلة دوم تصمیمات تـاکتیکی ، از جمله مسیریابی و تخصیص نقاط تقاضـا بـه تسـهیلاتهاب انتخاب شده در مرحلة اوب، صـورت مـی پـایرد . بـااستفاده از نرخ تخفیفی 1(≤α≤0)، که قبلاد تعریف شـد،می توان هزینة واحد تصادفی جابـه جـایی کـالای نـوع ???? ∈ ???? از مبدأ ???? ∈ ???? به مقصد ???? ∈ ???? با تسهیلات هاب
????, ???? ∈ ????، تحـــت ســـناریوی???? ∈ ???????? ، را بـــه صـــورت
???????????????????????? ???? = ???????????????????????? + ???????????????????????? + ???????????????????????? تعریف کـرد کـه در آن???? نرخ تخفیف مسیر مبدأ به هاب )α≤γ( و τ نرخ تخفیف مسیر هاب به مقصد )α≤τ( است. مدب با رعایت فـرضبرقراری نامساوی مثلثـی 21 تعریـف شـده اسـت. فـرضدیگر این است که در هر مسـیر حـداکثر از دو تسـهیلهاب استفاده می شود [24]. در ادامه مـدب پیشـنهادیدر قالــب یــک برنامــه ریــزی تصــادفی دومرحلــه ای فرموب بندی می شود:

)2(
-24637-158056

.
????, ???? ∈ ???? , ???? ∈ ????, ???? ∈ ???????? )3(
????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )4(
????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )5(
???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )6(
????, ???? ∈ ????, ???? ∈ ???? , ???? ∈ ???????? )7(
????, ???? ∈ ????, ???? ∈ ???? , ???? ∈ ???????? )8(
???? ∈ ????, ???? ∈ ????, ???? ∈ ???? , ???? ∈ ???????? )9(
????, ???? ∈ ???? , ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )10(
????, ???? ∈ ???? , ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )11(
????, ???? ∈ ???? , ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )12(
???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )13(
????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )14(
???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )15(
???? ∈ ????, ???? ∈ ???????? )16(
???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )17(
????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )18(
???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )19(
????, ???? ∈ ????, ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )20(
????, ???? ∈ ????, ????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ???????? )21(
)22(
رابطة 1 مربوط به تابع هدا اوب است؛ بـ ه صـورتکمینه سـازی هزینـة ثابـت اسـتقرار تسـهیلات هـاب وهزینة حمل ونقل ییرقطعـی تحـت سـناریوی sπ اسـت .
رابطة 2 تابع هدا دوم است؛ به صـورت کمینـه سـازیمتوسو ریسک نقـاط بـالقو ة اسـتقرار تسـهیلات هـاببه علاوة ریسک مسیر، کـه تحـت سـناریو تعریـف شـده است. رابطة 3 بیان می کند که برای هـر مبـدأ ???? ∈ ???? و
Subject to:
∑ ∑ ???????????????????????? ????= 1
????∈???? ????∈????
∑ ???????????????????????? ????≤ ???????? ????∈????
∑ ???????????????????????? ????≤ ????????
????∈????
???????????????? ???? ≤ ????????
???????????????? ???? ≤ ????????
???????????????? ???? ≤ ????????
???????????????? ???? ≤ ????????
???????????????????????? ????≤ ???????????????? ????
???????????????????????? ????≤ ???????????????? ????
???????????????????????? ????≤ ???????????????? ????
???????????????? ???? ≤ ∑ ∑ ???????????????????????? ????
????∈???? ????∈????
???????????????? ???? ≤ ∑ ∑ ???????????????????????? ????
????∈???? ????∈???? ???????????????? ???? ≤ ∑ ∑ ???????????????????????? ????
????∈???? ????∈????
????(????????????. ???????? ≥ ????1) ≤ ????1
????(???????????????? ????. ???????????????? ???? ≥ ????2) ≤ ????2
????(???????????????? ???? . ???????????????? ???? ≥ ????3) ≤ ????3
????(???????????????? ???? . ???????????????? ???? ≥ ????4) ≤ ????4
???? ((???????????????? ???? + ???????????????? ???? + ???????????????? ????)???????????????????????? ????≥ ????5) ≤ ????5
???????????????????????? ???? , ???????????????? ????, ???????????????? ????, ???????????????? ???? ≥ 0
???? ∈ ????|????|.
مقصد ???? ∈ ???? فقو یک مسیر وجود دارد. محدودیت هـا ی 4 تا 15 شرایو ایجاد صحیح مسیر را تضمین می کنند .محدودیت 16 تضمین می کند که ریسک هر گره هـابتح ت س ناریوی ???? ∈ ????????، ب ا احتم اب 1β-1 از مق دار 1δ بیشتر نشود. محدودیت 17 تضـمین مـی کنـد ریسـکمسیر مبدأ به هاب برای محصوب ???? ∈ ???? تحت سناریوی ???? ∈ ????????، بــا احتمــاب 2β-1، از مقــدار 2δ بیشــتر نشــود .محدودیت 18 تضمین میکند ریسک مسـیر هـاب بـههاب برای محصـوب???? ∈ ???? تحـت سـناریوی???? ∈ ???????? ، بـااحتماب 3β-1، از مقدار 3δ بیشتر نشـود. محـدودیت 19 تضمین می کند ریسـک مسـیر هـاب بـه مقصـد بـرایمحصوب ???? ∈ ???? تحت سناریوی ???? ∈ ????????، با احتماب 4β-1، از مقدار 4δ بیشتر نشود. محدودیت 20 نشان مـی دهـدریسک مسیر کلی مبدأ به مقصد محصوب ???? ∈ ???? تحـت
سناریوی ???? ∈ ????????، با احتمـاب 5β-1، از مقـدار 5δ بیشـتر نشود . محدودیتهای 21 و 22 مربوط به محدودیت های متلیر های ییر منفی و 0 یک مسسله است. گفتنی است در مــدب حاضــر نیــازی بــه تعریــف مســتقیم متلیرهــای
???????????????? ????, ???????????????? ???????????????????????????? ???? , ???????????????? ????, ???????????????? ???? به صورت متلیرهای صفر و یک نیست. زیرا ،بـا توجـه بـه مـاتریم ضـرایب تکنولوژیـک،همواره در جواب بهینة مدب 1 تا 22 متلیرهای ماکور به صورت عدد صحیح به دست می آیند.
برای حل مدب باید محدودیت های احتمـالی 16 تـا20 به صورت خطی درآینـد. اگـر تعـداد سـناریوها بـهاندازة کافی بزرگ فـرض شـوند، مـی تـوان تـابع توزیـع احتماب معیار های عـدم ا مینـان نقـاط بـالقوة هـاب ومسیر را به صورت نرمـاب فـرض کـرد. در ادامـه شـکلخطی محدودیت احتمالی 16 بیان می شود:

(√) ???? ∈ ????, ???? ∈ ???????? )23(

(
???????????????????????????? ????????: )3( ,)10( -)15(,)17( -)21(,
11176-47195

????, ???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ????)26(
∈ ????????
415137622999

???? ???? ∈ ????, ???? ∈ ????, ???? ∈ ????, ????

)28(
∈ ????????
???????????????? ???? ≤ ????̂???? ????, ???? ∈ ????, ???? ∈ ???? , ???? ∈ ???????? )29(
???????????????? ???? ≤ ????̂???? ????, ???? ∈ ????, ???? ∈ ???? , ???? ∈ ???????? )30(
???????????????? ???? ≤ ????̂???? ???? ∈ ????, ???? ∈ ????, ???? ∈ ???? , ????)31(
∈ ????????
???????????????????????? ???? , ???????????????? ????, ???????????????? ????, ???????????????? ???? ≥ 0 ????, ???? ∈ ????, ????, ???? ∈ ????, ????
∈ ????, ???? ∈ ????????
ب ه ص ورت درج ة θ2 و θ1 ب ا اس تفاده از ض رایباهمیت توابع هدا می توان تابع هـدا تجمیـع شـده را
به صورت رابطة 24 تعریف کرد:
-2463710267

)24(

در ارتباط با درجة اهمیت توابع هدا گفتنی اسـتکه این ضرایب شامل درجه اهمیت هـم مقیـاس سـازیتوابع هدا می باشند.
وش حل
با توجه به اینکه مدب این مسسله به صورت برنامه ریـزیعــدد صــحیح مرکــب اســت، و همچنــین ســاختارمحدودیت های مسسله بشکل بلوکی مـی باشـد، در ایـنبخش الگوریتم تجزیة بندرز جهت حـل مـدب اسـتفادهمی شود.
وش تجز ة بند ز
???????????????? ????, ???????????????????????? ???? , ???????????????? ????, ???????????????? ???? در فضای متلیرهای SP 22زیرمسسلة
برای هر بردار مقادیر ثابت |????̂ ∈ ????|???? به صورت روابـو 3 و
10 تا 15 و 17 تا 21 و 25 تا 31 تعریف می شود: فــرض کنیــد 17, … ,1 =???????? , ???? بــه ترتیــب مقــادیر متلیرهای مسسلة دوگان محدودیت های 3، 10 تـا 15 ،
17 تا 21 و 25 تا 31 باشـد. مـی تـوان مسـسلة دوگـان
???????????? ???? = ∑ ∑ ∑ ∑ ????1???????? ???????? − ∑ ∑ ∑ ∑ ∑ ????????????????2 ????????????̂???? − ∑ ∑ ∑ ∑ ∑ ????????????????3 ????????????̂???? − ∑ ∑ ∑ ∑ ????????????4 ????????????̂???? )32(
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????
− ∑ ∑ ∑ ∑ ????????????5 ????????????̂???? − ∑ ∑ ∑ ∑ ????????????6 ????????????̂???? − ∑ ∑ ∑ ∑ ????????????7 ????????????̂???? − ∑ ∑ ∑ ∑ ????????????14 ????????????2 − ∑ ∑ ∑ ∑ ????????????15 ????????????3
????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? − ∑ ∑ ∑ ∑ ????????16???? ????????????4 − ∑ ∑ ∑ ∑ ∑ ∑ ????????????????????17 ????????????5.
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈???? ????∈????????
0107063

Subject to:
(

(
???? ∈ ????|????|.
فرض کنید مقادیر ????̅???? متعلـق بـه مجموعـة (????(????????، نشان دهندة نقاط گوشـهای24 شـدنی مسـسلة دوگـان ومقــادیر ????̿???? متعلــق بــه مجموعــة (????(???????? نمایــانگر مجموعهشعاع های حد ی25 مسسلة دوگان باشند. مسـسلةآزادشدة اصلی بنـدرز26 (RMP) را مـی تـوان بـه صـورتروابو 14، 40 و 41 فرموب بندی کرد.
MinΩ=Zlower
Subject to: )14( حاب، بق الگوریتم تجزیة بنـدرز، جهـت محاسـبةحد پایین، مسسلة اصلی بندرز23 (MP) مـدب مـی شـود.متلیر جدید Zlower برای هزینة جابه جـایی کـل تعریـفمی شود. بدین ترتیب می توان مسسلة اصلی بنـدرز را بـهصورت روابو 14، 38 و 39 فرموب بندی کرد:
MinΩ=Zlower )38( Subject to: )14(
???????????????????????? ≥ ????1 ∑ ???????????????? + ????2 ∑ ∑ ???????????????????????????? )39(
????∈????????∈???? ????∈????????
)40( ???????????????????????? ≥ ????1 ∑ ???????????????? + ????2 ∑ ∑ ???????????????????????????? + ∑ ∑ ∑ ∑ ????̅1???????? ???????? − ∑ ∑ ∑ ∑ ∑ ????̅????????????2 ???????????????? − ∑ ∑ ∑ ∑ ∑ ????̅????????????3 ????????????????????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???? ????∈????????

− ∑ ∑ ∑ ∑ ????̅????????4 ???????????????? − ∑ ∑ ∑ ∑ ????̅????????5 ???????????????? − ∑ ∑ ∑ ∑ ????̅????????6 ???????????????? − ∑ ∑ ∑ ∑ ????̅????????7 ????????????????
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????
− ∑ ∑ ∑ ∑ ????̅14???????? ????????????2 ∑ ∑ ∑ ∑ ????̅15???????? ????????????3 − ∑ ∑ ∑ ∑ ????̅????????16 ????????????4 − ∑ ∑ ∑ ∑ ∑ ∑ ????̅17???????????????? ????????????5 . ∀????̅???? ∈ ????(????????) ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???????? ????∈???? ????∈???? ????∈???? ????∈???? ????∈???? ????∈???????? )41(
0 ≥ ∑ ∑ ∑ ∑ ????̅̅1???????? ???????? − ∑ ∑ ∑ ∑ ∑ ????̅̅????????????2 ???????????????? − ∑ ∑ ∑ ∑ ∑ ????̅̅????????????3 ???????????????? − ∑ ∑ ∑ ∑ ????̅̅????????4 ????????????????
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????
− ∑ ∑ ∑ ∑ ????̅̅????????5 ???????????????? − ∑ ∑ ∑ ∑ ????̅̅????????6 ???????????????? − ∑ ∑ ∑ ∑ ????̅̅????????7 ???????????????? − ∑ ∑ ∑ ∑ ????̅̅14???????? ????????????2 − ∑ ∑ ∑ ∑ ????̅̅????????15 ????????????3
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈????????
− ∑ ∑ ∑ ∑ ????̅̅????????16 ????????????4 − ∑ ∑ ∑ ∑ ∑ ∑ ????̅̅17???????????????? ????????????5 . ∀????̿???? ∈ ????(????????)
????∈???? ????∈???? ????∈???? ????∈????????????∈???? ????∈???? ????∈???? ????∈???? ????∈???? ????∈????????
???? ∈ ????|????|.

زیرمس سلة ف و ((DS را ب ه ص ورت رواب و 32 ت ا 37 تعریف کرد:
نمودا عملک د الگو تم تجز ة بند ز
نحوة حل مسسله و عملکرد الگوریتم بنـدرز در شـکل 1 می آید.

شکل 1. نمودا عملک د الگو تم تجز ة بند ز

نت ج عدد
در این بخش ابتـدا دو مسـسلة 1p و 2p بـا ویژگـی هـایمختلف تعریف می شود. سنم بـرای مـدب پیشـنهادیجواب مسسلة 1p برای شبکه های هاب با تعـداد 5، 10، 15، 20 گره و مسسلة 2p برای تعداد 6، 8، 10، 12 گره ب ا اس تفاده از الگ وریتم تجزی ة بن درز و ح لکنن دة پیش فرض Cplex محاسبه و با یکدیگر مقایسه می شود .
در جدوب 2 مقادیر مختلـف پارامترهـای اسـتفاده شـدهبرای مسسله های 1p و 2p مـی آیـد. مقـادیر پارامترهـا درسناریوهای مختلف به ور تصـادفی تولیـد شـده و بـه صورتی فرض شده که همة شرایو واقعی، شامل مقادیر محتمل و خوش بینانه و بدبینانه، را پوشش دهد. گفتنی است مقـادیر ریسـک شـاخص هـای مختلـف از ریـقتکنیک های تصمیم گیری وندمعیاره، بـق رابطـة 42، ادیام و میانگین و واریانم ریسک نهایی نقاط بـالقوه و مسیرهای مختلف شبکة محاسبه شد.

)42(
شاخص ???????????? ???? وزن شاخص mام ریسک گـرهi بـرایکالای نوع k ∈ K است، زمانی که برای هر گره n معیـارریس ک ف رض ش ود. در ش کل 2 نمون ة ش ماتیکی از معیارهای مختلف بـرای گـره هـای بـالقوة هـاب ، تحـتسناریو های مختلف، می آید.

گره

اب

ر

ريک

و

ی

ی

شر
آب
و

نر
با

نيت

یو

نا

n

م

و
یو

نا

وم
یو
نا

گره



قیمت: تومان


دیدگاهتان را بنویسید