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

• US 6,275,808 B1
• Filed: 07/02/1998
• Issued: 08/14/2001
• Est. Priority Date: 07/02/1998
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: DeMarcken, Carl G.
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US09/109,871
• Time in Patent Office: 1,139 Days
• Field of Search: 701/201, 701/202, 705/5, 705/6, 705/400, 707/10, 707/102, 707/104, 709/217, 709/218, 709/219
• 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 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 storage medium storing a data structure that represents pricing solutions for use with a travel planning software program comprises:

a first plurality of choice nodes that represent exclusive pricing solutions;

a second plurality of combining nodes that represent collective pricing solutions; and

a third plurality of terminal nodes that represent pricing objects.

2. The computer storage medium of claim 1 wherein said pricing objects of the third plurality of terminal nodes comprise pricing objects that include fares.

3. The computer storage medium of claim 1 wherein said pricing objects of the third plurality of terminal nodes comprise pricing objects that include itineraries.

4. The computer storage medium of claim 1 wherein said pricing objects of the third plurality of terminal nodes comprise pricing objects that include surcharges.

5. The computer storage medium of claim 1 wherein said third plurality of terminal nodes comprise pricing objects that include routes.

6. The computer storage medium of claim 1 wherein said third plurality of terminal nodes comprise pricing objects that include one or more of itineraries, routes, fares, prices, booking codes, surcharges, taxes or rules/regulations.

7. The computer storage medium of claim 1 wherein said third plurality of terminal nodes comprise a field having a value to indicate whether the node is valid or invalid.

8. The computer storage medium of claim 1 wherein the combining nodes contain values of subsequent nodes that are combined to produce a pricing solution.

9. The computer storage medium of claim 1 wherein said first plurality of exclusive nodes comprise a field having a value to indicate whether the node is valid or invalid.

10. The computer storage medium of claim 1 wherein said second plurality of combining nodes comprise a field having a value to indicate whether the node is valid or invalid.

11. The computer storage medium of claim 1 wherein the data structure is a directed acyclic graph.

12. The computer storage medium of claim 1 wherein said nodes are logically combined according to rules to enumerate a plurality of pricing solutions, with the number of said pricing solutions being substantially greater than the number of nodes.

13. The computer storage medium of claim 1 wherein said nodes are logically combined according to rules to enumerate a plurality of pricing solution components, with the number of said pricing solution components being substantially greater than the number of nodes;

each node having a field if containing a first value invalidates the node preventing the node from contributing to forming the enumerated pricing solution components or a second value to validate the node permitting the node to contribute to forming the enumerated pricing solution components.

14. The computer storage medium of claim 1 wherein the exclusive nodes include value fields corresponding to a minimum possible inner value, minimum possible outer value and minimum possible total value.

15. The computer storage medium of claim 1 wherein the combining nodes include value fields corresponding to a minimum possible inner value, minimum possible outer value and minimum possible total value.

16. The computer storage medium of claim 1 wherein the terminal nodes include value fields corresponding to a minimum possible inner value, minimum possible outer value and minimum possible total value.

17. The computer storage medium of claim 1 wherein at least some of the nodes include value fields corresponding to at least one of a minimum possible inner value, minimum possible outer value and minimum possible total value.

18. The computer storage medium of claim 1 wherein a first portion of the first plurality of exclusive nodes refer to subsequent combining nodes.

19. The computer storage medium of claim 9 wherein a second portion of said first plurality of exclusive nodes refer to terminal nodes.

20. The computer storage medium of claim 1 wherein a first portion of said second plurality of combining nodes refer to subsequent combining nodes.

21. The computer storage medium of claim 20 wherein a second portion of said second plurality of combining nodes refer to terminal nodes.

22. The computer storage medium of claim 1 wherein exclusive nodes include a pointing field pointing a child node having a least positive inner-value.

23. The computer storage medium of claim 21 wherein the value fields are used by algorithms to extract pricing solution components from the data structure.

24. The computer storage medium of claim 21 wherein the value fields are used by algorithms to return values in response to a query presented by an algorithm.

25. A computer storage medium storing a data structure that represents pricing solutions for use with a travel planning software program comprises:

a first plurality of choice nodes that represent exclusive pricing solutions;

a second plurality of combining nodes that represent collective pricing solutions;

a third plurality of terminal nodes that represent pricing objects; and

wherein said nodes are logically combined according to rules to enumerate a plurality of pricing solutions, with the number of said pricing solutions being substantially greater than the number of nodes.

26. The computer storage medium of claim 25 wherein exclusive nodes include a pointing field pointing a child node having a least positive inner-value.

27. The computer storage medium of claim 25 wherein at least some of the nodes include value fields corresponding to at least one of a minimum possible inner value, minimum possible outer value and minimum possible total value.

28. The computer storage medium of claim 27 wherein the value fields are used by algorithms to extract pricing solution components from the data structure.

29. The computer storage medium of claim 27 wherein the value fields are used by algorithms to return values in response to a query presented by an algorithm.

30. A method executed in a computer system for producing a pricing graph data structure from a plurality of data strictures used to represent information and operations involved in forming pricing solutions, for use with a travel planning software application comprises:

assigning a type to each of the plurality of data structures, said type requiring a corresponding data structure to be combinable with others of the plurality of data structures or exclusive to others of the plurality of data structures;

listing fields in the corresponding data structure that contribute to a node in the pricing graph data structure;

converting fields of the data structure into the assigned type; and

placing converted fields from the data structure in a node in the pricing graph data structure.

31. The method of claim 30 further comprising placing in the data structure at least one field of a data structure that represents terminal nodes corresponding to a pricing object.

32. The method of claim 31 wherein said pricing object is selected from the group of fares, itinerary, surcharge, and route.

33. The method of claim 30 wherein assigning a type to the data structure comprises assigning at least one of a logical OR type, logical AND type or a terminal type.

34. The method of claim 33 wherein at least one of said data structures is a data structure that groups itinerary divisions by multi-slice priceable units.

35. The method of claim 33 wherein at least one of said data structures is a data structure that includes a set of open multi-slice labels and a set of backward links.

36. The method of claim 35 wherein open label sets are converted into exclusive nodes and the backward links are converted into combinable nodes.

37. The method of claim 33 wherein at least one of said data structures is a data structure that represents priceable units.

38. The method of claim 37 wherein the at least one of said data structures that represents priceable units further comprises a priceable unit label data structure and a priceable unit core data structure.

39. A method executed on a computer system in a travel planning system for manipulating a pricing graph data structure having a plurality of nodes that represent pricing solutions, the data structure for use with a travel planning software application, the method comprising:

selecting a value function based on a user input and which initializes the value function;

applying the selected value function to the pricing graph data structure to extract from the pricing graph, a pricing solution component that satisfies the specified input to the value function.

40. The method of claim 39 wherein applying a value function operates on the pricing graph data structure and returns a numerical value that can be used to rank pricing solution components.

41. The method of claim 40 wherein the value function returned is a fare for a set of pricing solution components.

42. The method of claim 40 wherein the value function returned is a value determined from at least two attributes of a set of pricing solution components.

43. The method of claim 40 wherein the value function invalidates at least one of the plurality of nodes in the pricing graph data structure in accordance with a user preference indicating that the at least one invalidated node will not participate in forming pricing solution components.

44. The method of claim 43 wherein the nodes include value fields corresponding to a minimum possible inner value, a minimum possible outer value and a minimum possible total value represented by the nodes.

45. The method of claim 40 wherein the value function enumerates a plurality of pricing solutions by sorting the nodes in accordance with a user preference.

46. The method of claim 45 wherein nodes other than the at least one invalidated node are validated nodes and further comprises:

applying a value function to the pricing graph data structure; and

returning a numerical value from one of the value fields in validated nodes which are nodes that can be used to rank the pricing solution components.

47. The method of claim 46 wherein the value function returns a fare for a set of pricing solutions from one of the fields in the nodes.

48. The method of claim 46 wherein the value function returns a value determined from at least two attributes of a set of pricing solution components from two of the fields in the nodes.

49. The method of claim 46 wherein the value function enumerates a plurality of pricing solutions by sorting the nodes in accordance with a user preference and returns values from one of the fields in the sorted nodes.