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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 عضو هیات علمی دانشکده علوم گردشگری دانشگاه علم و فرهنگ.

2 دانشجوی کارشناسی ارشد مطالعات و برنامه ریزی اوقات فراغت-مدیریت دانشگاه علم و فرهنگ تهران

چکیده

صنعت گردشگری، همانند هر صنعت دیگری، به‌منظور توسعه باید از آخرین و مدرن‌ترین فنّاوری‌های اطلاعاتی و ارتباطی روز بهره‌مند باشد. رشد اقتصادی و زیرساختی جوامع در دنیای امروز موجب شده افراد زمان فراغت بیشتری برای مسافرت داشته باشند. اما، مسئله‌ای که در اینجا مطرح می‌شود هزینه‌های مسافرت است. به‌خصوص زمانی‌ که متصدیان خدمات تور، در بسته‌های تور خود، قصد برنامه‌ریزی برای تعیین مسیر گردشگران دارند. اگر مکان‌های موردبازدید گردشگر را به‌صورت نقاطی در نقشه مشخص و مسیر ارتباطی بین این نقاط رسم شود، می‌توان مجموعة نقاط و مسیرها را در یک گراف ترسیم کرد. بر این اساس، هر نقطه یا رأس گراف نشان‌دهندة نقطة هدف یا موردبازدید و هر یال نشان‌دهندة مسیر ارتباطی میان نقاط است. هر یال گراف می‌تواند دارای وزنی باشد که این وزن نشان‌دهندة هزینه، مدت زمان موردنیاز یا سایر شاخص‌های سفر خواهد بود. در اینجا مسئله، پیدا کردن کوتاه‌ترین، کم‌‌هزینه‌ترین یا سریع‌ترین مسیر میان یک رأس تا سایر رئوس گراف است. بدین منظور، در این پژوهش استفاده از الگوریتم دیکسترا، به‌عنوان راه حلی برای یافتن این مسیر، پیشنهاد می‌شود. روش این پژوهش توصیفی ـ تحلیلی است. درنهایت، مسئله با استفاده از این الگوریتم حل و بهینه‌ترین مسیر، از یک رأس تا سایر رئوس گراف، مشخص می‌شود. از این الگوریتم می‌توان در برنامه‌های نرم‌افزاری خدمات‌رسان در حوزة گردشگری برای مسیریابی و برنامه‌ریزی تورها استفاده کرد.
 
 
 
 

کلیدواژه‌ها


مرادویسی، هوشمند، مسگری، محمد سعدی، (1394)، «مسیریابی مکان‌های توریستی شهر، با استفاده از الگوریتم زنبور»، نشریة علمی ـ ترویجی مهندسی نقشه‌برداری و اطلاعات مکانی، دورة ششم، شمارة 3.
وحیدی، جواد (1387)، ساختمان‌های گسسته، انتشارات علوم رایانه.
موحد، علی و احمدی، عاطفه (1392)، «مسیریابی گردشگران در بافت‌های تاریخی با رویکرد حفاظت و احیای این بافت‌ها با استفاده از GIS (نمونة موردی: سنندج)»، محیط شناسی. سال سی‌ونهم، شمارة 1. صص 100-93.
Ahmadi, A., Shojaeean, A., Salari, T. and Izadi, P., (2011). Tourists Optimal Path-finding by GIS (Case Study: Historical Texture of Sanandaj). 5th Symposium on Advances in Science & Technology. Mashhad.
Han, Y., Guan, H., and Duan, J., (2014). Tour Route Multiobjective Optimization Design Based on the Tourist Satisfaction. Key laboratory of Traffic Engineering, Article ID 603494, 8 Pages. Beijing University of Technology, China.
Yang, Y., Dim, J., Wang, J and Li, F., (2012). Optimized Traveling Route Scheme based on Improved Prim Algorithm. International Journal of Digital Content Technology and its Applications (JDCTA). Volume6, Number 16.
Lourens, M. (2007). The Underpinnings for Successful Route Tourism Development in South Africa. University of the Witwatersrand, School of Geography, Archaeology and Environmental Studies in fulfilment of the requirements for the degree of Masters of Tourism. Johannesburg.
Zaheer, K. (2001). Artificial Intelligence Search Algorithms in Travel Planning. Department of Computer sciences and Electronics. Mälardalen University Västerås. Sweden.
Bang-Jensen, J. and Gutin, G. (2011). Digraphs: Theory Algorithms and Applications. Springer.
Haigh K. Z. and Veloso, M. (2005). Route Planning by Analogy. In Case-Based Reasoning Research and Development. Proceedings of ICCBR-2005, pp. 169–180.
Abbaspour, R. A. and Samadzadegan, F. (2011). Time-dependent Personal Tour Planning and Scheduling in Metropolises. Expert Systems with Applications. vol. 38, no. 10, pp. 12439–12452.
Yan, H. and Hongzhi, G. (2010). Study on Models of Commuter Mode Choice Beyond Fuel Prices Based on Rrdered Logit Models. Journal of American Science, vol. 6, no. 8, pp. 230–235.
Zhan, F. B. and Noon, C. E. (1998). Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transportation Science, 32 (1): 65–73.
Athieson, A. and Wall, G. (1982). Tourism, Economic, Physical and Social Impacts. Longman.
West, D. B. (2005). Introduction to Graph Theory (Second Edition). Mathematical Department. University of Illinois.
Prathik, A., Uma, k. and Anuradha, J. (2016). An Overview of application of Graph theory. International Journal of ChemTech Research. ISSN: 0974-4290. Vol.9, No.02 pp 242-248.
Mashaghi, A. et al. (2004). Investigation of a Protein Complex Network. European Physical Journal B. 41 (1): 113–121.
Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik.
Phil, F. (2010). An Interview with Edsger W. Dijkstra. Communications of the ACM. 53 (8): 41–47. doi:10.1145/1787234.1787249.
Kurt, M. and Sanders, P. (2008). Chapter 10. Shortest Paths. Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0.
Carmon, M., Heath, T., Oc, T. and Tiesdell, S. (2003). Public Places Urban Spaces: The Dimensions of Urban Design. Architectural Press. Boston. MA.
O-conor, A., Zeger, A. and Itami, B. (2005). Geo-temporal Tracking and Analysis of Tourist Movement, Mathematics and Computer in Simulation.
Tutte, W.T. (2001), Graph Theory, Cambridge University Press, p. 30, ISBN 978-0-521-79489-3, retrieved 2016-03-14.
Bondy, J. A. and Murty, U. S. R. (1982). Graph Theory with Applications.  Department of Combination and Optimization. University of Waterloo. Ontario. Canada.