در این روش به جای اینکه کروموزوم غیرموجّه حذف گردد تبدیل به یک کروموزوم موجّه می‌شود. این روش نیز مانند روش اول به مسأله وابسته بوده و یافتن فرآیند اصلاح گاهی بسیار پیچیده می‌باشد.

 

 

استراتژی جریمه‌ای

 

 

در این روش بر خلاف سه روش قبل که از ورود جواب‌های غیرموجّه جلوگیری می‌کردند، جواب غیرموجّه با احتمال کم امکان حضور می‌یابند. سه روش فوق دارای این عیب بودند که به هیچ نقطه‌ای بیرون از فضای موجّه توجّه نمی‌کردند، اما در بعضی مسائل بهینه‌سازی، جواب‌های غیرموجّه درصد زیادی از جمعیت را اشغال می‌کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجّه انجام گیرد شاید یافتن جواب موجّه خیلی وقت‌گیر و مشکل باشد.
استراتژی جریمه‌ای از متداولترین تکنیک‌های مورد استفاده برای سر و کار داشتن با جواب‌های غیرموجّه می‌باشد که در آن ابتدا محدودیت‌های مسأله در نظر گرفته نمی‌شوند پس برای هر تخلّف از محدودیت‌ها یک جریمه اختصاص داده می‌شود که این جریمه در تابع هدف قرار می‌گیرد.
مسأله اصلی چگونگی انتخاب یک مقدار مناسب برای مقدار جریمه می‌باشد تا در حل مسائل به ما کمک نماید.
نکته‌ای که در روش جریمه وجود دارد این است که یک جواب غیرموجّه به سادگی حذف نمی‌شود زیرا ممکن است در ژنهای آن اطلاعات مفیدی وجود داشته باشد که با اندکی تغییر به جواب بهینه تبدیل شود.
 
مرور ادبیات کاربرد الگوریتم ژنتیک در مسایل مکانیابی
الگوریتم ژنتیک برای اولین بار روی مسایل مکانیابی – تخصیص توسط هسیج[۶۷] و گودچایلد[۶۸] در سال ۱۹۸۶ بکار برده شد. گنگ و همکارانش[۶۹] در سال ۱۹۹۹ از یک ژنتیک برای تخصیص m ماشین به m محل استفاده کردند و مقایسهای بین این الگوریتم و دیگر روشهای حل زمانبر انجام دادند. مورنو و همکارانش[۷۰] در سال ۱۹۹۴ ژنتیک را برای مسایل p-median بکار بردند. کراتیکا و همکارانش[۷۱] در سال ۲۰۰۱ یک ژنتیک برای یک مثال ساده مکانیابی کارخانه بکاربردند و بزکیا و همکارانش[۷۲] یک ژنتیک کارا برای مسایل p-median توسعه دادند و ثابت کردند که الگوریتم نسبت به دیگر الگوریتمهای ارایه شده کارایی بیشتری دارد. جارامیلو و همکارانش[۷۳] در سال ۲۰۰۲ مقایسهای از عملکرد ژنتیک روی انواع مسایل مختلف مکانیابی داشتند. ایتوگ[۷۴] و سایدام[۷۵] یک ژنتیک ترکیبی را برای مسایل مکانیابی حداکثر پوشش مورد انتظار با استفاده از الگوریتم تقریبی هایپروکوب توسعه دادند. همچنین یک مقایسه بین ژنتیک بکار رفته روی مسایل جایابی حدکثر پوشش مورد انتظار و دیگر روشها و الگوریتمها انجام و نشان دادند که حداقل یکی از ژنتیکهای بکار برده شده در این مدل به یک جواب نزدیک به بهینه با زمان حل قابل قبول منجر میشود. توپوگلو و همکارانش[۷۶] در سال ۲۰۰۷ یک ژنتیک جدید ارایه کردند و مقایسهای بین ژنتیک ارایه شده و جستجوی ممنوع انجام دادند. شوندی و محلوجی در سال ۲۰۰۶ پس از ارایه مدل FQMCLP و با توجه به شباهت این مدل به مساله P-median یک ژنتیک مانند ژنتیک ارایه شده توسط بزکایا برای مدل p-median، برای مدلشان اراده دادند. شینگ و همکارانش[۷۷] در سال ۲۰۰۷ یک ژنتیک برای مکانیابی- تخصیص ارایه کردند، آنها در این الگوریتم از تکنیک ساب گرادیان برای حل کاراتر آن استفاده کردند. یانگ و همکارانش در سال ۲۰۰۷ یک ژنتیک برای جایابی ایستگاههای آتشنشانی که با استفاده از برنامهریزی چندهدفه فازی بهینه میشدند، ارایه کردند (شوندی و مردانه خامنه، ۱۳۹۰).
 
سابقه پژوهشهای دارای موضوعات مشابه
پژوهش حاضر به لحاظ بهرهگیری از مدل و الگوریتمی جدید جهت اخذ تصمیم مکانیابی دارای سابقهی مشابه نمیباشد اما از آنجاییکه در پایان نامه موجود از تمامی مباحث مرتبط همچون مکانیابی، مساله حداکثر پوشش و الگوریتم ژنتیک استفاده گردیده است، میتوان به گروهی از سوابق مرتبط با موارد فوق که بیشترین قرابت را با پژوهش حاضر داشته اند اشاره نمود. در رابطه با مکانیابی صنایع پژوهشهای داخلی و خارجی زیادی انجام گرفته است که غالب روشهای بکار گرفته شده در آنها مدلهای تصمیم گیری چندمعیاره و مدلهای ریاضی مکانیابی که عموماً به برنامه ریزی آرمانی و برنامه ریزی صفر و یک محدود میگردد است. در سالهای اخیر کارهای قابل قبولی در رابطه با بکارگیری مدل ریاضی حداکثر پوشش انجام گرفته است که البته بیشتر در قالب مقاله و بدون بکارگیری مورد مطالعاتی واقعی ارایه گردیده است. در اینجا به تعدادی از این پژوهش ها اشاره میکنیم :
 
علی حسینی (۱۳۷۹) در مطالعهای با عنوان «بکارگیری الگوریتم ژنتیک برای حل مساله پوشش مجموعه» با استفاده از یک مساله آزمون که به صورت تصادفی تولید شده بود. بهینه ترین وضعیت الگوریتم را از نظر بکارگیری عملگر جهشی ، مکانیسم انتخاب و نرخ تقاطعی معرفی کرد. سپس الگوریتم پیشنهادی طراحی و بر روی تعدادی مساله آزمون که آنها نیز به صورت تصادفی تولید شده بودند پیاده کرده و نتایج حاصله را با الگوریتم ابتکاری (Greedy Heuristic) هیراگو مقایسه کرد. الگوریتم پیشنهادی او دارای شرایط ذیل بود : الف – سیستم کدینگ : رشته دودویی ب – ایجاد جمعیت اولیه : تصادفی – بدون کروموزوم تکراری و غیر موجه پ – عملگر تقاطعی : دو نقطه برش با نرخ تقاطعی ۰/۹۵ ت – عملگر جهشی: یکنواخت با نرخ جهشی۰/۱ ج- تابع برازش : تابع هدف مساله چ – برخورد با محدودیت ها : استراتژی ردی (علیحسینی، ۱۳۷۹)
صادقی در سال ۱۳۸۷ در پژوهش خود با عنوان «جایابی بهینه مراکز توزیع در فرآیند بازاریابی با استفاده از روشهای ریاضی» به ارایه الگو و مدلی جهت مکان یابی مراکز فروش و خدمات پس از فروش شرکت تالیا پرداخته است. او از تلفیق دو مدل TOPSIS و برنامهریزی صفر و یک به ترتیب برای عوامل مشتری مدار – بازاریابی و محدودیت های مالی – جغرافیایی استفاده کرده است (صادقی،۱۳۸۷)
صفاریان (۱۳۸۸) در مقالهای با عنوان «کاربرد الگوریتم ژنتیک برای حل مساله پوشش حداکثر» یک الگوریتم ژنتیک مناسب برای حل مدلهای Maximal Covering ارایه کرد. این الگوریتم را برروی ۷۵ مساله متفاوت اجرا نموده و نتایج آن را با نتایج حاصل از دو الگوریتم لاگرانژ و گردی ادینگ برروی همان مسایل مقایسه کرد.. همچنین نتایج حاصل از این الگوریتم را با نتایج حاصل از نرم افزار لینگو مقایسه کرده و از نظر میزان دقت و کارایی مورد بررسی و مطالعه قرار داد (صفاریان، ۱۳۸۸).
سید حسینی و همکاران (۱۳۸۸) به حل مساله مکانیابی پایانههای اتوبوس رانی درون شهری با استفاده از الگوریتم ژنتیک پرداختند. آنها برای حل مساله یک الگوریتم ژنتیک پیشنهاد دادند. مهمترین مزیت الگوریتم ژنتیک پیشنهادی، رسیدن به جواب دقیق تر در زمان کمتر می باشد. برای تایید کارایی روش خود، الگوریتم را برای شبکه های اتوبوسرانی مشهد و تهران اجرا و نتایج آن را با نتایج کوشش های پیشین مقایسه کردند (سیدحسینی و همکاران، ۱۳۸۸).
فرقانی و همکاران (۱۳۸۹) در مقالهای تحت عنوان «توسعه یک مدل دو هدفه برای مساله حداکثر پوشش با محدودیت پارامترهای صف» مدل ارایه شده توسط کورآ و لورنا که به صورت یک مساله حداکثر پوشش با محدودیت شاخصهای صف است، توسعه دادند بگونه ای که علاوه بر تابع هدف حداکثر پوشش، هدف حداقل نمودن فواصل خدمت دهنده ها تا مشتریان نیز در نظر گرفته شود. سپس مدل توسعه داده شده خود را توسط الگوریتم ژنتیک و نرم افزارCPLEX حل کردند (فرقانی و همکاران، ۱۳۸۹).
مرادی و همکاران (۱۳۸۹) در مقاله «مکانیابی مراکز ارایه خدمات رقابتی با هدف کاهش ازدحام ترافیک شهری» مدلی برای مکان یابی مراکز با محدودیت ظرفیت، طراحی کرده و سپس یک الگوریتم شبیه سازی تبریدی موازی برای حل این مدل ارایه کردند. در پایان، الگوریتم پیشنهادی برای تعیین مکان های مراکز سلامت در شهر اصفهان استفاده قرار داده و کارایی آن را بررسی کردند (مرادی و همکاران ۱۳۸۹).
شوندی و خامنه (۱۳۹۰) مساله جایابی پوششی با در نظر گرفتن تراکم مشتریان و تقاضای از دست رفته با روش حل الگوریتم ژنتیک را حل کردند. آنها در مقاله خود یک مدل جایابی با ساختار احتمالی که احتمال مراجعه تقاضا از یک گره به خدمت دهنده ها با توجه به فاصله آنها برآورد می شود توسعه دادند. همچنین در مدل ارایه شده با فرض رقابتی بودن بازار بحث فروش از دست رفته را در نظر گرفتند و با توجه به این موضوع هدف مدل را حداقل کردن هزینه از دست دادن تقاضاها یا حداکثر کردن سود حاصل از پاسخگویی به این تقاضاها تعریف کردند. بعد از ارایه مدل، یک الگوریتم ژنتیک برای حل مدل ارایه کرده تا علاوه بر این از بحث طراحی آزمایشات و متدولوژی سطح پاسخ برای تنظیم پارامترهای الگوریتم ژنتیک استفاده کردند تا عملکرد آلگوریتم ارتقا یابد (شوندی و خامنه ۱۳۹۰).
شوندی و همکاران (۱۳۹۰) مدل مکانیابی – تخصیص حداکثر پوشش با امکان ایجاد ازدحام در محیط رقابتی مبتنی بر انتخاب مشتری را توسعه دادند. در مدل پیشنهادی آنها چندین ویژگی مهم یعنی مدل های تعامل فضایی، ازدحام، محیط رقابتی مبتنی بر انتخاب مشتری و تقاضای احتمالی مورد بررسی قرار گرفته است. هدف مدل حداکثر نمودن درصد تقاضای جذب شده توسط تجهیزات خدمتدهی در محیط رقابتی است. برای حل مدل با ابعاد کوچک از نرم افزار بهینه سازی لینگو ۸ و الگوریتم فرا ابتکاری ژنتیک استفاده شده است. اما با توجه به پیچیدگی مسئله و ماهیت غیرخطی آن، نرم افزار لینگو ۸ توانایی حل مسایل با ابعاد بزرگ را ندارد و مسایل با ابعاد بزرگتر با استفاده از الگوریتم ژنتیک پیاده سازی شده است (شوندی و همکاران ۱۳۹۰).
سادهوند (۱۳۹۰) به مکانیابی جایگاههای سوخت CNG با استفاده از مدل مکانیابی جریان سوختگیری FRLM پرداخت او در این مساله مطرح کرده است که شبکه فعلی جایگاههای سوخت CNG با توجه به گسترش ناوگان حمل و نقل گازسوز، علاوه بر کمبود ظرفیت سوخت رسانی، عمدتاً به سبب توزیع نامناسب جغرافیایی جوابگوی نیازها نمیباشد لذا لازم است تا با ارایه الگویی مناسب، توزیع شبکه جایگاههای سوخت CNG در سطح شهر به صورت صحیح انجام گیرد و علاوه بر جلوگیری از مشکلاتی که در آینده بر شهر تحمیل میگردد، مانع از اتلاف انرژی و افزایش بهرهوری امکانات و منابع موجود گردد (سادهوند ۱۳۹۰).
شورورزی و همکاران (۱۳۹۱) در مقاله «مقایسه قابلیت الگوریتمهای فراابتکاری در حل مساله مکانیابی مراکز آتشنشانی» روشهای فراابتکاری جست‌وجوی ممنوع، ژنتیک و شبیه‌سازی بازپخت را به‌عنوان روش‌های بهینهسازی برای مکانیابی مراکز آتشنشانی و تخصیص مناطق شهری به آن‌ها استفاده کردند. این روشها با توجه به معیارهای زمان حل مسئله، مقدار تابع هدف، تعداد تکرار و نحوه پوشش منطقه در سناریوهای مختلف ارزیابی شده‌ و سناریوهای مختلف در روش ژنتیک بر‌اساس تغییر در تعداد تکرار و جمعیت اولیه و در روش شبیهسازی بازپخت بر‌اساس تغییر در تعداد تکرار حرکات و تغییرات دما تولید شده‌ است (شورورزی و همکاران ۱۳۹۱).
خاتمی فیروزآبادی و همکاران )۱۳۹۱( به ارایه الگویی برای مکانیابی شعب موسسه مالی و اعتباری قوامین» با استفاده از رویکردهای کمی (آزمون تی یک نمونه ای برای شناسایی شاخصه‌ها) و کیفی (روش تحلیل سلسله مراتبی برای وزن دهی به شاخصه‌ها) و با استفاده از نرم افزارهای SPSS،Expert Choice، GISو LINGOپرداختند و مشخص کردند که بر مبنای شاخصه‌های بدست آمده و استفاده از مدل ریاضی حداکثر پوشش، می‌توان ۹۵ ٪ از تقاضای منطقه مورد مطالعه را با احداث حداکثر ۴ شعبه در نقاط مشخص شده (به علاوه ۴ شعبه موجود)، تحت پوشش قرار داد )خاتمی فیروزآبادی و همکاران ۱۳۹۱).
یوسفی در سال ۱۳۹۱ با بکارگیری منطق فازی و روش تصمیم گیری FUZZY DEMANTEL و همچنین روش تصمیم گیری گروهی Cook&Seiford به انتخاب سبد پروژههای عمرانی پرداخت (یوسفی، ۱۳۹۱).
ماریانوو سرا در سال ۱۹۹۸ در مقاله خود، چندین مدل حداکثر پوشش احتمالی با زمان انتظار یا طول صف محدود ارایه کردند. اولین آنها مدل مکان تعدادی مرکز خدمتدهی با یک خدمتدهنده را بطوری که جمعیت پوشش دادهشده در یک فاصله استاندارد و با طول صف محدود حداکثر شوند مشخص میکند و مدلهای بعدی مسائلی که در آنها بیشتر از یک خدمتدهنده وجود داشته باشد را ارایه میکنند (ماریانوو سرا، ۱۹۹۸).
کورآ و لورنا در سال ۲۰۰۶ در مقالهای تحت عنوان « استفاده از الگوریتم ژنتیک برای حل مساله مکانیابی حداکثر پوشش احتمالی» راه حلی برای مدلهای احتمالی با در نظر گرفتن یک سرویس دهنده در هر مرکز با استفاده از الگوریتم ژنتیک سازنده ارایه کردند (کورآ و لورنا، ۲۰۰۶).
رناد و همکاران (۲۰۱۲) به تعیین محل مناسب برای مراکز توزیع ماهوارهای جهت تامین کمکهای بشر دوستانه به مردم آسیب دیده در مناطقی که دچار بلایای طبیعی و یا هر حادثه مخرب دیگر شده است پرداختند. بدین منظور مدل این مساله را به صورت مدل حداکثر پوشش تور به همراه یک روش حل هیوریستیک ارایه کردند (رناد و همکاران ۲۰۱۲).
لیانگ وی و همکاران (۲۰۱۲) با بکارگیری مسائل مجموعه پوشش و حداکثر پوشش به ارایه مدلی جهت اخذ تصمیم مربوط به مکان پناهگاههای شهری پرداختند. در این مدل هزینهها و درآمدها کاملا در نظر گرفته شدهاند که موجب میشود در تصمیمات نهایی اتخاذ شده مساله بودجه نیز در نظر گرفته شده باشد (لیانگ وی و همکاران، ۲۰۱۲).
معین مقدس و کاخکی در سال ۲۰۱۲ در مقالهای با عنوان روش حل هیوریستیک برای مساله حداکثر پوشش با سیستم صف M/G/1، مدلی با هدف تعیین محل حداکثر p مرکز سرویس و تخصیص نقاط تقاضا به آنها بگونه ای که جمعیت سرویس داده شده ماکزیمم شود، اراده کردند در این مدل هر مرکز سرویس با سیستم صف M/G/1 به مشتریان ارایه سرویس می دهد و میانگین زمان انتظار در هر مرکز سرویس برای مشتریان از مقدار داده شده نبایستی تجاوز کند. در این مقاله پس از معرفی و مدل بندی مساله، یک روش تقریبی برای حل مساله پیشنهاد می شود (معین مقدس و کاخکی، ۲۰۱۲).
بارای و کلیکوئت (۲۰۱۲) در مقاله بهینه سازی مکانیابی از طریق مدل پوشش حداکثر و P-Median برای بیمارستان مادران فرانسه، به ارایه یک مدل مکانیابی تخصیص سلسله مراتبی که ترکیبی از مدل پوشش حداکثر و P-Median است، میپردازند. هدف انطباق توزیع فضایی از عرضه با سطوح مختلف تقاضاست. در حل مدل از الگوریتمهای Lagrangian relaxation و myopic استفاده شده است (بارای و کلیکوئت، ۲۰۱۲).

 

دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

 

فصل سوم

 

 

روش اجرای پژوهش

 

 

 
مقدمه
مکانیابی معمولاً شامل دو فاز اصلی است : ۱) تعیین محل (مشخص کردن مکانهای بالقوه در یک منطقه جغرافیایی) و ۲) ارزیابی مکان (در واقع آزمایش هر مکان کاندید شده براساس یک سری معیارهای معلوم برای مشخص نمودن اینکه کدام مناسبترین است) (فیروزآبادی، رودپشتی و تقوی فرد، ۱۳۹۱) .
مدلهای مکانیابی به دلیل اهمیت و تاثیر فراوانی که در کاهش هزینههای ایجاد و راهاندازی فعالیتهای مختلف دارد، همواره مورد توجه محققین و مهندسین صنایع بوده است. یکی از مهمترین مدلهای مکانیابی، مدل مکانیابی حداکثر پوشش (MCLP) است که سعی در حداکثر نمودن پوشش جمعیتی می کند که در یک حداکثر فاصله یا زمان مشخص از یک تجهیز قرار دارند. توسعه های بسیاری جهت بهبود کاربرد های این مساله ارایه شده است که یکی از آنها ترکیب این مساله با مدلهای صف میباشد. با توجه به ماهیت احتمالی تقاضا در برخی از مسائل مکانیابی و همچنین ظرفیت محدود تجهیزات برای خدمتدهی، در بسیاری از مسائل دنیای واقعی شاهد ایجاد ازدحام برای دریافت خدمت هستیم این ازدحام میتواند به صورت تشکیل صف برای خدمتدهی و یا از دست رفتن تقاضا نمود پیدا کند.
درخصوص اهمیت و ضرورت بررسی سیستم صف در مدل مکانیابی حداکثر پوشش میتوان گفت که هدف موسسات تولیدی و خدماتی کسب رضایت مشتری است. یکی از مهمترین عوامل ایجاد ارزش بلندمدت و وفادار نمودن مشتریان، نحوه خدمتدهی، کاهش زمان صف و زمان انتظار مشتریان سازمان است. لذا همواره سازمانها برآنند تا با مکانیابی صحیح برای محل ارایه خدمات خود، سه مورد فوق را تامین کرده و در نتجه مشتریان خود را راضی نگهدارند (زرین پور، شوندی، باقری نژاد، ۱۳۸۹).
 
مدل مسائل پوشش حداکثر (MCLP)