مسائل مکانیابی تک وسیله ای آرمانی تحت نرم Lp

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


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

Single facility goal location problems with Lp norm

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

  • Aria Soleimani 1
  • Jafar Fathali 2
  • Morteza Nazari 1
1 Faculty of Mathematical Science, Shahrood University of Technology,Shahrood, Iran.
2 Faculty of Mathematical Science, Shahrood University of Technology, Shahrood, Iran
چکیده [English]

Location theory is an interstice field of optimization and operations research. In the classic location problem, the goal is finding the location of one or more facilities such that some criteria such as transportation cost, the sum of distances passed by clients, total service time and cost of servicing are minimized. In this paper, we consider the goal location problem. In the goal location problem, the ideal is locating the facility in the distances ri, from the i-th client. However, in the most instances, the solution of this problem doesn’t exist. Therefore, we consider the minimizing of distances between clients and ideal point. The minimizing sum of square errors and minimizing absolute errors under Lp norm are considered as the objective function. We use the Weiszfeld like, Gauss-Newton and imperialist competitive algorithms for solving the problem. Then we compare the results which obtained by these methods for some test problems.

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

  • goal location
  • Weiszfeld like algorithm
  • Gauss-Newton
  • imperialist competitive

[1] Amiri, M., Taghavi Fard, M. T., Aghaei M., Development of Three-Objective Model for the Location–Allocation of Assistance Centers in a probabilistic Condition of availability to emergency Vehicles, , Modern Researches in Decision Making, 1 (2), 2016, 1-27.

[2] Nazari, M., Fathali, J., Reverse backup 2-median problem with variable coordinate of vertices, Journal of Operational Research and Its Applications, 15 (2), 2018, 63-88.

[3] Abbasi, F.,  Tabriz, A. A., Selection of  Bank Branches Location Based on Rough Set Theory – Multi Choice Goal Programming, Modern Researches in Decision Making, 2 (1), 2017, 119-148.

[4] Kuhn, H.W., On a pair of dual nonlinear programs, Nonlinear programming, J., Abadie(ed.), North-Holland Publishing Co.,  Amesterdam, 1967.

[5] Weber, A., 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., 1929.

[6] Honggzhong, J., Fernando, O., Maged, D., A Modeling framework for facility location of medical services for large-scale emergencies, IIE Transactions, 39: 1, 41-55.

[7]‎ Love‎, R‎. ‎F‎., ‎Morris, ‎J‎. ‎D‎., and Wesolowsky‎, G‎. ‎O., ‎Facilities locations‎: ‎Models and methods‎, ‎Publications in Operations Research Series‎, ‎vol‎. ‎7‎, ‎North-Holland‎, ‎Amsterdam‎, ‎1988.

[8] Brimberg, J., The Fermat-Weber location problem revisited, Mathematical Programming, 71, 1995, 71-76.

[9] Chen, R., Noniterative Solution of Some Fermat-Weber Location Problems, Advances in Operations Research, 2011, 10 pages.

[10] Trinh, M. H., Lee, B.H., and Ahn, H.S., The Fermat-Weber location problem in single integrator dynamics using only local bearing angles, Auto Matica, 59, 2015, 90-96.

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

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

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

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

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

[16] Vardi, Y., Zhang, CH., A modified Weiszfeld algorithm for the Fermat-Weber location problem, Math. Program., Ser. A 90, 2001, 559–566.

[17] Brimberg, J., Love, R.,  Mladenović, N., Extension of the Weiszfeld procedure to a single facility minisum location model with mixed lp norms, Math. Meth. Oper. Res., 70, 2009, 269-283     

[18] Iyigun, C., Ben-Israel, A., A generalized Weiszfeld method for the multifacility location problem, Oper. Res. Lett., 38, 2010, 207–214.

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

[20] Fathali, J., Zaferanieh, M. and Nezakati, A., A BSSS algorithm for the location problem with minimum square error, 2009, Advances in Operations Research.

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

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

[23] Nocedal, J., Wright, S. J., Numerical Optimization, Springer, New York, 1999.

[24] Bashiri, M., Garmeyi, Y., Solving Multi Criteria Gradual Covering Problem Using  Simulated Annealing and Artificial Neural Network, Management Research in Iran, 17 (4), 2014, 25-41.

[25] Notash, M., Zandieh, M., Dorri Nokorani, B., Using a Genetic Algorithm Approach for Designing Multi-objective Supply Chain Network, Management Research in Iran,  18 (4), 2015, 183-203 .

[26] Ho, Y. C., and Pepyne, D. L., Simple Explanation of the No Free Lunch Theorem of Optimization, Proceeding of the 40th IEEE, Conf. on Decision and Control, USA. 2001.

[27] Gargari, A., Lucas, E. C., Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialist competitive, IEEE Congress on Evolutionary computation, Singapore, 2007.