License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2020.14
URN: urn:nbn:de:0030-drops-131502
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13150/
Go to the corresponding OASIcs Volume Portal

Gündling, Felix ; Witzel, Tim

Time-Dependent Tourist Tour Planning with Adjustable Profits

pdf-format:
OASIcs-ATMOS-2020-14.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{gndling_et_al:OASIcs:2020:13150,
  author =	{Felix G{\"u}ndling and Tim Witzel},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Dennis Huisman and Christos D. Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13150},
  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}
}

Keywords: tourist tour planning, orienteering problem, TDTOPTW, mixed integer linear programming, iterated local search, computational study
Collection: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Issue Date: 2020
Date of publication: 10.11.2020
Supplementary Material: Evaluation data provided at https://github.com/motis-project/berlin-pois

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI