Computer system and method for determining a travel scheme minimizing travel costs for an organization

BACKGROUND OF THE INVENTION

0001The present invention relates to a computer system and a method for determining the distribution of transportation carrier support that will result in the lowest total travel cost for an organization. More particularly, the invention relates to a computer system and method for developing a model to represent an organization's travel requirements in order to maximize and leverage benefits obtained from individual transportation carriers.

0002Typically, a larger size organization will tend to purchase a significant amount of travel services from a number of travel carriers. For example, a large corporation having a headquarters office and several far-flung divisional offices, manufacturing plants, and the like may be expected to have its employees and/or representatives travel therebetween as well as to other locations in the ordinary course of business. Such an organization typically negotiates special incentive arrangements with one or more travel carriers in order to obtain a discount for supporting the travel carriers.

0003Nevertheless, a particular incentive arrangement may actually cost the organization more money than is being saved, for any of several reasons. For example, the organization may take advantage of a particular incentive arrangement by using a particular travel carrier to travel between a location A and a location B. However, in doing so, the organization may have to suffer the fact that the travel carrier does not provide fast and/or frequent service between the two locations.

0004Alternatively, the travel carrier may not provide added benefits that another travel carrier offers for traveling between the two locations. Still further, in supporting the one carrier, another less costly alternative may be ignored. Inevitably, the lack of an organized travel scheme causes the organization to incur significant additional total travel costs. Thus, it would be highly advantageous to have a system and method for organizing a coherent travel scheme based on the organization's travel demands, the negotiated travel incentives the organization has with particular travel carriers, and the service each travel carrier provides between particular travel locations, as well as several other factors, in order to minimize the total travel cost incurred by the organization.

SUMMARY OF THE INVENTION

0005The present invention is directed to a computer system and 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 comprises a travel origin and a travel destination, and is served by at least one of a plurality of travel 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. The system constructs an objective function and a set of constraints from the travel information. The objective function represents a travel cost to the organization to purchase travel trips for the plurality of travelers for the plurality of predetermined links, and the constraints comprise 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. The data output device then generates a report representative of the solution.

0006Preferably, 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. 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 is determined. Preferably, the objective function comprises the sum of a travel cost for each link, the travel cost for each link comprises the sum of a travel cost for each carrier serving the link, and the travel cost for each carrier serving the link comprises 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.

0007Preferably, the constraints are derived from the demand and supply information and the carrier goal information. Also preferably, the constraints comprise link demand constraints, carrier supply constraints, and carrier goal constraints. The link demand constraints require 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. The carrier supply constraints require 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 requires that the goal the organization has with respect to a particular carrier be accomplished.

0008Preferably, the information is organized in the form of a matrix or table, where each of the plurality of links is laid out in a first direction, each of the plurality of carriers is laid out in a second direction, and each carrier serving a particular link is designated by a cell having information pertaining thereto. Also preferably, the link demand information is organized according to each link and the carrier supply information and the carrier goal information is organized according to each carrier. Preferably, linear programming is implemented to apply the constraints to the objective function to determine the solution. Information from the solution may be communicated from the computer system to point of sale terminals for use in setting travel arrangements.

0009The computer system and method are preferably employed by a travel agency to provide a travel optimization service to an organization. The fee for the service may comprise a portion of the savings realized to the organization by employing the travel optimization service.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The foregoing summary, as well as the following detailed description of a preferred embodiment of the invention, will be better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the drawings an embodiment which is presently preferred. It should be understood, however, that the invention is not limited to the precise arrangements and instrumentalities shown. In the drawings:

0011<figref idref="DRAWINGS">FIG. 1</figref> is a schematic block diagram of a computer system for determining a travel scheme minimizing travel costs for an organization in accordance with the present invention;

0012<figref idref="DRAWINGS">FIG. 2</figref> is a schematic block diagram of a typical travel link;

0013<figref idref="DRAWINGS">FIG. 3</figref> is a flow diagram of the functions performed by the system of <figref idref="DRAWINGS">FIG. 1</figref>;

0014<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram of the data in the system of <figref idref="DRAWINGS">FIG. 1</figref>;

0015<figref idref="DRAWINGS">FIG. 5</figref> shows a matrix or table comprising typical input information for the system of <figref idref="DRAWINGS">FIG. 1</figref>; and

0016<figref idref="DRAWINGS">FIG. 6</figref> shows a matrix or table comprising typical output information from the system of FIG. <b>1</b>.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

0017Certain terminology may be used in the following description for convenience only and is not limiting. The words “right”, “left”, “upper” and “lower” designate directions in the drawings to which reference is made. The words “inwardly” and “outwardly” are further directions toward and away from, respectively, the geometric center of the Referenced element. The terminology includes the words above specifically mentioned, derivatives thereof, and words of similar import.

0018Referring to the drawings in detail, wherein like numerals are used to indicate like elements throughout, there is shown in <figref idref="DRAWINGS">FIG. 1</figref> a block diagram of a computer system <b>10</b> in accordance with the present invention. The computer system <b>10</b> may include a centralized main-frame computer having extended storage and processing capacity and the ability to interface with a plurality of local and remote external data sources, such as an IBM E90 mainframe computer. Alternatively, the computer system <b>10</b> may include a personal computer (not shown) having the proper power, programming, components, and external data access capabilities. For example, an IBM PS/2 Model 90 XP486 personal computer may be employed. However, one skilled in the art will recognize that the computer system <b>10</b> may be any computer system having the ability to perform the functions to be described below.

0019As seen in <figref idref="DRAWINGS">FIG. 1</figref>, the computer system <b>10</b> is bidirectionally linked to a plurality of data sources <b>12</b>, via a plurality of communications links <b>13</b>. Preferably, one of the data sources <b>12</b> is a computerized travel reservation system (CRS) <b>14</b>. The CRS <b>14</b> may comprise one or more of the computerized reservation systems widely used by travel agents to gather travel data and make travel reservations. Typically, such a computerized reservation system contains travel information on most if not all regularly scheduled travel services provided by most if not all major travel carriers. Such information includes, but is not limited to, the scheduled departure and arrival time for each travel service, the current fare or fares for the travel service, the number of travel services offered between a particular travel origin and a particular travel destination, whether a particular travel service requires a connection or stop-over, and if so, the connection or stop-over time, as well as other information relating to the travel services. As may be recognized, a connection comprises a physical change of travel vehicles at a connecting location while a stop-over comprises a stop at a connection location without a physical change of travel vehicles. Preferably, the computer system <b>10</b> can transmit information to as well as receive information from the CRS <b>14</b>. Such information may be transmitted and received via well-known protocols.

0020As should be recognized, the term “travel service” refers to airline travel if the travel provider is an airline, rail travel if the travel provider is a railroad line, and the like. As may be expected, though, the large majority of travel service provided will be air travel provided by air carriers. As should also be recognized, and as shown in <figref idref="DRAWINGS">FIG. 2</figref>, travel between a travel origin and a travel destination may be accomplished either directly or via a connection or stopover. For example, when traveling between Philadelphia. Pa. (PHL) and Palm Beach. Fla. (PBI), the CRS <b>14</b> may show a direct air flight <b>16</b> offered by USAir Airlines (US), and a series of connecting air flights <b>18</b>A from PHL to Newark, N.J. (EWR) and <b>18</b>B from EWR to PBI offered by Continental Airlines (CO). Thus, the travel link comprising the travel origin <b>20</b> of PHL and the travel designation <b>22</b> of PBI may be served by at least two carriers, with one carrier offering at least a direct flight <b>16</b> and the second carrier offering at least a series of connecting flights <b>18</b>A and <b>18</b>B. As is known, several other carriers may provide service for the PHL-PBI travel link, and those carriers may offer direct flights <b>16</b> and/or a series of connecting flights <b>18</b>A and <b>18</b>B connecting through several intermediary travel connections <b>24</b>.

0021Referring to <figref idref="DRAWINGS">FIG. 1</figref> again, the data sources <b>12</b> also preferably include an historical travel database <b>26</b> having information including, but not limited to, records concerning travel previously performed or arranged to be performed on behalf of the organization. Such information is preferably used to compile travel statistics for the organization, including the demand for particular travel links, and historical patterns for using particular travel carriers. However, one skilled in the art will recognize that the historical travel database <b>26</b> may also include other travel information pertinent to the organization, and that other pertinent travel statistics may be compiled or derived from the travel information.

0022Preferably, the data sources <b>12</b> further include a client or organization discount program database <b>28</b> including information from the organization representative of incentives and discounts the organization has negotiated with particular travel carriers. For example, a particular organization or client may have negotiated a discount from United Airlines (UA) wherein the organization automatically receives a ten percent discount on fares. Similarly, the organization may have negotiated a discount arrangement with American Airlines (AA) wherein the organization will receive a twenty percent discount on all fares only if the organization preferentially travels a particular travel link via the airline. Still further, the organization may have negotiated preferential seating arrangements with British Airways (BA) on flights to London only if the organization purchases a predetermined number of travel trips from the airline. Here, the term “travel trip” refers to a trip on a particular travel link.

0023Preferably, the data sources <b>12</b> also include particular client and/or organization information from the organization travel manager or the like <b>30</b>. Such information includes, but is not limited to, predetermined travel preferences an organization may have, travel policies or rules the organization may have, and the like. For example, an organization may wish to give a preference to Delta Airlines (DL) wherever possible, since the organization wishes to negotiate better travel incentives with carrier DL sometime in the future. Also, the information <b>30</b> may include details that the organization wishes to emphasize such as preferred connecting times, when to choose a direct route over a connecting route, the preferred times of day for departing and arriving, and the like.

0024As will be recognized, the data sources <b>12</b> may include other specific sources of electronic- and paper-based data and the like. Additionally, it will be recognized that information detailed above as being available from one particular data source <b>12</b> may in fact be available from another particular data source <b>12</b>.

0025Preferably, the computer system <b>10</b> includes a main processor <b>32</b> which has adequate power to receive and process large amounts of travel information from the various data sources <b>12</b>. One skilled in the art will recognize that any suitable processor <b>32</b> may be used in the computer system <b>10</b> without departing from the spirit and scope of the invention.

0026Travel information received by the processor <b>32</b> may be stored in a main memory <b>34</b> for immediate access or in a longer term storage <b>36</b> when immediate access is not necessary. One skilled in the art will recognize, however, that circumstances may require the exclusive use of the main memory <b>34</b> or the longer term storage <b>36</b>. Preferably, the main memory <b>34</b> is a semiconductor memory and the longer term memory <b>36</b> is a non-volatile memory such as a hard disk, magnetic tape. PROM or a floppy disk. However, the invention is not limited to such devices and suitable substitutes may be used.

0027Preferably, computer system <b>10</b> includes a printer <b>38</b> for printing output data <b>40</b> associated with the computer system <b>10</b>. Such output data <b>40</b> may include, but is not limited to, a travel analysis of an organization, information received by the computer system <b>10</b> from the data sources <b>12</b>, calculations performed on the information from the data sources <b>12</b>, and the like. Moreover, printer <b>38</b> may be employed to print output data <b>40</b> concerning the status of the computer system <b>10</b> or any of the data sources <b>12</b>. As will be recognized, printer <b>38</b> may be any suitable printer that can be interfaced with computer system <b>10</b> and processor <b>32</b>. Preferably, the printer <b>38</b> has the capability to print the information output from the computer system <b>10</b>.

0028Preferably, the computer system <b>10</b> includes a CRT or monitor <b>42</b> attached to the processor <b>12</b> to enable a user of the system <b>10</b> to view information associated with the computer system <b>10</b>. Also preferably, the computer system <b>10</b> includes a disk drive <b>44</b> for allowing the transfer of data between the computer system <b>10</b> and a remote location by means of a compatible floppy disk <b>46</b> or magnetic tape. As one skilled in the art will recognize, disk drive <b>44</b> and floppy disk <b>46</b> can be of any suitable type. Data received by the computer system <b>10</b> from the disk drive <b>44</b> may be actively used in the processor <b>12</b>, displayed on the monitor <b>42</b>, retained in main memory <b>34</b> or the longer term memory <b>36</b>, or a combination thereof. A keyboard <b>48</b>, also associated with the processor <b>12</b>, allows a user to actively input data into the processor <b>12</b>. The keyboard <b>48</b> may be a conventional ASCII or other type keyboard which is suitable for use with the processor <b>12</b>.

0029A scanner or a facsimile machine <b>50</b> may also be associated with the processor <b>12</b> to allow data in the form of a printed document <b>52</b> to be inputted to or outputted from the processor <b>12</b>. With the scanner or facsimile machine <b>50</b>, the printed document <b>52</b> can be scanned and transmitted in the form of electrical data signals to the processor <b>12</b> in the manner which is well-known in the art. The data signals may then be displayed on the monitor <b>42</b> or stored in the main memory <b>34</b> or longer term storage <b>36</b> for later use.

0030Data can also be received or transmitted from or to a remote location by use of a modem <b>54</b> via communications links <b>13</b>b or <b>13</b>c. As seen in <figref idref="DRAWINGS">FIG. 1</figref>, communications link <b>13</b>b interconnects the modem <b>54</b> with a remote modem <b>56</b> having direct access to at least one of the data sources <b>12</b>. Similarly, communications link <b>13</b>c interconnects the modem <b>54</b> with a remote modem <b>58</b> which can access at least one of the data sources <b>12</b> via a computer <b>60</b>. Still further, a communications link <b>13</b>a may directly interconnect the processor <b>12</b> with at least one of the data sources <b>12</b>.

0031Data may also be exchanged between at least one of the data sources <b>12</b> and the computer system <b>10</b> by way of floppy disk <b>46</b>, output data <b>40</b>, and/or printed document <b>52</b>. Accordingly, a computer <b>62</b> having access to a data source <b>12</b> would be provided with the proper disk drive, scanner, printer, and/or other data transfer device for purposes of inputting and outputting information. As one skilled in the art will recognize, other means for transferring data between the data sources <b>12</b> and the computer system <b>10</b> may be employed while still being within the spirit and scope of the present invention.

0032With the computer system <b>10</b> and data sources <b>12</b> as shown in <figref idref="DRAWINGS">FIG. 1</figref>, a travel scheme for minimizing travel costs for an organization is determined in the following manner. Preliminarily, an seen at step <b>301</b> in <figref idref="DRAWINGS">FIG. 3</figref>, the computer system <b>12</b> obtains the necessary travel information from the data sources <b>12</b>. The travel information obtained may be stored either in the main memory <b>34</b>, the longer term storage <b>36</b>, or both. Preferably, the processor <b>32</b> uses the information to construct a matrix or table (hereinafter “table”), as seen in FIG. <b>5</b>.

0033As seen in <figref idref="DRAWINGS">FIG. 4</figref>, the travel information comprises travel cost information <b>72</b>, demand and supply information <b>74</b>, and carrier goal information <b>76</b>. The travel cost information <b>72</b> is used to determine weighted values representative of the actual cost of traveling particular links using particular carriers. The demand and supply information <b>74</b> is used to determine link demand constraints <b>78</b> and carrier supply constraints <b>80</b>. The carrier goal information <b>76</b> is used to determine carrier goal constraints <b>82</b>.

0034The table of <figref idref="DRAWINGS">FIG. 5</figref> is organized in columns <b>64</b> and rows <b>66</b>, with each column <b>64</b> having information representative of a particular travel link and each row <b>66</b> having information representative of a particular travel carrier. Thus, a cell at the intersection of a particular column <b>64</b> and a particular row <b>66</b> holds information representative of a particular travel carrier serving a particular travel link, should in fact the carrier serve the link. As seen in the table, the travel carrier for each row <b>66</b> is identified in the left-most column and the travel link for each column <b>64</b> is identified in the upper-most row.

0035The table as described may have any number of rows <b>66</b>, each row <b>66</b> representing a travel carrier, and may have any number of columns <b>64</b>, each column <b>64</b> representing a travel link. Preferably, each carrier and each travel link included in the table is predefined according to client and/or organization information received from the travel manager <b>30</b>, as seen in FIG. <b>1</b>. However, such information could also be obtained from the historical travel database <b>26</b>, as well as other data sources <b>12</b>. In any case, it is preferable that the travel links appearing in the table are those travel links that are most often used by the travelers of the organization, and that the carriers appearing in the table are those carriers that have scheduled service for the aforementioned travel links, as well as those carriers with which the organization has arranged travel incentives.

0036Once the structure of the table is defined, the computer system <b>10</b> uses the travel cost information <b>72</b> obtained with respect to each link and each carrier serving that link to determine for each carrier serving each link a weighted value 68 representative of the actual cost of traveling the link using the carrier. Each weighted value 68 is preferably expressed in terms of monetary units (e.g. dollars), and is placed in the appropriate cell.

0037As an example, a weighted value 68 may take into consideration that a carrier charges an actual cost of C for a travel trip on a link, and that a discount of D percent is given to the organization. Thus, the weighted value 68=C* (1−D). If the weighted value 68 also takes into account that the carrier provides an upgrade worth U, then the weighted value 68=C*(1−D)−U. If the weighted value still further takes into account that all voyages on the link require a connection with a connection delay of H hours, and that the value of time is V, then the weighted value 68=C* (1−D)−U+V*H. As may be surmised, the weighted value 68 may take into account all factors that affect the cost of traveling a particular link using a particular carrier. Such factors may include probabilistic factors.

0038Thus, for each carrier serving each link, travel cost information <b>72</b> from the appropriate data sources <b>12</b> is obtained in order to determine such factors as the expected fare or fares of the carrier, any discounts the carrier provides to the organization, any added costs and any benefits received in connection with traveling the link using the carrier, the number of non-stop voyages and connecting voyages available on the link from the carrier, any expected transfer delays, and the percentage of total voyages the carrier provides for the link, as well as other pertinent travel information.

0039Preferably, the expected fare or fares that the carrier charges for traveling the link are obtained from the CRS <b>14</b> and/or the historical travel database <b>26</b> and take into account seasonal variations in the fares. Preferably, any discounts the carrier provides the organization is determined from the client or organization discount program database <b>28</b>, and takes into account any incentive the carrier may provide, as well as any negotiated arrangements the organization may have with the carrier. Preferably, any added costs and any benefits received in connection with traveling the link using the carrier include factors that either provide a benefit or a detriment to the traveler. For example, a benefit may be a seating upgrade or some other special service, and a detriment may be extra baggage costs or the like. Preferably, the number of non-stop voyages and connecting voyages available from the carrier for the link is obtained from the CRS <b>14</b>.

0040With all of the aforementioned factors, as well as others, the computer system <b>10</b> determines for each carrier serving each link a weighted value 68 representative of the actual cost of traveling the link using the carrier, and places the weighted value 68 in the appropriate cell, as seen in the table of FIG. <b>5</b>. Several cells are unoccupied, indicating that the carrier in the relevant row <b>66</b> does not serve the link in the relevant column <b>64</b> or that the carrier for other reasons should not be considered. Such a reason may be that the organization refuses to allow the carrier to serve its employees and/or representatives in connection with the relevant link, among other reasons. As one skilled in the art will recognize, the method for producing each weighted value 68 may be any one of several methods that properly takes into account each factor considered pertinent.

0041Each occupied cell is assigned a variable/designation <b>70</b> that both refers to the particular cell and acts as a variable representing the number of trips to be purchased from the carrier for the link represented by the cell.

0042For each link as represented by a column <b>64</b>, the computer system <b>10</b> determines a relative capacity for each carrier serving the link. The relative capacity is determined from information obtained from the CRS <b>14</b> and represents the relative service each carrier provides the link. The relative capacity may also be weighted depending on the type of service provided by the carrier for the link. For example, in the PHL-LHR (London, Heathrow, England) link, the carrier UA provides five percent of the voyages serving the link, carrier BA offers eighty-five percent of the voyages serving the link, and carrier AA offers ten percent of the voyages serving the link. As one skilled in the art will recognize, the relative capacity for each carrier serving a particular link may be readily determined based on the number of voyages offered by the carrier for the link and the total number of voyages offered by all carriers for the link, for example.

0043The demand and supply information <b>74</b> obtained by the computer system <b>10</b> is used to determine a projected demand for each link and a projected supply for each carrier, and may be received from several of the data sources <b>12</b>. For example, the historical travel database <b>26</b> may contain information showing that the organization has had an average demand of sixty-one segments for the PHL-BRU (Brussels, Belgium) link. Alternatively, client information from the travel manager <b>30</b> may reveal that because of an upcoming event, the organization will have a passenger demand of forty-eight segments for the PHL-MEX (Mexico City, Mexico) link. As will be recognized, the passenger demand for each link may be determined based upon any of several well-known techniques for forecasting demand. For example, the demand for a link may reflect actual past usage of the link as well as any projected changes. Similarly, the demand may reflect a projected usage based on expected travel needs. Once the passenger demand for each link is determined, such link demand information is organized in the table according to each link. Accordingly, and as seen in <figref idref="DRAWINGS">FIG. 5</figref>, the link demand information is found in the lowermost row.

0044From the link demand information and from the determined relative capacities for each carrier serving a link, carrier supply information may be determined. For example, since carrier AA in the table in <figref idref="DRAWINGS">FIG. 5</figref> has a relative capacity of seventy-five percent for link PHL-SJU (San Juan, Puerto Rico), and since the link PHL-SJU has a passenger demand of ninety-eight, it is to be expected that, absent other factors, seventy-five percent of the ninety-eight passenger demand or approximately seventy-four passengers would be served by carrier AA. Similarly, an expected number of passengers to be served may be determined from each of the other links served by carrier AA. The sum of all the expected passengers for all links served by carrier AA, one hundred ninety, represents the expected carrier supply or goal value 86 for carrier AA, absent other factors. Similarly, carrier supply information may be determined for each of the other carriers in the table.

0045Alternatively, carrier supply information for a particular carrier may be replaced by carrier goal information <b>76</b> which pertains to any predetermined goal the organization may have with respect to the carrier. For example, the organization may have previously negotiated a discount with carrier UA wherein the discount is received only if carrier UA receives a minimum predetermined amount of business from the organization. Such carrier goal information <b>76</b> is represented by a hurdle <b>84</b> of $100,000 in the right-most column at the row <b>66</b> for carrier UA, as seen in the table in FIG. <b>5</b>.

0046Alternatively, the carrier goal information <b>76</b> may represent a goal on the part of the organization to heavily support one carrier, or lightly support another carrier. In such a case, the carrier supply or goal value 86 originally determined to represent the anticipated carrier supply would be adjusted up or down, as the case may be, to represent a goal of the organization, and inserted in the table in <figref idref="DRAWINGS">FIG. 5</figref> in the right-most column at the row <b>66</b> corresponding to the relevant carrier as a carrier supply or goal value 86. As may be recognized, each carrier supply or goal value 86 may be adjusted freely depending on any maximum or minimum value the organization wishes to achieve. Thus, the rightmost column of the table of <figref idref="DRAWINGS">FIG. 5</figref> has values representing supplies and goals, each supply value 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 either above or below the supply value, and each goal value requiring that the goal the organization has with respect to a particular carrier be accomplished. As may be recognized, the demand and supply information <b>74</b> and the goal information <b>76</b> may be updated according to goals and supplies already fulfilled.

0047Once a table as seen in <figref idref="DRAWINGS">FIG. 5</figref> has been constructed from the information <b>72</b>, <b>74</b>, and <b>76</b>, the computer system <b>12</b> constructs an objective function, as seen at step <b>302</b> in FIG. <b>3</b>. The objective function represents the total travel cost to the organization for purchasing travel trips for travelers traveling on behalf of the organization on the plurality of predetermined travel links using the plurality of predetermined travel carriers. Preferably, the objective function comprises the sum of a travel cost for each link wherein the travel cost for each link comprises the sum of the travel cost for each carrier serving the link. In order to determine the travel cost for each carrier serving the link, the weighted value 68 assigned to the cell for the carrier serving the link is multiplied by the variable <b>70</b> representing the number of trips to be purchased from the carrier for the link.

0048For example, and with reference to the table of <figref idref="DRAWINGS">FIG. 5</figref>, since thirteen cells are occupied, the objective function constructed from the table would be the sum of thirteen factors, each factor comprising the weighted value in a particular cell multiplied by the variable <b>70</b> representing that cell. Specifically, the objective function would be: <br />($1496*x1)+($1760*x2)+($550*x3)+($3008* x4)+($1558*x5)+($1730*x6)+($355*x7)+($1474*x8)+($1804*x9)+($567*x10)+($3076 *x11)+($326*x12)+($1938*x13)

0049Since any travel scheme determined must minimize the travel costs for an organization, the objective function as constructed should be minimized. In order to do so, the computer system <b>12</b> constructs constraints, as seen in step <b>303</b> of <figref idref="DRAWINGS">FIG. 3</figref>, and applies the constraints to the objective function, as seen in step <b>304</b> of <figref idref="DRAWINGS">FIG. 3</figref>, in order to determine a solution of the objective function that satisfies the constraints and minimizes the travel costs of the organization. Accordingly, the constraints must be produced from the demand and supply information <b>74</b> and the carrier goal information <b>76</b> determined with respect to the organization and placed in the table of FIG. <b>5</b>.

0050Thus, each value in the lower-most row representing a passenger demand for a link is used to construct a link demand constraint <b>78</b>. For example, in the column <b>64</b> representing the PHL-MEX link, the link demand constraint <b>78</b> would require that the sum of the variables representing the number of trips to be purchased from each carrier for the link. i.e., x<b>3</b>+x<b>10</b>, be equal to the passenger demand of <b>48</b>. For the table of <figref idref="DRAWINGS">FIG. 5</figref>, five link demand constraints <b>78</b> are determined as follows:

0051<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="98pt" align="left" /><colspec colname="2" colwidth="91pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>x7 + x12 = 98</entry><entry>(PHL-SJU constraint)</entry></row><row><entry /><entry>x1 + x5 + x8 = 83</entry><entry>(PHL-LHR constraint)</entry></row><row><entry /><entry>x2 + x6 + x9 + x13 = 61</entry><entry>(PHL-BRU constraint)</entry></row><row><entry /><entry>x3 + x10 = 48</entry><entry>(PHL-MEX constraint)</entry></row><row><entry /><entry>x4 + x11 = 44</entry><entry>(PHL-EZE constraint)</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> (EZE represents Buenos Aires, Argentina).

0052Similarly, each value in the right-most column representing demand and supply information <b>74</b> or carrier goal information <b>76</b>, as the case may be, is used to construct carrier supply constraints <b>80</b> or carrier goal constraints <b>82</b>, as the case may be. For example, a hurdle <b>84</b> of $150,000 is seen in the right-most column in the cell corresponding to the row <b>66</b> for the carrier BA. Accordingly, the organization requires that at least $150,000 of business be given to carrier BA by purchasing trips on the PHL-LHR and PHL-BRU links from carrier BA. From the hurdle information in the table of <figref idref="DRAWINGS">FIG. 5</figref>, the following carrier goal constraints <b>82</b> are constructed:

0053<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="126pt" align="left" /><colspec colname="2" colwidth="77pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>$1600 * x1 + $1900 * x2 + $625 * x3 +</entry><entry>(UA hurdle constraint)</entry></row><row><entry /><entry>$3418 * x4 > = $100,000</entry></row><row><entry /><entry>$1750 * x5 + $1938 * x6 > = $150,000</entry><entry>(BA hurdle constraint)</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> The values $1600, $1900, $625, $3418, $1750, and $1938 are all assumed to be the actual pre-discounted costs charged by the various carriers for trips in connection with cells x<b>1</b>, x<b>2</b>, x<b>3</b>, x<b>4</b>, x<b>5</b>, and x<b>6</b>, respectively. Such pre-discounted costs are required in order to determine whether the hurdles <b>84</b> have been achieved.

0054Finally, carrier supply constraints <b>80</b> and/or carrier goal constraints <b>82</b> are constructed for each carrier where a carrier supply or goal value 86 is displayed in the right-most column in a cell corresponding to the row <b>66</b> of the carrier. For example, since the supply or goal value 86 of 17 has previously been determined for the carrier US in the table of <figref idref="DRAWINGS">FIG. 5</figref>, the variable x<b>12</b> representing the number of trips to be purchased from the carrier US for the link PHL-SJU should be greater than or equal to the carrier supply or goal value 86 of 17. Accordingly, the following carrier supply constraints <b>80</b> and/or carrier goal constraints <b>82</b> are constructed.

0055<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="126pt" align="left" /><colspec colname="2" colwidth="70pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>x7 + x8 + x9 + x10 + x11 >= 190</entry><entry>(AA constraint)</entry></row><row><entry /><entry>x12 >= 17</entry><entry>(US constraint)</entry></row><row><entry /><entry>x13 >= 3</entry><entry>(SN constraint)</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> (SN represents Sabena Airlines).

0056Although each of the above carrier supply constraints <b>80</b> and/or carrier goal constraints <b>82</b> requires the sum of the variables to be greater than or equal to the carrier supply or goal value 86, it should be recognized that an organization may choose to have the sum of the variables be less than the carrier supply or goal value 86 for any of a variety of reasons. For example, the organization may wish to limit business given to a particular carrier since the service provided by the carrier has been deemed sub-standard.

0057With the link demand constraints <b>78</b>, the carrier supply constraints <b>80</b>, and the carrier goal constraints <b>82</b> constructed, the processor <b>12</b> may then apply 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, as seen at step <b>304</b> in FIG. <b>3</b>.

0058Preferably, the table as seen in <figref idref="DRAWINGS">FIG. 5</figref> is embodied in a computer spreadsheet. Also preferably, the computer system <b>10</b> includes software for extracting information from the spreadsheet to construct the objective function and the set of constraints, and linear programming software for applying the constraints to the objective function to determine a solution. Preferably, the linear programming software includes the software for extracting the information.

0059As may be recognized, linear programming represents a technique for solving multi-variable systems in terms of a set of best values for maximizing or minimizing the system. Essentially, the linear programming allocates the trips to the carriers in accordance with the travel information and the constraints to provide a first test travel scheme, and determines the cost of the first test travel scheme. The trips are then re-allocated to provide a second test travel scheme, and the cost of the second test travel scheme is determined and compared with the cost of the first test travel scheme. The process is repeated until an optimum travel scheme minimizing the travel costs in accordance with the travel information and the constraints is determined.

0060Preferably, the linear programming software determines the solution according to a transportation algorithm. As one skilled in the art will recognize, a transportation algorithm minimizes the cost of a two-dimensional universe, each dimension having a plurality of members, subject to constraints on each of the members of each of the dimensions. More preferably, the spreadsheet is a “LOTUS-123”-type spreadsheet and the linear programming software comprises “WHAT'S BEST!” linear programming software, a product of Lindo Systems, Inc. of Chicago, Ill.

0061Preferably, the solution determined by the linear programming software is organized by the software in a table, as seen in <figref idref="DRAWINGS">FIG. 6</figref>, wherein the table corresponds to the table of the obtained information. Thus, easy reference may be made between the obtained information and the solution. As seen in <figref idref="DRAWINGS">FIG. 6</figref>, the solution comprises a solution value 88 for each variable <b>70</b>.

0062Preferably, the solution also comprises lower and upper limits <b>90</b>, <b>92</b> for each link demand value, carrier supply value, carrier goal value, and weighted value 68 (the weighted values 68 are shown as “net cost” in the table of FIG. <b>6</b>). The lower and upper limits <b>90</b>, <b>92</b> may be determined by the linear programming software. As may be recognized, each value may be adjusted between the limits <b>90</b>, <b>92</b> while still maintaining the determined solution. However, should a value change beyond a respective lower or upper limit <b>90</b>, <b>92</b>, the solution representing the minimum cost to the organization will have changed and a new solution must be determined.

0063Once the processor <b>12</b> determines the solution of the objective function that satisfies the constraints and that minimizes the travel cost to the organization, the computer system <b>10</b> preferably generates a report representative of the solution, as seen at step <b>305</b> of FIG. <b>3</b>. The generated report may be output via the printer <b>38</b>, the disk drive <b>44</b>, the scanner or fax <b>50</b>, the monitor <b>42</b>, and/or other means. Further, the generated report may be stored in the main memory <b>34</b> or the longer term storage <b>36</b>.

0064The report may take the form of the table shown in FIG. <b>6</b>. Additionally, the report may include the table of FIG. <b>5</b>. However, one skilled in the art will recognize that the report may present the solution in any of a plurality of ways using some or all of the obtained information, the solution values 88, the upper and lower limits <b>90</b>, <b>92</b>, and other information.

0065Once a report has been generated and reviewed, it may be determined that, for a plurality of reasons, a particular value should be changed. For example, a particular carrier goal value may have been set too high or too low, a hurdle <b>84</b> may have been changed, or a link may have been removed from consideration, among other things. Additionally, it may be recognized that a particular goal is unrealistic or inappropriate and should be ignored. In response to such a change, the information may be adjusted and a new solution may be obtained.

0066It will be realized that several iterations of such a process may be necessary before a travel, scheme is determined wherein the travel costs of the organization are minimized to the greatest extent possible. Once such a travel scheme is determined, the scheme must be implemented in order to realize the benefits thereof.

0067As may be recognized, travel arrangements made in connection with traveling on behalf of the organization may be set via a travel department of the organization, if one exists, or a travel agency of the organization. Accordingly, the implementation of the travel scheme requires that the travel department or travel agency be aware of the travel scheme, or at least the relevant portions of the travel scheme. For example, a travel agency setting travel arrangements for an employee wishing to travel the PHL-BRU link should at least be aware that carriers DA and SN are preferred. Additionally, the agency should be aware whether carriers BA or SN have already supplied the respective preferred number of travel trips 58 or 3, as determined by the solution values 88. As will be recognized, other information may be provided, preferably on a need to know basis.

0068In order that the travel agency be made aware of the necessary information from the travel scheme, the information must be communicated to the agency. Since a travel agency typically accesses travel information from a CRS <b>14</b> via a point of sale terminal (not shown), it is preferable that the information from the travel scheme be communicated from the computer system <b>10</b> to the travel agency point of sale terminal via the CRS <b>14</b>.

0069The computer system and method described above may be employed by a travel agency to provide a travel optimization service to one or more organizations, and the travel agency may charge a fee to each organization for providing the service. As may be recognized, at least a portion of the fee may comprise a portion of the savings realized to the organization by employing the travel optimization service.

0070In the foregoing description, it can be seen that the present invention comprises a new and useful computer system and method for determining a travel scheme that minimizes the travel costs of an organization. It will be appreciated by those skilled in the art that changes could be made to the embodiment described above without departing from the broad inventive concepts thereof. It is understood, therefore, that this invention is not limited to the particular embodiment disclosed, but it is intended to cover modifications within the spirit and scope of the present invention as defined by the appended claims.