مسیریابی در گراف دو-وزنه شامل ریوس با اولویت متفاوت

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

کلیدواژه ها:

فروشنده دوره گرد ، گراف دو-وزنه ، الگوریتم ، مسیریابی اولویت دار ، محیط آسیب دیده ، TSP ، الگوریتم تقریبی