Incremental searching in multi-passenger multi-route travel planning

• US 8,265,967 B2
• Filed: 08/19/2011
• Issued: 09/11/2012
• Est. Priority Date: 01/18/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: de Marcken, Carl G., Boyan, Justin A.
• Primary Examiner(s): FLYNN, KEVIN H
• Application Number:
  US13/213,229
• Publication Number:
  US 20120059679A1
• Time in Patent Office: 389 Days
• Field of Search: 705/5, 705/6
• US Class Current: 705/6
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation

Abstract

A multiple routes for multiple passengers are produced by ordering passenger groups and for each passenger group, constructing an individual query and sending the individual query to a travel planning system. Solutions based on the individual query are received from the travel planning system and a single individual solution is selected from the response. Constraints are added to subsequent individual queries based on previously selected individual solutions and joint travel requirements or preferences.

Claims

1. A computer-implemented travel planning method for multiple passenger groups traveling on multiple routes, the method comprising:

receiving, by a computer system including one or more computers, a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing, by operation of a computer, a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for one or more of an origin, a destination, a date of departure, a time of departure, a date of arrival, or a time of arrival, and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying, by operation of a computer, a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query;

deriving, by operation of a computer, a constraint on the at least one attribute based on the identified selection of at least one solution;

constructing, by operation of a computer, a second query for a second passenger group, the second query comprising attributes for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival, the second query comprising the constrained at least one attribute, and at least one attribute for the joint travel preference or requirement; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

2. The method of claim 1, wherein the solutions further comprise fares associated with the sets of flights.

3. The method of claim 1, further comprising:

receiving a second plurality of solutions from the same or a different travel planning system, the second plurality of solutions comprising sets of flights based on the second query.

4. The method of claim 1, further comprising sending the first query to the travel planning system for processing the first query by the travel planning system to derive the plurality of solutions.

5. The method of claim 1, further comprising:

ordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the passenger group with the most number of constraints.

6. The method of claim 5, further comprising:

adding constraints to queries for a subsequent passenger group based on the identified selection of at least one solution and one or more of joint travel requirements and preferences with at least one of the joint travel requirements and preferences including sharing a common segment of travel.

7. The method of claim 6, further comprising filtering sets of subsequent solutions for subsequent particular passenger groups according to the joint travel requirements to eliminate subsequent solutions not meeting the joint travel requirements.

8. The method of claim 1, wherein identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query comprises at least one of:

receiving the selection of the at least one solution from a user;

or

making the selection of the at least one solution by a computer.

9. The method of claim 3, further comprising:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query; and

determining a selection of at least one other solution from the first plurality of solutions received from the travel planning system in response to the first query.

10. The method of claim 3, further comprising:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query;

reordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the reordered plurality of passenger groups.

11. The method of claim 10, further comprising:

constructing a revised first query for a first passenger group of the reordered plurality of passenger groups, the revised first query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival;

receiving a revised first plurality of solutions from the travel planning system, the solutions comprising sets of flights based on the revised first query; and

identifying a selection of at least one solution from the revised first plurality of solutions received from the travel planning system in response to the revised first query.

12. The method of claim 11, further comprising:

deriving a constraint on the at least one attribute based on the identified selection of at least one solution from the revised plurality of solutions; and

constructing a third query for a third passenger group different from the revised first passenger group, the third query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival.

13. The method of claim 3, further comprising:

identifying a selection of at least one solution from the second plurality of solutions received from the travel planning system in response to the second query; and

providing information related to the first plurality of solutions and second plurality of solutions.

14. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for one or more of an origin, a destination, a date of departure, a time of departure, a date of arrival, or a time of arrival, and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query;

deriving a constraint on the at least one attribute based on the identified selection of at least one solution;

constructing a second query for a second passenger group, the second query comprising attributes for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival, the second query comprising the constrained at least one attribute, and at least one attribute for the joint travel preference or requirement; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

15. The computer storage medium of claim 14, wherein the solutions further comprise fares associated with the sets of flights.

16. The computer storage medium of claim 14, wherein the operations further comprise:

receiving a second plurality of solutions from the same or a different travel planning system, the second plurality of solutions comprising sets of flights and fares associated with the flights based on the second query.

17. The computer storage medium of claim 14, wherein the operations further comprise sending the first query to the travel planning system for processing the first query by the travel planning system to derive the plurality of solutions.

18. The computer storage medium of claim 14, wherein the operations further comprise:

ordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the passenger group with the most number of constraints.

19. The computer storage medium of claim 18, wherein the operations further comprise:

adding constraints to queries for the subsequent passenger group based on the identified selection of at least one solution and one or more of joint travel requirements and preferences with at least one of the joint travel requirements and preferences including sharing a common segment of travel.

20. The computer storage medium of claim 19, wherein the operations further comprise filtering sets of subsequent solutions for subsequent particular passenger groups according to the joint travel requirements to eliminate subsequent solutions not meeting the joint travel requirements.

21. The computer storage medium of claim 14, wherein identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query comprises at least one of:

receiving the selection of the at least one solution from a user;

or

making the selection of the at least one solution by a computer.

22. The computer storage medium of claim 16, wherein the operations further comprise:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query; and

determining a selection of at least one other solution from the first plurality of solutions received from the travel planning system in response to the first query.

23. The computer storage medium of claim 16, wherein the operations further comprise:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query;

reordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the reordered plurality of passenger groups.

24. The computer storage medium of claim 23, wherein the operations further comprise:

constructing a revised first query for a first passenger group of the reordered plurality of passenger groups, the revised first query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival;

receiving a revised first plurality of solutions from the travel planning system, the solutions comprising sets of flights based on the revised first query; and

identifying a selection of at least one solution from the revised first plurality of solutions received from the travel planning system in response to the revised first query.

25. The computer storage medium of claim 24, wherein the operations further comprise:

deriving a constraint on the at least one attribute based on the identified selection of at least one solution from the revised plurality of solutions; and

constructing a third query for a third passenger group different from the revised first passenger group, the third query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival.

26. The computer storage medium of claim 16, wherein the operations further comprise:

identifying a selection of at least one solution from the second plurality of solutions received from the travel planning system in response to the second query; and

providing information related to the first plurality of solutions and second plurality of solutions.

27. A system of one or more computers configured to perform operations comprising:

receiving a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for one or more of an origin, a destination, a date of departure, a time of departure, a date of arrival, or a time of arrival, and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query;

deriving a constraint on the at least one attribute based on the identified selection of at least one solution;

constructing a second query for a second passenger group, the second query comprising attributes for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival, the second query comprising the constrained at least one attribute, and at least one attribute for the joint travel preference or requirement; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

28. The system of claim 27, wherein the solutions further comprise fares associated with the sets of flights.

29. The system of claim 27, wherein the operations further comprise:

receiving a second plurality of solutions from the same or a different travel planning system, the second plurality of solutions comprising sets of flights and fares associated with the flights based on the second query.

30. The system of claim 27, wherein the operations further comprise sending the first query to the travel planning system for processing the first query by the travel planning system to derive the plurality of solutions.

31. The system of claim 27, wherein the operations further comprise:

ordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the passenger group with the most number of constraints.

32. The system of claim 31, wherein the operations further comprise:

adding constraints to queries for the subsequent passenger group based on the identified selection of at least one solution and one or more of joint travel requirements and preferences with at least one of the joint travel requirements and preferences including sharing a common segment of travel.

33. The system of claim 32, wherein the operations further comprise filtering sets of subsequent solutions for subsequent particular passenger groups according to the joint travel requirements to eliminate subsequent solutions not meeting the joint travel requirements.

34. The system of claim 27, wherein identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query comprises at least one of:

receiving the selection of the at least one solution from a user;

or

making the selection of the at least one solution by a computer.

35. The system of claim 29, wherein the operations further comprise:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query; and

determining a selection of at least one other solution from the first plurality of solutions received from the travel planning system in response to the first query.

36. The system of claim 29, wherein the operations further comprise:

prior to receiving the second plurality of solutions from the same or a different travel planning system, determining that there are insufficient solutions in the second plurality of solutions based on the second query;

reordering the plurality of passenger groups according to a determined number of constraints per passenger group; and

selecting the first passenger group based on the reordered plurality of passenger groups.

37. The system of claim 36, wherein the operations further comprise:

constructing a revised first query for a first passenger group of the reordered plurality of passenger groups, the revised first query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival;

receiving a revised first plurality of solutions from the travel planning system, the solutions comprising sets of flights based on the revised first query; and

identifying a selection of at least one solution from the revised first plurality of solutions received from the travel planning system in response to the revised first query.

38. The system of claim 37, wherein the operations further comprise:

deriving a constraint on the at least one attribute based on the identified selection of at least one solution from the revised plurality of solutions; and

constructing a third query for a third passenger group different from the revised first passenger group, the third query comprising at least one attribute for one or more of the origin, the destination, the date of departure, the time of departure, the date of arrival, or the time of arrival.

39. The system of claim 29, wherein the operations further comprise:

identifying a selection of at least one solution from the second plurality of solutions received from the travel planning system in response to the second query; and

providing information related to the first plurality of solutions and second plurality of solutions.