دانلود پروپوزال آماده: تخصیص ساده و چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور مبتنی بر رویکرد بهینه‌سازی استوار

قسمت هایی از پروپوزال:

۱- بیان مسأله:

……………………………

۲- اهمیت و ضرورت تحقیق:

……………………………

۳- پیشینه تحقیق:

اولین روش‌های ابتکاری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه توسطO’Kelly (1987) ارائه شده است. در هر دوی روش‌های ابتکاری او، تمامی انتخاب‌های ممکن مکان‌های p-محور به حساب می‌آیند. در روش ابتکاری اول (HEUR1)، گره‌های تقاضا به نزدیک‌ترین محور اختصاص ‌یافته‌اند و در روش ابتکاری دوم (HEUR2)، بر اساس مقدار تابع هدف، بهترین دو محور نزدیک به گره‌ی تقاضا انتخاب می‌شوند. از روش‌های ابتکاری برای حل مجموعه داده‌های CAB^[1] استفاده شده است.

Klincewicz (1991, 1992) در مقاله‌های خود روش‌های ابتکاری متنوعی را برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه توسعه داده است. Klincewicz (1991) یک روش ابتکاری مبادله‌ای بر اساس بهبود مکانی که هر دوی رویه‌های ساده و مضاعف مبادله را لحاظ می‌کند، ارائه کرده است. مقایسه‌ی او نشان داد که این روش‌های ابتکاری نسبت به روش‌های ابتکاری خوشه‌ای و روش ابتکاری پیشنهادی در O’Kelly (1987) دارای برتری است. Klincewicz (1992) یک روش ابتکاری جستجوی ممنوعه^[۲] و یک روش ابتکاری جستجوی حریصانه تصادفی (GRASP)^[3] پیشنهاد کرد که در هر دوی این روش‌ها گره‌های تقاضا به نزدیک‌ترین محورشان اختصاص ‌یافته‌اند. در هر دو مقاله‌ی Klincewicz, 1991, 1992)) از مجموعه داده‌های CAB و یک مجموعه داده‌ی بزرگ‌تر با ۵۲ نقطه‌ی تقاضا و بالغ بر ۱۰ محور جهت آزمایش عملکرد این روش‌های ابتکاری استفاده شده است.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) مقایسه کرده‌اند. نتایج آن‌ها بهتر است اما زمان واحد پردازشگر مرکزی^[۴] روش آن‌ها به دلیل تأکید بیشتر بر فاز تخصیص مسئله، بزرگ‌تر بود.

Campbell (1994b) اولین مدل برنامه‌ریزی خطی را برای تخصیص ساده/چندگانه‌ی ظرفیت محدود/نامحدود مسئله‌ی مکان‌یابی محور ارائه کرده است.

Campbell (1994) ادعا کرد که در غیاب محدودیت‌های ظرفیت بر روی اتصال‌ها، از آنجایی که جریان کلی برای هر زوج مبدأ/مقصد بایستی حداقل از دو محور متصل به هم گردش یابد، اگر دارای مقدار ۰ و ۱ باشد مسئله دارای جواب بهینه است. بنابراین هیچ نیازی به عدد صحیح بودن متغیر  نیست. او همچنین تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی ‌p-محور را با آستانه‌های جریان و هزینه‌های ثابت به عنوان یک برنامه‌ی عدد صحیح خطی مدل‌سازی کرد.

Campbell (1994b) اولین مدل برنامه‌ریزی عدد صحیح خطی را برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرد. مدل او تعداد () متغیر داشت که تعداد () متغیر آن دوتایی بودند و تعداد () محدودیت خطی داشت. او همچنین مسئله‌ را با آستا‌نه‌ی جریان مدل‌سازی کرد و مقدار حداقل جریان مورد نیاز برای سرویس‌دهی به هر اتصال را تعیین کرد. هنگامی‌که آستانه‌ی جریان در حداکثر مقدار خود هستند، هر گره‌ی تقاضا به یک تک محور اختصاص داده شد و مدل به تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه تقلیل یافت.

Aykin (1994) حالت ظرفیت محدود مسئله‌ی مکان‌یابی محور را با هزینه‌های ثابت که در آن محورها دارای ظرفیت محدودند، بررسی کرده‌ است. او مسئله را چنان مدل‌سازی کرده است که اتصالات مستقیم (بین گره‌های غیر محور) نیز مجازند. او یک الگوریتم انشعاب و تحدید پیشنهاد کرده که کران‌های پایین توسط ساده‌سازی لاگرانژی به دست می‌آیند. Aykin (1995a) مسئله‌ی مشابهی را با هزینه‌های ثابت و تعداد محورهای داده‌شده جهت مکان‌یابی تجزیه و تحلیل کرده است. او دو سیاست انتخاب محور را که سیاست‌های اکید و غیر اکید (اتصال مستقیم اجازه داده‌شده) نامیده، مقایسه کرده است. او یک الگوریتم شمارشی^[۵] و یک روش ابتکاری شبیه‌سازی تبرید^[۶] بر اساس روش ابتکاری حریصانه مبادله‌ای پیشنهاد کرده است.

O’Kelly et al. (1995) یک فن کران پایین بر اساس خطی سازی تابع هدف درجه دوم که مسافت‌ها جهت برقراری نامساوی مثلثی فرض شده‌اند، برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه کرده‌اند. آن‌ها با استفاده از این روش نشان داده‌اند که روش جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) برای مسائل کوچک‌تر (۱۰ الی ۱۵ گره) به طور متوسط دارای شکاف ۳/۳ درصد و برای مسائلی با ۲۰ الی ۲۵ گره به طور متوسط دارای شکاف ۹/۵ درصد است.

سپس Skorin-Kapov et al. (1996) با ساده‌سازی برنامه‌ریزی خطی مدل Campbell (1994b) جواب‌های بسیار کوچک‌تری به دست آوردند. آن‌ها مدل جدیدی برای تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه ارائه دادند. با تغییری که آن‌ها در مدل ایجاد کردند تعداد متغیرها به () کاهش یافت که از این تعداد، () متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز به () محدودیت کاهش یافت. بر اساس اطلاعات ما آن‌ها، اولین تلاش‌ها را برای حل بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه انجام دادند. آن‌ها با استفاده از جواب‌های بهینه‌ی مجموعه داده‌های CAB، بهینگی راه‌ جستجوی ممنوعه‌ی به دست آمده در مقاله‌ی Skorin-Kapov and Skorin-Kapov (1994) را اعتبار ببخشند.

مبرهن است که جواب‌های مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه کران پایینی را برای جواب بهینه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه مهیا می‌کند (Campbell, 1996). با استفاده از این ایده، Campbell (1996) دو روش ابتکاری برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه پیشنهاد داده است. این دو روش ابتکاری (MAXFLO و ALLFLO) جواب‌های مشتق شده از راه‌ مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه برای مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه هستند. در این روش‌های ابتکاری، تخصیص‌ها مطابق با نقش‌های متفاوت صورت گرفته اما تصمیم‌های مکانی همان تصمیم‌های قبلی هستند.

Ernst and Krishnamoorthy (1996) مدل برنامه‌ریزی خطی عدد صحیح جدیدی را برای مسئله‌ی تخصیص ساده ارائه کردند که دارای محدودیت‌ها و متغیرهای به مراتب کمتری بود و توانایی حل مسائل بزرگ‌تری را نیز داشت. آن‌ها انتقال‌های بین محور را به عنوان مسئله‌ی جریان چند محصولی تلقی کردند که در آن هر محصول بیانگر جریان ترافیک نشأت‌گرفته از یک گره‌ی خاص است. نویسندگان این مقاله چگونگی استفاده‌ی پست استرالیا (AP)^[7] از ضریب‌های کاهشی مختلف در جمع‌آوری و توزیع را مشاهده و مدل کردند و برای هر واحد هزینه‌ی جمع‌آوری و توزیع محصول یک ضریب کاهشی را اختصاص دادند ( برای ضریب کاهشی توزیع و  برای ضریب کاهشی جمع‌آوری محصول).

مدل آن‌ها دارای () متغیر بود که از این تعداد، () متغیر دوتایی بودند و تعداد محدودیت‌های خطی نیز () بود. آن‌ها یک روش ابتکاری شبیه‌سازی تبرید را توسعه و نشان داده‌اند که روش آن‌ها از هر دو منظر کیفیت جواب و زمان محاسباتی، با روش ابتکاری جستجوی ممنوعه‌ی Skorin-Kapov and Skorin-Kapov (1994) قابل مقایسه است. آن‌ها از این کران بالای به دست آمده از روش ابتکاری شبیه‌سازی تبرید برای توسعه‌ی راه حل روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی استفاده کردند. آن‌ها هر دوی روش‌های ابتکاری خود و الگوریتم انشعاب و تحدید را بر روی مجموعه داده‌های AP و CAB آزمایش کردند، اما آن‌ها قادر به حل مسائلی با بیش از ۵۰ گره نبودند.

O’Kelly et al. (1996) با ارائه‌ی داده‌های برابر جریان مدلی پیشنهاد کردند که باعث کاهش اندازه‌ی مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه شد. هنوز هم مدل جدیدی که آن‌ها معرفی کرده‌اند در بیشتر مقالات مورد استفاده قرار می‌گیرد. مهم‌ترین چیزی که آن‌ها در مقاله‌ی خود مطرح کردند، حساسیت جواب‌ها به ضریب کاهشی بین محورها () بود.

Campbell (1996) یک روش ابتکاری حریصانه-مبادله‌ای را برای مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور پیشنهاد کرده‌ است.Skorin-Kapov et al. (1996) یک مدل عدد صحیح مختلط جدید پیشنهاد کردند که در آن دو محدودیت مدل اولیه‌ی Campbell (1992) با حالت تجمعی‌شان جایگزین شده‌اند. این مدل دارای () متغیر است که تعداد () آن دوتایی است و نیاز به () محدودیت خطی دارد. این مدل باعث ساده‌سازی‌های برنامه‌ریزی خطی فشرده‌تری شد و تولید نتایجی یکپارچه در تقریباً تمام مواردی که از مجموعه داده‌های 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) مدل تخصیص ساده‌ی مکان‌یابی دو محور میانه را بررسی کرده‌اند. آن‌ها نشان داده‌اند که این مسئله را در حالتی که مکان‌های محور ثابت هستند، می‌توان در زمان چندجمله‌ای حل نمود. آن‌ها یک مدل برنامه‌ریزی خطی را برای مسئله‌ی تخصیص ساده با مکان‌های محور ثابت ارائه کرده و نشان داده‌اند که مسئله را می‌توان به مسئله‌ی حداقل برش تغییر شکل داد. از آنجایی که () راه برای انتخاب مکان‌های محور وجود دارد، مسئله‌ی مکان‌یابی دو محور را می‌توان در زمان چندجمله‌ای حل کرد.

Ernst and Krishnamoorthy (1998b) الگوریتم انشعاب و تحدید دیگری را برای تخصیص ساده پیشنهاد داده‌اند که مسائل کوتاه‌ترین مسیر را جهت به دست آوردن کران‌های پایین حل می‌نمود. برخلاف الگوریتم‌های انشعاب و تحدید مرسوم، الگوریتم آن‌ها به جای شروع با یک گره‌ی ریشه ساده با مجموعه‌ای از گره‌های ریشه شروع به کار می‌کرد. آن‌ها اثربخشی این الگوریتم را با مقایسه‌ی عملکردش با نتایج تهیه‌شده در Ernst and Krishnamoorthy (1996) بر روی مجموعه داده‌های AP و CAB محاسبه کرده‌اند. آن‌ها ادعا کرده‌اند که این الگوریتم جدید برای مقادیر کوچک p بسیار سریع‌تر عمل می‌کند و به حافظه‌ی اشغال‌شده‌ی کمتری نسبت به الگوریتم انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی ارائه‌شده در Ernst and Krishnamoorthy (1996) نیاز دارد. تا این تاریخ بزرگ‌ترین مسائل تخصیص ساده به صورت بهینه با این الگوریتم حل شده است. نویسندگان این مقاله مسائلی با ۱۰۰ گره و ۲ الی ۳ محور را به ترتیب در حدود ۲۲۸ و ۲۶۲۹ ثانیه حل نموده‌اند. با این وجود آن‌ها هنوز هم قادر به حل مسائلی با ۱۰۰ گره و بیش از ۳ محور در مدت زمان محاسباتی معقول نبودند.

Ernst and Krishnamoorthy (1998a) بر اساس همان ایده‌ای که برای حالت تخصیص ساده در Ernst and Krishnamoorthy (1996) ارائه کرده بودند، مدلی جدید برای تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور پیشنهاد دادند. این مدل جدید آن‌ها دارای () متغیر است که تعداد () متغیر آن دوتایی است و به () محدودیت خطی دارد. آن‌ها همچنین اثبات کردند که این مدل نسبت به مدل Skorin-Kapov et al. (1996) اثربخش‌تر است.

برای دستیابی به جواب‌های بهینه، Ernst and Krishnamoorthy (1998a) یک روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی ارائه کرده‌اند. آن‌ها کران پایین را با تعیین نامساوی نقض شده و اضافه‌ی آن‌ها به برنامه‌ریزی خطی، تقویت کرده‌اند. آن‌ها همچنین دو روش ابتکاری پیشنهاد کرده‌اند. اولین روش یک روش ابتکاری بر پایه‌ی کوتاه‌ترین مسیر و دومی یک روش ابتکاری شمارش ضمنی است. اگر مکان‌های محور ثابت باشند، تصمیم تخصیص بدون شک این است: هر زوج گره‌ جریان خود را از کوتاه‌ترین مسیرها از طریق محورهای تخصیص‌یافته انتقال می‌دهند.

هر دوی این روش‌های ابتکاری از این ایده بهره می‌گیرند (Alumur and Kara (2008)). نویسندگان این مقاله نتایج محاسباتی را برای هر دوی مجموعه داده‌های CAB و AP ارائه داده‌اند. همان سال، همان نویسندگان مقاله‌ی دیگری (Ernst and Krishnamoorthy, 1998b) را نوشتند که در آن، آن‌ها الگوریتم انشعاب و تحدید دیگری بر حسب زمان CPU مورد نیاز ارائه کردند که دارای اثربخشی بیشتری بود.

این بار آن‌ها به جای ساده‌سازی برنامه‌ریزی خطی، کران‌های پایین را با حل مسئله‌ی کوتاه‌ترین مسیر به دست آوردند. این الگوریتم انشعاب و تحدید جدید به صورت یکپارچه‌ای از الگوریتم انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی Ernst and Krishnamoorthy (1998a) بهتر عمل می‌کند تا جایی که مسائل را با سرعت ۵۰۰ برابر سریع‌تر و با حافظه‌ی مورد نیاز کمتری حل می‌کند. با این الگوریتم جدید آن‌ها قادر بودند تا جواب‌های دقیقی برای مسائل بزرگی که تا آن تاریخ در مرور ادبیات مطرح شده بود، به دست بیاورند. آن‌ها حتی توانستند تا برای مسائلی با بیش از ۲۰۰ گره و بیش از ۳ محور در مدت زمان ۶۳۲ ثانیه به جواب دست یابند. با این وجود آن‌ها هنوز هم قادر به حل مسائل AP با بیش از ۱۰۰ گره و بیش از ۵ محور و همچنین ۱۰۰ گره و بیش از ۳ محور در مدت زمان معقولی نبودند.

Pirkul and Schilling (1998) یک روش ساده‌سازی لاگرانژی کارآمد را توسعه داده‌اند که کران‌های پایین و بالای فشرده‌تری در CPU time معقولی تولید می‌کند. آن‌ها از بهینه‌سازی زیر گرادیان بر روی ساده‌سازی لاگرانژی مدل استفاده کرده و نیز محدودیتی برشی برای یکی از زیر مسائل مهیا کرده‌اند. آن‌ها در آزمایش‌های محاسباتی بر روی مجموعه داده‌های CAB ادعا کرده‌اند که متوسط شکاف این روش ابتکاری ۰۴۸/۰ درصد است و حتی حداکثر شکاف زیر ۱ درصد است (فشرده‌ترین کران‌ تمامی روش‌های ابتکاری تا به امروز).

در مقاله‌ی متعاقب 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-محور میانه را در نظر گرفته‌اند که در آن هر مسیر در شبکه مجاز به استفاده از تنها یک محور است. آن‌ها این روش را مسئله‌ی ۱-stop تخصیص چندگانه‌ی مکان‌یابی p-محور میانه نامیدند. آن‌ها یک مدل عدد صحیح مختلط ارائه کرده‌اند که می‌توان بیشتر به مسئله‌ی p-میانه تغییر شکل داد. آن‌ها یک الگوریتم انشعاب و تحدید و یک روش ابتکاری حریصانه پیشنهاد کرده‌اند و عملکرد الگوریتمشان را بر روی مجموعه داده‌های CAB آزمایش کرده‌اند.

Ernst and Krishnamoorthy (1999) دو مدل جدید برای تخصیص ظرفیت محدود مسئله‌ی مکان‌یابی محور پیشنهاد داده‌اند. مدل آن‌ها نسخه‌ی توسعه‌یافته‌ی مدل عدد صحیح مختلط قبلی است که برای مسئله‌ی p-محور میانه توسعه داده شده بود. آن‌ها دو روش ابتکاری ارائه کردند. اولی بر اساس شبیه‌سازی تبرید و دیگری بر اساس نزول تصادفی است. آن‌ها جواب‌های بهینه را با استفاده از روش انشعاب و تحدید بر پایه‌ی برنامه‌ریزی خطی با کران بالای اولیه‌ی تولید کردند. آن‌ها همچنین برخی گام‌های پیش‌پردازش را جهت بهبود عملکرد الگوریتم انشعاب و تحدید ارائه کردند و الگوریتم پیشنهادی را بر مجموعه داده‌های CAB و AP که شامل هزینه‌های ثابت و محدودیت نمی‌شوند آزمایش کردند.

در Sohn and Park (2000) تمرکز بر روی مسئله‌ی تخصیص ساده با شبکه‌ای شامل ۳ محور و مکان‌های محور ثابت صورت گرفته است. آن‌ها یک مدل برنامه‌ریزی عدد صحیح مختلط را ارائه و ویژگی‌های چند سطحی آن را بررسی کرده‌‌اند. اگر چه مسئله‌ی تخصیص ساده در سیستم دو محوری الگوریتم زمان چند سطحی دارد، نویسندگان این مقاله نشان داده‌اند که به محض اینکه تعداد محورها به ۳ افزایش یابد، مسئله به حالت NP-hard تبدیل می‌شود.

Ebery et al. (2000) حالت تخصیص چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌‌یابی محور را بررسی کرده‌اند. مدل آن‌ها شبیه مدل Ernst and Krishnamoorthy (1998a) است فقط با این تفاوت که در این مدل هیچ محدودیتی در انتخاب محورهای بهینه وجود ندارد. آن‌ها یک الگوریتم ابتکاری کارآمد بر پایه‌ی کوتاه‌ترین مسیرها ارائه کرده‌اند و کران بالای به دست آمده از این روش ابتکاری را با یک روش حل انشعاب و تحدید تلفیق کرده‌اند.

تابع هزینه‌ی غیرخطی دیگری توسط Horner and O’Kelly (2001) پیشنهاد شده است. آن‌ها اذعان داشته‌اند که ضریب‌های کاهشی را می‌توان در کنار هر قسمتی از مسیر که حجم مناسبی دارد، به دست آورد. بنابراین همانند Bryan (1998) آن‌ها این تابع هزینه‌ی مقعر غیرخطی را که صرفه‌جویی اقتصادی را جبران می‌کند، در تمامی اتصال‌های شبکه در یک محیط نرم‌افزار سیستم‌های اطلاعات جغرافیایی (GIS)^[8] به کار برده‌اند و جواب‌های فرضیات متفاوت هزینه‌های شبکه را مقایسه کرده‌اند.

Ebery (2001) یک مدل برنامه‌ریزی عدد صحیح مختلط را برای تخصیص ساده‌ی p-محور ارائه کرده که مکان‌های محور ثابت هستند و برای حل نیاز به () متغیر و () محدودیت دارد. تعداد متغیرها و محدودیت‌های این مدل از تمامی مدل‌های ارائه‌شده در مرور ادبیات کمتر است اما چون مسئله‌ی مکان‌یابی p-محور میانه از نوع مسائل NP-hard است، در عمل مدل او در زمان محاسباتی بیشتری به جواب می‌رسید. نتایج محاسباتی او نشان می‌دهد که به ازای ۲ و ۳ محور این مدل جدید نسبت به مدل‌های ارائه‌شده در 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) مدلی را برای تخصیص چندگانه‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور ۱-stop ارائه کرده‌اند. مدل آن‌ها شامل محدودیت‌های ظرفیت بر روی هر دوی محورها و یال‌ها است. آن‌ها سپس این مدل را توسط یک الگوریتم انشعاب و تحدید با استراتژی تحدید ساده‌سازی لاگرانژی حل نموده و عملکرد آن را بر مجموعه داده‌های CAB آزمایش کرده‌اند.

Boland et al. (2004) در مقاله‌ی خود به این نکته اشاره‌ کرده‌اند که با وجود اینکه الگوریتم ابتکاری Ernst and Krishnamoorthy (1998a) به مراتب در مدت زمان و حافظه‌ی کمتری مسائل را حل می‌کند اما باز هم نسبت به قضیه‌ی کران‌های پایین ضعیف عمل می‌کند. به منظور غلبه بر این کاستی، آن‌ها برخی ویژگی‌های جواب بهینه‌ را جهت توسعه‌ی فن‌های پیش‌پردازش و محدودیت‌های فشرده‌تر تعیین نمودند. زمانی که آن‌ها این توسعه‌ها را بر مدل تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی p-محور میانه اجرا کردند، نتایج نشان می‌داد که محدودیت‌های فشردگی نتایج بهینه‌ی بهتری را در برخی موارد ارائه می‌کند.

Hamacher et al. (2004) تحقیقی چند سطحی را در مورد مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور ارائه کرده‌اند. آن‌ها یک نقش عمومی در ارتباط با برداشتن سطوح از مسئله‌ی مکان‌یابی تسهیلات ظرفیت نامحدود به مدل تخصیص چندگانه‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور توسعه داده‌اند. آن‌ها یک مدل جدید را ارائه کرده‌اند که در آن تمام سطوح تعریف‌ شده‌اند.

برای مدل تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور، Labbé and Yaman (2004) به خانواده‌ای از نامساوی‌های معتبر دست‌یافته‌اند که سطح تعریف نامساوی‌ها را تعمیم می‌دهد و آن را می‌توان به زمان چندجمله‌ای تفکیک کرد.

Boland et al. (2004) برخی ویژگی‌های راه‌حل‌های بهینه‌ی هر دوی مدل‌های ظرفیت محدود و ظرفیت نامحدود تخصیص چندگانه‌ی مسئله‌ی مکان‌یابی محور را خلاصه‌شده بررسی کرده‌اند. بر اساس این نتایج آن‌ها پیش‌پردازش رویه‌ها و محدودیت‌های فشردگی‌ جهت بهبود ساده‌سازی‌های برنامه‌ریزی خطی را برای مدل‌های برنامه‌ریزی خطی عدد صحیح مختلط توسعه داده‌اند. آن‌ها همچنین محدودیت‌های پوشش-جریان را برای حالت ظرفیت محدود جهت بهبود زمان‌های محاسباتی به کار گرفته‌اند. این مدل‌ها منجر به یک کاهش کلی در زمان CPU مورد نیاز استفاده‌شده در CPLEX در قیاس با مدل‌های موجود شده است.

Elhedhli and Hu (2005) ازدحام محورها را در نظر گرفته و یک تابع هزینه‌ی غیر‌خطی محدّب را برای تابع هدف مدل تخصیص ساده‌ی مسئله‌ی مکان‌یابی p-محور میانه پیشنهاد داده‌اند. آن‌ها این مدل را با استفاده از توابع خطی پاره‌ای خطی سازی کرده و سپس ساده‌سازی لاگرانژی را به کار برده‌اند. از طریق مقایسه با مسئله‌ی غیر ازدحامی بر روی مجموعه داده‌های CAB، نویسندگان این مقاله ادعا کرده‌اند که نتایج مدل ازدحامی دارای توزیع تعادلی جریان بیشتری در محورها است.

Topcuoglu et al. (2005) الگوریتم ژن شناختی دیگری را برای تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور پیشنهاد داده‌اند. روش ابتکاری آن‌ها بر مجموعه داده‌های AP و CAB آزمایش شد و جواب‌های به دست آمده نسبت به روش ترکیبی Abdinnour-Helm (1998) در زمان محاسباتی کم‌تر و باکیفیت بهتری حاصل شدند.

Marin (2005a) یک مدل جدید برای حالت تخصیص چندگانه بر اساس همان ایده‌ای که در Ebery et al. (2000) وجود داشت، ارائه کرده‌اند اما از برخی ایده‌ها در مقاله‌ی Marin (2006) جهت کاهش اندازه‌ی مسائل بهره برده است. Marín (2005b) تعدادی سطوح معرف نامساوی‌های معتبر را برای مسئله‌ی ظرفیت نامحدود مکان‌یابی محور با هزینه‌های برآورده‌کننده‌ی نامساوی مثلثی ارائه کرده‌ است. او مسئله را الگوریتم تخفیف و برش حل نموده است.

Labbé et al. (2005) مدل تخصیص ساده‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور را در نظر گرفته‌اند که در آن هر محور ظرفیتی ثابت بر حسب ترافیکی که از آن عبور می‌کند، بررسی کرده‌اند. آن‌ها برخی خصوصیات چند سطحی این مسئله را بررسی کرده و الگوریتم انشعاب و تحدید را بر اساس این نتایج توسعه داده‌اند.

Kimms (2005) نیز فرض کرده است که صرفه‌جویی اقتصادی نه تنها در اتصال بین محورها بلکه می‌تواند در تمامی انواع اتصال‌ها اتفاق بیفتد. او مدلی را با تابع هزینه‌ی خطی پاره‌ای پیشنهاد داده است که متحمل هزینه‌ی ثابت استفاده از اتصال می‌شود. در مقاله‌ی Wagner (2004b) نویسنده  را یک تابع کمیتی وابسته‌ی غیر افزایشی ‌در مدل‌های تخصیص ساده‌ی پوششی محور تعریف کرده است.

Racunicam and Wynter (2005) یک مدل مکان‌یابی محور ظرفیت نامحدود برای تعیین مکان بهینه‌ی محورهای باربری چند وظیفه‌ای ارائه کرده‌اند. آن‌ها از یک تابع هزینه‌ی مقعّر غیرخطی برای نمایش صرفه‌جویی اقتصادی تولیدی در هر دوی اتصال‌های بین محوری و محور به مقصد استفاده کرده‌اند. تابع آن‌ها چنان است که هزینه‌های بین محوری بیشتر از هزینه‌های خطی سرحد مقدار آستانه و از آن به بعد کمتر است.

هنگامی‌که آن‌ها مدل خود را با تابع غیرخطی O’Kelly (1998) مقایسه کردند، اقدامات آن‌ها به صورت مستقیم بر روی جریان اتصال بود درحالی‌که اقدامات O’Kelly (1998) بر روی نسبت جریان اتصال بین محوری به جریان کلی شبکه انجام گرفته بود. آن‌ها این تابع را با یک تابع خطی پاره‌ای تقریب زده‌اند و تعدادی از ویژگی‌های چند سطحی مدل خطی جدید را ارائه کرده‌اند. همچنین دو روش ابتکاری متغیر-کاهش را توسعه داده و یک مورد مطالعه‌ای بر روی شبکه‌ی باربری Alpine تهیه ‌کرده‌اند.

Marín et al. (2006) یک مدل جدید پیشنهاد کرده‌اند که تعمیمی از مدل قبلی مسئله‌ی ظرفیت نامحدود مکان‌یابی محور با هزینه‌های برآورده‌کننده‌ی نامساوی مثلثی است و فرض داشتن ساختار هزینه برآورده‌کننده‌ی نامساوی مثلثی را تخفیف می‌دهد. مدل آن‌ها دارای محدودیت‌های کمتری بود و نسبت به همه‌ی مدل‌های قبل از خود دارای برتری بود.

Kratica et al. (2007) از دو الگوریتم ژن شناختی برای حل مدل تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی p-محور میانه استفاده کرده‌اند. آن‌ها با استفاده از این دو الگوریتم ابتکاری خود توانسته‌اند مسائلی با ۲۰۰ گره و ۲۰ محور را به صورت بهینه در زمان محاسباتی معقولی حل نمایند.

در مقاله‌ی Tan and Kara (2007)، نویسندگان آن بر روی سیستم‌های تحویل بار تمرکز کرده‌اند. آن‌ها با تجزیه و تحلیل شرکت‌های فعال ترکیه در این زمینه، محدودیت‌ها، التزامات و معیارهای مسئله‌ی تخصیص ساده‌ی مکان‌یابی محور را در ارتباط با سیستم‌های تحویل بار تعیین کرده‌اند.

Cunha and Silva (2007) بدون اطلاع از کار Topcuoglu et al. (2005) الگوریتم ژن شناختی دیگری را برای تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور ارائه کردند که با روش ابتکاری شبیه‌سازی تبرید تلفیق شده بود. این روش ترکیبی جدید از هر دوی الگوریتم‌های ژن شناختی Abdinnour-Helm (1998) and Abdinnour-Helm and Venkataramanan (1998) عمل می‌کرد.

Cunha and Silva (2007) مسئله‌ی پیکر‌بندی شبکه‌ی محور را برای یک شرکت حمل‌و‌نقل کمتر از گنجایش یک کامیون در برزیل در نظر گرفته‌اند. آن‌ها در مدل‌شان به جای ثابت در نظر گرفتن ضریب کاهشی محور به محور، ضریب کاهشی را بر طبق میزان کل باربری بین محورها متغیر فرض کرده‌اند.

روش ابتکاری دیگری که برای تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور پیشنهاد شده است، Chen (2007) است. روش ابتکاری ترکیبی او بر اساس روش شبیه‌سازی تبرید، جستجوی ممنوعه و روندهای بهبود‌یافته است. این روش ابتکاری هم از نظر کیفیت جواب‌ها و هم از دیدگاه زمان محاسباتی از روش ارائه‌شده در Topcuoglu et al. (2005) نیز بهتر عمل می‌کند.

Canovas et al. (2007) دوباره یک روش ابتکاری را برای تخصیص ساده‌ی ظرفیت نامحدود مسئله‌ی مکان‌یابی محور بر اساس فن صعود دوتایی ارائه کردند. آن‌ها سپس این روش ابتکاری را در الگوریتم انشعاب و تحدید اجرا کردند. با توجه به نتایج به دست آمده از اجرای این روش بر روی مجموعه داده‌های CAB و AP آن‌ها قادر به حل مثال‌هایی با ۱۲۰ گره نیز بودند.

Costa et al. (2007) یک روش متفاوت را برای مدل تخصیص ساده‌ی ظرفیت محدود مسئله‌ی مکان‌یابی محور پیشنهاد کرده‌اند. به جای استفاده از محدودیت‌های ظرفیت بر روی میزان جریان پردازش‌شده در محورها نویسندگان یک تابع هدف دوم برای مدل ریاضی‌شان معرفی کرده‌اند که مدت زمان پردازش جریان‌ها را حداقل می‌کند. آن‌ها دو مسئله‌ی دو معیاره‌ی متفاوت را در نظر گرفته‌اند. علاوه بر حداقل کردن هزینه‌ی کل در هر دوی مسائل، در اولی آن‌ها مدت زمان کل پردازش جریان را در محورها حداقل کرده‌اند و در دومین مسئله حداکثر زمان سرویس‌دهی محورها را کمینه کرده‌اند. آن‌ها یک روش تکراری را پیشنهاد داده‌اند که برای محاسبه‌ی جواب‌های غیر غالب شده از آن استفاده شده است.

[۱] Civil Aviation Board

[۲] Tabu Search

[۳] Greedy randomized search procedure

[۴] CPU time

[۵] Enumeration Algorithm

[۶] Simulated Annealing

[۷] Australian post

[۸] Geographical system information

……………………………

۴- اهداف تحقیق:

…………………………………….

۵- فرضيه ‏هاي تحقیق:

…………………………………….

۶- مدل تحقیق

…………………………

۷- سوالات تحقیق:

…………………………………….

۸- تعريف واژه‏ها و اصطلاحات فني و تخصصی (به صورت مفهومی و عملیاتی):

…………………………………….

۹- بیان جنبه نوآوری تحقیق:

………………………….

۱۰- روش شناسی تحقیق:

الف: شرح كامل روش تحقیق بر حسب هدف، نوع داده ها و نحوه اجراء (شامل مواد، تجهيزات و استانداردهاي مورد استفاده در قالب مراحل اجرايي تحقيق به تفكيك):

………………………….

ب- متغيرهاي مورد بررسي در قالب یک مدل مفهومی و شرح چگونگی بررسی و اندازه گیری متغیرها:

…………………………………….

ج – شرح کامل روش (ميداني، كتابخانه‏اي) و ابزار (مشاهده و آزمون، پرسشنامه، مصاحبه، فيش‏برداري و غيره) گردآوري داده‏ها :

…………………………………….

د – جامعه آماري، روش نمونه‏گيري و حجم نمونه (در صورت وجود و امکان):

…………………………………….

ر- روش نمونه گیری و حجم نمونه:

…………………………………….

ز- ابزار تحقیق:

…………………………………….

هـ – روش‌ها و ابزار تجزيه و تحليل داده‏ها:

…………………………………….

منابع :

…………………………………….

آسان داک: www.Asandoc.com

دانلود نمونه پروپوزال تکمیل شده، پروژه پر شده، طرح پیشنهادیه آماده