fa مساله پوشش هاب تک تخصیصی بر روی شبکه ستاره‌ای؛ مدل‌بندی، خطی‌سازی و یافتن کران مناسب برای آن‌ تخصصي Special پژوهشي Research <p dir="RTL" style="text-align: justify;"><span style="font-family:tahoma;">در این مقاله دو مساله پوشش هاب تک تخصیصی با ساختار ستاره‌ای که شامل دو مساله ماکزیمم پوشش <em><span dir="LTR">p</span></em>-هاب و پوشش هاب با در نظر گرفتن هزینه انتقال جریان است، مورد بررسی قرار می&shy;گیرد. ساختار ستاره‌ای شبکه به گونه‌ای ‌است که یک هاب مرکزی با مکان مشخص وجود دارد و سایر هاب‌ها به طور مستقیم به هاب مرکزی متصل می‌شوند. در مساله اول هدف انتخاب مکان <em><span dir="LTR">p</span></em> &nbsp;هاب و تخصیص هر مشتری به حداکثر یک هاب است به طوری که کل تقاضای انتقال یافته بین مشتریان ماکزیمم شود. هدف مساله دوم حداقل‌سازی مجموع هزینه ثابت احداث هاب‌ها و هزینه انتقال جریان بین گره‌های شبکه است به طوری که پوشش کامل در شبکه ایجاد شود. در هر دو مساله اتصال مشتریان به مراکز هاب و هاب‌ها به هاب مرکزی به گونه‌ای خواهد بود که فاصله مبادی تا مقاصد با در نظر گرفتن فاکتور تخفیف برای اتصال بین هاب و هاب مرکزی از مقدار از پیش تعیین شده کمتر یا مساوی است. در هر دو مساله پس از ارائه مدل ریاضی، به خطی‌سازی آن‌ها و سپس استفاده از آزادسازی لاگرانژ به منظور یافتن کران‌های مناسبی پرداخته شده است. علاوه بر این، در مساله دوم نامساوی‌های معتبری معادل دو محدودیت مساله ارائه شده است. در نهایت، نتایج حاصل از حل مدل‌های خطی، غیرخطی و بکارگیری آزادسازی لاگرانژ بررسی و مقایسه شده است. بررسی این نتایج بر روی مجموعه داده‌های <em><span dir="LTR"><span style="font-size: 11pt;">CAB</span></span></em> بیانگر آن است که مدل‌های خطی هم از لحاظ مقدار بهینه تابع هدف و هم زمان اجرا بسیار مطلوبتر از مدل‌های غیرخطی است. همچنین با توجه به نتایج، کران‌های بدست آمده از الگوریتم آزادسازی لاگرانژ فاصله کمی با جواب بهینه مسائل دارد. </span><br> &nbsp;</p> <p>The present study evaluates two problems of single allocation hub-covering problem with star structure including two problems of maximal p-hub covering and hub covering by considering the flow transfer costs. The star structure is as there is a central hub with definite location and other hubs are connected directly to the central hub. In the first problem, the goal is selection of p-hub locations and allocation of each customer to at most one hub as total transferred demand between customers is maximum. The purpose of the second problem is minimizing the sum of constant costs of construction of hubs and flow transfer costs between the network nodes as complete covering is created in the network. In two problems, connection of customers to hub centers and connection of hubs to the central hub is as the source to destination distance by considering discount factor to connect hub and central hub is lower or equal to the predefined value. After presenting the math model in two problems, linearization is performed, and then Lagrangian&nbsp;relaxation is applied to find suitable bounds. In addition, in the second problem, valid inequalities equal to two constraints of problem are presented. Finally, the results of solution of linear, non-linear models and using Lagrangian&nbsp;relaxation are evaluated and compared. The evaluation of these results on CAB data set shows that the linear models are better than non-linear models in terms of optimal value of objective function and implementation time. Based on the results, the bounds of Lagrangian&nbsp;relaxation are closer to the optimal solution of problems.&nbsp;</p> مسئله پوشش هاب, مساله ماکزیمم پوشش –pهاب, شبکه ستاره ای, خطی سازی, آزاد سازی لاگرانژ. Hub covering location problem, p-hub maximal covering location problem, Star network, Linearization, Lagrangean relaxation. 79 102 http://jamlu.lahijan.iau.ir/browse.php?a_code=A-11-1142-2&slc_lang=fa&sid=1 S.S. Sajadi سمیه سادات سجادی so.sa.sajadi@gmail.com 10031947532846005795 10031947532846005795 No Graduated master, University of Bojnord, Faculty of Basic Sciences, Department of Mathematics, Bojnord دانش آموخته کارشناسی ارشد، دانشگاه بجنورد، دانشکده علوم پایه ، گروه ریاضی، بجنورد F. Moeen Moghadas فروغ معین مقدس f.moeen@ub.ac.ir 10031947532846005796 10031947532846005796 Yes Assistant professor, University of Bojnord, Faculty of Basic Sciences, Department of Mathematics, Bojnord استادیار، دانشگاه بجنورد ، دانشکده علوم پایه ، گروه ریاضی ، بجنورد H. Karimi حسین کریمی h.karimi@ub.ac.ir 10031947532846005797 10031947532846005797 No Assistant Professor, University of Bojnord, Faculty of Engineering, Department of Industrial Engineering, Bojnord استادیار ، دانشگاه بجنورد ، دانشکده فنی و مهندسی ، گروه مهندسی صنایع، بجنورد