تحقیق با موضوع حمل و نقل، نرم افزار

تأمینکننده s به بارانداز میانی i
زمان ورود k’-امین وسیله نقلیه خروجی بارانداز میانی i به مکان خرده فروش r
زمان شروع حرکت k-امین وسیله نقلیه ورودی تأمینکننده s
زمان ترک k-امین وسیله نقلیه ورودی تأمینکننده s از بارانداز میانی i
زمان شروع حرکت k’-امین وسیله نقلیه خروجی بارانداز میانی i
زمان ترک k’-امین وسیله نقلیه خروجی بارانداز میانی i از مکان خرده فروش r
متغیر کمکی با مقدار مثبت، به منظور حذف زیر تورهای وسایل نقلیه
با در نظر گرفتن M به عنوان یک ثابت بسیار بزرگ و τ به عنوان اندیس زمان (0 τ ≤ T)، مدل برنامهریزی غیرخطی عددصحیح مختلط به صورت زیر ارائه میشود.
• مدل 2:
(3-47)
(3-48)
(3-49)
(3-50)
(3-51)
(3-52)
(3-53)
(3-54)
(3-55)
(3-56)
(3-57)
(3-58)
(3-59)
(3-60)
(3-61)
(3-62)
(3-63)
(3-64)
(3-65)
(3-66)
(3-67)
(3-68)
(3-69)
(3-70)
(3-71)
(3-72)
(3-73)
(3-74)
(3-75)
(3-76)
معادله (3-47) کل هزینههای زنجیره را حداقل میکند، به طوریکه چهار عبارت اول هزینههای حمل و نقل (شامل هزینههای ثابت و هزینههای متغیر حمل و نقل) و دو عبارت آخر به ترتیب هزینه خرید محصولات از تأمینکنندگان و هزینه نگهداری محصولات در باراندازهای میانی را شامل
میشوند. محدودیتهای (3-48) و (3-49) تضمین میکنند که در صورت استفاده از هر وسیله نقلیه (ورودی یا خروجی) این وسیله نقلیه فقط یک گره (به ترتیب بارانداز میانی یا خرده فروش) را در آغاز تورش ملاقات میکند. محدودیتهای (3-50) و (3-51) ایجاب میکنند که نقطه شروع حرکت هر وسیله نقلیه ورودی باید یک تأمینکننده و هر وسیله نقلیه خروجی باید یک بارانداز میانی باشد.
محدودیتهای (3-52) و (3-53) تضمین میکنند که نقطه شروع و پایان حرکت هر وسیله نقلیه باید یکسان باشند. محدودیتهای (3-54) و (3-55) پیوستگی مسیر هر وسیله را تضمین میکنند (اگر یک وسیله نقلیه به یک گره وارد شود باید آن گره را نیز ترک کند). زیر تورهای موجود در مسیر وسایل نقلیه توسط محدودیتهای (3-56) و (3-57) حذف میشوند. محدودیتهای (3-58) و
(3-59) ایجاب میکنند که یک محصول توسط یک وسیله نقلیه به یک گره (بارانداز میانی یا خرده فروش) تحویل داده میشود اگر و فقط اگر آن وسیله نقلیه آن گره را ملاقات کند. محدودیتهای
(3-60) و (3-61) ایجاب میکنند که تقاضای هر خرده فروش برای هر محصول از طریق یک وسیله نقلیه ورودی به یک بارانداز میانی تحویل داده شده و سپس، توسط یک وسیله نقلیه خروجی به خرده فروش تحویل داده میشود. محدودیتهای (3-62) و (3-63) تضمین میکنند که کل حجم محصولات حمل شده توسط هر وسیله نقلیه نباید از ظرفیت آن وسیله نقلیه بیشتر باشد. محدودیت (3-64) ایجاب میکند که برای هر محصول، کل مقدار عرضه شده توسط یک تأمینکننده نباید از حداکثر ظرفیت آن تأمینکننده به منظور عرضه آن محصول تجاوز نماید. محدودیت (3-65) جریان هر محصول در هر بارانداز میانی را متعادل میکند. محدودیت (3-66) زمان ورود هر وسیله نقلیه ورودی به هر بارانداز میانی (در صورت ملاقات کردن آن بارانداز میانی) را تعیین میکند. همچنین زمان ترک هر وسیله نقلیه ورودی از هر بارانداز میانی (در صورت ملاقات کردن آن بارانداز میانی) به وسیله محدودیت (3-67) مشخص میشود. محدودیت (3-68) تضمین میکند هر وسیله نقلیه خروجی زمانی بارانداز میانی را ترک میکند که کل عملیات بارگیری آن وسیله نقلیه خروجی به اتمام رسیده باشد. زمانهای ورود و خروج هر وسیله نقلیه خروجی به و از مکان یک خرده فروش (در صورت ملاقات کردن آن خرده فروش) به وسیله محدودیتهای (3-69) و (3-70) تعیین میشوند. محدودیت (3-71) نگهداری موقت محصولات در باراندازهای میانی را بررسی میکند. ظرفیت محوطه تخصیص داده شده به منظور نگهداری موقت محصولات در باراندازهای میانی به طور پیوسته در طول افق برنامهریزی به وسیله محدودیتهای (3-72) تا (3-74) کنترل میشود. در این محدودیتها، افق برنامهریزی به یک سری بازههای کوتاه با طول مساوی تقسیم شده است. محدودیت (3-75) ایجاب میکند که عملیات استراتژی فرابارانداز باید در طول افق برنامهریزی به اتمام برسد. نامنفی بودن متغیرهای تصمیم به وسیله محدودیت (3-76) چک میشود.
3-8- رویکرد حل مسأله دوم
با توجه به NP-hard بودن مسأله مذکور و عدم توانایی نرم افزارهای بهینهسازی در دسترس مانند نرم افزار Lingo در حل مسایل نمونهای تولید شده، در این تحقیق یک الگوریتم ترکیبی شامل الگوریتم ژنتیک و یک روش جستجوی محلی62 به منظور حل مدل مربوط به مسئله دوم توسعه داده شده است.
هالند63 در سال 1975 الگوریتم ژنتیک را به عنوان یک روش جستجوی موثر نشات گرفته از فرآیند تکامل طبیعی معرفی کرد. در الگوریتم ژنتیک جمعیتی از کروموزومها در طول چندین نسل به وسیله عملگرهای ژنتیک (شامل عملگرهای انتخاب64، همگذری65 و جهش66) تکامل مییابند. نحوه نمایش جواب67، تولید جمعیت اولیه، عملگرهای ژنتیک و شرایط توقف از جمله مهمترین عواملی هستند که در طراحی الگویتم ژنتیک باید مورد بررسی قرار گیرند. در طول دهه اخیر در موارد بسیار زیادی از الگوریتم ژنتیک به عنوان یک ابزار مناسب به منظور حل مسائل بهینهسازی ترکیباتی استفاده شده است. به منظور مطالعه بیشتر در ارتباط با الگوریتم ژنتیک، خواننده به منابع [63] و [64] ارجاع داده میشود.
ساختار کلی الگوریتم ترکیبی ارائه شده در این پایان نامه به شرح ذیل است:
گام1) (تولید جمعیت اولیه) یک جمعیت از کروموزومها را به عنوان جمعیت اولیه به صورت تصادفی تولید کنید.
گام2) (ارزیابی جوابها) میزان برازندگی هر جواب را محاسبه کنید.
گام3) (انتخاب والدین) با استفاده از عملگر انتخاب والدین را انتخاب کنید.
گام4) (عملگر همگذری) عملگر همگذری را بر روی والدین انتخاب شده اعمال کنید.
گام5) (عملگر جهش) عملگر جهش را بر روی فرزندان تولید شده اعمال کنید.
گام6) (مکانیزم اصلاح ساختار کروموزومها) کروموزومهای نامعتبر تولید شده توسط عملگرهای همگذری و جهش را اصلاح کنید.
گام7) (انتخاب نسل بعد) تعدادی از کروموزومها را به منظور تشکیل نسل بعد انتخاب کنید.
گام8) (جستجوی محلی) با استفاده از روش جستجوی محلی بعضی از جوابهای انتخاب شده برای نسل بعد را بهبود دهید.
گام9) (شرایط توقف) گامهای 2-9 را تا زمان برآورده شده معیار توقف تکرار کنید.
در ادامه این بخش گامهای فوق به طور مفصل تشریح میشوند.
3-8-1- نحوه نمایش جواب و تولید جمعیت اولیه
نخستین گام در طراحی یک الگوریتم ژنتیک تعیین نحوه نمایش جواب (تعیین ساختار کروموزوم) است. ساختار کروموزوم با تصویر کردن خصوصیات جواب به رشتهای از نمادها، یک ارتباط بین فضای اصلی مسأله و فضای جستجو شونده به وسیله فرآیند تکامل ایجاد میکند. در نتیجه، تعیین یک ساختار کروموزوم مناسب به عنوان یک عامل مهم تاثیر بسیار زیادی در بهبود عملکرد الگوریتم دارد.
در این تحقیق از یک ساختار کروموزوم آمیخته که در آن هر کروموزوم دارای پنج بخش است، به منظور نمایش جواب استفاده میشود. تعداد ژنهای تشکیل دهنده بخش اول برابر با مجموع کل وسایل نقلیه ورودی موجود در مکان تأمینکنندگان () است. مقدار هر ژن این بخش
نشاندهنده تعداد محصولاتی است که توسط وسیله نقلیه ورودی مربوط به آن ژن به باراندازهای میانی تحویل داده میشود.
بخش دوم با طولی برابر با مجموع کل وسایل نقلیه خروجی موجود در باراندازهای میانی ()
نشاندهنده تعداد محصولات حمل شونده توسط هر وسیله نقلیه خروجی به منظور تحویل به خرده فروشها است.
تعداد ژنهای تشکیل دهنده بخشهای سوم و چهارم یکسان بوده و هر کدام برابر با مجموع تعداد محصولات سفارش داده شده توسط خرده فروشها () میباشد. در هر کدام از این دو بخش یک جایگشتی68 از اعداد صحیح به عنوان شاخصهایی برای محصولات سفارش داده شده توسط خرده فروشها وجود دارد.
در این ساختار، استفاده از بخشهای یک و سه تعیین کننده تعداد و نوع محصولات حمل شونده توسط هر وسیله نقلیه ورودی و متعاقبا تعیین کننده تأمینکنندگان محصولات مختلف میباشد. علاوه بر این، بخشهای دو و چهار نشاندهنده تعداد و نوع محصولات حمل شونده توسط هر وسیله نقلیه خروجی به منظور تحویل به خرده فروشها هستند. در این ساختار، بخشهای یک تا چهار مشخص کننده مسیر وسایل نقلیه ورودی و بخشهای دو و چهار مشخص کننده مسیر وسایل نقلیه خروجی هستند. بخش پنج با طولی برابر با مجموع کل وسایل نقلیه ورودی موجود در مکان
تأمینکنندگان () نشاندهنده زمان شروع حرکت این نوع وسایل نقلیه از مکان تأمینکنندگان است.
مثال 3-3: نحوه نمایش جواب توسط ساختار کروموزوم معرفی شده برای یک زنجیره تأمین نمونه به وسیله شکل (3-8) نشان داده شده است. این زنجیره تأمین دارای شبکهای متشکل از دو تأمینکننده، دو بارانداز میانی، سه خرده فروش، دو نوع محصول و دو وسیله نقلیه موجود در مکان هر تأمینکننده و بارانداز میانی است. علاوه بر این شاخص محصولات مختلف خرده فروشها برای این مثال در جدول (3-1) ارائه شده است.
شکل 3-8: نمایش ساختار کروموزوم برای مثال (3-3)
جدول 3-1: شاخص محصولات مختلف خرده فروشها
مطابق بخشهای یک و سه، اولین وسیله نقلیه ورودی تأمینکننده 1 محصولات با شاخص 2 و 5 (محصول دوم خرده فروش اول و محصول اول خرده فروش سوم) را به باراندازهای میانی تحویل
میدهد. عدد صفر مربوط به ژن دوم این بخش نشان میدهد که دومین وسیله نقلیه ورودی
تأمینکننده 1 مورد استفاده قرار نگرفته است. بنابراین تأمینکننده 1محصولات 2 و 5 را عرضه
میکند. به طور مشابه، اولین وسیله نقلیه ورودی تأمینکننده دوم محصول 1 و دومین وسیله نقلیه ورودی تأمینکننده دوم محصولات 3، 4 و 6 را به باراندازهای میانی تحویل میدهند. از این رو
تأمینکننده دوم محصولات 1، 3، 4 و 6 را عرضه میکند.
مطابق بخشهای دوم و چهارم، در بارانداز میانی اول محصولات 3 و 2 در یک گروه قرار داده شده و توسط اولین وسیله

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