Prioritizing travel itineraries

• US 8,510,315 B2
• Filed: 12/06/2010
• Issued: 08/13/2013
• Est. Priority Date: 12/06/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Xie, Xing
• Primary Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US12/960,919
• Publication Number:
  US 20120143882A1
• Time in Patent Office: 981 Days
• Field of Search: None
• US Class Current: 707/751
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

One or more techniques and/or systems are disclosed for prioritizing one or more travel itineraries based on an itinerary query. Respective candidate itineraries from a set of candidate itineraries are ranked based on one or more ranking factors for the candidate itineraries, where the candidate itineraries were identified from a location-interest graph using the query. A desired number of the ranked candidate itineraries are re-ranked based on a one or more historical travel sequences, such that one or more prioritized travel itineraries can be identified in response to the itinerary query.

Claims

1. A computer-based method, comprising:

receiving an itinerary query comprising a starting location, an ending location and a duration;

identifying a set of trip candidates, from a location-interest graph, comprising;

performing a first comparison of the starting location of the itinerary query with at least one of a first starting location of a first trip candidate, a second starting location of a second trip candidate, a third starting location of a third trip candidate or a fourth starting location of a fourth trip candidate;

performing a second comparison of the ending location of the itinerary query with at least one of a first ending location of the first trip candidate, a second ending location of the second trip candidate, a third ending location of the third trip candidate or a fourth ending location of the fourth trip candidate;

performing a third comparison of the duration of the itinerary query with at least one of;

a combination of at least a first travel time associated with the first trip candidate and a first stay time associated with one or more locations associated with the first trip candidate;

a combination of at least a second travel time associated with the second trip candidate and a second stay time associated with one or more locations associated with the second trip candidate;

a combination of at least a third travel time associated with the third trip candidate and a third stay time associated with one or more locations associated with the third trip candidate;

or

a combination of at least a fourth travel time associated with the fourth trip candidate and a fourth stay time associated with one or more locations associated with the fourth trip candidate; and

including the first trip candidate, the second trip candidate and the third trip candidate, but not the fourth trip candidate, within the set of trip candidates based on the first comparison, the second comparison and the third comparison;

identifying;

a first threshold difference for the first trip candidate, the first threshold difference comprising a first difference between a desired threshold value and a first value for the first trip candidate;

a second threshold difference for the second trip candidate, the second threshold difference comprising a second difference between the desired threshold value and a second value for the second trip candidate; and

a third threshold difference for the third trip candidate, the third threshold difference comprising a third difference between the desired threshold value and a third value for the third trip candidate, at least one of the desired threshold value, the first value, the second value or the third threshold value based on one or more trip factors;

selecting the first trip candidate and the second trip candidate, but not the third trip candidate, from the set of trip candidates based on the first threshold difference and the second threshold difference corresponding to a desired range of identified threshold differences, and the third threshold difference not corresponding to the desired range of identified threshold differences;

ranking the first trip candidate and the second trip candidate based on one or more ranking factors;

re-ranking the first trip candidate and the second trip candidate based on one or more historical travel sequences; and

providing the re-ranked trip candidates in response to receiving the itinerary query.

2. The method of claim 1, ranking comprising ranking the first trip candidate, the second trip candidate and one or more other trip candidates based on the one or more ranking factors.

3. The method of claim 1, re-ranking comprising re-ranking the first trip candidate, the second trip candidate and one or more other trip candidates based on the one or more ranking factors.

4. The method of claim 1, the one or more trip factors comprising at least one of an elapsed time ratio, a stay time ratio or an interest density ratio.

5. The method of claim 1, the one or more ranking factors comprising one or more of:

a duration of a trip candidate;

a travel time between locations for the trip candidate;

a stay time at a location for the trip candidate;

or

a location interest factor for the trip candidate.

6. The method of claim 1, ranking comprising ranking a trip candidate based on a duration of the trip candidate.

7. The method of claim 1, ranking comprising ranking a trip candidate based on a travel time between locations for the trip candidate.

8. The method of claim 1, ranking comprising ranking a trip candidate based on a location interest factor for the trip candidate.

9. The method of claim 1, re-ranking comprising re-ranking based on an experience level of travelers associated with at least some of the one or more historical travel sequences.

10. The method of claim 1, re-ranking comprising re-ranking merely one or more ranked trip candidates that meet a desired rank threshold.

11. The method of claim 1, ranking comprising ranking the first trip candidate and the second trip candidate based on a first combination of ranking factors for the first trip candidate and a second combination of ranking factors for the second trip candidate.

12. The method of claim 1, comprising generating the location-interest graph comprising:

identifying a node for the location-interest graph comprising a geographical location;

identifying an interest level for the node;

identify a stay time for the node; and

identifying an edge for the location-interest graph comprising a travel trajectory between the node and a second node in the location-interest graph.

13. The method of claim 12, identifying the stay time comprising identifying a median stay time using a plurality of stay times from the one or more historical travel sequences.

14. The method of claim 12, identifying the edge comprising identifying a median travel trajectory using a plurality of travel trajectories from the one or more historical travel sequences.

15. The method of claim 1, at least one of the first trip candidate, the second trip candidate, the third trip candidate or the fourth trip candidate associated with one or more GPS trajectories.

16. The method claim 1, ranking comprising ranking a trip candidate based on a stay time at a location for the trip candidate.

17. A system, comprising:

one or more processing units; and

memory comprising instructions that when executed by at least some of the one or more processing units perform a method, comprising;

receiving an itinerary query comprising a starting location, an ending location and a duration;

identifying a set of trip candidates, from a location-interest graph, comprising;

performing a first comparison of the starting location of the itinerary query with at least one of a first starting location of a first trip candidate, a second starting location of a second trip candidate, a third starting location of a third trip candidate or a fourth starting location of a fourth trip candidate;

performing a second comparison of the ending location of the itinerary query with at least one of a first ending location of the first trip candidate, a second ending location of the second trip candidate, a third ending location of the third trip candidate or a fourth ending location of the fourth trip candidate;

performing a third comparison of the duration of the itinerary query with at least one of;

a combination of at least a first travel time associated with the first trip candidate and a first stay time associated with one or more locations associated with the first trip candidate;

a combination of at least a second travel time associated with the second trip candidate and a second stay time associated with one or more locations associated with the second trip candidate;

a combination of at least a third travel time associated with the third trip candidate and a third stay time associated with one or more locations associated with the third trip candidate;

or

a combination of at least a fourth travel time associated with the fourth trip candidate and a fourth stay time associated with one or more locations associated with the fourth trip candidate; and

including the first trip candidate, the second trip candidate and the third trip candidate, but not the fourth trip candidate, within the set of trip candidates based on the first comparison, the second comparison and the third comparison;

identifying;

a first threshold difference for the first trip candidate, the first threshold difference comprising a first difference between a desired threshold value and a first value for the first trip candidate;

a second threshold difference for the second trip candidate, the second threshold difference comprising a second difference between the desired threshold value and a second value for the second trip candidate; and

a third threshold difference for the third trip candidate, the third threshold difference comprising a third difference between the desired threshold value and a third value for the third trip candidate, at least one of the desired threshold value, the first value, the second value or the third threshold value based on one or more trip factors;

selecting the first trip candidate and the second trip candidate, but not the third trip candidate, from the set of trip candidates based on the first threshold difference and the second threshold difference corresponding to a desired range of identified threshold differences, and the third threshold difference not corresponding to the desired range of identified threshold differences;

ranking the first trip candidate and the second trip candidate based on one or more ranking factors;

re-ranking the first trip candidate and the second trip candidate based on one or more historical travel sequences; and

providing the re-ranked trip candidates in response to receiving the itinerary query.

18. The system of claim 17, the one or more trip factors comprising at least one of:

a stay time ratio;

an interest density ratio;

or

an elapsed time ratio.

19. The system of claim 17, the location-interest graph comprising:

a plurality of nodes respectively corresponding to a location;

an interest level for respective nodes;

a stay time for respective nodes; and

one or more edges respectively comprising a travel trajectory between two nodes.

20. A computer-readable medium excluding signals comprising instructions that when executed perform a method, comprising:

receiving an itinerary query comprising a starting location, an ending location and a duration;

identifying a set of trip candidates, from a location-interest graph, comprising;

performing a first comparison of the starting location of the itinerary query with at least one of a first starting location of a first trip candidate, a second starting location of a second trip candidate, a third starting location of a third trip candidate or a fourth starting location of a fourth trip candidate;

performing a second comparison of the ending location of the itinerary query with at least one of a first ending location of the first trip candidate, a second ending location of the second trip candidate, a third ending location of the third trip candidate or a fourth ending location of the fourth trip candidate;

performing a third comparison of the duration of the itinerary query with at least one of;

a combination of at least a first travel time associated with the first trip candidate and a first stay time associated with one or more locations associated with the first trip candidate;

a combination of at least a second travel time associated with the second trip candidate and a second stay time associated with one or more locations associated with the second trip candidate;

a combination of at least a third travel time associated with the third trip candidate and a third stay time associated with one or more locations associated with the third trip candidate;

or

a combination of at least a fourth travel time associated with the fourth trip candidate and a fourth stay time associated with one or more locations associated with the fourth trip candidate; and

including the first trip candidate, the second trip candidate and the third trip candidate, but not the fourth trip candidate, within the set of trip candidates based on the first comparison, the second comparison and the third comparison;

identifying;

a first threshold difference for the first trip candidate, the first threshold difference comprising a first difference between a desired threshold value and a first value for the first trip candidate;

a second threshold difference for the second trip candidate, the second threshold difference comprising a second difference between the desired threshold value and a second value for the second trip candidate; and

a third threshold difference for the third trip candidate, the third threshold difference comprising a third difference between the desired threshold value and a third value for the third trip candidate, at least one of the desired threshold value, the first value, the second value or the third threshold value based on one or more trip factors;

selecting the first trip candidate and the second trip candidate, but not the third trip candidate, from the set of trip candidates based on the first threshold difference and the second threshold difference corresponding to a desired range of identified threshold differences, and the third threshold difference not corresponding to the desired range of identified threshold differences;

ranking the first trip candidate and the second trip candidate based on one or more ranking factors;

re-ranking the first trip candidate and the second trip candidate based on one or more historical travel sequences; and

providing the re-ranked trip candidates in response to receiving the itinerary query.