DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2020.14

Time-Dependent Tourist Tour Planning with Adjustable Profits

Authors: Felix Gündling and Tim Witzel

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{gundling_et_al:OASIcs.ATMOS.2020.14,
  author =	{G\"{u}ndling, Felix and Witzel, Tim},
  title =	{{Time-Dependent Tourist Tour Planning with Adjustable Profits}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{14:1--14:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.14},
  URN =		{urn:nbn:de:0030-drops-131502},
  doi =		{10.4230/OASIcs.ATMOS.2020.14},
  annote =	{Keywords: tourist tour planning, orienteering problem, TDTOPTW, mixed integer linear programming, iterated local search, computational study}
}

Search Results

Documents authored by Witzel, Tim

Time-Dependent Tourist Tour Planning with Adjustable Profits

Abstract

Cite as

Thanks for your feedback!

Could not send message