مساله مسیریابی کمان در حالت ظرفیت دار با در نظر گرفتن تقاضای احتمالی

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

Keywords:

تقاضای احتمالی , مسیریابی کمان ظرفیت دار , الگوریتم بهبود یافته پریم , حذف زیرتور