کاربرد روش جریمه پویا در تخصیص ترافیک با محدودیت ظرفیت گره

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