الگوریتم تخصیص ترافیک برپایه مسیر با استفاده از حل دستگاه های معادلات خطی

مسئله تخصیص ترافیک همان مساله تعیین جریان تعادلی دریک شبکه حمل ونقل است که درحالت عمومی به صورت یک مدل تکمیلی غیرخطی برحسب جریان درمسیرها بیان میشود الگوریتم های تخصیص ترافیک برپایه مسیر خانواده ای از روشهای حل مدل تکمیلی هستند که درآنها جریان درمسیرهای بین زوجهای مبدا مقصد بطور تکراری با حرکت به سمت جواب تعادلی بهنگام می شوند درهر تکرار این روشها با استفاده از دو ایده تجزیه مساله وتولید مسیر به جای حل مساله اصلی یکریز مساله بسیار کوچکتر برای هر زوج مبدا مقصد حل می شود متغیرهای این زیرمساله شامل جریان درمسیرهای فعال بین آن زوج مبدا مقصد است مجموعه مسیرهای فعال درهر تکرار با تولید کوتاهترین مسیر از مبدا به مقصد و افزودن آن به مسیرهای فعال تکرار قبلی بهنگام می شود زیرمساله مربوط به هر زوج مبدا مقصد خود یک مساله تکمیلی غیرخطی است که حل آن به خاطر ماهیت غیرخطی سخت است.

Keywords:

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