نشریه تخصصی مهندسی صنایع، دوره 47، شماره 2 ، مهر ماه 1392، از صفحه 215 تا 228 مسیریابی وسایل نقلیه چند هدفه با کالاهاي مناسبتی

علیرضا عیدي*1 ، سید علی قاسمی نژاد2 و حنیف محققی2
استادیار گروه مهندسی صنایع- دانشگاه کردستان- سنندج
دانشجوي کارشناسی ارشد مهندسی صنایع- دانشگاه کردستان- سنندج
(تاریخ دریافت 22/5/91، تاریخ دریافت روایت اصلاح شده 31/6/92، تاریخ تصویب 14/7/92 )

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

واژه هاي کلیدي: مسئله مسیریابی وسیله نقلیه، چند هدفه، پنجرههاي زمانی، چند تقاضایی

مقدمه
یکی از مباحثی که در چند دهه اخیر کاربرد زیادي در سیستمهاي حملونقـل داشـته اسـت، موضـوع مسـیریابیوسایلنقلیه است . این موضوع به عنوان پایهايترین موضوع در مدیریت توزیـع شـناخته مـیشـود . مسـئ له مسـیریابیوسیله نقلیه به مجموعهاي از مسائل اطـلاق مـیشـو د کـههدف ایجاد چند تور براي سرویسدهی بـه مجموعـهاي از مشتریان با توجه به محدودیتهـا اسـت ، بـه گونـهاي کـههزینههاي سرویسدهی کمینـه شـود و مجمـوع تقاضـايمشتریان یک مسیر، از ظرفیت وسیله نقلیه مربـوط بـه آن مسیر بیشتر نباشد . تحقیقات نظري و کاربردهاي عملی در زمینه مسیریابی، با معرفی مسـئله اعـزام کـامیون توسـطدانتزیگ و رامسر[1] آغاز شد . با گذشت نزدیک بـه پنجـاهسال از انتشار اولین مقاله، توسـعه هـاي زیـادي در مسـئله مسیریابی وسیله نقلیه به وجود آمده اسـت . در ایـن گونـهمسائل، با توجه به عملیات مـورد انتظـار از وسـایل نقلیـه،ماهیــت مســئله و محــدودیت هــاي موجــود، پیچیــدگیمدل سازي و رویکرد حل مسئله تحت تأثیر قرار میگیـرد .
Email: [email protected] ، 0871- 6668513 :نویسنده مسئول: تلفن *

یکی ازحالتهـاي رایـج مسـئله مسـیریابی وسـایل نقلیـه،مسئله مسیریابی وسایل نقلیه با پنجره زمانی است کـه در این مسئله، علاوه برمحدودیت ظرفیت، هر یک ازمشـتریان یا قرارگاهها (محل استقرار وسایل نقلیه) بـازه هـاي زمـانی ب راي ارائ ه خ دمات دارن د . ول ی اغل ب، ای ن مشـتریان هستندکه براي دریافت کالا، محـدودیت زمـانی را تعریـف می کنند و فقط در آن محدوده زمانی کالا دریافت کـرد ه و یــا بــراي محــدوده زمــانی ذکرشــده، اولویــت در نظــر می گیرند[2] . مسیریابی وسایل نقلیه با محدودیت پنجـره -هاي زمانی ،در دنیاي واقعـی کاربردهـاي فراوانـی دارد؛ از آنجملـه مـ ی تـوان از تحویـل مرسـولات بـانکی و پس تی،جمع آوري زباله و فضولات، تقسیم سوخت بین جایگاههاي سوخت، مسیریابی اتوبوس مدرسه و . . . اشاره کـرد [3] . در حقیقت در اکثر مسائل دنیاي واقعی، بـه خصـوص مسـائللجستیک با مسائل چندهدفه مواجه هستیم . زمانی کـه در پی شناسایی اهداف هستیم، خیلی اوقـات اهـداف بـا هـم تضاد دارند، بنابراین در نظر گرفتن چنـد هـدف مـی توانـدبسیار سودمند باشد . مسائل مسیریابی چندهدفه اغلـب بـه صورت توسعه مسائل آکادمیک بـه منظـور بهبـود کـاربردعملی آنها، تعمیم مسائل کلاسیک و مطالعه مسـائ ل دنیـا ، مورد استفاده قرار میگیرند .
یکی از محـدودیت هـایی کـه مسـایل کلاسـیک را بـهمسایل دنیاي واقعی بسـیار نزدیـک مـی کنـد، محـدودیتپنجرههاي زمانی با در نظر گرفتن اهـداف مختلـف اسـت .
بنابراین در دنیاي رقابتی کـه توجـه بسـیاري بـه رضـایتمشتري می شود، باید درصدد ارایه مـدل هـایی باشـیم کـهخواســتههــاي مشــتریان را بیشــتر مــدنظر قــرار دهــد .
سسومبون و همکاران[4] اهدافی را بـه مسـئله مسـیریابیوسایل نقلیه با پنجره هـاي زمـانی افزودنـد و بـراي بهبـودرضایت مشتري، تابعی براي رعایت موعـد تحویـل کـالا درنظر گرفتند و براي حل آن، یک الگوریتم ژنتیـک تلفیقـیارایه دادند . هونـگ و پـارك[5] زمـان انتظـار مشـتریان رامدنظر قرار داده و سعی کردنـد بـا حـداقل کـردن مجمـوعزمان انتظار مشتریان، رضایتمندي آنها را حـداکثر کننـ د .
آنها این مسئله را با یک روش ابتکاري حـل کـردهانـد . إل-شـربنی [6] ب راي ی ک کمپ انی حم ل و نق ل در بلژی ک ،مسیریابی حمل و نقل را مـد ل کـرده و آن را بـا الگـوریتمشبیه سازي بازپخت حل کرده است . در ایـن مـدل، هشـتهدف مدنظر کمپانی در نظر گرفته شده است . فان[7] نیـزهدفی را به عنوان حداکثر کردن رضـایت مشـتري در نظـرگرفته که در آن با اعمال روابطی، رضایت مشتري را عکس زم ان انتظ ار مش تري معرف ی ک رد و آن را ب ا الگ وریتمجستجوي ممنوعه حل کرد . توکلی مقـدم و همکـاران[8] در تحقیق خود، اهداف کمینـه کـردن هزینـههـاي سـفر وحداکثر کردن فروش را مدنظر قرار دادند؛ مشروط به آنکـهبراي حداکثر کردن فروش، قبل از اینکـه توزیـع کننـدگانرقیب، این تقاضا را کسب کرده باشند، سرویسدهی انجـامشود . آنها از شبیهسازي بازپخت براي حل آن بهره برده اند .
قصیري و قنادپور [9] یـ ک مـدل و راه حـل جدیـد بـرايمسائل مسیریابی وسایل نقلیه چند هدفـه بـا پنجـره هـايزمانی ارائه دادند . آنها اهـدافی مشـتمل بـر تعـداد وسـایلنقلیه و مجموع مسافتهاي سفر را در نظر گرفته و مسـئله را با برنامه ریزي آرمانی مـدل کردنـد و در نهایـت آن را بـاالگوریتم ژنتیک حل کردنـ د . فیلـت و همکـاران[10] یـککلاس از مسایل را به نـام فروشـنده دوره گـرد بـا در نظـرگرفتن سود تعریف کردند، به طوري که براي هـر مشـتريیک سود در نظر گرفته شـده اسـت ، ولـی ضـرورتی بـرايملاقات همه مشتريها وجـود نـدارد . مسـیریابی سـعی درحداکثر کردن سود و کمینه کـردن مجمـوع مسـافت طـیشده دارد .
به دلیل وجود اهـداف چندگانـه متضـاد، نتیجـه یـکمسئله بهینهیابی چندهدفه، تعدادي جواب بهینه است کـهبه عنوان جوابهاي بهینه پارتو شناخته میشوند . بـه طـورایدهآل در برخـورد بـا اهـداف چندگانـه، مایـل بـه یـافتنج واب ه اي بهین ه پ ارتو هس تیم . در سـال ه اي اخی ر ،تکنیک هاي زیادي براي حـل مسـائل چندهدفـه پیشـنهادشده است . این روشها را میتوان بـه دو گـروه روش هـايپارتو و روشهاي عددي، دستهبندي کرد . در روش پـارتو ، دو جواب بر این اساس که یکی بر دیگري غالـب اسـت یـاخیر، مورد مقایسه قرار میگیرند . جواب (1)X بر جـواب (2)X غالب است؛ اگر جواب (1)X در هیچ یـک از اهـداف بـدتر ازجواب (2)X نباشـد و همچنـین جـواب (1)X حـداقل در یـکهدف بهتر از جواب (2)X باشد. اغلب روشهـاي بهینـهیـابیچند هدفه، از مفهوم غلبـه، بـراي جسـتجوي جـوابهـاينامغلوب استفاده میکنند . روشهاي عددي با تبـدیلهـايریاضی، مانند مجموع وزنی خطی استفاده میشـوند . روش پارتو، از مفهوم مجموعـه غالـب پـارتو بـا ارزیـابی کیفیـتجوابها یا مقایسه جـواب هـا اسـتفاده مـی شـود[12و11] .
معروفترین روش عددي، روش مجموع وزنی خطی1 است . هر چند این روش چندین عیب دارد: اول اینکه وزنها باید مطابق اهمیت اهداف باشند. دوم، این روش در پیدا کـردن همه جوابهاي بهینه پارتو ناتوان است. بـه عنـوان مثـال،فقط جوابهایی را پیدا میکند کـه روي قسـمت محـدبمجموعه پارتو قرار دارند[13]. دیگر رویکرد عددي استفاده شده، روش برنامـه ریـزي آرمـانی2 اسـت . در ایـن روی کـرد،مقدار آرمانی (به عنوان مثال یک نقطـه از فضـاي جـواب) انتخاب میشود و سپس براي کم کردن مسافت بین جواب جاري و مقدار آرمانی، یک جستجو انجام میشود . دشواري اصـلی ای ن روش، ب ه دسـت آوردن مق دار آرم انی اس ت.
رویکرد دیگر روش Є– محدودیت3 اسـت [15و14] در ایـنروش فقط یک هدف بهینـه مـی شـود و سـایر اهـداف بـه عنوان محدودیت در نظر گرفته میشوند کـه طبـق رابطـهfi(x)≤Єi بیان میشود .
در روشهـاي پ ارتو، مفه وم پـارتو در ی ک چ ارچوبتکاملی مورد استفاده قرار گرفته است . بیشتر محققان نیـزاز الگوریتم تکاملی براي مسـیریابی اسـتفاده کـردهانـد . در برخــی از ایــن کارهــا ، یــک ترکیــب از روش تکــاملی وجستجوي محلی، هیوریستیک یا الگـوریتم دقیـق در نظـرگرفته شده است[16و17]. گارسیا- نجـرا و بولیناریـا[18] الگوریتم تکاملی چندهدفه پیشنهاد دادنـد و روش هـایی رابراي اندازهگیري شباهت جوابها ترکیـب کـرده انـد. آنهـابیان میکنند که روشهاي تکاملی در تحقیقات قبلـی بـهندرت روي بهینه کردن بیش از یک هدف و تنوع بخشـیدنبه جوابها تمرکز کردهاند . در این تحقیق، سه تابع هـدفمشتمل بر تعداد وسـایل نقلیـه، مجمـوع مسـافت پیمـودهشده و مجموع زمان سفر کمینه می شود .
در برخی تحقیقات نیـز از الگـوریتم هـاي غیرعـددي وپارتو در حل مسیریابی چندهدفه استفاده شده است . ایـنالگـوریتم هـا ب ر پایـه الگـوریتم ژنتی ک، الگـوریتم کل ونیمورچگان و یا هیوریستیکهاي خاص انجام شدهاند . دونر و همکاران از الگوریتم ژنتیک ارزیـابی بـرداري4 [19] بـرايحل مسیریابی چندهدفه استفاده کردهاند . این روش بـراياولین بار توسط اسکافر[20] براي حل مسائل چندهدفه بـارویکـرد الگ وریتم ژنتی ک پیشـنهاد ش ده اس ت . در روش VEGAدر هر تکرار، هر جمعیت به n زیـر جمعیـت تقسـیمشده و با آمیختن این جمعیتها با یکدیگر، یـک جمعیـتکوچک تر به دست میآید. n تعداد اهداف ما است .
در دنیاي واقعـی، مسـائلی وجـود دارنـد کـه تقاضـايمشتريها قطعیت دارد، ولی وابسته به نوع و زمان سرویس از طرف تأمینکننده است . به عبارتی تقاضـاهاي مشـتري،قطعی و نبـود قطعیـت در زمـان سـرویسدهـی اسـت . مـااینگونـه مسـائل را م د نظـر قـرار دادهای م و تقاضـاي ه رمشتري را منوط به زمانسرویس دهی به آن داشتهایـم . بـاتوجه به برخی از جنبههاي مشاهده شده از مسایل دنیـايواقعی در حوزه زنجیره تأمین، این موضـوع قابـل دریافـتاس ت ک ه وج ود کالاه اي مناس بتی ، نق ش بس زایی در مسیریابی وسایل نقلیه دارند . به عبارتی، تقاضاي کالاهـايمناس بتی در بره هاي از زم ان اف زایش پی دا م یکن د و مشتري، تقاضاهاي بیشتري فقـط در همـان برهـه زمـانیدارد . به عنوان مثال، کالاهاي فصلی و فاسد شدنی از جمله این کالاها هستند . کالاهاي فصـلی در پنجـرههـاي زمـانیبـزرگ تـر و کالاهـاي فاس د شـدنی نظیـر کالاهـاي لبن ی،کالاهایی با پنجره زمـانی باریـک تـر هسـتند . بـه عبـارتیمسیریابی وسایل نقلیـه ، بـه عنـوان یکـی از ارکـان اصـلیزنجیره تأمین، باید این تصمیم را به درستی گرفتـه باشـدکه سرویس دهـی را بـه نحـوي انجـام دهـد کـه متناسـبتقاضاي بازار باشد . سرویس دهی خارج از ایـن شـرایط، نـهتنها سـ ود حاصـله را افـزایش نمـیدهـد ، بلکـه نارضـایتیمشتري را نیز در پی خواهد داشت .
ایده موردنظر مـا بـر پایـه چنـد تقاضـایی5 بـراي هـرمشتري است؛ به طوري که براي هر مشـتري، دو تقاضـايمتفاوت و یک پنجره زمانی تعیین میشود کـه در صـورتارایه سرویس در پنجره زمانی مورد نظر مشـتري، مشـتريتقاضاي اول را دارد،که اغلب تقاضاي بیشتر است و در غیر این صورت(یعنی در صورت ملاقات مشتري خارج از پنجره زمانی) تقاضاي دوم را خواهد داشت . بنابراین تأمین کننـدهباید درصدد یافتن مسیرهایی باشد که رضایتمندي بیشتر مشتري با تأمین به موقع تقاضـا را در پـی داشـته باشـد وهمچنین درصدد کاهش هزینههاي ناشی از تورها باشد . ما این رویکرد را در قالب یک مسـئله چندهدفـه بـا تقاضـايمتفاوت در پنجـره هـاي زمـانی بـراي هـر مشـتري، مـدلخواهیم کرد . در فرموله کردن این مـدل ، از دو تـابع هـدفمینیمم کردن مجموع مسافت طی شده تورهـا و مـاکزیممکردن پوشش تقاضاي مشتریان نیز استفاده خواهیم کرد .
مسیریابی وسیله نقلیه، یکی از مسائل مشهور در حوزه بهینه سازي ترکیباتی است که الگوریتمهـاي مختلفـی نیـزبراي حل انواع متفـاو تی از مسـائل مسـیریابی، ارائـه شـدهاست . براي حل مسائل با اندازه کوچـک ، از الگـوریتم هـايح ل دقی ق اس تفاده م یش ود ک ه در ای ن مقال ه نی ز از نرم افزارGAMS براي ارزیابی مدل پیشـنهادي بـراي مسـائلکوچک و متوسط استفاده شده است . همچنین بـراي حـلمسئله با ابعاد بزرگ با توجه به Np-Hard[18] بودن مسـئله مسیریابی وسیله نقلیه، دو رویکـرد فراابتکـاري مبتنـی بـرالگوریتم NSGA-II با استفاده از ساختار دو سـطري نمـایشجواب و همچنین تنوع بخشی به عملگر جهـش ، طراحـی وپیشنهاد شده است .
از این رو ساختار مقاله شامل این بخش ها است: در بخـشدوم، مفروضات، فرمول بندي مسئله تحقیق و ارزیابی مـدلپیشـــنهادي بـــر اي مســـائل کوچـــک بـــا اســـتفاده ازنرم افزارGAMS مورد مطالعه قرار خواهد گرفـت . در بخـشسوم مقاله، متدولوژي حل مسئله شامل طراحی دو رویکرد فراابتکاري مبتنی بر NSGA-II ارائه خواهـد شـ د . در بخـشچه ارم نی ز آزمایش ات م دل ش امل محاس بات و اج راي الگوریتم هاي ارائه شده در مورد مجموعه مسائل تولید شده با استفاده از نرم افزارMATLAB انجام شده اسـت . در نهایـت در بخش پنجم جمعبندي و نتیجهگیـري از تحقیـق ارائـهمیشود .

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

فرمول بندي مدل
در ایـن بخ ش ، فرم ولبن دي م دل پیش نهادي ارائ ه می شود . در ادامه، بـراي بیـان فـرم ریاضـی مـدل، نمادهـا(شامل مجموع اندیسها، پارامترهـا و متغیرهـاي تصـمیم) معرفی شـده و در فرمـول بنـدي مـدل پیشـنهادي، مـورداستفاده قرار میگیرند .

مجموعه اندیسها:
n : مجموعه گره ها(مشتریان و قرارگاه) که گره اول شـاملقرارگاه است .
nv : مجموعه وسایل نقلیه
پارامترهاي مدل:
[, ]: پنجره زمانی مختص مشتري iام
: حداکثر ظرفیت وسیله نقلیه kام
: حداکثر زمانی است که وسیله نقلیه kام میتوانـد سـفرکند .
: هزینه (مسافت/زمان) گره i تا گرهj
: مدت زمان سرویس دهی به مشتري iام با وسیله نقلیـه
kام
: تقاضاي اول مشتري iام
: تقاضاي دوم مشتري iام ε: یک مقدار بسیار کوچک0 ≈ M: عدد خیلی بزرگ

متغیرهاي تصمیم براي مسئله مورد بررسی:
1 = اگ ر مش تري iام در پنج ره زم انی [ , ] ملاق ات شود، در غیر این صورت 0 =
1 = اگر مشتري iام قبل از ملاقات شود و وسیله نقلیه منتظر بماند تا به زمان برسد و سرویس را انجـام دهـد، در غیر این صورت 0 =
1₌ اگر مشتري iام بعد ملاقات شود، در غیر این صورت
₌0
1 = اگر گره i به گره j توسط وسیله نقلیه k ام پیموده شود، در غیر این صورت 0 =
: زمان رسیدن به گرهi ام
:زمان انتظار بعد از رسیدن بـه گـرهi ام بـراي شـروعسرویس دهـی توسـط وسـیله نقلیـهk ام (زمـان انتظـار درقرارگاه صفر است)
در نهایت، مسـئله تحقیـق بـه صـورت زیـر فرمـول بنـديمی شود:
Objective1: Minnnnv C Xijijk
1 j 1 k 1  
Objective2: Maxn [d1i qi  wi  di2 1 qiwi ]
1
nnv Xijk 1 j  2
i 1 k 1 
nnv Xijk 1 i  2 (4)
j 1 k 1 
 n Xijk  n Xjik  0 j , k  (5)
i 1i 1
ti   Sik Ci1 Weik M(1xi1k )  T ik   2, k (6) n n X [dijk 1j qj  w j d (12j  q j w )]j  Q kk  (7)
i 1 j 2 
tj nnv Xijk (ti   SikCijWe ) jik  2
i 1 k 1 
n Xi1k 1 k
i 2
806387-4766

nv Xijk     S1 Sn 1,S  (10)
k 1 i S ij Sj
(ti  u )iM(1  z )iε 0 i  2 (11)

(ti  l )iM(1 q ) i0 i  2 (12)
(ti  u )iM(1 q )i0 i  2 (13)
(ti  l )iM(qi   z )iε 0 i  2 (14)
zi   qiwi1 i  2 (15)
Wei  w (lii  t ) ii  2 (16)
z , q ,w ,xiii ijk 0,1 ; t ,We iik  0 (17)

روابط (7)، (8) و (16) غیر خطی هستند که به قرار ذیـل،خطی سازي میشوند . رابطه (7) با جـایگزینی روابـط (23-19)، رابطه (8) با جایگزینی روابط (31-25) و رابطه (16) با جایگزینی روابط (35-32) خطی سازي میشوند .

خطی سازي رابطه (7):
nn
[d1jX q wijk  j  j  d2j Xijk (1 q wjj )]Qk k
i 1 j 2
(18)
n
(d 1j f jk1  d 2j f jk2 )  Q k k
j  2 (19)
n
f jk1  1 Xijk  qjwj   j2 ,k
i1
(20)
n
2( f jk1 ) Xijk  q jwj   j2,k
i1 (21)
n
f jk2  1 Xijk   (1 qjwj )   j2,k
i1 (22)
n
2( f jk2 )Xijk   (1 qjwj )   j2, k
i1 (23)
خطی سازي رابطه (8) :
tj nnv (X tijk i X Weijk ik) nnv Xijk(Sik  Cij) j 2 (24)
i 1 k 1i 1 k 1 tj   n fij3  n nv fijk4  n nv Xijk(Sik Cij) j 2 (25)
i1i 1 k 1i 1 k 1 nv
fij3  M xijk ,  ij2
k1 (26)
fij3  ti   i,j2 (27)
nv
fij3  tiM(1xijk )   i, j2
k1 (28)
fijk4  M x ijk ,  ij2, k (29)
f 4 We , ij 2, k
ijkik (30)
f 4   WeM(1 x ) ,  ij 2, k
ijkikijk (31)

خطی سازي رابطه (16) :
Weik  wli i fi i 2, k (32)
fik Mw i i 2, k (33)
fik ti  i2, k (34)
fik  tiM(1wi)  i2, k (35)
در مدل بالا، رابطههاي (1) و (2) توابع هدف را نشـانمیدهند که به ترتیب بیانگر کمینه کردن مسـافت پیمـودهشده و بیشینه کردن پوشـش تقاضـاهاي بـالقوه مشـتریاناست. محدودیت هاي (3) و (4) تضمین میکننـد کـه هـرمشتري فقط یک بـار توسـط یـک وسـیله نقلیـه ملاقـاتشود(سرویس بگیرد) . محدودیت (5) پیوسته بودن تورها را تضمین می کند، به عبارتی چنانچه وسـیله نقلیـه بـه گـرهوارد میشود، باید از آن خارج شود . محدودیت (6) تضمین میکند که زمان سفر هر وسیله نقلیه از حداکثر زمان سفر تجاوز نکند . محدودیت (7) تضمین میکند که تقاضـاهايبرآورده شده توسط هر وسیله نقلیه، از ظرفیـت آن تجـاوزنکند . محدودیت (8) زمـان ملاقـات هـر گـره را محاسـبهمی کند . محدودیت (9) تضمین می کند که تـور از قرارگـاهآغاز و به آن ختم شـود . محـدودیت (10) از تشـکیل زیـرتورهــا جلــوگیري بــ ه عمــل مــی آورد کــه در آن S هــر زیرمجموعه اختیاري از مجموعـه مشـتريهـا و |S| بیـانگرتعداد اعضاي مجموعـه S اسـت . محـدودیت (11) تضـمینم یکن د ک ه اگ ر 1 = آنگ اه بـه طـور ح تم > . محدودیت هاي (12) و (13) تضمین میکند که اگر 1 = آنگاه به طـور حـتم [ , ] ∈ . محـدودیت (14) تضـمینمیکند که اگر 0 = و همچنین 0 = آنگاه به طور حـتم < . در روابـط (11) و (14) ب راي اسـتفاده از نامس اوي بزرگتر مساوي به جاي نامساوي بزرگتر، به ترتیب مقدار ε کس ر و اضـافه ش ده اس ت. مح دودیت (15) تض مین می کند که در صورت یک شدن و یا ؛ مقدار صـفراختیار کند. در محدودیت (16) مدت زمان انتظار در گـرهiام محاسبه میشود. (در صورت ملاقات مشتري قبـل از و همچنــین 1 = مقــدار مــیگیــرد) . محــدودیت هــاي متغیرهاي تصمیم در رابطه (17) نشان داده شده است .
در بخش بعدي، نتایج محاسـباتی حاصـل از اجـراي مـدلروي برخی از مسائل نمونهاي را ارائه خواهیم داد.

آزمایشات مدل
هدف از انجام آزمایشات محاسباتی، اعتبارسنجی مدل است . از آنجایی که مسائل محک در مورد مدل پیشـنهاديدر ادبیات موضوع وجود ندارد، تعـدادي مسـئله نمونـه بـه طور تصادفی تولید شـد ند . مـدل پیشـنهادي در نـرم افـزار3.6.GAMS 23کد شده است و سپس مسـائل نمونـه توسـطحل کننده CPLEX روي رایانه همراه بـا پردازنـده .Core i3 213GHz و با حافظه داخلی 3 GB حل شـده و نتـایج مطـابقجدول (1) به دست آمده است . در روند حل مدل، براي به دســت آوردن جــواب هــاي بهینــه پــارتو، از رویکــردЄ– محــدودیت اســتفاده کــرده ایــم، بــه طــوري کــه هــدف هزینه(مسافت) سفر بهینه می شود و هدف پوشـش تقاضـابه عنوان محـدودیت در نظـر گرفتـه شـده و طبـق رابطـهЄ ≥ بیان میشود . مجمـوع تقاضـاهاي دوم مشـتریان بـهعنوان حد پایین پوشش تقاضا تعیین میشـود و ایـن حـدپس از هر بار اجراي برنامه به روزرسانی میشود . ایـن رونـدرا تا بـه دسـت آمـدن همـه جوابهـاي بهینـه پـارتو ادامـهمی دهیم .
در جدول (1)، در ستون جواب هاي بهینـه پـارتو، هـرجواب پارتو در یـک پرانتـز آورده شـده اسـت . مقـادیر بـهترتیب متناظر با هـدف مجمـوع مسـافت هزینـه(سـفر ) و هدف دوم یعنی مجموع پوشـش تقاضـاها هسـتن د . همـان طور که از این جدول مشاهده میشود، در مثال هاي مـوردآزمایش، تعداد جواب هاي بهینـه پـارتو بـراي هـر مسـئله متفاوت است. بنابراین تعداد حل برنامه و همچنـین زمـاناجراي آن براي به دسـت آمـدن جـواب هـاي بهینـه پـارتو

جدول 1: نتایج مسائل نمونه
Specification Problems Result Of GAMS No. of
problem Number of
Vehicle Number of
Customer Number of
Pareto
Solution Pareto Solutions Average run time(s)
1 3 5 2 (92,32),(104,34) 0
2 3 6 2 (56,43),(64,45) 0
3 3 7 2 (78,49),(88,52) 0.9
4 3 8 2 (74,50),(86,58) 7
5 3 9 6 (74،61)،(76،65)،(80،67) 70
(82،71)،(94،73)،(98،75) 6 3 10 3 (138,56),(142,62),(146,65) 212
7 4 11 1 (118,92) 1470
8 4 12 3 (110,94),(112,99),(116,102) 2740
9 4 13 ― Error Memory 69450
متفاوت است؛ به همین سـبب بـراي هـر مسـئله متوسـط . زمان حل جواب هاي بهینه پارتو بیان شده است
رویکرد حل مسئله
همان گونه که از نتایج جدول(1) نیز بر میآید، مسئله مسیریابی وسایل نقلیـه ، جـز و مسـایلNP-Hard بـوده و بـاافزایش ابعاد مسئله، زمان حل آن به صورت نمایی افزایش یافته و پیداکردن جواب بهینه نیز با مشکل روبه رو خواهـدشد . از این رو براي رسیدن به جواب هاي مناسب در مـدتزمان قابل قبول، براي ابعاد بزرگ تر مسئله، لازم است یـکروش ابتکاري و یا فراابتکاري با رویکرد چندهدفه طراحـیشود . رویکرد پیشنهادي براي حل مدل ارائـه شـده، روشـیمبتنی بر الگوریتم 6NSGA-II است . از دلایل استفاده از ایـنالگوریتم میتوان به جمعیتی بودن این الگـوریتم و سـازگاربودن آن با مسـایل چندهدفـه، عملکـرد سیسـتماتیک درمواجهه با جوابهاي نامغلوب هر نسل و پراکنـدگی خـوبجوابها در مرز بهینه پارتو اشاره کرد . به عبارتی به جـايتابع برازندگی، مفهوم غالب بودن جواب ها در این الگوریتم، آورده شده است .

الگوریتم ژنتیک مرتب سازي نامغلوب2
ایده گلـدبرگ [12] در مفهـوم مجموعـه غالـب پـارتو،توسط سیرنیواس و دب به طور مستقیم به کار بـرده شـد . در واقع با به کارگیري ایده ارجحیت جوابهاي نامغلوب و اختصاص برازش بیشتر به آنها و همچنین اسـتفاده از تـابعتسهیم، طوري که جوابهاي نامغلوب هر صـف 7 بـه طـورجداگانــه مــورد توجــه قــرار گیــرد، الگــوریتم ژنتیــکمرتب سازي نامغلوب(NSGA) به وجود آمد . دب و همکـاران[12] براي فراهم آوردن تنوع و گونـاگونی در جـواب هـايبهینه پارتو، یک مکانیسم نخبه گرا بر اسـاس اهمیـت دادنبه صفهاي بهتر نـامغلوب تحـت قالـب الگـوریتمNSGA-II ارائه کردنـد . منظـور از صـفهـاي نـامغلوب، دسـتهبنـديجواب هاي هم رتبه است که هر دسته را مـی تـوان متنـاظری ک ص ف ن امغلوب در نظ ر گرف ت . در ای ن روش، ابت دا جمعیت فرزندان() شامل N جواب با استفاده از جمعیـتوالدین() ساخته میشوند . در ایـن روش بـه جـاي پیـداک ردن ج وابه اي ن امغلوب از ، ابت دا دو جمعی ت ب ا یکدیگر ترکیب شده و جمعیـت بـا انـدازه2N را ایجـادم یکنن د . س پس از ی ک مرت ب س ازي ن امغلوب ب راي دسته بندي تمـام جمعیـت اسـتفاده مـیشـود . بـا یـکمقایسه عمومی در بین اعضاي و پس از ایجاد صفهـايمتفاوت نامغلوب به ترتیب اولویت (اولویت صفهـا نسـبتبه هم) جمعیت بعدي یکی یکی از این صفها پر میشـود .
از آنجاکه اندازه برابر 2N است، همـه اعضـاي آن ممکـناست نتوانند در قرار گیرند و بـ ه راحتـی جـواب هـايباقیمانده را حذف خواهیم کرد . البتـه بـراي رعایـت اصـلچگالی8 در بین جوابها، جواب هایی که در ناحیـه ازدحـامکمتري هستند، براي پرکردن در اولویت قـرار دارنـد . در ادامـه، رویک رد مقایس ه اي ب ر مبن اي ازدح ام، درب اره الگوریتم NSGA-II توضیح داده میشود.

عملگر انتخاب مسابقهاي ازدحام9
این عملگر با توجه به اینکه هر جواب رتبه نـامغلوبri داشته و همچنین یک فاصله ازدحـامdi دارد، دو جـواب رامقایسه کرده و پیروز مسابقه را مشخص مـی کنـ د . فاصـلهازدحام جواب، اندازهاي از فضاي جـواب اسـت کـه توسـطهیچ جواب دیگري از جمعیت اشغال نشده باشد . بنـابراینبر پایه دو ویژگی بیـان شـده، عملگـر انتخـاب مسـابقهاي ازدحام را با این قاعده تعریف میکنیم که جواب i بر جواب j پیروز میشود، اگر و فقط اگر یکی از شـرایط زیـر برقـرارباشد:
جواب i رتبه بهتري نسبت به j داشته باشد، یعنیri< rj
جوابهاي i و j هم رتبهاند، اما جـوابi فاصـله ازدحـام
بهتري نسبت به j دارد . یعنیri= rjو di > dj شرط اول، این اطمینان را بـ ه وجـود مـیآورد کـه جـوابپیروز از درجه نامغلوب بودن بهتري نسبت به حریف خـودبهره منـد اسـت و شـرط دوم، ایـن اطمینـان را بـه وجـودمی آورد که جواب پیروز در ناحیـه ازدحـامی کوچـک تـرينسبت به حریف واقع شده باشد .
محاسبه فاصله ازدحام
در NSGA-II یک معیار فاصله ازدحام به روال شـکل (1) مورد استفاده قرار میگیرد . الگـوریتم زیـر بـراي محاسـبهفاصله ازدحام براي هر نقطه دلخواه در مجموعه F اسـتفادهمیشود . در این شـکل، انـدیسIj نمایـانگرj امـین عضـو ازلیست مرتب شده در گام دوم است . بدین ترتیب براي همه توابع هدف از 1I تا IL مقدار کمینـه و بیشـینه از ارزش هـانسبت داده میشـود . پارامترهـاي و بـ ه ترتیـببیشترین و کمترین ارزش هـاي موجـود در جمعیـت بـرايهدفm ام هستند .

گام اول: قرار میدهیم |L=|F (طـول صـفF) همچنـینبراي هر جواب i از مجموعه F قرار میدهیم 0=di

گام دوم: براي هر هـدفm=1,…,M مجموعـهfm را بـهترتیب نزولی و برحسب ارزش آنها مرتب میکنیم . در واقـعبردار اندیس مرتب شده (Im=Sort(fm را ایجاد میکنیم .

گام سوم: از m=1 تا m=M یک مقدار بزرگ براي حدود جوابها اختصاص میدهـیم و یـا

= و بـرايتمام جوابهاي دیگر 1(-j=2,3,…,(L قرار میدهیم:
(-)/(-) ( 36)
شکل 1: مراحل تخصیص فاصله ازدحام
با توجه به توضیحات داده شده در بخش هاي قبلی، ما
الگ وریتم اس تانداردNSGA-II را ب ا دو رویک رد متف اوت در س اختار عملگ ر جه ش ب ه ص ورت فلوچ ارت ش کل (2) پیاده سازي کردهایم . در فلوچارت شکل (2) بـراي تشـکیلفرزندان از جمعیت ، چهـار جـواب بـه طورتصـادف ی از جمعیت انتخـاب شـده و جـوابهـاي پیـروز مسـابقهفاصله ازدحام، براي عمل ترکیب و جهش کاندید میشوند .
در صورت پذیرش جواب براي جهش و ترکیب، جوابهـايتولید شده به جمعیت منتقل می شوند . همچنین ایـنروند تا پرشدن کامل جمعیت به اندازه N جواب ادامه مییابد . روند تولید جوابها، رتبهبندي و انتخاب آنها بـراينسل بعد، تا تشـکیل تعـداد نسـلهـاي مـورد نظـر ادامـهمی یابد .
همچنین جواب هاي نسل اولیه به طور تصادفی تولید میشوند و براي تسریع در همگرایی الگوریتم حل به جواب هاي مرز پارتو ،0 .1 از جمعیت اولیه از روش ابتکاري 10PFIHکه توسط سولومون[22] براي مسئله VRPTW ارایه شده است، تولید میشوند . این الگوریتم یک مسیر را با انتخاب یک مشتري با کمترین هزینه آغاز کرده و سپس مشتري با هزینه کمتر به مسیر اضافه می شود . این روال تا نقض ظرفیت وسیله نقلیه و پنجرههاي زمانی ادامه می یابد . تابع هزینه انتخاب مشتري به صورت رابطه(37) به دست می آید . در رابطه بالا فاصله مشتري تا دپو ، دیرترین زمان شروع سرویس به مشتري و نیز زاویه قطبی میان دپو و مشتري است . ، و نیز ضرایب ثابت هستند .

(37)= −++360

نحوه نمایش جواب

شکل 2: فلوچارت الگوریتم NSGA=II
یکی از اجزاي مهم در الگوریتم حل پیشنهادي ،ساختار نمایش جواب هاي مسئله است . از آنجا که جواب مسئله باید مسیرهاي سرویسدهی به مجموعهاي از مشتریان را نشان دهد، بنابراین چنانچه تعداد n مشتري و k وسیله نقلیه داشته باشیم، آنگاه نمایش جواب جاي گشتی از n مشتري به همراه 1(-(k درایه صفر است. از طرفی در صورت ملاقات مشتري قبل از شروع پنجره زمانی، وسیله نقلیه باید تصمیم بگیرد که خارج از پنجره-زمانی سرویس دهی را انجام دهد و تقاضاي دوم را کسب کند و یا تا شروع پنجرهزمانی منتظر بماند و تقاضاي اول (تقاضاي بیشتر) را کسب کند . این تصمیمگیري در مدل ریاضی با متغیر تصمیم در نظر گرفته شد . براي نشان دادن این متغیر تصمیم در نمایش جواب، یک سطر دیگر از اعداد صفر و یک در نظر گرفته شده که در صورت ملاقات مشتري قبل از پنجره زمانی درایه مربوط به آن، مشتري از این سطر خوانده میشود . به عبارتی از ساختار دو سطري در نمایش جواب با یک سطر براي نمایش مسیرهاي سفر و سطر دوم براي نمایش متغیر تصمیم استفاده میشود .
در شکل (3) مثالی از نحوه نمایش جواب را با 9 مشتري و 3 وسیله نقلیه نشان میدهد . در این شکل، مربع بیانگر قرارگاه و دایره نشانگر مشتریان است. مشتري 8 که به رنگ مشکی توپر نشان داده شده است، قبل از شروع پنجره زمانی، ملاقات شده، ولی وسیله نقلیه تا آغاز پنجره زمانی منتظر مانده است.

شکل 3: مثالی از نمایش جواب براي مسئله مدل شده

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

عملگر جهش
هدف از اجراي این عملگر، جستجوي نقاط بیشـتري ازفضاي جواب و جلوگیري از همگرایی زودرس است . پس از تولید جواب هاي اولیه، در این مرحله یکـی از رویکردهـايزیر را در پیش می گیریم . در رویکرد اول از ساختارOpt-2 به عنوان عملگر جهش بهره میبریم و در رویکرد دوم کـه بـانماد 2-NSGA-II نشان خواهیم داد، درصدد تنـوع بخشـیدنبه عملگر جهش هستیم . به همـین سـبب از سـه سـاختار
همسایگی Opt* ،2-Opt-2 و Or-Opt [21] بهره گرفتهایم . هر گـاهجوابی کاندید جهش قرار بگیرد، به طـور تصـادف ی یکـی ازاین ساختار همسایگیها، براي جهش مـورد اسـتفاده قـرارمی گیرد . ساختار همسـایگیopt -2 بـراي آشـفتگی بـالا درجوابها ،opt*-2 براي آشفتگی بین تـوري بـا حفـظ جهـتحرکت و Or-opt نیز آشفتگی داخل تـوري بـا حفـظ جهـتحرکت هستند . نحوه عملکرد این سه ساختار بـا توجـه بـهنحوه نمایش جـواب مسـئله در شـکل هـاي (4)،(5) و (6) آورده شده است . در ایـن سـه سـاختار، اعـداد انتخـابی درس طر دوم از بــین 0 و ی ا 1 بــه ط ور تصــادفی انتخــابمی شوند . در نهایت اینکه اعمال این عملگر نیازمند تنظـیمپارامتر نرخ جهش است .

شکل 4: نحوه عملکرد



قیمت: تومان


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