مساله مکان‌یابی مرکز- میانه مسیر استوار با وزن‌های راسی بازه‌ای روی شبکه های درختی

هدف: در این مقاله، مساله مکان یابی مرکز-میانه مسیر استوار روی شبکه های درختی با وزن های راسی بازه ای یکسان برای هر دو مساله میانه مسیر و مرکز مسیر مورد بررسی قرار می گیرد. تابع هدف استفاده شده در این مقاله، جمع ساده تابع هدف مساله میانه مسیر و مرکز مسیر است. در کارهایی که در ادبیات تحقیقی صورت گرفته است، وزن ریوس برای هر دو مساله مکان یابی میانه مسیر و مرکز مسیر مجزا در نظر گرفته شده است. روش شناسی پژوهش: رویکرد استفاده شده برای محاسبه جواب استوار، رویکرد مینیماکس پشیمانی است. در این رویکرد، بیشترین مقدارپشیمانی برای هر مسیر انتخاب شده روی شبکه ی درختی، به ازای تمامی رخدادهای ممکن برای وزن های راسی گراف های درختی مینیمممی شود. یافته ها: با استفاده از رویکرد مینیماکس پشیمانی، یک الگوریتم ترکیبیاتی با زمان اجرای o(n^5) برای محاسبه جواب استوار مساله مرکز-میانه مسیر استوار روی شبکه های درختی ارائه می شود. اصالت/ارزش افزوده علمی: در این مقاله، با استفاده از سناریوهای بدترین حالت مسایل مرکز مسیر و میانه مسیر، سناریوهای بدترین حالت مساله مرکز-میانه مسیر استوار پیدا شده و با استفاده از آن، یک جواب استوار برای مساله مورد نظر محاسبه می شود.

the robust path centdian problem with interval vertex weights on tree networks

purpose: in this paper, the robust path centdian problem is investigated on tree networks with the same interval vertex weights for the both path center and path median problems. the used objective function in this paper is the simple sum of path median and path center problems. in the past research works, the vertex weights for the both path median and path center location problems are disjoint. methodology:the used approach to compute the robust solution is the minmax regret criterion. in this method, for any selected path on the tree, the maximum value of regret is minimized for all possible events of vertex weights. findings: using the minmax regret criterion, an algorithm with o (n^5) time complexity is presented to obtain a robust solution of the robust path centdian problem on tree networks. originality/value: in this paper, using the worst case scenarios for the path median and path center we obtain the worst case scenarios of robust centdian problem. then we obtain a robust solution for this problem.