مدل های مکان یابی مرکز کلاسیک و معکوس با در نظر گرفتن فاصله های مبتنی بر وزن های راسی روی گراف های بازهای

در این مقاله مسائل مکان یابی 1- مرکز کلاسیک و معکوس با در نظر گرفتن فاصله های مبتنی بر وزن راسی روی گراف های بازهای مورد مطالعه قرار می گیرند. ابتدا میتوان نشان داد که مدل 1-مرکز کلاسیک روی گراف های بازهای در زمان خطی قابل حل است. در مدل معکوس هدف تغییر وزن های راسی با صرف کمترین هزینه کلی است بطوریکه یک مکان از پیش تعیین شده مانند S* به مکان 1- مرکز گراف G تبدیل گردد. با به کارگیری یک رویکرد ترکیباتی، گراف بازهای G به یک درخت فراگیر دو شاخه تبدیل می شود و برای مدل 1- مرکز معکوس با فاصله های مبتنی بر وزن راسی یک الگوریتم دقیق با پیچیدگی زمانی خطی ارائه می گردد

Keywords:

مدل مکان یابی مرکز , بهینه سازی معکوس , بهینه سازی ترکیبیاتی , گراف های بازهای