نشریه تخصصی مهندسی صنایع، دوره 49، شماره 2، پاییز و زمستان 1394، از صفحه 257 تا 271

یک الگوریتم ژنتیک کارا برای مسئلة مسیریابی وسایل نقلیه با درنظرگرفتن مهارت تیم های کاری

مرتضی کیانی1، هانی صیدگر2، ایرج مهدوی3*‌،‌رضا توکلیمقدم4‌ ‌
کارشناس ارشد مهندسی صنایع دانشگاه علوم و فنون مازندران
کارشناس ارشد مهندسی صنایع دانشگاه علوم و فنون مازندران
استاد دانشکدة مهندسی صنایع دانشگاه علوم و فنون مازندران
استاد دانشکدة مهندسی صنایع و مرکز پژوهشی بهینهسازی، پردیس دانشکدههای فنی دانشگاه تهران

)تاریخ دریافت 04/09/92 ـ تاریخ دریافت روایت اصلاح شده 12/03/94 ـ تاریخ تصویب 18/03/94( چکیده
در این پژوهش، مدل ریاضی جدیدی برای مسئلة ترکیبی نیروی انسانی- مسیریابی وسایل نقلیه ،با درنظرگرفتن تیمهایی با سطوح مختلف مهارت به عنوان عوامل خدمتدهنده، ارائه شده است. وجود تیمهایی با مهارت های متفاوت، موجب انجام کارهای مختلف مشتریان در زمان و هزینههای متفاوت و افزایش انعطافپذیری برنامهریزی میشود. جابهجایی این تیمها با استفاده از گروهی از وسایل نقلیه با سرعت و هزینه های متفاوت انجام میشود و برای ارائة خدمت به هریک از مشتریان، موعد خاصی درنظر گرفته شده است. تابع هدف مسئله، کمینه سازی هزینه های کل خدمتدهی از طریق تیمها، جابهجایی وسایل نقلیه و جریمة دیرکرد است. برای حل مسئله، از الگوریتم ژنتیک و بهینه سازی ذرات انبوه استفاده شده و پارامترهای آن بهروش تاگوچی تنظیم شده است. نتایج بیانگر کارایی مطلوب الگوریتم ژنتیک پیشنهادی در کیفیت جوابها و زمان محاسباتی است.

واژه‌های‌کلیدی: الگوریتم بهینه سازی تجمع ذرات، الگوریتم ژنتیک، مسیریابی وسایل نقلیه، مهارت تیم ها، نیـروی
انسانی.

مقدمه
مسیریابی وسایل نقلیه1، مشخصکردن مجموعة بهینه ای از مسیرهاست که از طریق ناوگانی از وسایل نقلیه، برای ارائـة خدمات به مشتریان با حداقل هزینه انجـام مـ ی شـود . ایـن مسئله را نخستینبار دانتزیگ و رامسر] 1[ به صورت فرمول ریاض ی ارائ ه دادن د و ب رای ح ل آن از روش ه ای دقی ق استفاده کردند. در مسائل کلاسیک مسیریابی وسایل نقلیه، اغلب انتقال و جابهجـایی کـا بـه عنـوان خـدمت نهـایی و وسایل نقلیه به عنوان عوامل خـدمت دهنـده درنظـر گرفتـه شده اند درحالی که مسئلة ترکیبی مسیریابی وسایل نقلیـه – نیروی انسانی با درنظرگـرفتن نیروهـای انسـانی ب ـه عنـوانعوامل ارائة خدمت، به برنامهریزی هم زمـان تخصـیص ایـن

* نویسندة مسئول: تلفن: 0911113380
نیروها به خدمتدهی به مشتریان و مسیریابی وسایل نقلیة جاب هجاکنن دة آن ه ا م یپ ردازد. تص میمگی ری درم ورد تخصیص و نحوة جابهجایی نیروهای انسانی بین مکان ها، در ح وز هه ای مختلف ی مانن د م دیریت ت یمه ای تعمی رات ،مراقبت های خانگی و مدیریت بحـران کـاربرد دارد. مسـئلة ترکیبی نیروی انسانی- مسیریابی وسـایل نقلیـه، بـهعنـوانتعمیمی از مسئلة کلاسیک مسیریابی وسـایل نقلیـه ، جـز مسائل پیچیده و مربوط به ردة مسائل NP-Hard است ]2[.
در ادبیات موضوعی، پژوه شهـای انـدکی ، مؤلفـه هـ ای انسانی را در قالب تیمهای کاری یا رانندگان وسـایل نقلیـه درنظر گرفتهاند. از میان آن ها می توان به لیم و همکاران]3[ Email: [email protected]
اشاره کرد که مسئلة تخصـیص و برنامـه ریـزی جابـه جـایی تعمیرکاران را درنظر گرفتند. در مسئلة آن ها، هـر مشـتری باید با توجه به درخواستش، از سـو ی یـک یـا چنـد نفـر از تعمیرکــاران خــدمت دهــی شــود بــه طــوری کــه هــدف، کمینه سازی تعداد تعمیرکاران، زمان معطلی و کل مسـافت طیشده باشد. آن هـا بـرای حـل مسـئله ، رویکـرد ترکیبـی لیست ممنوع و شبیه سازی تبرید را بهکار گرفتنـد . پـس ازآنها، لـی و همکـاران ]4[ محـدودیت تـ یم هـای کـاری را معرفی کردند. در مدل آن ها، برای انجام دسـته ای از کارهـا در مکان هر مشتری، کارکنان متفاوتی مورد نیاز است و هر تیم مخصوص از کارکنان باید با هم ترکیب شوند و به مکان مش تری انتق ال یابن د. آن ه ا ب رای ح ل مس ئله، از روش شبیه سازی تبرید اسـتفاده کردنـد . بهـریس و تومـاس ]2[ رویهای ابتکاری نیز برای مسئلة مسیریابی و تدارکات نیروی انسانی ارائه کردند به طـور ی کـه در آن، بایـد پـول هـایی از دستگاه های فروش یک منطقه جمع آوری شوند.
دهن و همکاران ]5[ مسئلة برنامه ریزی کارهـای حمـل بار در بعضی فرودگاه های اروپایی را مطالعه کردنـد . مسـئل ة آن ها نیازمند تخصیص نیروهـای انسـانی ، بـا درنظرگـرفتن محدودیت های تیمهای کاری و پنجرة زمـانی اسـت. آن هـارویة شاخه و هزینه را برای حـل مسـئله شـان ارائـه دادنـد . برداستورم و روکویست ]6[، محدودیتهـای پـ یش نیـازی و تط ابقی را ب ه مس ئلة ترکیب ی مس یریابی و برنام هری زی افزودند. محدودیت پیش نیازی موجـب مـی شـود وسـیله ای پس از وسیلة دیگر به مشـتر ی خـدمت کنـد درحـال ی کـه محدودیت تطابقی سبب می شود دو وسیله، در یک زمان در کنار مشتری باشند. آنها یک رویکرد ابتکاری بهینه سازی را برای حل مدلشان پیشنهاد کردند. از دیگر مسـائل ترکیـب برنامه ریزی وسایل حمل ونقل و نیروی انسانی مـ ی تـوان بـه تحقیق کیم و همکاران ]7[ اشاره کرد. آن ها مسئلة ترکیبی مسیریابی وسایل نقلیـه و برنامـه ریـزی تـ یم هـای کـاری را بررسی کردند به طـور ی کـه بایـد تعـدادی کـار بـا ترتیـب مشخص در مکان هر مشتری انجام شود.
رنت و ها ]8[ برنامه ریزی هم زمان وسایل حمل ونقل و رانندگان را برای شرکت اجارة ماشین های لیمـوزین درنظـر گرفتن د. هــدف برنام ه ریــزی جاب ه جــایی ب رای ســوار و پیاده کردن مشتریان در یک پنجرة زمانی ارائه شـده اسـت.نویسندگان از رویة حل دومرحلهای برای تعیین جواب هـا یشدنی تخصیص زوج راننده و ماشین به هـر سـف ر اسـتفاده کردن د. زاپ ل و ب ول ]9[، م دلی ک اربردی از توزی ع نام هبه صورت محلی را درنظر گرفتند که در آن، برنامه ریزی، هم برای وسایل و هم رانندگان، با درنظرگرفتن قوانین اتحادیـة اروپا انجام می شود. مسئله، به صورت ابتکاری بـا تجزیـه بـه یک مسئلة کلی مسیریابی با پنجرة زمانی حل شد. در سایر پژوهشها نیز هولیس و همکاران ]10[ و درکس و همکاران ]11[ به بررسی برنامه ریزی هم زمان مسیریابی وسایل نقلیه و رانندگان پرداختند.
در ح وزة خ دمات مراقب ته ای خ انگی م ی ت وان ب ه پژوهش راس موسن و همکاران ]12[ اشاره کرد. آنها یکی از مسائل برنامه ریزی کارکنـان مراقبـت هـای خـانگی را در ش رایط اولوی ت ه ای ملاق اتی درنظ ر گرفتن د ک ه در آن، خدمتکاران باید یک یا چند خدمت مراقبتی را بـه ترتیـب و در زمان مشخصی، در محل زندگی افراد نیازمنـد نگهـداری انجام دهند به طوری کـه سـطح کلـی رضـایت از خـدمات ، حداکثر شود. تامسون ]13[ این مسئله را بـه همـراه پنجـرة زمانی درنظر گرفت و از الگوریتم جستوجوی ممنوع بـرای حل آن اسـتفاده کـرد . لسـل ]14[ رویـه ای دومرحلـه ای را اتخاذ کرد که در مرحلة اول، ملاقـات هـا براسـاس موقعیـت جغرافیایی، تـرجیح و توانـایی دسـته بنـد ی مـ ی شـوند و در مرحلة دوم، هر دسته به صورت یک مسئلة مسیریابی درنظر گرفته و حل می شـود . از دیگـر پـژوهش هـا در ایـن زمینـه می توان بـه برتلـز و فاهـل ]15[ و دهـن و همکـاران ]16[ اشاره کرد.
در این پژوهش، تیمهای کاری با مهارت هـا ی متفـاوت ، به عنوان عوامل خـدمت دهـی درنظـر گرفتـه شـده انـد کـه می توانند خدمات مختلفی را در زمان و هزینه های متفـاوت ارائه کنند. همچنین بعضی از تیمها یا وسایل نقلیه، ممکـن است توانایی سفر و ارائة خدمت به یک یا چنـد مشـتری را نداشته باشند بنـابراین ، برنامـه ریـزی تخصـیص تـ یم هـا و جابه جایی وسایل به صـورت جداگانـه ، امـا هماهنـگ انجـام می شود. تابع هدف مدل نیز بهگونهای درنظر گرفته شده که بین هزینههای جابهجایی، خـدمت دهـی و دیرکـرد ، تعـادل ایجاد شود.
ادامة پژوهش شامل بخش های زیر است .در بخش دوم، به تعریف مسئلة ترکیبی نیروی انسانی- مسـیریابی وسـایل نقلیه پرداخته می شود. در بخـش سـوم ویژگـی هـای مـدل ساخته شده و مدل ریاضی ارائه می شـود . طراحـی الگـوریتم ژنتیک2 برای حل مسئله و تنظیم پارامترهای آن، به ترتیـب در بخ ش ه ای چه ارم و پ نجم بررس ی م ی ش وند. نت ایج محاسباتی و بررسی آن ها در بخش ششم انجـام مـ ی گیـرد . درنهایت، در بخش هفتم نتیجه گیری و زمینة پژوهشهـای آینده مطرح می شود.
تعریف مسئله
در مسئلة ترکیبی نیروی انسانی- مسیریابی وسایل نقلیه در این پژوهش، تیم ها توانایی های مختلـف و منعطفـی دارنـد بنابراین می توانند کارهای مشتریان را با سطوح مختلفـی از مهارت انجام دهند و مهارت تیم ها در زمـان ارائـة خـدمت ، تأثیرگذار فرض شده است. هرچه مهـارت تـی م بـرای ارائـة
خ دمت ب ه ی ک مشــتری بیش تر باش د، آن را در م دت کوتاه تری انجام می دهد. همچنین هریک از تـ یم هـا ممکـن است توانایی خدمت رسانی به یک یا چند مشـتری را نداشـته باشند و از این جهت، محدودیت هـایی در بـه کـارگ یری انـواع تیم وجود دارد. وسایل نقلیه نیز از نظر نوع، سرعت و هزینـه ، با یکدیگر متفاوتاند و بعضی از وسایل ممکن اسـت امکانـات زم برای سفر به مکان یک یا چند مشتری را نداشته باشـند .
وسایل نقلیه ممکن است در طول مسیر، برای تعویض تیم هـا به مرکز برگردند. از این رو، برای حل مسئله، علاوهبر مشخص کردن تـ یم هـای خـدمت دهنـده بـ ه هریـک از مشـتر ی هـا و همین طور مسیریابی وسایل جابهجاکننـدة آن هـا ، بایـد بـین ادامة مسیر یک وسیله یا یک تیم بـه سـمت مشـتری بعـدی به صورت مستقیم یا بازگشت به مرکـز و سـپس انتقـال تـیم جدی د از مرک ز ب ه مش تری بع دی )حرک ت غیرمس تقیم( تصمیم گیری شود. انتخاب های بهینه، بـه ایجـ اد تعـادل بـین هزینه های جابهجایی وسایل، هزینه های خدمت دهی تیم هـا و همین طور هزینه های دیرکرد منجـر مـ ی شـود . بـه طـورکل ی، فرضیههای زیر برای مسئله درنظر گرفته شده است:
تیم ها و وسایل نقلیه، از یک مرکز پخش، کـار خـود را آغـاز می کنند و پـس از ارائـة خـدمت ، در انتهـای مسـیر بـه آن بازمی گردند. موقعیت جغرافیایی مرکز و مشتری ها مشخص است و فواصل به صورت مستقیم محاسبه می شوند.
هریک از مشتریان به دریافت یک خدمت نیـاز دارنـد وبرای هریک از آن هـا موعـد تحویـل و جریمـة دیرکـرد درنظر گرفته شده است. درصورتی که خدمت دهی بعد ازاین موعد انجام شود، هزینه ای به صورت جریمة دیرکرد درنظر گرفته می شود که میـزان آن بـرا ی هـر مشـتری متفاوت است.
چند وسیلة نقلیه از هر نوع تـیم در مرکـز وجـود دارد.
هریک از تیم ها مهارت های متفـاوتی در انجـام کارهـای مشتریان دارند و ممکن اسـت امکـان خـدمت دهـی بـه بعض ی از مش تریان را نداش ته باش ند. همچن ین ه ر مشتری، تنها توسط یک تیم خدمترسانی می شود.
وسایل نقلیه، از نظر سرعت جابهجایی و هزینـة انتقـال با یکدیگر متفاوت اند و هریـک در هـر زمـان ، قـادر بـه جابهجایی یک تیم هستند.
برای درک مسئله می توان یک شـرکت نصـب و تعمیـر تجهیزات سنگین را درنظر گرفت که تیم هایی فنـی در سـه ردة حرفه ای، متوسط و تـازه کـار دارد و تـ یم هـای رده هـا ی مختلف، از نظـر تـوان و دسـتمزد بـا یکـدیگر متفـاوت انـد .
همچنین جابهجایی این تیم ها، از طریق سه دسـته وسـیلة نقلیة سواری، وانت و کـامیون انجـام مـ ی شـود کـه از نظـر سرعت و هزینة جابهجایی با یکدیگر تفـاوت دارنـد . هـدف ، ارائة خدمات به مشتریان بـا توجـه بـه درخواسـت و موعـد تحویل، با کمترین هزینه است .یکی از مهم ترین فرضیههای این پژوهش آن است که با توجه به کمبود نیروهای انسـانی متخصـــص در حـــوزة خـــدمت دهـــی بـــه مشـــتریان، چندمهارته بودن آن ها و نیز تجهیزات و امکانـات زم بـرای اج رای هری ک از خ دمات م ورد تقاض ای مش تریان ک ه حمل ونقل آن ها تنها با وسایل نقلیة مخصوص که به میـزان محدود )بهعلت محـدودیت مـالی و فنـی شـرکت خـدمت -دهنده( در سازمان امکانپـذیر اسـت ، نیروهـای متخصـص ، پس از تکمیل هریک از خدمات و بازگشت به مرکـز توزیـع باید با توجه به اولویت مشتریان و میزان تخصص و مهـارت آن ها برای مشتریان دیگر فرستاده شوند.
شکل 1 نحوة نمـایش گرافیکـی یـک جـواب بـا هفـت مشتری، سه وسیلة نقلیه و سه نوع تیم را نشـان مـ ی دهـد .
تور حرکت وسایل نقلیه به این صورت است که وسیلة نقلیة اول، از مرک ز ب ههم راه ت یم ن وع 1 ب هترتی ب ب هس مت مشتری های 5 و 6 سفر می کنـد و بـه مرکـز بـازم ی گـردد .

مسیر وسیلة نقلیة اول

مسیر وسیلة نقلیة دوم

مسیر وسیلة نقلیة سوم

شکل 1. نمایش گرافیکی جواب
وسیلة نقلیة دوم نیز، ابتدا تیم نوع 2 را به مکان مشـتری 7 می برد. سپس به مرکز بازمیگردد و تیم نوع 2 را با تیم نوع 1 تعویض می کند. پس از آن بههمراه تیم نوع 1 بـه ترتیـب بهسمت مشتریان 3 و 4 سفر مـ ی کنـد و سـپس بـه مرکـز بازمی گردد. وسیلة نقلیه سوم نیز ابتدا تیم نوع 3 را به مکانمشتری 1 می برد. پس از آن به مرکز بازمیگردد، تـیم نـوع 3 را با تیم نوع 1 تعویض می کند و سپس بههمراه تیم نـوع
1 به مشتریان 2 سفر می کند.

ارائة مدل ریاضی خصوصیت مدل
برای مدل پیشنهادی، دو متغیر تصـمیم گیـری بیـ انگر نـوع حرکت وسایل تعریف شده است: متغیر اول X_ij^mk است که جابهجاییهای مستقیم بین مکان ها را نشان مـ یدهـد و درصورتی مقدار یک میگیرد که تیم نوع m از طریق وسیلة نقلی ة k از مک ان i ب ه مک ان j منتق ل ش ود. متغی ر دوم Y_ij^mm’k است که بیانگر جابهجایی های غیرمستقیم بین مکان هاست و درصورتی مقدار یک میگیـرد کـه وسـ یلة k، تیم m را از مکان i به مرکز ببرد و پس از تعویض تیم m با تیم ‘m، تیم ‘m را از مرکز به مکان j منتقل سـازد . مهـارت هریک از انواع تیم ها برای خدمت به هر مشـتری ، از طریـق ماتریس P نشان داده مـ ی شـود . ایـن مـاتریس دارای ابعـاد R*N است که N تعداد مشتریان و R تعداد انواع تـ یم هـا را نشان میدهد. همان طورکه پیش تر توضیح داده شد، وسایل نقلیه از نظر سرعت جابهجایی و هزینة انتقال، انواع متفاوتی دارند و برای سفر هریک از وسایل نقلیه به مکان مشـتریان نیز محدودیت هایی وجود دارد که با ماتریس G نشـان داده می شود. این ماتریس دارای ابعاد V*N است کـه در آن،V تعداد وسایل نقلیه را نشان میدهـد . در مـدل پیشـنهادی ، باید به تمام مشتریان سیستم خدمترسـانی شـود و بـرای هریک از مشتریان، موعدی برای ارائة خدمت درنظر گرفتـه شده است. درصورتی که زمـان اتمـام خـدمت دهـ ی بـه هـر مشتری، بعد از این موعد باشد، هزینهای به صـورت جریمـة دیرکرد به سیستم تحمیل می شود.
اندیسها

: تعداد مشتریان سیستم V: حداکثر تعداد وسیلة نقلیة سیستم R: حداکثر تعداد انواع تیمهای سیستم i, j: شاخصهای نشاندهندة مکان )مشتریهـا و مرکـز پخش(
بهطوریکه در

،

مقدار صـفر مربـوط به مرکز است
m, m’: شاخصهای نشاندهندة نوع تیم بهطوریکه: m, m’ =1,2,3,…,R
k : شاخص نشـان دهنـدة وسـیلة نقلیـه بـهطـوری کـه :
k=1,2,3,…,V
پارامترهای ورودی

: زمان زم برای جابهجایی بین مکانهـای i وj توسـط وسیلة k

: هزینة جابهجایی وسیلة k در واحد زمان

: زمان انجام خدمت مشتری i ام توسط تیم m

39116713424

: هزینة خدمتدهی تیم m در واحد زمان مدل ریاضی

: توانایی تیم نوع m برای خدمتدهی به مشـتری i که بهصورت ماتریسی با اعداد بین صفر و یک نمـایش داده میشود

: قابلیت وسیلة نقلیة k برای سفر به مشـتری i کـ ه ماتریسی با اعداد صـفر و یـک اسـت . مقـدار یـک بـه ایـن معناست که وسـیلة k قابلیـت سـفر بـه مشـتری i را دارد درغیراینصورت، مقدار آن برابر صفر است

: موعد انجام خدمت به مشتری i

: جریمة دیرکرد خدمتدهی به مشتری i M: یک عدد دلخواه بزر متغیرهای تصمیم

:

درصورتیکه تیم نوع

با وسیلة نقلیة

از مکـان

به مکان

منتقل شود، مقدار یک میگیرد

:

درصورتیکه وسیلة k، تیم m را از مکـانi بـهمرکز ببرد و پس از تعویض این تیم بـا تـیم’m، تـ یم’m را از مرکز به مکان j منتقل کند، مقدار یک میگیرد

: زمان اتمام خدمتدهی به مشتری i ام

: میزان تأخیر در برآوردهسازی خدمت مشتری i ام.
(

)2(

)3(

)4(

)5(
39116-545725

(

)8(

)10(

)11(
???????? ≥ ???????? − ???????? ∀ ???? )12(
???????? ≥ 0 ∀ ???? )13(
????????????????????, ????????????????????′???? ∈ {0,1} ????????, ????????, ???????? ≥ 0 )14(

فرایند تکاملی، عملگر تقـاطع 3، جهـش 4، رقابـت و انتخـاب هستند. روش متداول پیاده سازی الگـوریتم ژنتیـک بـدین -ترتیب است که مجموعه ای از جواب ها )کرومـوزوم هـا( کـه جمعی ت نامی ده م ی ش وند، تولی د و ب ه ط ور متن اوب ب ا جواب های جدیـدی جـایگزین مـ ی شـوند . در هربـار تکـرار، تمامی جواب هـا بـا اسـتفاده از یـک تـابع تناسـب ارزیـابی می شوند. آنگاه تعدادی از بهترین جـواب هـا بـا اسـتفاده از یک تابع احتمـال انتخـاب مـی شـوند و جمعیـت جدیـد را تشکیل می دهند. تعدادی از این جواب ها بههمـان صـورت و باقی آنها با استفاده از اپراتورهای ژنتیکـی نظیـر تقـاطع و جهش برای تولید فرزندان5 بهکار می روند ]17[.
نحوة نمایش جواب ها
برای نمایش جواب، از یک مـاتریس بـا دو سـطر و 1-N+V ستون استفاده شده است به طوری که N نشان دهندة تعـداد مشتریان و V نشانگر تعداد وسـایل نقلیـه اسـت. عـددهای سطر اول، شمارة مشتریان و عددهای سطر دوم، انواع تیم ها را نشان میدهند. برای تفکیک مسیرهای هر وسیلة نقلیـه ، از علامت * استفاده شده است بنابراین، بـرای تولیـد یـک جواب امکانپذیر، 1-V سـتاره مـورد نیـاز اسـت . شـکل 2 نمایش ماتریسی جواب گرافیکی شکل 1 است. همان طورکه در شکل مشخص است، مشتریان 5 و 6 در تور وسیلة نقلیة اول، مشتریان 3، 4 و 7 در تور وسیلة نقلیة دوم و مشتریان 1 و 2 در تور وسـی لة نقلیـة سـوم قـرار دارنـد . همـ ین طـور خدمت مشتریان 6، 5، 7، 3، 4، 1 و 2 بهترتیـب بـه دسـت تیم های 1، 1، 2، 1، 1، 3 و 1 انجام می شود. متفاوتبـودن تیم های مربوط به دو مشـتری متـوالی از تـور یـک وسـیلة نقلیه، به این معناست که آن وسیله باید برای تعـویض تـیم به مرکز بازگردد. درغیراینصورت، بهمعنای حرکت مستقیم بین دو مشتری متوالی است.
معادلة 1 نشان دهندة تابع هدف مدل اسـت کـه شـامل هزینه های خدمتدهی تیمهـا بـه مشـتریان و هزینـه هـای جابهجایی از طریق وسایل نقلیه و هزینههای دیرکـرد مـی -شود. محدودیت هـای 2 و 3 تضـمین مـ ی کننـد کـه تمـام وسایل نقلیه از مرکز پخش، مسیر خـود را آغـاز کننـد و در انتهای مسیرشان به مرکز پخش بازگردند .محدودیتهای 4 و 5 نشان میدهند که برای هر مشتری، تنها یک وسـیله و یک تیم وارد و از آن خارج میشود. محدودیت 6 بیان کنندة آن است که همـان وسـیله و تـیم ورودی بـه محـدودة هـر مشتری، باید از آن خارج شود. محدودیت 7 برای جلوگیری از ایجاد زیرتور اسـت . محـدودیت هـای 8 و 9 ارتبـاط بـین زمان خدمتدهی مشـتریان متـوالی در یـک تـور را نشـان مــی دهنــد. محــدودیتهــای 10 و 11، محــدودیتهــای امکان پذیربودن مسئلهاند و بهترتیب، به توانایی وسیلة نقلیه و توانایی تیم برای خـدمت دهـی بـه یـک مشـتری مربـوطمی شوند. محدودیتهای 12 و 13، ارتباط بین زمـان اتمـام خدمتدهی به هر مشتری و موعد تعریفشـده بـرای آن را نشان میدهند.
الگوریتم های پیشنهادی الگوریتم ژنتیک
قواعد اساسی الگوریتم ژنتیک را نخستینبار هالند] 16[ در سال 1975 معرفی کرد که تاکنون کاربردهـا ی فراوانـ ی در بهینه سازی انـواع توابـع خطـی ، غیرخطـی ، مشـتق ناپـذ یر، گسســته و… داشــته اســت. الگــوریتم ژنتیــک، تکنیــک جست وجوی فراگیر هدفمندی است کـه بـر عمـل ژنتیـک طبیعی استوار شده و بدین معناست که تنهـا گونـه هـا یی از یک جمعیت ادامة نسل می دهند کـه بهتـرین ویژگـی هـا را داشته باشند و آن هایی کـه ایـن صـفات را نداشـته باشـند ، به تدریج و طی زمان از بـ ین مـ ی رونـد . اجـزا ی زیرسـاختی
6 5 * 7 3 4 * 1 2
1 1 * 2 1 1 * 3 1
9029701112520

شکل 2. نمایش ماتریسی جواب عملگر تقاطع
در عملیات تقاطع، ابتدا مکان ستاره ها- که تعیین کننـدة تـور وسایل نقلیه هستند- از والد اول )p1( گرفتـه مـی شـوند و در مکان متنـاظر خـود در مـاتریس نمـا یش دهنـدة فرزنـد قـرار م ی گیرن د. س پس مک ان ه ای باقیمان ده از س طر اول- ک ه نشان دهندة ترتیب مشتریان ملاقـات شـدة هـر وسـیلة نقلیـه است- از والد دوم )p2( گرفته می شوند و در مکان های متناظر قرار می گیرند. پس از آن، مکان های مربوط به سطر دوم- کـه نشان دهندة تیم های خـدمت دهنـده بـه هـر مشـتری اسـت – به صورت یک درمیان، از والد اول و دوم انتخاب مـ یشـوند و در جای خود قرار می گیرند. شکل 3 این رویکرد را نشان می دهد.
عملگر جهش
عملگر جهش در الگوریتم پیشنهادی به این صورت اسـت کـه ترتی ب ملاق ات مش تریان در ی ک مس یر ع وض م ی ش ود.
بدین منظور پس از انتخاب یک کروموزوم، تور یکـی از وسـایل نقلیه- که در آن، بیش از یک مشـتری ملاقـات شـده اسـت – انتخاب و سپس بخشی از این مسیر به صورت تصادفی معکوس می شود. شکل 4 عملگر جهش را نشان می دهد.

شکل 3. نمایش عملگر تقاطع

شکل 4. عملگر جهش

الگوریتم‌بهینه‌سازی‌تجمع‌ذرات
الگ وریتم بهین ه س ازی تجم ع ذرات )PSO( از روش ه ای محاسبات تکاملی است و با تقلید از پرواز پرندگان و تبـادل اطلاعات میان آن ها ابداع شده است. در PSO هـر راه حـل ، تنها یک پرنده در فضـا ی جسـت وجوسـت و عضـو 6 نامیـده می شود. تمام پرندگان، یک مقدار شایسـتگی دارنـد کـه از طریق تابع شایستگی- که باید بهینه شود- ارزیابی می شود علاوهبراین، هـر پرنـدة i دارای یـک موقعیـت در فضـا ی D بعدی مسئله است که در تکرار t ام، با یک بردار بـه صـورتزیر نمایش داده می شود: ‌
(Xit  (xti1,xti2,…,xtiD ‌همچنین این پرنـده سـرعت ی دارد کـه پـر وازش را هـدا یت می کند و در تکرار t ام با بردار زیر نشان داده می شود: ‌
(Vit  (vti1,vti2,…,vtiD ‌و این پرنده نیز در هر تکرار یک حافظه از بهترین موقعیـت قبلی خودش را دارد که با بردار P نمایش داده می شود: ‌
(Pit  ( pti1, pti2,…, ptiD ‌در هر تکرار جستوجو، هـر عضـو بـا درنظرد اشـتن دو مقدار بهترین بروزرسـان ی مـی شـود. مـورد اول مربـوط بـه بهترین راهحلی است که پرنده تـاکنون آن را تجربـه کـرده است )مقدار شایستگی بهترین راه حل نیز ذخیره می شـود (. این مقدار را بهترین p یا دراصطلاح P_best می نامند. مورد دوم، بهترین راهحلی است که با PSO دنبال می شـود و نیـز بهترین موقعیتی که تاکنون در جمعیت به دست آمده است. این مقدار بهینة عمومی است و دراصطلاح، G_best نام یـده می شود. زمانیکه یک عضو، بخشی از جمعیت را بـه عنـوانتوپولوژی همسایگانش درنظر می گیرد، بهترین مقـدار ، یـک بهترین محلی است و L_best نامیده می شود. پس از اینکـه دو مقدار بهترین پیدا شدند، موقعیت و سرعت هـر عضـو از طریق فرمولهای زیر بروزرسانی می شود:
Vit1     wVitC1 r1t Gbest Xit 
tt )15(
C2 r2 Pbest Xi 

)16( X X Vit1  itit1 )17(
در فرم ول ه ای ف وق، t بی انگر ش مارة تک رار اس ت و متغیرهای c1 و c2 فاکتورهای یادگیری هسـتند کـه اغلـب برابر 2 هستند و میزان جابهجایی یک پرنده را در یـک بـار تکرار کنترل می کنند. r1 و r2 دو عدد تصـادف ی یکنواخـت در بازة ]1،0[ هستند. w یک وزن جبری است که به صورت نوعی در بازة ]1،0[ مقداردهی اولیه مـ ی شـود . وزن جبـر ی ب زر ت ر، استکش اف عم ومی و وزن جبـری کوچ ک ت ر، استکشاف محلی را تسهیل می سازد. t_max و t بـه ترتیـب ، ماکزیمم تعداد تکرارهـا و نسـل جـاری هسـتند . همچنـین ???????????????? و ???????????????? حداقل و حداکثر مقداری هستند که هریک از وزن های خارجی دریافـت مـ ی کننـد . در الگـور یتم PSO استاندارد، جمعیت با راهحل های تصادفی، مقداردهی اولیـه می شود و تا رسیدن به شـرط خاتمـه ، شایسـتگی جمعیـت به صورت تکراری از طریـق مقـاد یر ???????????????????? و ???????????????????? محاسـبهمیشود. سـپس سـرعت و موقعیـت بـه ترتیـب بروزرسـان ی م ی ش وند. در آخ ر ه م G_best و مق دار شایسـتگی اش، به عنوان خروجی بیان م یشوند. شرط خاتمـه ممکـن اسـترسیدن به ماکزیمم تعداد نسل ها یا رسیدن به مقدار خـاص شایستگی در G_best باشد.
تنظیم پارامترها بهروش تاگوچی
کارایی الگوریتم های فراابتکاری، ارتباط مستقیمی با تنظـیم پارامترهای آن دارد بهطـوری کـه انتخـاب صـحیح مقـا دیر پارامترها، سبب افزایش کارایی الگوریتم میشود. روشهـای آماری متنوعی برای طراحی آزمایشها مطـرح شـده اسـت ، اما در استفاده از رویکرد جامعی مانند آزمایش هـای عـاملی کامل بـا افـزایش تعـداد عامـل هـا ی مـورد بررسـی ، انجـام محاسبات، پیچیده و بسیار زمانبر می شـود . تـاگوچی ]18[ دستهای از آزمایشهای عاملی کسـری را معرفـی کـرد کـه به طور شایانتوجهی تعداد آزمایشهای ضروری برای بررسی را با حفظ اطلاعات مورد نیاز، کاهش می دهد. در ایـن پـژوهش،فاکتورهای کنترلی روش تاگوچی، شامل پارامترهای الگـوریتم ژنتیک است .این پارامترهـا عبـارت انـد از: نـ رخ تقـاطع ، نـرخ جهش، ترکیب انـدازة جمعیـت اولیـه و تعـداد نسـل . سـطوح مختلف این فاکتورها در جدول های 1 و 2 مشاهده میشود.

جدول 1. فاکتورهای الگوریتم ژنتیک بههمراه سطوحشان
عامل ها نماد شاخص سطوح سطوح
نرخ تقاطع A 1 0/6
2 0/7

نرخ جهش
B 3
1 0/8
0/5
2 0/15

تعداد جمعیت و نسل
C 3
1 0/25
80×150
2 100×200
3 150×300

41910194028

1

8
/
0

2

85
/
0

1



قیمت: تومان


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