«دیمکتب» دنیایی دیجیتالی برای یادگیری

مروري بر مسئله طراحي مسير گردشگر (بخش اول): آشنایی با مسئله

مروري بر مسئله طراحي مسير گردشگر (بخش اول): آشنایی با مسئله

اگر تا کنون با واژه هایی نظیر «طراحی مسیر گردشگر (Tourist Trip Design Problem)»، «فروشنده دوره گرد انتخابی (Selective Traveling Salesman Problem)» یا «مسئله جهت یابی (Orienteering Problem)» روبرو شده اید اما منبعی مناسبی به زبان فارسی برای آن نیافته اید، در این مقاله با ما همراه باشید تا با این واژگان کلیدی و ابعاد مهم آن ها آشنا شوید.

در ادبيات مسائل مبتني بر شبکه، تحقيقات بسيار زيادي به بررسي و حل مسئله طراحي مسير گردشگر که تلفيقي از دو مسئله کلاسيک و معروف «فروشنده دوره گرد» و «کوله پشتي» است، پرداخته اند. در اين مسئله هدف حداکثر کردن امتيازات (علاقمندي گردشگر) حاصل از بازديد رئوس مفروض (مقاصد گردشگري یا Point of Interest)، مشروط بر عدم عدول از محدوديت زماني در دسترس (طول مدت سفر گردشگر) مي باشد. هر چند اين مسئله که عنوان «مسئله جهت يابي» براي آن متواتر است؛ مورد توجه بسياري از پژوهشگران و نشريات تراز اول بين المللي قرار گرفته است؛ اما ندرتاً پژوهش هاي داخلي در اين حوزه را مي توان شناسايي نمود. از این رو و با توجه به گستره کاربردي اين مسئله و همچنین نزديک تر بودن آن به ويژگي هاي دنياي واقعي در مقايسه با ساير مسائل کلاسيک موجود، اين مقاله که بخش اول از سلسله مباحث مرتبط با مسئله طراحی مسیر گردشگر می باشد، به معرفي مسئله طراحي مسير گردشگر پرداخته است. در بخش دوم این مقاله که بزودی منتشر خواهد شد، به مرور تلاش هاي تحقيقاتي مرتبط و معرفی زمينه هاي توسعه آتي مسئله طراحی مسیر گردشگر اختصاص دارد.

1- مقدمه

اهميت ويژه مدل سازي و حل مسائل مبتني بر شبکه، پايه و علت اصلي شکل گيري موضوع اين مقاله مي باشد. اين اهميت ريشه در نقش و تاثير خاص و نيز چشم گير اين مسائل در بهبود فضاهاي کسب و کار در بخش خصوصي و عمومي دارد. بسياري از مسائل بنيادين در حوزه هاي مختلفي از جمله گردشگري، توليد، توزيع، دفاعي، امداد و نجات، مديريت شهري و حمل و نقل داراي قابليت انطباق با مفاهيم شبکه بوده و از اين رهگذر مي توان از ابزارهاي متنوع مدل سازي و حل مسائل مبتني بر شبکه جهت مواجهه با مسائل حوزه هاي مختلف به نحو مقتضي بهره جست. از اين رو در اين مقاله «مسئله طراحي مسير گردشگر (TTDP)» که حالتی خاص و کاربردي از مسائل شبکه مي باشد، مد نظر قرار گرفته است. اين مسئله که از تلفيق مسئله فروشند دوره گرد و مسئله کوله پشتي بوجود آمده است، سعي در ارائه يک ترتيب بهينه بازديد از «نقاط مورد علاقه (POI) » گردشگران با توجه به «محدوديت هاي ايشان (عمدتاً منابع مالي و زمان)»، «ويژگي هاي هر مقصد گردشگري (نظیر زمان های قابل بازدید و شرایط آب و هوایی)» و «ميزان علاقمندي گردشگر به بازديد هر مقصد» دارد [1]. بنابراين در انطباق با مفاهيم حوزه شبکه مي توان گفت در اين مسئله تعدادي رأس با امتياز مشخص موجود بوده و هدف يافتن يک مسير در يک افق زماني محدود با گذر از برخي رئوس و حداکثر کردن مجموع امتيازات جمع آوري شده مي باشد که با اين تعريف اين مسئله در زمره «مسئله جهت يابي (OP)» قرار مي گيرد [2,3]. بنابراین «مسئله طراحی مسیر گردشگر» زیرمجموعه ای کاربردی از «مسئله جهت یابی» قلمداد می شود. بدين صورت که يک گردشگر مقاصد مختلفي را جهت بازديد (مجموعه کليه رئوس) در فهرست خود داشته و در بازه زماني سفر خود (افق زماني) تمايل به کسب بيشترين بهره (مجموع امتيازات جمع آوري شده) را دارد.

شایان ذکر است با توجه به تواتر بسیار بالای استفاده از واژه «جهت یابی» در ادبیات مرتبط، در مقاله حاضر از هر دو واژه «مسئله طراحي مسير گردشگر» و «مسئله جهت يابي» برای مسئله مورد مطالعه استفاده شده است.

علیرغم پیشینه ادبیاتی گسترده و طولانی این مسئله و مسائل مشابه آن در فضای بین المللی و همچنین اهمیت مقوله گردشگری در توسعه کشور که توسط بسیاری از مسئولان و سیاستگذاران مورد تاکید قرار گرفته است، فعالیت های پژوهشی محدودی در داخل به این مقوله معطوف شده اند. از این رو در «دیمکتب» سلسله ای مباحث را در این زمینه آغاز نموده ایم که بنا داریم در آن به معرفی و تشریح این مسئله، مرور مقالات کلیدی مرتبط پرداخته و متعاقباً زمینه های تحقیقاتی موجود را مشخص نموده و زیرساخت های مورد نیاز جهت بسط و توسعه این حوزه جذاب تحقیقاتی در بین پژوهشگران داخلی را فراهم نماییم. لذا در مقاله حاضر که بخش اول این سلسله مباحث می باشد، تعريف دقيق تر مسئله طراحي مسير گردشگر ارائه شده و در سپس اهميت مسئله از دو منظر «هزينه هاي حمل و نقل سفر» و «محدوديت هاي زماني» مورد بحث قرار گرفته است. تاریخچه و پژوهش های اولیه، معرفی مقالات مروری و پر استناد مرتبط و مرور برترین مقالات اين حوزه و نیز جمع بندي و نتيجه گيري و معرفی زمينه هاي تحقيقاتي پيشنهادي آتی براي مسئله مباحث آتی مرتبط با این مقاله می باشد که به زودی توسط «دیمکتب» منتشر خواهد شد.

2- جایگاه «مسئله طراحي مسير گردشگر (TTDP)» در بین مسائل شبکه

مسئله طراحي مسير گردشگر (TTDP)، یک حالت خاص کاربردی از مسئله جهت يابي در حوزه گردشگری می باشد و بسیاری از پژوهشگران معتقدند مناسب است برنامه ریزی سفر گردشگران در قالب مسئله جهت یابی مدل سازی شود [1, 4-7]. مسئله جهت یابی نیز حالتی از «مسئله فروشنده دوره گرد (TSP)» است که در آن محدودیت افق زمانی (یا طول کل مسیر یا بودجه کل) وجود دارد. با افزایش تعداد سفرکننده به بیش از یک مورد «مسئله فروشنده دوره گرد (TSP)» به «مسئله مسیریابی وسیله نقلیه (VRP)» و «مسئله جهت یابی» به «مسئله جهت یابی تیمی (TOP)» تبدیل می شود. شرط اصلی در بوجود آمدن VRP و TOP امکان حرکت هر سفرکننده در یک مسیر خاص می باشد؛ فلذا در صورتی که در مسئله طراحی مسیر گردشگر، تنها یک مسیر برای تمامی گردشگران وجود داشته باشد، عملاً شرط حالت تیمی بوجود نیامده است.

مطابق با تعاريف کلاسيک موجود دو معيار «امتياز جمع آوري شده» و «کل هزينه/زمان سفر» به عنوان معيارهاي اصلي در بهينه سازي مسائل جهت یابی (و به تبع آن مسئله طراحی مسیر گردشگر) وجود دارد که يا به صورت تابع هدف و يا به صورت محدوديت در مدل ها ظاهر مي شوند. بر اين اساس سه مسئله به شرح ذيل وجود خواهد داشت [8]:

  • مسئله تور سودآور (Profitable Tour Problem)
  • مسئله جهت يابي (Orienteering Problem)
  • مسئله فروشنده دوره گرد امتيازآور (Prize Collecting Traveling Salesman Problem)

در ادامه هر یک از این سه نوع مسئله معرفی خواهند شد.

  • مسئله تور سودآور: در اين مسئله هر دو معيار فوق الذکر در قالب يک تابع هدف به کار گرفته شده و تابع هدف به صورت جمع کل هزينه منهاي جمع کل درآمد حاصل شده دسته بندي مي شوند. نامگذاري اين مسئله توسط دلاميکو و همکارانش در سال 1995 [9] انجام شده است که البته اين دسته از مسائل در ادبيات تواتر بالايي ندارند.
  • مسئله جهت يابي: در اين دسته از مسائل معيار «کل هزينه/زمان سفر» به عنوان محدوديت مد نظر قرار گرفته و هدف يافتن بهترين تور/مسيري است که امتياز حاصل از بازديد رئوس را حداکثر نمايد. شايان ذکر است در اکثر پژوهش هاي انجام شده در اين زمينه نقطه مبدأ و مقصد با يکديگر متفاوت مي باشد. در هر صورت اين موضوع نکته چندان مهمي نبوده و با اضافه کردن يک کمان فرضي بين نقطه پايان و نقطه شروع پس از حل مسئله مرتفع مي گردد.
  • مسئله فروشنده دوره گرد امتيازآور : در اين دسته از مسائل، معيار «کل امتياز جمع آوري شده» به عنوان محدوديت مد نظر قرار گرفته و هدف يافتن بهترين تور/مسيري است که کل هزينه/زمان سفر حاصل از بازديد رئوس را حداقل نمايد. اين نامگذاري توسط بالاس در سال 1989 [10] صورت گرفته است.

با عنایت به تعاریف فوق الذکر، «مسئله طراحي مسير گردشگر (TTDP)» در شاخه «مسئله جهت یابی» قرار گرفته و هدف آن یافتن مسیری است که با رعایت محدوديت «کل هزينه/زمان سفر در اختیار گردشگر»، مجموع رضایت مندی گردشگر از بازدید مقاصد مختلف گردشگری را حداکثر نماید.

3- اهميت مسئله طراحي مسير گردشگر (TTDP)

3-1- اهميت مسئله از منظر هزينه هاي حمل و نقل سفر

هزينه هاي حمل و نقل بخش عمده اي از هزينه هاي سفر گردشگران را تشکيل مي دهد. براي مثال فرر-روزل و همکارانش در سال 2015 در تحقيقي به نقل از موسسه IET اسپانيا، هزينه هاي حمل و نقل گردشگران در اين کشور در سال 2010 بيش از 32% اعلام کرده اند که اين عدد براي گردشگران فرهنگي بيش از 40% بوده است [13]. در مقاله ديگري که توسط پاولين در سال 2015 منتشر شده است، در سال 2013 حدود 39% از هزينه هاي سفرگردشگران بومي در ايالات متحده به هزينه هاي حمل و نقل اختصاص داشته است؛ حال آنکه اين مقدار براي گردشگران خارجي حدود 54% برآورد شده است [14]. با احتساب تعداد گردشگران ايالات متحده در سال 2013 (200 ميليون گردشگر بومي و 12.5 ميليون گردشگر خارجي) و متوسط هزينه هاي سفر (583 دلار براي هر سفر گردشگران بومي و 3,273 دلار براي هر سفر گردشگران خارجي) [14]، تنها در ايالات متحده در سال 2013، بيش از 67.5 ميليارد دلار جهت حمل و نقل توسط گردشگران پرداخت شده است. مطابق با آمارهاي ارائه شده توسط معاونت گردشگري سازمان ميراث فرهنگي، صنايع دستي و گردشگري و مرکز آمار ايران، در سال 1395نزديک به 5 ميليون نفر گردشگر خارجي و فقط در بهار 1395بيش از 75 ميليون سفر داخلي انجام شده است (نتايج آمارگيري از گردشگران ملي، 1395، مرکز آمار ایران). با وجود عدم در دسترس بودن اطلاعات مربوط به هزينه کرد گردشگران در بخش حمل و نقل در داخل کشور، به جرات مي توان گفت هزينه هاي حمل و نقل سهم قابل توجهي از هزينه هاي سفر در ايران را شامل مي شود. فلذا با طراحي مسير مناسب براي گردشگران (داخلي و خارجي)، مي تواند ضمن استفاده بهتر از مدت زمان در دسترس توسط گردشگران، صرفه جويي قابل ملاحظه اي در اين زمينه انجام داد.

3-2- اهميت مسئله از منظر محدوديت هاي زماني

طبيعت ذاتي فعاليت هاي انساني محدوديت آن به زمان است. بديهي است پرداختن به مسائل دنياي واقعي و مدل سازي آن ها بدون در نظر گرفتن چنين پارامتر مهمي از قابليت کاربرد (Applicability) کافي برخوردار نمي باشد. اين نياز و ضرورت بديهي، سبب پيدايش نوع خاصي از مسائل مسيريابي شد که «محدود بودن افق زماني» و «امتيازدار بودن بازديدها» ويژگي هاي بارز آن ها مي باشد. لازم به ذکر است ويژگي «امتيازدار بودن بازديدها» در تعامل با «محدود بودن افق زماني» معنادار است؛ بدين صورت که در حالت محدود نبودن افق زماني تفاوتي در ترتيب بازديدها از اين منظر نخواهد بود و تنها هزينه ها و مسافت ها اهميت خواهد داشت. اين دو ويژگي سبب مي شود که در هنگام طراحي مسير و يا دور در مسائل خانواده مسيريابي از تمرکز صرف بر هزينه ها و مسافت ها فاصله گرفته و واقعيت زمان را در تصميمات مد نظر قرار دهيم. طبيعتاً اين گونه مسائل نسبت به حالت هاي بدون زمان واقعي تر هستند [15]. پس از جستجوهاي متعدد در ادبيات مشخص شد زمان به صور مختلف از جمله افق زماني (Time Horizon) ، زمان سفر (Travel Time) ، پنجره زماني (Time Window) ، مدت زمان خدمت (Service Time) در مسائل وارد شده اند که مسائل طراحي مسير گردشگر (TTDP) بر روي حالت افق زماني متمرکز شده و از اين رو از جذابيت تحقيقاتي بالاتري نسبت به مسائل هم رده خود برخوردار است.

با بخش های آتی این مقاله که به زودی توسط «دیمکتب» منتشر خواهد شد با ما همراه باشید...

مطالب آموزشی

1- سلسله مقالات و مباحث پیرامون آموزش مقاله نویسی:

بهترین روش مقاله نویسی (بخش اول): «ساختار یک مقاله علمی» و «انواع مقاله علمی»

بهترین روش مقاله نویسی (بخش دوم): «ماهیت مقاله علمی-پژوهشی»، «انواع گزارشات علمی» و «تعریف پژوهش»

بهترین روش مقاله نویسی (بخش سوم): «ساختار تفصیلی یک مقاله علمی» و «نحوه ارجاع دهی منابع در متن»

بهترین روش مقاله نویسی (بخش چهارم): «سيستم هاي ارزيابي آثار علمي»

بهترین روش مقاله نویسی (بخش پنجم): «شاخص هاي ارزيابي آثار علمي»

بهترین روش مقاله نویسی (بخش ششم): «چند نکته اساسي در تهيه يک مقاله علمي» و «نرم افزارهاي پرکاربرد در نگارش مقاله علمي»

بهترین روش مقاله نویسی (بخش هفتم): «انواع مجامع علمی»

بهترین روش مقاله نویسی (بخش هشتم): «معرفي برخي از مهمترين بانک هاي اطلاعاتي»

2- آشنایی با ابزارهای پیشرفته تحقیق و پژوهش (Research Tools)

آشنایی با گوگل پژوهشگر(Scholar Google) و ترفندهای پیشرفته جستجو در آن

3- اعتبارسنجی مدل های تحقیق در عملیات

اعتبارسنجی مدل های تحقیق در عملیات (بخش اول): تاریخچه

اعتبارسنجی مدل های تحقیق در عملیات (بخش دوم): مقدمه ای بر تصدیق، اعتبارسنجی و تست

4- سلسله مقالات و مباحث پیرامون مسئله طراحی مسیر گردشگر

مروري بر مسئله طراحي مسير گردشگر (بخش اول): آشنایی با مسئله

5- سلسله مقالات و مباحث پیرامون مسئله مکان یابی رقابتی

مکانیابی تسهیلات رقابتی (Competitive Facility Location) (بخش اول): چیستی مسئله

منابع و مآخذ

  1. Gavalas, D., Konstantopoulos, C., Mastakas, K., and Pantziou, G., (2014). A survey on algorithmic approaches for solving tourist trip design problems, Journal of Heuristics, 20 (3), pp. 291-328.
  2. Vansteenwegen, P., Souffriau, W., and VanOudheusden, D., (2011). The orienteering problem: A survey, European Journal of Operational Research, 209 (1), pp. 1-10.
  3. Gunawan, A., Lau, H. C., and Vansteenwegen, P., (2016). Orienteering problem: A survey of recent variants, solution approaches and applications, European Journal of Operational Research, 255 (2), pp. 315-332.
  4. Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., and Vathis, N., (2015). Heuristics for the time dependent team orienteering problem: Application to tourist route planning, Computers & Operations Research, 62 pp. 36-50.
  5. Kwon, W. Y., Mingu, K., and Suh, I. H., "Probabilistic tourist trip-planning with time-dependent human and environmental factors," in 2016 International Conference on Big Data and Smart Computing (BigComp), 2016, pp. 505-508.
  6. Souffriau, W. and Vansteenwegen, P., "Tourist trip planning functionalities: State–of–the–art and future," in International Conference on Web Engineering, 2010, pp. 474-485: Springer.
  7. Shcherbina, O. and Shembeleva, E., (2014). Modeling recreational systems using optimization techniques and information technologies, Annals of Operations Research, 221 (1), pp. 309-329.
  8. Feillet, D., Dejax, P., and Gendreau, M., (2005). Traveling salesman problems with profits, Transportation science, 39 (2), pp. 188-205.
  9. Dell'Amico, M., Maffioli, F., and Värbrand, P., (1995). On prize‐collecting tours and the asymmetric travelling salesman problem, International Transactions in Operational Research, 2 (3), pp. 297-308.
  10. Balas, E., (1989). The prize collecting traveling salesman problem, Networks, 19 (6), pp. 621-636.
  11. Miller, C. E., Tucker, A. W., and Zemlin, R. A., (1960). Integer programming formulation of traveling salesman problems, Journal of the ACM (JACM), 7 (4), pp. 326-329.
  12. Verbeeck, C., "Optimizing practical orienteering problems with stochastic time-dependent travel times: towards congestion free routes," Ghent University, 2016.
  13. Ferrer-Rosell, B., Coenders, G., and Martínez-Garcia, E., (2015). Determinants in tourist expenditure composition—the role of airline types, Tourism Economics, 21 (1), pp. 9-32.
  14. Paulin, G. D., (2015). Travel expenditures, 2005-2013: domestic and international patterns in recession and recovery, Monthly Lab. Rev., 138 p. 1.
  15. Raff, S., (1983). Routing and scheduling of vehicles and crews: The state of the art, Computers & Operations Research, 10 (2), pp. 63-211.