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

چکیده مقاله

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

کلیدواژه‌ها

نویسندگان

عباس بابازاده

استادیار دانشکده مهندسی عمران، دانشگاه تهران

وحید کریمی

دانشجوی کارشناسی ارشد مهندسی عمران، دانشگاه تهران

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

ارائه‌شده در

مجموعه مقالات هجدهمین کنفرانس بین المللی مهندسی حمل و نقل و ترافیک6 اسفند 1398 · تهران