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

نوع مقاله : مقاله پژوهشی

نویسندگان

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

چکیده

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

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Comparison of Convergence Speed among Conjugate Directions Traffic Assignment Algorithms

نویسندگان [English]

  • Vahid Karimi
  • Abbas Babazadeh
School of Civil Engineering, University of Tehran , Tehran, Iran
چکیده [English]

The Traffic assignment problem in the transport networks is formulated as a convex optimization problem using simplifier assumptions. Link based, path based and bush based algorithms have been presented to solve this problem, among which the link based algorithm have found more applications thanks to their low memory requirements. The link based algorithm of Frank-Wolf (FW) is yet amongst the most popular assignment algorithms, because of its simplicity as well as high convergence speed during the initial iterations. However, the low convergence rate of this algorithm near the optimal solution has driven many studies that focus on modifying the FW search direction, resulted in newer link based algorithms. Among them are conjugate direction algorithms which are more effective and simply implementable. These algorithms include PARTAN, conjugate FW (CFW) and bi-conjugate FW (BFW). This paper uses the Chicago Regional and Sioux-Falls test networks to make direct comparisons among these algorithms with respect to the CPU time and iteration number needed to reach various accurate solutions. The results for Chicago show that, compared with the FW algorithm, the three algorithms CFW, PARTAN increase the convergence speed to the relative error of 10-5 (i.e. a stable solution) by about 89, 72 and 63%, respectively, while only the BFW can reach to a 10-6 relative error. Comparing the results from Sioux-Fall with those of Chicago demonstrate that the performance of the conjugate directions Algorithms improves as network size decreases.

کلیدواژه‌ها [English]

  • traffic assignment
  • .Link based algorithms
  • Frank-Wolf Algorithm
  • PARTAN Algorithm
  • Conjugate direction algorithms