Method and system for determining marginal values for use in a revenue management system

• US 5,918,209 A
• Filed: 01/11/1996
• Issued: 06/29/1999
• Est. Priority Date: 01/11/1996
• Status: Expired due to Term

• Current Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Original Assignee: Talus Solutions, Inc. (RedPrairie Holding Incorporated)
• Inventors: Phillips, Robert L., Campbell, Gregory L., Saleh, Richard A., Zimmerman, Jon P., Beskow, Stefan L., Grimes, Richard C.
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/585,637
• Time in Patent Office: 1,265 Days
• Field of Search: 705/5, 705/6, 705/7, 705/10, 705/20, 705/28, 705/29
• US Class Current: 705/5
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

A method and system for determining marginal values for perishable resources expiring at a future time, for example, an airline seat, hotel room night, rental car day or the like, for use in a perishable resource revenue management system. Data for the perishable resources and composite resources is loaded from the perishable resource revenue management system into the marginal value system. Internal data structures are constructed for linking each of the perishable resources to their associated composite resources and for linking each of the composite resources to their associated perishable resources. The marginal values for the perishable resources are determined using a continuous optimization function using interdependencies among the perishable resources and the composite resources in the internal data structures. The marginal values are stored from the marginal value system into the perishable resource revenue management system.

Claims

1. A method using a computer for determining marginal values for perishable resources, comprising the steps of:

loading data for the perishable resources and composite resources from a perishable resource revenue management system into the marginal value system;

constructing internal data structures for linking each of the perishable resources to their associated composite resources and for linking each of the composite resources to their associated perishable resources;

determining the marginal values for the perishable resources using a continuous optimization function using interdependencies among the perishable resources and the composite resources in the internal data structures; and

storing the marginal values from the marginal value system into the perishable resource revenue management system.

2. A method according to claim 1, the step of determining further comprising the steps of:

evaluating a locally optimal marginal value for the perishable resources using the continuous optimization function on each of the perishable resources; and

performing the step of evaluating in successive iterations until a globally optimal marginal value is evaluated for the perishable resources based on a convergence criterion.

3. A method according to claim 2, further comprising the steps of:

monitoring a maximum difference between such locally optimal marginal values evaluated during a current iteration and such locally optimal marginal values evaluated during a previous iteration;

comparing the maximum difference and the convergence criterion upon completion of the current iteration whereby convergence is satisfied when the maximum difference is less than the convergence criterion.

4. A method according to claim 1, the step of determining further comprising the steps of:

evaluating a locally optimal marginal value for one of the perishable resources using the continuous optimization function; and

performing the step of evaluating in successive iterations for another of the perishable resources until a locally optimal marginal value has been evaluated for all of the perishable resources.

5. A method according to claim 4, further comprising the steps of:

determining the absolute difference between such locally optimal marginal value evaluated for one of the perishable resources during a current iteration and such locally optimal marginal value evaluated for the resource during a previous iteration;

comparing the absolute difference to a maximum difference between such locally optimal marginal value evaluated for another of the perishable resources during the current iteration and such locally optimal marginal value evaluated for the resource during the previous iteration whereby the maximum difference equals or exceeds all such absolute differences between such locally optimal marginal values evaluated for all other perishable resources during a current iteration and such locally optimal marginal values evaluated for the resources during a previous iteration; and

replacing the maximum difference with the absolute difference when the absolute difference is greater than the maximum difference.

6. A method according to claim 1, further comprising the steps of:

loading resource value data comprising a supply of the perishable resources and a set of resource prices from the perishable resource revenue management system into the marginal value system; and

constructing an internal data structure for linking each of the composite resources to their associated set of resource prices and for linking each of the perishable resources to their associated supply.

7. A method according to claim 6, whereby the continuous optimization function is a deterministic optimization function, the step of determining further comprising evaluating locally optimal marginal values based on a certain demand for each of the composite resources.

8. A method according to claim 7, whereby the deterministic optimization function is a supply-demand balance optimization function, further comprising the step of:

searching for a marginal value for one of the composite resources whereby the supply substantially equals the demand for the one composite resource.

9. A method according to claim 8, further comprising the steps of:

determining the difference between the supply and the certain demand for the one resource; and

setting the marginal value for the one resource to indicate that the supply exceeds the demand when the difference is positive.

10. A method according to claim 8, further comprising the step of:

determining the certain demand for the one perishable resource based on the marginal values for each other of the perishable resources contained in each of the composite resources containing the one perishable resource.

11. A method according to claim 10, further comprising the steps of:

determining a composite resource demand for each of the composite resources containing the one perishable resource; and

adding the composite resource demand for each of the composite resources to the certain demand for the one perishable resource.

12. A method according to claim 11, further comprising the steps of:

adding the marginal value for each of the perishable resources contained in one of the composite resources to a total marginal value; and

determining the composite resource demand for the one composite resource using the total marginal value.

13. A method according to claim 12, whereby each of the set of resource prices comprises a corresponding demand point on a demand curve, further comprising the steps of:

searching for the first demand point on the demand curve corresponding to a resource price that exceeds the total marginal value;

determining a linear average between the first demand point and a second demand point previous to the first demand point; and

determining the composite resource demand based on an intersection of the supply and the linear average.

14. A method according to claim 6, whereby the continuous optimization function is a non-deterministic optimization function, the step of determining further comprising evaluating locally optimal marginal values based on an uncertain demand for each of the composite resources.

15. A method according to claim 14, whereby the continuous optimization function is a non-deterministic optimization function based on a supply of each of the perishable resources and an uncertain demand for the composite resources.

16. A method according to claim 15, whereby the non-deterministic optimization function is an expected marginal resource revenue (EMRR) optimization function, further comprising the steps of:

searching for a marginal value for one of the composite resources whereby the supply substantially matches a protection level for the one composite resource.

17. A method according to claim 16, further comprising the step of:

loading resource value data further comprising a set of means and a set of variances from the perishable resource revenue management system into the marginal value system whereby the set of means and the set of variances correspond to the set of resource prices; and

constructing an internal data structure for linking each of the composite resources to their associated set of means and set of variances.

18. A method according to claim 16, further comprising the steps of:

creating a demand point list for the one perishable resource containing a set of demand points corresponding to each of the set of resource prices;

determining an accumulated mean, an accumulated net leg revenue and an accumulated variance based on the set of resource prices, the set of means and the set of variances for each demand point in the demand point list;

determining an updated average net resource revenue based on the accumulated net leg revenue and the accumulated mean; and

determining the protection level for each of a set of accumulated demand points using the accumulated mean, the accumulated variance and the average net leg revenue for each demand point in the demand point list.

19. A method according to claim 18, whereby the demand point list is determined, further comprising the steps of:

accumulating the marginal values for all of the perishable resources in a composite resource containing the one perishable resource except for the marginal value for the one composite resource for each of the set of resource prices;

determining a net leg revenue for each demand point in the demand point list using the accumulated marginal values; and

creating a new demand point when the net leg revenue is positive.

20. A method according to claim 19, further comprising the steps of:

setting the net leg revenue to the difference of the corresponding resource price minus the accumulated marginal values.

21. A method according to claim 18, further comprising the steps of:

determining the accumulated mean comprising a summation of each mean in the set of means for each of the set of demand points;

determining the accumulated net leg revenue comprising a summation of each of the set of resource prices multiplied by each of the means in the set of means for each of the set of demand points; and

determining the accumulated variance comprising a summation of each variance in the set of variances for each of the set of demand points.

22. A method according to claim 18, further comprising the steps of:

determining the updated average net resource comprising the quotient of the accumulated net leg revenue divided by the accumulated mean.

23. A method according to claim 18, further comprising the steps of:

determining a standard deviation equaling a square root of the accumulated variance;

determining an inverse cumulative normal of the equation;

space="preserve" listing-type="equation">(1-NNRR/ANRR)

whereby NNRR corresponds to next net resource revenue for a demand point in the demand point list and ANRR corresponds to the average net resource revenue for each demand point in the demand point list; and

setting the protection level to the sum of the accumulated mean plus the inverse cumulative normal multiplied by the standard deviation.

24. A computerized marginal value system for determining marginal values for perishable resources, comprising:

means for loading data for the perishable resources and composite resources from a computerized perishable resource revenue management system into the computerized marginal value system;

means for constructing internal data structures for linking each of the perishable resources to their associated composite resources and for linking each of the composite resources to their associated perishable resources;

means for determining the marginal values for the perishable resources using a continuous optimization function using the perishable resources and the composite resources in the internal data structures; and

means for storing the marginal values from the marginal value system into the perishable resource revenue management system.

25. A method of producing a marginal value representing currency determined using a computerized marginal value system for use in a computerized perishable resource revenue management system for granting and denying a sale of one or more perishable resources expiring at a future time depending on marginal values for each of such perishable resources received from the computerized perishable resource revenue management system, comprising the steps of:

loading data for the perishable resources, composite resources and a resource value from a computerized perishable resource revenue management system into the computerized marginal value system;

constructing internal data structures for the perishable resources, composite resources and resource value;

determining marginal values for the perishable resources using a continuous optimization function; and

storing the marginal values from the computerized marginal value system into the computerized perishable resource revenue management system.

26. A method using a computer for determining marginal values for perishable resources, comprising the steps of using the computer for:

loading data for the perishable resources and composite resources from a perishable resource revenue management system into the marginal value system;

constructing internal data structures for linking each of the perishable resources to their associated composite resources and for linking each of the composite resources to their associated perishable resources;

evaluating a locally optimal marginal value for one of the perishable resources using a continuous optimization function dependent on the marginal values for the other perishable resources; and

iteratively reevaluating the locally optimal marginal value until a globally optimal marginal value is attained for the one of the perishable resources.

27. A method according to claim 26, further comprising the steps of:

iteratively performing the step of evaluating until a locally optimal marginal value is attained for each of the perishable resources.

28. A method according to claim 26, whereby the continuous optimization function is a supply demand balance optimization function, further comprising the steps of:

determining whether a supply for the one perishable resource minus a demand for the one perishable resource is positive; and

searching for the locally optimal marginal value that makes the supply equal the demand.

29. A method according to claim 26, whereby the continuous optimization function is a expected marginal resource revenue optimization function, further comprising the steps of:

creating a demand point list for the one perishable resource based on a set of resource prices, means and variances associated with each of the composite resources containing the one perishable resource;

determining a protection level for each demand point in the demand point list; and

searching for the locally optimal marginal value that makes the supply equal the protection level.

30. A marginal value system for determining marginal values for perishable resources, comprising:

computerized means for evaluating a locally optimal marginal value for one of the perishable resources using a continuous optimization function dependent on the marginal values for the other perishable resources; and

computerized means for iteratively reevaluating the locally optimal marginal value until a globally optimal marginal value is attained for the one of the perishable resources.

31. A method using a computer for determining marginal values for seats on flight leg departures departing on a future departure date, comprising the steps of:

loading data for flight leg departures and flight path departures from an airline revenue management system into a marginal value system;

constructing internal data structures for linking each of the flight leg departures to their associated flight path departures and for linking each of the flight path departures to their associated flight leg departures;

determining the marginal values for seats on the flight leg departures using a continuous optimization function using interdependencies among the flight leg departures and the flight path departures in the internal data structures; and

storing the marginal values from the marginal value system into the airline revenue management system.

32. A method according to claim 31, the step of determining further comprising the steps of:

evaluating a locally optimal marginal value for seats on the flight leg departures using the continuous optimization function on each of the flight leg departures; and

performing the step of evaluating in successive iterations until a globally optimal marginal value is evaluated for the flight leg departures based on a convergence criterion.

33. A method according to claim 32, further comprising the steps of:

monitoring a maximum difference between such locally optimal marginal values evaluated during a current iteration and such locally optimal marginal values evaluated during a previous iteration;

comparing the maximum difference and the convergence criterion upon completion of the current iteration whereby convergence is satisfied when the maximum difference is less than the convergence criterion.

34. A method according to claim 31, the step of determining further comprising the steps of:

evaluating a locally optimal marginal value for a seat on one of the flight leg departures using the continuous optimization function; and

performing the step of evaluating in successive iterations for another of the flight leg departures until a locally optimal marginal value has been evaluated for all of the flight leg departures.

35. A method according to claim 34, further comprising the steps of:

determining the absolute difference between such locally optimal marginal value evaluated for a seat on one of the flight leg departures during a current iteration and such locally optimal marginal value evaluated for the seat during a previous iteration;

comparing the absolute difference to a maximum difference between such locally optimal marginal value evaluated for a seat on another of the flight leg departures during the current iteration and such locally optimal marginal value evaluated for the seat during the previous iteration whereby the maximum difference equals or exceeds all such absolute differences between such locally optimal marginal values evaluated for seats on all other flight leg departures during a current iteration and such locally optimal marginal values evaluated for the seats during a previous iteration; and

replacing the maximum difference with the absolute difference when the absolute difference is greater than the maximum difference.

36. A method according to claim 31, further comprising the steps of:

loading passenger value data comprising a supply of seats on each of the flight leg departures and a set of booking class prices from the airline revenue management system into the marginal value system; and

constructing an internal data structure for linking each of the flight path departures to their associated set of booking class prices and for linking each of the flight leg departures to their associated supply of seats.

37. A method according to claim 36, whereby the continuous optimization function is a deterministic optimization function, the step of determining further comprising evaluating locally optimal marginal values based on a certain demand for seats on each of the flight leg departures.

38. A method according to claim 37, whereby the deterministic optimization function is a supply-demand balance optimization function, further comprising the step of:

searching for a marginal value for one of the flight leg departures whereby the supply of seats substantially matches the demand for seats on the one flight leg departure.

39. A method according to claim 38, further comprising the steps of:

determining the difference between the supply of seats and the certain demand for seats on the one flight leg departure; and

setting the marginal value for the one flight leg departure to indicate that the supply of seats exceeds the demand for seats when the difference is positive.

40. A method according to claim 38, further comprising the step of:

determining the certain demand for the one flight leg departure based on the marginal values for each other of the flight leg departures contained in each of the flight path departures containing the one flight leg departure.

41. A method according to claim 40, further comprising the steps of:

determining a path demand for each of the flight path departures containing the one flight leg departure; and

adding the path demand for each of the flight path departures to the certain demand for the one flight leg departure.

42. A method according to claim 41, further comprising the steps of:

adding the marginal value for each of the flight leg departures contained in one of the flight path departures to a total marginal value; and

determining the path demand for the one flight path departure using the total marginal value.

43. A method according to claim 42, whereby each of the set of booking class prices comprises a corresponding demand point on a demand curve, further comprising the steps of:

searching for the first demand point on the demand curve corresponding to a booking class price that exceeds the total marginal value;

determining a linear average between the first demand point and a second demand point previous to the first demand point; and

determining the path demand based on an intersection of the supply of seats and the linear average.

44. A method according to claim 36, whereby the continuous optimization function is a non-deterministic optimization function, the step of determining further comprising evaluating locally optimal marginal values based on an uncertain demand for seats on each of the flight leg departures.

45. A method according to claim 44, whereby the continuous optimization function is a non-deterministic optimization function based on a supply of seats on each of the flight leg departures and an uncertain demand for the seats.

46. A method according to claim 45, whereby the non-deterministic optimization function is an expected marginal seat revenue (EMSR) optimization function, further comprising the steps of:

searching for a marginal value for one of the flight leg departures whereby the supply of seats substantially matches a protection level for seats on the one flight leg departure.

47. A method according to claim 46, further comprising the step of:

loading passenger value data further comprising a set of means and a set of variances from the airline revenue management system into the marginal value system whereby the set of means and the set of variances correspond to the set of booking class prices; and

constructing an internal data structure for linking each of the flight path departures to their associated set of means and set of variances.

48. A method according to claim 46, further comprising the steps of:

creating a demand point list for the one flight leg departure containing a set of demand points corresponding to each of the set of booking class prices;

determining an accumulated mean, an accumulated net leg revenue and an accumulated variance based on the set of booking class prices, the set of means and the set of variances for each demand point in the demand point list;

determining an updated average net leg revenue based on the accumulated net leg revenue and the accumulated mean; and

determining the protection level for each of a set of accumulated demand points using the accumulated mean, the accumulated variance and the average net leg revenue for each demand point in the demand point list.

49. A method according to claim 48, whereby the demand point list is determined, further comprising the steps of:

accumulating the marginal values for all of the flight leg departures in a flight path departure containing the one flight leg departure except for the marginal value for the one flight leg departure for each of the set of booking class prices;

determining a net leg revenue for each demand point in the demand point list using the accumulated marginal values; and

creating a new demand point when the net leg revenue is positive.

50. A method according to claim 49, further comprising the steps of:

setting the net leg revenue to the difference of the corresponding booking class price minus the accumulated marginal values.

51. A method according to claim 48, further comprising the steps of:

determining the accumulated mean comprising a summation of each mean in the set of means for each of the set of demand points;

determining the accumulated net leg revenue comprising a summation of each of the set of booking class prices multiplied by each of the means in the set of means for each of the set of demand points; and

determining the accumulated variance comprising a summation of each variance in the set of variances for each of the set of demand points.

52. A method according to claim 48, further comprising the steps of:

determining the updated average net leg comprising the quotient of the accumulated net leg revenue divided by the accumulated mean.

53. A method according to claim 48, further comprising the steps of:

determining a standard deviation equalling a square root of the accumulated variance;

determining an inverse cumulative normal of the equation;

space="preserve" listing-type="equation">(1-NNLR/ANLR)

whereby NNLR corresponds to a next net leg revenue for a demand point in the demand point list and ANLR corresponds to the average net leg revenue for each demand point in the demand point list; and

setting the protection level to the sum of the accumulated mean plus the inverse cumulative normal multiplied by the standard deviation.

54. A computerized marginal value system for determining marginal values for seats on flight leg departures departing on a future departure date comprising:

means for loading data for flight leg departures and flight path departures from a computerized airline revenue management system into the computerized marginal value system;

means for constructing internal data structures for linking each of the flight leg departures to their associated flight path departures and for linking each of the flight path departures to their associated flight leg departures;

means for determining the marginal values for seats on the flight leg departures using a continuous optimization function using the flight leg departures and the flight path departures in the internal data structures; and

means for storing the marginal values from the marginal value system into the computerized airline revenue management system.

55. A method of producing a marginal value representing currency determined using a computerized marginal value system for use in conjunction with an airline reservations system for granting and denying a sale of seats on one or more flight leg departures departing on a future departure date depending on marginal values for seats on each of such flight leg departures received from a computerized airline revenue management system, the method comprising the steps of:

loading data for flight leg departures, flight path departures and passenger value from the computerized airline revenue management system into the computerized marginal value system;

constructing internal data structures for the flight leg departures, flight path departures and passenger value;

determining marginal values for seats on the flight leg departures using a continuous optimization function; and

storing the marginal values from the marginal value system into the computerized airline revenue management system.

56. A method using a computer for determining marginal values for seats on flight leg departures departing on a future departure date, comprising the steps of using the computer for:

loading data for flight leg departures and flight path departures from an airline revenue management system into the marginal value system;

constructing internal data structures for linking each of the flight leg departures to associated flight path departures and for linking each of the flight path departures to their associated flight leg departures;

evaluating a locally optimal marginal value for a seat on one of the flight leg departures using a continuous optimization function dependent on the marginal values for a seat on the other flight leg departures; and

iteratively reevaluating the locally optimal marginal value until a globally optimal marginal value is attained for the seat on one of the flight leg departures.

57. A method according to claim 56, further comprising the steps of:

iteratively performing the step of evaluating until a locally optimal marginal value is attained for each of the flight leg departures.

58. A method according to claim 56, whereby the continuous optimization function is a supply demand balance optimization function, further comprising the steps of:

determining whether a supply of seats for the one flight leg departure minus a demand for seats for the one flight leg departure is positive; and

searching for the locally optimal marginal value that makes the supply of seats equal the demand for seats.

59. A method according to claim 56, whereby the continuous optimization function is a expected marginal seat revenue optimization function, further comprising the steps of:

creating a demand point list for the one flight leg departure based on a set of booking class prices, means and variances associated with each of the flight path departures containing the one flight leg departure;

determining a protection level for each demand point in the demand point list; and

searching for the locally optimal marginal value that makes the supply of seats equal the protection level.

60. A marginal value system for determining marginal values for seats on flight leg departures departing on a future departure date, comprising:

computer means for evaluating a locally optimal marginal value for a seat on one of the flight leg departures using a continuous optimization function dependent on the marginal values for a seat on the other flight leg departures; and

computer means for iteratively re-evaluating the locally optimal marginal value until a globally optimal marginal value is attained for the seat on one of the flight leg departures.