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

مسیله تخصیص ترافیک در شبکه های حمل و نقلی تحت فروضی ساده کننده به صورت یک مسیله بهینه سازی محدب فرمول بندی می شود. برای حل این مسیله الگوریتم های بر پایه کمان، بر پایه مسیر و بر پایه مبدا ارایه شده اند. در بین این الگوریتم های بر پایه کمان به دلیل حافظه مصرفی کمتر کاربرد بیشتری یافته اند. الگوریتم بر پایه کمان فرانک-ولف به دلیل سادگی و نیز سرعت همگرایی زیاد آن در تکرار های اولیه هنوز جزو محبوب ترین الگوریتم های تخصیص ترافیک محسوب می شود. ولی، این الگوریتم در نزدیکی جواب بهینه دارای همگرایی ضعیفی است، و به همین علت تاکنون پژوهش های متعددی با هدف اصلاح جهت جست وجو فرانک-ولف انجام شده است. الگوریتم های جهات مزدوج موثرترین نوع این الگوریتم ها بوده و در ضمن پیاده سازی آنها بسیار ساده تر است. این الگوریتم ها شامل پارتان، فرانک-ولف مزدوج ، فرانک-ولف مزدوج می باشند. در این مقاله مقایسه هایی مستقیم از نظر زمان حل و تعداد تکرار تا رسیدن به دقت های مختلف جواب بین این چهار الگوریتم روی شبکه ی بزرگ مقیاس شیکاگو و شبکه کوچک مقیاس سوفالز انجام می شود. نتایج نشان می دهند که سه الگوریتم فرانک-ولف دومزدوج، فرانک-ولف مزدوج و پارتان، در مقایسه با الگوریتم فرانک-ولف، سرعت همگرایی به جوابی با خطای 5-10 (جواب پایدار) را برای شبکه شیکاگو به ترتیب در حدود 89، 72 و 63 درصد افزایش می دهند. در ضمن، فقط الگوریتم فرانک-ولف دومزدوج توانایی رسیدن به خطای 6-10 را دارد. مقایسه نتایج شبکه سوفالز با نتایج شبکه شیکاگو نشان می دهد که کارایی الگوریتم های جهات مزدوج با کاهش اندازه شبکه افزایش می یابد.