Patent US5832453A successfully refreshed from Google Patents.
US5832453A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer system and method for determining a travel scheme minimizing travel costs for an organization
Assignee: American Express Travel Related Services Co Inc
•
Filing: 1994-03-22
•
Granted: 1998-11-03
•
Expires: 2014-03-22
Abstract
Abstract A computer system and a method for determining a travel scheme minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of travel links. Each travel link comprises a travel origin and a travel destination, and is served by at least one of the carriers. The system comprises a data input device for receiving travel information relating to the carriers and the links, a data storage device for storing the travel information received by the data input device, a processor, and a data output device. From the travel information, the system constructs an objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links, and a set of constraints comprising restrictions relating to the objective function. The constraints are applied to the objective function to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs of the organization, and a data output device then generates a report representative of the solution. The travel information comprises travel cost information for each link for each carrier serving the link, demand and supply information pertaining to a projected demand for each link and a projected supply for each carrier, and carrier goal information pertaining to any predetermined goal the organization may have with respect to any of the carriers.
Inventors
- 👤 Danamichele Brennen O'Brien
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 10:13
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/04; G06Q10/047; G06Q10/02; G06Q10/025; G06Q10/028; G06Q10/0283; G06Q30/00; G06Q30/02; G06Q50/00; G06Q50/10; G06Q50/14
Claims Analysis
Total Claims: 74
Claim 1
Independent Claim
215 words
In a computer system having a data input device, a data storage device, and a processor, a method for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the method comprising the steps of: obtaining travel information relating to the carriers and the links via the data input device; storing the travel information via the data storage device; constructing an objective function from the travel information via the processor, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; constructing a set of constraints from the travel information via the processor, the constraints comprising restrictions relating to the objective function; applying the constraints to the objective function via the processor to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs of the organization; and applying the solution as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 2
Dependent Claim
215 words
In a computer system having a data input device, a data storage device, and a processor, a method for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the method comprising the steps of: obtaining travel information relating to the carriers and the links via the data input device; storing the travel information via the data storage device; constructing an objective function from the travel information via the processor, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; constructing a set of constraints from the travel information via the processor, the constraints comprising restrictions relating to the objective function; applying the constraints to the objective function via the processor to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs of the organization; and applying the solution as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 3
Dependent Claim
69 words
The computer system of claim 1 wherein the obtaining travel information step comprises the steps of: obtaining travel cost information for each link for each carrier serving the link; obtaining demand and supply information pertaining to a projected demand for each link and a projected supply for each carrier; and obtaining carrier goal information pertaining to any predetermined goal the organization has with respect to any of the carriers.
Claim 4
Dependent Claim
41 words
The computer system of claim 2 wherein the processor determines from the travel cost information for each link for each carrier serving the link a weighted value representing an actual cost to the organization for traveling the link using the carrier.
Claim 5
Dependent Claim
84 words
The computer system of claim 3 wherein the objective function comprises the sum of a travel cost for each link, the travel cost for each link comprising the sum of a travel cost for each carrier serving the link, the travel cost for each carrier serving the link comprising the weighted value representing the actual cost to the organization for traveling the link using the carrier multiplied by a variable representing a number of trips to be purchased from the carrier for the link.
Claim 6
Dependent Claim
16 words
The computer system of claim 4 wherein the solution comprises a solution value for each variable.
Claim 7
Dependent Claim
29 words
The computer system of claim 5 wherein the processor determines lower and upper limits for each constraint, each constraint being adjustable between the limits while maintaining the determined solution.
Claim 8
Dependent Claim
31 words
The computer system of claim 5 wherein the processor determines lower and upper limits for each solution value, each solution value being adjustable between the limits while maintaining the determined solution.
Claim 9
Dependent Claim
125 words
The computer system of claim 4 wherein the constraints are derived from the demand and supply information and the carrier goal information, the constraints comprising link demand constraints, carrier supply constraints, and carrier goal constraints, the link demand constraints requiring that for each link the sum of the variables representing the number of trips to be purchased from all carriers for the link be equal to the projected demand for the link, each carrier supply constraint requiring that for a particular carrier the sum of the variables representing the number of trips to be purchased from the carrier for all links be in a predetermined range, each carrier goal constraint requiring that the goal the organization has with respect to a particular carrier be accomplished.
Claim 10
Dependent Claim
19 words
The computer system of claim 2 wherein the processor determines the obtained information in the form of a table.
Claim 11
Dependent Claim
60 words
The computer system of claim 9 wherein the processor organizes organizing each of the plurality of links in a first direction on the table and each of the plurality of carriers in a second direction on the table, each carrier serving each link being designated by a cell on the table having information pertaining to the carrier serving the link.
Claim 12
Dependent Claim
31 words
The computer system of claim 10 wherein the processor organizes the link demand information according to each link and the carrier supply information and carrier goal information according to each carrier.
Claim 13
Dependent Claim
24 words
The computer system of claim 11 wherein the processor employs linear programming to apply the constraints to the objective function to determine the solution.
Claim 14
Dependent Claim
26 words
The computer system of claim 12 wherein the processor organizes the solution in the form of a table corresponding to the table of the obtained information.
Claim 15
Dependent Claim
23 words
The computer system of claim 2 wherein the obtaining travel cost information step comprises acquiring current travel data from a computerized reservation system.
Claim 16
Dependent Claim
26 words
The computer system of claim 2 wherein the obtaining travel cost information step comprises acquiring previously generated historical travel data from a historical travel data file.
Claim 17
Dependent Claim
43 words
The computer system of claim 2 wherein the obtaining demand and supply information and obtaining carrier goal information steps comprise acquiring the demand and supply information and the carrier goal information for the organization from a previously generated organization discount program data file.
Claim 18
Dependent Claim
24 words
The computer system of claim 1 wherein the processor employs linear programming to apply the constraints to the objective function to determine the solution.
Claim 19
Independent Claim
176 words
A method for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the method comprising the steps of: obtaining travel information relating to the carriers and the links; constructing an objective function from the travel information, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; constructing a set of constraints from the travel information, the constraints comprising restrictions relating to the objective function; applying the constraints to the objective function to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs of the organization; and applying the solution as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 20
Independent Claim
176 words
A method for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the method comprising the steps of: obtaining travel information relating to the carriers and the links; constructing an objective function from the travel information, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; constructing a set of constraints from the travel information, the constraints comprising restrictions relating to the objective function; applying the constraints to the objective function to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs of the organization; and applying the solution as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 21
Dependent Claim
67 words
The method of claim 18 wherein the obtaining travel information step comprises the steps of: obtaining travel cost information for each link for each carrier serving the link; obtaining demand and-supply information pertaining to a projected demand for each link and a projected supply for each carrier; and obtaining carrier goal information pertaining to any predetermined goal the organization has with respect to any of the carriers.
Claim 22
Dependent Claim
42 words
The method of claim 19 further comprising the step of determining from the travel cost information for each link for each carrier serving the link a weighted value representing an actual cost to the organization for traveling the link using the carrier.
Claim 23
Dependent Claim
83 words
The method of claim 20 wherein the objective function comprises the sum of a travel cost for each link, the travel cost for each link comprising the sum of a travel cost for each carrier serving the link, the travel cost for each carrier serving the link comprising the weighted value representing the actual cost to the organization for traveling the link using the carrier multiplied by a variable representing a number of trips to be purchased from the carrier for the link.
Claim 24
Dependent Claim
15 words
The method of claim 21 wherein the solution comprises a solution value for each variable.
Claim 25
Dependent Claim
30 words
The method of claim 22 further comprising the step of determining lower and upper limits for each constraint, each constraint being adjustable between the limits while maintaining the determined solution.
Claim 26
Dependent Claim
32 words
The method of claim 22 further comprising the step of determining lower and upper limits for each solution value, each solution value being adjustable between the limits while maintaining the determined solution.
Claim 27
Dependent Claim
124 words
The method of claim 21 wherein the constraints are derived from the demand and supply information and the carrier goal information, the constraints comprising link demand constraints, carrier supply constraints, and carrier goal constraints, the link demand constraints requiring that for each link the sum of the variables representing the number of trips to be purchased from all carriers for the link be equal to the projected demand for the link, each carrier supply constraint requiring that for a particular carrier the sum of the variables representing the number of trips to be purchased from the carrier for all links be in a predetermined range, each carrier goal constraint requiring that the goal the organization has with respect to a particular carrier be accomplished.
Claim 28
Dependent Claim
20 words
The method of claim 19 further comprising the step of organizing the obtained information in the form of a table.
Claim 29
Dependent Claim
60 words
The method of claim 26 wherein the organizing step comprises organizing each of the plurality of links in a first direction on the table and each of the plurality of carriers in a second direction on the table, each carrier serving each link being designated by a cell on the table having information pertaining to the carrier serving the link.
Claim 30
Dependent Claim
34 words
The method of claim 27 wherein the organizing step further comprises organizing the link demand information according to each link and the carrier supply information and the carrier goal information according to each carrier.
Claim 31
Dependent Claim
25 words
The method of claim 28 further comprising the step of employing linear programming to apply the constraints to the objective function to determine the solution.
Claim 32
Dependent Claim
27 words
The method of claim 29 further comprising the step of organizing the solution in the form of a table corresponding to the table of the obtained information.
Claim 33
Dependent Claim
22 words
The method of claim 19 wherein the obtaining travel cost information step comprises acquiring current travel data from a computerized reservation system.
Claim 34
Dependent Claim
25 words
The method of claim 19 wherein the obtaining travel cost information step comprises acquiring previously generated historical travel data from a historical travel data file.
Claim 35
Dependent Claim
42 words
The method of claim 19 wherein the obtaining demand and supply information and obtaining carrier goal information steps comprise acquiring the demand and supply information and the carrier goal information for the organization from a previously generated organization discount program data file.
Claim 36
Dependent Claim
25 words
The method of claim 18 further comprising the step of employing linear programming to apply the constraints to the objective function to determine the solution.
Claim 37
Dependent Claim
206 words
A computer system for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the system comprising: a data input device for receiving travel information relating to the carriers and the links; a data storage device for storing the travel information received by the data input device; a programmed processor for constructing an objective function from the travel information, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; and a programmed processor for constructing a set of constraints from the travel information, the constraints comprising restrictions relating to the objective function; the processor for applying the constraints to the objective function to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs the organization; the solution for being applied as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 38
Dependent Claim
206 words
A computer system for determining a travel scheme for minimizing travel costs for an organization, where the organization expects to purchase travel trips for a plurality of travelers for a plurality of predetermined travel links, each travel link comprising a travel origin and a travel destination, each travel link being served by at least one of a plurality of travel carriers, the system comprising: a data input device for receiving travel information relating to the carriers and the links; a data storage device for storing the travel information received by the data input device; a programmed processor for constructing an objective function from the travel information, the objective function representing a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links; and a programmed processor for constructing a set of constraints from the travel information, the constraints comprising restrictions relating to the objective function; the processor for applying the constraints to the objective function to determine a solution of the objective function that satisfies the constraints and that minimizes the travel costs the organization; the solution for being applied as the travel scheme for minimizing travel costs by purchasing travel trips in accordance with the solution.
Claim 39
Dependent Claim
61 words
The computer system of claim 35 wherein the travel information comprises travel cost information for each link for each carrier serving the link, demand and supply information pertaining to a projected demand for each link and a projected supply for each carrier, and carrier goal information pertaining to any predetermined goal the organization has with respect to any of the carriers.
Claim 40
Dependent Claim
41 words
The computer system of claim 36 wherein the processor determines from the travel cost information for each link for each carrier serving the link a weighted value representing an actual cost to the organization for traveling the link using the carrier.
Claim 41
Dependent Claim
84 words
The computer system of claim 37 wherein the objective function comprises the sum of a travel cost for each link, the travel cost for each link comprising the sum of a travel cost for each carrier serving the link, the travel cost for each carrier serving the link comprising the weighted value representing the actual cost to the organization for traveling the link using the carrier multiplied by a variable representing a number of trips to be purchased from the carrier for the link.
Claim 42
Dependent Claim
16 words
The computer system of claim 38 wherein the solution comprises a solution value for each variable.
Claim 43
Dependent Claim
31 words
The computer system of claim 39 wherein lower and upper limits for each constraint are determined by the processor, each constraint being adjustable between the limits while maintaining the determined solution.
Claim 44
Dependent Claim
33 words
The computer system of claim 39 wherein lower and upper limits for each solution value are determined by the processor, each solution value being adjustable between the limits while maintaining the determined solution.
Claim 45
Dependent Claim
125 words
The computer system of claim 38 wherein the constraints are derived from the demand and supply information and the carrier goal information, the constraints comprising link demand constraints, carrier supply constraints, and carrier goal constraints, the link demand constraints requiring that for each link the sum of the variables representing the number of trips to be purchased from all carriers for the link be equal to the projected demand for the link, each carrier supply constraint requiring that for a particular carrier the sum of the variables representing the number of trips to be purchased from the carrier for all links be in a predetermined range, each carrier goal constraint requiring that the goal the organization has with respect to a particular carrier be accomplished.
Claim 46
Dependent Claim
32 words
The computer system of claim 42 wherein the goal constraint comprises a predetermined discount from a particular carrier only if the carrier receives a minimum predetermined amount of business from the organization.
Claim 47
Dependent Claim
21 words
The computer system of claim 36 wherein the information retrieved by the processor is organized in the form of a table.
Claim 48
Dependent Claim
56 words
The computer system of claim 44 wherein the table is organized with each of the plurality of links laid out in a first direction and each of the plurality of carriers laid out in a second direction, each carrier serving each link being designated by a cell having information pertaining to the carrier serving the link.
Claim 49
Dependent Claim
34 words
The computer system of claim 45 wherein the link demand information is organized according to each link and wherein the carrier supply information and the carrier goal information is organized according to each carrier.
Claim 50
Dependent Claim
41 words
The computer system of claim 46 further comprising software for extracting information from the table to construct the objective function and the set of constraints and linear programming software for applying the constraints to the objective function to determine the solution.
Claim 51
Dependent Claim
25 words
The computer system of claim 47 wherein the solution is organized in the form of a table corresponding to the table of the obtained information.
Claim 52
Dependent Claim
43 words
The computer system of claim 36 further comprising a means for acquiring travel data from a computerized reservation system, wherein the travel cost information for each link for each carrier serving the link is compiled at least in part from the travel data.
Claim 53
Dependent Claim
43 words
The computer system of claim 36 further comprising a generated historical travel data file having historical travel data, wherein the travel cost information for each link for each carrier serving the link is compiled at least in part from the historical travel data.
Claim 54
Dependent Claim
29 words
The computer system of claim 36 further comprising a generated organization discount program data file having the demand and supply information and the carrier goal information for the organization.
Claim 55
Dependent Claim
101 words
The computer system of claim 36 wherein the travel cost information for each link for each carrier serving the link includes a member of the group selected from an expected fare the carrier charges for traveling the link, any discounts the carrier provides to the organization, any added costs in connection with traveling the link using the carrier, any benefits received in connection with traveling the link using the carrier, the number of non-stop voyages available, the number of connecting voyages available, any expected transfer delays, the percentage of total voyages the carrier provides for the link, and a combination thereof.
Claim 56
Dependent Claim
45 words
The computer system of claim 35 further comprising software executed on the processor for extracting information from the table to construct the objective function and the set of constraints and linear programming software for applying the constraints to the objective function to determine the solution.
Claim 57
Independent Claim
174 words
A method for determining an optimum travel scheme for minimizing travel costs for traveling a plurality of travel links being served by a plurality of travel carriers by selectively allocating travel trips on each link to the carriers serving the link, comprising the steps of: (a) determining travel information representative of the links and the carriers serving the links; (b) determining constraints on allocating the trips to the carriers; (c) prospectively allocating the trips among the carriers in accordance with the travel information and the constraints to provide a travel scheme; (d) determining a cost of the travel scheme of step (c); (e) ascertaining whether any of the travel information or constraints have changed; (f) if any of the travel information or constraints have changed, then repeating steps (c), (d), and (e) until the optimum travel scheme minimizing the travel costs in accordance with the travel information and the constraints is determined; and (g) applying the optimum travel scheme to minimize travel costs by purchasing travel trips in accordance with such optimum travel scheme.
Claim 58
Independent Claim
174 words
A method for determining an optimum travel scheme for minimizing travel costs for traveling a plurality of travel links being served by a plurality of travel carriers by selectively allocating travel trips on each link to the carriers serving the link, comprising the steps of: (a) determining travel information representative of the links and the carriers serving the links; (b) determining constraints on allocating the trips to the carriers; (c) prospectively allocating the trips among the carriers in accordance with the travel information and the constraints to provide a travel scheme; (d) determining a cost of the travel scheme of step (c); (e) ascertaining whether any of the travel information or constraints have changed; (f) if any of the travel information or constraints have changed, then repeating steps (c), (d), and (e) until the optimum travel scheme minimizing the travel costs in accordance with the travel information and the constraints is determined; and (g) applying the optimum travel scheme to minimize travel costs by purchasing travel trips in accordance with such optimum travel scheme.
Claim 59
Dependent Claim
68 words
The method of claim 54 wherein the determining travel information step comprises the steps of: obtaining travel cost information for each link for each carrier serving the link; obtaining demand and supply information pertaining to a projected demand for each link and a projected supply for each carrier; and obtaining carrier goal information pertaining to any predetermined goal the organization has with respect to any of the carriers.
Claim 60
Dependent Claim
42 words
The method of claim 55 further comprising the step of determining from the travel cost information for each link for each carrier serving the link a weighted value representing an actual cost to the organization for traveling the link using the carrier.
Claim 61
Dependent Claim
89 words
The method of claim 56 wherein the cost of the travel scheme comprises a function representing the sum of a travel cost for each link, the travel cost for each link comprising the sum of a travel cost for each carrier serving the link, the travel cost for each carrier serving the link comprising the weighted value representing the actual cost to the organization for traveling the link using the carrier multiplied by a variable representing a number of trips to be purchased from the carrier for the link.
Claim 62
Dependent Claim
17 words
The method of claim 57 wherein the optimum travel scheme comprises a solution value for each variable.
Claim 63
Dependent Claim
31 words
The method of claim 58 further comprising the step of determining lower and upper limits for each constraint, each constraint being adjustable between the limits while maintaining the optimum travel scheme.
Claim 64
Dependent Claim
33 words
The method of claim 58 further comprising the step of determining lower and upper limits for each solution value, each solution value being adjustable between the limits while maintaining the optimum travel scheme.
Claim 65
Dependent Claim
124 words
The method of claim 57 wherein the constraints are derived from the demand and supply information and the carrier goal information, the constraints comprising link demand constraints, carrier supply constraints, and carrier goal constraints, the link demand constraints requiring that for each link the sum of the variables representing the number of trips to be purchased from all carriers for the link be equal to the projected demand for the link, each carrier supply constraint requiring that for a particular carrier the sum of the variables representing the number of trips to be purchased from the carrier for all links be in a predetermined range, each carrier goal constraint requiring that the goal the organization has with respect to a particular carrier be accomplished.
Claim 66
Dependent Claim
20 words
The method of claim 55 further comprising the step of organizing the obtained information in the form of a table.
Claim 67
Dependent Claim
60 words
The method of claim 62 wherein the organizing step comprises organizing each of the plurality of links in a first direction on the table and each of the plurality of carriers in a second direction on the table, each carrier serving each link being designated by a cell on the table having information pertaining to the carrier serving the link.
Claim 68
Dependent Claim
34 words
The method of claim 63 wherein the organizing step further comprises organizing the link demand information according to each link and the carrier supply information and the carrier goal information according to each carrier.
Claim 69
Dependent Claim
33 words
The method of claim 64 further comprising the step of employing linear programming to apply the constraints to a function representing the cost of the travel scheme to determine the optimum travel scheme.
Claim 70
Dependent Claim
29 words
The method of claim 65 further comprising the step of organizing the optimum travel scheme in the form of a table corresponding to the table of the obtained information.
Claim 71
Dependent Claim
22 words
The method of claim 55 wherein the obtaining travel cost information step comprises acquiring current travel data from a computerized reservation system.
Claim 72
Dependent Claim
25 words
The method of claim 55 wherein the obtaining travel cost information step comprises acquiring previously generated historical travel data from a historical travel data file.
Claim 73
Dependent Claim
42 words
The method of claim 55 wherein the obtaining demand and supply information and obtaining carrier goal information steps comprise acquiring the demand and supply information and the carrier goal information for the organization from a previously generated organization discount program data file.
Claim 74
Dependent Claim
17 words
The method of claim 54 further comprising the step of employing linear programming to determine a solution.
References Cited (Backward Citations)
US2910238A
Cited
US2995729A
Cited
US3253262A
Cited
US4775936A
Cited
US4755963A
Cited
US4862357A
Cited
US4845625A
Cited
US4931932A
Cited
US5021953A
Cited
US5331546A
Cited
US5191523A
Cited
US5253165A
Cited
US5343388A
Cited
US5255184A
Cited
US5270921A
Cited
US5253166A
Cited
US5237499A
Cited
US5402336A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-02 | 2002-05-04 | 2002-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-02 | 2006-05-04 | 2006-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-02 | 2010-05-04 | 2010-11-03 | $7700.00 | Window Closed / Lapsed |