بخشی از مقاله
چکیده:
مسأله مکانیابی - مسیریابی با برداشت و تحویل همزمان - LRPSPD - ، ازجمله مسایلی است که در مدلسازي و حل مسایل دنیاي واقعی، به عنوان مثال سیستمهاي توزیع محصولات آشامیدنی، کاربرد دارد. اما این مسأله به خانواده مسایل NP-hard تعلق داشته و بنابراین روشهاي دقیق بهینه-سازي در حل مقیاسهاي متوسط و بزرگ آن کارایی مطلوبی ندارند. در این مقاله، با استفاده از قدرت الگوریتم تبرید شبیهسازي شده، رویکردي جدید جهت حل مسأله LRPSPD ارائه شده و عملکرد آن با استفاده از یک مثال عددي تصادفی در مقیاس متوسط مورد بررسی قرار میگیرد. نتایج حاصل از بررسیهاي انجام شده، عملکرد مناسب رویکرد پیشنهادي را نشان میدهند.
کلمات کلیدي:مسأله مکانیابی - مسیریابی با برداشت و تحویل همزمان؛بهینهسازي؛الگوریتم تبرید شبیهسازي شده.
.1 مقدمه
حمل و نقل، پایههاي پل رابطی است که بخشهاي مختلف جوامع با عبور از روي آن، به سمت توسعه پایدار حرکت میکنند. در جهان امروز، حمل و نقل از جمله بخشهاي زیربنایی اقتصاد است که فرآیند توسعه اقتصادي را تحت تأثیر قرار داده و اساس مبادلات بازرگانی و کلید توسعه اقتصادي و اجتماعی میباشد.در واقع حمل و نقل چون شریانی است که سایر اجزاي خدماتی، بازرگانی، صنعتی و کشاورزي را در سطوح ملی و بینالمللی به هم پیوند داده و تأثیرات عمیقی بر رشد و توسعه این بخشها برجا میگذارد؛ بخشهایی که در حقیقت پیشرفت و پسرفت اقتصاد یک کشور بستگی مستقیم به عملکرد تک تک آنها دارد.
از مهمترین علل افزایش هزینههاي حمل و نقل میتوان به ازدحام جادهها [1]، تصادفات، تأخیر در سفرها [2] و مصرف انرژي اشاره نمود. با توجه به تأثیر مسافت پیموده شده بر تمامی این موارد، میتوان گفت که حتی بهبودي جزئی در مسیر ممکن است به کاهش قابل ملاحظه هزینهها بیانجامد .[3] اهمیت این موضوع باعث شده که طراحی مسیر وسایل نقلیه، توجه بسیاري از پژوهشگران حوزهي حمل و نقل را به خود معطوف دارد که در این میان مسأله مسیریابی سهم قابل توجهی را به خود اختصاص داده است.در طراحی سیستمهاي توزیع علاوه بر تعیین مسیر حرکت وسایل نقلیه خدمترسان، تصمیمگیري درخصوص مکان احداث دپوها - نقاط شروع و پایان سفرها -
نیز حائز اهمیت بوده و طی سالهاي اخیر، اتخاذ تصمیمهاي اثربخش، قابل اتکا و منعطف درخصوص این دو موضوع تبدیل به یکی از دغدغههاي اصلی مدیران شده است .[4]در این راستا، موضوعی که گاهاً مورد نقد پژوهشگران مختلف قرار گرفته است، پرداختن جداگانه به این دو مقولهي کلیدي میباشد. به عنوان مثال، صلحی و راند [5] نشان دادند که حل مسألهي مکانیابی بدون توجه به مسیرها ممکن است منجر به یک راهحل زیربهینه گردد. براي فائق آمدن بر این مشکل، مسألهاي تحت عنوان مسأله مکانیابی - مسیریابی - LRP - شکل گرفت که بطور همزمان تصمیمات مربوط به مکانیابی و مسیریابی را اتخاذ مینماید6]، .[7
این مسأله با پرداختن همزمان به مسائل مکانیابی تسهیلات - FLP - و مسیریابی وسایل نقلیه - VRP - تحت محدودیتهایی نظیر محدودیت ظرفیت وسایل نقلیه و تسهیلات، راه حلی ارائه مینماید که به موجب آن تقاضاي مشتریان با کمترین هزینهي کل - شامل هزینههاي حمل و نقل، هزینههاي احداث دپو و هزینههاي ثابت وسایل نقلیه - تأمین گردد. مسأله مکانیابی - مسیریابی در حوزههاي مختلفی نظیر تحویل روزنامه 8]، [9 و توزیع محصولات آشامیدنی [10]کاربرد دارد.در مسأله مکانیابی - مسیریابی، مشتریان فقط داراي تقاضاي تحویل بوده و هدف تعیین نحوهي توزیع اقلام با استفاده از وسایل نقلیهي مستقر در دپوهاي فعال میباشد. یکی از فرضیاتی که میتواند مسأله را براي برخی مسائل دنیاي واقعی کاربرديتر نماید این است که مشتریان علاوه بر تقاضاي تحویل، تقاضاي برداشت نیز داشته باشند و این دو نوع تقاضا بطور همزمان و توسط یک وسیله پاسخ داده شوند.
این فرض منجر به تعریف مسألهاي تحت عنوان مسأله مکان-یابی - مسیریابی با برداشت و تحویل همزمان - LRPSPD - ، به عنوان تعمیمیافتهي مسأله مکانیابی - مسیریابی و مسأله مسیریابی خودرو با برداشت و تحویل همزمان - VRPSPD - ، توسط کارائوگلانو همکاران [11] گردید که میتوان آن را خلاصهوار بدین نحو تشریح نمود: تعیین همزمان مکان دپوهاي فعال - با ظرفیت و هزینهي ثابت مشخص - و مسیر حرکت وسایل نقلیه خدمترسان - با ظرفیت و هزینهي ثابت مشخص - جهت برآورده نمودن همزمان تقاضاي تحویل و برداشت مجموعهاي از مشتریان به گونهاي که ضمن پیروي از قیود ظرفیتی، تقاضاي همه مشتریان با کمترین هزینهي کل پاسخ داده شود.
ازجمله کاربردهاي این مسأله میتوان به استفاده از آن در سیستمهاي توزیع محصولات آشامیدنی اشاره نمود که در آنها وسایل نقلیه علاوه بر تحویل محصول به مشتري، وظیفهي دریافت بطريهاي خالی از مشتریان را نیز بر عهده دارند.با توجه به اینکه LRP یک مسأله NP-hard میباشد، LRPSPD نیز به این دسته از مسایل تعلق داشته [12] و بنابراین روشهاي دقیق بهینهسازي در حل مقیاسهاي متوسط و بزرگ این مسأله کارایی مطلوبی ندارند. یکی از بهترین گزینههاي موجود جهت حل این قبیل مسایل، بهرهگیري از قدرت الگوریتمهاي فراابتکاري میباشد که بارها توانایی خود را در دستیابی سریعتر به جواب بهینه - نزدیک بهینه - مسایل NP-hard به رخ کشیدهاند.
در مطالعه حاضر با استفاده از الگوریتم معروف و شناخته شدهي شبیهسازي تبرید - SA - رویکردي جدید جهت حل مسأله مکانیابی - مسیریابی با برداشت و تحویل همزمان ارائه میگردد.سازماندهی سایر بخشهاي این مقاله به شرح ذیل میباشد. بخش 2 به مرور ادبیات مرتبط با موضوع پرداخته و در بخش 3 پس از تعریف مسأله، یک مدلبرنامهریزیعددصحیحمختلط براي آن ارائه میشود. رویکرد پیشنهادي جهت حل مسأله در بخش 4 شرح داده شده و پس از بررسی عملکرد الگوریتم پیشنهادي با استفاده از مثال عددي در بخش 5، نتیجهگیري نهایی در آخرین بخش ارائه میگردد.
.2 مرورادبیات
مسأله مکانیابی - مسیریابی با برداشت و تحویل همزمان نخستین بار توسط کارائوگلان و همکاران [11] معرفی شد. مؤلفین پس از ارائهي یک مدل ریاضی متشکل از 5 نوع متغیر تصمیم، با بهرهگیري از الگوریتمهاي شاخه و برش، تبرید شبیهسازي شده - SA - و چندین نامساوي معتبر روشی براي حل مسأله پیشنهاد نمودند. آنها عملکرد الگوریتم توسعه یافته را با استفاده از نمونههاي بدست آمده از ادبیات مورد بررسی قرار داده و نتیجه گرفتند که برخی نمونههاي تشکیل شده از حداکثر 88 مشتري و 8 دپوي بالقوه را میتوان در زمان معقول حل نمود. چندي بعد، کارائوگلان و همکاران [13] دو مدل برنامهریزي خطی عدد صحیح مختلط - یکی مبتنی بر گره و دیگري مبتنی بر جریان - و مجموعهاي از نامساويهاي معتبر جهت تقویت این مدلها ارائه کرده و براي حل مسأله از یک رویکرد ابتکاري دو مرحلهاي مبتنی بر الگوریتم تبرید شبیهسازي شده با جواب اولیهي به دست آمده از دو روش ابتکاري استفاده نمودند.
نتایج حاصل از ارزیابیهاي انجام شده نشان میدهند که در نمونههاي کوچک 10 - تا 30 مشتري - مدل مبتنی بر جریان از نظر کیفیت جواب و مدت زمان اجرا عملکرد بهتري داشته، اما در نمونههاي متوسط 50 - تا 100 مشتري - مدل مبتنی بر گره جایگاه بهتري را به خود اختصاص میدهد. همچنین، الگوریتم SA در نمونههاي با اندازهي متوسط، به میانگین فاصله %1 و بیشترین فاصله %6 با بهترین کران پایین رسیده است.وینسنت و لین [12]، با به کارگیري استراتژي تپهنوردي با چندین نقطهي شروع در چارچوب تبرید شبیهسازي شده، یک الگوریتم تبرید شبیهسازي شده با چند نقطهي شروع - MSA - براي حل مسأله LRPSPD پیشنهاد کردند. آنها الگوریتم خود را با استفاده از 360 نمونه مورد آزمایش قرار دادند و نتیجه گرفتند که استفاده از چندین نقطهي شروع میتواند عملکرد الگوریتم تبرید شبیهسازي شده را بطور چشمگیري بهبود دهد. مدتی بعد با بهرهگیري از قدرت الگوریتم
SA، رویکردي ابتکاري جهت حل مسأله مکانیابی - مسیریابی با تحویل و برداشت همزمان توسط وینسنت و لین [14] ارائه گردیده و عملکرد آن با استفاده از 8 مجموعه نمونه آزمایشی مورد ارزیابی قرار گرفت. نتیجهي حاصل از بررسیهاي صورت گرفته حاکی از این بود که روش پیشنهادي در حل مسایل LRPSPDعملکرد مناسبی دارد.قطره سامانی و حسینی مطلق [15] یک مدل برنامهریزي خطی عدد صحیح مختلط براي مسأله مکانیابی - مسیریابی دوسطحی با برداشت و تحویل همزمان پیشنهاد کردند. آنها تقاضاي مشتریان را غیرقطعی فرض کرده و براي رویارویی با پارامترهاي غیرقطعی، یک رویکرد برنامهریزي فازي را به خدمت گرفتند.
براي حل مدل پیشنهادي، یک رویکرد ابتکاري ترکیبی برپایهي الگوریتم تبرید شبیهسازي شده و الگوریتم ژنتیک ارائه شده و عملکرد آن با استفاده از مثالهاي عددي مختلف مورد بررسی قرار گرفت.وانگ و لی [16]، موضوع کاهش انتشارات کربن در مسأله مکانیابی - مسیریابی با ناوگان غیریکسان، برداشت و تحویل همزمان و پنجرههاي زمانی را مورد مطالعه قرار داده و ضمن ارائهي مدل برنامهریزي عدد صحیح مختلط براي مسأله، یک رویکرد ابتکاري ترکیبی 2 مرحلهاي براي حل مسایل متوسط و بزرگ و یک روش ابتکاري جهت ایجاد جواب اولیه براي جستجویهمسایگیمتغیر - VNS - پیشنهاد دادند.
مولفین در روش طراحی شده از الگوریتم ژنتیک نیز استفاده کرده و با وارد نمودن ایدهي SA به چارچوب VNS قدرت بهینهسازي الگوریتم را بهبود دادند.ناديزاده و کفاش [17] مسأله مکانیابی - مسیریابی ظرفیتدار فازي با تحویل و برداشت همزمان - FCLRP-SPD - را برپایهي نظریهي اعتبار فازي مدل کرده و براي حل آن یک روش خوشهبندي حریصانه - GCM - ، متشکل از 4 مرحله، ارائه نمودند. در رویکرد پیشنهادي، پس از خوشهبندي مشتریان، تعیین مراکز ثقل خوشهها براي انتخاب دپو - هاي - مناسب و تخصیص خوشهها به دپو - هاي - انتخاب شده، در مرحلهي پایانی براي ایجاد مسیر بین دپو - ها - و خوشههاي تخصیص یافته از رویکرد کلونی مورچگان استفاده گردید.
در مطالعهاي دیگر، ناديزاده و حسینینسب [18] پس از ارائهي یک مدل برنامهریزي عددصحیح مختلط مبتنی بر گره براي مسأله مکانیابی - مسیریابی ظرفیتدار با تحویل و برداشت همزمان - CLRP-SPD - از رویکرد حریصانه فوق جهت حل مسأله استفاده کردند.الگوریتم تبرید شبیهسازي شده - SA - پس از معرفی توسط متروپلیسو همکاران [19]، نخستین بار توسط کیرکپاتریکو همکاران [20] در حل مسایل بهینه-سازي مورد آزمایش قرار گرفت و بعد از آن به واسطهي توانایی خروج از نقاط بهینهي موضعی تبدیل به یکی از محبوبترین الگوریتمها در حل مسایل NP-hard شد. در مقالهي حاضر نیز با بهرهگیري از قدرت الگوریتم SA رویکردي جهت حل مسألهLRPSPD ارائه میگردد.
.3 تعریفومدلسازیمسأله
مسألهي LRPSPD را بر روي گراف جهتدار کاملGمتشکل از مجموعه گرههاي - Nشامل گرههاي احداث دپوN0و گرههاي مشتریان - Nc و مجموعه کمان-هايAتعریف مینماییم. به هریک از کمانها، مثلاً کمان - i, j - ، عدد نامنفیCijنسبت داده میشود که این عدد هزینهي سفر از گرهiبه گره - jیا فاصله گرهiاز گره - jمیباشد. این اعداد باید به گونهاي انتخاب شوند که در نامساوي مثلثی صدق نمایند - یعنی - . براي هریک از گرههاي احداث دپو، یک ظرفیتCDkو یک هزینهي ثابتFDkدر نظر گرفته میشود. به منظور ارائهي خدمت به مشتریان - هریک با تقاضاي تحویلDiو تقاضاي برداشت - Pi، ناوگانی متشکل از تعدادي نامحدود وسیلهي نقلیهي یکسان با ظرفیتCVو هزینهي عملیاتی ثابتFVدر دپوها استقرار دارند. هدف مسأله تعیین مکان دپوها، تخصیص مشتریان به دپوهاي احداث شده و تعیین مسیر حرکت وسایل خدمترسان با کمترین هزینهي کل و تحت فرضیات زیر میباشد:
•هر وسیله باید حداکثر در یک مسیر بکار گرفته شود، •هر مشتري باید فقط از یک وسیله خدمت دریافت نماید،
•دپوي شروع و پایان هر مسیر باید یکسان باشد،
•کل بار یک وسیله در هر نقطهي مسیر نباید از ظرفیت آن وسیله تجاوز کند،
•مجموع تقاضاهاي تحویل مشتریان اختصاص یافته به یک دپو نباید از ظرفیت آن دپو بیشتر شود،
•مجموع تقاضاهاي برداشت مشتریان اختصاص یافته به یک دپو نباید ازظرفیت آن دپو بیشتر شود.
در ادامه مدل برنامهریزي عدد صحیح مختلط مبتنی بر جریان [13] ارائه میگردد. این مدل متشکل از 5 نوع متغیر تصمیم به شرح زیر میباشد:اگر دپو در محل k احداث شود 1 در غیر اینصورت 0اگر یک وسیله نقلیه مستقیما از گره i به گره j سفر کند 1 در غیر اینصورت 0اگر مشتري i به دپوي k اختصاص داده شود 1 در غیر اینصورت 0اگر یک وسیله نقلیه مستقیماً از گره i به گره j سفر کند برابرست با میزان تقاضاي تحویل باقیمانده پس ازترك گرهi، در غیر این صورت برابرست با 0اگریک وسیله نقلیه مستقیماً ازگره i به گره j سفر کند برابرست با میزان تقاضاي برداشت جمعآوري شده تا گرهi، در غیر اینصورت برابرست با 0
