Het plannen van routes voor toeristen aan de hand van meerdere criteria
- IneUmans
Het plannen van routes voor toeristen aan de hand van meerdere criteria Umans Ine
U vertrekt voor enkele dagen naar een bestemming. U bent een toerist op die bestemming op zoek naar cultuur. Wat gaat u op die bestemming bezichtigen? Hoeveel tijd heeft u ter beschikking om die bezienswaardigheden te bezoeken? Stel dat u gekozen heeft om X aantal bezienswaardigheden te bezoeken, wanneer gaat u dan dewelke bezoeken? Misschien is het beter om de bezienswaardigheden in een andere volgorde te bezoeken zodat de route tussen de bezienswaardigheden optimaler bevonden wordt? Verschillende vragen die samen met de overvloed aan informatie vanuit verschillende invalshoeken ervoor zorgen dat het plannen van een reis geen gemakkelijke opgave is voor een toerist.
Reisbureaus en ontwikkelde aanbevelingsystemen zijn er om de toerist te helpen in het plannen van zijn reis. Bij het uitvoeren van de geplande reis kunnen echter problemen opduiken zoals een foutief aangebrachte sluitingsdag of het ontbreken van tijdelijke informatie bijvoorbeeld theatervoorstellingen. De personalised electronic tourist guide (PET) is een applicatie die deze problemen kan voorkomen.
De PET is gebaseerd op het voorkomen van het tourist trip design probleem (TTDP). De problematiek rond het oplossen van toeristische problemen is actueel. Toeristen hebben nood aan effectieve ondersteuning van hun besluitvorming omtrent de selectie van bezienswaardigheden en een route hiertussen. Het probleem bestaande uit het selecteren van een route tussen de verschillende bezienswaardigheden met als doel de voldoening van de toerist te maximaliseren, wordt geclassificeerd als een tourist trip design probleem. Startend vanuit het meest eenvoudige probleem, het orienteering probleem, wordt getracht te evolueren naar een complexer probleem, het multi-constraint team orienteering problem with multiple time windows. Deze evolutie zorgt ervoor dat met meer factoren rekening gehouden wordt zoals het beschikbare budget van de toerist of verschillende openingsuren van bezienswaardigheden op verschillende dagen.
Aangezien de toerist snel over een oplossing voor zijn probleem wil beschikken, zijn efficiënte algoritmen nodig die in realtime een oplossing voor het TTDP kunnen aanbieden. Verscheidene auteurs hebben gepoogd een oplossingsmethode te ontwikkelen voor de verschillende gradaties van tourist trip design problemen. In de literatuurstudie worden zowel exacte algoritmen als heuristieken aangehaald die dienen als oplossingsmethoden voor tourist trip design problemen. Vertrekkend vanuit deze beschikbare algoritmen, wordt in de praktijkstudie een tabu search algoritme beschreven om een specifiek probleem op te lossen. Een oplossing wordt voorgesteld voor een toerist die de stad Hasselt gedurende twee dagen bezoekt.
Het is mogelijk een toeristische route te plannen met als doel de meest interessante locaties te bezoeken, rekening houdend met budget- en tijdsbeperkingen alsook met verscheidene criteria aangaande de aantrekkelijkheid van locaties.
Bibliografie
Archetti, C., Feillet, D., Hertz, A., & Speranza, M.G. (2010). The undirected capacitated arc routing problem with profits. Computers and Operations Research, vol. 37, 1860-1869.
Baeza-Yates, R., & Ribeiro-Neto, R. (1999). Modern information retrieval. New York: Addison-Wesley.
Basistarieven en kortingen. (2013). Opgevraagd op 19 maart, 2013, via http://kinepolis.be/nl/bioscopen/kinepolis-hasselt#information.
Buhalis, D. (2003). eTourism: information technology for strategic tourism management. London: Prentice Hall.
Buhalis, D., & Law, R. (2008). Twenty years on and 10 years after the internet: the state of eTourism research. Tourism Management, vol. 29, 609–623.
Castro, M., Goos, P., Sörensen, K., & Vansteenwegen, P. (2013). A memetic algorithm for the travelling salesperson problem with hotel selection. Computers and Operations Research, http://dx.doi.org/10.1016/j.cor.2013.01.006.
Chao, L., Golden, B., & Wasil, E. (1996). Theory and methodology – a fast and effective heuristic for the orienteering problem. European Journal of Operational Research, vol. 88, 475-489.
Chong, C.S., Low, M.Y.H., & Wong, L.-P. (2010). Bee colony optimization with local search for travelling salesman problem. International Journal on Artificial Intelligence Tools, vol. 19, 305-334.
Dunlop, M., McCallum, S., Morrison, S., Ptasinski, P., Risbey, C., & Stewart, F. (2004). Design and development of Taeneb city guide - from paper maps and guidebooks to electronic guides. Proceedings of Enter 2004, Caïro, Egypte, 2004.
Feillet, D., Dejax, P., & Gendreau, M. (2005). Travelling salesman problems with profits. Transportation Science, vol. 39, 188-205.
Fesenmainer, D.R., Ricci, F., Schaumlechner, E., Wober, K., & Zanella, C. (2003). Dietorecs: travel advisory for multiple decision styles. In Information and communication Technologies in tourism, 232-241. New York: Springer.
Fischetti, M., Salazar, J., & Toth, P. (1998). Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, vol. 10, 133-148.
Fomin, F.V., & Lingas, A. (2002). Approximation algorithms for time-dependent orienteering. Information Processing Letters, vol. 83, 57-62.
Fung, R.Y.K., Tang, J., & Zhang, J. (2011). A scatter search for multi-depot vehicle routing problem with weight-related cost. Asia-Pacific Journal of Operational Research, vol. 28, 323-348.
Garcia, A., Vansteenwegen, P., Souffriau, W., Arbelaitz, O., & Linaza, M. T. (2010). Solving multi constrained team orienteering problems to generate tourist routes. Discrete Optimization, under review.
Gavalas, D., Konstantopoulus, C., Mastakas, K., Pantziou, G., & Tasoulas, Y. (2012). A survey on algorithmic approaches for solving tourist trip design problems. eCompass.
Gendreau, M., Laporte, G., & Semet, F. (1998a). A tabu search heuristic for the undirected selective travelling salesman problem. European Jounal of Operational Research, vol. 106, 539-545.
Gendreau, M., Laporte, G., & Semet, F. (1998b). A branch-and-cut algorithm for the undirected selective travelling salesman problem. Networks, vol. 32, 263-273.
Golden, B., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics, vol. 34, 307-318.
Hannes, W. (2003). Intelligent system in travel and tourism. Proceeding of the 18th international joint conference on artificial intelligence, Acapulco, Mexico, 2003.
Hillier, F.S., & Lieberman, G.J. (2010). Introduction to Operations Research. New York: McGraw-Hill.
Jeong, M., Oh, H., & Gregoire, M. (2003). Conceptualizing Web site quality and its consequences in the lodging industry. International Journal of Hospitality Management, vol. 22, 161-175.
Kalender. (2013). Opgevraagd op 28 maart, 2013, via http://www.plopsa.be/plopsa-indoor-hasselt/nl/kalender.
Kramer, R., Modsching, M., & ten Hagen, K. (2006). A city guide agent creating and adapting individual sightseeing tours based on field trial results. International Journal of Computational Intelligence Research, vol. 2, 191-206.
Labadi, N., Prins, C., & Reghioui, M. (2009). Tour splitting algorithms for vehicle routing problems. International Journal of Production Research, vol. 47, 507-535.
Laporte, G., & Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Mathematics, vol. 26, 193-207.
Leifer, A., & Rosenwein, M. (1994). Strong linear programming relaxations for the orienteering problem. Europan Journal of Operational Research, vol. 73, 517-523.
Lin, S.-W., & Yu, V.F. (2012). A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, vol. 217, 94-107.
Miller, C., Tucker, A., & Zemlin, R. (1960). Integer programming formulations and travelling salesman problems. Journal of the ACM, vol. 7, 326-329.
Montemanni, R., & Gambardella, L. (2009). Ant colony system for team orienteering problems with time windows. Computational Decision Science, vol. 34.
Morrison, A.M., Jing, S., O’Leary, J.T., & Lipping, A.C. (2001). Predicting usage of the Internet for travel bookings: An exploratory study. Information Technology & Tourism, vol. 4, 15-30.
Muyldermans, L., Beullens, P., Cattrysse, D., & Van Oudheusden, D. (2005). Exploring variants of 2- and 3-opt for the general routing problem. Operations Research, vol. 53, 982-995.
Ramesh, R., & Brown, K. (1991). An efficient four-phase heuristic for the generalized orienteering problem. Computers and Operations Research, vol. 18, 151-165.
Ramesh, R., Yoon, Y., & Karwan, M. (1992). An optimal algorithm for the orienteering tour problem. ORSA Journal on Computing, vol. 4, 155-165.
Ricci, F., & Wether, H. (2002). Case base querying for travel planning recommendation. Information Technology & Tourism, vol. 4, 215-226.
Righini, G., & Salani, M. (2009). Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computational Operations Research, vol. 36, 1191-1203.
Routebeschrijving. (2013). Opgevraagd op 19 maart, 2013, via http://maps.google.be/.
Schafer, J. B., Konstan, J. & Riedi, J. (1999). Recommender systems in e-commerce. In Proceedings of the 1st acm Conference on Electronic Commerce 1999.
Schilde, M., Doerner, K.F., Hartl, R.F., & Kiechle, G. (2009). Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, vol. 3, 179-201.
Souffriau, W., & Vansteenwegen, P. (2010). Tourist trip planning functionalities: State-of-the-art and future. In F. Daniel & F.M. Facca (Eds.), Lecture Notes in Computer Science (Vol. 6385, pp. 474–485). Presented at the 10th International conference on Web Engineering (ICWE 2010), Berlin, Germany: Springer.
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2006). Multilevel metaheuristics for the orienteering problem. In 7th EU/Meeting on Adaptive, Self-Adaptive, and Multi-Level Metaheuristics, University of Malaga, Spain, November 2006.
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2012). The multiconstraint team orienteering problem with multiple time windows. Transportation Science.
Souffriau, W., Vansteenwegen, P., Vertommen, J., Vanden Berghe, G., & Van Oudheusden, D. (2008). A personalized tourist trip design algorithm for mobile tourist guides. Applied Artificial Intelligence, vol. 22, 964-985.
Sylejmani, K., Dorn, J., & Musliu, N. (2012). A tabu search approach for multi constrained team orienteering problem and its application in touristic trip planning. In Proceedings of the 12th International Conference on Hybrid Intelligent Systems 2012, 300-305.
Tarieven. (2013). Opgevraagd op 19 maart, 2013, via http://www.hasselt.be/nl/content/3416/tarieven.html.
Tarieven. (2013). Opgevraagd op 19 maart, 2013, via http://www.plopsa.be/plopsa-indoor-hasselt/nl/tarieven.
Toerisme. (2010). Opgevraagd op 21 april, 2012, via http://www.belgium.be/nl/over_belgie/toerisme/.
Toerisme Hasselt. (2013). Bezienswaardig Hasselt & Zonhoven.
Toerisme Hasselt. (2013). Opgevraagd op 18 februari, 2013, via http://toerisme.hasselt.be/nl/.
Toerisme in Europa ondersteunen. (2012). Opgevraagd op 21 april, 2012, via http://ec.europa.eu/enterprise/sectors/tourism/index_nl.htm.
Toerisme Limburg. (2013). Hasselt Ontdekkingsgids 2013. Hasselt: Toerisme Limburg vzw.
Tricoire, F., Romauch, M, Doerner, K.F., & Hartl, R.F. (2010). Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, vol. 37, 351-367.
Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, vol. 35, 797-809.
Vansteenwegen, P., Souffriau, W., & Sörensen, K. (2011a). The travelling salesperson problem with hotel selection. Journal of the Operational Research Society, vol. 63, 207-217.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, vol. 36, 3281-3290.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2011b). The City Trip Planner: An expert system for tourists. Expert Systems with Applications, vol. 38, 6540-6546.
Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011c). The orienteering problem: A survey. European Journal of Operational Research, vol. 209, 1-10.
Vansteenwegen, P., & Van Oudheusden, D. (2007). The mobile tourist guide: An OR opportunity. OR Insights, vol. 20, 21-27.
Voudouris, C., & Tsang, E. (1999). Guided local search and its application to the travelling salesman problem. European Journal of Operational Research, vol. 113, 469-499.
Wang, X., Golden, B., & Wasil, E. (2008). Using a genetic algorithm to solve the generalized orienteering problem. In: Golden, B., Raghavan, S., & Wasil, E. (Eds.), The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 263-274.
Why Tourism?. (2012). Opgevraagd op 21 april, 2012, via http://unwto.org/en/content/why-tourism.
Zhu, C., Hu, J.Q., Wang, F., Xu, Y., & Cao, R. (2010). On the tour planning problem. Annals of Operations Research, vol. 192, 67-86.
Zong, G., Tseng, C.-L., & Park, Y. (2005). Harmony search for generalized orienteering problem: Best touring in China. Advances in Natural Computation, 741-750.
