Multi-passenger multi-route travel planning

• US 7,921,022 B2
• Filed: 01/18/2006
• Issued: 04/05/2011
• Est. Priority Date: 01/18/2006
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Boyan, Justin A., de Marcken, Carl G.
• Primary Examiner(s): Hayes; John W
• Assistant Examiner(s): CHEN, GEORGE YUNG CHIEH
• Application Number:
  US11/334,959
• Publication Number:
  US 20070168239A1
• Time in Patent Office: 1,903 Days
• Field of Search: None
• US Class Current: 705/5
• 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 executed over a computer network for finding travel solutions each travel solution comprising a set of one or more units of transportation and one or more fares useable with the set of units of transportation in response to travel planning queries for multiple routes for multiple passenger groups, the method comprising:

receiving, by a computer, joint travel requirements/preferences for multiple passenger groups, the joint travel requirements/preferences specifying a shared unit of transportation for a common travel segment corresponding to co-dependent portions of travel routes that are common for the passenger groups, with at least one of the routes for at least one of the passenger groups having plural segments of travel between an origin airport and a destination airport, the joint travel requirements/preferences being at least one of a common origin airport for an initial outbound portion of a trip, a common destination airport for a return portion of the trip, and a common segment of travel for an intermediate portion of the trip;

sending by a computer to a scheduler system, multiple, individual queries to produce individual solutions that meet the received joint travel requirements/preferences;

merging, by a computer system, individual solutions from the multiple, individual queries to produce joint solutions for the passenger groups according to the received joint travel requirements/preferences.

2. The method of claim 1 further comprising:

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

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

4. The method of claim 3 further comprising:

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

5. The method of claim 4 further comprising:

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

6. The method of claim 4 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.

7. The method of claim 2 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.

8. The method of claim 1 wherein each individual query is processed and a list of individual solutions is produced for each passenger group.

9. The method of claim 8 wherein each of the lists is received, and merging individual solutions comprises:

producing by a computer from the lists of individual solutions a list of potential joint solutions; and

filtering by a computer the list of potential joint solutions to eliminate potential joint solutions from the list of potential joint solutions that violate joint travel requirements/preferences.

10. The method of claim 9 wherein producing from the lists of individual solutions a list of potential joint solutions comprises:

matching each individual solution in the lists of individual solutions with every other individual solution in the lists of individual solutions to provide a list of potential joint solutions.

11. The method of claim 1 further comprising:

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

12. The method of claim 11 wherein a client system sends the MPMR query to the server computer 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 multiple individual queries.

13. The method of claim 11 wherein a 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.

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

processing the multiple individual queries concurrently by sending the multiple individual queries to different computers.

15. The method of claim 1 wherein merging individual solutions comprises:

producing indices of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements/preferences.

16. The method of claim 15 wherein merging individual solutions 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.

19. A computer program product residing on a computer readable medium, for multiple routes for multiple passenger groups, the computer program product comprising instructions for causing a computer to:

receive joint travel requirements/preferences for multiple passenger groups, the joint travel requirements/preferences specifying a shared unit of transportation for a common travel segment corresponding to co-dependent portions of travel routes that are common for the passenger groups, with at least one of the routes for at least one of the passenger groups having plural segments of travel between an origin airport and a destination airport, the joint travel requirements/preferences being at least one of a common origin airport for an initial outbound portion of a trip, a common destination airport for a return portion of the trip, and a common segment of travel for an intermediate portion of the trip;

send to a scheduler system, multiple, individual queries to produce individual solutions that meet the received joint travel requirements/preferences; and

merge individual solutions from the multiple, individual queries to produce joint solutions for the passenger groups according to the received joint travel requirements/preferences.

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

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

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

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

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

23. The computer program product of claim 20 wherein instructions to construct a factored representation further comprises instructions to:

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

link individual indices to those solutions with the index.

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

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

25. The computer program product of claim 20 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.

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

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

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

produce from the lists of individual solutions 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/preferences.

28. The computer program product of claim 27 wherein instructions to produce from the lists of individual solutions a list of potential joint solutions further comprising instructions to:

match each individual solution in the lists of individual solutions with every other individual solution in the lists of individual solutions to provide a list of potential joint solutions.

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

produce indices of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements/preferences.

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

combine the individual solutions according to the indices.

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

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

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

33. A system, comprises:

a processor;

memory coupled to the processor; and

a computer readable medium storing a computer program product for processing of queries for multiple routes for multiple passenger groups, the computer program product comprising instructions for causing the processor to;

receive joint travel requirements/preferences for multiple passenger groups, the joint travel requirements/preferences specifying a shared unit of transportation for a common travel segment corresponding to co-dependent portions of travel routes that arc common for the passenger groups, with at least one of the routes for at least one of the passenger groups having plural segments of travel between an origin airport and a destination airport, the joint travel requirements/preferences being at least one of a common origin airport for an initial outbound portion of a trip, a common destination airport for a return portion of the trip, and a common segment of travel for an intermediate portion of the trip;

send to a scheduler system, multiple, individual queries to produce individual solutions that meet the received joint travel requirements/preferences; and

merge individual solutions from the multiple, individual queries to produce joint solutions for the passenger groups according to the received joint travel requirements/preferences.

34. The system of claim 33 wherein the instructions to merge further comprises instructions to:

produce from the lists of individual solutions 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/preferences.

35. The system of claim 34 wherein the instructions to merge further comprises instructions to:

produce indices of individual solutions according to aspects of the solutions that are relevant for evaluating joint requirements/preferences.

36. The system of claim 35 wherein the instructions to merge further comprises instructions to:

combine the individual solutions according to the indices.

37. The system of claim 33 further comprises instructions to:

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

38. The system of claim 37 wherein the instructions to construct 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 the index.

39. The system of claim 37 wherein the factored representation is an AND/OR graph that compactly represents the set of joint solutions.

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

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

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

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