مسئله مکان‌یابی مرکز-میانه رأسی استوار با وزن‌های رأسی بازه‌ای روی گراف‌های کلی

نویسندگان
نارنین اسکندری ارجمند
فهیمه باروقی
سودابه سیدی قمی
بهروز علی زاده
دانشگاه صنعتی سهند
چکیده
در این مقاله، مسئله ی مکان یابی مرکز -میانه ی استوار رأسی با وزن های رأسی غیر قطعی روی گرا فهای کلی مورد مطالعه و بررسی قرار

می گیرد. معیار مورد استفاده برای حل مسئله در این مقاله معیار مینی-ماکس پشیمانی است. این مسئله با تابع هدفی که دارای ضریبی از $lambada$

بوده مورد بررسی قرار گرفته و یک الگوریتم با زمان اجرای چند جمله ای برای آن ارائه می شود. نشان داده می شود که مسئله ی مرکز -میانه

استوار رأسی روی گراف های کلی در زمان مکعبی حل می شود.
کلیدواژه‌ها
مسئله‌ی مکان‌یابی مرکز- میانه
معیار مینی- ماکس پشیمانی
بهینه‌سازی استوار

عنوان مقاله English

The robust vertex centdian location problem with interval vertex weights on general graphs

نویسندگان English

Nazanin Eskandari Arjomand
Fahimeh Baroughi
Soudabeh Seyyedi Gomi
Behrooz Alizadeh
Sahand University of Technology
چکیده English

In this paper, the robust vertex centdian location problem with uncertain vertex weights on general graphs is studied. The used criterion to solve the problem is the min-max regret criterion. This problem is investigated with objective function contains $lambda$ and a polynomial time algorithm for the problem is presented. It is shown that the vertex centdian problem on general graphs is solved in cubic time.

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

Centdian location problem
Min-max regret criterion
Robust optimization
1. Averbakh I., Berman O., Minimax regret p-center location on a network with demand uncertainty, Locat. Sci., 5 (1997) 247–254.



2. Averbakh I., Berman O., Algorithms for the robust 1-center problem on a tree, Eur. J. Oper. Res., 123 (2000) 292–302.



3 Averbakh I., Berman O., An improved algorithm for the minmax regret median problem on a tree, Networks, 41 (2003) 97–103.



4. Halpern J., The location of a center-median convex combination on an undirected tree, J. Reg. Sci., 16 (1976) 237–245.



5. Kouvelis P.,.Yu G., Robust Discrete Optimization and Its Applications, Kluwer Academic Publisher, Boston, 1997.