Multi-Passenger Multi-Route Travel Planning

• US 20110213833A1
• Filed: 04/04/2011
• Published: 09/01/2011
• Est. Priority Date: 01/18/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Boyan, Justin A., de Marcken, Carl G.
• Granted Patent: US 8,595,039 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• 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, the method executed over a computer network, the method comprising:

sending by a computer to one or more computer systems executing a scheduler process, joint travel requirements and multiple, individual queries the multiple individual queries including origin, destination and travel data and time information to produce individual solutions that meet the joint travel requirements;

merging results from the multiple, individual queries to produce joint solutions for the passenger groups that satisfy the joint travel requirements;

displaying the joint solutions.

2. The method of claim 1 further comprising:

sending a multiple passenger, multiple route (MPMR) query to a server that processes the MPMR query to produce the multiple individual queries.

3. The method of claim 2 further comprising:

sending from a client system the multiple passenger, multiple route query for a plurality of passenger groups to a system.

4. The method of claim 3 wherein the client system sends the MPMR query to a server that processes the MPMR query to produce the multiple individual queries, and the method further comprises:

sending the multiple individual queries to a travel planning system for processing of the queries, the travel planning system including the scheduler process and a faring process that produces the results.

5. The method of claim 3 wherein the client system sends the MPMR query to a travel planning system, and the method further comprises:

processing the multiple individual queries in the travel planning system.

6. The method of claim 3 wherein the MPMR query is a query that includes for each passenger group, a set of fields for entering the origin, destination and travel data and time information.

7. The method of claim 1 wherein each query is processed to produce a corresponding list of individual solutions for each passenger group.

8. The method of claim 7 wherein each of the lists is received, and merging results comprises:

producing a cross-product of the lists of individual solution 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 5 wherein merging results comprises:

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

10. The method of claim 9 wherein merging results further comprises:

combining the individual solutions according to the indices.

17. The method of claim 1 wherein seat availability requirements in individual queries are increased to account for possibility of passengers from other individual queries using the same flights.

18. The method of claim 1 further comprising:

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

11. The method of claim I further comprising:

constructing a factored representation of joint solutions to represent the joint solutions.

12. The method of claim 11 wherein constructing a factored representation comprises:

building a representation of possible combinations of individual solution indices; and

linking individual indices to those solutions with the index.

13. The method of claim 11 wherein the factored representation is an AND/OR graph that compactly represents the set of joint solutions.

14. The method of claim 13 further comprising:

enumerating joint solutions from the AND/OR graph with terminal elements of the AND/OR graph being individual solutions.

15. The method of claim 14 further comprising:

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

16. The method of claim 14 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 the cost of that solution without regard to joint travel preferences.

19. A computer program product tangibly embodied on a computer readable storage device, the computer program product for determining travel solutions that involve multiple routes for multiple passenger groups, the computer program product comprising instructions for causing a computer to:

send to a scheduler, joint travel requirements and multiple, individual queries the multiple individual queries including origin, destination and travel data and time information to produce individual solutions that meet the joint travel requirements;

merge results from the multiple, individual queries to produce joint solutions for the passenger groups that satisfy the joint travel requirements;

display the joint solutions.

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

send a multiple passenger, multiple route (MPMR) query to a server that processes the MPMR query to produce the multiple individual queries.

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

process each query and produce a list of individual solutions for each passenger group.

22. The computer program product of claim 19 wherein merging further comprising instructions to:

produce a cross-product of the lists of individual solution 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.

23. The computer program product of claim 19 wherein merging further comprising instructions to:

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

24. The computer program product of claim 23 wherein merging further comprising instructions to:

combine the individual solutions according to the indices.

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

construct a factored representation of joint solutions to represent the joint solutions.

26. The computer program product of claim 25 wherein constructing a factored representation further comprising instructions to:

build a representation of possible combinations of individual solution indices; and

link individual indices to those solutions with e index.

27. The computer program product of claim 25 wherein the factored representation is an AND/OR graph that compactly represents the set of joint solutions.

28. The computer program product of claim 27 further comprising instructions to:

enumerate joint solutions from the AND/OR graph with terminal elements of the AND/OR graph being individual solutions.

29. The computer program product of claim 25 further comprising instructions to:

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

30. The computer program product of claim 25 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 the cost of that solution without regard to joint travel preferences.

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

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

32. 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;

send to a scheduler, joint travel requirements and multiple, individual queries the multiple individual queries including origin, destination and travel data and time information to produce individual solutions that meet the joint travel requirements;

merge results from the multiple, individual queries to produce joint solutions for the passenger groups that satisfy the joint travel requirements;

display the joint solutions.

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

process each query and produce a list of individual solutions for each passenger group.

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

produce a cross-product of the lists of individual solution 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.

35. The system of claim 33 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.

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

combine the individual solutions according to the indices.