بخشی از مقاله
خلاصه
مساله مسیریابی - مکانیابی، دو نوع از مسائل اساسی مدیریت زنجیره تامین، مساله مکانیابی تسهیل و مساله مسیریابی وسیله نقلیه را با هم ادغام می کند. هدف مساله مسیریابی مکانیابی حل همزمان مساله مکانیابی تسهیل و مساله مسیریابی وسیله نقلیه براي کاهش مجموع هزینه هاي پشتیبانی سازمان ها است. ما ترکیب الگوریتم ژنتیک - GA - 1 و شبیه سازي تبرید - SA - 2 را براي حل مساله مسیریابی - مکانیابی با محدودیت ظرفیت روي وسایل نقلیه و انبارها پیشنهاد کردیم. الگوریتم پیشنهادي روي یک مجموعه از مسائل الگو امتحان شد و نتایج بدست آمده با سایر الگوریتم هاي موجود در ادبیات مقایسه شد. نتایج محاسباتی نشان داد که الگوریتم پیشنهادي قابل رقابت با سایر الگوریتم ها است.
کلمات کلیدي: مساله مسیریابی - مکانیابی، الگوریتم ژنتیک و شبیه سازي تبرید ترکیبی، مساله مسیریابی وسیله نقلیه
.1 مقدمه
مساله مسیریابی - مکانیابی 3 - LRP - شامل دو نوع از مسائل اساسی مدیریت زنجیره تامین، مساله مکانیابی تسهیل4 و مساله مسیریابی وسیله نقلیه5 می باشد. جنبه هاي مختلف این مسائل مانند مکانیابی، تخصیص و مسیریابی عموما به صورت مستقل مورد مطالعه قرار گرفته اند. مکانیابی یک تصمیم استراتژیک است که در یک چارچوب زمانی بلند مدت بیان می شود، در حالیکه مسیریابی یک جنبه عملیاتی است که می تواند چندین بار در کوتاه مدت تغییر کند. مساله مسیریابی مکانیابی جنبه هاي استراتژیک - مکان یابی - و عملیاتی - مسیریابی - را با هم ادغام می کند. مساله مسیریابی - مکانیابی می تواند به عنوان حالت خاصی از مساله مسیریابی وسیله نقلیه تعریف شود به طوري که در آن نیاز است که تعداد و مکان بهینه انبارها همزمان با یافتن مسیرهاي توزیع انجام شود.
اگرچه اکثر کاربردهاي مسیریابی - مکانیابی به توزیع بستهها یا کالاهاي مصرف کننده تمرکز دارد، اما کاربردهاي دیگري نظیر مکانیابی تجهیزات نظامی [1]، طراحی شبکه هاي نوري [2]، صنعت کشتیرانی [3]، در دنیاي واقعی وجود دارند. مساله مسیریابی - مکانیابی با محدودیت ظرفیت روي انبارها و وسایل نقلیه را مساله مسیریابی - مکانیابی با ظرفیت محدود 6 - CLRP - می نامند. گري و جانسون [4]، نشان دادند که مساله مکانیابی تسهیلات و مساله مسیریابی وسیله نقلیه، NP-hard هستند. از این رو، مساله مسیریابی- مکانیابی به دلیل اینکه از ترکیب این دو مساله تشکیل شده است یک مساله NP-hard است.
از این رو، پژوهشگران از رویکردهاي مختلف براي حل این مساله استفاده کرده اند. لاپورته، نوربرت و ارپین [5]، یک الگوریتم دقیق براي حل مساله مسیریابی- مکانیابی با ظرفیت محدود ارائه کردند. مین، جایارامن و اسریواستا [6]، سیر تکاملی مساله مسیریابی - مکانیابی در ادبیات را بررسی کردند و فرصتهاي مطالعاتی را در تلفیق جنبههاي واقعی تر، طراحی الگوریتمی و پیچیدگی مدل بیان کردند. بوهافس، هاجام و کوکام [7]، براي حل مساله مسیریابی - مکانیابی با ظرفیت محدود یک الگوریتم، ترکیبی از الگوریتم شبیه سازي تبرید و سیستم کلونی مورچگان1 پیشنهاد کردند. پرینس، پرودهنو کالوو [8]، یک الگوریتم ممتیک با مدیریت جمعیت 2 - MA|PA - براي حل مساله مسیریابی - مکانیابی با محدودیت ظرفیت و مسیرها ارائه کردند. - MA|PA -
شکلی از الگوریتم ممتیک است که در آن تنوع جمعیت کوچکی از راه حل ها بوسیله قبول یک راه حل جدید کنترل شده است، اگر فاصله آنها تا جمعیت از یک حد آستانی تجاوز نکند. یو و همکاران [9]، یک الگوریتم شبیه سازي تبرید مبتنی بر الگوریتم ابتکاري پیشنهاد دادند و آن را روي سه نمونه از مسائل الگو3 امتحان کردند. بلنگور و همکاران [10]، یک روش دقیق بر مبناي الگوریتم شاخه و برش4 در جهت حل مساله مسیریابی مکانیابی با محدودیت هاي گنجایش و ظرفیت در انبارها و وسایل نقلیه پیشنهاد دادند. آنها از یک مدل خطی صفر و یک که توسط خانواده هاي جدید از نابرابري هاي معتبر تقویت شده بود استفاده کردند.
تینگ و چن [11]، یک الگوریتم بهینه سازي مورچگان چندگانه با محدودیت روي انبارها و مسیرها براي حل مساله مسیریابی - مکانیابی توسعه دادند. آنها مساله مسیریابی مکانیابی با ظرفیت محدود را درون مساله مکانیابی تسهیلات و مساله مسیریابی وسیله نقلیه چند انباره 5 - MDVRP - تجزیه کردند، به طوري که مساله دوم به صورت یک مساله فرعی در درون مساله اول مورد بحث قرار گرفت. اسکوبار و همکاران [12]، یک الگوریتم ترکیبی از الگوریتم جستجوي ممنوع6 و جستجوي همسایگی متغیر7 براي حل مساله مکان یابی – مسیریابی با ظرفیت محدود پیشنهاد کردند. ماریناکیس [13]، یک الگوریتم بهینه سازي ازدحام ذرات8 براي حل مساله مسیریابی – مکان یابی با ظرفیت محدود توسعه دادند.
لوپس و همکاران [14]، یک الگوریتم ژنتیک ترکیبی براي حل مساله مسیریابی – مکان یابی با طرفیت محدود توسعه دادند و نتایج آن را با الگوریتم هاي پیشنهاد شده در ادبیات مقایسه کردند. با توجه به کاربرد گستردهي مساله مسیریابی مکانیابی در شبکه هاي توزیع، بررسی بیشتر آن ضروري است. با توجه به تحقیقات کم انجام شده در این زمینه، ناحیه وسیعی براي تحقیقات بیشتر در این زمینه وجود دارد. تمرکز این تحقیق روي استفاده از ترکیب الگوریتم ژنتیک و شبیه سازي تبرید جهت کمینه سازي کل هزینه ها در مساله مسیریابی مکانیابی است و به دنبال این است که ترکیب این دو الگوریتم ما را به نتایج بهتر در مقایسه با سایر الگوریتم هاي ارائه شده توسط پژوهشگران می رساند.ادامه این پژوهش به شرح ذیل از این قرار است. روش حل ارئه شده بر اساس ترکیبی از الگوریتم هاي ژنتیک و شبیه سازي تبرید در بخش 2 مورد بحث قرار می گیرد. در بخش 3، طراحی آزمایشات مبتی بر طراحی تاگوچی ارائه می شود و در بخش نهایی 4، نتایج و نتیجه گیري تشریح می شود.
.2 الگوریتم فرا ابتکاري
به طور کلی، دو کلاس متفاوت براي دست بندي الگوریتم هاي فرا ابتکاري در نظر گرفته می شود: الگوریتم هاي مبتنی بر یک جواب و الگوریتم هاي مبتنی بر جمعیت. در کلاس اول، الگوریتم ها تلاش می کنند که در هر تکرار روي یک جواب کاندید بهبود ایجاد کنند. الگوریتم جستجوي ممنوع، شبیه سازي تبرید و جستجوي همسایکی متغیر مثال هایی از الگوریتم هاي متعلق به این کلاس می باشند. در کلاس دوم، الگوریتم ها تلاش می کنند که در هر تکرار روي چندین راه حل کاندید بهبود ایجاد نمایند. الگوریتم ژنتیک، بهینه سازي کلونی مورچه وبهینه سازي ازدحام ذرات در این کلاس قرارمی گیرند. در این تحقیق، به دلیل عملکرد قابل توجه الگوریتم شبیه سازي تبرید و ژنتیک در حل مسائل مرتبط با موضوع - لوپس و همکاران [14]، یو و لین [15] و یو و لین - [16]، ترکیبی از دو الگوریتم براي حل مساله مورد بررسی در نظر گرفته شده است.
.2,1 ترکیب الگوریتم ژنتیک با شبیه سازي تبرید 1 - HSAGA -
الگوریتم شبیه سازي تبرید یک الگوریتم مبتنی بر یک جواب و الگوریتم ژنتیک یک الگوریتم مبتنی بر جمعیت است. براي ترکیب این دو الگوریتم باید الگوریتم شبیه سازي تبرید را با اعمال مکانیزمی به الگوریتمی مبتنی بر جمعیت تبدیل کرد. براي این کار در هر تکرار چند نقطه داریم که جمعیت فعلی ما هستند و این نقاط هر کدام تعدادي همسایه تولید می کنند. در شکل 1، انداره جمعیت - جمعیت فعلی - 3 و تعداد همسایه ها براي هر عضو جمعیت 5 می باشد.
با توجه به شکل 1، 15 پاسخ جدید - فرزندان - داریم که به همه آنها نیازي نداریم حال باید آنها را با یکی از رویکردهایی که در الگوریتم ژنتیک وجود دارد با جواب هاي اولیه - والدین - مقایسه کنیم. رویکرد مورد نظر مقایسه جواب فعلی با بهترین جوابی است که در همسایگی جواب فعلی ایجاد شده است - شکل 2 را ببینید - . براي این کار همسایه ها - فرزندان - را داخل یک جمعیت قرار می دهیم. بین این همسایه ها رقابت اتفاق می افتد و 3 همسایه که بهترین هستند انتخاب می شوند و این 3 جواب با جواب فعلی - والدین - به سبک شبیه سازي تبرید مقایسه می شوند و بعد از آن ما 3 جواب جدید داریم - در شکل - 2 که این جواب ها نیز 15 همسایه تولید می کنند و این روند ادامه خواهد داشت.
