36 ms·
Orienteering Algorithms for Generating Travel Itineraries [pdf]
- troydavis 8y agoBackground: https://ai.google/research/pubs/pub46479 https://ai.google/research/pubs/pub46479, https://ai.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html https://ai.googleblog.com/2016/09/the-280-year-old-algorithm... "We study the problem of automatically and efficiently generating itineraries for users who are on vacation. We focus on the common case, wherein the trip duration is more than a single day. Previous efficient algorithms based on greedy heuristics suffer from two problems. First, the itineraries are often unbalanced, with excellent days visiting top attractions followed by days of exclusively lower-quality alternatives. Second, the trips often re-visit neighborhoods repeatedly in order to cover increasingly low-tier points of interest. Our primary technical contribution is an algorithm that addresses both these problems by maximizing the quality of the worst day."