مقاله حل مدل برنامه ریزی ریاضی برای مسئله مکانیابی مسیریابی موجودی در شرایط عدم قطعیت

بخشی از مقاله

چکیده

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

کلمات کلیدي: مسیریابی، مکانیابی انبار، حل فرا ابتکاري، بهینهسازي، برنامهریزي ریاضی،

.1 مقدمه

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

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

کمکهاي میانمدتمعمولاً از چند هفته تا 2 سال پس از فاجعه طول میکشند. با توجه به حملونقل از دستگاهها به انبار، فرض میکنیم که تعداد نامحدودي از وسایل نقلیه - و رانندگان - در دسترس هستند، اما هزینه حملونقل بستگی به مقدار مسافت حملونقل دارد. سیستم حملونقلی که در نظر داریم به شرح زیر است: کالاي امدادمستقیماً از تأمینکنندگان به انبارهاي میانی توسط کامیونها منتقل میشوند - تأمینکنندگان شامل فرودگاههاي بینالمللی، بنادر و در صورت لزوم تأمینکنندگان محلی هستند - ، حملونقل از انبارها به مشتریان توسط خودروها انجام میگردد. مسئله شامل یک بخش استراتژیک و یک بخش عملیاتی است که بخش استراتژیک آن مربوط به محل انبارها و بخش عملیاتی آن تخصیص مشتریان به انبارها هست .

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

در این پژوهش علاوه بر در نظر گرفتن مسئله تخصیص و مکانیابی و مسیریابی، موجودي چند دورهاي نیز در نظرگرفته شده است و بهطور همزمان بهینهسازي محل انبار و تخصیص مشتري به انبار و کنترل موجودي بررسی میشود و از الگوریتمهاي فرا ابتکاري براي حل مسئله استفاده میکنیم.مسئله مسیریابی وسایل نقلیه در زمره مسائل با پیچیدگی سخت قرار دارد درنتیجه، مسئله مسیریابی- مکانیابی-موجودي که توسعهیافته مسئله مسیریابی وسایل نقلیه است نیز یک مسئله با پیچیدگی سخت به شمار میآید. بنابراین، در مقالات بسیاري، این مسئله با استفاده از الگوریتمهاي فرا ابتکاري، روشهاي حل تقریبی براي مسئله توسعه دادهشده است .[14]

.1,1 ضرورت انجام تحقیق

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

در چنین شرایط اضطراري و پیچیدهاي، تصمیمگیرنده باید با سرعت و بهصورت مؤثر به مشکلات لجستیکی پاسخ دهد و نیاز آسیب دیدگان را تأمین کند. یک فاجعه، نتیجه یک رویداد بین رابطه انسان و محیطزیستش است [12] این اتفاق میتواند هم طبیعی - سیل، زلزله، ... - و هم حاصل دست انسان - حملات تروریستی و... - باشد . برآورد شده است هرساله بیش از 500 فاجعه در این سیاره خاکی رخ میدهد .13]] در سالهاي اخیر، در مناطق مختلف در سراسر جهان قربانیان بلایاي طبیعی بهطور گستردهاي کاهشیافته است. در سال 2004 زلزله در اقیانوس هند باعث سونامی و آسیبرسانی تا حدود 5000 مایل از کانون زلزله شد و عده زیادي جان خود را از دست دادند. در سال 2005 طوفان کاترینا باعث ویرانی منطقهاي حدود 90000 مترمربع شد. این حوادث در مقیاس بزرگ توجه به فنآوري مدیریت در زنجیره امداد و برنامهریزي ریاضی براي کمکهاي امدادي را افزایش داد.

.2,1 فرضیات مسئله

در این مقاله فرضیهاي که قصد رد یا پذیرش آن را داشته باشیم وجود ندارد، اما در رابطه با مدلسازي مفروضاتی در نظر گرفتهشده است که آنها را در نوشتن مدل لحاظ کردهایم. مفروضات به شرح زیر است:.1 در نظر گرفتن شرایط عدم قطعیت براي پارامترهاي مدل..2 فرض عدم کمبود در انبار. .3 مدل در حالت چند دورهاي بررسی میشود. .3مکان هریک از تسهیلات در طول دوره برنامهریزي ثابت است..4 ماشینآلات و ظرفیت آنها و همچنین ظرفیت انبارها محدود هستند.

.3,1 اهداف تحقیق

تحقیق حاضر در راستاي به تحقق رساندن اهداف زیر ارائه گشته است:..1 ارائه یک مدل ریاضی بهمنظور مسیریابی مکانیابی موجودي در انبار..2 ارائه یک روش حل مناسب براي مدل ارائهشده .3.لحاظ نمودن شرایط عدم قطعیت در مسئله موردبررسی.

.2 مرور ادبیات تحقیق

زنجیرههاي تأمین بهعنوان پایه و اساس عملیات براي بسیاري از صنایع - بازارهاي رقابتی، امدادرسانی و ... - در نظر گرفته میشوند. در سالهاي اخیر، در مناطق مختلف در سراسر جهان قربانیان بلایاي طبیعی به مقدار گستردهاي کاهشیافته است. در سال 2004 زلزله در اقیانوس هند باعث سونامی و آسیبرسانی تا حدود 5000 مایل از کانون زلزله شد و عده زیادي جان خود را از دست دادند. در سال 2005 طوفان کاترینا باعث ویرانی منطقهاي حدود 90000 مترمربع شد. این حوادث در مقیاس بزرگ توجه به فنآوري مدیریت در زنجیره امداد و برنامهریزي ریاضی براي کمکهاي امدادي را افزایش داد.

درحالیکه مقدار زیادي از تحقیق و فناوري موجود براي زنجیره تأمین، تجاري است، چالشهاي مرتبط با کمکهاي انسان دوستانه در مقیاس بزرگ اورژانسی کاملاً متفاوت از برنامههاي کاربردي تجاري است. به چند نمونه از این تفاوتها براي کمکهاي انسان دوستانه اشاره میکنند که در آن زنجیره تأمین تجاري در اطراف مجموعهاي از مشتریان شناختهشده با الگوي تقاضا پیشبینیشده طراحیشده است. تفاوت کلی دیگر در هدف استراتژیک هر زنجیره تأمین است که زنجیره تأمین تجاري به فکر سودآوري و زنجیره تأمین بشردوستانه به فکر تأمین کامل متقاضیان است. ایده ترکیب مکانیابی انبار و مسیریابی وسایل نقلیه قدمتی نزدیک به پنجاه سال دارد [9]اما آن زمان پیشرفت کامپیوتر در حدي نبوده که جوابگوي حل این مسائل ترکیبی باشد.

بر اساس تعریف [1]مکانیابی- مسیریابی را بهصورت مکان-یابی- مسیریابی با در نظر گرفتن جنبههاي طراحی تور در نظر میگیریم که این مطالب همسو با نظر [2]است که مسائل مکانیابی- مسیریابیرابا توجه به تصمیمات اساساً استراتژیک مکانیابی امکانات در نظر میگیرد. خوب است بدانیم که مکانیابی امکانات و مسیریابی وسایل نقلیه باهم مرتبط هستند،[3] نشان داد که محل کارخانجات، انبارهاي کالا و عرضه محصولات، اغلب تحت تأثیر هزینههاي انتقال هستند.[25] براي اولین بار خلاصهاي از روش تکراري رابین دو مرحله موقعیتیابی و مرحله مسیریابی معرفی کردند مرحله موقعیتیابی بهصورت یک مدل برنامهریزي خطی فرموله شده و بهصورت بهینه با استفاده از شمردن مجازي حلشدهاند مجموع فاصلههاي بین انبارها و نقطه پایانی از مسیرهاي پیداشده را در مسیریابی مینیمم میکند، مرحله مسیریابی از یک نوع ذخیرهسازي تصادفی بهصورت عام براي انبارهاي چندگانه استفاده میکند هنگامیکه با مرحله گسترش قیمت صفر یا ناچیز و جزئی باشد به پایان میرسد.

این روش بعدها توسط چندین نویسنده گسترش پیدا کرد. [24] یک مدل برنامهریزي عدد صحیح غیرخطی را پیشنهاد دادند که در آن هدف به حداقل رساندن حملونقل، مکانیابی و هزینههاي موجودي اطمینان است و از طریق الگوریتم لاگرانژ حل نمودند[20] مدل داسکین همکاران بهعنوان یک مدل برنامهریزي عدد صحیح پوشش مجموعهاي مدلسازي کردند و از یک روش مبتنی بر تولید ستون براي حل مدل براي دو مورد خاص استفاده نمودند، نخست هنگامیکه واریانس تقاضا با میانگین متناسب است و دوم زمانی که واریانس تقاضا صفر است. [6] تنها نقاط انتهایی از سفر را بهصورت ورودي به مرحله موقعیتیابی موردبررسی قرار ندادند بلکه تمام زوج مشتریان را بررسی کردند.

آنها همچنین طول سفر را در محاسبه ارزشهاي - قسمتهاي - متغیري از مدل مکانیابی دخیل کردند. علاوه بر این، هزینههاي متغیر در زمره قدمهاي نامتجانس بهحساب میآیند. فاز مکانیابی برم بناي انتقال ساخته میشود و فاز مسیریابی بر مبناي گامهاي مخلوط ابتکاري چندگانه ساخته میشود و هنگامیکه با یک روش مداوم - پیدرپی - مقایسه میشود، پیشرفت قابلتوجهی را نشان میدهد . روش [8]به بالا شبیه شده است. بهاستثناي اینکه هر دو مرحله آن به یک تحقیق جدولی ترکیبی و چهارچوب برگشتی شبیهسازيشده وابسته است اما با یک ساختمان همسایگی ساده کننده.[6] یک روش مرتبهاي و معرف به روش آشیانه ارائه کردند، این نویسندگان نشان دادند که حل مسئله محل یابی و مسیریابی بهطور جداگانه اغلب منجر به هزینهاي بیشتر از حالت ادغامی آن میشود.

این دو نویسنده مسئله مکانیابی مسیریابی را طبقهبندي کرده و به بررسی انواع روشها براي قطعی، تصادفی پویا و نسخههاي با شبکههاي پیچیدهتر پرداختهاند. بررسی فرمولاسیون اصلی مسئله مکانیابی مسیریابی انبارها توسط [27] بیانشده است. در این مقاله طراحی پیچیده مسئله که شامل تسهیلات محل و انبارداري و حملونقل موجودي است، بررسیشده و دو نوع فرمولاسیون برنامه-ریزي ریاضی براي تمام مسائل به همراه اثبات آنها پیشنهادشده است. بهطور دقیقتر این مسئله شامل تعیین بهترین راهحل براي انتقال کالا از عرضهکننده به نقاط تقاضا با انتخاب ساختاري از شبکه است که هزینهها را به حداقل برساند و یک نوع آن توسعه مدل [24] است.

[22] تصمیمگیري کنترل موجودي را با مسئله مکانیابی تسهیلات با محدودیت ظرفیت ترکیب کردند. مدل آنها مراکز توزیع را مکانیابی و خردهفروشان را به آنها تخصیص میدهد و بهترین سیاست موجودي در هر مرکز توزیع را با توجه به محدودیت ظرفیت مرکز توزیع تعریف میکند و مسئله عدد صحیح غیرخطی حاصل با استفاده از آزادسازي لاگرانژ حل میشود. میرندا و کار قبلی خود را با در نظر گرفتن دو نوع محدودیت ظرفیت در مراکز توزیع توسعه دادند، اولی حداکثر مقدار سفارش را محدود میکند و دومی حداکثر سطح موجودي را براي هر مرکز توزیع تعیین میکند.[30] به بررسی مکانیابی مسیریابی انبار با حل فرا ابتکاري در یک حادثه پرداختهاند، مسئله سه هدفهاي که سیستم حملونقل آن شامل حمل کالا از تأمینکننده به انبارهاي میانی و سپس توزیع در بین مشتریان است.

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

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

همچنین مسئله واکنش به بلاهاي طبیعی بین دیگران توسط [28] موردمطالعه قرارگرفته است. آنها مسیریابی مکانیابی وسایل نقلیه را در یک فاجعه بزرگ تجزیهوتحلیل کردند، ازآنجاکه مسیریابی وسایل نقلیه روي زمان رسیدن کمکها به نیازمندان تاثیر میگذارد و هم تحویل سریع و هم عادلانه مهم است پس در اینجا دو تابع هدف جایگزین براي TSP و VRP در نظر گرفتهشده است که اولی حداکثر زمان رسیدن را حداقل و دومی زمان متوسط رسیدن را کمینهسازي میکند. آزمایشات محاسباتی نشان میدهد که راهحل بهینه سازي سنتی به طورقابل توجهی متفاوت از حل بهینه با تابع هدف جایگزین است. نکته اصلی آن است که هردو روش درحالتوسعه مرزهاي جواب در آزمایشات هستند و به بررسی تأثیر هزینه کل بر اهداف میپردازند.

در این مقاله تأکید بر توسعه حل براي مسئله مسیریابی درزمینه ي امداد است نه براي نشان دادن تأثیرات بر هدفهاي جایگزین، مسئله نیز آخرین زمان خدمت هر مشتري را به حداقل میرساند. در مقاله نوشتهشده توسط [29] مسئله حملونقل تحویل اضطراري کمکهاي غذایی موردمطالعه قرارگرفته است. این مقاله به برنامهریزي هفتگی تحویل اورژانسی کمکهاي هوایی غذایی براي انگولا پرداخته است که در آن برنامههاي سفر رفتوبرگشت بین انبار و مشتریان بررسیشده و طبق یک مدل برنامهریزي عدد صحیح خطی تمام بارها به مشتریان در هرزمانی میرسد. در این برنامهریزي سفرها از %9 به %28 افزایشیافته است و میتوان بین حداقل تقاضاهاي مشتریان اولویتبندي ایجاد کرد، براي رضایت کافی مشتریان و همچنین میتوان دوره کوتاه یکهفتهاي را براي دورههاي کوچکتر دو الی سهروزه نیز به کاربرد 9]] یک مدل براي عرضه به مراکز توزیع و تخلیه مجروحان از مناطق بحرانی به اورژانس را پس از یک فاجعه طبیعی پیشنهاد دادهاند.

در مقالهاي که توسط [31]نوشتهشده است، یک زنجیره تأمین با انبارهاي متعدد در نظر گرفتهشده است و مشتریان ازلحاظ جغرافیایی پراکنده و داراي تقاضاي غیرثابت در طول افق برنامهریزي گسسته هستند، هدف باز کردن مجموعهاي از انبارها است بهطوريکه مقادیر تحویل به مشتریان از طریق ناوگان حداکثر و هزینه سیستم حداقل میگردد. براي حل این مدل ابتدا یک مدل برنامهریزي عدد صحیح مختلط ساختهشده و سپس روش ابتکاري ترکیبی بهکاربرده شده است. سهم اصلی این مقاله بهینهسازي همزمان محل تخصیص موجودي و تصمیمات مسیریابی است. این پژوهش با مدلهاي ILRP متفاوت است.-1انبارها و وسایل نقلیه داراي ظرفیت محدود هستند. -2سیاست دوباره