## [Styletrip] 在總旅程時間限制下，如何有效的找到可行的旅遊路線

This is a paper study note for my startup travel service called StyleTrip.

The paper isTrip-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

- 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. - 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.