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

نویسندگان

1 دانشگاه صنعتی سهند

2 گروه ریاضی کاربردی، دانشگاه صنعتی سهند تبریز، تبریز، ایران.

10.22105/dmor.2022.287402.1406

چکیده

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

کلیدواژه‌ها

موضوعات

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

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

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

  • Soudabeh Seyyedi Ghomi 1
  • Fahimeh Baroughi 2

1 Sahand University of Technology

2 Department of Applied Mathematics, Faculty of Science, Sahand University, Tabriz, Iran.

چکیده [English]

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. 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. 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. 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.

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

  • optimization
  • Path location
  • Centdian problem
  • Minmax regret criterion