نشریه تخصصی مهندسی صنایع، دوره 48، شماره 1، فروردین ماه 1393، از صفحه 109 تا 123
الگوریتم ممتیک براي طراحی شبکه هاب ظرفیت محدود با شرایط نبود
قطعیت تقاضا و اختلال

احسان نیک بخش1 و سید حسام الدین ذگردي*2
دانشجوي دکتراي مهندسی صنایع- دانشکده فنی و مهندسی- دانشگاه تربیت مدرس
دانشیار مهندسی صنایع- بخش مهندسی صنایع- دانشکده فنی و مهندسی- دانشگاه تربیت مدرس
(تاریخ دریافت 21/7/92، تاریخ دریافت روایت اصلاح شده 21/10/92، تاریخ تصویب 24/12/92 )

چکیده
مسایل مکان یابی هاب، یکی از توسعه هاي مسایل مکان یابی سنتی بوده که کاربردهاي متعددي در طراحی شبکه هاي حمل و نقل، پستی ،و مخابراتی دارند. با وجود توجه مشهود محققان به این مسایل در طی سالیان اخیر، تحقیق هاي اندکی در زمینه طراحی شـبکه هـاي هـاب بـا شرایط نبود قطعیت و اختلال انجام شده است. در این تحقیق، مسئله مکان یابی هاب با ظرفیت محدود و تخصیص یگانه با شرایط نبود قطعیت تقاضاي جریان و اختلال در ظرفیت تسهیلات، بررسی شده و ضمن پیشنهاد یک مدل ریاضی بر پایه مفهوم بودجه نبود قطعیت ، یک روش حل ترکیبی بر پایه الگوریتم ممتیک و جستجوي همسایگی متغیر ارائه شده است. نتایج محاسباتی، حاکی از دقت بالاي روش حل پیشـنهادي درحل مسایل نمونه است. همچنین، نتایج به دست آمده از آزمایش هاي شبیه سازي مونـت کـارلو بـراي بررسـی اثـر نبـود قطعیـت بـر عملکـردپیکربندي هاي مختلف شبکه هاب، نشان دهنده اهمیت در نظرگیري شرایط نبود قطعیت و اختلال در هنگام طراحی شبکه هاي هاب هستند.

واژه هاي کلیدي: مکان یابی هاب ،نبود قطعیت، اختلال، بهینه سازي استوار، الگوریتم ممتیک، جستجوي همسایگی متغیر

تسهیل هاب، نـوع خاصـی از تسـهیلات اسـت کـه بـهعنوان نقطه انتقال، سوئیچ و مرتب سـازي در سیسـتم هـايتوزیع چنـد بـه چنـد انجـام وظیفـه مـی کنـ د. بـر خـلافتسهیلات متداول در مکان یابی کـه هـر تسـهیل بـه طـور مستقیم به نقاط مبـداء -مقصـد خـدمت رسـانی مـی کنـ د ،تسهیلات هاب بـا متمرکـز کـردن جریـان بـین مبـادي ومقاصد از صـرفه هـاي اقتصـادي حمـل و نقـل انبـوه بهـرهمی جویند. مسئله مکان یابی هاب کـه بـراي اولـین بـار در دهه 1980 [1] مطرح شده است را مـی تـوان مکـان یـابیهاب و تخصیص تقاضاي نقاط شبکه به این تسهیلات هاب به نحوي دانست که ترافیک بـین نقـاط مبـداء-مقصـد بـاتوجه به یک معیار عملکرد به صورت بهینـه هـدایت شـود [2]. از جمله کاربردهاي شـبکه هـاي هـاب ، مـی تـوان بـهطراحــی شــبکه هــاي حمــل و نقــل (مســافري/بــاري در شـ بکه هـ اي هـ وایی-دریـ ایی-زمینـ ی)، پسـ ت[3] و مخابراتی/کامپیوتري اشاره کرد [4].
مقدمه Email: [email protected] ،82883394 :نویسنده مسئول: تلفن: 82883394 ، فاکس *

یکی از خصوصیات مهم شبکه هاي مبتنی بر تسهیلات هاب مانند شبکه هاي مخابراتی و حمل و نقل
هوایی-دریایی-زمینی، امکان وقوع اختلال1 در عملکرد آنها به دلایل مختلفی از قبیل خرابی تجهیزات در شبکه هاي کامپیوتري-مخابراتی و نیز نبود دسترسی به یک یال انتقال یا تسهیل هاب در شبکه هاي حمل و نقل هوایی-دریایی به دلیل شرایط بد و اختلال هاي آب و هوایی، وقوع سوانح طبیعی یا سوانح تروریستی است. همچنین، این شبکه ها همانند انواع دیگر سیستم هاي حمل و نقل در معرض نبود قطعیت2 پارامترهاي تعیین کننده خود مانند هزینه هاي ثابت، هزینه هاي حمل و نقل و تقاضا هستند. از این رو، در نظرگیري اختلال و نبود قطعیت در بهبود و حفظ سطح شبکه هاي هاب اهمیت زیادي دارد.
در ادامه مروري بر مفاهیم نبود قطعیت و اختلال و پیشینه تحقیق مرتبط در زمینه مسایل مکان یابی هاب می شود. براي آشنایی با آخرین تحقیقات در زمینه مدل هاي مکان یابی هاب به [4, 5] رجوع شود.
یکی از خصیصه هاي شبکه هاي هاب، امکان رخ دادن اختلال در عملکرد آنها است. اختلالها گروهی از انواع ریسک هستند که به صورت غیر قابل پیشبینی جریان فعالیت را در شبکه ها مانند شبکه هاي مخابراتی و زنجیره تأمین مختل میکنند. اختلال ها در شبکه هاي مخابراتی و زنجیره هاي تأمین، دلایل مختلفی دارند که از جمله می توان به اشکالات فنی ،بحران هاي اقتصادي، بلایاي طبیعی، جنگ و حملات تروریستی و اعتصاب هاي کارگري اشاره کرد[6]. پس از وقوع اختلال در یک شبکه، منابع و زمان بسیار کمی براي بازسازي و ترمیم زیرساخت هاي استراتژیک شبکه وجود دارد. با این حال بررسی ها نشان داده است که سرمایه گذاري اضافی هنگام طراحی اولیه یک شبکه می تواند منجر به عملکرد مطلوب زنجیره تأمین هنگام وقوع اختلال شود [7].
طراحی شبکه هاي کامپیوتري هاب p-تسهیلاتی با هدف بیشینه سازي پایایی کل شبکه و در نظرگیري تخصیص هاي یگانه و چندگانه براي اولین بار توسط کیم و اوکلی [8] بررسی شده است. در این تحقیق، پایایی هر مسیر در شبکه به صورت حاصلضرب ضریب پایایی یال هاي موجود روي مسیر در نظر گرفته شده است. براي مدل سازي این مسئله، دو مدل حداکثر پایایی p-تسهیلاتی و پراکندگی اجباري p-تسهیلاتی ارائه شده است. در پایان، محققان، با استفاده از نرم افزار CPLEX مدل هاي پیشنهادي را حل کرده اند. در تحقیقی دیگر، کیم [9] این مسئله را در حالتی که امکان نصب q تجهیزات تقویتی وجود داشته باشد ،بررسی و عملکرد چندین توسعه مدل پیشنهادي خود را با شرایط مختلف بررسی کرده اند. فاضل زرندي و همکاران [10] نیز مسئله مکان یابی هاب پوششی را با شرایط قطعی با در نظرگیري تسهیلات پشتیبان و پراکندگی آنها بررسی کرده و مسایل نمونه را با سناریوهاي مختلف با استفاده از نرم افزار CPLEX حل کرده اند. سرانجام ،پرورش و همکاران [11] مسئله مکان یابی هاب p -تسهیلاتی با اختلال هاي عمدي را به وسیله برنامه ریزي دو سطحی مدل کرده و مدل حاصل را با استفاده از تبرید شبیه سازي شده حل کرده اند.
خصیصه مهم دیگر شبکه هاي هاب، نبود قطعیت در پارامترهاي طراحی این شبکه ها است. به دلیل تغییرات ذاتی و گاهی شدید سیستم هاي عملیاتی، بسیاري از پارامترهاي این شبکه ها خصوصیاتی تصادفی و غیرقطعی دارند. با این حال بسیاري از مدل هاي توسعه یافته براي شبکه هاي هاب خصوصیات قطعی دارند، از این رو توسعه مدل هاي بهینه سازي با شرایط نبود قطعیت براي درنظرگیري شرایط تصادفی و غیرقطعی اهمیت بسیار زیادي دارد. با وجود توجه زیاد محققان به بهینه سازي مسایل مکان یابی هاب با شرایط ریسک با استفاده از برنامه ریزي تصادفی [12-15] و ابهام با استفاده از بهینه سازي فازي [16 -20]، توجه کمی به مدل هاي بهینه سازي استوار براي بهینه سازي بدترین حالت ممکن و همیشه موجه شده است. در یکی از این تحقیق ها، مسئله چند هدفه مکان یابی هاب استوار با شرایط نبود قطعیت تقاضا و هزینه حمل و نقل، بررسی شده و یک روش حل مبتنی بر الگوریتم ژنتیک ارائه شده است [21]. توابع هدف در نظر گرفته شده به کمینه سازي هزینه سیستم در هر یک از سناریوهاي ممکن اختصاص دارند. در تحقیقی دیگر [22]، مدل کمینه سازي، بدترین حالت ممکن براي مسئله مکان یابی هاب با هزینه هاي گشایش غیرقطعی در نظر گرفته شده و تعدادي مسایل نمونه با استفاده از نرم افزار CPLEX حل شده اند. سرانجام، ماکویی و همکاران [23] مسئله سه هدفه مکان یابی هاب p-تسهیلاتی با ظرفیت محدود را با شرایط نبود قطعیت تقاضا و زمان پردازش کالا با رویکرد بهینه سازي استوار سناریو- محور حل کرده اند. تابع هدف پیشنهادي به کمینه سازي مجموع هزینه گشایش تسهیلات و حمل و نقل، حداکثر فاصله طی شده توسط جریان هاي تقاضا و مجموع زمان پردازش کالاها در تسهیلات هاب می پردازند.
در این تحقیق، مسئله مکان یابی هاب با ظرفیت محدود با شرایط نبود قطعیت تقاضا و اختلال جزیی ظرفیت تسهیلات هاب مورد بررسی قرار می گیرد. فرض می شود مقادیر تقاضاي جریان بین گره هاي مبداء و مقصد و نیز مقدار ظرفیت تسهیلات هاب پارامترهاي غیرقطعی بازه اي باشند. مقصود از پارامتر غیرقطعی، پارامتري است که قطعی نبوده و هیچ توزیع احتمال یا تابع عضویت فازي براي نمایش آن وجود نداشته باشد. همچنین منظور از پارامتر غیرقطعی بازه اي، پارامتري غیرقطعی است که نبود قطعیت آن به وسیله یک بازه3 (به بیان دیگر، یک حداقل و یک حداکثر براي مقدار پارامتر) نمایش داده می شود. کاربرد این مسئله در طراحی شبکه هاي مخابراتی است که میزان تقاضاي جریان اطلاعات و نیز پایایی عملکرد تسهیلات هاب، پارامترهایی غیرقطعی هنگام طراحی محسوب می شوند. در این سیستم ها، منبع نبود قطعیت تقاضا نوسانات ناشی از تغییرات تقاضاي کاربران و منبعاختلال جزیی در عملکرد تسهیلات از کار افتادن تعدادي نامعین از تجهیزات مستقر در هر تسهیل هاب است. طبق مرور پیشینه تحقیق ، تا کنون این مسئله در پیشینه تحقیق مسایل مکان یابی هاب مورد بررسی قرار نگرفته است. براي مواجهه با این مسئله، یک مدل ریاضی بهینه سازي استوار بازه اي مبتنی بر بودجه نبود قطعیت و یک الگوریتم ابتکاري مبتنی بر الگوریتم ممتیک4 و جستجوي همسایگی متغیر5 ارائه می شود. نتایج محاسباتی حاکی از اهمیت و لزوم در نظرگیري اثر نبود قطعیت و اختلال هنگام طراحی شبکه هاي هاب و نیز کارآمدي روش حل پیشنهادي است.
ساختار ادامه این مقاله به شرح زیر خواهـد بـود. ابتـداتعریف مسئله تحقیق و مفروضات اصلی آن ارائه می شـوند . آنگاه، ابتدا مدل ریاضی کلی مسئله در حالت نبود قطعیت بدون در نظرگیري شـیوه نمـایش نبـود قطعیـت و سـپسشیوه عمومی ساخت مـدل همتـاي اسـتوار بـراي مسـایلبهینه سـازي بـا پارامترهـاي غیرقطعـی بـازه اي بـا شـرایطمحدود بودن تعـداد پارامترهـاي غیرقطعـی نوسـان کننـدهتشریح می شوند. در ادامه، شـیوه حـل مسـئله تحقیـق بـااستفاده از یک روش حـل م بتنـی بـر الگـوریتم ممتیـک وجستجوي همسایگی متغیر ارائه می شود. در بخـش نتـایجمحاس باتی، ت أثیر نب ود قطعی ت و اخ تلال ب ر عملک رد شبکه هاي هاب و کـارآ یی روش حـل پیشـنهادي، بررسـیمی شود. سرانجام، در بخش پایانی از تحقیق نتیجـه گیـريلازم به عمل آمـده و زمینـه هـاي تحقیقـاتی بعـد ي ذکـرمی شوند.

تعریف مسئله
در این تحقیق ، مسئله طراحی یک شبکه هاب با ظرفیت محدود با شرایط نبود قطعیت تقاضا و اختلال ظرفیت تسهیلات هاب بررسی می شود. در این شبکه ،کالاي مرتبط با تقاضاي حمل و نقل بین هر جفت مبداء و مقصد، ابتدا از مبداء جمع آوري شده و به هاب اول فرستاده می شود. پس از انجام عملیات هاي مرتبط مانند مرتب سازي و تجمیع در تسهیل هاب اول، کالاهاي تجمیع شده از مبادي مختلف براي مقاصد مختلف به تسهیل هاب دوم فرستاده می شوند. سرانجام ،همه کالاهاي ارسالی به مقصد مد نظر، در هاب دوم تجمیع شده و به آن مقصد ارسال می شوند.
در این تحقیق ، فرض می شود فضاي جواب، گسسته و محدود بوده و می توان آن را به وسیله یک گراف کامل شامل گره هاي مبداء و مقصد و یال هاي متصل کننده گره ها به یکدیگر نمایش داد. در گراف فضاي جواب ،همه تسهیلات هاب به یکدیگر متصل بوده و هر نقطه مبداء (مقصد) به طور دقیق به یک تسهیل هاب متصل است
(تخصیص یگانه). همچنین، در گراف فضاي جواب هیچ دو گره غیر هابی به طور مستقیم به یکدیگر وصل نیستند (یعنی حمل و نقل بین دو نقطه غیر هاب فقط از طریق گذر از یک یا دو تسهیل هاب امکان پذیر است).
ظرفیت هر تسهیل هاب مقداري معین و محدود است و تحت تأثیر رخ دادن پیشامد اختلال است. فرض می شود اثر اختلال روي عملکرد تسهیلات، ماهیت اختلال کامل و قطعی نداشته و فقط درصدي از ظرفیت هر تسهیل را از کار می اندازد. به این ترتیب، اثر رخ دادن اختلال بر ظرفیت تسهیل هاب مستقر در مکان بالقوه تسهیل هاب kام ،ak، به صورت پارامتري غیرقطعی بازه اي بین صفر و حد بالاي اثر اختلال ،aˆk، در تسهیل هاب kام در خواهد آمد. مقدار ak نشان دهنده درصد ظرفیت از دست رفته تسهیل هاب kام است. همچنین ، مقدار تقاضاي حمل و نقل بین هر دو نقطه مبداء و مقصد، مقداري غیرقطعی مانند hij و متعلق به بازه h h h hij  ˆij, ij  ˆij  باشد. سرانجام، حداکثر تعداد پارامترهاي غیرقطعی متعلق به تابع هدف و محدودیت ها که نوسان می کنند (بودجه نبود قطعیت) مقادیري مشخص و از پیش تعیین شده توسط تصمیم گیرنده هستند. هدف سیستم کمینه سازي مجموع هزینه گشایش تسهیلات و هزینه هاي حمل و نقل با شرایط ذکرشده است.

مدل سازي ریاضی
در این بخش، مدل ریاضی مسئله مکان یابی هاب با ظرفیت محدود با شرایط نبود قطعیت تقاضا و اختلال ارائه می شود. بنابراین در این بخش به ترتیب، نمادهاي مورد نیاز براي ایجاد مدل ریاضی ، مدل ریاضی مسئله در حالت نبود قطعیت و اختلال و شیوه ایجاد همتاي استوار مدل پیشنهادي ارائه می شوند.
نمادگذاري
نمادهاي مورد استفاده براي نمایش پارامترها و متغیرها تصمیم مدل ریاضی پیشنهادي عبارتند از:
I: مجموعه نقاط مبداء و مقصد K: مجموعــه مکــان بــالقوه تســهیلات هــاب (زیــر مجموعه اي از مجموعه نقاط مبداء و مقصد،I )
f k: هزینه گشایش تسهیل هاب در مکان بـالقوهk ام ،
k K
k: ظرفیت تسهیل هاب مستقر در مکان بـالقوهk ام ،
k K
ak: پارامتر غیرقطعـی بـازه اي میـزان درصـد کـاهشظرفیت تسهیل هـاب مسـتقر در مکـان بـالقوهk ام در صورت رخ دادن اختلال در آن تسهیل، k K
hij: پارامتر غیرقطعـی بـازه اي تقاضـاي جریـان بـینمبداء iام و مقصد jام ،i j, I d ik: مسافت بین گره iام و گره kام ،i k,  I Cik: هزین ه حم ل و نق ل ب ین گ ره iام و گ ره kام ،
i k,  I
: ضریب صرفه اقتصادي حمـل و نقـل از یـک گـرهمبداء به یک تسهیل هاب
: ضریب صرفه اقتصادي حمل و نقل بین دو هاب
: ضریب صرفه اقتصادي حمل و نقل از یک تسـهیلهاب به یک گره مبداء Zik: متغیر صفر و یک نبـود تخصـیص یـا تخصـیصتقاضاي جریان آغـاز شـده گـرهi ام بـه تسـهیل هـابمستقر در مکان بالقوه kام ،i I & k K
Yijkm: متغیر صفر و یک انتقال یا عدم انتقـال جریـانبین مبداء iام و مقصد jام از طریق هابهاي مستقر در
i j,  I & k m,  K، امm ام وk مکان هاي

مدل ریاضی
با توجه به توضیحات ارائه شده در بخش تعریف مسئله ،مدل ریاضی 4-اندیسی مسئله مکان یابی هاب با ظرفیت محدود و تخصیص یگانه با شرایط نبود قطیت تقاضا و اختلال به صورت زیر خواهد بود:

Minimize  f Zk kk 
k K
hij   Cik  Ckm  C Ymj  ijkm (1)
i I   j I k K m K مقید به محدودیت هاي:

Yijkm 1
k K m K   i j,I (2)
Zik  Zkk   iI & kK (3)
Yijkm Zik m K   i j,I & kK (4)
Yijkm Z jm
k K    i j,I & m K (5)
hYijijkm  (1 ak )kWk  kK (6)
m K i j I , 
Zik 0,1  iI & kK
Yijkm 0,1    i j,I& k m K,

6922773932938

در این مدل، تابع هدف (1) سعی در کمینه سازي مجموع هزینه گشایش تسهیلات و هزینه حمل و نقل دارد. محدودیت (2) باعث تخصیص جریان تقاضاي بین یک جفت مبداء و مقصد به طور دقیق به یک یا دو تسهیل هاب می شود. محدودیت (3) تضمین می کند تقاضاي یک گره غیره هاب فقط در صورتی می تواند به یک گره هاب تخصیص یابد که که آن گره هاب انتخاب شده باشد (دقت کنید تخصیص تقاضاي یک گره به خودش معادل است با انتخاب آن گره به عنوان هاب). محدودیت هاي (4) و (5) باعث می شوند مقدار متغیر جریان تقاضاي بین یک جفت مبداء و مقصد گذرنده از دو تسهیل هاب مستقر در دو مکان بالقوه وابسته به تخصیص گره هاي مبداء و مقصد به تسهیل هاي هاب متناظر با مسیر باشد. محدودیت (6) ضمن کنترل سقف میزان جریان ورودي به یک تسهیل هاب، اثر اختلال بر میزان ظرفیت آن تسهیل را اعمال می کند. سرانجام ،محدودیت هاي (7) و (8) نوع متغیرهاي تصمیم را بیان میکنند. این مدل داراي K 1 I 2 K  متغیر تصمیم و نیز I 2 K I 2 K محدودیت کارکردي است. لازم به ذکر است براي به دست آوردن مدل همتاي استوار این مدل، می توان به سادگی از مدل هاي مختلف موجود در پیشینه تحقیق بهینه سازي استوار همچون مدل نبود قطعیت بدترین حالت ممکن [24]، نبود قطعیت بیضوي [25]، و نبود قطعیت بودجه اي [26] استفاده کرد. دربخش بعدي، شیوه به دست آوردن همتاي استوار مدل ریاضی (6-1) بر پایه مفهوم بودجه نبود قطعیت پیشنهادي برتسیماس و سیم [26] تشریح می شود.

شیوه ایجاد مدل همتاي استوار
در این بخش شیوه ایجاد مدل همتاي استوار بر مبناي یک مدل بهینه سازي استوار ارائه می شود. بهینه سازي استوار روشی در تحقیق در عملیات براي برخورد با شرایطی است که اطلاعات تاریخی کافی براي برازش توزیع احتمال پارامترهاي غیرقطعی مسئله وجود ندارد. در چنین شرایطی ،اغلب فقط یک حد پایین و بالا براي توصیف همه حالت هاي ممکن تحقق پارامترهاي غیرقطعی وجود دارد. هدف از مدل هاي بهینه سازي استوار در مواجهه با ضرایب تابع هدف غیرقطعی، تلاش براي پیدا کردن بهترین راه حلی است که حساس به تغییرات پارامترهاي غیرقطعی در تابع هدف نباشد. از طرف دیگر ،در صورت وجود ضرایب غیرقطعی در ماتریس فناوري و بردار ضرایب سمت راست، مدل بهینه سازي استوار سعی در به دست آوردن راه حلی همیشه موجه براي همه حالت هاي تحقق ممکن براي پارامترهاي غیرقطعی دارد.
حال مسئله برنامه ریزي خطی زیر را با پارامترهاي غیرقطعی در تابع هدف، ماتریس فناوري و بردار سمت راست در نظر بگیرید:
min c xT
مقید به محدودیت هاي:
Ax b xRn (11)

به دنبال شیوه نمادگذاري برتسیماس و سیم [26]، اگر یک پارامتر غیرقطعی ماتریس فناوري ،aij، با یک مقدار اسمی ،aij، و یک مقدار انتقال ،aˆij، مرتبط باشد ،آنگاه پارامتر غیرقطعی aij را میتوان به وسیله بازه aij  a ,aˆij ij  aˆij  نمایش داد. رویکرد بهینه سازي استوار مبتنی بر بودجه نبود قطعیت که توسط برتسیماس و سیم [26] پیشنهاد شده است، سعی می کند حداکثر تعداد پارامترهاي غیرقطعی را که می توانند از مقدار اسمی خود انحراف یابند، به مقداري مانند Γ محدود کند. به بیانی ساده، مفهوم بودجه نبود قطعیت آن است که احتمال انحراف یافتن بیش از Γ پارامتر قطعی از مقدار اسمی متناظر آن، مقدار بسیار کم و در حد صفر محسوب می شود. مقدار بودجه نبود قطعیت که توسط تصمیم گیرنده و صاحب مسئله تعیین می شود ،به میزان محافظه کار بودن آنها بستگی دارد و هر چه مقدار آن بزرگ تر باشد، مدل قطعی همتاي استوار حاصل به رویکرد اول نزدیک تر می شود. با در نظرگیري توضیحات ذکرشده، در نظرگیري Γi به عنوان پارامتري عدد صحیح ،و سرانجام تعریف Ji به عنوان مجموعه پارامترهاي غیرقطعی سطر iام ماتریس فناوري، مدل قطعی همتاي استوار مسئله (11-9) به صورت زیر قابل ایجاد خواهد بود
:[26]
min c xT (12)
مقید به محدودیت هاي:
971360101131

a xijj S |Sii maxJ ,Sii ia yˆijj bi i (13)
j j S i  xj  y j j (14)
x ,yjj Rn j (15)

هر چند محدودیت (13) غیر خطی است ،ولی می توان آن را به سادگی با استفاده از گزاره پیشنهادي در [26] خطی کرد. بنابراین، این مسئله می تواند به سادگی با استفاده از روش سیمپلکس حل شود. همچنین، این مدل همتاي استوار می تواند درون مدل هاي برنامه ریزي عدد صحیح و مختلط گنجانیده شود. در نهایت، شایان ذکر است همراه با میل کردن Γ به سمت صفر، محافظه کاري مدل کمتر می شود و مدل بهینه سازي شبیه به مدل قطعی اسمی می شود. از سوي دیگر ،همراه با میل کردن Γ به سمت حداکثر تعداد پارامترهاي غیرقطعی، مدل همتاي استوار شبیه به مدل محافظه کارانه بدترین حالت ممکن می شود.

روش حل پیشنهادي
در این بخش، یک روش حل ترکیبی مبتنی بر الگوریتم ممتیک و جستجوي همسایگی متغیر به عنوان روش جستجوي محلی الگوریتم ممتیک براي حل مسئله تحقیق ارائه می شود. در ادامه توضیحاتی در مورد روش حل پیشنهادي ارائه می شود.
الگوریتم ممتیک، یک الگوریتم مبتنی بر جمعیتاست که براي مسایل بهینه سازي پیچیده و بزرگ مورد استفاده قرار میگیرد. ایده اصلی این الگوریتم، به کارگیري یک روش جستجوي محلی در درون ساختار الگوریتم ژنتیک براي بهبود کارآیی فرایند تشدید6 هنگام جستجو است [27]. جستجوي محلی به کارگرفته شده در الگوریتم ممتیک، می تواند ضعف روش هاي تکاملی همچون الگوریتم ژنتیک را در تشدید فرایند جستجو رفع کند[28]. الگوریتم ممتیک در ابتدا مجموعهاي از جواب هاي اولیه را رمزگذاري می کند . آنگاه این الگوریتم میزان مطلوبیت هر یک از جواب ها را بر اساس یک تابع برازندگی محاسبه کرده و با استفاده از عملگرهایی چون تقاطع و جهش، جواب هاي جدیدي را تولید می کند. در پایان، هر نسل روي مجموعه اي از جواب هاي آن نسل، یک جستجوي محلی با هدف تشدید فرایند جستجو انجام می شود تا کیفیت جواب هاي بهینه محلی افزایش یابد. سپس زیر مجموعه اي از نسل فعلی (مجموعه جواب هاي فعلی ، والدین و جواب هاي جدید، فرزندان) بر اساس مفهوم تنازع براي بقا به نسل بعد منتقل می شوند. فرآیند تولید نسل هاي جدید تا زمان برقرار شدن شرایط توقف ادامه مییابد. نماي کلی الگوریتم ممتیک پیشنهادي در شکل 1 آمده است.
با توجه به ساختار سلسله مراتبی تصمیم هاي مسئله و وابستگی سطح دوم (تخصیص) به سطح اول (مکان یابی)، اعمال فقط علمگر تقاطع روي آرایه هاي تخصیص نمی تواند کافی باشد. دلیل این موضوع آن است که با توجه به نیاز به تعمیر آرایه تخصیص پس از اعمال عملگر تقاطع، احتمال همگرایی آرایه تخصیص به حالت بهینه پایین خواهد بود. بنابراین، اضافه کردن یک روش جستجوي محلی که بتواند آرایه تخصیص را بهبود بدهد ،می تواند کارآیی الگوریتم پیشنهادي را افزایش دهد. در این تحقیق، براي انجام جستجوي محلی در الگوریتم ممتیک پیشنهادي از روش جستجوي همسایگی متغیر
[29] استفاده می شود.
ایـ ن روش کـ ه بـ ر مبنـ اي تغییـ ر سیسـ تماتیک همسایگی ها هنگام جستجو بنا شده است، سـعی مـی کنـد هنگام برخورد با جـواب هـاي بهینـه محلـی بـا اسـتفاده ازتغییر همسایگی، امکان فرار از جـواب بهینـه محلـی را بـهوجود آورد. هر الگوریتم جستجوي همسـایگی متغیـر سـهمرحله اصلی لرزش7، جسـتجوي محلـی8، و حرکـت 9 دارد (شکل 2). در مرحله لرزش، بر اساس همسایگی فعلی یـکجواب جدید از جواب در دست ایجاد مـی شـود . در مرحلـهجستجوي محلی، سعی می شود جـواب بـه دسـت آمـده ازمرحله لرزش، تا حد ممکن بهبود داده شود. اگر مقدار تابع هدف جواب نهایی مرحله جستجوي محلی از مقـدار تـابعهدف جواب در دست (اولیه) بهتر بود، روش به همسـایگیاول بازگشته و این فرایند را از ابتدا آغاز می کنـد . چنانچـهبهبود در مقدار تابع هدف رخ ندهد، روش همسایگی بعدي را انتخاب کـر ده و فراینـد را تکـرار مـی کنـد . در الگـوریتمجستجوي همسایگی متغیر مورد استفاده در ایـن تحقیـق،از روش opt-3 ب ه عن وان روش جس تجوي محل ی و از دو روش تعــویض مجــاور وopt -2 بــه عنــوان ســاختارهايهمسایگی استفاده شده است. نماي کلـی فرای نـد اسـتفادهشده در این تحقیق، بر مبنـاي ایـن الگـوریتم در شـکل 2 آمده است.
جزئیات بقیه اجزاي روش حل پیشنهادي بدین ترتیب است:

نمایش جواب: مطابق [30]، هر کروموزوم (جواب ) از دو آرایه هاب و آرایه تخصیص، هر یک با اندازه تعداد گره هاي شبکه تشکیل شده است. آرایه صفر و یک هاب، بیانگر انتخاب یا انتخاب نکردن هر یک از گره هاي شبکه به عنوان تسهیل هاب است. همچنین آرایه عدد صحیح تخصیص، نشان دهنده چگونگی تخصیص گرههاي غیرهاب به تسهیلات هاب است. براي مثال اگر گره غیر هاب i به گره هاب k تخصیص یابد (مقدار گره هاي i و k در آرایه هاب به ترتیب برابر صفر و یک است)، درایه متناظر در آرایه تخصیص، مقدار k را اختیار میکند.

1412557269942

31432519878

تشکیل جمعیت اولیه: در این تحقیق، تعـداد تسـهیلاتهاب براي 13 اعضـاي جمعیـت اولیـه بـه طـور تصـادفیمقداري در بازه 1,…,n6 انتخـاب مـی شـوند . بـراي 13 بعدي اعضاي جمعیت اولیه، تعداد تسهیلات هاب به طـورتصادفی از بازه n6,…,n4 انتخاب مـ ی شـوند . سـرانجامبراي باقیمانده اعضاي جمیت اولیه، تعداد تسـهیلات هـاب از بازه n4,…,n2 به طور تصادفی انتخاب میشود. انتخاب والدین: براي تولید فرزندان جدید از جمعیتفعلی، والدین توسط روش تورنمنت انتخاب می شوند.
عملگر تقاطع: در روش پیشنهادي از عملگر تقاطع دو نقطه اي براي هر دو آرایه هاب و تخصیص استفاده می شود. عملگر تقاطع بر هر کروموزم با احتمال pc اجرا می شود. پس از اجراي عملگر تقاطع، چنانچه آرایه تخصیص با آرایه هاب منطبق نباشد (تخصیص گره غیر هاب به گره غیر هاب)، موارد نبود انطباق بر اساس تخصیص گره هاي غیر هاب به نزدیک ترین هاب رفع می شوند.

عملگر جهش: در روش پیشـنهادي، هـر یـک از ژن هـايمربوط به آرایه هاب با احتمـالpc – 1 انتخـاب شـده و بـهطور تصادفی یکی از ژن ها دچار جهـش (تبـدیل صـفر بـهیک و تبدیل یک به صفر) می شود.

تابع ارزیابی: تـابع ارزیـابی در روش پیشـنهادي، همـانمقدار تابع هدف مسئله اسـت . بـا ایـن حـال، از آنجـا کـهممکن است تعدادي از جواب ها نتواننـد شـرط محـدودیتظرفیت را برآورده کنند (غیر موجه باشند)، جواب هاي غیر موجه با مقداري بزرگ، ماننـدBP ، جریمـه مـی شـوند . در اینجا ،BP چهار برابر مقدار تـابع هـدف مسـئله در حالـتقطعی قرار داده شده است. لازم به ذکر است با توجه به در نظرگرفتن نبود قطعیت پارامتر تقاضـا و اخـتلال در قالـبیک مدل بهینه سازي استوار، ارزیابی تابع هـدف بـراي هـرجواب یافت شده (شامل آرایه هاي هاب و تخصیص) توسط نرم افزار GAMS/CPLEX انجام می شود.

جستجوي محلی: در روش پیشنهادي، در پایان هر نسل ،روي آرایه تخصیص بهترین جواب جمعیت فعلی، الگوریتم جستجوي همسـایگی متغیـر اعمـال مـی شـود . همچنـینچنانچه براي NI نسل متوالی، بهتـرین مقـدار تـابع هـدفبهبود نیابـد،NI % اعضـاي نسـل فعلـی بـه طـور تصـادفیانتخاب شده و الگوریتم جستجوي همسـایگی متغیـر رويهـ ر دو آرایـ ه هـ اب و تخصـ یص انجـ ام مـ ی شـ ود.

شکل 1: نماي کلی الگوریتم ممتیک پیشنهادي

جستجوي همسایگی متغیر:
انتخاب یک جواب اولیه مانند x تکرار کنید{
i ← 1
تکرار کنید{
یک جواب از همسایگی iام جواب فعلی، مانند x، را انتخاب کنیـ د.
 لرزش
یک روش جستجوي محلی را روي x بـه کـار گرفتـه و جـواب بـه
دست آمده را x بنامید.  جستجوي محلی
تفاوت مقدار تابع هدف جواب فعلی و جواب جدیـد را محاسـبه کنیـ د
(F∆). اگر 0 ≥ F∆{
جواب جدید را بپذیرید.  حرکت
1 ← i  بازگشت به همسایگی اول }
در غیر این صورت{ 1 + i ← i  رد جواب به دست آمده و رفتن به همسایگی بعدي}
}(تا هنگامیکه i ≤ I)
}(تا هنگامیکه شرط توقف برآورده شود)
شکل 2: نماي کلی الگوریتم جستجوي همسایگی متغیر

نتایج محاسباتی
در این بخش، نتایج مجموعه اي از آزمایش هاي محاسباتی براي سنجش کارآیی روش حل پیشنهادي و به دست آوردن درك عمیق تري از اثر نبود قطعیت پارامتر تقاضا و اختلال بر عملکرد شبکه هاب ارائه می شود. به این منظور مسایل نمونه استاندارد AP در ابعاد 10، 20، 25، 40، 50، و 100 گره انتخاب شده اند. مقدار انتقال پارامترهاي غیرقطعی تقاضا و اختلال در ظرفیت به طور تصادفی یکنواخت در سه بازه (20 -10%)، (30-20%)، و (50-30%) تولید شده اند. همچنین مقدار بودجه نبود قطعیت برابر مقادیر 0، 1%، 10%، 20%، 50%، و 100% تعداد کل پارامترهاي غیرقطعی در نظر گرفته شده است.
1116902133329

بهترین مقدار به دست آمده در جدول (1) گزارش شده  1in1 i2
150685-11683

S N  10 log  y  (16)
n
پارامترهاي روش حل پیشنهادي توسط روش تاگوچی تنظیم شده اند. همچنین این روش در زبان برنامه نویسی C# پیاده سازي شده و روي یک کامپیوتر با پردازنده 2 گیگاهرتزي و یک گیگابایت حافظه اجرا شده است. الگوریتم پیشنهادي براي هر مسئله 10 بار تکرار شده و است. براي اعتبارسنجی روش پیشنهادي، از نرم افزار بهینه سازي GAMS/CPLEX نسخه 5/12 روي یک کامپیوتر تحت لینوکس با یک هسته 2/3 گیگاهرتزي و 24 گیگابایت حافظه استفاده شده است. به نرم افزار براي حل هر یک از مدل ها، حداکثر 24 ساعت وقت داده شده است.

تنظیم پارامترهاي روش حل پیشنهادي
از عوامل مهم و تأثیرگذار بر عملکرد روش هاي فراابتکاري، می توان به تنظیم دقیق پارامترهاي این روش ها اشاره کرد. در این تحقیق، براي افزایش کارآیی روش حل پیشنهادي، از روش آماري تاگوچی [31] استفاده می شود. در این روش، از معیار سیگنال به نویز10 (S/N) براي اندازه گیري میزان تغییرات متغیر پاسخ استفاده می شود. با توجه به جهت کمینه سازي تابع هدف در این تحقیق، از رابطه (17) مبتنی بر اصل نسبت کوچک تر نسبت بهتر استفاده می شود.
مطابق با روش حل پیشنهادي، اسامی و سطوحپارامترهایی که براي تنظیم کردن در نظر گرفته شده اند، در جدول (1) آمده اند. با توجه به تعداد پارامترها و تعداد سطوح آنها، آرایه متعامد 27L براي انجام آزمایش هاي لازم انتخاب می شود.

جدول 1: سطوح پارامترهاي روش حل پیشنهادي سطح

پارامتر

پارامتر



قیمت: تومان


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