مقایسه الگوریتم های تخصیص ترافیک بر پایه کمان، بر پایه مسیر، و بر پایه مبدا از نظر تناسب جریان

مسیله ی تخصیص ترافیک در شبکه های شهری بر اساس اصل واردراپ به صورت یک مسیله ی بهینه سازی محدب فرمولبندی می شود. جواب این مسیله بر حسب جریان در کمان یگانه است ، در حالی که جریان در مسیرها می توانند معاوضه شوند، و بنابرین بیشمار جواب بر حسب جریان در مسیر وجود دارد. این نوع عدم یگانگی استفاده از جواب مسیله را در کاربردهایی که نیاز به جریان در مسیرها دارند غیرقابل تفسیر می سازد. یک فرض اضافی که منجر به یافتن جریان های یگانه در مسیرها می شود، شرط تناسب نام دارد. این شرط بیان می کند که نسبت توزیع جریان بین مقاطع موازی دارای هزینه های برابر، برای تمام زوجهای مبدا-مقصد با هم برابر است. در این مقاله معیاری جهت اندازه گیری میزان تناسب جریان ارایه شده، و بر اساس آن جواب های حاصل از الگوریتم بر پایه کمان فرانک - ولف (FW) ، الگوریتم های بر پایه مسیر فرانک- ولف مبدا-مقصدی (ODBFW) و گرادیان تقلیل یافته (RG)، و الگوریتم بر پایه مبدا لوچه (LUCE) برای شبکه سوفالز مورد ارزیابی قرار می گیرند. نتایج نشان می دهند که با افزایش دقت حل مسیله تا 10 تناسب جواب افزایش یافته، و پس از آن تقریبا ثابت می ماند. همچنین، تناسب جوابهای FW و LUCE به مراتب از تناسب جوابهای ODBFW و RG بیشتر است.

Keywords:

مسیله تخصیص ترافیک , جریان در مسیر , تناسب جریان