[Styletrip] 在總旅程時間限制下,如何有效的找到可行的旅遊路線
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 oftrip2
. - Given a invalid (total trip time exploded)
trip1
, then any super-trip oftrip1
is invalid, too. (pruning strategy 1)
Pruning strategy
- Given a invalid (total trip time exploded)
trip1
, then any super-trip oftrip1
is invalid, too. Based on the pruning strategy 1, we can prune the trips which contain any invalid trip to reduce the calculations. - Given an place set A, A is not a valid trip set if the trip time is greater than the travel time constraint.
Approach
- 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).
- Filter the valie trip set with pruning strategy 2.
- 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.