Optimizing trip itinerary for tourist groups

Abstract

In dieser Arbeit wird eine Lösung für die Planung eines Weges für Gruppen von Touristen vorgeschlagen. Wir nehmen an, dass jeder Tourist individuelle Präferenzen für interessante Punkte hat und auch individuelle Präferenzen hat, mit wem er gemeinsam reisen will. Dieses Problem hat praktische Relevanz, weil häufig Touristen es vorziehen in Gruppen zu verreisen, wobei sie aber stets auch ihre eigenen Präferenzen zumindest teilweise erfüllt haben möchten. Folglich kann die vorgeschlagene Lösung Touristengruppen von der Planung der Tour befreien, Aus der Sicht der Optimierungtheorie ist das Problem komplex, weil die maximale Erfüllung von Zielen aller Touristen unter Beachtung weiterer individueller Einschränkung erreicht werden soll. Auf dem Weg zur Lösung haben wir drei wesentliche Schritte gesetzt. Im ersten Schritt haben wir eine Lösung zur Suche eines optimalen Weges für einen einzelnen Touristen entwickelt, die wir mit existierenden Lösungen in Bezug auf Qualität und Zeitverbrauch vergleichen. Im zweiten Schritt haben wir das Group Tour Problem definiert, das die Optimierung und Berücksichtung aller Touristen in einer gemeinsamen Gruppe beschreibt. Wir stellen drei Ansätze vor, wie das Group Tour Problem mit dem im ersten Schritt entwickelten Algorithmus gelöst werden kann. Der Unterschied dieser drei Ansätze beruht auf der Entscheidung, ob für jeden Touristen einzeln ein Weg geplant wird, für Untergruppen oder für die ganze Gruppe. Schliesslich erweitern wir im dritten Schritt unseren Algorithmus, um ein verbessertes Verfahren zu erhalten, das es erlaubt, dass Touristen einen individualisierten Weg vorgeschlagen bekommen, Dieser Group Tour Algorithmus versucht die Wege der verschiedenen Touristen teilweise vereinen, um eine Maximierung aller Präferenzen zu erreichen. Um die vorgeschlagene Lösung zu evaluieren, entwickeln wir einen neuen Benchmark Test indem wir die in der Literatur existierende Benchmarks für Einzeltouren erweitern. Wir führen Experiment auf Basis des Benchmark Tests mit den vier genannten Ansätzen durch und vergleichen die Ergebnisse in Bezug auf Qualität und benötigter Rechenzeit. Die Experimente zeigen, dass unser verbesserter Algorithmus für die erweiterten Benchmarks immer eine bessere Lösung findet als die drei anderen Ansätze. Zusätzlich führen wir Experimente durch um zwei Ausführungsmodi zu unterscheiden, bei denen entweder kurze Verarbeitungszeit oder höchste Qualität im Vordergrund steht.

In this PhD thesis, we solve the problem of trip itinerary planning for tourist groups. We assume that each tourist has individual preferences for points of interest and preferences with whom in the group s/he would like to share travelling. This problem has practical relevance, since often tourists prefer going on trip in company, while aiming to visit points of interest that meet their individual preferences. Hence, the proposed solution can relieve the tourists from the task of itinerary planning. However, in terms of optimization, this problem is complex due to its objective to maximize the satisfaction of all tourists, while coping with various individual constraints. We follow a path of three steps for solving the problem at hand. In the first step, we develop an algorithm based on Tabu search for solving the solo trip planning problem, which we compare in quality and time consumption against existing solutions in the literature. In the second step, we define the group trip problem that models the objective and the constraints of itinerary planning for a whole tourist group. Further, we use the algorithm developed in the first step to devise three straightforward approaches for solving group trip problem. The difference between the three approaches is whether tourist travel alone, in subgroups or altogether. Finally, in the third step, we extend our planning algorithm, to develop a sophisticated group trip planning algorithm, which allows tourists to have a personalised trip itinerary throughout the trip. In order to meet individual preferences of tourists, the group trip algorithm combines the itinerary of different tourists so that they are sometimes planned to travel alone, and at other times travel in groups. In order to evaluate the proposed algorithms, we create a new benchmark for the group trip problem by extending the existing benchmarks in the literature for the solo trip problem. We conduct the computational experiments with four different proposed approaches by using the new benchmark. The proposed approaches are evaluated based on the quality and respective computation time. Our experiments show that our sophisticated algorithm finds always a better solution than the other three approaches for our extended benchmarks. In addition, we also make experiments with the aim of identifying two modes of algorithm execution, one which produces high quality solutions with a longer computation time, and the other one that produces slightly worse solutions, but with a much less computation effort.