Multi-passenger multi-route travel planning

• US 20070168236A1
• Filed: 01/18/2006
• Published: 07/19/2007
• Est. Priority Date: 01/18/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Boyan, Justin A., de Marcken, Carl G.
• Granted Patent: US 8,185,418 B2
• Time in Patent Office: Days
• US Class Current: 705/5
• 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
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G07B 15/02 taking into account a variable factor such as distance or time, e.g. for passenger transport, parking systems or car rental systems G07B15/06 takes precedence; taximeters G07B13/00; parking meters per se G07F17/24; car rental systems per se G07B15/00

Abstract

Multiple passenger multiple route techniques are disclosed including sending independent queries to a travel planning system for each of a plurality of passenger groups and receiving lists of individual solutions appropriate for the passenger groups in response to the independent queries. The lists are combined to provide joint solutions according to joint travel requirements/preferences and if there are not a sufficient number of joint solutions, the individual queries are resent with constraints on features of the resent individual queries.

Claims

1. A method, comprising:

sending independent queries to a travel planning system for each of a plurality of passenger groups;

receiving lists of individual solutions appropriate for the passenger groups in response to the independent queries;

combining the lists to provide joint solutions according to joint travel requirements/preferences;

determining if there are a sufficient number of joint solutions; and

, if there are not a sufficient number of joint solutions,

resending individual queries with constraints on features of the resent individual queries.

2. The method of claim 1 wherein resending queries further comprises:

selecting a property of an individual solution for a passenger group;

deriving constraints implied by the property on the remaining passenger groups using the joint travel requirements/preferences;

adding the derived constraints to individual queries for other passenger groups; and

resending the individual queries with the constraints.

3. The method of claim 2 wherein the property is related to a sequence of flights for the individual solution that will be shared with other passengers.

4. The method of claim 2 wherein the derived constraints are based on a sequence of flights selected for other passenger groups.

5. The method of claim 1 wherein if there are not sufficient joint solutions, the method further comprises:

examining joint travel requirements to find the smallest subset of joint travel requirements that cannot be satisfied.

6. The method of claim 1 wherein if there are not sufficient joint solutions, the method further comprises:

examining joint travel requirements to find the smallest subset of joint travel requirements that cannot be satisfied; and

determining the passenger group whose individual solutions exhibit the least diversity with respect to the subset of joint travel requirements.

7. The method of claim 1 further comprising:

modifying the individual queries to produce constrained individual queries constrained in accordance with the subset of joint travel requirements.

8. The method of claim 4 further comprising:

re-posing the constrained queries based on the requirements.

9. The method of claim 1 wherein examining joint travel requirements further comprises:

constructing a factored representation of the individual and joint solutions; and

choosing a passenger group whose individual solutions has the fewest number of sub-indices for a subset of unsatisfied joint travel requirements.

10. The method of claim 1 further comprising:

sending from client systems a multiple passenger, multiple route query;

receiving the query and processing the query to provide the independent queries to the travel planning system for each of the plurality of passenger groups.

11. A computer program product residing on a computer readable medium, for producing multiple routes for muliptel groups of passengers, the computer program product comprising instructions for causing a computer to:

send independent queries to a travel planning system for each of a plurality of passenger groups;

receive lists of individual solutions appropriate for the passenger groups in response to the independent queries;

combine the lists to provide joint solutions according to joint travel requirements/preferences;

determine if there are a sufficient number of joint solutions; and

, if there are a sufficient number of joint solutions,

return the joint solutions.

12. The computer program product of claim 11 wherein the computer program product further comprises instructions to:

select a property of an individual solution for a passenger group if there are not sufficient joint solutions;

derive constraints implied by the property on the remaining passenger groups using the joint travel requirements/preferences;

add the derived constraints to individual queries for other passenger groups; and

resend the individual queries with the constraints.

13. The computer program product of claim 12 wherein the property is related to a sequence of flights for the individual solution that will be shared with other passengers.

14. The computer program product of claim 12 wherein the derived constraints are based on a sequence of flights selected for other passenger groups.

15. The computer program product of claim 12 wherein the computer program product further comprises instructions to:

examine joint travel requirements to find the smallest subset of joint travel requirements that cannot be satisfied if there are not sufficient joint solutions.

16. The computer program product of claim 12 wherein the computer program product further comprises instructions to:

examine joint travel requirements to find the smallest subset of joint travel requirements that cannot be satisfied if there are not sufficient joint solutions; and

determine the passenger group whose individual solutions exhibit the least diversity with respect to the subset of joint travel requirements.

17. The computer program product of claim 12 wherein the computer program product further comprises instructions to:

modify the individual queries to produce constrained individual queries constrained in accordance with the subset of joint travel requirements.

18. The computer program product of claim 17 wherein the computer program product further comprises instructions to:

re-pose the constrained queries based on the requirements.

19. The computer program product of claim 12 wherein the computer program product further comprises instructions to:

construct a factored representation of the individual and joint solutions; and

choose a passenger group whose individual solutions has the fewest number of sub-indices for a subset of unsatisfied joint travel requirements.

20. The computer program product of claim 12 wherein the computer program product further comprises instructions to:

send from client systems a multiple passenger, multiple route query;

receive the query and processing the query to provide the independent queries to the travel planning system for each of the plurality of passenger groups.