نشریه تخصصی مهندسی صنایع، دوره 49، شماره 1، بهار و تابستان 1394، از صفحه 79 تا 92
مسیریابی تجهیزات امدادی در شرایط بحران با رویکرد پوششی و
تقاضای فازی با استفاده از الگوریتم هیبریدی جست وجوی هارمونی
مهدی علینقیان1*، علیرضا گلی2، فریماه مخاطب رفیعی3 1. استادیار دانشکدة صنایع و سیستم های دانشگاه صنعتی اصفهان
کارشناس ارشد مهندسی صنایع دانشگاه صنعتی اصفهان
دانشیار دانشکدة فنی بخش مهندسی صنایع دانشگاه تربیت مدرس
)تاریخ دریافت 17/3/93ـ تاریخ دریافت روایت اصلاح شده 16/10/93ـ تاریخ تصویب 28/10/93( چکیده
یکی از اقدامات مهمی که لازم است هنگام وقوع بحران صورت پذیرد بهینه سازی نحوة توزیع و تخصیص منابع بین افراد است. زمانْ در افـاایش تعداد افراد نجات یافته توسط فعالیت های امدادی تأثیری به ساا دارد. در این پژوهش یک مدل مسیریابی وسایل نقلیة امدادی مبتنی بر مسیریابی پوشش تور در منطقة آسیب دیده توسعه داده شد. همچنین، به دلیل اینکه تعیین میاان دقیق تقاضا برای کالاهای اساسی هنگام وقـوع فجـایع، که مهم ترین آن ها داروست، بسیار دشوار و در بسیاری موارد ناممکن است و به منظور نادیک سازی مدل به شرایط واقعی عدم قطعیت تقاضا بـراساس اعداد فازی مدّ نظر قرار گرفت. به منظور صحه گذاری بر مدل ارائه شده چنـدین نمونـ ة عـدد ی بـه کمـک روش شـاهه و کـران ـل شـد .
8842259779508

همچنین یک الگوریتم فراابتکاری مبتنی بر الگوریتم جست وجوی هارمونی همراه شبیه سازی تصادفی توسعه داده شد .مقایسة نتـای اصـل ازالگوریتم ارائه شده در مقایسه با نتای اصل از روش دقیق هطای 1 درصد را برای الگوریتم نشان می دهـد . ایـن موضـوع نشـان دهنـد ة کـاراییمناسب الگوریتم ارائه شده است. به منظور بررسی الگوریتم ارائه شده در ابعاد بارگ، نتای اصـل از الگـوریتم جسـت وجـوی هـارمونی بـا نتـای اصل از ترکیب الگوریتم با الگوریتم ابتکاری GRASP مقایسه شد. بررسی ها کارایی الگوریتم ترکیبی پیشنهادی را نشان می دهد.
کلیدواژگان: الگوریتم جست وجوی هارمونی، تئوری اعتبار فازی، تور پوششی ،شبیه سازی تصادفی، لجستیک بحران.
مقدمه
منظــور ایجــاد دسترســی ســریع تــر بــرای همــة منــاطق آسیب دیده، درنظرگـرفتن عـدم قطعیـت تقاضـا بـا رویکـردتئوری اعتبار، درنظرگرفتن تابع هـد کمینـه سـازی زمـانرسیدن به آهرین مشتری، بهینه یابی اعتبار بهینة مسـئله بـاتلفیــق شــبیه ســازی و روش شــاهه و کــران و الگــوریتمجست وجوی هارمونی، و در نهایت ارائة یک روش فراابتکاری ترکیبی بر پایة الگوریتم هارمونی است.
در ادامــة مقالــه و در بخــش دوم پیشــینة موضــوع مسیریابی در شرایط بحران بررسی می شود. در بخش سوم تئوری اعتبار فازی مطرح می شود. در بخـش چهـارم مـدلریاضی مسـیریابی وسـایل نقلیـ ة امـدادی بـا رویکـرد تـورپوششــی ارائــه مــی شــود. در بخــش پــنجم الگــوریتمجست وجوی هارمونی معرفـی مـی شـود . در بخـش ششـمنتای عددی اصل از شبیه سازی، ل دقیـق ، و الگـوریتمجست وجوی هارمونی ارائه مـی شـود . در نهایـت در بخـشهفتم نتای و پیشنهادها بیان می شود. امروزه، به رغم پیشرفت های تکنولوژیکی موجود، عدم آمادگی و مقابلة مناسب با مصـائب ناشـی از سـوان طبیعـی )زلالـه ، سیل، توفان، صاعقه، بهمن، گردباد، آتش سوزی، آتشفشـان ، و …( و غیـر طبیعـی )جنـ، ـواد تروریسـتی ، تصـادفات جاده ای، واد صـنعتی، نـاآرامی هـای سیاسـی ، مهـاجرت آوارگان، و …( با تحت تأثیر قـراردادن سـه شـاهص اقتصـاد ، اجتماع، و محیط تلفات و هسارات سنگینی را بـه ملـت هـا و دارایی های آن ها وارد می کند که بعضـا جبـران ناپـذیر اسـت .
بنابراین بحران ها از موانع اصلی توسعة پایدار کشورها به شمار می رود و از اولویـت هـای برنامـه هـای هـر کشـور محسـو می شود. لجستیک بحران به فرایند برآورد، تأمین، مل ونقل، نگه داری، و توزیع کالاها و هدمات مورد نیاز در بحران گفتـه می شود که به جهت داشتن نقشی اساسی در کل این زنجیرة تأمین یکی از عوامل شاهص اثرگـذار در موفقیـت مـدیریت بحران است ]1[.
از نوآوری های این پژوهش ارائة یک مدل ریاضی جدیـد
مبتنی بر پوشش تور برای مسیریابی امدادی1)DRVRP( بـه
Email : [email protected] 03133915526 :نویسنده مسئول تلفن: 03133915511، فکس *
پیشینة موضوع
تحقیقات در زمینة مل ونقل اقلام امدادی را اولین بار نات در سال 1987 انجـا م داد. نـات بـا دراهتیارداشـتن منـابعمحدود به مدل سازی شرایطی پرداهت که در آن تعدادی از وسایل نقلیـ ة متفـاوت در یـک انبـار قـرار داشـت و هـد کمینـه سـازی تقاضـاهای ازدسـت رفتـه بـود ]2[. هانـ و همکــاران الــت چنــدکالایی را بــرای امدادرســانی بــهنیازمندان در شرایط بحران در نظر گرفتند و به هر یـک از کالاه ا وزن ی تخص یص دادنـد و می انگین وزن دار زم ان رسیدن هر کالا به نقاط آسیب دیده را ـداقل کردنـد ]3[.
مت و زابینسکی هاینة ایجاد انبار در نقاط آسـیب دیـده راهمراه کل زمان رساندن کالا به این انبارها در مدل هود در نظر گرفتند ]4[. نولا و همکاران زمان رسیدن بـه آهـریننقطة آسیب دیده را در التی داقل کردند کـه بیشـترینتقاضای ممکن برآورده شود ]5[.
به جهت اهمیت عدم قطعیت در مدیریت بلایا، تعدادی از محققان به بهینه سازی تصادفی در برنامه ریای امداد بلایا توجه کردند. ژو و همکاران عرضة کالا در شرایط بحـران را پارامتری تصـادفی در نظـر گرفتنـد . آن هـا در فـاز اول بـهمکان یـابی انبارهـای میـانی قبـل از وقـوع بلایـا و تعیـینظرفیت آن ها بدون دهالـت دادن تقاضـا پرداهت نـد ]6[. در فاز دوم هنگام وقوع بلایا بـه مسـیریابی وسـایل نقلیـه، بـهمنظور انتقال کالاها از انبارهای میانی به منـاطق نیازمنـد ، پرداهتند. شن و همکاران در سال 2009 تقاضـای منـاطقآسیب دیـده را غیـر قطعـی در نظـر گرفتنـد. آن هـا نیـا ازرویکرد دومر له ای بـرای مقابلـه بـا عـدم قطعیـت تقاضـااستفاده کردند. در مر لة اول مسیر رکـت وسـایل نقلیـهتعیین و در مر لة دوم میاان کالای تحویلی به هـر نقطـ ة تقاضا مشخص می شود ]7[.
اسـتفاده از ت ور پوششـی رویک ردی اسـت ک ه بره یمحقق ان در زمین ة امدادرس انی هنگ ام بح ران ب ه ک ار گرفته اند .نکتة قابل توجه در این زمینه آن است کـه اکرـرتحقیقات شـعاع پوشـش بسـیار کـوچکی را مـد نظـر قـرارداده اند تـا تقاضـای افـراد در کوتـاه تـرین فاصـله از آن هـابرآورده شود. در کنـار مسـیریابی بـه روش تـور پوششـی،مکان یابی مراکا امدادرسانی و مراکا توزیع کالاهـای مـوردنیاز انجام می شود. در برهی تحقیقات ایجاد این مراکـا بـهصورت سرپایی مطرح اسـت تـا در کمتـرین زمـان ممکـنا دا و راه اندازی آن ها صورت گیرد.
عظیم ی و همک اران در س ال 2012 م دلی را ب رای مکان یابی نقاط امداد و مسـیریابی تجهیـاات تـ أمین ارائـهکردند. آن ها اعلام کردند که در بسیاری از موارد تجهیـااتامدادی نمی توانند از همة نقـاط بازدیـد کننـد. بـه همـیندلیل نقاط امدادی را در فاصلة کمی از آن ها قرار دادنـد تـاافراد نیازمند، هود، به این مراکا مراجعه و کالای مورد نیاز هود را دریافت کنند .همة تقاضـا ها بایـد بـرآورده شـوند و نقاط امدادی به گونه ای بایـد مکـان یـابی شـوند کـه نقـاطتقاضا در فاصله ای کمتـر از ـداکرر فاصـل ة مجـاز )شـعاعپوشش( از یک مرکا امدادی قرار گیرند. هـد ایـن مـدلمسیریابی وسایل نقلیه این است که کل مسافت طی شده با وسایل نقلیه داقل شود ]8[.
در این پژوهش از مسـیریابی پوشـش تـور بـه منظـورمسیریابی در شـرایط بحـران بهـره بـرده شـد. آنچـ ه ایـنپژوهش را از سایر پژوهش ها متفاوت می کند عبارت اسـتاز 1. درنظرگرفتن عدم قطعیت تقاضا که در شرایط بحـرانیک فرض انکارناپـذیر اسـت؛ 2. درنظرگـرفتن تـابع هـد کاهش زمان رسیدن وسایل نقلیه به آهـرین گـره امـدادیبازدیدشــده؛ 3. یــافتن ســط اعتبــار بهینــه بــا ترکیــبش بیه س ازی ب ا روش دقی ق ش اهه و ک ران و الگ وریتمهارمونی؛ و 4. ارائة الگوریتم فراابتکاری ترکیبی مبتنـی بـرالگوریتم جست وجوی هارمونی.
تئوری فازی و معیار اعتبار2 فازی
یک مجموعة کلاسیک به طور عادی مجموعه ای از اعضـایآن تعریف می شود. هر داده به تنهایی مـی توانـد عضـو ایـنمجموعه باشد یا نباشد. در نتیجه، عضویت یا عدم عضـویتهر داده به وضوح مشخص است. اما در برهـی مجموعـه هـاعضویت بـ ا قطعیـت همـراه نیسـت. در برهـورد بـا چنـینمجموعه هایی از تئـوری فـازی اسـتفاده مـی شـود. تئـوریمجموعة فازی را ابتدا زاده ]9[ معرفی کرد و بـرای مسـائلگوناگون توسعه داده شد. لی ]10[ در تحقیقـات هـود بـهتئوری اعتبار پـی بـرد. در ایـن قسـمت بـه طـور مختصـرمفاهیم اساسی مجموعة فازی و اندازه گیری فـازی معرفـی می شود. ابتدا اصول معیار امکان3 معرفی می شود که پایه و اساس مفهوم اعتبار است.
 را مجموعه ای غیر تهی و (P( را توان مجموعة
 در نظر بگیرید. هر عضو (P( یـک رهـداد نامیـدهمی شود. همچنین  را یک مجموعة تهی در نظر بگیرید .برای هر رهداد A، که ( )A P است، عدد غیر منفی
{}pos A وجود دارد که از چهار اصل پیروی می کند:
Pos{ }  0 .1 اصل
Pos{ } 1 .2 اصل
اصــل 3. بــرای هــر زیرمج موعــة دلخــواه {AK } از مجموعة (P( رابطة 1 برقرار است:
Pos{k Ak } sup (k Ak ) )1(
سه تـایی ( , (P),Pos) فضـای امکـان نامیـدهمـی شـود و تـابع {}pos معیـار سـنجش امکـان معرفـیمی شود.
اصل 4. اگر i یک مجموعة غیـر تهـی باشـد و تـابعPosi {} i 1,2,…,n دارای سـه اص ل ف وش باش د و
   12…n، آنگـــاه بـــرای هـــرA در
(P( رابطة زیر برقرار است:
Pos A{ }Sup(1,.., n ) A Pos1{ 1} Pos2
{  2}…Posn{n } )2(
به کمک چهار اصل فوش می توان اساس معیار امکان را تشکیل داد و همة مفاهیم امکـان را از آن هـا مشـتق کـرد.
بدین منظور دو تعریف ارائه می شود:
تعریف 1. ( , (P ),Pos ) را فضـای امکـان وA را مجموعه ای در (P( در نظـر بگیریـد. آن گـاه معیـارالاام4 به صورت رابطة 3 تعریف می شود:
Nec A{ } 1 Pos A{ C } )3(
تعریف 2. ( , (P ),Pos ) را فضـای امکـان وA را مجموعه ای در (P( در نظـر بگیریـد. آن گـاه معیـار اعتبار به صورت رابطة 4 تعریف می شود:
Cr A{ }

(Nec A{ }Pos A{ }) )4(
179046873419

466276-25978

اگر تابع D( )x عضـویت پـارامتر فـازیD باشـد ، برای رهداد} D r { امکان، الاام، و اعتبـار بـه صـورتزیر هواهد بود:
Pos D r{  } supx r D ( )x )5(
333899-282759

1
2

1

2

Nec D r{   } 1 supx r D ( )x )6(

)7( ({Cr D r{  } (Pos D r{  } Nec D r{  در اینجا اعتبار یک رهداد فازی میانگین امکان و الـاامآن رهداد تعریف شده است. یک رهداد فازی ممکن اسـتشکست بخورد، تی اگر امکان رخ دادن آن برابر 1 باشد. و ممکن است اتفاش بیفتد، تـی اگـر الـاام آن 0 باشـد. بـههمین دلیل معیار اعتبار از ترکیـب ایـن دو تـابع اسـتفادهمی کند و در اصل نقش ا تمال رهداد را در شـرایط فـازیایفا می کند ]12،11[.
(x d1)
(d2 d1) d1  xd2

218577-384649

D( )x 1(d3 x )xd2 dx2d3 )8(
(d3 d2)

0otherwise

بر این اساس، تقاضای یـک مشـتری از 1d کمتـر و از 3d نی ا بیش تر نیس ت و 2d معق ول ت رین مق دار ب رای تقاضای مشتری است. بر اساس تعاریف فوش توابع امکـان والاام و اعتبار به صورت زیر بازنویسی می شود:
1if r d2

400325-52949

Pos D{  r} d3 r
d3 d2 0
 if d2  r d3 if r d3 )9(
1 
422385-55725

Nec D{  r} d2 r d2 d1 0
 if r d1 if d1  r d2 if r d2 )10(
1 if r d1 2d2  d1rif drd
 294534-44346

Cr D{  r}  2(d2 d1)1   2 )11(
d3 r
if d2  rd
2(d3 d2)3
0تعریف مسئله
16783845100192

یکی از اقدامات بسیار مهم که لازم است هنگام فـاز پاسـخ بحران صورت پذیرد بهینه سازی نحـو ة توزیـع و تخصـیص منابع بین افراد است .در این مدل هد تعیین مراکا امداد مناسب در منطقة آسیب دیده و مسیریابی وسایل نقلیه بـهمنظور تأمین تقاضای این مراکا است. این مراکا مـی توانـددر یکی از نقاط آسیب دیـده یـا در محلـی بیـرون از آن هـامستقر شود. بنابراین، مدل ارائه شده مناسب ترین سیاسـت امدادرسانی را در زمانی کـه بـرآورده سـاهتن نیـاز نـوا ی آسیب دیده به دو شکل ملاقات مستقیم یـا تحـت پوشـش قرارگرفتن امکان پذیر است پیشـنهاد مـی دهـد . بـه عبـارت دیگر، تقاضای نقاط مـی توانـد در همـان مکـانی کـه واقـع شده اند تحویل داده شود یا به مکان دیگری که در فاصله ای معقول قرار گرفته است برده شود تا افراد با پیمودن مسیری کوتاه کالای امدادی را دریافت کنند .وظیفـ ة مراکـا امـدادبرطــر ســاهتن تقاضــای افــراد آســیب دیــده در نقــاط آسیب دیده برای کالاهـای ضـروری و داروهـای مـورد نیـازاست. از طر دیگر، تأمین کـالای مـورد نیـاز ایـن مراکـاامداد از طریق دپوی مرکای صورت می گیـرد. ایـن کالاهـاتوسط وسایل نقلیه با ظرفیت مشخص به نقاطی که مراکـاامداد در آن ها برپا شده رکت می کنند و با تشـکیل یـک تور مشخص پس از عبور از چند نقطة دریافت کـالا دوبـاره به دپوی مرکای برمی گردند. همچنین در بسیاری از فجایع تعیین مقدار دقیق کالای مورد نیاز )تقاضـا( کـاری بسـیاردشوار است. بنابراین در ایـن پـژوهش تقاضـای هـر نقطـ ة آسیب دیده را عددی فازی با تابع عضویت مرلری به صورت (di  (d d d1i , 2i , 3i در نظر می گیـریم. از آنجـا کـه درفجایع برطر سازی فوری نیازهای اولیة افراد آسیب دیده و تــأمین کالاهــای درمــانی آن هــا اهمیتــی ویــژه دارد، در مسیریابی وسایل نقلیه برای این مسئله هد کاهش زمـانرسیدن کالاهای مورد نیاز به نقاط امدادرسانی است.
فرضیات
فرضیات این مدل در پی می آید.
ـ تابع هد مدل ارائه شده کمینه کردن زمـان رسـیدنکالا به آهرین نقطة امدادرسانی است.
ـ مدل تککالایی است. در واقع امکان یکپارچـه سـازیکالاها وجود دارد.
ـ هر مرکا امداد فقـط از یـک وسـیلة نقلیـ ه کـالا دریافـتمی کند.
ـ نقاط تحت پوشش کالای مورد نیـاز هـود را فقـط از یک نقطة ملاقات شده دریافت میکنند.
ـ تقاضای هر نقطة آسیب دیده از ظرفیت وسایل نقلیـهکمتر است.
ـ کل تقاضای همة نقاط آسیب دیده باید برآورده شود.
ـ به منظور رساندن کالاها در اسرع وقت از همة وسایل نقلیة موجود استفاده می شود.
ـ وسایل نقلیه به جـا در مراکـا امـداد در هـی نقطـ ة دیگر توقف ندارند.
ـ وسایل نقلیه همسان اند. به عبارت دیگر، ظرفیت همة آن ها یکسان و زمان طی کردن یک مسیر بین همة وسـایلنقلیه یکسان است.
ـ هر نقطه داکرر توسـط یـک وسـیل ة نقلیـه بازدیـد میشود.
ـ از زمان بارگیری و تخلیة صر نظر می شـود و زمـانرسیدن یک وسیله به نقطة مشخص برابر زمان طـی کـر دن مسیر رسیدن به آن نقطه است.
ـ یکسری نقاط کاندید ایمن با شرایط تأسیس مراکـا
امداد بین نقاط آسیب دیده وجود دارد و این مراکا می تواند در نقاط آسیب دیده یا در نقاط میانی تأسیس شود.
مجموعه ها
‘R: تعداد کل نقاط R ‘ 1,2,…R R, 1 نقطة 1 دپو و نقطة R+1 نقطة مجازی است.
‘n: مجموعة نقاط ادثه دیده {n R n’  , ‘ {1,…,n
k: مجموعة وسایل نقلیهk 1,2,…,K پارامترها
2456180401110

tlm: مدت زمان طی کردن فاصلة بین دو نقطـ ة l و m بـا هر یک از وسایل نقلیه {l m, {0,1,2,..,R di: تقاضای فازی نقطة iام {i {1,2,..,n dismax: داکرر شعاع پوشش
ail: پارامتر باینری که برابر 1 هواهد بـود اگـر فاصـل ة نقط ة تقاض ای iام و نقط ة lام کمت ر از dismax باش د {l {1,2,..,R}،i {1,2,..,n Qk: ظرفیت وسیلة نقلیة k ام{k {1,2,…,K
M: عدد هیلی بارگ متغیرهای تصمیم
xlmk: برابر 1 هواهد بود اگر مسیر بین دو گره l و m با وسیلة mام طی شود. در غیر این صورت برابر 0 هواهد بود
k{1,2,…,K }، l m, {1,2,..,R}1
CDl: تقاضای جمع شده در نقطة l {1,2,..,R} l
yl: برابر 1 هواهد بود اگر نقطة l با یکی از وسایل نقلیه بازدید شود. در غیر این صورت برابر 0 هواهد بود {k{1,2,…,K }،l{1,2,..,R
Dil: برابر 1 هواهد بود اگر برآورده سازی تقاضای نقطة i به نقطة بازدیدشدة l واگذار شود. در غیر این صورت برابر 0 هواهد بود {l{2,3,..,R}،i{1,2,..,n{k{1,2,…,K
ulk: زمان رسیدن وسیلة نقلیةk ام به نقطة k{1,2,…,K }،l{1,2,..,R}l
Z: زمان رسیدن کالا به آهرین مرکا امداد مستقرشده مدل ریاضی
در این بخش مدل ریاضی تشری می شود.
Minimize Z  max {l k,ulk } )12(
Subjectto
KR
xijk  y j j=2,…,R
k1 i1 )13(
R
x1 jk 1  kK
j2 )14(
R1
xi k1 0  kK
i1 )15(
R
xi R( 1)k 1  kK
i2 )16(
KR1
x( R1) jk 0  kK
k 1 j 1 )17(
RR1
 xilk  xljk   0l2,…,R k, K i1j2 )18(
R
a Dijij   1iAf
j2 )19(
a Dijij  yj  j2,…, , Rin )20(
210103-96936

d Diij CDj  j2,…,R
i n )21(
RR1
CD xiijk Q  kK
i 2 j 2 )22(
yi  Diiin )23(
K
u1k 0
k1 )24(
ulk  tlmumk M(1 xlmk )
l 1,2,…,R1 m 1,2,…,R1
k 1,2,…,K )25(
xlmk , y Dl ,il {0,}1
l m, 1,2,…,R1
k 1,2,…,K )26(
CD ul , lk  0 i  1,2,…,n l 1,2,…,R )27(
k  1,2,…,K
رابطة 12 تابع هد مدل است که کمینـه کـر دن زمـانرسیدن بـه آهـرین منطقـة امـدادی در آن مـد نّظـر اسـت.محدودیت 13 بیان می کند که وسایل نقلیه فقـط از نقـاطیکه مراکا امدادی موقـت در آن هـا تأسـیس شـده انـد عبـورمی کنند. محدودیت 14 و 15 بیان می کنند که همة وسـائطنقلیه باید از دپو هارج شوند و امکان بازگشت وسـائط نقلیـهبه دپو وجود ندارد. محدودیت های 16 و 17 بیان می کند که همة وسائط نقلیه باید به گـره مجـازی) R+1( وارد شـوند وهی وسیله ای نبایـد از ایـن گـره هـارج شـود. دربـارة گـرهمجــازی در بخــش «گــره مجــازی» توضــیحاتی مــی آیــد.
محدودیت 18 بیان می کند که اگر وسیلة نقلیـه ای بـه یـکگره وارد شود، باید از آن هارج شـود . محـدودیت هـای 19 و 20 بیان می کند هر نقطة دارای تقاضـا بایـد بـه یـک مرکـاامداد موقت در فاصلة پوشش آن تخصیص یابـد. محـدودیت21 تقاض ای جم ع ش ده در ه ر ی ک از مراک ا را محاس به می کند. محدودیت 22 مربوط به ظرفیت وسائط نقلیه است.
محدودیت 23 به این موضوع اشاره می کنـد کـه اگـر نقطـةبازدیدشده تقاضا داشته باشد، نباید تقاضای هـود را از مرکـادیگری که در فاصـلة پوشـش آن قـرار گرفتـه تـأمین کنـد.محدودیت 24 زمان هروج وسایل نقلیه از دپـوی مرکـای رابرابر 0 در نظر می گیرد .محـدودیت 25 زمـان رسـیدن هـروسیلة نقلیه را به نقاطی کـه در تـور آن قـرار دارد محاسـبهمی کند. همچنین، این محدودیت باعـ ـذ زیرتورهـایغیر مجاز برای هر وسیلة نقلیه می شود .رابطه هـای 26 و 27 نوع متغیرهای تصمیم را مشخص می کند.
گره مجازی
به منظور مدل سازی مسئلة مطرح شده به طـور ابتکـاری ازیک گره مجازی) R+1( بهره بـرده شـد. فاصـل ة ایـن گـرهنسبت به همة نقاط برابر صفر اسـت و همـة وسـایل نقلیـهپس از عبور از نقاط تعیین شده به مبدأ برنمی گردند؛ بلکـهبه این گره مجازی می روند. با استفاده از این نـوآوری ، ایـنامکان به وجود آمـد کـه تـابع هـد کمینـه کـر دن زمـانرسیدن به آهرین نقطة امدادی مد نظر واقع شـود. گفتنـی است برای هر وسیلة نقلیه مدت زمّان طی تور برابـر زمـانرسیدن آن به گره مجازی R+1 در نظر گرفته می شود.
خطی سازی مدل
به دلیل غیرهطی بودن تابع هـد کمینـه سـازی ـداکررزمان رسیدن به مناطق تابع هد معادلة 12 با معادلـ ة 28 جایگاین می شود. محدودیت 29 نیـا بـه محـدودیت هـایمدل اضافه می شود.
Min Z )28(
Z  ulk l 1,2,…,R k 1,2,…,K )29(
به منظور ل مدل فوش، با توجه به فازی بودن پـارامترتقاضا، فاکتور cr را در بازة 1[ ,0] تغییر می دهـیم و سـپسبا توجه به رابطة تابع اعتبار میاان تقاضای هر یک از نقـاطتعیین مـی شـود و بـا اسـتفاده از الگـوریتم جسـت وجـویهارمونی و نیا سـولورCLPEX بهتـرین جـوا ممکـن بـاتوجه به پارامتر cr تعیین می شود.
روش حل
در این قسمت روش های ل استفاده شده در ل مدل، که شامل الگوریتم جست وجـوی هـارمونی پیشـنهادی و روش ابتکاری است، تشری می شود. سپس، رشتة اسـتفاده شـدهدر الگــوریتم بیــان مــی شــود. در نهایــت، نحــوة تنظــیم پارامترهای الگوریتم می آید.
الگوریتم جست وجوی هارمونی
الگوریتم جست وجوی هارمونی )HS( به دلیل کاربردی بودن بـرای مسـائل بهینـه سـازی گسسـته و پیوسـته ، محاسـبات ریاضیاتی کم، مفهوم ساده، پارامترهای کم، و اجرای آسان به یکی از الگوریتم های پرکاربرد بهینه سازی در سال های اهیـر در مسائل مختلف تبدیل شده اسـت ]13[. ایـن الگـوریتم در مقایسه بـا سـایر روش هـای فراابتکـاری الاامـات ریاضـیاتی کمتری دارد و می توان آن را در مسائل مختلف مهندسـی بـا تغییر در پارامترها و عملگرها تطبیق داد ]13[.
گام های الگوریتم جست وجوی هارمونی
پارامترهای الگوریتم جست وجـوی هـارمونی عبـارت انـد ازتعداد بردارهای راه ل در افظة هـارمونی )HMS(5، نـرخدرنظرگ رفتن افظ ة ه ارمونی )HMCR( 6، ن رخ تنظ یم دان صدا )PAR(7، فاصـل ة پهنـای بانـد )BW(8، و تعـدادبداهه سرایی ها) NI .9)NI با تعداد کل تکرار برابر اسـت . در این الگوریتم هر ل یک هارمونی نامیده می شود و با یـکبــردار N مؤلفــه ای نمــایش داده مــی شــود .الگــوریتم جست وجوی هارمونی دارای افظة ذهیره سـازی ، بـه نـام افظ ة هـارمونی) HM(10، اس ت؛ ک ه ش امل برداره ای هارمونی افظة هارمونی است. بردارهای هارمونی و مقادیر تابع هد متنـاظر در افظـ ة هـارمونی بیـان و بـه منالـة ماتریس در )30( ذهیره می شود.
34290-254251

)30(

این الگوریتم سه فاز اصلی دارد:
1. نســل اولیــه )مقــداردهی اولیــه(؛ 2. بهبــود بــردار هارمونی جدید؛ 3. به روزکردن افظة هارمونی.
در فاز اول، یک نسل اولیه از بردارهای هارمونی به طور تصادفی ایجاد و در افظة هارمونی )HM( ذهیره می شود.
در فاز دوم ،بردار هارمونی جدیـد X new بـا اسـتفاده ازسـه قـانون اصـلاح مـی شـود : ملا ظـ ة افظـه 11، تنظـیمدان 12، انتخا تصادفی13. اول، عدد تصادفی یکنواهـت 1r در مح دودة ]1، 0[ ایج اد ش ده اس ت. اگ ر 1r کمت ر از HMCR باشد، متغیر تصمیمگیری با ملا ظة افظه ایجاد می شود. در غیر این صورت، xnew (k) با انتخـا تصـادفیبه دست می آید )مقداردهی مجدد بین مرزهای جست وجو انجام می شود(. xnew (k)، در ملا ظة افظـه، از هـر بـردارهارمونی i در 1، 2، …، HMS انتخـا مـی شـود. بعـد، هـر مقدار xnew (k) را می توان با مقادیر هو ذهیـره شـده، بـاا تمال PAR، تنظیم کرد ]13[..
for (j=1 to n) do if (r1< HMCR) then Xnew(j) = Xa(j) where a

(1,2,…,HMS) if (r2< PAR) then Xnew(j) = Xnew(j) + r 3 × BW where r1,r2,r3

(
(0,)1 end if else Xnew(j) = LBj + r × (UBj -LBj), where r

( (0,1) end if end for شبه کد تولید هارمونی جدید
در ف از س وم، ه ارمونی جدی د تولیدش ده ب ا ب دترین هارمونی موجود در افظة هارمونی مقایسه مـی شـود. اگـربردار هارمونی جدید مقدار تـابع هـد بهتـری نسـبت بـهبدترین بردار هارمونی موجود داشته باشد، هارمونی جدیـدبه افظة هـارمونی اضـافه و بـدترین هـارمونی از افظـ ة هارمونی ذ می شود.
تنظ یم پارامتره ای الگ وریتم جس ت وجیوی هارمونی
به منظور استفاده از الگوریتم جست وجوی هارمونی،مقـدارپارامترهای این الگوریتم، از روش سعی و هطا و ـل سـهمسئلة نمونه و با توجـه بـه میـانگین جـوا هـای اصـله، تنظیم شده است. تنظیم پارامترها در جدول 1 می آید.

جدول 1. مقدار تنظیم شده برای پارامترهای الگوریتم
پارامتر مقدار تنظیم شده
اندازة افظة هارمونی )HMS( 1000
نرخ انتخا از افظة هارمونی )HMCR( 0/9
نرخ تنظیم گام )PAR( 0/1
پهنای باند )BW 0/01
تعداد تکرار الگوریتم (NI) 10000
الگوریتم بهبوددهنده
هنگام اجرای الگوریتم جست وجوی هارمونی، از رویکـر دی ابتکاری به منظور بهبود جوا های به دسـت آمـده اسـتفادهمی شود. رویکرد ابتکاری درنظرگرفته شده بـر مبنـای روش
.]14[ است GRASP
الگوریتم GPASP یک الگوریتم فرااکتشافی ساده است که اکتشافات ساهتاری و جسـت وجـوی محلـی را ترکیـبمی کند. ساهتار آن رویه ای تکـراری شـامل دو فـاز اسـت:
ســاهت راه ــل و بهبــود راه ــل .هنگــام اتمــام رویــ ة جست و جو، بهترین راه ل یافته شده برگردانده می شود.
به منظور اسـتفاده از الگـوریتمGRASP از فـاز تولیـدجــوا اولیــه صــر نظــر و از هروجــی هــای الگــوریتمجست وجوی هارمونی استفاده می شود. همچنین، به منظور اجرای فاز جست وجوی محلی، از شش روش جست وجو به منظور بهبود جوا های در دست اسـتفاده مـی شـود . ایـنشش روش عبارت است از:
انتقال نقاط: یک نقطة ملاقـات شـده همـراه همـة نقاطی که تحت پوشش آن است به تور دیگـری تخصـیصمی یابد.
تعويض نقاط در داخل مسلیر : جـای دو نقطـ ة ملاقات شده داهل یک مسیر تعویض می شود.
تعلويض نقلاط در د مسلیر: جـای دو نقطـ ة ملاقات شده در الت کلی عوض می شود.
تخصیص نقاط: امکان پوشـش مجـدد یـک نقطـ ة پوشش داده شده به جایی مناسب تر بررسی می شود.
جابه جايي نقاط: امکان جابه جایی یک نقطة تحـتپوشش را با نقطـ ة پوشـش دهنـد ة آن )نقطـ ة بازدیدشـده( بررسی می کند.
پوشش نقطة ملاقات شده: یک نقطة ملاقات شده از مسـیر هـود بیـرون کشـیده و بـا بهتـرین نقطـ ة ممکـنپوشیده می شود.
الگوریتم بهبوددهنده بر منبای GRASP در هر مر لـهاز الگوریتم و بر هر یک از جـوا هـای )هـارمونی( افظـة هارمونی بهبودهای ممکن را به وجود می آورد.

شک

1
.

نقاط

انتقال

از

مثالي



قیمت: تومان


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