نشریه تخصصی مهندسی صنایع، دوره 49، شماره 1، بهار و تابستان 1394، از صفحه 129 تا 137
مدل‌سازی‌ریاضی‌جدید‌برای‌مسئلة‌مکان‌یابی‌تسهیلات‌و‌مسیریابی‌وسائط‌نقلیه‌و‌حل‌آن‌با‌الگوریتم‌رقابت‌استعماری‌تلفیقی ‌
نرگس‌نوروزی1،‌رضا‌توكلی‌مقدم2*،‌محسن‌صادق ‌عمل‌‌نیک3،‌صادق‌خائفی4 ‌
دانشجوی دکتری مهندسی صنایع پردیس دانشکده های فنی دانشگاه تهران
استاد دانشکدة مهندسی صنایع پردیس دانشکده های فنی دانشگاه تهران
دانشیار دانشکدة مهندسی صنایع پردیس دانشکده های فنی دانشگاه تهران
دانشجوی کارشناسی ارشد دانشکدة مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران
)تاریخ دریافت 24/3/93 – تاریخ دریافت روایت اصلاح شده 19/10/93 – تاریخ تصویب 28/10/93( چکیده ‌
یکی از اهداف سیستم های یکپارچة لجستیکی، که به مثابة یك فلسفة مدیریتی جدید طی چند دهة گذشته پدید آمده، افزایش کاارایی توزیاعمحصولات است. این نوع مسائل معمولاً در دو بخش بررسی می شوند؛ مکان یابی تسهیلات برای سیاست های بلندمدت و مسیریابی وسائط نقلیاهبرای پاسخگویی بیشتر به تقاضای مشتریان در تصمیم های عملیاتی. این دو جزء به صورت جداگانه قابل حل است؛ اما این حل ممکن اسات باهجواب بهینة مسئلة اصلی منجر نشود و برای هر زیرمسئله جواب بهینه پیدا کند .این تحقیا ، باه تعیاین همزماان مسا ائل مکاان تساهیلات ومسیریابی وسائط نقلیه برای بازدید از تسهیلات مورد نظر، که باید سرویس دهی شوند، می پردازد. از آنجا که مسئلة مورد بررسای از ناوع مساائل NP-Hard است، به منظور حل آن در ابعاد بزرگ از الگوریتم رقابت اساتعماری تلفیقای اساتفاده مای شاود. بارای نشاان دادن کاارایی الگاوریتمپیشنهادی تعدادی از مسائل در ابعاد کوچك و بزرگ با این الگوریتم و روش حل دقی به کمك نرم افزار CPLEX حل می شود. مقایسا ة ایان دوروش نشان دهندة کارایی الگوریتم پیشنهادی است. در پایان نتیجه گیری ارائه می شود.
كلیدواژگان:‌الگوریتم رقابت استعماری تلفیقی ،مسیریابی وسائط نقلیه ،مکان یابی تسهیلات.
مقدمه ‌
(VRP)، که مسیر هر وسیله را از انتار یا دپو به تساهیلاتیکه باید سرویس دهی شوند مشخ می کند، بررسای شاد. یوچنور و دمیرال] 3[ نیز یك الگوریتم خوشه زنی بار پایا ة الگوریتم ژنتیك برای حل یاك مسائل ة VRP هماراه چنادانتار ارائه دادناد و کاارایی ایان الگاوریتم را بارای مساائلمختلف بررسی کردند. نتایج نشان دهندة زماان محاساتاتیپایین همراه با کیفیت بالاست.
مقالة بالداچی و همکاران او ]4[ حاوی مرور و مقایسا ة جااامع الگااوریتم هااای دقیاا توسااعه داده شااده در حاال مسئلة VRP با پنجرة زمانی است که می تواند به منزلة یك منتع مناسب برای مطالعات این الگوریتم ها در نظر گرفتاهشود. برای حالات چندهدفا ة مسا ئلة VRP هماراه پنجار ة زمانی، که کمتر به اهمیت این موضوع پرداخته شده، ناجرا و بولیناریا] 5[ یك الگوریتم تکاملی چندهدفة کارا بر پایا ة مقایسة شتاهت میان جواب ها برای حل ایان مسائله ارائاهدادند. کریتیکوس و یونانو] 6[ یك مسا ئلة VRPTW را در طراحی یك سیستم مناسب تدارکات، باا توجاه باه ساهمشایان توجه هزینه های توزیع نساتت باه کال هزیناه هاایزنجیرة تأمین، یکای از موضاوعات بسایار مهام در دنیاایرقابتی امروز است. از لحاا طراحای و ادارة سیساتم هاای لجستیکی، مکان یابی تسهیلات مسئله ای مشترك است که مدیران لجستیك با آن مواجه اند. چنین مفهومی وابساتگیبین مکان یاابی تساهیلات )مراکاز پشاتیتانی( و تخصای مشتریان به تسهیلات و نیز ساختار مسیریابی وسائط نقلیه را تعیین می کناد. ایان ناوع مساائل معماولاً در دو بخاشبررسی می شوند؛ مکان یابی تساهیلات بارای سیاسات هاایبلندمدت و مسیریابی وسائط نقلیه برای پاسخگویی بیشاتربه تقاضای مشتریان در تصمیم های عملیاتی. ایان دو جاز ء به صورت جداگانه قابل حل اند؛ اما این حل ممکن است باهجواب بهینة مسئلة اصلی منجر نشود و برای هر زیرمسا ئله جواب بهینه پیدا کند .از این رو، در این تحقی مکان یاابیتسااهیلات (FLP) 1و مساائلة مساایریابی وسااائط نقلیااه 2
Email : [email protected] 02188013102 :نویسنده مسئول تلفن: 02182084183، فکس *
نظر گرفته اناد کاه دارای دو وییگای منحصاربه فارد اسات:خودروها دارای ظرفیت های متفاوت اند و همچناین امکاانبارگیری اضاافه بارای هار خاودرو وجاود دارد. ساپس بااتخصی یك مقدار جریمه برای هر اضافه بار هزینة نهااییبه کمك یك الگوریتم ابتکاری کمینه می شود.
میراب ی و همک اران او ]7[ رویک رد ترکیت ی ابتک اری تصادفی کارآمدی را برای حل مسئلة VRP باا چناد انتاارارائه کردند. هدف این تحقی کمینه کردن زماان بازگشاتماشین ها به انتار با ود. رویکارد ارائاه شاده در ایان تحقیا ترکیتی از روش های توسعه یافتة قطعی و تصادفی و رویکرد شتیه سازی تترید3 SA است. آن هاا نتاایج ایان رویکارد رابهترین رویکرد شناخته شده معرفی کردند.
روان و همکاران او ]8[ راه حلی ترکیتای بارای مسا ئلة VRP ظرفیت دار با محدودیت های بارگذاری سه بعدی ارائاهکردند. هدف این راه حل کمینه کردن هزینة حمل ونقال درزما ان سا رویس دادن با ه مشا تری با ود. رویکردها ای استفاده شده ، که ترکیتی از الگوریتم زنتاور عسال و شاشالگوریتم ابتکاری بارگذاری بود، در همة آزمون هاا بهتارینجواب را برای سناریوهای مختلاف باه دسات آورد. فاضالزرندی و همکاران او ]9[ در زمینة مسائل تعیین تسهیلات در شرایط پنجار ة زماانی و عادم قطعیات تحقیا کردناد.
تقاضای مشتری و زمان سفر در پیوهش ایشان متغیرهاایفازی در نظر گرفته شدند. برای حال ایان مسا ئله از مادلفازی برنامه نویسی محدودشدة شانس (CCP) 4و ترکیتی از الگوریتم فراابتکاری شاتیه ساازی تتریاد و همچناین روشابتکاری الگوریتم خوشه بندی c میانگین (FCM) 5 استفاده شد. نتایج اجرای رویکردها بیانگر مؤثربودن آن ها بود.
ژو و همکاران او ]10[ یك مادل ریاضای و روش حالکارا برای مسئلة تخصی دومعیاری در حالت چنادانتاریبا ظرفیت های مختلف ارائه کردند. در روش حل، الگاوریتمژنتیك به کار رفت که به منظور یافتن جاواب هاای بهیناةپ ارتو ب رای دوره ه ای زم انی کوت اه م دت طراح ی ش د.
همچنااین اسااکوبار و همکاااران او ]11[ یااك الگااوریتمدومرحله ای ترکیتی برای حل مسئلة مسایریابی تساهیلاتارائه کردند.
تعریف‌مسئله ‌
طراحی و تحلیل شتکة تأمین یکی از مساائل بسایار مهام در زنجیرة تأمین چندسطحی است. در سال های اخیر دو مسا ئلة اصلی در طراحی شتکه هاای تا أمین، مکاان یاابی تساهیلات و مسیریابی وسایل نقلیة همزمان، در نظار گرفتاه شاده و مادلمکان یابی تسهیلات و مسیریابی تاو أم آن را شاکل داده اناد. از آنجا که این مسئله NP-hard است ،ارائا ة روشای دقیا بارایحل آن در ابعاد واقعی ممکن نیست .با پیشرفت های اخیار در حل ایان گوناه مساائل و باا درنظرگارفتن مفروضاات و قیاودپیچیده تر روش های فراابتکاری همانند روش بهینه سازی انتاوهذرات] 12[، کلونی مورچگان] 13[، و جسا ت وجا وی پراکناده
]14[ در سا ل های اخیر توسعه داده شدند .
مسئولان پشتیتانی و خرید در واحدهای تولیدی اغلب به دنتال چیدمان بهینة تسهیلات نصب شده جهات تا أمین محصولات مورد نیاز در فضای موجودند تاا هزیناه و زماانحمل ونقل مواد و محصولات را کمینه کنند. در ایان میاانگاااهی لازم اساات بااا محاادودیت هااایی از قتیاال قیااودپیش نیازی، فضای در دسترس، و حداقل و حاداکثر فاصال ة پذیرفتنی باین تساهیلات روباه رو شاوند . پاس از طراحایچیاادمان تسااهیلات ، نوباات بااه طراحاای خااط تولیااد وبرنامه ریزی حمال ونقال بارای بهیناه ساازی جریاان ماوادمی رسد. در این مرحله مهندسان و طراحان با معضالاتی ازقتیل محدودیت پتانسیل حمل ونقال، معادودبودن وساایلنقلیاه، پنج ره هاای زم انی ، و محادودیت ظرفی ت روب ه رو هستند. مدل پیشنهادی زیر به منظور ارائا ة تاو أم طراحایبهینة چیدمان تسهیلات، برنامه ریزی حمال ونقال ماواد، و جابه جایی تسهیلات نصب شده معرفی می شود.
فض ای کارخان ه ب ا m مک ان ب القوه جه ت قرارگ رفتنتسهیلات در نظار گرفتاه شاده اسات. لازم اسات n ماشاین)تسهیلات( در گزیده ای از این مکان ها نصب شاوند )mn(. در این میان مکان نصب برخای تساهیلات در تصامیم گیاری لحا نشده و بناا بار محادودیت هاایی جاای آن هاا از پایش
مش خ اس ت .v خ ودرو ب رای س رویس ده ی و بازدی د m تسهیلات نصب شده در دسترس اند. قرار است آن ها به گوناه ای برنامه ریزی شوند که زمان سرویس دهی همة تسهیلات کمینه شود. در این تحقی ، مسیریابی حمل ونقال باه صاورت بااز درنظر گرفته شد؛ به گونه ای که حرکت خودرو هاا از یاك مرکازخاص شروع و به آن ختم نشاود . در حقیقات ابتادا و انتهاایمسیر خودروها باز باشاد. همچناین تعادادی محادودیت هاایپایش نی ازی وج ود دارد؛ ب ه گون ه ای ک ه لازم اس ت بعض ی ماشین ها پیش از بعضی دیگر توسط خودرویی یکسان بازدیادشوند. پنجره ای زمانی برای بازدید هر یك از تسهیلات در نظارگرفته شد. در ادامه مادل ریاضای مسا ئلة فاو بارای یاافتنبهینه ترین چیدمان تسهیلات در مکان های بالقوه و تخصای بهینة خودروها جهات سارویس دهای تساهیلات در کمتارینزمان ممکن ارائه می شود.
اندیس‌ها ‌
i,j ماشین هاا (m,…,0) k,l نقاط استقرار (n,…,0)  اندیس خودروها (v,… ,1) پارامتر‌ها‌و‌متغیر‌های‌تصمیم ‌
زودترین زمان ورود پذیرفتنی برای ماشین i؛ دیرترین زمان ورود پذیرفتنی برای ماشین i؛
زمان بارگیری توسط خودروی v برای ماشین i
؛
زمان مورد نیاز برای پیمودن نقطة k به l؛ ei li
fi dkl
اگر ماشین i قتل از ماشین j ملاقات شود؛ در غیر این صورت 1
0ij
اگر مکان پیش فرض ماشین i محل k باشد؛ در غیر این صورت 1
0ik
tij زمان مورد نیاز برای پیمودن نقطة i به j؛ ai زمان رسیدن به ماشین i؛
1 اگر خودروی v ماشین i را به مقصد ماشینj ترك
کند؛ xij
0 در غیر این صورت
yik10 دراگر غیر ماشیناین i در صورت محل k مستقر شود؛
مدل‌ریاضی‌پیشنهادی ‌
m Min Z max{xi0(ai  ti0fi)}
i1 s.t.
mm
 xij xjij, )1(
i0i0
vm
xij1 j0 )2(
 1 i 0
vm
x ji1  j0 )3(
 1 0i
vm
x0 jv)4(
 1 j 1
vm
xij(ai  tijfi) aj  j0 )5(
 1 0i
ei  aili  i 0 )6(
f00 )7(
n
yik 1&y00 1 i 0 )8(
k1
m
yik 1k )9(
i0
a aj  i ij i j, )10(
mm
819501774

 xii xijij i j v, , )11(
i 0i 0 yik ik i k, )12(
tij   yikyjldkl i j k l, , , )13(
از آنجا که مدل ارائه شده غیر خطی اسات و باه دلیالآنکه مدل های غیر خطی سخت تر از مدل های خطای حالمی شوند، در این قسمت مدل به صورت زیار خطای ساازیمی شود:
xxij   xij (aitij ) xxij M(1 xij) aitij )14(
i j, ,
vm
xij(ai  tijfi)  a j
 1 0i vm (xxij  fixij)  a j)15(

 1 0i
 j 0
m zmax{x i 0(ai  ti 0f i)}
i 1 zm (xx i 0  f i x i 0)  )16(
i 1
tij    yiky jldkl tij  M(2 ( yik  y jl )) dkl i j k l, , , )17( t aij, i  0, xij,ij, ik , yik [0,1])18(

همان طور که پایش از ایان نیاز اشااره شاد، هادف ازم دل س ازی ف و طراحای چیادمان و تخص ی بهیناة خودروهاست، به نحوی که امکان سارویس دهای باه هماة ماشین ها )تسهیلات( در کمترین زمان ممکن فراهم شاود.
از آنجا که مسئلة مورد بحث یك مسئلة مسیریابی باز است و بازگشت به متدأ حرکت الزامی نیست، مکاان و ماشاینیمجازی با اندیس 0 در نظر گرفتاه شاده اسات کاه فاصال ة آن ها تا سایر نقااط و ماشاین هاا برابار 0 اسات . همچناینمحدودیت 0=00y متضمن این اسات کاه ماشاین مجاازیحتماً در مکان مجاازی باا انادیس 0 قارار گیارد. در ایانحالت، هر خودرو با حرکت از ماشین مجازی و بازگشت باهآن در واقع مسیر بازی را طی خواهد کرد و متاد أ و مقصادحرکت آن یکسان نخواهد بود. زمان سرویس دهی برای هر خودرو برابر زمان بازگشت آن خودرو به ماشین 0 است. در نتیجه، تابع هدف فو به کمینه سازی طولانی تارین زماانسرویس خودروها منجر می شود.
با اعمال اولین محدودیت، اطمینان حاصل می شاود کاه هیچ خودرویی در هیچ گاره خاصای بااقی نماناده و پاس ازسرویس آن از آنجا خارج می شود. بر متنای محادودیت هاای2 و 3 و 4 لازم است همة ماشین ها به غیر از ماشین مجازی فقط و فقاط توساط یاك خاودرو بازدیاد شاو د. در مقابال ، برنامه ریزی خودروها باید به گونه ای باشد که ماشین مجاازیرا همة خودروهاا با زدیاد کنناد . محادودیت 5 گویاای ایانواقعیت است که هر گاه ماشین j بلافاصله بعد از ماشاینi و توسط خودرویی یکسان بازدید شود، زمان ورود به ماشاینj برابر زمان ورود به ماشین i ب ه علاوة زمان سارویس ماشاینi و زمان لازم بارای جاباه جاایی باین ایان دو ماشاین اسات.محدودیت 6 محدودیت پنجرة زماانی )زودتارین و دیرتارینزمان( برای بازدید هر ماشین است. طت محدودیت 7 زماانسرویس ماشین مجازی توسط همة خودروها برابار 0 اسات.
بر متنای محدودیت 8 هر ماشین باید در یاك مکاان نصاب شود و ماشین مجازی لازم است در مکان مجاازی قارار دادهشود. از طرفی محدودیت 9 دلالت بر این موضوع دارد که در هر مکاان حاداکثر نصاب یاك ماشاین امکاان پاذیر اسات.محدودیت های 10 و 11 محدودیت های پیش نیاازی نامیادهمی شوند. بر متنای این محدودیت ها هرگاه بازدیاد ماشاینi پیش نیاز بازدید ماشین j باشد، لازم است هر دو توسط یاكخودرو بازدید شوند و زماان بازدیاد ماشاینi کوچاك تار ازماشین j باشد. محدودیت 12 نشان دهناد ة لازوم قرارگارفتنبرخی ماشین ها در مکان های از پیش تعیین شده است. طت محدودیت 13 فاصلة زمانی بین دو ماشین برابر فاصلة زمانی مکان های آن هاست.
از عتارات 14 و 15 برای خطی سازی محادودیت 5، از عتااارات 14 و 16 باارای خطاای سااازی تااابع هاادف ، و از محدودیت 17 جهت جایگزینی رابطة غیر خطی به کاررفته در محدودیت 13 استفاده شد. در نتیجة این خطای ساازیهمة عتارات به کاررفته در مدل خطی شاد ؛ ولای باه علاتوجود متغیرهای 0 و 1 و عدد صاحی متعادد مادل فاو کماکان به شکل یك مدل مختلط عدد صحی مطرح است که حل آن با روش های دقیا بسایار زماان بار و در اغلابمااوارد ناااممکن اساات. همچنااین محاادودیت 18 نااوع متغیرهای مدل را نشان می دهد.
الگوریتم‌حل‌پیشنهادی
در ارائة الگوریتم های بهینه سازی ،به رغم توجاه باه تکامالزیستی انساان و ساایر موجاودات، باه تکامال اجتمااعی وتاریخی و به مثابة پیچیده ترین و موف ترین حالات تکامالتوجه چندانی نشده است. الگاوریتم رقابات اساتعماری بااالهام گرفتن از تکامل اجتماعی انسان، جهات بهیناه ساازیتوابع پیچیده، توسعه داده شد. ایان الگاوریتم باا تعادادیجمعیت اولیه شروع می شود. در این الگاوریتم، هار عنصارجمعیت یك کشور نامیده می شود. کشاورها باه دو دسات ة مستعمره و استعمارگر تقسیم مای شاوند. هار اساتعمارگر،بسته به قدرت خود، تعدادی از کشورهای مساتعمره را باهسلطة خود درمی آورد و آن ها را کنترل مای کناد. سیاساتجذب و رقابت اساتعماری هسات ة اصالی ایان الگاوریتم راتشکیل می دهد .عملگر جذب برای حرکت دادن مستعمرات به طرف قوی ترین کشور هر امپراتوری اساتفاده مای شاو د. رقابت استعماری شتیه ساز رفتار کشورهای استعمارگر برای زیاار ساالطه درآوردن سااایر کشورهاساات. قاادرت کلاایامپراتوری با ه صاورت مجماوع قادرت کشاور اساتعمارگربه اضافة درصدی از قدرت میانگین مسات عمرات آن تعریافمی شود. یکی از شروط توقف این الگوریتم ازبین رفتن همة امپراتوری های ضعیف و یکی شدن همة آن هاسات ]15[. از طرفاای الگااوریتم رقاباات اسااتعماری، بااه رغاام عملکاارددرخشانش، در جست وجوی فضاهای پیوسته، به تنهاایی دربهینه سازی مسائل گسسته ناتوان اسات . بناابراین ، در ایانتحقی روشی جهت تلفی قدرت جسات وجاوی الگاوریتمرقابت استعماری و تواناایی ابزارهاای الگاوریتم ژنتیاك دربهتود جواب های گسسته ارائه می شود. در واقاع ایان روش تلفیقی نتیجة هماهنا شادن عملگرهاای جاذب، رقاباتاستعماری، ترکیب، جهش، و تولید تصادفی است. شته کادالگوریتم طراحی شده در شکل 1 می آید.
در ابتدای الگوریتم طراحی شده امپراتاور ی هاای اولیاهشکل می گیرد و قدرت هر امپراتوری محاسته می شود.
تولید تصادفی: ابتدا، با توجاه باه اطلاعاات موجاود درصورت مسئله، مجموعه ای از مسیرها بار متناای رواباطپیش نیازی ساخته می شود؛ به گوناه ای کا ه تساهیلاتپیش نیاز و پس نیاز در قالب رشته های عددی به صورت مت والی بیاین د. ب ر متن ای مح دودیت ه ای مس ئله، می دانیم هر مسیر می تواناد فقاط و فقاط توساط یاكخودرو بازدید شود. بنابراین، در ادامه، به منظور تولیادجواب هاای تصاادفی، مسایرها باه شاکل تصاادفی باهخودروهای موجود تخصی مای یابناد. پاس از آن، باا
توج ه ب ه مق ادیر پ ارامتر ، برخ ی ماش ین ه ا در مکان های از پیش تعیین شده قرار می گیرند. در نهایت، ماشین های باقی مانده به شکلی احتمالی در مکان هاایخالی نصب می شوند. احتمال قرارگرفتن هر ماشین در هاار مکااان خااالی بسااته بااه ماشااین هااای مجاااور و خودروه ای بازدیدکنن دة آن ه ا ب ه گون ه ای تعی ین می شود که ماشین هایی که توساط خاودرویی یکساانبازدید می شوند با احتمالی بالا در مجااورت یاك دیگارقرار گیرند.
در بدنة اصلی الگوریتم تلفیقی مورد بحث عملگر جذب از طری ترکیب مستعمرات با امپراتورها فعال می شود.
ترکیب: ماشین های منتخب جهات بازدیاد توساط هارخ ودروی خ اص ب ه ص ورت ترکیت ی از ماش ین ه ای بازدیدشده توسط آن خودرو در کروموزوم های والادینتعیین مای شاو ند. بعاد از ترکیاب بازدیادها نوبات باهمکان یابی آن ها می رسد. در ایان مرحلاه ماشاین هاایجدیدی که قرار است توسط هر خاودرو بازدیاد شاو ند جایگزین مکان ماشین های قدیمی بازدیدشاده توساطآن خودرو می شوند.
به منظور جست وجوی محلای جهات ارتقاا ی بهتارینجواب هاای موجاود، تعادادی از مساتعمرات هماراه هماة امپراتورها انتخاب می شوند و جهش می یابند.
جهش: دو خودروی متفاوت از کروموزوم اولیه در نظارگرفته می شوند و برخی مسیرهای تخصای یافتاه باهآن ها به صورت تصادفی انتخااب و تعاویم مای شاوند .
همانند عملگر ترکیاب، در اجارای عملگار جهاش نیازماشین های جدیدی که قرار اسات توساط هار خاودروبازدی د ش وند ج ایگزین مک ان ماش ین ه ای ق دیمی بازدیدشده توسط آن خودرو می شوند.
اکنون بخشی از مستعمرات به صورت تصادفی انتخاابو کشورهای تصادفی جدیادی جاایگزین آن هاا مای شاو ند. سپس، قدرت هر کشور بر متنای تابع هدف معرفی شده در مدل ریاضی محاسته و قوی ترین کشورها در هر امپراتوری به منزلة امپراتور جدید شا ناخته مای شاوند . اکناون نوباتفعال کردن عملگر رقابت استعماری بین امپراتورهاست.
رقابت استعماری: در این مرحله ضعیف ترین امپراتوری شناسایی و بخشی از مستعمرات آن با توجه به قادرتمحاسته شده برای سایر امپراتوری ها به شکلی احتمالی بین آن ها تقسیم می شود.
الگوریتم فو تا آنجاا اداماه پیادا مای کناد کاه هماة امپراتوری های ضعیف به مرور زمان از هم می پاشد و فقاط یك امپراتوری باقی می ماند. امپراتور باقی ماناده باه منزلاة بهترین جواب ذخیره می شود و به نمایش درمی آید.

داده های صورت مسئله را بخوان.
پارامترهای الگوریتم را مقداردهی کن.
امپراتوری های اولیه را بساز.
کشورهای اولیه را به صورت تصادفی بساز.
قدرت هر کشور را با توجه به مقدار تابع هدف آن برازش کن.
امپراتورها و مستعمراتشان را بر متنای قدرت کشورها مشخ کن.
قدرت هر امپراتوری را بر متنای قدرت امپراتور و مستعمراتش محاسته کن.
4. حلقة زیر را تا آنجا تکرار کن که فقط یك امپراتوری باقی بماند )حلقة اصلی الگوریتم(.
4-1. عملیات زیر را برای هر امپراتوری انجام بده.
عملگر جذب را فعال کن:
مستعمرات را با امپراتوری هایشان ترکیب کن و آن ها را به سمت امپراتور حرکت بده.
77927-3432201

از عملگر جهش برای جست وجوی موضعی امپراتورها و برخی مستعمراتشان استفاده کن.
درصد از پیش تعیین شده ای از جمعیت را به صورت تصادفی جایگزین کن.
قدرت هر کشور را با توجه به مقدار تابع هدف آن برازش کن.
قوی ترین کشور را در هر امپراتوری به منزلة امپراتور جدید مشخ کن.
قدرت هر امپراتوری را بر متنای قدرت امپراتور و مستعمراتش محاسته کن.
شکل 1. شبه کد الگوریتم تلفیقی رقابت استعماری نتایج‌محاسباتی ‌
در ایاان قساامت عملکاارد الگااوریتم پیشاانهادی بررساایمی شود. به همین منظور، دو نمونه مسا ئله، یکای در ابعاادکوچك و دیگری در ابعاد بزرگ، طراحی شد. در نمونة اول شانزده نمونه از مسائل نمونة کوچك با الگوریتم فرا ابتکاری پیشنهادی حل و جواب ها با جواب های حاصل از حل مدل با نرم افزار CPLEX مقایسه می شاود . هادف ایان آزماایشسنجش اعتتار مدل پیشنهادی و بررسی تواناایی الگاوریتمفراابتکاری پیشنهادی به منظور یافتن جواب های بهیناه درمقایسه با حل مدل توسط روش های دقی است. همان طور که در جدول 1 مشاهده می شود، تعداد تسهیلات بیشترین تأثیر را بر سختی حل این گونه مسائل دارد؛ به طاوری کاهنرم افزار CPLEX نمی تواند محاستات خود را بارای یاافتنجواب بهینة مسائلی باا بایش از 10 ماشاین )تساهیل( در کمتر از 1000 ثانیه انجام دهد.
3094812-1327909

شکل 3. مقایسة زمان های حل برای الگوریتم ICA پیشنهادی و نرم افزار CPLEX
الگوریتم فراابتکاری با حل این مسائل در 4 تا 99 درصد از زمان CPLEX تواناایی باالایی از خاود نشاان داده اسات.علاوه بر زمان اجرای بسایار پاایین الگاوریتم فراابتکااری درمقایسه با مدل تحقی در عملیات خطی شده، ایان الگاوریتمحتی در برخی موارد توانسته جاواب باه دسات آماده توساطنرم افزار CPLEX را تا 31 درصد بهتاود بخشاد. در کال، بااتوجه به نتایج حل شانزده مسا ئلة نموناه ، الگاوریتم تلفیقایعملکرد بسیار خوبی در مقایسه با نرم افزار CPLEX در حالاین دسته از مسائل از خود نشان داده است .شاکل هاای 2 و 3 جهت مقایسة آسان تر زماان اجارا و کیفیات جاواب هاایبه دست آمدة دو الگوریتم ارائه می شود.
طراحی شده قتل از نرم افزار CPLEX به همگرایی مای رساد؛ اما میزان رشد زمان حل برای این نرم افازار باا بازرگ شادنابعاد مسئله به مراتاب بازرگ تار از ایان میازان بارای روشفراابتکاری است. بنابراین، می توان نتیجه گرفت که اساتفادهاز روش تلفیقی معرفی شده امکان حال مساائل واقعای را باادقت بالا در زمانی بسیار کمتار از زماان ماورد نیااز توساطنرم افزار CPLEX فراهم می آورد. در ادامه، به منظور مشاهدة عملکرد الگوریتم فراابتکاری در حل مساائل بازرگ باا ابعاادنستتاً واقعی، سه مسا ئلة نموناه باا مشخصاات ذکرشاده درجدول 2 تولید و توسط روش تلفیقای کدشاده در نارم افازارمت لب حل شدند. سه مسا ئلة نموناه باا 30 تاا 50 ماشاینجهت مکان یابی و برنامه ریزی حمل ونقل به صورت تصاادفیساخته شدند. روند تکامل جواب به دست آماده بارای مسئللةP17‌در شکل 4 می آید. روند تکامل و بهتود جواب از هار دومقدار کمینه و میانگین قابل مشاهده است؛ طوری که شایبحاصله برای کمینة جواب ها بیشتر از شایب باه دسات آمادهبرای میانگین جواب هاست. این مسئله نشان دهناد ة عملکاردمناسب و هوشمند روش تلفیقی در حل مسائل فو است.

شکل 2. مقایسة جواب های به دست آمده توسط الگوریتم ICA پیشنهادی و نرم افزار CPLEX
در ش کل 2 نمااودار آب ی نشااان دهن دة جااواب هااای به دست آمده با الگوریتم فراابتکاری است و رن قرمز باراینمایش دادن جواب های به دست آمده از نرم افزار CPLEX.
همان طور که مشاهده می شود جواب های به دست آمادهبا هر دو روش بسیار نزدیك به هم اند؛ طوری که در برخایموارد جواب های CPLEX تحات الشاعاع روش فراابتکااریقرار گرفته و در سایر موارد بالعکس.
در شکل 3 نیز از رن آبای بارای روش فراابتکااری و ازرن قرماز بارای نارم افازارCPLEX اساتفاده شاده اسات.همان طور که مشااهده ما ی شاود ، هماواره روش فراابتکااری

شکل 4. روند بهبود در حل مسلله توسط الگوریتم ICA پیشنهادی در مسللة P17
نتیجه‌گیری ‌
مسئلة زنجیرة تأمین چندسطحی شاخة مهمای از مساائلزنجیرة تأمین است که به آن بسیار توجه می شود. یکای ازتصمیم گیری های مهام در ایان دسات مساائل مکاان یاابیمراکز توزیع مواد و محصولات مورد نیاز است؛ در حالی که لازم اس ت ترتی ب بازدی د ای ن مراک ز نی ز ب ا توج ه ب همحدودیت های موجود به شکلی بهینه انتخاب شود. پس از تعریف صورت مسا ئله، مادل تحقیا در عملیاات آن ارائاهمی شود و سپس به منظور سهولت حل مدل ارائاه شاده باانرم افزار CPLEX عتارات غیار خطای م وجاود در مادل باابهره گیری از روش های خطی سازی از بین می روند. با وجود متغیرهااای گسسااتة متعاادد و طتیعاات پیچیاادة ماادل خطی شده، نیاز به طراحی الگوریتمی فراابتکاری جهت حل کارای مسائل با ابعاد نساتتاً واقعای احسااس مای شاو د. درهم ین زمین ه، از تلفی الگ وریتم رقاب ت اس تعماری ب ا ابزارهای الگاوریتم ژنتیاك باه منظاور اساتفاد ة توأماان از قدرت جست وجوی الگاوریتم رقابات اساتعماری و توانااییابزارهای الگوریتم ژنتیك در بهتود جواب های گسسته بهره گرفته شد. در نهایت، اعتتار مدل تحقی در عملیات ارائه و روش فراابتکاری ماذکور باا تولیاد شاانزده مسا ئلة نمونا ة کوچ ك و متوس ط و س پس ح ل آن ه ا ب ه ه ر دو روش سنجیده شد.
توانایی الگوریتم فراابتکاری در حل مسائل مذکور در 4 تا 99 درصد زمان حل مورد نیاز توسط نارم افازارCPLEX نشان از کارایی بالای این الگوریتم در حل مسائل واقعی بااابعاد بزرگ دارد.
جدول 1. مقایسة نتایج برای مسائل با ابعاد کوچک
Test problems No. of machines No. of nodes No. of vehicles CPLEX Hybrid ICA Comparison
Objective Running value time Objective Running value time Running Objective time (%): value gap
(meta- (%): (meta-
CPLEX)/ CPLEX)/
CPLEX CPLEX
p1 5 10 3 55.77 10.9 58.23 10.8 99 4.4
p2 5 8 1 90.83 11.2 95.8 10.7 95 5.4
p3 6 10 1 155.32 12.4 187.19 11.5 93 20.5
p4 7 11 2 74.45 28.2 51.65 23.7 84 -30.6
p5 8 15 3 78.86 85.3 90.23 40 47 14.4
p6 7 15 4 22.71 105.5 23.87 53.8 51 5.1
p7 8 11 2 119.34 220.4 122.22 37.4 17 2.4
p8 7 20 4 40.3 723.5 52.74 73.5 10 30.8
p9 9 13 3 172.61 1000 189.89 40.5 4 10.0
p10 10 14 3 136.75 1000 112.13 47.4 5 -18.0
p11 10 18 4 184.62 1000 253.75 86.4 9 37.4
p12 9 20 3 94.03 1000 102.93 71.4 7 9.4
p13 10 20 3 61.55 1000 66.76 95.6 10 8.4
p14 9 20 4 132.91 1000 161.98 101.7 10 21.8
p15 10 20 4 95.68 1000 110.83 112.4 11 15.8
p16 20 40 4 18 26.9
4202253215874

631.41

1000

801.89

182.2

22.71

10.9

23.87

10.7

631.41

1000



قیمت: تومان


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