Pricing tickets based on constructing tables of pricing units for sub-portions of a ticket

• US 20070021989A1
• Filed: 07/19/2005
• Published: 01/25/2007
• Est. Priority Date: 07/19/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: de Marcken, Carl
• Granted Patent: US 8,583,460 B2
• Time in Patent Office: Days
• US Class Current: 705/5
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions

Abstract

Pricing of a sequence of transportation units includes receiving a set of sellable-units, encoding the set of sellable-units into a context-free grammar that represents possible ways that the sellable-units can be combined to produce valid tickets and producing a ticket from the encoded set of sellable units.

Claims

1. A method of pricing a sequence of transportation units, the method comprising:

receiving a set of sellable-units;

encoding the set of sellable-units into a context-free grammar that represents possible ways that the sellable-units can be combined to produce valid tickets;

producing a ticket from the encoded set of sellable units.

2. The method of claim 1 wherein encoding the set of sellable units comprises:

adding a context free grammar rule for each of the sellable units.

3. The method of claim 1 wherein the rule for the context-free grammar is of the form P[i]==>

FA[i][1] . . . FA[i][n[i]].

4. The method of claim 1 wherein faring-atoms are represented as sets of flights and adding rules to the context-free grammar comprises:

expanding faring-atoms into their component flights in order that the context-free grammar represents tickets as sequences of flights, by adding a rule for each faring-atom FA[k] of length L[k] as;

FA[k]==>

Flight[k][1] . . . Flight[k][L[k]].

5. The method of claim 4 wherein the set of sellable units are priceable units and the set of priceable units has priceable-unit-label Q[i] has a set of possible faring-atoms FAS[i][1] . . . FAS[i][n[i]] for each of its n[i] parts, with individual faring-atoms indexed FA[i][j][1] . . . FA[i][j][m[i,j]] where m[i,j] is the number of faring-atom possibilities for the j'"'"'th fare-component of priceable-unit-label i, and the altered grammar is of the form:

 

 

 

Ticket ==>

S  

 

 

S  

==>

Q S | <

empty>

 

 

 

Q  

==>

Q[1] | Q[2] | ... | Q[N]  

 

 

(1 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1]  

 

 

 

(2 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1]FAS[i][2]  

 

 

(3 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1] FAS[i][2] FAS[i][3]  

 

 

(4 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1] FAS[i][2] FAS[i][3] FAS[i][4] FAS[i][j] ==>

FA[i][j][1] | FA[i][j][2] | ... | FA[i][j][m].

6. The method of claim 1 wherein the context-free grammar supports non-consecutive fare-components by allowing an arbitrary number of sellable-units to appear between every fare-component of a priceable-unit.

7. The method of claim 1 further comprising:

extending the context-free grammar to support non-consecutive fare-components by allowing an arbitrary number of priceable-units to appear between every fare-component of a sellable-unit.

8. The method of claim 1 wherein the core grammar non-terminal nodes are extended with sets of partially completed priceable units to account for crossing priceable-units.

9. The method of claim 1 wherein sellable-units contain multiple fare-components, and the grammar comprises

augmenting the grammar with a set that represents the set of crossing sellable-units whose first fare-component appears within the non-terminal'"'"'s expansion;

and augmenting the grammar with a set that represents the set of crossing sellable-units whose second fare-component appears within the non-terminal'"'"'s expansion.

10. The method of claim 1 wherein parsing a lattice of terminals with the context free grammar produces a packed parse forest representation in a form of an AND/OR graph representation.

11. The method of claim 10 further comprising:

enumerating priced tickets that include assignments of fares to flights from the AND/OR graph representation.

12. The method of claim 1 further comprising:

associating price information with the context-free grammar.

13. The method of claim 12 wherein associating price information further comprises:

linking the price information with non-terminal priceable-unit symbols in the context free grammar.

14. The method of claim 13 wherein linking links the price information with the context-free grammar linking the fares as a list.

15. The method of claim 1 wherein the priceable-units are represented as a set of priceable-unit-labels linked to priceable-unit-cores, where a priceable-unit-label is a factored representation of faring-atom combinations and a priceable-unit-core is a factored representation of fare combinations to encode the context-free grammar.

16. A method of pricing multiple tickets, the method comprising:

receiving a set of priceable-units;

encoding the set of priceable-units into a context-free grammar that represents possible ways that the priceable-units can be combined to produce valid tickets;

constructing a lattice of flights that represents permitted flight combinations for a ticket; and

parsing the lattice to produce a packed parse forest representation of valid priced tickets.

17. The method of claim 16 wherein the packed parse forest representation is a standard representation of valid parses of the lattice.

18. The method of claim 16 further comprising associating pricing information with the grammar to build the ticket.

19. The method of claim 16 wherein the ticket is built from one or more priceable-units.

20. The method of claim 16 wherein price information is fares.

21. The method of claim 16 wherein price information is associated with the grammar by linking the price information with non-terminal priceable-unit symbols in the grammar representations of the priceable-unit'"'"'s fares.

22. A method for pricing a sequence of flights, the method comprising:

receiving a set of sellable units; and

successively building a table T_ij of possible pricings of subsequences of flights from a flight i to a flight j.

23. The method of claim 22 wherein the sellable units are limited to a specific sequence of flights.

24. The method of claim 22 wherein the sellable units are priceable units.

25. The method of claim 22 wherein a table entry T_ij is a representation of the mathematical union of the following:

any sellable unit of a subsequence of flight i to flight j, and

for all sellable units P decomposable into two parts, flights i to k and flights l to j, and the combination of P with each of the pricing possibilities stored in T_kl,

for all i<

k<

j, the cross product of the pricing possibilities stored in T_ij and Tkj.

26. The method of claim 22 wherein the table T_ij maintains at most a single pricing for each subsequence of flights.

27. The method of claim 22 wherein the lattice is a unique sequence of flights.

28. The method of claim 22 further comprising:

producing a packed forest representation of possible tickets.

30. The method of claim 28 further comprising:

producing a packed forest representation of possible tickets.

29. A method for generating a ticket comprising:

receiving a set of sellable units;

receiving a set of flight constraints;

encoding the sellable units into a grammar that represents the possible ways the sellable units can be combined to produce valid tickets;

transforming the grammar to encode the flight constraints;

successively expanding a root node of the grammar to produce a sequence of grammar terminals.

31. A computer program product tangible embodied on a computer readable medium for pricing a sequence of transportation units, the computer program product comprising instructions for causing a computing device to:

receive a set of sellable-units;

encode the set of sellable-units into a context-free grammar that represents possible ways that the sellable-units can be combined to produce valid tickets;

produce a ticket from the encoded set of sellable units.

32. The computer program product of claim 31 wherein instructions to encode the set of sellable units comprises instructions to:

add a context free grammar rule for each of the sellable units.

33. The computer program product of claim 31 wherein the rule for the context-free grammar is of the form P[i]==>

FA[i][1] . . . FA[i][n[i]].

34. The computer program product of claim 31 wherein faring-atoms are represented as sets of flights and adding rules to the context-free grammar comprises:

expand faring-atoms into their component flights in order that the context-free grammar represents tickets as sequences of flights, by adding a rule for each faring-atom FA[k] of length L[k] as;

FA[k]==>

Flight[k][1] . . . Flight[k][L[k]].

35. The computer program product of claim 31 wherein the set of sellable units are priceable units and the set of priceable units has priceable-unit-label Q[i] has a set of possible faring-atoms FAS[i][1] . . . FAS[i][n[i]] for each of its n[i] parts, with individual faring-atoms indexed FA[i][j][1] . . . FA[i][j][m[i,j]] where m[i,j] is the number of faring-atom possibilities for the j'"'"'th fare-component of priceable-unit-label i, and the altered grammar is of the form:

 

 

 

Ticket ==>

S  

 

 

S  

==>

Q S | <

empty>

 

 

 

Q  

==>

Q[1] | Q[2] | ... | Q[N]  

 

 

(1 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1]  

 

 

 

(2 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1] FAS[i][2]  

 

 

(3 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1] FAS[i][2] FAS[i][3]  

 

 

(4 fare-component)  

 

 

 

 

Q[i] ==>

FAS[i][1] FAS[i][2] FAS[i][3] FAS[i][4] FAS[i][j] ==>

FA[i][j][1] | FA[i][j][2] | ... | FA[i][j][m].

36. The computer program product of claim 31 wherein the context-free grammar supports non-consecutive fare-components and the program includes instructions to:

allow an arbitrary number of sellable-units to appear between every fare-component of a sellable-unit.

37. The computer program product of claim 31 wherein sellable-units contain multiple fare-components, and computer program product comprises instructions to:

augment the grammar with a set that represents the set of crossing sellable-units whose first fare-component appears within the non-terminal'"'"'s expansion; and

augment the grammar with a set that represents the set of crossing sellable-units whose second fare-component appears within the non-terminal'"'"'s expansion.

38. The computer program product of claim 31 wherein instructions to parse a lattice of terminals with the context free grammar produce a packed parse forest representation in a form of an AND/OR graph representation.

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

enumerating priced tickets that include assignments of fares to flights from the AND/OR graph representation.

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

associate price information with the context-free grammar.

41. The computer program product of claim 31 wherein instructions to associate price information further comprising instructions to:

link the price information with non-terminal priceable-unit symbols in the context free grammar.

42. The computer program product of claim 31 wherein instructions to associate price information further comprising instructions to:

link the price information with the context-free grammar linking the fares as a list.

43. A computer program product tangible embodied on a computer readable medium for pricing a sequence of transportation units, the computer program product comprising instructions for causing a computing device to:

receive a set of priceable-units;

encode the set of priceable-units into a context-free grammar that represents possible ways that the priceable-units can be combined to produce valid tickets;

construct a lattice of flights that represents permitted flight combinations for a ticket; and

parse the lattice to produce a packed parse forest representation of valid priced tickets.

44. The computer program product of claim 43 wherein the packed parse forest representation is a standard representation of valid parses of the lattice.

45. The computer program product of claim 43 further comprising instructions to:

associate pricing information with the grammar to build the ticket.

46. The computer program product of claim 43 wherein the ticket is built from one or more priceable-units.

47. The computer program product of claim 43 wherein price information is fares.

48. The computer program product of claim 43 wherein price information is associated with the grammar by linking the price information with non-terminal priceable-unit symbols in the grammar representations of the priceable-unit'"'"'s fares.

52. The computer program product of claim 43 further comprising instructions to:

produce a packed forest representation of possible tickets.

54. The computer program product of claim 43 further comprising instructions to:

producing a packed forest representation of possible tickets.

49. A computer program product tangible embodied on a computer readable medium for pricing a sequence of transportation units, the computer program product comprising instructions for causing a computing device to:

receive a set of sellable units;

successively build a table T_ij of possible pricings of subsequences of flights from a flight i to a flight j.

50. The computer program product of claim 49 wherein the sellable units are limited to a specific sequence of flights.

51. The computer program product of claim 49 wherein the sellable units are priceable units.

53. A computer program product tangible embodied on a computer readable medium for pricing a sequence of transportation units, the computer program product comprising instructions for causing a computing device to:

receive a set of sellable units;

receive a set of flight constraints,

encode the sellable units into a grammar that represents the possible ways the sellable units can be combined to produce valid tickets;

transform the grammar to encode the flight constraints;

successively expand a root node of the grammar to produce a sequence of grammar terminals.