فهرست نشریات علمی دسترسی آزاد ایران

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