تعمیم الگوریتم فرانک ولف برای مسیله تخصیص ترافیک با محدودیت های ظرفیت کمان

کاربرد وسیع الگوریتم های تخصیص ترافیک در ارزیابی و انتخاب گزینه های مناسب برای بهبود عملکرد شبکه های حمل ونقل نیازمند واقعی تر شدن هر چه بیشتر نتایج حاصل از آنها می باشد. یکی از عوامل واقعی تر شدن این نتایج، صرفنظر از روش حل، در نظر گیری محدودیت های ظرفیت کمان ها است. الگوریتم هایی مانند فرانک-ولف (FW) کارایی زیادی در حل مسیله تخصیص ترافیک دارند، ولی عدم در نظرگیری ظرفیت کمان ها جزو نقاط ضعف آنها محسوب می شود. در هر تکرار الگوریتم FW، جهت حرکت توسط حل مسیله جریان با هزینه مینیمم در شبکه بدون در نظرگیری ظرفیت، یا همان تخصیص همه یا هیچ، بدست می آید. برخلاف این روش، (Out of Kilter ( OFK نوعی روش تخصیص برای حل مسیله جریان با هزینه مینیمم در شبکه با در نظر گیری ظرفیت کمان ها می با شد. در این مقاله، جهت حرکت در الگوریتم FW توسط روش OFK تعیین می شود؛ و در نتیجه جریان کمان ها در هر تکرار کوچکتر یا مساوی ظرفیت باقی می ماند. نتایج کاربرد روش پیشنهادی برای شبکه سوفالز با فرض یک مبدا به چند مقصد و نیز زمان سفرهای وابسته به جریان ارایه ، و نتایج آن با حالت بدون محدودیت ظرفیت مقایسه می شوند.

Keywords:

تخصیص ترافیک , محدودیت ظرفیت کمان , الگوریتم فرانکولف , الگوریتم Out of Kilter