Pricing graph representation for sets of pricing solutions for travel planning system

• US 8,571,903 B1
• Filed: 06/27/2003
• Issued: 10/29/2013
• Est. Priority Date: 07/02/1998
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: DeMarcken, Carl G.
• Primary Examiner(s): Hayes, John
• Assistant Examiner(s): JOSEPH, TONYA S
• Application Number:
  US10/609,032
• Time in Patent Office: 3,777 Days
• Field of Search: 705/5
• 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/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

An airline travel planning system is described. The system includes a server computer executing a server process including a search process to search for set of pricing solutions in accordance with at least one destination and at least one origin. The search process represents the set of pricing solutions in the form of a directed acyclic graph. The system also includes a client computer executing a client process on the set of pricing solutions. The client process has a manipulation process that manipulates the set of pricing solutions in response to user preferences. Several processes are described including a process responsive to user preferences and to set of pricing solutions that provides pricing solutions sorted by said user preference, a process that sorts set of pricing solutions to produce a subset of said set of pricing solutions in accordance with user specified preferences, and a process that prunes from the directed acyclic graph nodes that are no longer contained within the subset of set of pricing solutions.

Claims

1. A computer program product residing on a non-transitory computer readable storage medium for determining fares for sets of itineraries, the computer program product comprising instructions for causing one or more computers to:

decompose the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;

retrieve fares, with fares comprising a carrier, a market, fare class, and a price;

retrieve fare rules for the faring atoms from a fare rules database;

retrieve routings for a fare;

for a retrieved fare;

apply the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules;

produce the fare component as a combination of the faring atom and the retrieved fare; and

compute travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

2. The computer program product of claim 1 wherein the faring atoms are data structures that comprise:

a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

3. The computer program product of claim 1 wherein the faring atoms are data structures and, for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring-market that the particular one of the faring atoms is in, and cached results that store results of applying fare rule records to the particular one of the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

4. The computer program product of claim 2 wherein the flight sequences are represented as a set of lists of itineraries.

5. The computer program product of claim 3 wherein the instructions for causing one or more computers to compute prices comprise instructions for causing one or more computers to:

for applying a fare rule to a faring atom, determine if the faring atom has cached results for the fare rule, and if it has cached results,

retrieve the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

6. The computer program product of claim 5 wherein the instructions to retrieve the cached results retrieves the result of applying fare rules to the faring atom and avoids repeating of applying fare rules to the faring atom for those fare components common to multiple trips.

7. The computer program product of claim 1 wherein instructions for causing one or more computers to compute prices for more than one of the flight segments in a sequence of flight segments cause one or more computers to share computational work among more than one flight segment.

8. The computer program product of claim 1 further comprising instructions to produce a representation of fares useable with flight segments of the itinerary sets using a structure that shares flight segments and fares across multiple trips.

9. A computer implemented method for determining fares for sets of itineraries, the method comprising:

decomposing, by one or more computers, the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;

retrieving fares, with fares comprising a carrier, a market, fare class, and a price;

retrieving fare rules for the faring atoms from a fare rules database;

retrieving routings for a fare;

for a retrieved fare;

applying, by one or more computers, the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules;

produce the fare component as a combination of the faring atom and the retrieved fare; and

compute, by one or more computers, travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

10. The method of claim 9 wherein the faring atoms are data structures that comprise a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

11. The method of claim 9 wherein faring atoms are data structures and for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring market that the particular faring atom is in, and cached results that store results of applying fare rule records to the particular faring atom, with the result being one of pass, fail, no match, unavailable or defer.

12. The method of claim 10 wherein trips are represented as a set of lists of itineraries.

13. The method of claim 11 wherein computing prices comprises:

for applying a fare rule to a faring atom, determining if the faring atom has cached results, and if it has cached results,

retrieving the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

14. The method of claim 13 wherein retrieving the cached results retrieves the result of applying fare rules to the faring atom and avoids repeating of applying fare rules to the faring atom for those fare components common to multiple trips.

15. The method of claim 9 wherein computing prices for at least some of the sequence of flight segments comprises sharing computational work among more than one flight segment.

16. The method of claim 9 further comprising:

producing a representation of fares useable with flight segments of multiple trips using a structure that shares flight segments and fares across the multiple trips.

17. A computer system for travel planning comprising:

a processor;

a memory in which resides a computer program product for determining fares for sets of itineraries, the computer program product comprising instructions for causing a computer to;

decompose the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;

retrieve fares, with fares comprising a carrier, a market, fare class, and a price;

retrieve fare rules for the faring atoms from a fare rules database;

retrieve routings for a fare;

for a retrieved fare;

apply the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules;

produce the fare component as a combination of the faring atom and the retrieved fare; and

compute travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

18. The system of claim 17 wherein the faring atoms are data structures that comprise a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

19. The system of claim 17 wherein faring atoms are data structures and for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring market that the particular one of the faring atoms is in, and cached results that store results of applying fare rule records to the particular one of the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

20. The system of claim 17 wherein the computer program product comprises instructions for causing one or more computers to link fares and fare components.

21. The system of claim 19 wherein the computer program product comprises instructions for causing one or more computers to:

for applying a fare rule to a faring atom, determine if the faring atom has cached results, and if it has cached results,

retrieve the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

22. The system of claim 17 wherein the instructions to retrieve fare rule results avoids repeated computation of prices for those fare components common to multiple trips.

23. A computer-implemented method for determining a set of fares for a set of itineraries, the method comprising:

retrieving by operation of one or more computers, from one or more databases, itinerary sets of sequences of flight segments for at least one slice of a journey; and

, for each itinerary set of sequences of flight segments;

computing prices by one or more computers for more than one of the flight segments in the set of sequences of flight segments by one or more computers;

parsing retrieved itinerary sets into one or more travel unit segments associated with a single fare, with a fare comprising a carrier, a market, a fare class, and a price;

applying fare rules to the one or more travel unit segments to produce fare components;

storing information associated with applying of the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare component; and

constructing by operation of one or more computers, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

24. The method of claim 23 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

25. The method of claim 23 wherein computing prices comprises retrieving fares for those fare components of the set of sequences of flight segments that are shared across trips.

26. The method of claim 23 wherein a set of trips is represented as a set of lists of itineraries.

27. The method of claim 23 wherein applying a fare rule to a travel unit segment comprises:

determining if the travel unit segment has cached results for the fare rule; and

if it has cached results,

retrieving the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare component.

28. The method of claim 27 further comprising producing a representation of fares useable with flight segments of multiple trips, the representation including flight segments and fares that are shared across the multiple trips.

39. The method of claim 23, wherein storing information associated with application of the fare rules stores the information into a fare component structure and the method further comprises:

checking a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,

applying the stored result to the fare component.

29. A computer program product residing on a non-transitory computer readable storage medium for determining a set of fares for a set of itineraries, the computer readable storage medium comprising instructions for causing a computer to:

retrieve, from one or more databases, itinerary sets of sequences of flight segments for at least one slice of a journey; and

compute prices for more than one of the flight segments in the set of sequences of flight segments by instructions to;

parse retrieved itinerary sets into one or more travel unit segments spanned by a single fare with a fare comprising a carrier, a market, fare class, and a price;

apply fare rules to the one or more travel unit segments, to produce fare components;

store information associated with applying the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare components; and

construct, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

30. The computer program product of claim 29 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

31. The computer program product of claim 29 wherein computing prices comprises instructions to retrieve fares for those fare components of the set of sequences of flight segments that are shared across trips.

32. The computer program product of claim 29 wherein applying a fare rule to a travel unit segment comprises instructions to:

determine if the travel unit segment has cached results for the fare rule, and if it has cached results,

retrieve the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare component.

33. The computer program product of claim 32, further comprising instructions to:

produce a representation of fares useable with flight segments of multiple trips, the representation including flight segments and fares that are shared across the multiple trips.

40. The computer program product of claim 29 wherein instructions to store information associated with application of the fare rules comprises storing the information into a fare component structure and the product further comprises instructions to:

check a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,

apply the stored result to the fare component.

34. A computer system for determining a set of fares for a set of itineraries comprising:

a computer; and

a computer readable medium storing a computer program that causes one or more computers to;

retrieve, from one or more databases, a set of sequences of flight segments for at least one slice of a journey; and

compute prices for more than one of the flight segments in the set of sequences of flight segments by instructions to;

parse retrieved itinerary sets into one or more travel unit segments associated with a single fare with a fare comprising a carrier, a market, fare class, and a price;

apply fare rules to the one or more travel unit segments to produce fare components;

store information associated with applying the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare components; and

construct, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

35. The computer system of claim 34 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

36. The computer system of claim 34 wherein the instructions to compute prices comprises instructions to retrieve fares for those fare components of the set of sequences of flight segments that are shared across trips.

37. The computer system of claim 34 wherein applying a fare rule to a travel unit segment comprises instructions to:

determine if the travel unit segment has cached results for the fare rule, and if it has cached results, retrieve the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare.

38. The computer system of claim 36 further comprising instructions to produce a representation of fares useable with flight segments of the trips, the representation including flight segments and fares that are shared across the trips.

41. The computer system of claim 34 wherein instructions to store information associated with application of the fare rules comprises storing the information into a fare component structure and the computer program further comprises instructions to:

check a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,

apply the stored result to the fare component.