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

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

Keywords:

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