مقاله الگوریتم رقابت استعماری برای مسأله مسیریابی گروهی با پنجره زمانی

فایل ممکن است بخاطر نمایش در سایت بهم ریختگی داشته باشد.

مقاله الگوریتم رقابت استعماری برای مسأله مسیریابی گروهی با پنجره زمانی

فرمت: ورد ( word )

حجم: ۲۶ کیلوبایت

چکيده

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

كليد واژه– الگوریتم رقابت استعماری، مسأله TOPTW، هیوریستیک، مسائل NP-hard، نقاط بازدید، امپراطوری.

• مقدمه

مفهوم گردشگری درقرن نوزدهم وامروزه صنعت گردشگری دردنیا به یکی از بهترین منابع درآمدوتبادلات فرهنگی بین کشورهاتبدیل شده است. گردشگر، کسی است که به منظوری غیر از کار و کسب درآمد برای مدتی بیش از یک شب وکمتراز یک سال به سرزمینی جزمحیط متعارف خود پای می گذارد ودر آن اقامت می گزیند و گردشگری شامل کلیه فعالیتهایی است که گردشگران درهنگام سفر انجام می دهندو به ایشان مرتبط می شود که می تواند شامل برنامه‌ریزی برای سفر، جابجایی میان مبدا و مقصد، و نظایر آن باشد[1]. برنامه ریزی یک مسافرت توریستی به یک شهرناشناس ممکن است وقت گیر باشد، ازاینرو، توجه به سمت سیستم هایی است که می توانند به کاربر نقاط دیدنی راپیشنهاد کنند. برای سادگی فرض می شود که مکان های دیدنی، مکان هایی هستند که اغلب از آنها عکس برداری شده است، با توجه به عکس های موجود می توان به سادگی لیستی از جالب ترین مکان ها رادریک شهربدست آورد. دریک مرحله، ممکن است لیستی ازدنباله ای ازمکان ها رابرای کاربر موردنظر، که در زمینه موردنظر مربوط هست رامشخص کرد[2].

درحالیکه جنبه شخصی سازی مسأله موردبررسی قرار گرفته است [3]، تأثیرفاکتورهای زمینه ای مانند زمان هنوزموردتوجه زیادی قرارنگرفته است. بااین وجود، واضح است که چنین فاکتورهای زمینه ای ممکن است جایی که گردشگران قراراست بروندراتحت تأثیرقراربدهند[2]. یک توریست ازمکانی به مدت یک یا چند روز دیدن می کند که آن مکان شامل جاذبه های توریستی زیادی است. بعلت محدودیت های زمانی یا بودجه ای ویا ساعاتی که نقاط دیدنی باز هستند، تعداد وقفه های مورد نظرومدت زمان آنها(مانند ناهار یا استراحت) و…، بازدید از تمام این جاذبه ها معمولا شدنی نیست. ازاینرو انتخاب مهمترین مکان های دیدنی برای بازدیدبه طوریکه با محدودیت های موجود سازگار باشد مورد نیاز است، لذا اینجاست که مسأله طراحی سفر توریستی مطرح می شود[4]، که  ازاهمیت ویژه ای برخورداربوده و می تواند به گردشگر درانتخاب مکان های بازدید با اولویت بالاتر وبا در نظرگرفتن محدودیت های موجودکمک نماید.

امامسأله طراحی سفر توریستی یک چالش الگوریتمی درمقایسه با تورهای توریستی است، چرا که نمی تواند در زمان چند جمله ای حل شود والگوریتم های اکتشافی[1] کارآمد نوعا برای کار با این مسأله در کاربرد های آنلاین پیاده سازی شده اند. یکی ازمسائلی که می تواند به عنوان مدل اصلی برای مسأله طراحی سفر توریستی در نظر گرفته شودمسأله مسیر یابی گروهی با پنجره زمانی یا Team Orienteering Problem With Time Windows(به اختصارTOPTW ) است، که جزء مسائل NP-hard می باشد[5,6].

 مسأله مسیریابی بدون پنجره زمانی در مقالات مختلفی مورد بررسی قرار گرفته است که از آن جمله می توان به مسأله فروشنده دوره گردانتخابی[7]، مسأله مجموع ماکزیمم[8] و مسأله دزدبانک[9] اشاره کرد. همچنین مسأله مسیریابی می تواند به صورت یک حالت خاص ازمسأله فروشنده دوره گردیا Travelling  Salesman  Problem  (به اختصار TSP) بامحدودیت منابع[10]، یک TSP باسود[11]، یا به صورت یک مسأله کوتاهترین مسیر ابتدایی با منابع محدود[12]، فرمول بندی شود. بسیاری از کاربردهای مسأله مسیریابی را می توان در مقالات زیر جستجو کرد: مسابقه ورزشی مسیریابی[13]، مسأله تحویل سوخت خانگی[14]، تکنیک های مسیریابی برای سرویس دهی به مشتریان[15] وغیره که در مقاله Vansteenwegen وهمکارانش [16] به همگی آن ها اشاره شده است. امادر مقالات  زیرکه به بررسی مسأله مسیریابی گروهی با پنجره زمانی می پردازد، رویکردهای پیشنهادی هریک برای حل این مسأله به اختصار بیان شده است: