الگوریتمی ابتکاری برای مساله ممانعت از حدکثر جریان شبکه در فضای اقلیدسی

در این مقاله مساله ممانعت از حداکثر جریان در شبکه در حالتی که گره های شبکه و ممانعت کننده ها به صورت نقاطی در فضای اقلیدسی قرار دارند، بیان شده و فرمول بندی می شود. سپس الگوریتمی دقیق که با استفاده از تکنیک گسسته سازی فضا برای حل این مساله نامحدب طراحی شده است مرور می گردد. در ادامه یک الگوریتم ابتکاری با استفاده از یک مرحله از الگوریتم دقیق گسسته و نقاط کاندید متفاوت طراحی شده و نتایج محاسباتی آن از نظر کیفیت جواب و زمان اجرای الگوریتم با الگوریتم دقیق مقایسه می شود.

کلیدواژه ها:

شبکه جریان ، ممانعت ، اقلیدسی ، گسسته سازی ، ابتکاری