مسائل معکوس مکان‌یابی تسهیلات 2- میانه پشتیبان با تغییر طول یال‌ها و وزن رئوس روی درخت و تغییر مختصات نقاط در صفحه

مقدمه

مسائل بهینه‎سازی مرتبط با مفاهیم مکان‌یابی در چندین دهۀ گذشته توجه ویژه‎ای را به‌خود اختصاص داده‎اند؛ به‎نحوی‌که در سال‎های اخیر مطالعات مکان‌یابی به یکی از عناصر کلیدی در موفقیت و بقای مراکز صنعتی و تولیدی تبدیل شده است. توجه ویژه به این مفاهیم به‌چند دلیل است؛ نخست به‌دلیل اینکه به‎طور مداوم در تمام سطوح برنامه‎ریزی بشری حضور داشته‎اند؛ دوم به‌دلیل اینکه تصمیم‎گیری‎های مکانی دارای ماهیت استراتژیک هستند (یعنی بیشتر آنها با منابع عظیمی از سرمایه سروکار دارند و تأثیرات اقتصادی آنها بلندمدت است)، درنهایت به‌دلیل اینکه بیشتر مدل‎های مکان‌یابی به‌سختی حل می‎شوند و حتی پایه‎ای‎ترین مدل‎های مرتبط به این مسائل دارای پیچیدگی محاسباتی بالایی هستند.

مکان‌یابی یکی از علوم مهندسی صنایع است که توجه به آن سبب کاهش هزینه‎ها و موفقیت واحدهای صنعتی می‎شود. مکان‌یابی تسهیلات و تأسیسات از کاربردی‌ترین زمینه‌های پژوهشی است که در بسیاری از شاخه‌های علوم گسترده شده است. ازجملۀ این شاخه‌ها تحقیق در عملیات، علوم مدیریت، مهندسی صنایع، جغرافیا و دیگر شاخه‌های مرتبط هستند.

امروزه مسائل مکان‌یابی کلاسیک به این‌صورت شناخته می‎شود که مجموعه‎ای از نقاط، مکان مشتریان هستند و هدف پیدا‌کردن بهترین مکان برای یک یا چندین سرویس‌دهنده است؛ به‎نحوی‎که با‌توجه‌به شرایط موجود به‌بهترین شکل به مشتریان سرویس‌دهی شود.

مسائل - میانه از جمله مسائل پرکاربر و مهم مکان‌یابی هستند. در یک مسئلۀ - میانه،  نقطه v_i، به‌ازاءِ ، داده شده است. هریک از این نقاط دارای وزن  w_i هستند. در این نوع مسائل باید به‌دنبال پیدا‌کردن مجموعه‌ای شامل  نقطه ( - میانه) مانند بود؛ به‎نحوی‎که مجموع وزنی این نقاط تا کل  نقطۀ داده‌شده‎ حداقل شود؛ به‎‎عبارت دیگر باید تابع هدف زیر حداقل شود.

d(v_i, m_j)، فاصلۀ بین نقاط v_i و  است (فتحعلی^[i]، 2006). از طرف دیگر در طول دهه‎های اخیر تلاش‎های زیادی برای ایجاد مدل‎های مکان‌یابی‎ انجام شده است که مشخصه‎های بیشتری از دنیای واقعی را در نظر می‎گیرند. ازجمله مشخصه‎های پرکاربرد و مهمی که در نظریه‎های اخیر تحقیق در عملیات ظاهر شده است، مفاهیم "عدم‌قطعیت" و "مکان‌یابی معکوس" هستند.

در مسئلۀ مکان‌یابی معکوس، بر‌خلاف مسئلۀ مکان‌یابی کلاسیک، سرویس‌دهنده‎ها از قبل مشخص (انتخاب شده) هستند. آنگاه باید به‌جای پیدا‌کردن مکان‎های بهینه برای این سرویس‌دهندها، این نقاط به‎وسیلۀ تغییر در بعضی پارامترهای اساسی مسئله (مثل مسیرهای ترافیکی) با کمترین هزینۀ ممکن یا با استفاده از بودجه‌ای ثابت و مشخص بهبود یابند (باروقی و همکاران^[ii]، 2011). باتوجه‌به اینکه هدف در این نوع مسائل بهینه‌شدن سرویس‌دهنده‎ها با کمترین هزینۀ ممکن و یا بهبود سرویس‌دهنده‎ها با استفاده از بودجه‌ای محدود است، این نوع مسائل را به‎ترتیب مسائل معکوس نوع حداقل هزینه^[iii] و مسائل معکوس نوع محدودیت بودجه‎ای^[iv] می‎نامند (بورکارد و همکاران^[v]، 2006).

از طرف دیگر، تئوری مکان‌یابی به‎طور سنتی علاقه‎مند به مسائلی است که وزن سرویس‌دهنده‎ها و در دسترس بودن آنها با قطعیت مشخص باشد؛ اما در واقعیت برآورد دقیق همۀ پارامترها امکان‌پذیر نیست؛ بنابراین مدل‎های مکان‌یابی با عدم‌قطعیت بررسی شده‎اند و برخی از حالت‎های آنها تعریف و مطالعه شده است (وانگ و همکاران^[vi]، 2009). در این مدل‎ها ممکن است سرویس‌دهنده‎ها شکست بخورند و مشتریان اختصاص‌داده‌شده به این سرویس‌دهنده‎ها مجبورند از سرویس‌دهنده‎های درحال کار سرویس بگیرند. این مسائل مبتنی‌بر این ویژگی را به‌اختصار مسائل مکان‌یابی پشتیبان می‎نامند (وانگ و همکاران، 2009).

مروری بر ادبیات

نظریۀ مکان‌یابی به‌شکلی که امروزه استفاده می‌شود با منتشر‌شدن کتاب آلفرد وبر^[vii] (1909) پدید آمد. وبر در این کتاب نتایج پژوهش‌های خود را دربارۀ صنایع کارخانه‌ای ارائه کرد؛ اما مطالعات جدی روی مکان‌یابی از زمانی شروع شد که حکیمی^[viii] (1946)، تابع هدف را به دو صورت کمترین مجموع و حداقل- حداکثر مدل‌سازی کرد؛ در‌واقع حکیمی روابط -میانه را ابداع کرد. همچنین نخستین طبقه‎بندی مدل‌های مختلف مکان‌یابی در مقالات هندلر^[ix] و میرچندانی^[x] (1979) مشاهده می‌شود.

بورتن^[xi] و توئینت^[xii] (1992)، با بررسی مسئلۀ معکوس کوتاه‌ترین مسیر، نخستین کسانی بودند که درزمینۀ مسائل بهینه‎سازی معکوس روی شبکه‎ها پژوهش انجام دادند.

برمن و همکاران^[xiii] (2000)، برای نخستین‌بار مسئلۀ 1- میانه معکوس نوع محدودیت بودجه‎ای را روی درخت مطالعه کردند و برای حل آن الگوریتمی خطی به ‎دست آوردند. بورکاردو همکاران (2006)، ثابت کردند مسئلۀ 1- میانه معکوس نوع محدودیت بودجه‎ای با تغییرات طولی یال، روی گراف‎های عمومی، NP – سخت است. همچنین آنها برای دور گراف‎ها، الگوریتم خطی ارائه کردند. بورکارد و همکاران^[xiv] (2008)، مسئلۀ 2- میانه معکوس نوع محدودیت بودجه‎ای روی درخت‎ها را بررسی کردند. آنها برای حل آن الگوریتمی از مرتبۀ ، ارائه دادند.

وانگ و همکاران^[xv] (2010)، مسئلۀ 2- میانه معکوس نوع محدودیت بودجه‎ای روی دورها را به مسئلۀ 3- میانه معکوس نوع محدودیت بودجه‎ای روی یک مسیر تبدیل کردند و از این طریق نشان دادند این مسئله در زمان چندجمله‎ای حل می‌شود. همچنین جیانفنگ و همکاران^[xvi] (2012)، مسئلۀ 1- میانه معکوس نوع محدودیت بودجه‎ای را با یک محدودیت اضافه روی درخت‎ها بررسی کردند و ثابت شد که این مدل به دو زیرمسئلۀ معادل تقسیم‌پذیر است. این زیر‌مسئله‎ها به‎ترتیب با الگوریتم‎های حداقل برش^[xvii] و حریصانه^[xviii] حل می‌شوند.

در سال‌های اخیر نیز نگوین^[xix](2016)، معکوس نوع محدودیت بودجه‎ای مسئلۀ 1- مرکز روی درخت‎های وزن‎دار را مطالعه کردند و برای آن الگوریتمی از مرتبۀ زمانی  ارائه کرد که تعداد رئوس درخت است.

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

گلوی^[xx] (2008)، مسئلۀ 1- میانه معکوس نوع حداقل هزینه را با تغییرات وزن رأسی روی درخت (که قبلا بورکارد و همکارانش در مقاله بورکارد و همکاران^[xxi] (2004)ارائه داده بودند) به‎صورت مدل کوله‌پشتی مدل‌سازی کرد و نشان داد که این مسئله در زمان خطی حل‌شدنی است. از طرف دیگر، باروقی و همکاران (2011) نشان دادند مسئلۀ - میانه معکوس نوع حداقل هزینه با تغییرات طول یالی روی شبکه‎های کلی مسئله‌ای NP– سخت است؛ بنابرین آنها شبکه‎های خاصی چون درخت‎ها و گراف‎های ستاره‎دار را در نظر گرفتند و الگوریتم‎هایی از مرتبه چندجمله‎ای برای حل آنها ارائه دادند.

باروقی و همکاران (2010)، مسئلۀ 1- میانه معکوس را با تغییر مختصات نقطه‎ای ارائه کردند. سپاسیان و رهبرنیا^[xxii] (2015)، نیز مسئلۀ 1- میانه معکوس را با تغییرات هم‌‌زمان وزن رأسی و طول یالی روی درخت بررسی کردند و الگوریتمی برای آن ارائه کردند.

برای نخستین‌بار اشنایدر^[xxiii]و دسکین^[xxiv]( 2005)، مدل قابلیت اطمینان را برای مسائل مکان‌یابی بررسی کردند. مسائل مکان‌یابی 2- میانه و 2- مرکز پشتیبان، نخستین‌بار به‌وسیلۀ وانگ و همکاران (2009) بررسی شد. آنها به‎ترتیب الگوریتم‎هایی با زمان‎های  و  را برای این دو مسئله ارائه کردند. چنگ و همکاران^[xxv] (2014) نیز مسئلۀ مکان‌یابی 2- میانه پشتیبان را روی گراف‎های بلوکی در زمان  حل کردند.

همچنین فتحعلی (2014)، مسئلۀ مکان‌یابی چند‌وسیله‎ای پشتیبان در صفحه را بررسی کردند و الگوریتمی تکراری برای حل آن ارائه دادند. مدبر و همکاران (1395) نیز مسئلۀ 2- مرکز ناخوشایند پشتیبان روی درخت‎ها را بررسی و الگوریتم‎هایی چندجمله‎ای برای حل آن ارائه کردند.

در این پژوهش برای نخستین‌بار معکوسِ مسئلۀ بهینه‎سازی 2- میانه پشتیبان مطالعه شده است. در قسمت 3 مقاله، تعاریف و نمادگذاری‎های لازم برای قسمت‎های بعدی مقاله آورده شده است. در قسمت 4 مقاله، معکوس نوع محدودیت بودجه‎ای و معکوس نوع حداقل هزینه برای مسئلۀ 2- میانه پشتیبان در فضای گسسته (گراف‎ها و درخت‎ها) مطالعه می‌شود. در‌ادامه در قسمت 5 مقاله، معکوس نوع محدودیت بودجه‎ای مسئلۀ 2-میانه پشتیبان درفضای پیوسته و با تغییر در مختصات نقاط، مدل‌سازی ریاضی می‌شود و با‌توجه‌به NP- سخت‌بودن مسئلۀ مذکور، روش‎های فرا ابتکاری ازدحام ذرات (PSO) و الگوریتم بهبودیافتۀ ازدحام ذرات (IPSO)، برای حل آن پیشنهاد شده است. در قسمت 6 نتایج و پیشنهادات لازم برای کارهای آتی ذکر شده است. در‌انتها در پیوست حساسیت پارامتر‎های مختلف مسئله درحالت پیوسته ارائه و چند مثال در این حالت بررسی شده است.

تعریف مسئله و نمادگذاری

در این قسمت مفاهیم و نمادگذاری‎های لازم در  مقاله بیان می‎شود. فرض کنید، ، گرافی ساده و بدون‌جهت است که  مجموعه رأس‎ها،  مجموعه یال‎ها، ، تابع وزنی رأس‎ها و ، تابع طول یال‎های گراف  است. مجموع وزنی رأس‎های گراف  با نماد ، نمایش داده می‌شود؛ به‎نحوی‌که .

فاصلۀ بین دو رأس و در گراف  است و به‎صورت مجموع طولی کوتاه‌ترین مسیر بین دو رأس  و ، تعریف می‎شود. اگر در گراف ،  باشد، در‌این‎صورت زیر‌گراف  شامل  به‎صورت  نشان داده می‌شود. همچنین در درخت ، مسیری یکتا بین دو رأس  و  به‎صورت  نمایش داده می‌شود.  برای هر زوج رأس  رابطۀ زیر قرار می‌گیرد.

به‎طوری‎که  و  است؛ بنابراین با‌توجه‌‌به تعریف (2)، در یک درخت هریک از مجموعه‎های  و ، زیرگراف همبند را تولید می‎کنند. این دو مجموعه با حذف یال  به‎ دست می‎آید که یال ، یال مرکزی  و  و همان نقطۀ میانگین مسیر  است.

مسئله مکان‌یابی 2- میانه پشتیبان: در مسئلۀ مکان‌یابی 2- میانه پشتیبان، هر سرویس‌دهنده ممکن است با احتمالی شکست بخورد. با این فرض که سرویس‌دهنده‎ها نمی‎توانند به‎طور هم‌زمان شکست بخورند، سرویس‌دهندۀ دیگر مسئولیت سرویس‎دهی را بر عهده می‎گیرد. فرض کنید، و  احتمال شکست دو سرویس‌دهنده در مسئلۀ 2- میانه پشتیبان هستند. جواب مسئله با زوج رأس  نشان داده می‎شود؛ به‎نحوی‌که ، مکان سرویس‌دهنده با احتمال شکست  و ، مکان سرویس‌دهنده با احتمال شکست هستند. در این مقاله فرض شده است احتمال شکست دو سرویس‌دهنده با هم برابر هستند؛ یعنی، .

هدف مسئلۀ 2- میانه پشتیبان حداقل‌کردن مجموع فاصله از تمام نقاط به مجموعه سرویس‌دهنده‎های در‌حال کار است؛ درواقع هدف حداقل‌کردن تابع زیر است.   

تعریف 1 (وانگ و همکاران، 2009):  فرض کنید درخت  و احتمال شکست  داده شده‌اند. مسئلۀ 2- میانه پشتیبان روی درخت به‌دنبال پیدا‌کردن یک جفت رأس مانند  است؛ ‎طوری‌که تابع هدف زیر حداقل شود.

‎طوری‌که،  و 

اگر  یال مرکزی m₁ و m₂ در درخت باشد، دراین‎صورت با حذف یال ، درخت T به دو زیردرخت T_xو T_yتقسیم می‎شود؛ طوری‌که x  درT_xوy در  T_yقرار دارد. 

لم 1 (وانگ و همکاران، 2009): اگر ، 2- میانه پشتیبان روی رأس‎های مختلف درخت  باشند، آنگاه  و ، به‎ترتیب میانه‎های زیر‌درخت‎های  و  هستند؛ به‌نحوی‌که  یال مرکزی  و  است.

در لم بالا  همان زیردرخت T_x است که وزن رأس در آن  در نظر گرفته شده است. به‎طور مشابه زیردرخت  همان زیردرخت T_y است که وزن رأس  y در آن  در نظر گرفته‎ شده است (وانگ و همکاران، 2009).

معکوس مسألۀ 2- میانه پشتیبان در فضای گسستۀ گراف‎ها 

در مسئلۀ 2- میانه پشتیبان، هدف حداقل‌کردن رابطۀ (3) است. درحالت معکوس در فضای گسسته هدف این است که با تغییر پارامتر‎های اصلی مسئله، مانند وزن نقاط و طول یال‎ها و با کمترین هزینۀ ممکن، دو رأس دلخواه  و ، تبدیل به 2- میانه پشتیبان شوند. در این قسمت معکوس نوع حداقل هزینه و نوع محدودیت بودجه‎ای مسئلۀ 2- میانه پشتیبان درحالت گسسته با تغییر در وزن رئوس گراف و طول یال‎های گراف بررسی می‌شوند.

مسئلۀ 2- میانه پشتیبان معکوس نوع حداقل هزینه^[xxvi](BI2MP)با روش تغییر در وزن رئوس گراف: در مسئلۀ BI2MP به‌روش تغییر در وزن رئوس، هدف این است که با تغییر در وزن رئوس یک گراف و با کمترین هزینه، دو رأس از پیش تعیین شده بهینه شوند. فرض کنید  تعداد رئوس گراف  و  هزینۀ متحمل‌شده از افزایش هر واحد وزن رأس  و  هزینۀ متحمل‌شده از کاهش هر واحد وزن رأس  باشند. همچنین  و  به‎ترتیب میزان افزایش و کاهش وزن رئوس  یعنی هستند؛ بنابراین هزینۀ متحمل‌شده از تغییر وزن رئوس برابر با  است. همچنین زوج رأس  باید بهینه شوند؛ بنابراین باید برای هر ، نامساوی  برقرار باشد.  ، مقدار تابع هدف مسئلۀ 2-میانه پشتیبان است که در رابطۀ (3) بیان شده است.

حال مسئلۀ BI2MP با روش تغییر در وزن رئوس گراف  به‎صورت زیر مدل‌سازی می‌شود. این مدل یک مدل برنامه‎ریزی غیرخطی با تعداد محدودیت‎های از مرتبۀ  است. مسئلۀ بهینه‎سازی بالا، روی گراف‎های کلی از نوع مسائل NP- سخت است؛ بنابراین این مسئله برای گراف‎های خاصی مانند درخت‎ها بررسی شده‌اند.

در مسئلۀ BI2MP، دو رأس (m₁, m₂)جواب مسئله هستند؛ بنابراین با‌توجه‌به لم 1،  و  به‎ترتیب میانه‎های زیردرخت‎های X (e) وY(e) هستند. طبق تعریف میانه‌بودن  برای زیردرخت X (e)، رابطۀ زیر برقرار است.

و به‎طور مشابه  در زیردرختY(e)، میانه است؛ بنابراین رابطۀ زیر برقرار است.

روابط (10) و (11) جایگزین رابطۀ (7) می‎شوند. همچنین با جایگذاری‌ محدودیت (8) در روابط (10) و (11) و مقداری عملیات ریاضی، مسئلۀ BI2MP با تغییر در وزن رئوس درخت به‎صورت زیر ‎مدل‌سازی می‎شود.

در محدودیت‎های (13) و (14) همۀ ضرائب ، ،  و ، مقادیر ثابتی هستند و به‌صورت زیر تعریف می‌شوند.

این مسئله به‎صورت زیر بازنویسی می‌شود.

به‎نحوی‌که:

 مسئلۀ BI2MP روی درخت از مسئلۀ برنامه‎ریزی غیرخطی با تعداد محدودیت‎هایی از مرتبۀ ، به مسئلۀ برنامه‌ریزی خطی و حداکثر با  محدودیت تبدیل شده است؛ بنابراین با روش‎های حل مسائل برنامه‎ریزی خطی حل‌شدنی است.

مسئلۀ 2- میانه پشتیبان معکوس نوع حداقل هزینه با روش تغییر در طول یال‎های گراف: فرض کنید  هزینۀ متحمل‌شده از افزایش هر واحد طول یال  و  هزینۀ متحمل‌شده از کاهش هر واحد طول یال  باشند.  و  به‎ترتیب میزان افزایش و کاهش طول یال  هستند که  طول یال  است همچنین  کوتاه‌ترین مسیر بین دو رأس  در گراف  است. در این مسئله هدف این است که با کمترین هزینۀ ممکن از تغییر طول یال‎های گراف (یعنی حداقل‌کردن) دو رأس دلخواه  و ، تبدیل به 2-میانه پشتیبان شوند؛ بنابراین مسئلۀ BI2MP با تغییر در طول یال به‌صورت زیر مدل می‎شود.

مدل بالا مدلی غیرخطی با تعداد محدودیت‎های  است. مسئلۀ بالا برای یک گراف کلی از نوع مسئلۀ NP-سخت است؛ ولی اگر گراف مدنظر درخت در نظر گرفته‌ شود، مدل بالا به‎صورت مدل برنامه‎ریزی خطی بیان‌ می‌شود.

 فرض کنید ، درختی است که  ، همچنین  و  دو رأسی باشند که هدف بهینه‌کردن آنها است. ازآنجایی‌که در معکوس مسئلۀ 2- میانه پشتیبانِ حاضر،  و  جواب‎های مسئلۀ از قبل مشخص هستند، با‌توجه‌به لم 1 می‎توان گفت،  و  به‎ترتیب میانه‎های زیردرخت‎های X (e) وY(e) هستند؛ بنابراین با‌توجه‌به شرط میانه‌بودن  برای زیردرخت‎X (e) رابطۀ زیر برقرار است.

از طرفی رابطۀ 26 به‌صورت زیر است.

با قراردادن روابط (26) در شرط (25)، رابطۀ زیر برقرار می‌شود.

و به‎طور مشابه برای شرط میانه‌بودن  در زیردرخت  Y(e)به‌صورت زیر تعریف می‌شود.

به‌نحوی‌که:

با قرار‌دادن شروط (27) و (28) به‌جای محدودیت (21)، مسئلۀ BI2MP با روش تغییر طول یالی به‎صورت زیر مدل‌سازی می‎شود. این مدل یک مسئلۀ بهینه‎سازی خطی روی یک مسیر و با حداکثر  محدودیت است.  و  نیز حداکثر میزان افزایش یا کاهش در طول یال هستند.

مسئلۀ 2- میانه پشتیبان معکوس نوع محدودیت بودجه‎ای(BR2MP) با تغییر در وزن رئوس گراف: فرض کنید ، بودجۀ مدنظر برای تغییر پارامتر مسئله یعنی وزن رئوس(w_v) باشد. همچنین فرض کنید  و ، دو رأسی هستند با این هدف که در یک مسئلۀ پشتیبان تبدیل به 2- میانه شوند. هدف مسئلۀ معکوس از نوع محدودیت بودجه‎ای این است که با بودجۀ ، دو رأس دلخواه  و  را تا حد ممکن به بهینه‌شدن نزدیک کند. اگر فاصلۀ بین رأسv  و رأس  با  و فاصلۀ آن با رأس  با  نمایش داده شوند و p_v و q_v به‌ترتیب میزان افزایش و کاهش وزن رأسv یعنی w_v باشند و هزینۀ متحمل‌شده از افزایش و کاهش وزن رأسv به‌ترتیب با  و نمایش داده شود، در این صورت مدل کلی مسئلۀ BR2MP با تغییر در وزن رئوس به‎صورت زیر است.

تابع هدف (35) همان تابع هدف (3) برای مسئلۀ 2- میانه پشتیبان است که قرار است با تغییر در وزن رئوس یعنی تغییر به ، تا حد امکان بهینه شود. از طرف دیگر نیز تغییر وزن رئوس گراف تنها به‌اندازۀ بودجۀ مجاز است؛ بنابراین رابطۀ زیر برقرار است.

در این رابطه،C برداری مثبت است. بدون اینکه کلیت مسئله تغییر کند، فرض می‌شود است؛ بنابراین محدودیت (37) به‎صورت زیر بازنویسی می‌شود و می‌توان به‎جای ، با کار کرد.

از‌آنجایی‌که  و  مقادیری مشخص هستند، مقادیر  و  نیز برای هر ثابت هستند. به‌وضوح مشخص است که تابع هدف (35) و محدودیت‎های (36) تا (38) خطی هستند؛ بنابراین مدل این مسئله به‌صورت مسئلۀ برنامه‎ریزی خطی است.

مسئلۀ 2- میانه پشتیبان معکوس نوع محدودیت بودجه‎ای(BR2MP) با تغییر در طول یال گراف: فرض کنید ، بودجۀ مدنظر برای تغییر پارامتر مسئله یعنی وزن رئوس(w_v) باشد، همچنین فرض کنید  و ، دو رأسی هستند که قرار است در مسئلۀ پشتیبان به 2- میانه تبدیل شوند. فاصلۀ بین رأس  و رأس  با  و فاصلۀ آن با رأس  با  نمایش داده می‌شود. در‌این‌‌صورت مدل کلی مسئلۀ BR2MP با تغییر در طول به‎صورت زیر است.

در روابط بالا x_e میزان تغییرات طول یالی است و u_e نیز حداکثر تغییرات طول یالی را بیان می‎کند. همچنین l_e بیانگر طول یال،  را نمایش می‎دهد.  نیز تابع هزینۀ ناشی از تغییرات طول یال است که به‌صورت زیر در نظر گرفته می‌شود.

معکوس مسئلۀ 2- میانه پشتیبان^[xxvii] در فضای پیوسته با تغییر در مختصات نقاط

در این قسمت معکوس نوع محدودیت بودجه‎ای مسئلۀ 2-میانه پشتیبان^[xxviii] (BR2MP) به‌روش تغییر در مختصات نقاط بررسی می‌شود

 هدف این است که با تغییر در مختصات نقاط ، دو نقطۀ دلخواه (از پیش تعیین شده) و  با استفاده از بودجۀ محدود، تا‌ حد امکان به‌حالت بهینه نزدیک شوند. فرض کنید تغییر هر واحد مختصات نقاط ، هزینۀ  را دارد؛ به‎‌نحوی‌که  هزینۀ متحمل‌شده از تغییر مختص - ام نقطۀ ، است. به‎طور مشابه بردارهای  و  به‎ترتیب میزان افزایش و کاهش مختصات نقاط  را نشان می‌دهند.

اکنون مسئلۀ BR2MP همراه با تغییر در مختصات نقاط به‎صورت زیر مدل‎سازی می‌شود.

که ، تابع هزینۀ ناشی از تغییر مختصات نقاط است و به‎صورت زیر تعریف می‌شود.

مدل برنامه‎ریزی بالا با تابع هدف (46) و محدودیت‎های (47) تا (49)، مسئلۀ بهینه‎سازی غیر‌خطی و به‌دلیل وجود عبارت  در تابع هدف، نامحدب است.

مسئلۀ 2- میانه پشتیبان معکوس نوع محدودیت بودجه‎ای در صفحه با نُرم .:  برای نقاط  رابطۀ زیر تعریف می‌شود .

به‎نحوی‌که:

و

اگر ، میزان تغییرات مختصات نقاط  باشد، دراین‌صورت با‌توجه‌به مجموعه‎های  و، مدل مسئلۀ  در صفحه به‎صورت زیر بازنویسی می‎شود.

حال دو لم زیر برای مدل فوق بیان می‌شود.

لم 2 : تابع هدف مسئلۀ ، محدب است. اثبات: قرار داده می‌شود:

فرض کنید  و باشد. در این صورت رابطۀ زیر برقرار است.

تابع محدب است؛ بنابراین با‌توجه‌به مثبت‌بودن ضرائب w_i و p و با‌توجه‌به اینکه جمع تعداد شمارا تابع محدب، محدب است، نتیجه می‌شود که عبارت  محدب است. به‎طور مشاب ثابت می‌شود که قسمت‎های دیگرتابع هدف نیز محدب هستند؛ بنابراین با‌توجه‌به اینکه جمع چند تابع محدب، محدب است‎، نتیجه می‌شود تابع هدف مسئلۀ  نیز محدب است.

لم 3 : مشتقات تابع هدف مسئلۀ  در بعضی از نقاط، تعریف نشده است.

اثبات: مشتقات تابع هدف در نقاطی که مخرج آنها صفر می‎‌شود، تعریف‌نشده هستند.

با‌توجه‌به لم 3، برای آنکه نقاط ناپیوستگی مشتقات جزئی تابع هدف مسئلۀ  از بین برود، مقدار که عددی کوچک و مثبت است به رابطۀ (54) اضافه می‌شود تا مشتقات جزئی آن همواره پیوسته باشد؛ بنابراین تقریبی از تابع هدف مسئلۀ  به‎صورت زیر به دست می‎آید.

وقتی ، مقدار تابع هدف مسئلۀ  (BR2MPH) با مقدار تابع هدف مسئلۀ  (BR2MP) برابر می‎شود. این موضوع در لم 4 مشاهده می‌شود.

لم 4: با رفتن ، خطای حاصل از اضافه‌کردن مقدار  به تابع هدف مسئلۀ  برابر صفر است.

اثبات: قرار داده می‌شود، اگر و  باشد، رابطۀ زیر برقرار است.

همچنین با استفاده از نامساوی مینکوفسکی، رابطۀ زیر برقرار می‌شود.

بنابراین:

به‌طور مشابه این اثبات برای قسمت‎های دیگرتابع هدف (57) نیز بیان‌ می‌شود؛ بنابراین رابطۀ زیر برقرار است.

در رابطۀ (61) وقتی ، خطا صفر می‎شود.

 در‌حالت خاصی که بودجۀ مدنظر به‌اندازه‌ای بزرگ باشد تا بتوان به اندازۀ دلخواه نقاط را به سرویس‌دهنده‎ها نزدیک کرد (یعنی، )، می‎توان با استفاده از شرط لازم بهینگی و لم 2 برای بهینه‌شدن مسئلۀ ، الگوریتمی بازگشتی ارائه کرد؛ بنابراین رابطۀ زیر برقرار است.

و به‎طور مشابه:

از مساوی با صفر قرار‌دادن روابط (55) و (56) نتیجۀ زیر حاصل می‌شود.

و

که:

و

بنابراین وقتی بودجۀ مدنظر به‌اندازۀ کافی بزرگ باشد، از روابط بازگشتی (64) و (65) استفاده می‌شود. در اینجا وقتی بودجۀ مدنظر محدود باشد مسئلۀ  با الگوریتم‎های فرا ابتکاری حل و نتایج با هم مقایسه می‌شوند.

الگوریتم‎های فرا ابتکاری: الگوریتم­های بهینه­سازی، مقادیر متغیرهای طراحی را به‎گونه‎ای تغییر می­دهند تا تابع هدف مدنظر حداقل یا حداکثر شود. به‎طورکلی روش­های بهینه­سازی  به دو گروه روش­های گرادیانی و روش‎های جستجو تقسیم می‌شود. روش­های جستجو برای مسائل حجیم و در مواردی که مشتق‌گرفتن از تابع هدف دشوار است کارایی زیادی دارند. هرچند نمی­توان به‌صراحت دربارۀ برتری روش‎های تکاملی فوق نسبت به یکدیگر نظر داد و این امر طبق نظریۀ NFLT^[xxix] (هو و همکاران^[xxx]، 2002)، از مسئله­ای به مسئله دیگر متفاوت است، روش­های الگوریتم ژنتیک^[xxxi](GA) و PSO، تواناتر و پرکاربردتر از بقیه بوده­اند. در این پژوهش که مسئله­ای NP- سخت (مگیدو و همگاران^[xxxii]، 1984) و به‌شدت غیرخطی همراه با قیود فراوان است، از روش PSO و IPSO استفاده می­شود.

الگوریتم‎های فرا ابتکاری PSO و IPSO: PSO ازجمله­ روش­های تکاملی و مدرن است که در سال 1995 کندی^[xxxiii] و ابرهارت^[xxxiv] با الهام از رفتار دسته‌جمعی موجوداتی مثل حشرات، زنبورها، مورچگان و پرندگان معرفی کرده‌اند. هر عضو این گروه براساس اطلاعات و آگاهی خود و اطلاعات کلی گروه حرکت می­کند. این روش براساس گروه‎هایی از اعضا در نظر گرفته می‌شود که به‌دنبال بهترین مقدار برای تابع هدف، حرکت می­کنند.

هرکدام از این اعضا دارای دو مشخصۀ موقعیت و سرعت هستند که دائماً تغییر می‌کنند و اصلاح می‎شود. هر عضو در فضای طراحی مسئله، گردش می­کنند و به‌دنبال نقطۀ بهینه است. از سوی دیگر هر عضو بهترین موقعیت خود را نیز در نظر گرفته و در حافظۀ خود حفظ می‎‌کند. تبادل اطلاعات میان این اعضا براساس بهترین نقاط برای هر عضو و بهترین نقطۀ تمام اعضا، باعث می‌شود موقعیت و سرعت هر عضو به‌طور مداوم طبق روابط زیر اصلاح ‎شود (رائو^[xxxv]، 2009).

 موقعیت فعلی ذره،  سرعت حرکت ذره،  بهترین موقعیتی که ذره تاکنون تجربه کرده است،  بهترین مکانی است که تاکنون ذرات مجاور یافته‌اند.

 ضریب یادگیری مربوط به تجارب شخصی هر ذره است که در این مقاله  در نظر گرفته شده است. درمقابل  ضریب یادگیری برای کل جامعه و دراینجا  است. از طرف دیگر  و ، باعث می‎شوند که نوع گوناگونی در جواب‎ها به‌وجود بیاید و جستجوی کامل‎تری روی فضا انجام گیرد (رائو، 2009).  و  در این مقاله در هر تکرار به‌صورت عدد تصادفی از توزیع نرمال در بازۀ (0,1) تولید و در هر تکرار به‌روز‌رسانی می‎شوند؛ بنابراین همان‎طور‌که مشاهده می‎شود موقعیت و سرعت هر ذره در هر مولفه برای ، به‎طور جداگانه به‌روز‌رسانی خواهد شد.

 ضریب وزنی است که به‎صورت خطی از  تا  تغییر می­کند. مقدار زیاد ضریب وزنی، جستجوی کلی و مقدار کم آن جستجوی محلی را برای تعیین نقطۀ بهینه انجام می­دهد؛ بنابراین در مراحل تکرار روش، برای یافتن نقطۀ بهینه،‌ این ضریب به‎صورت خطی و طبق رابطۀ زیر کاهش می‎یابد تا در آخرین مرحله به کمترین مقدار خود می­رسد (رائو، 2009).

در این مقاله ، حداکثر مراحل تعیین‌شده برای تکرار مسئله و و به‎ترتیب برابر با 2/0 و 9/0، در نظر گرفته شده‎اند. اگر همۀ اعضا به یک نقطه نزدیک شوند یا فاصلۀ اعضا از یکدیگر تا مقدار تعیین­شده­ای کاهش یابد، حل مسئله همگرا می‌شود و نقطۀ بهینه به‎ دست می­آید.

در روش IPSO ضریب وزنی  به‎صورت زیر است (داس و همکاران^[xxxvi]، 2016).

در این رابطه  فاصلۀ اقلیدسی عضو - ام از بهترین نقطه  و  نیز بیشترین فاصله تا  در بین همه اعضا است (داس و همکاران، 2016). این مقادیر با‌توجه‌به مشخص‌بودن نقاط و بهترین جواب در هر تکرار محاسبه می‌شود.

نتیجه‌گیری و پیشنهادات

مکان‌یابی تسهیلات و تأسیسات از کاربردی‌ترین زمینه‌های پژوهشی است که در بسیاری از شاخه‌های علوم گسترده شده است. امروزه مدل‎هایی از مکان‌یابی تأسیسات و تسهیلات بررسی شده است که با شاخصه‎های دنیای واقعی تطابق بیشتری دارند. به مکان‌یابی معکوس و پشتیبان به‌دلیل تطابق بیشتر با واقعیت توجه می‌شود. در این مقاله برای نخستین‌بار، معکوس (نوع محدودیت بودجه‎ای و نوع حداقل هزینه) مسئلۀ 2- میانه پشتیبان درحالت گسسته برای گراف‎های عمومی مدل‌سازی ریاضی شده است و سپس در‌حالتی‌که گراف مدنظر درخت باشد، به مسئلۀ برنامه‎ریزی خطی تبدیل می‌شود. همچنین درحالت پیوسته نیز برای مسئلۀ معکوس نوع محدودیت بودجه‎ای 2- میانه پشتیبان (با تغییر در مختصات نقاط) مدل‎ ریاضی ارائه می‌شود. همچنین با‌توجه‌به NP-سخت‌بودن و نامحدب‌بودن مسئله در‌حالت خاصی که بودجه به‌اندازۀ کافی بزرگ باشد با انجام تخصیص، به یک مسئلۀ محدب تبدیل می‌شود و برای آن الگوریتمی تکراری ارائه می‌شود. همچنین در‌حالت کلی و زمانی که بودجه محدود باشد، مسئلۀ مذکور در‌حالت پیوسته با الگوریتم‎های فرا ابتکاری ازدحام ذرات^[xxxvii](PSO) و الگوریتم بهبودیافته ازدحام ذرات^[xxxviii](IPSP) حل می‌شود و تغییرات پارامترهای مختلف مسئله همچون ضریب شکست، بودجه و نرم، تحلیل می‌شود.

در ادامه مسائل معکوس محدودیت بودجه‎ای در فضای پیوسته به‌وسیلۀ تغییر در وزن رئوس، مسائل معکوس حداقل هزینه در فضای پیوسته به‌وسیلۀ تغییر در وزن رئوس و تغییر در مختصات نقاط برای مطالعه و بررسی کارهای آتی پیشنهاد می‌شود.

پیوست آ:

در این قسمت مثال‎هایی عددی برای مسئلۀ معکوس 2- میانه پشتیبان درحالت پیوسته با روش تغییر در مختصات نقاط آورده شده است و اثرات مختلف تغییر در پارامترهای مختلف مسئله همچون تغییر در نرم p، مقدار بودجه B و ضریب شکست  pبررسی شده است. نرم‌افزار استفاده‌شده در این مقاله، نرم افزار Matlab ورژن R2017b است که در لپ‌تاپ مدل Fujitsu با مشخصات زیر مدل‌سازی شده است.

Intel(R)  Core™ i5-2430M CPU, 4.00GB RAM

مثال 1

در این مثال مسئلۀ BR2MP با تغییر در مختصات نقاط در محیط پیوسته، برای 20 مشتری با بودجۀ  و  در نرم اقلیدسی با روش‎های فرا ابتکاری PSO و IPSO حل شده است. نمودار (1) نحوۀ جابجایی نقاط اولیه (مشتریان) را نشان می‎دهد. نمودار (2) و (3) نیز عملکرد الگوریتم‌های فرا ابتکاری PSO و IPSO استفاده‌شده برای  و  در این مقاله را نشان می‌دهد.

نمودار 1- نقاط اولیه (مربع قرمز)، نقاط بهینه (ستاره مشکی) و نقاط 2- میانه (نقاط بعلاوه آبی) برای و .

نمودار 2- نمودار مقایسه‎ای عملکرد روش‎های PSO ,

IPSO برای حالت  و .

نمودار 3- نمودار مقایسه‎ای عملکرد روش‎های PSO ,

IPSO برای حالت  و .

همان‌طورکه در نمودار (2) و (3) مشاهده می‎کنید و در متن مقاله نیز اشاره شد، عملکرد IPSO نسبت به PSO بهتر است.

مثال 2- اثرات ضریب شکستp ، بر مسئلۀ    BR2MP درحالت پیوسته به‌روش تغییر در مختصات

به‎طور‌کلی با‌توجه‌به تعریف یک مسئلۀ 2- میانه پشتیبان، وقتی یکی از میانه‎ها (سرویس‌دهنده‎ها)، شکست بخورد، مشتریان این سرویس‌دهنده مجبورند از سرویس‌دهندۀ دیگر سرویس بگیرند؛ بنابراین این امر باعث افزایش مقدار تابع هدف خواهد شد. زمانی که p باشد تابع هدف مسئلۀ مذکور همان تابع هدف مسئلۀ 2- میانه معمولی است ( در رابطۀ (3)، p را معادل صفر در نظر بگیرید)؛ ولی زمانی‌که  باشد دو جملۀ  و  به تابع هدف مسئله اضافه می‎شوند و با افزایشp این دو مقدار نیز افزایش می‎یابند؛ بنابراین با افزایش ضریب شکست ، مقدار تابع هدف مسئله BR2MP نیز افزایش می‎یابد؛ برای مثال، این امر در جداول (1) و (2) مشاهده می‌شود.

در این مثال دو شبیه‎سازی عددی با تعداد نقاط  و  آورده شده است. جدول (1) مقدار تابع هدف با نرم اقلیدسی را به‎ازاءِ  و بودجۀ  نسبت به مقادیر مختلف p نشان می‎دهد. جدول (2) نیز مقدار تابع هدف با نرم اقلیدسی را به‎ازاءِ  و بودجۀ  نسبت به مقادیر مختلف p نشان می‎دهد. 

جدول 1- تأثیرات  p بر مقدار تابع هدف مسئلۀ BR2MP برای حالت   ، و .

جدول 2- تأثیراتp بر مقدار تابع هدف مسئلۀ BR2MP برای حالت و .

مثال 3- اثرات تغییر نرم ، بر مسئلۀ BR2MP درحالت پیوسته به‌روش تغییر در مختصات

به‎طورکلی مقدار (نرم ) با افزایش مقدار p، کاهش پیدا می‎کند؛ بنابراین در بودجۀ ثابت ، که باشد، برای حالت نسبت به حالت p، نقاط اولیه نزدیک‌تر به نقاط  هستند؛ بنابراین بودجۀ ثابت ، برای حالت  نسبت به حالت p، تابع هدف را بیشتر کاهش می‎دهد؛ بنابراین با افزایش مقدار p تابع هدف کاهش پیدا می‎کند. این امر در جدول (3) نیز مشاهده می‌شود. در جدول (3) مثال عددی با تعداد نقاط  و و بودجۀ  نسبت به مقادیر مختلفp آورده شده است.

جدول 3- تأثیراتp ، بر مقدار تابع هدف مسئلۀ BR2MP برای حالت ،  و .

مثال 4- اثرات تغییر بودجۀ B روی مسئلۀ BR2MP درحالت پیوسته به‌روش تغییر در مختصات

افزایش بودجه به این معنی است که می‎توان تغییرات بیشتری را در جابجایی مختصات نقاط اعمال کرد و این امر بیانگر این موضوع است که با افزایش بودجه، تابع هدف بهبود بخشیده می‎شود. به‌عبارت‌دیگر ازلحاظ ریاضی با افزایش بودجه، فضای جوابی که محدودیت مسئله یعنی رابطۀ (55) ایجاد می‎کند، افزایش می‌یابد و این امر باعث بهبود مقدار تابع هدف خواهد شد. جدول (4) اثرات تغییر بودجه را بر مسئلۀ شبیه‎سازی‌شده برای حالت  و  نشان می‎دهد.

جدول4- تاثیرات ، بر مقدار تابع هدف مسئله BR2MP برای حالت و .