تخصیص ترافیک مبتنی بر مسیر با استفاده از روش حذفی گاوس-جردن

حل مسئله تخصیص ترافیک با روش های بر پایه ی مسیر همواره موضوعی جذاب برای محققان در این حوزه بوده است. از بین این روش ها، الگوریتم خطی سازی آشتیانی مسئله تخصیص ترافیک را در هر تکرار روی زوج های مبدا-مقصد تجزیه کرده و هر زیر مسئله را با استفاده از تقریب نیوتون به یک مسئله تکمیلی خطی تبدیل می کند. جهت کاهش هزینه محاسبات، تنها مسیرهای فعال بین هر زوج مبدا-مق صد در فرمول بندی هر زیرمسئله در نظرگرفته می شوند، و مجموعه مسیرهای فعال در هر تکرار توسط یک الگوریتم کوتاه ترین مسیر به روز می شوند. در نهایت، این الگوریتم هر زیرمسئله را با روش لمکه حل می کند. با توجه به اینکه اعمال روش لمکه برای زیر مسائل تکمیلی نسبتا پرهزینه است، در این مقاله از تکرار روش حذفی گاوس-جردن برای حل هر زیرمسئله استفاده می شود. در هر تکرار این روش، مسئله تکمیلی خطی فقط برای مسیرهای فعالی که جریان فعلی آنها مثبت است تشکیل شده، در حالی که جریان در هر مسیر دیگر برابر صفر قرار داده می شود. در این حالت، زیرمسئله تکمیلی معادل با یک دستگاه معادلات خطی می شود و توسط روش حذفی گاوس-جردن قابل حل است. الگوریتم پیشنهادی روی شبکه شیکاگو اعمال شده، و همگرایی بسیار خوب آن به شکاف نسبی ۶-^۱۰ نشان داده می شود.

Keywords:

تخصیص ترافیک , الگوریتم های بر پایه مسیر , روش حذفی گاوس-جردن