مقايسه سرعت همگرايي بين الگوريتم‌هاي تخصيص ترافيك جهات مزدوج

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