Multi-passenger multi-route travel planning

• US 8,595,039 B2
• Filed: 04/04/2011
• Issued: 11/26/2013
• 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): Chen, George
• Application Number:
  US13/079,365
• Publication Number:
  US 20110213833A1
• Time in Patent Office: 967 Days
• Field of Search: 705/1.1, 705 5- 6, 705 711- 736, 705/26.1, 705/400, 701/1
• US Class Current: 705/6
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• 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

Multiple passenger multiple route travel queries are solved using travel planning systems that receive multiple, individual queries to produce individual solutions that meet joint travel requirements. The multiple, individual sub-queries are merged to produce joint solutions for the passenger groups.

Claims

1. A method for determining travel solutions that involve multiple routes for multiple passenger groups for a trip, the method comprising:

receiving, by a computer system including one or more computers, separate travel constraints for each of a plurality of different passenger groups and a set of joint travel requirements applicable to all of the passenger groups;

sending, by the computer system, a first individual query for each of the plurality of different passenger groups, each of the first individual queries including travel parameters of an origin, a destination and travel date information,

receiving, by the computer system, for each of the plurality of different passenger groups, first sets of individual solutions that meet the travel parameters of the first individual query;

merging individual solutions from the first sets of individual solutions and determining that an insufficient number of joint solutions for the passenger groups satisfy the joint travel requirements;

selecting, by the computer system, an evaluation aspect of a trip other than an origin, a destination, or travel date information, upon which to evaluate the individual solutions, and selecting a value for the evaluation aspect;

evaluating, by the computer system, a combined value of each of the first sets of individual solutions, with regard to the evaluation aspect, obtained for each of a plurality of combinations of the first sets of individual solutions, to identify a combination of individual solutions having a combined value closest to the selected value for the evaluation aspect;

for each of a plurality of the passenger groups, creating a second individual query comprising the travel parameters of the first individual query and a parameter having a value for the evaluation aspect consistent with the value for the evaluation aspect of the individual solution for the passenger group in the identified combination of individual solutions; and

sending, by the computer system, the second individual query for each of the plurality of different passenger groups; and

receiving, for each of the plurality of different passenger groups, second sets of individual solutions that meet the travel parameters of the second individual query.

2. The method of claim 1 wherein each of the first sets of individual solutions for each of the different passenger groups comprises a list of individual solutions and further comprising merging the lists of individual solutions.

3. The method of claim 2 wherein merging the lists of individual solutions comprises:

producing an index of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements or preferences; and

combining the individual solutions according to the index.

4. The method of claim 3 further comprising:

constructing a factored representation of joint solutions by building a representation of possible combinations of individual solution indices; and

linking individual indices to those solutions with the index.

5. The method of claim 4 wherein the factored representation is an AND/OR graph that represents a set of joint solutions, with terminal elements of the AND/OR graph being individual solutions.

6. The method of claim 5 further comprising:

applying a value function that assigns values to the joint solutions that reflect cross-passenger-group penalties.

7. The method of claim 5 further comprising:

applying a first value function that assigns values to the individual solutions that reflect cross-passenger-group penalties;

applying a second value function that assigns values to the individual solutions that reflect a cost of that solution without regard to joint travel preferences.

8. The method of claim 2 wherein each of the lists of individual solutions is received and merged by:

producing a cross-product of the lists of individual solutions to provide a list of potential joint solutions; and

filtering the list of potential joint solutions to eliminate potential joint solutions from the list of potential joint solutions that violate joint travel requirements.

9. The method of claim 1 further comprising:

receiving, by the computer system, second sets of individual solutions to each of the second individual queries.

10. The method of claim 9 further comprising:

merging individual solutions from the second sets of individual solutions to identify any joint solutions for the passenger groups that satisfy the joint travel requirements; and

providing instructions causing presentation of the joint solutions for the passenger groups that satisfy the joint travel requirements.

11. The method of claim 1 further comprising:

sending the first individual query for each of the plurality of different passenger groups to a travel planning system for processing of the queries, the travel planning system including a scheduler process and a faring process that produces the first sets of individual solutions for each of the plurality of different passenger groups.

12. The method of claim 1 further comprising:

increasing seat availability requirements in individual queries to account for a possibility of passengers from other individual queries using the same flights.

13. A computer program product tangibly embodied on a non-transitory computer readable storage device, the computer program product for determining travel solutions that involve multiple routes for multiple passenger groups for a trip, the computer program product comprising instructions for causing one or more computers to:

Receive separate travel constraints for each of a plurality of different passenger groups and a set of joint travel requirements applicable to all of the passenger groups;

Send a first individual query for each of the plurality of different passenger groups, each of the first individual queries including travel parameters of an origin, a destination and travel date information,

Receive, for each of the plurality of different passenger groups, first sets of individual solutions that meet the travel parameters of the first individual query;

Merge individual solutions from the first sets of individual solutions and determine that an insufficient number of joint solutions for the passenger groups satisfy the joint travel requirements;

Select an evaluation aspect of a trip other than an origin, a destination, or travel date information, upon which to evaluate the individual solutions, and selecting a value for the evaluation aspect;

Evaluate a combined value of each of the first sets of individual solutions, with regard to the evaluation aspect, obtained for each of a plurality of combinations of the first sets of individual solutions, to identify a combination of individual solutions having a combined value closest to the selected value for the evaluation aspect;

For each of a plurality of the passenger groups, create a second individual query comprising the travel parameters of the first individual query and a parameter having a value for the evaluation aspect consistent with the value for the evaluation aspect of the individual solution for the passenger group in the identified combination of individual solutions; and

Send the second individual query for each of the plurality of different passenger groups; and

Receive, for each of the plurality of different passenger groups, second sets of individual solutions that meet the travel parameters of the second individual query.

14. The computer program product of claim 13 wherein each of the first sets of individual solutions for each of the different passenger groups comprise a list of individual solutions and further comprising instructions to merge the lists of individual solutions.

15. The computer program product of claim 14 wherein merging the lists of individual solutions further comprises instructions to:

produce an index of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements or preferences; and

combine the individual solutions according to the index.

16. The computer program product of claim 15 wherein constructing a factored representation further comprises instructions to:

construct a factored representation of joint solutions by building a representation of possible combinations of individual solution indices; and

link individual indices to those solutions with the index.

17. The computer program product of claim 16 wherein constructing a factored representation further comprises instructions to:

construct an AND/OR graph that represents a set of joint solutions, with terminal elements of the AND/OR graph being individual solutions.

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

apply a value function that assigns values to the joint solutions that reflect cross-passenger-group penalties.

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

apply a first value function that assigns values to the individual solutions that reflect cross-passenger-group penalties;

apply a second value function that assigns values to the individual solutions that reflect a cost of that solution without regard to joint travel preferences.

20. The computer program product of claim 14 wherein each of the lists of individual solutions is received and merged, and further comprises instructions to:

produce a cross-product of the lists of individual solutions to provide a list of potential joint solutions; and

filter the list of potential joint solutions to eliminate potential joint solutions from the list of potential joint solutions that violate joint travel requirements.

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

receive second sets of individual solutions to each of the second individual queries.

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

merge individual solutions from the second sets of individual solutions to identify any joint solutions for the passenger groups that satisfy the joint travel requirements; and

provide instructions causing presentation of the joint solutions for the passenger groups that satisfy the joint travel requirements.

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

send the first individual query for each of the plurality of different passenger groups to a travel planning system for processing of the queries, the travel planning system including a scheduler process and a faring process that produces the first sets of individual solutions for each of the plurality of different passenger groups.

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

increase seat availability requirements in individual queries sent to a scheduler to account for a possibility of passengers from other individual queries using the same flights.

25. A system, comprising:

a computer system comprising a processor and memory;

a computer storage device storing a computer program product for determining travel solutions that involve multiple routes for multiple passenger groups, the computer program product comprising instructions for causing the processor to;

receive separate travel constraints for each of a plurality of different passenger groups and a set of joint travel requirements applicable to all of the passenger groups;

send a first individual query for each of the plurality of different passenger groups, each of the first individual queries including travel parameters of an origin, a destination and travel date information;

receive, for each of the plurality of different passenger groups, first sets of individual solutions that meet the travel parameters of the first individual query;

merge individual solutions from the first sets of individual solutions and determine that an insufficient number of joint solutions for the passenger groups satisfy the joint travel requirements;

select an evaluation aspect of a trip other than an origin, a destination, or travel date information, upon which to evaluate the individual solutions, and select a value for the evaluation aspect;

evaluate a combined value of each of the first sets of individual solutions, with regard to the evaluation aspect, obtained for each of a plurality of combinations of the first sets of individual solutions, to identify a combination of individual solutions having a combined value closest to the selected value for the evaluation aspect;

for each of a plurality of the passenger groups, creating a second individual query comprising the travel parameters of the first individual query and a parameter having a value for the evaluation aspect consistent with the value for the evaluation aspect of the individual solution for the passenger group in the identified combination of individual solutions; and

send the second individual query for each of the plurality of different passenger groups; and

receive, for each of the plurality of different passenger groups, second sets of individual solutions that meet the travel parameters of the second individual query.

26. The system of claim 25 wherein each of the first sets of individual solutions for each of the different passenger groups comprise a list of individual solutions and the lists of individual solutions are merged.

27. The system of claim 26 wherein the computer program product further comprises instructions to:

produce an index of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements or preferences; and

combine the individual solutions according to the index.

28. The system of claim 27 wherein the computer program product further comprises instructions to:

construct a factored representation of joint solutions by building a representation of possible combinations of individual solution indices; and

link individual indices to those solutions with the index.

29. The system of claim 28 wherein the factored representation is an AND/OR graph that represents a set of joint solutions, with terminal elements of the AND/OR graph being individual solutions.

30. The system of claim 29 wherein the computer program product further comprises instructions to:

apply a value function that assigns values to the joint solutions that reflect cross-passenger-group penalties.

31. The system of claim 29 wherein the computer program product further comprises instructions to:

apply a first value function that assigns values to the individual solutions that reflect cross-passenger-group penalties;

apply a second value function that assigns values to the individual solutions that reflect a cost of that solution without regard to joint travel preferences.

32. The system of claim 26 wherein the computer program product further comprises instructions to:

produce a cross-product of the lists of individual solutions to provide a list of potential joint solutions; and

filter the list of potential joint solutions to eliminate potential joint solutions from the list of potential joint solutions that violate joint travel requirements.

33. The system of claim 25 wherein the computer program product further comprises instructions to:

receive second sets of individual solutions to each of the second individual queries.

34. The system of claim 33 wherein the computer program product further comprises instructions to:

merge individual solutions from the second sets of individual solutions to identify any joint solutions for the passenger groups that satisfy the joint travel requirements; and

provide instructions causing presentation of the joint solutions for the passenger groups that satisfy the joint travel requirements.

35. The system of claim 33 wherein the computer program product further comprises instructions to:

send the first individual query for each of the plurality of different passenger groups to a travel planning system for processing of the queries, the travel planning system including a scheduler process and a faring process that produces the first sets of individual solutions for each of the plurality of different passenger groups.

36. The system of claim 25 wherein the computer program product further comprises instructions to:

increase seat availability requirements in individual queries sent to a scheduler to account for a possibility of passengers from other individual queries using the same flights.