مدلسازی ریاضی مسئله مکان یابی P‏ مرکز با در نظر گرفتن سلسله مراتب لانه ای وکاربرد الگوریتم بهینه سازی گروهی ذرات در حل آن

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

نویسندگان

دانشگاه شاهد

چکیده

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

کلیدواژه‌ها


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

the nested hierarchical p-center modeling & solving with PSO algorithm

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

  • Mahdi Bashiri
  • Mohammad reza yaghoubi
چکیده [English]

In this paper, a mathematical modeling of nested hierarchical p-center problem is presented. In this model there are two levels of hierarchies and the first one should be passed to achieve the second level . The second level facility can provide both services of the first and the second level. This model is a linear integer mathematical programming model. To provide an application of the model, some simulated cases are investigated and resolved, the results show that using this model reduces the initial construction cost while the main objective which is maximum servicing distance will not be changed basically.for the large size problem using of metaheuristic algorithms is necessary so in this paper an algorithm based on the Particle swarm intelligence is proposed to solve the problem. Numerical results confirm efficiency of the algorithm.

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

  • mathmatical modeling
  • p-center
  • nested hierarchical
  • Particle swarm optimization
 
 
 
 
 
[1] Hakimi SL. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 1964;12(3):450–459
[2] Daskin MS. Network and discrete location: models, algorithms, and applications. New York: Wiley; 1995
[3] Elloumi S, Labbé M, Pochet Y. A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing 2004;16(1):84–94.
[4] Mladenovic´, N., Brimberg, J., Hansen, P., & Moreno-Pérez, J. The p-median problem: A survey of metaheuristic approaches.European Journal of Operational Research, 2007,:179(3): 927–939.
[5] Hansen, P., Brimberg, J., Uroševic´, D., & Mladenovic ´, N. Solving large p-median clustering problems by primal-dual variable neighborhood search.Data Mining and Knowledge Discovery,2009: 19(3): 351–375.
[6] Scaparra, M. P., Pallottino, S., & Scutellà, M. G. , Large scale local search heuristics for the capacitated vertex p-center problem. Networks, 2004: 43(1): 241-255.
[7] Daskin, MS , A new approach to solving the vertexp-center problem to optimality: Algorithm and computational results. Communications of the Operations Research Society of Japan, 2000 :45(9) : 428–436.
[8] Albareda-Sambola, M., Díaz, J. A., & Fernández, E. , Lagrangean duals and exact solution to the capacitated p-center problem. European Journal of Operational Research,2010: 201(1): 71–88.
[9] Ilhan T, Pinar M. An efficient exact algorithm for the vertexp-center problem.2001 URL⟨http://www.ie.bilkent.edu.tr/mustafap/pubs/)
[10] Hatic Calic, Barbaros C. Tansel. “Double bound method for solving the p-center location problem”. Computers & Operations Research, 2014:40(1): 2991-2999.
[11] Yang K, Yankui L, Guoqing Y. Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion. Appl. Math. Modelling 2014 ; 17(3): 100-113
[12] Cheng Lu C. Robust weighted vertex p-center model considering uncertain data: An application to emergency management. European Journal of Operational Research 2013. 230(2): 113-121.
[13] Dagoberto R, Orozco O, Roger Z. Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent. Computers & Operations Research 2014. 16(7): 359-371
[14] Elshaikh A, Salhi S, Nagy G. The continuousp-centre problem: An investigation into variable neighbourhood search with memory. European Journal of Operational Research 2014. 17(30): 1-16
[15] Kaveh A, Nasr H. Solving the conditional and unconditional p-center problem with modified harmony search: A real case study. Scientia Iranica 2011; 18(4): 867-877
[16] Yang k, Liu Y, Qing  Yang G. Solving  fuzzy  p-hub  center  problem  by  genetic  algorithm  incorporating  local search. Applied  Soft  Computing 2013. 13(9) :  2624–2632
[17] Serra D, ReVelle C. The pq-median problem: location and districting of hierarchical facilities II. Heuristic solution methods. Location Science , 1994: 2(2):63–82
[18] Aardal K. Reformulation of capacitated facility location problems: how redundant information can help. Annals of Operations Research 1998;82(11) :289–308
[19] Weaver JR, Church RL. The nested hierarchical median facility location model. INFOR 1991 ;29(2) :100–115.
[20] Gao L-L, Robinson Jr EP. A dual-based optimization procedure for the two-echelon uncapacitated facility location problem. Naval Research Logistics 1992;39(4):191–212
[21] Sahin G. Solution approaches for the two-level p-median problem. MS thesis, METU, Ankara, Turkey; 2002.
[22] Kennedy, J., Eberhart, R.C , Particle Swarm Optimization, Proc. of IEEE In Int. Conf. on Neural Networks,1995 :15(4): 1942-1948,.