جستجوی محلی

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

مسیریابی یکی از مسائل بسیار پرکاربرد GIS است که هدف اصلی آن یافتن بهترین مسیر گذرنده از یک سری موقعیت های از پیش تعیین شده است. این فرایند می تواند تأثیر بسزایی در تصمیم گیری های حساس مکانی داشته باشد. به همین دلیل از دیرباز تحقیقات بسیاری در مورد بهینه سازی این مسئله با استفاده از الگوریتم های مختلف صورت گرفته است. مسئله فروشنده دوره گرد یکی از مسائل بسیار کهن در علوم کاربردی است که پیش از پیدایش GIS نیز مطرح بوده است. این مسئله با ظهور فناوری های جدید مانند GIS کاربردهای بسیاری یافته و روش های جدیدی نیز برای حل آن پیشنهاد شده است. الگوریتم های تکاملی (ژنتیک) یکی از روش هایی هستند که برای حل مسائل بهینه سازی مختلف به کار گرفته می شوند. تحقیقات نشان داده است که تلفیق روش های جست وجوی محلی (Local Search) با عملگرهای ژنتیک می تواند منجر به نتایج بهتری در حل مسئله فروشنده دوره گرد شود. در نوشتار حاضر، روشی تازه و ابتکاری برای حل مسئله مسیریابی ارائه و پیاده سازی شده است. در این روش با بهره گیری از مفهوم مرکز هندسی به برازش چندضلعی ها با رئوس شهرها، به گونه ای پرداخته شده است که مسیر نهایی محدب ترین چندضلعی باشد. این الگوریتم با رویکردی پوششی با جهت بیرونی ـ درونی بزرگ ترین دایره محیطی شهرها را به کوچک ترین چندضلعی محدب ممکن تبدیل می کند. همچنین با استفاده از جست وجوی محلی مبتنی بر الگوریتم ژنتیک و روش نزدیک ترین همسایه (NN)، به حل مسئله مسیریابی فروشنده دوره گرد پرداخته شده است. ارزیابی نتایج حاصل از روش پیشنهادی با نتایج حاصل از روش های ژنتیکی، جست وجوی محلی و نزدیک ترین همسایه حاکی از این بود که روش پیشنهادی، سرعت و دقت بالایی را در تولید مسیرهای نهایی ارائه می کند. بررسی نتایج نهایی ژنتیک با روش ابتکاری نشان دادکه این الگوریتم همواره نمی تواند به جواب های بهتری برسد. مثلاً در تعداد 25 بار اجرای جداگانة جست وجوی ژنتیک، 3/69 درصد از جواب ها از جواب روش پیشنهادی، بهتر نبودند. از طرف دیگر روش پیشنهادی می تواند چندین هزار برابر سریع تر از الگوریتم قدرتمند ژنتیک جواب های نهایی را تولید کند.

در این مقاله، مسأله مسیریابی وسایل نقلیه با حمل برگشتی همراه با یک سری محدودیت های عملیاتی بررسی می شود. مشتریان به دو گروه مشتریان خط رفت که تحویل کالا به آن ها صورت می گیرد و مشتریان خط برگشت که کالا از آن ها دریافت می شود، تقسیم می شوند. همچنین، اولویت خدمت رسانی با مشتریان خط رفت است. نکته حائز اهمیت در این تحقیق آنکه، امکان تقسیم تقاضا برای مشتریانی که تقاضای آن ها از بزرگترین وسیله نقلیه موجود بیشتر است و همچنین، محدودیت عملیاتی جدید عدم دسترسی به بعضی از وسایل نقلیه برای تعدادی از مشتریان، به صورت توأمان در نظر گرفته می شود. دپوی مرکزی شامل ناوگانی از وسایل نقلیه با ظرفیت های مختلف و به تعداد نامحدود بوده و تقاضای مشتریان به صورت پویا است و در هر دوره قابل تغییر است. این مسأله از نوع چند جمله ای نامعین سخت (NP-hard) است و با توجه به ساختار خاص آن و بررسی ادبیات موضوع، یک الگوریتم کلونی مورچه چندگانه جدید[i] (NM-ACO) برای حل آن پیشنهاد می شود. در این مقاله، پس از آشنایی با کلیات و بیشینه تحقیق، مدل ریاضی جدیدی برای مسأله مورد نظر ارایه می شود و در ادامه الگوریتم کلونی مورچه چندگانه پیشنهادی که شامل دو فاز تخصیص و مسیریابی است، تشریح می گردد. در پایان، به تحلیل نتایج عددی حاصل از این الگوریتم برای مسایل آزمون طراحی شده پرداخته می شود.

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