پایان نامه با واژه های کلیدی مکان‌یابی، شبیه‌سازی، مدل‌سازی

دانلود پایان نامه ارشد

نزدیک‌ترین محورشان اختصاص ‌یافته‌اند. در هر دو مقاله‌ی Klincewicz, 1991, 1992)) از مجموعه داده‌های CAB و یک مجموعه داده‌ی بزرگ‌تر با 52 نقطه‌ی تقاضا و بالغ بر 10 محور جهت آزمایش عملکرد این روش‌های ابتکاری استفاده شده است.Campbell (1992) اولین فردی بود که تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه را به عنوان یک برنامه‌ی عدد صحیح خطی مدل‌سازی کرد.
در مسئله‌ی p-محور میانه از هزینه‌های ثابت راه‌اندازی تسهیلات صرف‌نظر شده است (Alumur and Kara (2008)). در مقاله‌ی O’Kelly (1992a) نویسنده آن، تخصیص ساده‌ی مسئله‌ی مکان‌یابی محور را با هزینه‌های ثابت معرفی کرده‌ که تعداد محورها را به یک متغیر تصمیم‌گیری تبدیل می‌کند. او این مسئله را به عنوان یک برنامه‌ی عدد صحیح درجه دو مدل‌سازی کرده است. در این روش از آنجایی که تعداد محورهای انتخاب‌شده از قبل مشخص نیست، علاوه بر داشتن حالت‌های تخصیص چندگانه و ساده می‌توان به گونه‌های ظرفیت محدود و نامحدود این مسائل نیز دسترسی پیدا کرد.
Skorin-Kapov and Skorin-Kapov (1994) روش ابتکاری جستجوی ممنوعه‌ی دیگری را برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرده‌اند. آن‌ها با استفاده از مجموعه داده‌های CAB نتایج روش ابتکاری خود را با دو روش ابتکاری O’Kelly (1987) یعنی (HEUR1 و HEUR2) و جستجوی ممنوعه‌ی Klincewicz (1992) مقایسه کرده‌اند. نتایج آن‌ها بهتر است اما زمان واحد پردازشگر مرکزی8 روش آن‌ها به دلیل تأکید بیشتر بر فاز تخصیص مسئله، بزرگ‌تر بود.
Campbell (1994b) اولین مدل برنامه‌ریزی خطی را برای تخصیص ساده/چندگانه‌ی ظرفیت محدود/نامحدود مسئله‌ی مکان‌یابی محور ارائه کرده است.
Campbell (1994) ادعا کرد که در غیاب محدودیت‌های ظرفیت بر روی اتصال‌ها، از آنجایی که جریان کلی برای هر زوج مبدأ/مقصد بایستی حداقل از دو محور متصل به هم گردش یابد، اگرX_ijkm دارای مقدار 0 و 1 باشد مسئله دارای جواب بهینه است. بنابراین هیچ نیازی به عدد صحیح بودن متغیر X_ijkm نیست. او همچنین تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی ‌p-محور را با آستانه‌های جریان و هزینه‌های ثابت به عنوان یک برنامه‌ی عدد صحیح خطی مدل‌سازی کرد.
Campbell (1994b) اولین مدل برنامه‌ریزی عدد صحیح خطی را برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرد. مدل او تعداد (n^4+n^2+n) متغیر داشت که تعداد (n^2+n) متغیر آن دوتایی بودند و تعداد (n^4+〖2n〗^2+n+1) محدودیت خطی داشت. او همچنین مسئله‌ را با آستا‌نه‌ی جریان مدل‌سازی کرد و مقدار حداقل جریان مورد نیاز برای سرویس‌دهی به هر اتصال را تعیین کرد. هنگامی‌که آستانه‌ی جریان در حداکثر مقدار خود هستند، هر گره‌ی تقاضا به یک تک محور اختصاص داده شد و مدل به تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه تقلیل یافت.
Aykin (1994) حالت ظرفیت محدود مسئله‌ی مکان‌یابی محور را با هزینه‌های ثابت که در آن محورها دارای ظرفیت محدودند، بررسی کرده‌ است. او مسئله را چنان مدل‌سازی کرده است که اتصالات مستقیم (بین گره‌های غیر محور) نیز مجازند. او یک الگوریتم انشعاب و تحدید پیشنهاد کرده که کران‌های پایین توسط ساده‌سازی لاگرانژی به دست می‌آیند. Aykin (1995a) مسئله‌ی مشابهی را با هزینه‌های ثابت و تعداد محورهای داده‌شده جهت مکان‌یابی تجزیه و تحلیل کرده است. او دو سیاست انتخاب محور را که سیاست‌های اکید و غیر اکید (اتصال مستقیم اجازه داده‌شده) نامیده، مقایسه کرده است. او یک الگوریتم شمارشی9 و یک روش ابتکاری شبیه‌سازی تبرید10 بر اساس روش ابتکاری حریصانه مبادله‌ای پیشنهاد کرده است.
O’Kelly et al. (1995) یک فن کران پایین بر اساس خطی سازی تابع هدف درجه دوم که مسافت‌ها جهت برقراری نامساوی مثلثی فرض شده‌اند، برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرده‌اند. آن‌ها با استفاده از این روش نشان داده‌اند که روش جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) برای مسائل کوچک‌تر (10 الی 15 گره) به طور متوسط دارای شکاف 3/3 درصد و برای مسائلی با 20 الی 25 گره به طور متوسط دارای شکاف 9/5 درصد است.
سپس Skorin-Kapov et al. (1996) با ساده‌سازی برنامه‌ریزی خطی مدل Campbell (1994b) جواب‌های بسیار کوچک‌تری به دست آوردند. آن‌ها مدل جدیدی برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه دادند. با تغییری که آن‌ها در مدل ایجاد کردند تعداد متغیرها به (n^4+n^2) کاهش یافت که از این تعداد، (n^2) متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز به (〖2n〗^3+n^2+n+1) محدودیت کاهش یافت. بر اساس اطلاعات ما آن‌ها، اولین تلاش‌ها را برای حل بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه انجام دادند. آن‌ها با استفاده از جواب‌های بهینه‌ی مجموعه داده‌های CAB، بهینگی راه‌ جستجوی ممنوعه‌ی به دست آمده در مقاله‌ی Skorin-Kapov and Skorin-Kapov (1994) را اعتبار ببخشند.
مبرهن است که جواب‌های مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه کران پایینی را برای جواب بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه مهیا می‌کند (Campbell, 1996). با استفاده از این ایده، Campbell (1996) دو روش ابتکاری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه پیشنهاد داده است. این دو روش ابتکاری (MAXFLO و ALLFLO) جواب‌های مشتق شده از راه‌ مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه هستند. در این روش‌های ابتکاری، تخصیص‌ها مطابق با نقش‌های متفاوت صورت گرفته اما تصمیم‌های مکانی همان تصمیم‌های قبلی هستند.
Ernst and Krishnamoorthy (1996) مدل برنامه‌ریزی خطی عدد صحیح جدیدی را برای مسئله‌ی تخصیص ساده ارائه کردند که دارای محدودیت‌ها و متغیرهای به مراتب کمتری بود و توانایی حل مسائل بزرگ‌تری را نیز داشت. آن‌ها انتقال‌های بین محور را به عنوان مسئله‌ی جریان چند محصولی تلقی کردند که در آن هر محصول بیانگر جریان ترافیک نشأت‌گرفته از یک گره‌ی خاص است. نویسندگان این مقاله چگونگی استفاده‌ی پست استرالیا (AP)11 از ضریب‌های کاهشی مختلف در جمع‌آوری و توزیع را مشاهده و مدل کردند و برای هر واحد هزینه‌ی جمع‌آوری و توزیع محصول یک ضریب کاهشی را اختصاص دادند (δ برای ضریب کاهشی توزیع و χ برای ضریب کاهشی جمع‌آوری محصول).
مدل آن‌ها دارای (n^3+n^2) متغیر بود که از این تعداد، (n^2) متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز (〖2n〗^2+n+1) بود. آن‌ها یک روش ابتکاری شبیه‌سازی تبرید را توسعه و نشان داده‌اند که روش آن‌ها از هر دو منظر کیفیت جواب و زمان محاسباتی، با روش ابتکاری جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) قابل مقایسه است. آن‌ها از این کران بالای به دست آمده از روش ابتکاری شبیه‌سازی تبرید برای توسعه‌ی راه حل روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی استفاده کردند. آن‌ها هر دوی روش‌های ابتکاری خود و الگوریتم انشعاب و تحدید را بر روی مجموعه داده‌های AP و CAB آزمایش کردند، اما آن‌ها قادر به حل مسائلی با بیش از 50 گره نبودند.
O’Kelly et al. (1996) با ارائه‌ی داده‌های برابر جریان مدلی پیشنهاد کردند که باعث کاهش اندازه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه شد. هنوز هم مدل جدیدی که آن‌ها معرفی کرده‌اند در بیشتر مقالات مورد استفاده قرار می‌گیرد. مهم‌ترین چیزی که آن‌ها در مقاله‌ی خود مطرح کردند، حساسیت جواب‌ها به ضریب کاهشی بین محورها (α) بود.
Campbell (1996) یک روش ابتکاری حریصانه-مبادله‌ای را برای مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور پیشنهاد کرده‌ است.Skorin-Kapov et al. (1996) یک مدل عدد صحیح مختلط جدید پیشنهاد کردند که در آن دو محدودیت مدل اولیه‌ی Campbell (1992) با حالت تجمعی‌شان جایگزین شده‌اند. این مدل دارای (n^4+n) متغیر است که تعداد (n) آن دوتایی است و نیاز به (〖2n〗^3+n^2+1) محدودیت خطی دارد. این مدل باعث ساده‌سازی‌های برنامه‌ریزی خطی فشرده‌تری شد و تولید نتایجی یکپارچه در تقریباً تمام مواردی که از مجموعه داده‌های CAB استفاده شده است، نمود. در مواردی که ساده‌سازی برنامه‌ریزی خطی راه‌حل یکپارچه‌ای به دست نمی‌دهد، نویسندگان این مقاله درخت جستجوی شمارش ضمنی را برای دستیابی به جواب‌های بهینه به کار بستند. این درخت جستجو معمولاً گره‌های درختی کمتر را شامل می‌شود.
Smith et al. (1996) مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه را برای شبکه‌ی عصبی اصلاح‌شده‌ی Hopfield ترسیم کرده‌اند. آن‌ها از مدل برنامه‌ریزی عدد صحیح درجه دوم O’Kelly (1987) استفاده کرده‌اند، زیرا این مدل تعداد کمتری متغیر و محدودیت دارد. آن‌ها نتایجشان را بر روی مجموعه داده‌های CAB با روش ابتکاری شبیه‌سازی تبرید Ernst and Krishnamoorthy (1996) و بسته‌ی تجاری نرم‌افزار GAMS با حل کننده‌ی MINOS-5 مقایسه کرده‌اند. آن‌ها پی بردند که عملکرد GAMS/MINOS-5 به طور قابل‌توجهی ضعیف‌تر از دیگر روش‌هاست زیرا که این نرم‌افزار برای کمینه کردن توابع محدّب طراحی شده است؛ همچنین آن‌ها پی بردند که روش شبکه‌ی عصبی Hopfield به صورت اثربخشی با شبیه‌سازی تبرید قابل محاسبه است.
برای مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور، Klincewicz (1996) یک الگوریتم بر اساس فن‌های صعود دوتایی و تنظیم دوگانه درون طرح انشعاب و تحدید ارائه کرده‌ است. محورها از مجموعه‌ی از قبل تعیین‌شده‌ی محورهای بالقوه انتخاب شده و الگوریتم بر روی مجموعه داده‌های CAB آزموده شده‌اند.
Sohn and Park (1997) مدل تخصیص ساده‌ی مکان‌یابی دو محور میانه را بررسی کرده‌اند. آن‌ها نشان داده‌اند که این مسئله را در حالتی که مکان‌های محور ثابت هستند، می‌توان در زمان چندجمله‌ای حل نمود. آن‌ها یک مدل برنامه‌ریزی خطی را برای مسئله‌ی تخصیص ساده با مکان‌های محور ثابت ارائه کرده و نشان داده‌اند که مسئله را می‌توان به مسئله‌ی حداقل برش تغییر شکل داد. از آنجایی که (n^2) راه برای انتخاب مکان‌های محور وجود دارد، مسئله‌ی مکان‌یابی دو محور را می‌توان در زمان چندجمله‌ای حل کرد.
Ernst and Krishnamoorthy (1998b) الگوریتم انشعاب و تحدید دیگری را برای تخصیص ساده پیشنهاد داده‌اند که مسائل کوتاه‌ترین مسیر را جهت به دست آوردن کران‌های پایین حل می‌نمود. برخلاف الگوریتم‌های انشعاب و تحدید مرسوم، الگوریتم آن‌ها به جای شروع با یک گره‌ی ریشه ساده با مجموعه‌ای از گره‌های ریشه شروع به کار می‌کرد. آن‌ها اثربخشی این الگوریتم را با مقایسه‌ی عملکردش با نتایج تهیه‌شده در Ernst and Krishnamoorthy (1996) بر روی مجموعه داده‌های AP و CAB محاسبه کرده‌اند. آن‌ها ادعا کرده‌اند که این الگوریتم جدید برای مقادیر کوچک p بسیار سریع‌تر عمل می‌کند و به حافظه‌ی اشغال‌شده‌ی کمتری نسبت به الگوریتم انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی ارائه‌شده در Ernst and Krishnamoorthy (1996) نیاز دارد. تا این تاریخ بزرگ‌ترین مسائل تخصیص ساده به صورت بهینه با این الگوریتم حل شده است. نویسندگان این مقاله مسائلی با 100 گره و 2 الی 3 محور را به ترتیب در حدود 228 و 2629 ثانیه حل نموده‌اند. با این وجود آن‌ها هنوز هم قادر به حل مسائلی با 100 گره و بیش از 3 محور در مدت زمان محاسباتی معقول نبودند.
Ernst and Krishnamoorthy (1998a) بر اساس همان ایده‌ای که برای حالت تخصیص ساده در Ernst and Krishnamoorthy (1996) ارائه کرده بودند، مدلی جدید برای تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور پیشنهاد دادند. این مدل جدید آن‌ها دارای (〖2n〗^3+n^2+n) متغیر است که تعداد (n) متغیر آن دوتایی است و به (〖4n〗^2+n+1) محدودیت خطی دارد. آن‌ها همچنین اثبات کردند که این مدل نسبت به مدل Skorin-Kapov et al. (1996) اثربخش‌تر است.
برای دستیابی به جواب‌های بهینه، Ernst and Krishnamoorthy (1998a) یک روش انشعاب و تحدید بر پایه‌ی

پایان نامه
Previous Entries پایان نامه با واژه های کلیدی عدم قطعیت، مکان‌یابی، مدل‌سازی Next Entries پایان نامه با واژه های کلیدی مکان‌یابی، شبیه‌سازی، بهبود عملکرد