Document Open Access Logo

Time-Dependent Tourist Tour Planning with Adjustable Profits

Authors Felix Gündling, Tim Witzel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.14.pdf
  • Filesize: 454 kB
  • 14 pages

Document Identifiers

Author Details

Felix Gündling
  • Technical University of Darmstadt, Germany
Tim Witzel
  • Technical University of Darmstadt, Germany

Funding

This work was partially supported by Deutsche Bahn.

Cite AsGet BibTex

Felix Gündling and Tim Witzel. Time-Dependent Tourist Tour Planning with Adjustable Profits. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.14

Abstract

Planning a tourist trip in a foreign city can be a complex undertaking: when selecting the attractions and choosing visit order and visit durations, opening hours as well as the public transit timetable need to be considered. Additionally, when planning trips for multiple days, it is desirable to avoid redundancy. Since the attractiveness of activities such as shopping or sightseeing depends on personal preferences, there is no one-size-fits-all solution to this problem. We propose several realistic extensions to the Time-Dependent Team Orienteering Problem with Time Windows (TDTOPTW) which are relevant in practice and present the first MILP representation of it. Furthermore, we propose a problem-specific preprocessing step which enables fast heuristic (iterated local search) and exact (mixed-integer linear programming) personalized trip-planning for tourists. Experimental results for the city of Berlin show that the approach is feasible in practice.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Randomized local search
Keywords
  • tourist tour planning
  • orienteering problem
  • TDTOPTW
  • mixed integer linear programming
  • iterated local search
  • computational study

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Rahim A Abbaspour and Farhad Samadzadegan. Time-dependent personal tour planning and scheduling in metropolises. Expert Systems with Applications, 38(10):12439-12452, 2011. Google Scholar
  2. Victor Anthony Arrascue Ayala, Kemal Cagin Gülsen, Marco Muñiz, Anas Alzogbi, Michael Färber, and Georg Lausen. A delay-robust touristic plan recommendation using real-world public transportation information. In CEUR Workshop Proceedings, volume 1906, 2017. Google Scholar
  3. Ali Azizi, Farid Karimipour, and Ali Esmaeily. Time-dependent, activity-based itinerary personal tour planning in multimodal transportation networks. Annals of GIS, 23(1):27-39, 2017. Google Scholar
  4. Joan Borràs, Antonio Moreno, and Aida Valls. Intelligent tourism recommender systems: A survey. Expert Systems with Applications, 41(16):7370-7389, 2014. Google Scholar
  5. Sylvain Boussier, Dominique Feillet, and Michel Gendreau. An exact algorithm for team orienteering problems. 4or, 5(3):211-230, 2007. Google Scholar
  6. I-Ming Chao, Bruce L Golden, and Edward A Wasil. A fast and effective heuristic for the orienteering problem. European journal of operational research, 88(3):475-489, 1996. Google Scholar
  7. I-Ming Chao, Bruce L Golden, and Edward A Wasil. The team orienteering problem. European journal of operational research, 88(3):464-474, 1996. Google Scholar
  8. Daniel Delling, Thomas Pajor, and Renato F Werneck. Round-based public transit routing. Transportation Science, 49(3):591-604, 2015. Google Scholar
  9. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly simple and fast transit routing. In International Symposium on Experimental Algorithms, pages 43-54. Springer, 2013. Google Scholar
  10. Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-criteria shortest paths in time-dependent train networks. In International Workshop on Experimental and Efficient Algorithms, pages 347-361. Springer, 2008. Google Scholar
  11. Güneş Erdoǧan and Gilbert Laporte. The orienteering problem with variable profits. Networks, 61(2):104-116, 2013. Google Scholar
  12. Fedor V Fomin and Andrzej Lingas. Approximation algorithms for time-dependent orienteering. Information Processing Letters, 83(2):57-62, 2002. Google Scholar
  13. Ander Garcia, Olatz Arbelaitz, Maria Teresa Linaza, Pieter Vansteenwegen, and Wouter Souffriau. Personalized tourist route generation. In International Conference on Web Engineering, pages 486-497. Springer, 2010. Google Scholar
  14. Ander Garcia, Pieter Vansteenwegen, Olatz Arbelaitz, Wouter Souffriau, and Maria Teresa Linaza. Integrating public transportation in personalised electronic tourist guides. Computers & Operations Research, 40(3):758-774, 2013. Google Scholar
  15. Damianos Gavalas, Vlasios Kasapakis, Charalampos Konstantopoulos, Grammati Pantziou, Nikolaos Vathis, and Christos Zaroliagis. The ecompass multimodal tourist tour planner. Expert systems with Applications, 42(21):7303-7316, 2015. Google Scholar
  16. Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, and Grammati Pantziou. Mobile recommender systems in tourism. Journal of network and computer applications, 39:319-333, 2014. Google Scholar
  17. Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, and Grammati Pantziou. A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20(3):291-328, 2014. Google Scholar
  18. Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, Grammati Pantziou, and Nikolaos Vathis. Heuristics for the time dependent team orienteering problem: Application to tourist route planning. Computers & Operations Research, 62:36-50, 2015. Google Scholar
  19. Bruce L Golden, Larry Levy, and Rakesh Vohra. The orienteering problem. Naval Research Logistics (NRL), 34(3):307-318, 1987. Google Scholar
  20. Cyrille Gueguen. Méthodes de résolution exacte pour les problèmes de tournées de véhicules. PhD thesis, Châtenay-Malabry, Ecole centrale de Paris, 1999. Google Scholar
  21. Aldy Gunawan, Hoong Chuin Lau, and Pieter Vansteenwegen. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2):315-332, 2016. Google Scholar
  22. Felix Gündling, Mohammad Hossein Keyhani, Mathias Schnee, and Karsten Weihe. Fully realistic multi-criteria multi-modal routing, December 2014. URL: http://tuprints.ulb.tu-darmstadt.de/4298/.
  23. LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL: http://www.gurobi.com.
  24. Gilbert Laporte and Silvano Martello. The selective travelling salesman problem. Discrete applied mathematics, 26(2-3):193-207, 1990. Google Scholar
  25. Shih-Wei Lin and F Yu Vincent. A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 217(1):94-107, 2012. Google Scholar
  26. Antonio Moreno, Aida Valls, David Isern, Lucas Marin, and Joan Borràs. Sigtur/e-destination: ontology-based personalized recommendation of tourism and leisure activities. Engineering applications of artificial intelligence, 26(1):633-651, 2013. Google Scholar
  27. Wouter Souffriau, Pieter Vansteenwegen, Greet Vanden Berghe, and Dirk Van Oudheusden. The multiconstraint team orienteering problem with multiple time windows. Transportation Science, 47(1):53-63, 2013. Google Scholar
  28. V Subramaniyaswamy, R Logesh, V Vijayakumar, K Keerthana, K Rakini, and B Swarnamalya. Dynamo: Dynamic multimodal route and travel recommendation system. In 2018 International Conference on Recent Trends in Advance Computing (ICRTAC), pages 47-52. IEEE, 2018. Google Scholar
  29. Fabien Tricoire, Martin Romauch, Karl F Doerner, and Richard F Hartl. Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, 37(2):351-367, 2010. Google Scholar
  30. Theodore Tsiligirides. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9):797-809, 1984. Google Scholar
  31. Pieter Vansteenwegen and Aldy Gunawan. Orienteering problems: Models and algorithms for vehicle routing problems with profits. Springer Nature, 2019. Google Scholar
  32. Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden. Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12):3281-3290, 2009. Google Scholar
  33. Pieter Vansteenwegen, Wouter Souffriau, and Dirk Van Oudheusden. The orienteering problem: A survey. European Journal of Operational Research, 209(1):1-10, 2011. Google Scholar
  34. Pieter Vansteenwegen and Dirk Van Oudheusden. The mobile tourist guide: an or opportunity. OR insight, 20(3):21-27, 2007. Google Scholar
  35. Jingjin Yu, Javed Aslam, Sertac Karaman, and Daniela Rus. Optimal tourist problem and anytime planning of trip itineraries. arXiv preprint arXiv:1409.8536, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact