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

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

برنامه‌ریزی خطی ارائه کرده‌اند. آن‌ها کران پایین را با تعیین نامساوی نقض شده و اضافه‌ی آن‌ها به برنامه‌ریزی خطی، تقویت کرده‌اند. آن‌ها همچنین دو روش ابتکاری پیشنهاد کرده‌اند. اولین روش یک روش ابتکاری بر پایه‌ی کوتاه‌ترین مسیر و دومی یک روش ابتکاری شمارش ضمنی است. اگر مکان‌های محور ثابت باشند، تصمیم تخصیص بدون شک این است: هر زوج گره‌ جریان خود را از کوتاه‌ترین مسیرها از طریق محورهای تخصیص‌یافته انتقال می‌دهند.
هر دوی این روش‌های ابتکاری از این ایده بهره می‌گیرند (Alumur and Kara (2008)). نویسندگان این مقاله نتایج محاسباتی را برای هر دوی مجموعه داده‌های CAB و AP ارائه داده‌اند. همان سال، همان نویسندگان مقاله‌ی دیگری (Ernst and Krishnamoorthy, 1998b) را نوشتند که در آن، آن‌ها الگوریتم انشعاب و تحدید دیگری بر حسب زمان CPU مورد نیاز ارائه کردند که دارای اثربخشی بیشتری بود.
این بار آن‌ها به جای ساده‌سازی برنامه‌ریزی خطی، کران‌های پایین را با حل مسئله‌ی کوتاه‌ترین مسیر به دست آوردند. این الگوریتم انشعاب و تحدید جدید به صورت یکپارچه‌ای از الگوریتم انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی Ernst and Krishnamoorthy (1998a) بهتر عمل می‌کند تا جایی که مسائل را با سرعت 500 برابر سریع‌تر و با حافظه‌ی مورد نیاز کمتری حل می‌کند. با این الگوریتم جدید آن‌ها قادر بودند تا جواب‌های دقیقی برای مسائل بزرگی که تا آن تاریخ در مرور ادبیات مطرح شده بود، به دست بیاورند. آن‌ها حتی توانستند تا برای مسائلی با بیش از 200 گره و بیش از 3 محور در مدت زمان 632 ثانیه به جواب دست یابند. با این وجود آن‌ها هنوز هم قادر به حل مسائل AP با بیش از 100 گره و بیش از 5 محور و همچنین 100 گره و بیش از 3 محور در مدت زمان معقولی نبودند.
Pirkul and Schilling (1998) یک روش ساده‌سازی لاگرانژی کارآمد را توسعه داده‌اند که کران‌های پایین و بالای فشرده‌تری در CPU time معقولی تولید می‌کند. آن‌ها از بهینه‌سازی زیر گرادیان بر روی ساده‌سازی لاگرانژی مدل استفاده کرده و نیز محدودیتی برشی برای یکی از زیر مسائل مهیا کرده‌اند. آن‌ها در آزمایش‌های محاسباتی بر روی مجموعه داده‌های CAB ادعا کرده‌اند که متوسط شکاف این روش ابتکاری 048/0 درصد است و حتی حداکثر شکاف زیر 1 درصد است (فشرده‌ترین کران‌ تمامی روش‌های ابتکاری تا به امروز).
در مقاله‌ی متعاقب Sohn and Park (1998) با ارائه‌ی مدلی جدید برای مسائل تخصیص ساده تعداد متغیرها و محدودیت‌ها را در حالتی که هزینه‌ی واحد جریان برابر است و به مسافت گره‌ها ارتباط دارد، هر چه بیشتر کاهش دادند. آن‌ها روش‌هایی جهت یافتن جواب‌های بهینه برای مسائل تخصیص با مکان‌های محور ثابت ارائه کرده‌اند. آن‌ها یک مدل عدد صحیح مختلط برای مدلی با مکان‌های محور ثابت که هزینه‌های ثابت راه‌اندازی اتصال‌ها نیز در نظر گرفته‌شده‌اند، ارائه کرده‌اند.
چندین مقاله به بررسی مدل تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور پرداخته‌اند. Abdinnour-Helm and Venkataramanan (1998) یک مدل عدد صحیح درجه دوم جدیدی بر اساس ایده‌ی جریان چند محصولی در شبکه پیشنهاد کرده‌اند. آن‌ها سپس این مدل را با یک روش انشعاب و تحدید که از ساختار اصولی شبکه‌ی مسئله جهت دستیابی به کران‌های پایین استفاده می‌کند، حل نموده‌اند. از آنجایی که روش انشعاب و تحدید به زمان قابل‌توجهی نیاز دارد، برای دستیابی سریع و اثربخش به جواب یک الگوریتم ژن شناختی ابتکاری نیز ارائه کرده‌اند.
Abdinnour-Helm (1998) یک روش ابتکاری جدید بر اساس ترکیب الگوریتم‌های ژن شناختی و جستجوی ممنوعه ابداع کرده ‌است. ابتدا از الگوریتم ژن شناختی جهت تعیین تعداد و مکان محورها استفاده شده و سپس هر نقطه‌ی تقاضا به نزدیک‌ترین محور خود اختصاص یافته تا جواب آغازینی برای روش ابتکاری جستجوی ممنوعه که تخصیص‌های بهینه را پیدا می‌کند، شکل بگیرد. او نتایجش را با الگوریتم ژن شناختی Abdinnour-Helm and Venkataramanan (1998) بر روی مجموعه داده‌های CAB مقایسه کرد و دریافت که استفاده از ترکیب همزمان جستجوی ممنوعه و الگوریتم ژن شناختی جواب‌های خیلی بهتری نسبت به الگوریتم ژن شناختی به دست می‌دهد.
O’Kelly and Bryan (1998) در مقاله‌ی خود اظهار داشته‌اند که فرض مستقل بودن هزینه‌های جریان نه تنها باعث اشتباه در محاسبه‌ی هزینه‌های کلی شبکه می‌شود، بلکه ممکن است موجب انتخاب ناصحیح مکان‌یابی و اختصاص محورها شود. آن‌ها یک تابع هزینه‌ی غیرخطی را پیشنهاد کرده‌اند که اجازه می‌دهد تا همگام با افزایش جریان‌ها، هزینه‌ها با سرعت کاهشی افزایش یابند. سپس این تابع هزینه‌ی غیرخطی را به وسیله‌ی یک تابع مقعّر پاره‌ای خطی تقریب زده و آن را با مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی محور ترکیب کرده‌اند.
آن‌ها با ارائه‌ی یک مثال گویا نشان داده‌اند که جواب بهینه با استفاده از این تابع هزینه‌ی جدید تغییر می‌کند. Bryan (1998) اندکی تغییر و توسعه در مدل O’Kelly and Bryan (1998) ایجاد کرده است. او ظرفیت‌ها و حداقل جریان‌هایی برای اتصال بین محورها و هزینه‌های وابسته‌ی جریان در سراسر اتصال‌های شبکه در نظر گرفته است.
Sasaki et al. (1999) مورد خاصی از مسئله تخصیص چندگانه‌ی مکان‌یابی p-محور میانه را در نظر گرفته‌اند که در آن هر مسیر در شبکه مجاز به استفاده از تنها یک محور است. آن‌ها این روش را مسئله‌ی 1-stop تخصیص چندگانه‌ی مکان‌یابی p-محور میانه نامیدند. آن‌ها یک مدل عدد صحیح مختلط ارائه کرده‌اند که می‌توان بیشتر به مسئله‌ی p-میانه تغییر شکل داد. آن‌ها یک الگوریتم انشعاب و تحدید و یک روش ابتکاری حریصانه پیشنهاد کرده‌اند و عملکرد الگوریتمشان را بر روی مجموعه داده‌های CAB آزمایش کرده‌اند.
Ernst and Krishnamoorthy (1999) دو مدل جدید برای تخصیص ظرفیت محدود مسئله‌ی مکان‌یابی محور پیشنهاد داده‌اند. مدل آن‌ها نسخه‌ی توسعه‌یافته‌ی مدل عدد صحیح مختلط قبلی است که برای مسئله‌ی p-محور میانه توسعه داده شده بود. آن‌ها دو روش ابتکاری ارائه کردند. اولی بر اساس شبیه‌سازی تبرید و دیگری بر اساس نزول تصادفی است. آن‌ها جواب‌های بهینه را با استفاده از روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی با کران بالای اولیه‌ی تولید کردند. آن‌ها همچنین برخی گام‌های پیش‌پردازش را جهت بهبود عملکرد الگوریتم انشعاب و تحدید ارائه کردند و الگوریتم پیشنهادی را بر مجموعه داده‌های CAB و AP که شامل هزینه‌های ثابت و محدودیت نمی‌شوند آزمایش کردند.
در Sohn and Park (2000) تمرکز بر روی مسئله‌ی تخصیص ساده با شبکه‌ای شامل 3 محور و مکان‌های محور ثابت صورت گرفته است. آن‌ها یک مدل برنامه‌ریزی عدد صحیح مختلط را ارائه و ویژگی‌های چند سطحی آن را بررسی کرده‌‌اند. اگر چه مسئله‌ی تخصیص ساده در سیستم دو محوری الگوریتم زمان چند سطحی دارد، نویسندگان این مقاله نشان داده‌اند که به محض اینکه تعداد محورها به 3 افزایش یابد، مسئله به حالت NP-hard تبدیل می‌شود.
Ebery et al. (2000) حالت تخصیص چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌‌یابی محور را بررسی کرده‌اند. مدل آن‌ها شبیه مدل Ernst and Krishnamoorthy (1998a) است فقط با این تفاوت که در این مدل هیچ محدودیتی در انتخاب محورهای بهینه وجود ندارد. آن‌ها یک الگوریتم ابتکاری کارآمد بر پایه‌ی کوتاه‌ترین مسیرها ارائه کرده‌اند و کران بالای به دست آمده از این روش ابتکاری را با یک روش حل انشعاب و تحدید تلفیق کرده‌اند.
تابع هزینه‌ی غیرخطی دیگری توسط Horner and O’Kelly (2001) پیشنهاد شده است. آن‌ها اذعان داشته‌اند که ضریب‌های کاهشی را می‌توان در کنار هر قسمتی از مسیر که حجم مناسبی دارد، به دست آورد. بنابراین همانند Bryan (1998) آن‌ها این تابع هزینه‌ی مقعر غیرخطی را که صرفه‌جویی اقتصادی را جبران می‌کند، در تمامی اتصال‌های شبکه در یک محیط نرم‌افزار سیستم‌های اطلاعات جغرافیایی (GIS)12 به کار برده‌اند و جواب‌های فرضیات متفاوت هزینه‌های شبکه را مقایسه کرده‌اند.
Ebery (2001) یک مدل برنامه‌ریزی عدد صحیح مختلط را برای تخصیص ساده‌ی p-محور ارائه کرده که مکان‌های محور ثابت هستند و برای حل نیاز به (n^2) متغیر و (n^2) محدودیت دارد. تعداد متغیرها و محدودیت‌های این مدل از تمامی مدل‌های ارائه‌شده در مرور ادبیات کمتر است اما چون مسئله‌ی مکان‌یابی p-محور میانه از نوع مسائل NP-hard است، در عمل مدل او در زمان محاسباتی بیشتری به جواب می‌رسید. نتایج محاسباتی او نشان می‌دهد که به ازای 2 و 3 محور این مدل جدید نسبت به مدل‌های ارائه‌شده در Sohn and Park (1997, 2000) و نسبت به روش کوتاه‌ترین مسیر ارائه‌شده در Ernst and Krishnamoorthy (1998b) اثربخش‌تر است.
روش ابتکاری شبیه‌سازی تبرید دیگری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه توسط Abdinnour-Helm (2001) پیشنهاد شده است. با این وجود Ernst and Krishnamoorthy (1996) به نتایج بهتری نسبت به Abdinnour-Helm (2001) دست‌یافته‌اند.
Nickel et al. (2001) در مقاله‌ی خود امکان‌پذیری چندمنظوره‌ی مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور را آزمایش کرده‌اند که این مدل کاربردهای فراوانی در زمینه‌ی حمل‌و‌نقل هوایی مسافران و محموله‌های ترافیکی هوایی، خدمات پیام‌رسانی و ارتباطات دارد.
Klincewicz (2002) نشان داد که برای یک مجموعه محور ثابت، مدل هزینه‌ی مقعر ارائه‌شده در O’Kelly and Bryan (1998) را می‌توان به مسئله‌ی کلاسیک ظرفیت نامحدود مکان‌یابی تسهیلات تبدیل کرد. او یک رویه‌ی شمارشی و تعدادی روش ابتکاری بر اساس جستجوی ممنوعه و روش جستجوی حریصانه تصادفی تطبیقی پیشنهاد کرد. او این الگوریتم را بر روی مجموعه داده‌های CAB امتحان کرد و نشان داد که مجموعه‌ی بهینه‌ی محورها به ازای توابع هزینه‌ی مختلف، تغییری نمی‌کنند.
Mayer and Wagner (2002) یک روش ابتکاری انشعاب و تحدید جدیدی تحت عنوان HubLocator (یابنده‌ی مکان) مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور توسعه داده‌اند. مزیت اصلی HubLocator در دستیابی به کران‌های پایین است. کران‌های پایین فشرده‌تر هستند و از شدّت دشواری محاسباتی مورد نیاز در الگوریتم انشعاب و تحدید برای دستیابی به جواب بهینه می‌کاهند.
آن‌ها HubLocator را با الگوریتم ارائه‌شده در Klincewicz (1996) و با CPLEX بر روی مجموعه داده‌های CAB و AP مقایسه کرده‌اند. برای مقایسه‌ی الگوریتمشان با CPLEX از یک مدل ریاضی بر اساس روش مدل‌سازی جریان چند محصولی که توسط Ernst and Krishnamoorthy (1998a) برای مسئله‌ی p-محور میانه ارائه شده بود، استفاده کرده‌اند. با وجود اینکه الگوریتم آن‌ها نسبت به روشی که در Klincewicz (1996) معرفی شده بود دارای برتری بود اما در مواردی نمی‌توانست از CPLEX عمل کند.
Sasaki and Fukushima (2003) مدلی را برای تخصیص چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور 1-stop ارائه کرده‌اند. مدل آن‌ها شامل محدودیت‌های ظرفیت بر روی هر دوی محورها و یال‌ها است. آن‌ها سپس این مدل را توسط یک الگوریتم انشعاب و تحدید با استراتژی تحدید ساده‌سازی لاگرانژی حل نموده و عملکرد آن را بر مجموعه داده‌های CAB آزمایش کرده‌اند.
Boland et al. (2004) در مقاله‌ی خود به این نکته اشاره‌ کرده‌اند که با وجود اینکه الگوریتم ابتکاری Ernst and Krishnamoorthy (1998a) به مراتب در مدت زمان و حافظه‌ی کمتری مسائل را حل می‌کند اما باز هم نسبت به قضیه‌ی کران‌های پایین ضعیف عمل می‌کند. به منظور غلبه بر این کاستی، آن‌ها برخی ویژگی‌های جواب بهینه‌ را جهت توسعه‌ی فن‌های پیش‌پردازش و محدودیت‌های فشرده‌تر تعیین نمودند. زمانی که آن‌ها این توسعه‌ها را بر مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه اجرا کردند، نتایج نشان می‌داد که محدودیت‌های فشردگی نتایج بهینه‌ی بهتری را در برخی موارد ارائه می‌کند.
Hamacher et al. (2004) تحقیقی چند سطحی را در مورد مدل تخصیص چندگانه‌ی

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