مساله پوشش هاب تك تخصيصي بر روي شبكه ستاره‌اي؛ مدل‌بندي، خطي‌سازي و يافتن كران مناسب براي آن‌

The single allocation hub covering location problem on star network; modeling, linearization and finding a suitable bound for them

در اين مقاله دو مساله پوشش هاب تك تخصيصي با ساختار ستاره‌اي كه شامل دو مساله ماكزيمم پوشش p-هاب و پوشش هاب با در نظر گرفتن هزينه انتقال جريان است، مورد بررسي قرار مي­گيرد. ساختار ستاره‌اي شبكه به گونه‌اي ‌است كه يك هاب مركزي با مكان مشخص وجود دارد و ساير هاب‌ها به طور مستقيم به هاب مركزي متصل مي‌شوند. در مساله اول هدف انتخاب مكان p هاب و تخصيص هر مشتري به حداكثر يك هاب است به طوري كه كل تقاضاي انتقال يافته بين مشتريان ماكزيمم شود. هدف مساله دوم حداقل‌سازي مجموع هزينه ثابت احداث هاب‌ها و هزينه انتقال جريان بين گره‌هاي شبكه است به طوري كه پوشش كامل در شبكه ايجاد شود. در هر دو مساله اتصال مشتريان به مراكز هاب و هاب‌ها به هاب مركزي به گونه‌اي خواهد بود كه فاصله مبادي تا مقاصد با در نظر گرفتن فاكتور تخفيف براي اتصال بين هاب و هاب مركزي از مقدار از پيش تعيين شده كمتر يا مساوي است. در هر دو مساله پس از ارائه مدل رياضي، به خطي‌سازي آن‌ها و سپس استفاده از آزادسازي لاگرانژ به منظور يافتن كران‌هاي مناسبي پرداخته شده است. علاوه بر اين، در مساله دوم نامساوي‌هاي معتبري معادل دو محدوديت مساله ارائه شده است. در نهايت، نتايج حاصل از حل مدل‌هاي خطي، غيرخطي و بكارگيري آزادسازي لاگرانژ بررسي و مقايسه شده است. بررسي اين نتايج بر روي مجموعه داده‌هاي CAB بيانگر آن است كه مدل‌هاي خطي هم از لحاظ مقدار بهينه تابع هدف و هم زمان اجرا بسيار مطلوبتر از مدل‌هاي غيرخطي است. همچنين با توجه به نتايج، كران‌هاي بدست آمده از الگوريتم آزادسازي لاگرانژ فاصله كمي با جواب بهينه مسائل دارد.

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 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 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 relaxation are closer to the optimal solution of problems.