نسخه سریع تر الگوریتم فرانک-ولف مزدوج برای کاربردهای تخصیص ترافیک
Publish Year: 1398
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 350
This Paper With 12 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
TTC18_281
تاریخ نمایه سازی: 13 شهریور 1400
Abstract:
مسئله تخصیص ترافیک طبق اصل اول واردراپ و تحت فروضی خاص به صورت یک مسئله بهینه سازی محدب فرمول بندی می شود. برای حل این مسئله روش های بر پایه کمان، بر پایه مسیر و بر پایه مبدا ارایه شده اند، که در بین آنها روش های بر پایه کمان به دلیل حافظه مصرفی کمتر دارای کاربرد بیشتری هستند. روش فرانک-ولف (FW) ساده ترین و معروف ترین روش بر پایه کمان است. این روش در عین حال که حافظه بسیار کمی مصرف می کند، نرخ همگرایی ضعیفی دارد. روش فرانک-ولف مزدوج (CFW)، به عنوان تعمیمی از روش جهات مزدوج در بهینه سازی، به منظور بهبود همگرایی روش FW و در عین حال اجتناب محاسبات پیچیده معرفی شده است. در این مقاله نسخه ای سریع تر از این روش به نام CFW+ ارایه می شود. الگوریتم های CFW ،FW، و CFW+ توسط C++ کد نویسی شده و روی شبکه آزمایشی سوفالز و نیز شبکه بزرگ مقیاس شیکاگو آزمایش می شوند. نتایج اجرای این الگوریتم ها روی شبکه شیکاگو نشان می دهد که الگوریتم های CFW و CFW+ نسبت به الگوریتم FW به ترتیب در حدود ۷۴ و ۸۵ درصد زمان حل کمتری را برای رسیدن به شکاف نسبی ۵-^۱۰ صرف می کنند.
Keywords:
Authors
عباس بابازاده
استادیار دانشکده مهندسی عمران، دانشگاه تهران
وحید کریمی
دانشجوی کارشناسی ارشد مهندسی عمران، دانشگاه تهران