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

مسئله تخصیص ترافیک طبق اصل اول واردراپ و تحت فروضی خاص به صورت یک مسئله بهینه سازی محدب فرمول بندی می شود. برای حل این مسئله روش های بر پایه کمان، بر پایه مسیر و بر پایه مبدا ارایه شده اند، که در بین آنها روش های بر پایه کمان به دلیل حافظه مصرفی کمتر دارای کاربرد بیشتری هستند. روش فرانک-ولف (FW) ساده ترین و معروف ترین روش بر پایه کمان است. این روش در عین حال که حافظه بسیار کمی مصرف می کند، نرخ همگرایی ضعیفی دارد. روش فرانک-ولف مزدوج (CFW)، به عنوان تعمیمی از روش جهات مزدوج در بهینه سازی، به منظور بهبود همگرایی روش FW و در عین حال اجتناب محاسبات پیچیده معرفی شده است. در این مقاله نسخه ای سریع تر از این روش به نام CFW+ ارایه می شود. الگوریتم های CFW ،FW، و CFW+ توسط C++ کد نویسی شده و روی شبکه آزمایشی سوفالز و نیز شبکه بزرگ مقیاس شیکاگو آزمایش می شوند. نتایج اجرای این الگوریتم ها روی شبکه شیکاگو نشان می دهد که الگوریتم های CFW و CFW+ نسبت به الگوریتم FW به ترتیب در حدود ۷۴ و ۸۵ درصد زمان حل کمتری را برای رسیدن به شکاف نسبی ۵-^۱۰ صرف می کنند.

کلیدواژه ها:

مسئله تخصیص ترافیک ، الگوریتم های بر پایه کمان ، الگوریتم فرانک-ولف مزدوج