حل مسئله مکانیابی پشتیبان چند وسیله‎ای با در نظر گرفتن شعاع آرمانی برای هر مشتری

محورهای موضوعی : آمار

جعفر فتحعلی ¹ , مرتضی نظری ²

1 - گروه ریاضی کاربردی، دانشکده علوم ریاضی ، دانشگاه صنعتی شاهرود، شاهرود، ایران
2 - گروه ریاضی کاربردی - دانشکده علوم ریاضی - دانشگاه صنعتی شاهرود- شاهرود- ایران

تاریخ دریافت : 1397/03/06 تاریخ پذیرش : 1397/12/11 تاریخ انتشار : 1398/10/01

کلید واژه: Continuose location, Weiszfeld method, Backup, Multifacility, Ideal radius,

چکیده مقاله :

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

چکیده انگلیسی:

In this paper we introduce a new facility location model, called backup multifacility location problem by considering the ideal radius for each customer. In this problem the location of clients are given in the plane. A radius is assigned to each client. We should find the location of new facilities, which some of them may fail with a given probability, such that the sum of weighted distances from new facilities to the radius distance of clients and sum of weighted distances between new facilities is minimized. Since in the most instance there dose not exist the location of a new facility such that its distance to each Customers be exactly equal to given radiuses, so we try to minimize the sum of the weighted square errors. We model the problem and propose an iterative method (weiszfeld like algorithm) for solving the presented problem. Then a discussion about convergence of presented method and some numerical examples are given. We show that the optimal solution lies in an extended rectangular hull of the existing points.

منابع و مأخذ:

 

]1[ نظری، م.، و فتحعلی ج.، مسئله معکوس نوع محدودیت بودجه‌ای 2-میانه پشتیبان با تغییر در مختصات نقاط، مجله تحقیق در عملیات و کاربردهای آن، ۱۵ (2)، 63-88 (1397)

 

[2] Weiszfeld, E., Sur le point par lequel la somme des distances de n points donns est minimum, Tohoku Math, 43, 355–386 (1937)

 

[3] Miehle, W., Link-length minimization in networks, Oper. Res., 6, 232–243 (1958)

 

[4] Eyster, J.W., White, J.A., Wierwille, W.W., On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Transacions, 5, 1–6 (1973)

 

[5] Morris, J.G., Convergence of the Weiszfeld algorithm for Weber problems using a generalized distance function, Oper. Res., 29, 37–48 (1981)

 

[6] Morris, J.G., Verdini, W.A., A simple iterative scheme for solving minisum facility location problems involving lp distances, Oper. Res., 27, 1180–1188 (1979)

 

[7] Iyigun, C., Ben-Israel, A., A generalized weiszfeld method for the multi-facility location problem, Oper. Res. Lett., 38, 207–214 (2010)

 

[8] Francis, R., McGinnis, L.F. Jr., White, J.A., Facility Layout and Location: An Analytical Approach, Prentice Hall (1992)

 

[9] Love, R.F., Morris, J.G., Wesolowsky, G.O., Facility Location: Models and Methods, North Holland. (1988)

 

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

 

[11] Snyder, L. V., and Daskin, M. S., Reliability  models for facility location: The expected failure cost case, Trans. Sci., 39, 400-416 (2005)

 

[12] Cheng, Y. K.,  Kang, L. Y., and Yan,  H., The backup 2-median problem on block graphs, Opt. Meth. and Soft., 164, 309-320 (2014)

 

[13] Fathali, J., Backup multifacility location problem with  norm, OPSEARCH, 52, 382-391 (2014)

 

]14[  مدبر، ل.، علیزاده، ب.، باروقی، ف.، الگوریتم‎های بهینه برای مدل‎های مکانیابی 2- مرکز ناخوشایند پشتیبان روی گراف‎های درختی، تحقیق در عملیات در کاربردهای آن، 13 (2)، 69-83 (1395)

 

[15] Fathali, J., Zaferanieh, M., and Nezakati, A., A BSSS algorithm for the location problem with minimum square error, Advances in Operations Research, Volume 2009, Article ID 212040, 10 pages (2009)

 

[16] Jamalian, A., and Fathali, J., Linear programming for the location problem with minimum absolute error, World Applied Sciences Journal, 7, 1423-1427 (2009)

 

[17] Fathali, J., Jamalian, A., Efficient methods for goal square Weber location problem, Iranian Journal of Numerical Analysis and Optimization,   7, 65-82 (2017)