Multi-passenger multi-route travel planning through common locations

• US 8,265,966 B2
• Filed: 08/19/2011
• Issued: 09/11/2012
• 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): FLYNN, KEVIN H
• Application Number:
  US13/213,224
• Publication Number:
  US 20120059740A1
• Time in Patent Office: 389 Days
• Field of Search: 705/5, 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
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• CPC Class Codes: G06Q 30/0641 Shopping interfaces
• CPC Class Codes: G06Q 50/14 Travel agencies

Abstract

Determining multiple routes for multiple passenger groups, includes sending to a scheduler, multiple individual queries with a bias to produce individual solutions that meet joint travel requirements, merging results from the multiple individual queries to produce joint solutions for the passenger groups and returning the joint solutions.

Claims

1. A computer-implemented method comprising:

receiving, by a computer system including one or more computers, a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing, by operation of a computer, a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for each of a first origin and a first destination and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying, by operation of a computer, a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query, the selected at least one solution comprising at least two of the first origin, the first destination, or a first intermediate location between the first origin and the first destination;

constructing, by operation of a computer, a second query for a second passenger group of the plurality of passenger groups, the second query comprising at least one attribute for each of a second origin and a second destination and at least one attribute for the joint travel preference or requirement;

receiving a second plurality of travel solutions from the travel planning system, the solutions comprising sets of flights based on the second query;

selecting, by operation of a computer, a predetermined number of solutions from the second plurality of travel solutions, each of which involves at least one passenger of the first passenger group traveling together with at least one passenger of the second passenger group on at least one segment of travel, each of the selected solutions further comprising at least one of;

(i) a second intermediate location between the second origin and second destination that matches the first origin, or (ii) a second intermediate location between the second origin and second destination that matches the first intermediate location when the selected at least one solution includes a first intermediate location; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

2. The method of claim 1, wherein the first and second destinations are identical.

3. The method of claim 1, wherein each of the selected solutions from the second plurality of travel solutions comprise a second intermediate location between the second origin and second destination that matches the first intermediate location, and the first and second origins are identical.

4. The method of claim 1, further comprising providing instructions causing display of the selected predetermined number of solutions for display.

5. The method of claim 1, further comprising:

sending the first query to a scheduler computer system that produces itineraries as combinations of flights, each individual travel planning query of the plurality of individual travel planning queries comprising an origin and a destination.

6. The method of claim 1, further comprising:

processing a multiple passenger, multiple route (MPMR) query for the plurality of passenger groups to produce a plurality of individual queries that comprise the first query.

7. The method of claim 6, wherein the MPMR query comprises a set of information for each passenger group of the plurality of passenger groups, the set comprising origin and destination information and a set of joint travel requirements, the set of joint travel requirements including a requirement to share flights for some portion of a trip segment, and further comprises at least one additional joint travel requirement selected from the group consisting of arriving or departing an airport at similar times;

sharing all flights for a segment of a trip;

sharing over-water or international flights for a segment of a trip;

sharing as much mileage or time as possible for a segment of a trip; and

sharing origin or destination airports or cities.

8. The method of claim 6, wherein a client system sends the MPMR query to a server that processes the MPMR query to produce the plurality of individual queries that comprise the first query.

9. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving, by a computer system including one or more computers, a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for each of a first origin and a first destination and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query, the selected at least one solution comprising at least two of the first origin, the first destination, or a first intermediate location between the first origin and the first destination;

constructing a second query for a second passenger group of the plurality of passenger groups, the second query comprising at least one attribute for each of a second origin and a second destination and at least one attribute for the joint travel preference or requirement;

receiving a second plurality of travel solutions from the travel planning system, the solutions comprising sets of flights based on the second query;

selecting a predetermined number of solutions from the second plurality of travel solutions, each of which involves at least one passenger of the first passenger group traveling together with at least one passenger of the second passenger group on at least one segment of travel, each of the selected solutions further comprising at least one of;

(i) a second intermediate location between the second origin and second destination that matches the first origin, or (ii) a second intermediate location between the second origin and second destination that matches the first intermediate location when the selected at least one solution includes a first intermediate location; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

10. The computer storage medium of claim 9, wherein the first and second destinations are identical.

11. The computer storage medium of claim 9, wherein each of the selected solutions from the second plurality of travel solutions comprise a second intermediate location between the second origin and second destination that matches the first intermediate location, and the first and second origins are identical.

12. The computer storage medium of claim 9, wherein the operations further comprise providing instructions causing display of the selected predetermined number of solutions for display.

13. The computer storage medium of claim 9, wherein the operations further comprise:

sending the first query to a scheduler computer system that produces itineraries as combinations of flights, each individual travel planning query of the plurality of individual travel planning queries comprising an origin and a destination.

14. The computer storage medium of claim 9, wherein the operations further comprise:

processing a multiple passenger, multiple route (MPMR) query for the plurality of passenger groups to produce a plurality of individual queries that comprise the first query.

15. The computer storage medium of claim 14, wherein the MPMR query comprises a set of information for each passenger group of the plurality of passenger groups, the set comprising origin and destination information and a set of joint travel requirements, the set of joint travel requirements including a requirement to share flights for some portion of a trip segment, and further comprises at least one additional joint travel requirement selected from the group consisting of arriving or departing an airport at similar times;

sharing all flights for a segment of a trip;

sharing over-water or international flights for a segment of a trip;

sharing as much mileage or time as possible for a segment of a trip; and

sharing origin or destination airports or cities.

16. The computer storage medium of claim 14, wherein a client system sends the MPMR query to a server that processes the MPMR query to produce the plurality of individual queries that comprise the first query.

17. A system of one or more computers configured to perform operations comprising:

receiving, by a computer system including one or more computers, a travel search request including travel preferences for each of a plurality of passenger groups, each passenger group having different members, traveling on multiple, different routes and at least one joint travel preference or requirement shared by each member of the plurality of passenger groups;

constructing a first query for a first passenger group of the plurality of passenger groups, the first query comprising at least one attribute for each of a first origin and a first destination and at least one attribute for the joint travel preference or requirement;

receiving a first plurality of travel solutions from a travel planning system, the solutions comprising sets of flights based on the first query;

identifying a selection of at least one solution from the first plurality of solutions received from the travel planning system in response to the first query, the selected at least one solution comprising at least two of the first origin, the first destination, or a first intermediate location between the first origin and the first destination;

constructing a second query for a second passenger group of the plurality of passenger groups, the second query comprising at least one attribute for each of a second origin and a second destination and at least one attribute for the joint travel preference or requirement;

receiving a second plurality of travel solutions from the travel planning system, the solutions comprising sets of flights based on the second query;

selecting a predetermined number of solutions from the second plurality of travel solutions, each of which involves at least one passenger of the first passenger group traveling together with at least one passenger of the second passenger group on at least one segment of travel, each of the selected solutions further comprising at least one of;

(i) a second intermediate location between the second origin and second destination that matches the first origin, or (ii) a second intermediate location between the second origin and second destination that matches the first intermediate location when the selected at least one solution includes a first intermediate location; and

returning information regarding travel solutions for each of the plurality of passenger groups in response to the travel search request.

18. The system of claim 17, wherein each of the selected solutions from the second plurality of travel solutions comprise a second intermediate location between the second origin and second destination that matches the first intermediate location, and the first and second destinations are identical.

19. The system of claim 17, wherein the first and second origins are identical.

20. The system of claim 17, wherein the operations further comprise providing instructions causing display of the selected predetermined number of solutions for display.

21. The system of claim 17, wherein the operations further comprise:

sending the first query to a scheduler computer system that produces itineraries as combinations of flights, each individual travel planning query of the plurality of individual travel planning queries comprising an origin and a destination.

22. The system of claim 17, wherein the operations further comprise:

processing a multiple passenger, multiple route (MPMR) query for the plurality of passenger groups to produce a plurality of individual queries that comprise the first query.

23. The system of claim 22, wherein the MPMR query comprises a set of information for each passenger group of the plurality of passenger groups, the set comprising origin and destination information and a set of joint travel requirements, the set of joint travel requirements including a requirement to share flights for some portion of a trip segment, and further comprises at least one additional joint travel requirement selected from the group consisting of arriving or departing an airport at similar times;

sharing all flights for a segment of a trip;

sharing over-water or international flights for a segment of a trip;

sharing as much mileage or time as possible for a segment of a trip; and

sharing origin or destination airports or cities.

24. The system of claim 22, wherein a client system sends the MPMR query to a server that processes the MPMR query to produce the plurality of individual queries that comprise the first query.