This is a paper study note for my startup travel service called StyleTrip.
The paper is Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints

Introduction

• How to efficiently search for the most interesting trip which satisfies a travel time constraint from a large number of attractions.
• The efficient of trip planning is sensitive to the scalability of travel regions.
• The optimal trip finding problem is different from Traveling Sales Problem(TSP).
• The reason is that TSP finds the shortest path from the extra N given locations. However, the optimal trip problem is to finds a sub-permutation of given N locations.
• The dynamic programming searches all possible trips based on the concept of DFS.

Optimization mechanisms

• Attraction sorting ( User favorite, the must-go / popular / high-rating places )
• Low bound checking ( meeting time, cost constaints )
• Score Checking ( meeting low bound checking and the score is maximum）

Definitions

• Score: It can refer to user favorite , popularity or rating value.
• Valid trip: A trip is valid if the total trip time is less than or equal to the required travel time.
• Optima trip: A valid trip is optimal if the Score(tripA) is maximum among the valid trip.

Proposed theorem

• We can find out that calculation of the trip takes an exponential time, so that it can conclude that this is a NP complete problem.
• Triangle inequality Travel time (x,y)+(y,x) >= (x,z)
• If travel time (a0,trip1) <= (a0,trip2), then trip1 is the sub-trip of trip2.
• Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. (pruning strategy 1)

Pruning strategy

1. Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. Based on the pruning strategy 1, we can prune the trips which contain any invalid trip to reduce the calculations.
2. Given an place set A, A is not a valid trip set if the trip time is greater than the travel time constraint.

Approach

1. Find the candidate place set: starting from 1-place-set, 2-place-set (#2 permutation) ... , n-place-set (#n combination), we find all valid trip permutation and remove all the invalid trip and its super-trip permuation (pruning strategy 1).
2. Filter the valie trip set with pruning strategy 2.
3. The trip scores of a trip set and its all permutations are the same, so we don't need to check the permutations which satisifies the travel time constraint.