منابع پایان نامه ارشد با موضوع مکانیابی، طراحی الگو، مکان‌یابی

باتوجه به نقطه مشخصی درنظر گرفت. به همین منظور، ما این شاخص را براساس شاخص MID که در بخش (2-5-1) شرح داده شد، درنظر گرفته ایم. به این معنی که ما سرعت همگرایی MID را محاسبه کرده‌ایم. معیار ما برای همگرایی نیز، 50 تکرار الگوریتم، بدون تغییر در شاخص MID بوده‌است. بدیهی است که هرچه زمان همگرا شدن کمتر باشد، سرعت الگوریتم بهتر بوده‌است.
2-5-8- منطقه زیر پوشش دو مجموعه
معیار منطقه زیر پوشش دو مجموعه113 (C)، منطقه زیر پوشش دو مجموعه را مقایسه می‌کند و خروجی آن، نشان دهنده درصد حل‌هایی از یک مجموعه پارتو است که بر حل‌های مجموعه دیگر غالب است. مقدار این معیار از رابطه زیر بدست می‌آید:
(38.2)
که در این رابطه، دو مجموعه از بردارهای متغیر تصمیم متعلق به فضای مسأله با و نمایش داده شده‌است. در این رابطه اگر C=1 شود، به این مفهوم است که بر غالب است.
2-6- جمع بندی
مسئله‌ای که برای این تحقیق درنظر گرفته شده است، سعی شده است که تا حدّامکان به واقعیت نزدیک باشد. بنابراین فرضیاتی درنظر گرفته شده است تا این نزدیک بودن را بیشتر کند. باتوجه به فرضیات و خصوصیات مدل درنظر گرفته شده و همچنین باتوجه به جستجوی بسیار در وب‌سایت‌های معتبر انتشار مقالات و مرور ادبیاتی که انجام گرفته، مقالات و تحقیقات کمی در این زمینه صورت گرفته است و این زمینه، محیطی بکر برای کار دارد. اکثر مقالاتی که در این موضوع انجام شده‌است، مسئله را به صورت تک هدفه درنظر گرفته و آن را با روش های مختلف حل نموده‌اند. ازجمله این کارها می توان به کاستیلو114 و همکارانش اشاره کرد که در آن دو رویکرد انتخاب ظرفیت برای مکانیابی بهینه تسهیلاتی با سرورهای ثابت، تقاضای تصادفی و تراکم درنظر گرفته شده‌است. در آن مقاله، هر تسهیل به صورت یک سیستم صف M/M/s عمل می کند. بِرمن و همکارانش، مسئله مکانیابی مجموعه‌ای از تسهیلات خدمت‌رسان را درون یک شبکه تحلیل کردند که در آن تقاضا به علت تراکم و پوشش ناکافی از دست می رود. هدف آن مسئله، پیدا کردن حداقل تعداد تسهیلات به گونه‌ای است که مقدار تقاضایی که از هر منبع از دست می رود، از یک سطح مشخص فراتر نرود. یکی از مدل های مکانیابی تصادفی با توزیع تقاضای پیوسته، توسط بارُن115 و همکارانش انجام شده است. این مدل یک توزیع عمومی از توزیع تقاضا و ورودها و فرایندهای خدمت رسانی دارد. فرض می‌شود که تسهیلات به صورت اختیاری بر روی یک سطح یا فضا واقع شده‌اند و مشتریان به نزدیکترین تسهیل بازشده مراجعه می‌کنند. به هر حال، محدودیت سطح سرویس برای مطمئن شدن از سرویس مناسب، وضع شده‌است. هدف، تعیین تعداد، مکان و ظرفیت تسهیلات با مینیمم کردن جمع هزینه‌های ایجاد تسهیلات و سرورهاست. در نزدیکترین مقاله به تحقیق ما، وانگ و همکارانش [21] مسئله‌ای را درنظر گرفته اند که هر تسهیل به صورت یک سیستم صف M/M/1 ساده عمل می‌کند. فرض شده‌است که مشتریان به نزدیکترین تسهیل سفر می‌کنند. هدف، تعیین مکانیابی تسهیلات با مینیمم کردن متوسط زمان کل سفر و زمان سپری شده مشتریان می باشد. آنها دو هدف را با یکدیگر ترکیب و مسئله را با استفاده از Greedy-dropping ، Tabu search و Lagrangian relaxation به صورت تک هدفه حل نموده‌اند. در تمامی مواردی که ذکر شد، باوجود اینکه آن ها از لحاظ مدل‌بندی و نوع مسئله، به مسئله ما بسیار نزدیک می باشند، امّا در تمامی آن‌ها، یا یک هدف درنظر گرفته شده‌است و یا اینکه اهداف مختلف با یکدیگر ترکیب و هدفی واحد را تشکیل داده‌اند. حال آنکه ما در این تحقیق، سه هدف کاملاً مجزا را درنظر گرفته و مسئله را به صورت یک مسئله چندهدفه حل نموده‌ایم.

مدل‌ سازی مسأله و توسعه الگوریتم ها

3-1- مسأله موردتحقیق
یک سیستم خدماتی را درنظر بگیرید که در آن، خدمت دهندگان ثابت هستند و مشتریان برای دریافت خدمت، باید به این خدمت دهندگان مراجعه کنند. ما فرضیات کلی زیر را درنظر می‌گیریم: 1) مشتریان برای دریافت خدمت، به نزدیکترین تسهیل بازشده مراجعه می‌کنند، 2) درخواست خدمت توسط هر گره مشتری، از یک جریان پواسن مستقل پیروی می‌کند، 3) هر جایگاه تسهیل بازشده ای، فقط یک خدمت‌رسان با زمان‌های خدمت نمایی دارد، و 4) یک حد بالایی بر روی حداکثر زمان انتظار مجاز مشتریان، وجود دارد.
برای مدل سازی این وضعیت، علامت‌های زیر را وضع می‌کنیم:
• M={1,2,…,m} : مجموعه گره‌های مشتریان
• N={1,2,…,n} : مجموعه گره‌های تسهیل بالقوه
• : ماتریس فاصله گره مشتری i تا گره تسهیل j
• : نرخ تقاضای کلی درخواست‌های سرویس در سیستم
• : نرخ تقاضای درخواست خدمت از گره مشتری
• : نرخ تقاضا در مکان تسهیل بازشده
• : متوسط نرخ خدمت در هر تسهیل
• : زمان انتظار مشتریانی که به گره تسهیل تخصیص می‌یابند
• : حد بالای زمان انتظار مجاز برای مشتریان
• : ظرفیت خدمت مازاد برای تضمین
• p : تعدادی تسهیلاتی که واقعاً بازشده‌اند؛
• : ماکزیمم تعداد تسهیلاتی که می‌توانند بازشوند؛
این مسأله می‌تواند به صورت زیر بیان شود [21]: فرضیات زیر را درنظر بگیرید: مجموعه‌ای از مشتریان با نرخ‌های تقاضایی که با مشخص می‌شوند، مجموعه‌ای از مکان تسهیلات بالقوه با متوسط ظرفیت‌های خدمت (نرخ) ، یک عدد صحیح مثبت و یک عدد مثبت ؛ مجموعه‌ای از مکان‌های تسهیلات را که حداکثر به اندازه باشد را بیابید که متوسط تعداد کل مشتریانی که به نزدیکترین تسهیلشان سفر می‌کنند و در آن منتظر می‌مانند، مینیمم گردد. این شرط را نیز درنظر بگیرید که متوسط زمان انتظار در هر تسهیل بازشده بزرگتر از نباشد.
اگر ، سرعت سفر باشد و

بنابراین، زمان سفر تجمعی مشتریان در واحد زمان برابر است با:

از این رو، هر تسهیل باز، به صورت یک صف M/M/1 رفتار می‌کند، متوسط زمان انتظار در مکان تسهیل باز j ، برابر که می‌باشد. بنابراین، زمان انتظار تجمعی مشتریان در واحد زمان برابر است با:

باتوجه به قانون ليتِل که در بخشهای قبل شرح داده شد، T، بیانگر متوسط تعداد مشتریان درحال سفر و V، بیانگر متوسط تعداد مشتریان در حال انتظار می‌باشد.
يکي از معيارهاي ارزيابي سيستم، درصدي از زمان است که سيستم کار مي کند. براي نشان دادن اين معيار، از عاملي به نام ضريب بهره‌وري يا کارائي استفاده مي شود که تعريف آن به شرح زير است:

ميانگين کل تقاضا براي دريافت خدمت در واحد زمان

کل ظرفيت سيستم براي ارائه خدمت در واحد زمان

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

و يا به عبارت ديگر:

برای تضمین اینکه مشتریان به نزدیکترین جایگاه تسهیل بازشده شان می‌روند، احتیاج داریم که:

که ، یک عدد بزرگ مثبت است (مثل ). وقتی ، به خاطر اینکه بزرگ است، این محدودیت ناکارآمد می‌شود. وقتی ، مشتری i نمی‌تواند به تسهیلی که دورتر از j است، تخصیص داده شود، درغیراینصورت، این محدودیت نقض می‌شود.
بنابراین، ما فرمول بندی برنامه نویسی ریاضی زیر را بدست می‌آوریم:
(1.3)
(2.3)
(3.3)
(4.3)
(5.3)
(6.3)
(7.3)
(8.3)

هدف (1.3)، بیانگر مینیمم کردن متوسط تعداد مشتریان درحال سفر، هدف (2.3)، بیانگر مینیمم کردن متوسط تعداد مشتریان در حال انتظار و هدف (3.3)، بیانگر ماکزیمم کردن مجموع کارکرد دستگاه‌ها در واحد زمان می‌باشد. این اهداف با توجه به محدودیت‌هایی که بیان شده‌اند، می‌باشد که محدودیت (4.3) به حداکثر تعداد تسهیلاتی که ممکن است باز شوند اشاره می‌کند. محدودیت (5.3) و (6.3) تضمین می‌کند که هر تقاضا مشتری تخصیص پیدا کند و این تخصیص، فقط به یک تسهیل باز باشد. محدودیت (7.3) نیز تضمین می‌کند که این تخصیص، به نزدیکترین تسهیل صورت پذیرد. در پایان محدودیت (8.3)، تضمین می‌کند که متوسط زمان انتظار در هر تسهیل، از فراتر نرود.

3-2- طراحی الگوریتم‌ها
برای اینکه عملکرد روش‌های فراابتکاری مورد بررسی قرارگیرد، نیاز به انجام آزمایشات است. برای پاسخ به این سؤال، لازم است که از چندین روش ارزیابی مناسب استفاده شده تا از نتایج آن‌ها یک نتیجه کلی حاصل شود. در این بخش، لازم است که ابتدا مسائل استانداردی ایجاد شود و کلیه این الگوریتم‌ها، شروع به حل این مسائل نمایند. شرایط و پارامترهایی که برای اجرای این الگوریتم‌ها تنظیم می‌گردد، باید برای کلیه آن‌ها یکسان درنظر گرفته شود تا شرایط عادلانه برای آنها رعایت شده باشد و در شرایط یکسان به رقابت پرداخته باشند.
3-2-1- تطبیق الگوریتم‌ها با مسئله موردبررسی
کارايي الگوريتم‌هاي فراابتکاري ارتباط مستقيمي با تنظيم پارامتر‌هاي آن دارد، بطوريکه انتخاب نادرست پارامتر(هاي) الگوريتمي کاملاً کارا، باعث ناکارآمدي آن مي شود. به اين منظور روش‌هاي متنوعي در ادبيات استفاده شده که اکثر آنها تجربي بوده‌است. در این تحقیق نیز سعی شده‌است تا تنظیم پارامترهایی که به صورت متعدد توسط مقالات مورداستفاده قرار گرفته، استفاده شود.
در ابتدا، پارامترهایی که در کلیه مسائل، به یک نحو مورد استفاده قرار گرفته‌اند و در تمامی الگوریتم‌ها به طور یکسان تنظیم شده‌اند، شرح داده می‌شود و سپس به تطبیق هر الگوریتم برای مسئله مورد بررسی می‌پردازیم.
3-2-1-1- ساختار حل‌ها
هر حل، به صورت یک رشته N تایی مرتب شده‌است که N، تعداد جایگاه تسهیلاتی است که بالقوه می‌توانند ایجاد شوند و این رشته به صورت باینری پر می‌شود که مثلاً اگر قرارشود تسهیل j ام ایجاد شود، عنصر j ام این رشته، برابر یک فرض می‌شود و درغیراینصورت صفر درنظر گرفته می‌شود. به عنوان مثال، حل را درنظر بگیرید. این حل بیانگر این است که در مثال ما، 12 جایگاه برای مکانیابی تسهیلات درنظر گرفته شده‌است و از این 12 جایگاه، در مکان‌های 3، 5، 6، 7، 10 و 12، تسهیلاتی واقع شده اند، یعنی در کل 6 تسهیل، مکان‌یابی شده اند.
3-2-1-2- معیار توقف
برای اینکه کارایی الگوریتم‌ها را در شرایط یکسان اندازه گیری کنیم، باید شرایط مساوی را برای همه آنها در نظر بگیریم. یکی از این شرایط، معیار توقف یکسان است، زیرا مثلاً اگر معیار توقف، تعداد تکرار و یا زمان اجرای الگوریتم باشد، شانس هر الگوریتم در بدست آوردن جواب‌های بهینه بهتر، با تعداد الگوریتم بالاتر و یا زمان اجرای بیشتر، افزایش می‌یابد. به این علت، ما معیار توقف را تعداد تکرار درنظر نگرفته ایم که بتوانیم سرعت اجرای الگوریتم‌ها را در رسیدن به همگرایی، اندازه‌گیری کنیم. بنابراین، از دو معیار توقفی که ذکر شد، ما زمان اجرای الگوریتم‌ها را یکسان درنظر گرفته‌ایم.
برای تعیین زمان اجرای الگوریتم، سعی بر آن داشتیم که زمان همگرا شدن هر مسأله را برای هر الگوریتم، بدست بیاوریم و سپس زمان الگوریتمی که بیشترین زمان را می‌برد تا همگرا شود را به عنوان معیار، برای تمامی الگوریتم‌ها درنظر بگیریم. ما مشاهده کردیم که بعضی الگوریتم‌ها، یا به همگرایی نمی‌رسند، و یا زمان بسیار زیادی طول می‌کشد تا به همگرایی برسند. به همین علت، ما این روش را نادیده گرفتیم. بنابراین، ما روش دیگری را درنظر گرفتیم، بدین ترتیب که زمان اجرای 100 مرتبه تکرار الگوریتم‌ها را بدست آورده، الگوریتمی که بیشترین زمان را برای اجرای این تعداد تکرار می‌برد و یا به عبارتی، کندترین الگوریتم می‌باشد را به عنوان الگوریتم معیار درنظر گرفتیم. باتوجه به آزمایشاتی که انجام شد، مشخص شد که الگوریتم VIS، کندترین الگوریتم می‌باشد. بنابراین، معیار توقف را برای تمامی