توضیحات

 

پروژه متلب مسئله مسیریابی خودرو ظرفیت دار(VRP) با پنجره زمانی به منظور جمع آوری زباله با استفاده از الگوریتم شبیه سازی تبرید(SA)

 

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

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

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

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

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

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

مسئله مسیریابی خودرو:

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

الگوریتم شبیه سازی تبريد:

الگوریتم شبیه سازی تبرید،یکی از الگوریتم های فراابتکاری الهام گرفته از طبیعت می باشد. این الگوریتم برخلاف سایر اكثر الگوریتم های الهام گرفته از طبیعت مبتنی بر جمعیت و هوش دسته جمعی نیست و از طرفی بیشتر بر پایه اصول احتمال می باشد.

پسماند:

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

۱) زباله های شهری که شامل زایدات غذایی، آشغال، خاکستر، زایدات ویژه و زایدات ناشی از تخریب و ساختمان سازی می شود.

۲) زباله های صنعتی: مواد زاید ناشی از فعالیت های صنعتی هستند و معمولا شامل فلزات، مواد پلاستیکی، مواد شیمیایی خطرناک هستند که عمل جمع آوری، حمل و نقل و دفع آنها ضوابط خاص و مقررات ویژه ای را به خود اختصاص داده است.

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

جمع آوری پسماند :

جمع آوری پسماند تفکیک نشده (مخلوط) و تفکیک شده در یک منطقه شهری مشکل است؛ زیرا پسماند مسکونی و تجاری- صنعتی در هر خانه و مجتمع آپارتمانی و همه تاسیسات تجاری و صنعتی و نیز خیابان ها، پارکها و حتی مناطق خالی از سکنه، تولید می شود. توسعه قارچ مانند حومه شهرها در سراسر کشور، عملیات جمع آوری را پیچیده تر می کند.

با گسترده تر شدن الگوی تولید پسماند و افزایش مقدار تولید آن، تدارکات و سازماندهی جمع آوری آن پیچیده تر می شود. اگر چه این مشکلات همواره در درجه های مختلف وجود داشته است، اما امروزه به دلیل هزینه های بالای سوخت و کارگر، این مشکلات بحرانی تر شده است. در یک برآورد در سال ۱۹۹۰ در آمریکا، مشخص شد که بین۵۰ تا ۷۰ درصد هزینه های مدیریت پسماند به مرحلهی جمع آوری اختصاص می یابد.

اهمیت این موضوع از آن جهت است که بهبود اندکی در عملیات جمع آوری می تواند تاثیر قابل ملاحظه ای در صرفه جویی هزینه های کل داشته باشد.

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

مسئله فروشنده دوره گرد(TSP):

یکی از بنیادی ترین و مشهورترین مسائل حمل و نقل، مسئله فروشنده دوره گرد می باشد. در این مسئله تعدادی شهر وجود دارد. یک فروشنده دوره گرد می خواهد به تمامی این شهرها برود، به طوری که حرکت خود را از یک شهر شروع کرده و در پایان به همان شهر بازگردد. همچنین به هر شهر فقط یک بار می تواند برود و هزینه کل سفر (می تواند مسافت، زمان و … در نظر گرفته شود) فروشنده کمیته شود. فروشنده دوره گرد شکل زیر نمونه ای از یک مسئله فروشنده دوره گرد را نشان می دهد.

شکل مسئله فروشنده دوره گرد.

اگر به جای یک فروشنده، چند فروشنده داشته باشیم. مسئله ی چندین فروشنده دوره گرد(MTSP) خواهد شد.

 

شکل زیر نمایی از مسئله چند فروشنده دوره گرد را نشان می دهد.

شکل مسئله چند فروشنده دوره گرد.

 

مسئله کلاسیک مسیریابی خودرو(VRP)

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

این مسئله نخستین بار توسط دانتزیک و رامسر مطرح شد. شبکه را می توان با گراف G(E,V) نشان داد که V={0,1,…,n} مجموعه ای از گره ها است که گره صفر نشان دهنده انبار است و بقیه مشتری هستند. مجموعه E مجموعه ای از یالها است. هر یال نشان دهنده این است که مسیر از یک گره (شروع بال) به گره دیگر (انتهای بال) وجود دارد. برای هر یال یک وزن وجود دارد که معمولا با C_ij نمایش داده می شود. اگر C_ij=C_ji مسئله متقارن است.

شکل زیر نمایی از مسئله مسیریابی خودرو را نشان میدهد. مسئله مسیریابی خودرو از جمله مسائل ترکیبی به شمار می رود.

شکل مسئله مسیریابی خودرو.

 

فرض های مسئله کلاسیک مسیریابی خودرو: 

• هریک از خودروها در صورت انتخاب حرکت خود را از انبار شروع می کند و با طی یک تور در انتها به انبار باز می گردد.
• هر گره فقط یک بار بازدید می شود.
• تمام تقاضای یک گره در یک بازدید باید بر آورده شود.
• تقاضای کل مشتریان ملاقات شده توسط یک خودرو، از ظرفیت خودروها تجاوز نکند.

مسئله مسیریابی خودرو در شکل کلاسیک به مسئله مسیریابی خودرو با محدودیت ظرفيت (CVRP) هم معروف است. اگر ظرفیت خودروها برابر باشد به آن مسئله مسیریابی خودرو ظرفيت دار همگون و در غیر این صورت به آن مسئله مسیریابی خودرو ظرفیت دار ناهمگون می گویند.

در ادبیات نظری ثابت شده است که مسئله TSP مربوط به کلاس مسائل NP-Hard است و به این علت مسئله VRP نیز که تعمیمی از مسئله TSP می باشد نیز متعلق به همین کلاس مسائل می باشد. از این رو برای حل اینگونه مسائل از روش های ابتکاری و فراابتکاری استفاده می شود.

مسئله مسیریابی خودرو ظرفیت دار با پنجره های زمانی

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

مسئله ی مسیریابی دوره ای خودرو (PVRP)

در مسئله کلاسیک مسیریابی خودرو سرویس دهی به مشتریان در یک روز یا یک دوره در نظر گرفته می شود؛ اما با گذشت زمان و تغییر در درخواست مشتریان در شیوه سرویس دهی نوع دیگری از مسئله ی مسیریابی خودرو با پنجره – زمانی به نام مسئله مسیریابی دوره ای خودرو با پنجره زمانی توسعه داده شد که در آن بازه خدمت دهی به مشتریان به جای یک روز در یک بازه زمانی چند روزه در نظر گرفته می شود. در این مسئله هر یک از مشتریان روزهای مورد نظر خود را برای خدمت دهی مشخص می کنند. علاوه بر این مشتریان می توانند ترکیبی از روزهای دوره را برای سرویس دهی انتخاب کنند.

 

شکل مسئله ی دوره ای مسیریابی خودرو.

 

مسئله مسیریابی خودرو چند سفره( TVRPM ):

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

انواع مسائل بهینه سازی:

مسائل بهینه سازی را می توان به چهار روش دسته بندی کرد:

1) دسته بندی براساس تابع هدف و نوع آن: یک هدفه یا چند هدفه،

۲) دسته بندی بر اساس محدودیت: مقید یا نامقید،

۳) دسته بندی براساس متغیرها: پیوسته، گسسته – عدد صحیح و ترکیبی،

۴) دسته بندی بر اساس ویژگی های توابع: مشتق پذیریا مشتق ناپذیر، محدب یا غير محدب، خطی یا غیرخطی.

 

شکل دسته بندی مسائل بهینه سازی.

 

الگوریتم شبیه سازی تبرید(SA):

شبیه سازی تبرید، اولین بار در سال ۱۹۸۳ توسط کرک پاتریک و همکارانش و سپس در سال ۱۹۸۵ به طور مستقل توسط چرنی با الهام گیری از اتفاقاتی که در فرآیند ذوب و انجماد فلزات در ابعاد ملکولی اتفاق می افتد پیشنهاد گردید.

در واقع آنها ایده اصلی خودر را از الگوریتم میروپولیس – هستینگز که برای تعیین حالت اتم ها در یک سیستم ترمودینامیکی به کار می رود، گرفته اند. متروپولیس و همکارانش در سال ۱۹۵۳ این الگوریتم ساده را برای شبیه سازی موثر مجموعه ای از اتم ها که در دمای معین در حالت تعادل قرار دارند پیشنهاد دادند.

در هر تکرار از این الگوریتم جابجایی اندکی به طور تصادفی به هر یک از اتم ها اعمال میشود. با این جابجایی انرژی درونی سیستم نیز تغییر می کند. بعد از جابجایی انرژی درونی سیستم را محاسبه می کنند. اگر انرژی درونی کمتر از حالت قبل بود این آرایش جدید قابل قبول است. در غیر این صورت اگر u را اختلاف انرژی درونی فعلی سیستم با انرژی درونی قیلی سیتم در نظر بگیریم احتمال p(u) از رابطه زیر محاسبه میشود:

p(u) = exp(-u / (T*k_b ))

کهk_b ثابت بولتزمن وT دما برحسب درجه کلوین است. برای رد یا قبول این احتمال چون تابع بالا برای اعداد مثبت بین صفر و یک قرار دارد یک عدد تصادفی در بازه (0،1) انتخاب می کنیم. حال اگر عدد تصادفی انتخاب شده کمتر از حاصل مقدار p(u) باشد چینش جدید اتم ها را می پذیریم. در الگوریتم شبیه سازی تدریجی ثابت بولتزمن برابر با یک در نظر گرفته میشود. انرژی درونی همان مقدار تابع هدف میباشد. همچنین جابجایی اندک را همان همسایگی حالت قبلی در نظر می گیرند.

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

از این الگوریتم می توان برای مسائل ترکیبی مانند مسئله فروشنده دوره گرد و مسائلی نظیر این مسائل استفاده کرد. بیشتر کاربرد این الگوریتم برای مسائل ترکیبی است اما برای مسائل پیوسته هم کاربرد دارد.

این الگوریتم بر خلاف الگوریتم های دیگر الهام گرفته از طبیعت مبتنی بر جمعیت نیست و از هوش دسته جمعی استفاده نمی کند، اما چون از یک پدیده طبیعی الهام گرفته شده، جزء الگوریتم های الهام گرفته از طبیعت قرار می گیرد.

دو نکته مهم و اساسی وجود دارد که باید مورد توجه قرا گیرند.

1-فرآیند کاهش دما به صورت تدریجی و با کاهش اندک صورت می گیرد.

2- نقاط تصادفی جدید باید در همسایگی نقطه قبلی ایجاد شوند به طوری که اندکی تغییر در جواب داشته باشیم.

مهمترین نقاط قوت الگوریتم شبیه سازی تبرید(SA):

1-پیاده سازی بسیار ساده

2-عدم نیاز به مشتق تابع هدف

۳-تعداد کم پارامترها.

در مورد تعدا کم پارامترهای باید این توضیح را داد که اساسا هرچه تعداد پارامترهای مورد استفاده در یک الگوریتم بهینه سازی کمتر باشد، تنظیم آنها ساده تر خواهد بود و این یک مزیت برای الگوریتم های فراابتکاری به شمار می رود.

پارامترهای الگوریتمSA، پارامتر دمای اولیه و پارامتر کاهش دما می باشد.

بطور کلی یک الگوریتم فراابتکاری اگر بتواند جست و جوی مناسبی در فضای حل مسئله داشته باشد و همچنین مکانیسمی برای فرار از دام بهینه محلی داشته باشد، الگوریتم مناسبی بشمار می رود. الگوریتمSA هر دو مورد ذکر شده را دارد.

نقاط ضعف:

1-وابستگی زیاد به مقدار اولیه پارامترها

2- در صورت مقداردهی نادرست پارامترها امکان افتادن در دام بهینه محلی وجود دارد.

همگرایی الگوریتمSA

همگرایی این الگوریتم توسط گرانویل و همکاران(1994) و لاندی و مس(1986) مورد بررسی قرارگرفته است.

گرانویل و همکاران(1994) ثابت کرده است که، در هر مسئله با بعد محدود(مثلا مشخص بودن تعدا شهرها در مسئله TSP) احتمال رسیدن به جواب بهینه سراسری در پایان این الگوریتم، با کندتر کردن فرایند کاهش دما (تبرید)، به سمت یک میل می کند.

الگوریتمSA:

الگوریتمSA، یکی از الگوریتم های فراابتکاری الهام گرفته از طبیعت می باشد. این الگوریتم برخلاف سایر اكثر الگوریتم های الهام گرفته از طبیعت مبتنی بر جمعیت و هوش دسته جمعی نیست. این الگوریتم، بیشتر بر پایه اصول احتمال می باشد. ایده این الگوریتم از فرآیند رسیدن به ساختار کریستالی فلزات، گرفته شده است. در ساختار کریستالی، چینش اتم ها به صورتی است انرژی درونی ماده مورد نظر نسبت به چینش های دیگر کمتر است. هر چه انرژی درونی کمتر باشد، استحکام ماده بیشتر است. برای رسیدن به ساختار کریستالی فلزات، ابتدا آنها را حرارت داده و سپس به آرامی سرد می کنند. الگوریتم شبیه سازی تبرید از این فرآیند الهام گرفته شده است. مراحل الگوریتم شبیه سازی تبرید بصورت زیر می باشد:

1-تعیین دمای اولیه و پارامتر کاهش دما، دمای فعلی را برابر با دمای اولیه قرار می دهیم.

2- تولید یک جواب تصادفی اولیه و محاسبه مقدار تابع هدف و قراردادن آن بعنوان بهترین جواب تا زمان فعلی

۳- تولید یک نقطه در همسایگی نقطه قبل و محاسبه مقدار تابع هدف نقطه جدید

۴-اگر مقدار تابع هدف نقطه جدید کمتر از مقدار تابع هدف نقطه قبلی باشد، جواب جدید را جایگزین جواب قبلی می کنیم. به مرحله ۶ می رویم.

5-یک عدد تصادفی با تابع توزیع یکنواخت بین۰ و ۱ تولید می کنیم. مقدار  و  را از رابطه زیر بدست می آوریم، که در آن،T دمای فعلی است.

6-مقدار u و  را به ترتیب از روابط زیر محاسبه می کنیم

مقدار تابع هدف در نقطه قبلی – مقدار تابع هدف در نقطه فعلی = Au

۷-اگر مقدار عدد تصادفی کمتر یا مساوی با مقدار  باشد جواب جدید را جایگزین جواب قبلی میکنیم.

8-اگر به تعداد لازم همسایگی تولید نشده باشد به مرحله ۳ باز می گردیم.

۹-اگر جواب فعلی بهتر از بهترین جواب باشد آن را جایگزین بهترین جواب میکنیم.

10- دما را با استفاده از فرمول T_i=T_i-1*a کاهش می دهیم. a ضریب کاهش دما و T_i دما در تکرار فعلی و   T_i-1 دما در تکرار قبلی است.

۱۱-اگر شرط پایان برقرار نباشد به مرحله ۳ می رویم.

۱۲-پایان

مراحل ۴ و ۵ روش میترو پولیس – هستنیگز می باشد.

نمودار الگوریتمSA در شکل زیر نشان داده شده است.

 

شکل فلوچارت الگوریتمSA.

 

سناریوهای مسئله:

سناریوی اول: ماشین حمل زباله هفته ای یکبار به هر بلوک ساختمانی سر می زند.

سناریوی دوم(مقید به پنجره زمانی): ماشین حمل زباله در زمان های متعدد در هفته به بلوک های ساختمانی سر می زند.

 

فرضیات:

1-فرض شده است که هر فرد 4.4 پوند زباله در هفته بطور میانگین تولید می کند.

2- فرض شده است که ماشین حمل زباله به جای سرزدن از هر خانه یا آپارتمان به هر بلوک ساختمانی سر می زند.

3- تعداد بلوک های ساختمانی 500

 

شكل  خروجی حل الگوریتمSA برای مسئله مسیریابی خودروی حمل زباله سناریوی 1

 

 

شكل  خروجی حل الگوریتمSA برای مسئله مسیریابی خودروی حمل زباله سناریوی 2