Multi-passenger multi-route travel planning

• US 20070168238A1
• 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., Marcken, Carl G. de
• Granted Patent: US 8,589,195 B2
• Time in Patent Office: Days
• 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

Techniques for processing a multiple passenger, multiple route query are disclosed. The techniques include a travel planning system that searches for airline tickets in response to queries and a server that sends multiple, individual queries to the travel planning system and combines solutions received from execution of the multiple individual queries by the travel planning system, producing answers for the multiple passenger, multiple route query.

Claims

1. A system for processing a multiple passenger, multiple route query, the system comprising:

a travel planning system that searches for airline tickets in response to queries and that finds answers that satisfy the queries, with the queries involving different passengers taking different, but related routes.

2. The system of claim 1 wherein the multiple passenger, multiple route query relates to the joint planning of trips for multiple passengers groups, where the passenger groups share portions of different but co-dependent routes.

3. The system of claim 1 wherein a client sends the multiple passenger, multiple route query directly to the travel planning system.

4. The system of claim 1 comprising:

a multiple passenger, multiple route process that processes multiple passenger, multiple route queries and produces multiple passenger, multiple route answers.

5. The system of claim 1 further comprising:

a server that sends multiple, individual queries to the travel planning system and combines solutions received from execution of the multiple individual queries by the travel planning system, producing answers for the multiple passenger, multiple route query.

6. The system of claim 5 wherein a client sends the multiple passenger, multiple route query to the server.

7. The system of claim 4 wherein the multiple passenger, multiple route process combines the individual solutions into potential joint solutions by:

a process to determine a cross product of sets of individual solutions

8. The system of claim 4 wherein the multiple passenger, multiple route process combines the individual solutions into potential joint solutions by:

a filter to filter the individual solutions by joint travel requirements.

9. The system of claim 4 wherein multiple passenger, multiple route process combines the individual solutions into potential joint solutions, and the system further comprises:

a process to produce a factored representation of the set of joint solutions.

10. The system of claim 9 wherein the factored representation of the set of joint solutions is an “

and/or Directed Acyclic Graph.

11. The system of claim 9 wherein solutions are enumerated from the factored representation.

12. The system of claim 9 wherein solutions are enumerated from the factored representation in an order determined by a joint travel preference function.

13. The system of claim 4 wherein the multiple passenger, multiple route process groups individual solutions from an individual query into sets of individual solutions for evaluating the individual solutions with respect to the joint travel requirements.

14. The system of claim 1 wherein the individual query for each passenger group comprises a set of joint travel requirements.

15. The system of claim 1 wherein the individual query for each passenger group is expressed as a set of information for each passenger group, the set comprising a set of joint travel requirements and a specification of how to choose among solutions received from the travel planning system.

16. A system for processing a multiple passenger, multiple route query, the system comprising:

a travel planning system that searches for airline tickets in response to queries; and

a server that sends multiple, individual queries to the travel planning system and combines solutions received from execution of the multiple individual queries by the travel planning system, producing answers for the multiple passenger, multiple route query.

17. The system of claim 16 wherein the travel planning system comprises a scheduling process and a faring process that produces travel solutions comprising priced itineraries.

18. The system of claim 16 wherein a client sends a multiple passenger, multiple route query to the server and wherein the server produces the multiple individual queries from the multiple passenger, multiple route query.

19. The system of claim 16 wherein the server combines the individual solutions into potential joint solutions by:

determining a cross product of sets of individual solutions.

20. The system of claim 16 wherein the server combines the individual solutions into potential joint solutions by:

filtering the individual solutions by joint travel requirements.

21. The system of claim 16 wherein the server combines the individual solutions into potential joint solutions, and the system further comprises:

a process to produce a factored representation of the set of joint solutions.

22. The system of claim 21 wherein solutions are enumerated from the factored representation.

23. The system of claim 22 wherein solutions are enumerated from the factored representation in an order determined by a joint travel preference function.

24. The system of claim 16 wherein the multiple passenger, multiple route query includes a set of information for each passenger group, the set comprising an individual query and a set of joint travel requirements.

25. The system of claim 16 wherein the multiple passenger, multiple route query includes a set of information for each passenger group, the set comprising an individual query, a set of joint travel requirements, and a specification of how to choose among solutions received from the travel planning system.

26. A method for processing a multiple passenger, multiple route query, the method comprising:

searching for airline tickets in response to queries; and

determining answers that satisfy the queries, with the queries involving different passengers taking different, but related routes.

27. The method of claim 26 wherein the multiple passenger, multiple route query relates to the joint planning of trips for multiple passengers groups, where the passenger groups share portions of different but co-dependent routes.

28. The method of claim 26 further comprising:

sending the multiple passenger, multiple route query by a client directly to a travel planning system.

29. The method of claim 26 further comprising:

sending multiple, individual queries to a travel planning system by a server; and

combining, on the server, solutions received from execution of the multiple individual queries by the travel planning system, to provide the answers for the multiple passenger, multiple route query.

30. The method of claim 29 further comprising:

sending the multiple passenger, multiple route query to the server from a client.

31. The method of claim 29 wherein combining comprises:

determining a cross product of sets of individual solutions.

32. The method of claim 29 wherein combining comprises:

filtering the individual solutions by joint travel requirements.

33. The method of claim 29 wherein combining comprises:

producing a factored representation of the set of joint solutions.

34. A method comprising:

searching for airline tickets in a travel planning system in response to queries; and

sending by a server multiple, individual queries to the travel planning system; and

combines by the server solutions received from execution of the multiple individual queries by the travel planning system to provide answers for the multiple passenger, multiple route query.

35. The method of claim 34 wherein the travel planning system comprises:

scheduling and faring to produce travel solutions comprising priced itineraries.

36. The method of claim 34 further comprising:

sending a multiple passenger, multiple route query to the server from a client.