یک رویکرد دقیق و چند جمله ای برای مسئله مدلسازی عدد صحیح دو هدفه در مورد مسیریابی جریان شبکه

در این مقاله به معرفی یک مسئله مسیریابی جریان در شبکه با دو هدف می پردازیم. هدف اول ایجاد توازن بار شبکه می باشد و هدف دوم بحث طول مسیر جریان. این مسئله در چارچوب برنامه نویسی عدد صحیح مدلسازی شده و یک رویکرد صحیح ای مبتنی بر تکنیک و چندجمله ϵ -محدودیت برای حل آن ارائه شده است. در هر تکرار، الگوریتم پیشنهادی زیرمسئله برنامه نویسی عدد صحیح خطی تک هدفه را حل می کند. هدف الگوریتم پیشنهادی، دستیابی به مجموعه کامل مینیمال یا کمینه ای از راه حل های بهینه پارتو است. الگوریتم پیشنهاد شده از طریق چندین آزمایش محاسباتی مورد ارزیابی قرار گرفت، که شامل شبکه های تصادفی نیز می شدند. توپولوژی تصادفی توسط مدل بارباسی - آلبرت تولید و تنظیمات جریانات شبکه که در اینجا تعریف شدند، در شبکه های حسگر بی سیم و شبکه های مش بی سیم، بکار برده شده اند. تحلیل نتایج محاسباتی، اطلاعاتی ارزشمند در مورد عوامل اثرگذار بر راه حل ها، مثلا کوچکترین و بزرگترین تنگنا، اندازه افزایش کوتاهترین مسیر آخرین راه حل بهینه پارتو و اختلاف بین طول های مسیر اولین و آخرین راه حل های بهینه پارتو تولید شده، در اختیار تصمیم گیرنده قرار می دهد.

کلیدواژه ها:

زمان چندجمله ای ، مسئله مسیریابی جریان شبکه ، بهینه سازی دو هدفه ، تکنیک 𝝐 -محدودیت