Incremental searching in multi-passenger multi-route travel planning

• US 8,005,696 B2
• Filed: 01/18/2006
• Issued: 08/23/2011
• Est. Priority Date: 01/18/2006
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Boyan, Justin A., de Marcken, Carl G.
• Primary Examiner(s): Hayes; John W
• Assistant Examiner(s): FLYNN, KEVIN H
• Application Number:
  US11/335,170
• Publication Number:
  US 20070174239A1
• Time in Patent Office: 2,043 Days
• Field of Search: 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 method for providing multiple routes for multiple passenger groups, the method executed over a computer network, the method comprising:

constructing, by a computer, an individual query for a first passenger group, the individual query having query attributes that are used to find travel solutions, the query attributes including values for origin, destination, number of travelers, date of departure, and time of departure;

sending by the computer the individual query to a travel planning system;

receiving, by the computer, solutions comprising sets of flights and fares usable with the flights from processing of the individual query;

selecting, a single, individual solution from the solutions received by the computer from processing of the individual query;

deriving, by the computer, constraints on values of at least one of the query attributes from the single individual solution to apply to a subsequent individual query for a subsequent, different passenger group;

adding by the computer constraints to subsequent individual queries for the subsequent passenger group based on previously selected individual solutions 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; and

constructing, by the computer, the subsequent individual query for the subsequent passenger group, the subsequent individual query for the subsequent passenger group having values for query attributes determined based at least in part on the constraints on the values derived from the single individual solution from the first passenger group.

2. The method of claim 1 further comprising:

ordering passenger groups, for each subsequent passenger group, according to a determined number of constraints per passenger group to select the individual query corresponding to the passenger group with the most constraints.

3. The method of claim 2 further comprising:

filtering by the computer sets of subsequent individual solutions for subsequent particular passenger groups according to the joint travel requirements to eliminate those subsequent individual solutions not meeting the joint travel requirements.

4. The method of claim 1 further comprising:

selecting the individual solution by a user.

5. The method of claim 1 further comprising:

selecting by the computer the individual solution.

6. A computer-implemented method for providing multiple routes for multiple passengers, the method executed over a computer network, the method comprising:

sending, by a computer, query to a travel planning system for a first passenger group selected from a plurality of passenger groups, the query having query attributes that are used to find travel solutions, the query attributes including values for origin, destination, number of travelers, date of departure, and time of departure;

receiving by the computer a set of solutions for the first passenger group from the travel planning system

producing, by the computer, a table of individual solutions comprising sets of flights and fares usable with the flights for the first passenger group;

deriving, by the computer, a set of constraints on values of at least one of the query attributes, based on individual solutions in the table of individual solutions and joint travel requirements, with at least one of the joint travel requirements including sharing a common segment of travel for an individual query for a second passenger group;

constructing, by the computer, a modified individual query for the second passenger group according to the set of constraints the modified individual query for the second passenger group having values for query attributes determined based at least in part on the constraints on the values derived from the single individual solution from the first passenger group; and

sending, from the computer, the modified individual query for the second passenger group to a travel planning system.

7. The method of claim 6 further comprising:

sorting by the computer passenger groups according to a number of constraints on travel with the first passenger group being the group with the most determined constraints.

8. The method of claim 6 further comprising:

ordering passenger groups according to a determined number of constraints per passenger group to select the individual query corresponding to the passenger group with the most constraints.

9. The method of claim 6 wherein the set of constraints does not reflect all of the constraints imposed by the individual solutions.

10. The method of claim 6 further comprising:

selecting an individual solution from the solutions returned from the travel planning system.

11. The method of claim 10 wherein the individual solution is selected by a user.

12. The method of claim 10 further comprising:

selecting, by the computer, the individual solution.

13. A computer program product tangibly embodied on a computer readable storage device for processing queries involving multiple routes for multiple passengers, the computer program product comprising instructions for causing a computer to:

construct an individual query for a first passenger group the individual query having query attributes that are used to find travel solutions, the query attributes including values for origin, destination, number of travelers, date of departure, and time of departure;

send the individual query to a travel planning system;

receive solutions comprising sets of flights and fares usable with the flights from processing of the individual query;

select a single, one of the received individual solutions; and

derive constraints on values of at least one of the query attributes from the single individual solution to apply to a subsequent individual query for a subsequent, different passenger group;

add the constraints to the subsequent individual query based on the previously selected individual 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; and

construct the subsequent individual query for the subsequent passenger group, the subsequent individual for the subsequent passenger group having values for query attributes determined based at least in part on the constraints on the values derived from the single individual solution from the first passenger group.

14. The computer program product of claim 13 further comprising instructions to:

order passenger groups according to a determined number of constraints per passenger group to select the individual query corresponding to the passenger group with the most constraints.

15. The computer program product of claim 13 further comprising instructions to:

order passenger groups according to a determined number of constraints per passenger group to select the individual query corresponding to the passenger group with the most constraints; and

filter sets of subsequent individual solutions for subsequent particular passenger groups according to joint travel requirements to eliminate those subsequent individual solutions not meeting the joint travel requirements.

16. The computer program product of claim 13 further comprising instructions to:

receive the selection of the individual solution for a passenger group from a user.

17. The computer program product of claim 13 further comprising instructions to:

cause the computer to calculate a selection of the individual solution.

18. A computer program product tangibly embodied on a computer readable storage device for providing multiple routes for multiple passengers, the computer program product comprising instructions for causing a computer to:

send an individual query to a travel planning system for a first passenger group selected from a plurality of passenger groups, the query having query attributes that are used to find travel solutions, the query attributes including values for origin, destination, number of travelers, date of departure, and time of departure;

receive a set of solutions from the travel planning system in response to the query;

produce a table of individual solutions comprising sets of flights and fares usable with the flights for the first passenger group;

derive a set of constraints on values of at least one of the query attributes, based on individual solutions in the table of individual solutions and joint travel requirements, for an individual query for a second passenger group with at least one of the ioint travel requirements including sharing a common segment of travel for an individual query for a second passenger group;

construct a modified individual query for the second passenger group according to the set of constraints the modified individual query for the second passenger group having values for query attributes determined based at least in part on the constraints on the values derived from the single individual solution from the first passenger group; and

send the modified individual query for the second passenger group to a travel planning system.

19. The computer program product of claim 18 further comprising instructions to:

order passenger groups according to constraints on travel, with the first passenger group chosen as the group with the most constraints.

20. The computer program product of claim 18 further comprising instructions to:

filter sets of subsequent individual solutions for subsequent particular passenger groups according to joint travel requirements to eliminate those subsequent individual solutions not meeting the joint travel requirements.

21. The computer program product of claim 18 further comprising instructions to:

select an individual solution from the solutions returned from the travel planning system.

22. The computer program product of claim 21 further comprising instructions to;

receive the individual solution as selected by a user.

23. The computer program product of claim 21 further comprising instructions to:

cause the computer to select the individual solution.