مسئله جهت یابی

در عصر حاضر، صنعت گردشگری به عنوان یکی از مؤلفه های توسعه اقتصادی از اهمیت بالایی در بسیاری از کشورها برخوردار است. از طرف دیگر، با رشد فناوری اطلاعات و ارتباطات (فاوا)، با رویکرد گردشگری الکترونیک و گردشگری هوشمند، راه اندازی وب سایت ها و تولید نرم افزارهای موبایلی که به گردشگران در برنامه ریزی سفر (بر مبنای سلایق و ترجیحات شخصی یا گروهی آن ها، مشخصات جاذبه های گردشگری و وضعیت ترافیک شبکه معابر در یک مقصد گردشگری) کمک می کند، برای توسعه گردشگری و تقویت توان رقابتی مقاصد گردشگری، موردتوجه قرارگرفته است. از دیدگاه پژوهش عملیاتی، چالشِ برنامه ریزی سفر شخصی گردشگر، یک مسئله بهینه سازی به نام مسئله جهت یابی است که با مدل سازی و حل آن، برنامه سفر بهینه برای یک مقصد گردشگری شامل توالی بازدید برخی از نقاط جاذبه گردشگری طوری طراحی می شود که ضمن رعایت محدودیت های گوناگون، امتیاز کسب شده بیشینه گردد. این تحقیق با دیدگاهِ پژوهش عملیاتی ازنظر روش، توصیفی – تحلیلی و ازنظر هدف، توسعه ای است. در این مقاله یک روش فرا ابتکاری جستجوی محلی تکرارشونده، برای حل مسئله جهت یابی با وابستگی زمانی و پنجره های زمانی پیشنهادشده است. این الگوریتم حل بر مبنای تعدادی ساختار همسایگی خاص طراحی شده برای بهبود موضعی جواب عمل می کند که در مرحله جستجوی محلی آن از حرکت های درج، جابجایی و تعویض استفاده شده است. در این پژوهش، برای در نظرگیری شرایط تراکم و تأخیر ترافیک بر روی زمان سفر شبکه معابر، زمان سفر کمان های شبکه به صورت متغیر گسسته و تابعی از ساعت روز در نظر گرفته شده است. الگوریتم پیشنهادی در زبان برنامه نویسی C++ پیاده سازی شده و جهت ارزیابی کارایی آن، بر روی یک پایگاه داده واقعی از شهر شیراز (که از طریق مطالعات میدانی و کتابخانه ای جمع آوری شده است)، اجراشده است. بر اساس ارزیابی نتایج مطالعه موردی، کیفیت بالای جواب و زمان حل مناسب، از نقاط قوت روش پیشنهادی این تحقیق محسوب می گردد.

مسئله جهت یابی گونه ای از مسائل کلاسیک حوزه حمل و نقل قلمداد می شود که هدف آن، یافتن بهترین مسیر جهت بازدید مجموعه ای از رئوس مفروض می باشد، مشروط بر آن که طول مسیر از یک افق زمانی مشخص بیشتر نشود. از زمان پیدایش این مسئله، پژوهشگران متعددی با بهره گیری از ساختار خاص آن، اقدام به مدل سازی و حل مسائل متنوعی در حوزه های مختلف از جمله موضوعات و مشکلات حوزه حمل و نقل شهری کرده اند. به دلیل ماهیت NP-Hard مسئله، در این مقاله الگوریتم ژنتیک با درجه تصادفی بسیار بالا برای حل گونه ای جدید از این مسئله با عنوان مسئله جهت یابی با افق زمانی وابسته ارائه شده است. الگوریتم ژنتیک پیشنهادی از دو عملگر ترکیب و تلفیق و دو عملگر جهش استفاده کرده است که در این مقاله جهت نشان دادن همگرایی آن، بهترین جواب های موجود در ادبیات برای ۴۰ مثال استاندارد مسئله جهت یابی، ملاک عمل قرار گرفته است؛ بدین صورت که جواب های حاصل از حل این مثال ها با استفاده از الگوریتم پیشنهادی با آن ها مقایسه شده است و به دلیل عملکرد مطلوب الگوریتم، الگوریتم مذکور برای حل مسئله جهت یابی با افق زمانی وابسته به کار گرفته شده است.