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

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، دانشکده ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران

2 دانشیار، دانشکده ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران

3 استادیار، گروه جامدات، دانشکده مهندسی مکانیک، دانشگاه صنعتی شاهرود، شاهرود، ایران

چکیده

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



[i] Backup 2-meian


[ii] Particle Swarm Optimization (PSO)


[iii] Improve Particle Swarm Optimization (IPSO)

کلیدواژه‌ها


عنوان مقاله [English]

Inverse of Backup 2-Median Problems with Variable Edge Lengths and Vertex Weight on Trees and Variable Coordinates on the Plane

نویسندگان [English]

  • Morteza Nazari 1
  • Jafar Fathali 2
  • Mostafa Nazari 3
  • Seyed mojtaba Varedi Koulaei 3
1 PhD student, Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
2 Associate Professor, Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
3 Assistant Professor, Dept. of Mech. Eng., Shahrood University of Technology, Shahrood, Iran
چکیده [English]

In this paper we consider the inverse of backup 2-median problem. In this problem, a set of weighted points are given and we should change some parameters of the problem such as weights of vertices and edges and coordinates of points such that the two given points be the backup 2-median. We present mathematical models for inverse backup 2-median problems on graphs. In the case that the underlying network is a tree, linear models are presented for the problem with variable edges and weight of vertices. We also consider the continuous case of the problem with variable coordinates of vertices on the plane. In this case, we solve the model by PSO and a hybrid improved PSO methods. Computational results are compared for the varying amounts of parameters.
  Introduction: The inverse and backup location facility problems are two important branches of location theory that have been interested by many researchers in the recent decades.  Let n weighted points be given in the plane or on a graph. The inverse median models investigate to change some parameters of problem such as coordinates, edge lengths and vertex weights such that the given facilities be the median points. For more information about inverse location problems see Burkard et al. (2004). On the other hand, in the backup median problems supposed that some facilities may failed. Therefore the other facilities should serve the clients. The backup 2-median problem on trees has been considered by Wang et al. (2009). Fathali (2014) investigated the backup multi-facility location problem on the plane.
In this paper we consider the combination of inverse location and backup facility location problems. We want to change coordinates, weight of vertices or length of edges with minimum cost such that the given facilities be backup median facilities.
 Materials and Methods:
2. inverse Backup 2-Median On Trees: Let T=(V,E)  be a tree with n vertices. Each vertex  has a nonnegative weight . Let  be the distance between two points  and ,  and  be the two given vertices in T which are assumed the location of facilities.  Each facility may fail with a probability . For any vertex , suppose that the cost of increasing and decreasing per unit of  is  and , respectively. Let  and  be the amounts by which the weight is increased and decreased, respectively. Then, the model of inverse backup 2-median problem can be written as follows.




 




 
Using some properties of backup 2-median problem on trees, this model can be converted to a linear programming model.
 
3. Inverse Backup 2-Median on The Plane: In this section we consider the inverse backup 2-median on the plane. Let n points  be given in the plane. Let we have a limited budget B, to change the parameters. Then we want to modify the coordinate of given points such that the two points  and be close to backup 2-median. With the same notation of inverse backup 2-median on trees, the model of inverse backup 2-median problem on the plane can be written as follow.




 




 
Results and Discussion: Two Particle Swarm Optimization (PSO) methods have been applied to solve the inverse backup 2-median problem on the plane.  Table 1, shows the results with varying norms , which obtained by running the two PSO methods on a problem with 80 points.
 
Table 1. The results of two PSO models for BR2MP with n=80, B=700 and
 




 
 
 
 
 



1


5.81E+03


5.64E+03


676.09


481.06




2


4.71E+03


4.65E+03


353.89


378.37




5


4.19E+03


3.75E+03


526.14


462.06




10


3.83E+03


3.39E+03


362.328


657.44





 
Conclusion: In this paper we investigated the backup 2-median problem with variable edge lengths and vertices weights on trees. The problem with variable coordinates on the plane is also considered. The models of mentioned problems and computational results which obtained by two PSO methods are presented.
 References
Burkard, R. E., Pleschiutsching, C., & Zhang, J. (2004). "Inverse median problems". Discrete Optimization, 1(1), 23-39.
Fathali, J. (2014). "Backup multifacility location problem with norm"OPSEARCH, 52(2), 382-391.
Wang, H. L., Wu, B. Y., & Chao, K. M. (2009). "The backup 2-center and backup 2-median problems on trees". Networks, 53(1), 39-49.

کلیدواژه‌ها [English]

  • Facility Location
  • ReverseOptimization
  • Backup -Median
  • Meta-Heuristic

مقدمه

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

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

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

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

(1)

 

d(vi, mj)، فاصلۀ بین نقاط vi و  است (فتحعلی[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- میانه پشتیبان هستند. جواب مسئله با زوج رأس  نشان داده می‎شود؛ به‎نحوی‌که ، مکان سرویس‌دهنده با احتمال شکست  و ، مکان سرویس‌دهنده با احتمال شکست هستند. در این مقاله فرض شده است احتمال شکست دو سرویس‌دهنده با هم برابر هستند؛ یعنی، .

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

(3)

 

 

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

(4)

 

 

طوری‌که،  و 

(5)

 

اگر  یال مرکزی m1 و m2 در درخت باشد، دراین‎صورت با حذف یال ، درخت T به دو زیردرخت Txو Tyتقسیم می‎شود؛ طوری‌که x  درTxوy در  Tyقرار دارد. 

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

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

 

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

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

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

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

(6)

 

 

 

 

 

(7)

 

(8)

(9)

 

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

(10)

 

 

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

(11)

 

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

(12)

 

 

(13)

 

(14)

 

 

(15)

 

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

(16)

 

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

(17)

 

به‎نحوی‌که:

(18)

 

(19)

 

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

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

(20)

 

 

 

 

(21)

 

(22)

 

(23)

 

(24)

 

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

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

(25)

 

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

(26)

 

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

(27)

 

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

(28)

 

به‌نحوی‌که:

(29)

 

 

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

(30)

 

 

 

 

 

 

 

(31)

 

 

 

 

 

 

 

(32)

 

(33)

 

(34)

 

 

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

(35)

 

 

 

(36)

 

(37)

 

(38)

 

 

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

(39)

 

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

(40)

 

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

 

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

(41)

 

(42)

 

(43)

(44)

 

 

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

(45)

 

 

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

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

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

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

 

(46)

 

 

(47)

(48)

(49)

 

 

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

(50)

 

 

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

 

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

(51)

 

به‎نحوی‌که:

(52)

 

و

(53)

 

 

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

(54)

 

 

 

 

 

 

 

 

 

 

 

(55)

(56)

 

 

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

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

 

 

 

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

 

 

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

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

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

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

(57)

 

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

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

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

(58)

 

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

(59)

 

بنابراین:

(60)

 

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

(61)

 

 

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

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

(62)

 

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

(63)

 

 

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

(64)

 

و

(65)

 

که:

(66)

 

و

(67)

 

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

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

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

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

(68)

 

(69)

(70)

 

 

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

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

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

(71)

 

 

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

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

(72)

 

 

در این رابطه  فاصلۀ اقلیدسی عضو - ام از بهترین نقطه  و  نیز بیشترین فاصله تا  در بین همه اعضا است (داس و همکاران، 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 برای حالت   ، و .

         

0

81/68

04/70

74/63

23/32

3/0

90/166

56/166

59/50

10/31

5/0

74/225

44/225

28/39

29/33

7/0

37/287

49/287

17/38

93/47

9/0

46/346

40/345

58/39

74/48

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

         

0

02/634

99/571

05/23

75/121

3/0

10/1E+03

07/1E+03

32/91

81/99

5/0

48/1E+03

39/1E+03

94/92

18/134

7/0

00/2E+03

68/1E+03

42/129

35/138

 

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

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

 

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

         

1

81/5E+03

64/5E+03

09/676

06/481

2

71/4E+03

65/4E+03

89/353

37/378

5

19/4E+03

75/3E+03

14/526

06/462

10

83/3E+03

39/3E+03

328/362

44/657

 

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

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

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

         

100

90/496

79/471

88/750

80/541

200

72/326

50/314

38/1207

36/682

500

48/269

43/255

91/889

52/769

 

 

 



[i] Fathali

[ii] Baroughi et al.

[iii] Inverse Problem

[iv] Reverce Problem

[v] Burkard et al.

[vi] Wang et al.

[vii] Weber

[viii] Hakimi

[ix] H‎andler

[x] Mirchandani

[xi] Butron

[xii] Toint 

[xiii] Berman et al.

[xiv] Burkard et al. 

[xv] Wang et al.

[xvi] Jianfang et al.

[xvii] Minimum cut

[xviii] Greedy

[xix] Nguyen

[xx] Galavii

[xxi] Burkard et al.

[xxii] Sepasian and Rahbarnia

[xxiii] Snyder

[xxiv] Daskin

[xxv] Cheng et al.

[xxvi] Backup Inverce -Median Problem (BI2MP)

[xxvii] Backup Reverce -Median Problem (BR2MP)

[xxviii] Backup Reverce -Median Problem (BR2MP)

[xxix] No Free Lunch Theorem (NFLT)

[xxx] Ho et al.

[xxxi] Genetic algorithm (GA(

[xxxii] Megiddo et al.

[xxxiii] Kenedy

[xxxiv] Eberhart

[xxxv] Rao

[xxxvi] Das et al.

[xxxvii] Particle Swarm Optimization (PSO)

[xxxviii] Improve Particle Swarm Optimization (IPSO)

 

 

Baroughi, B. F., Burkard. R. E., & Alizadeh, B. (2010). "Inverse median location problems with variable coordinates". Central European Journal of Operations Research, 18(3), 365- 381.

Baroughi, B. F., Burkard, R. E., & Gassner, E. (2011). "Inverse p- median location problems with variable edge lengths". Mathematical. Methods of Operations Research, 73(2), 263-280.

Berman, O. & Drezner, Z. (2000). "A note on the location of an obnoxious facility on a networks".  European Journal of Operational Research, 120(1), 215-217.

Burkard, R. E., Gassner, E., & Hatzl, J. (2006). "A linear time algorithm for the reverse 1-median problem on cycle|. Networks, 48(1), 16-23.

Burkard, R. E., Gassner, E., & Hatzl, J. (2008). "Reverse 2-median problems on trees". Discrete Applied Mathematics, 156(11), 1963-1976.

Burkard, R. E., Pleschiutsching, C., & Zhang, J. (2004). "Inverse median problems". Discrete Optimization, 1(1), 23-39.

Burton, D., & Toint, Ph. L. (1992). "On an instance of the inverse shortest path problem". Mathematical Programming, 53(1-3), 45-61.

Cheng, Y. K., Kang, L. Y., & Yan, H. (2014). "The backup 2-median problem on block graphs". Acta Mathematicae Applicatae Sinica, 30(2), 309–320.

Das, P. K., Behera, H. S., & Panigrahi B. K. (2016). "A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning". Swarm and Evolutionary Computation, 28, 14–28.

Fathali, J. (2006), “A genetic algorithm for the p-median problem with pos/neg weights”, Applied Mathematics and Computation, 183(2), 1071-1083.

Fathali, J. (2014). "Backup multifacility location        problem with norm".  OPSEARCH, 52(2), 382-391.

Galavii, M. (2008). Institute of Optimization and Discrete Mathemati". Ph.D Thesis, Graz University of Technology, Graz, Austria.

Hakimi‎, ‎S. L.‎ ‎(1964)‎ ‎"Optimum location of switching centers and the absolute centers and medians of a graph". ‎Operations Research, ‎12(3), 450-459‎.

Handler, G. Y., & Mirchandani, P. B. (1979). Location on    Networks: Theory and Algorithms. MIT Press, Cambridge.

Ho, Y. C., & Pepyne, D. L. (2002). "Simple explanation of the  no free lunch theorem of optimization". Cybernetics and Systems Analysis, 38(2), 292–298.

Jianfang, Y., & Juan, J. (2012). "Reverse 1-median problem with constraint in trees". Proceedings of the 2012 International Conference on Computer Application and System Modeling, Paris, France, 75-78.

Modaber, L., Alizadeh, B., Baroughi, B. F., (2016). "The Optimal Algorithms for Backup Undesirable 2-Center Location Models on Tree Graphs". Journal of Operational Research and Its Applications. 13 (2), 69-83.

Nguyen, K. T., (2016). "Reverse 1-center problem on weighted trees”. Optimization, 65(1), 253-264.

Megiddo N, & Supowitz K, (1984). On the complexity of some common geometric location problems, SIAM Journal on Computing, 13(1), 182-196.

Rao, S. S. (2009).  Engineering Optimization Theory and Practice (Fourth Edition). John Wiley and Sons, Inc.

Sepasian, A. R., & Rahbarnia, F. (2015). "An O(nlog n) alghorithm for the 1- median problem on the tree with variable vertex weight and edge reductions". Optimization, 64(3), 595-602.

Snyder, L. V., & Daskin, M. S. (2005). "Reliability  models for facility location: The expected failure cost case". Transportaion Science., 39(3), 400-416.

Wang, H. L., Wu, B. Y., & Chao, K. M. (2009). "The backup 2-center and backup 2-median problems on trees". Networks, 53(1), 39-49.

Wang, Q., & Bai, Y. (2010). "An efficient algorithm for reverse 2-median problem on a cycle". Journal of Networks, 5(10), 1169-1176.

 Weber, A. (1929). "Uber den Standort der Industrient,   Tubingen" (1909). English Trans.: Theory of Location of Industries, (C. J. Friedrich, ed. and trans.). Chicago, University Press, Chicago, Illinois.