Personalised sightseeing itineraries computed in seconds

Note on the source. This source should be read with caution: it may be funded by the sector, a draft or a thesis, or rely on self-reported or modelled data. See the limitations below.

The question

How can personalised sightseeing itineraries, over one or more days, be planned automatically while respecting opening hours, public transport timetables, variable visit times and individual preferences, fast enough for a real-time service?

The method

Mathematical formulation (mixed-integer linear programming) of a time-dependent team orienteering problem with time windows and variable profits, plus heuristic algorithms (greedy and iterated local search) on a pre-computed graph of walking and public-transport routes. Tests on 41 points of interest in Berlin and 25 queries (tours of 2 to 10 hours, one or two days).

What the study finds

41 placesof interest in Berlin used for testingFor testing, the authors used 41 Berlin points of interest, chosen manually from several categories, with opening hours collected by hand.

6–20%gap from the theoretical maximum after 10 hoursEven after 10 hours of computation per query, the exact method proves it has found the best possible itinerary only for the simplest case (a two-hour tour); for the others, the distance between the best solution found and the theoretical maximum stays between 6% and 20%.

5–10 pct ptslower itinerary score of the greedy methodThe simplest greedy method answers in 2-4 milliseconds, but its itineraries score 5-10 percentage points below those of the exact method, and 16 points below in one case.

≈ 1.5 saverage run time of iterated local searchIterated local search takes about 1.5 seconds on average: it repairs poor starting solutions well but hardly ever improves on solutions that are already good.

Computing all walking and public-transport links between these places in advance takes roughly a quarter of an hour, short enough to redo whenever timetables or routes change.
Dividing the day into 5-minute intervals is the best compromise: moving to 1-minute intervals makes computation about five times slower and improves quality by only 0.5-1 percentage points.

Why it matters for ports and cities

The study is not about cruises, but it tackles a problem similar to a shore call: building a personal itinerary within a fixed time, taking opening hours and public transport into account. It shows usable suggestions can be produced within seconds, although fast methods can fall noticeably short of the best solution.

Limitations

Algorithmic study with no real users or behavioural data; the value of points of interest and preferences are assumed parameters; a single case (Berlin, 41 points of interest) and no specific reference to cruise tourism or to back-on-board constraints.

Full reference and source

Gündling, F., Witzel, T. (2020). Time-Dependent Tourist Tour Planning with Adjustable Profits. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), OpenAccess Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Read the original study ↗

Summary written by the ODYBOAT Observatory in our own words. Tables and figures belong to the authors.