Trip planner optimizing travel itinerary selection conforming to individualized travel policies5021953Abstract A travel planner system automatically constructs itineraries with available seats for a traveler's trip request which conform to pre-stored reasonableness standards which includes a satisfactory check on whether a connecting flight distance exceeds that of a possible direct flight by a preset distance or ratio. The system finds the fares in a process which includes constructing sum-of-segments fares for each such itinerary which are valid under all the applicable airline tariffs and rules, finds itinerary-with-fare combinations acceptable in terms of cost and convenience to the traveler in accordance with an individualized travel policy of the traveller, and displays at least some of the itineraries by departure or arrival time. Claims We claim: Description The appendix includes 4 fiche of 208 frames each and 1 fiche of 98 frames.
__________________________________________________________________________
MR DAVID WEBBER
OF TRAVELMATION, INC.
FROM LAGUARDIA
TO FORT MYERS
ON 5 JAN DEPART BETWEEN 8 AM AND 10 AM
RETURN 17 JAN
LEAVE AFTER 5 PM ARRIVE NO LATER THAN 9
__________________________________________________________________________
PM
In the above example the normal characters are a part of the template or are provided from a stored database, and the bold characers are keyed in by the travel arranger. At step 48 this information (the trip request) is sent to processor 18 in the manner earlier described, and at step 50 processor 18 searches traveller file 24 to locate the traveler record for this traveller, e.g., in a name search (or a search on some other appropriate basis). If the test at step 52 determines that there is no traveler record for this individual, the procedure ends so that the travel arranger (or a system administrator) can then create a traveller record, and the procedure can start again at step 46. After the test at step 52 shows that the relevant traveler record has been found in step 50, the system searches at step 54 for the policy record applying to this individual. This search at step 54 can be on the basis of a pointer contained in the traveller record (for each individual there is a travel policy record; the same policy record can apply to several individuals). The trip initialization procedure ends after it locates the traveller record and the policy record for the particular individual, and these records, together with the other information regarding the trip which the travel arranger has keyed in, become the "trip request" which is made available for the flight search procedure illustrated in FIG. 4. The purpose of the flight search procedure illustrated in FIG. 4 is to find all of the itineraries which could be used to satisfy the trip request being processed (e.g., for which flight and seats are available and which meet the constraints of the relevant policy file and traveller file and any other constraints that may have been keyed in FIG. 3) and to rank these candidate itineraries in terms of "non-preference" factors (e.g., wide body aircraft is better, stops are undesirable, etc.) and to rank them in terms of personal preference factors (e.g., this traveller prefers this particular airline and dislikes another airline, or wishes to avoid a particular airport, etc.). The output of this flight search procedure of FIG. 4 is a set of itineraries which have survived so far as candidates for this trip, ranked as stated, which can then be processed in accordance with the procedure of FIG. 5 to find the lowest fare candidate itineraries from which the travel arranger can select one for this trip request. The flight search process starts at step 56 with the first flight (or trip) request which has been processed through the steps of FIG. 3, and at step 58 searches tariff file 20 to find all airports to which there are direct flights from the origin of the trip being planned. Any airport which is found in this search is added to a temporary list called a From List. At step 60 processor 18 again searches tariff file 20, but this time for all airports from which there are direct flights to the destination location of the trip being planned, and places all finds in another temporary list called a To List. For example, if the origin is JFK airport and the destination is Los Angeles International airport, the From List would contain cities (in the U.S.A. in this example) such as Kansas City, St. Louis and Chicago which have direct flights from JFK, and the To List would contain those cities (again in the U.S.A. in this example) from which there are direct flights to Los Angeles International. In this example each of these two lists would contain well over 50 cities. At step 62 processor 18 starts a sequence designed to find candidate itineraries each of which would consist of connecting rather than direct flights. To start this, at step 62 processor 18 looks for possible 2-leg routes from the origin to the destination of the trip request being processed, by searching the From List and the To List for any airports which are in both lists and to thereby create another temporary list, of airports which are common to the From and To lists. For an airport to qualify for this Common Airport List there must be a direct flight leg from the origin (JFK) to that airport (e.g., Atlanta) and there must be a direct flight from that airport (Atlanta) to the destination (O'Hare). If the test at step 64 determines that the Common Airport List is empty, i.e., there is no airport to which there is direct flight from the oriqin and from which there is a direct flight to the destination (i.e., that there are no candidate 2-leg itineraries), the process goes to step 66 to see if any 3-leg itineraries can become candidates; to this end step 66 is a search in the tariff file and the From and To lists for all direct flights from any airport in the From list to any airport in the To list, i.e., to find each pair of airports in which (1) one of the airports in a pair is in the From List and the other is in the To List and (2) there is a direct flight between the airports in the pair. Stated differently, step 66 finds the intermediate leg in each of the possible 3-leg trips between the origin and the destination of the trip request. If the test at step 70 shows that there are no such 3-leg trips, the process ends because the system has not been able to automatically create an acceptable itinerary. If the list tested at step 70 is not empty (i.e., there are possible 3-leg itineraries between the origin and destination of the trip request being processed), or if the test in step 64 shows that there are 2-leg itineraries which are candidates, processor 18 at step 80 sorts the list of possibly acceptable connecting routes (found in steps 62 and 66) by total distance, i.e., by the sum of the distances of the legs of each candidate multi-leg route. At this stage, processor 18 has created a list of all multi-leg routes which so far conform to the trip request constraints and therefore are candidate routes or itineraries. At the next step, 82, processor 18 looks for possible direct flights from the origin to the destination which would be candidate itineraries, by searching tariff file 20 to find all direct flights which are within a set time, e.g., two hours, of the desired time window. If the test at step 84 shows that there are such direct flights, the process enters a sequence to see if these flights have seats available and, to this end at step 86 it establishes a connection with an airline reservation system such as Apollo and interrogates it for seat availability on each of the flights found in step 82 (direct origin-to-destination fights), and temporarily stores the information from Apollo identifying what seats are available and in what class or classes. If the test at step 88 shows that there are flights (direct) with seats in the desired class and in the desired time window, processor 18 at step 90 checks if connecting flight routes are allowed for this trip request, as specified in the procedure of FIG. 3 or as specified by the applicable traveller and/or policy records in traveller file 22). If connecting flights are allowed, processor 18 goes to step 92 to start processing the multi-leg routes sorted in step 80. Note that step 92 can be reached directly from the test at step 84 if it shows that there are no direct flights from the origin to the destination of this trip request, and from step 88 if the test there shows that there are no direct flights with seats in the desired time window. In order to further process the connecting flight routes which are candidates at this stage, at step 92 processor 18 starts with the first connecting route in the list sorted at step 80, and at step 94 checks if the connecting route under consideration makes sense i.e., conforms to a pre-stored reasonableness standard if (1) the connecting route distance is greater by a preset distance, e.g., 250 miles, than the shortest possible route (the route from the origin to the destination found up until that point for which there are seats) and (2) the distance ratio (of the currently investigated connecting route and the same shortest possible route) is greater than a preset amount, e.g., 1.2. If the answer is negative to either inquiry, this means that the connecting route is still a candidate, and processor 18 goes to step 96 and interrogates tariff file 20 to find each direct flight which (1) is from the trip origin to the first connect point of the connecting route under consideration, (2) is on the desired departure date and (3) departs within two hours of the desired time window for this trip. If the test at step 98 shows that the search at step 96 was successful, i.e., there are direct flights meeting the constraints of step 96, processor 18 at step 100 interrogates the airline reservation system (e.g., Apollo) for seat availability (by class) on each of the flights found in step 96 and stores the seat availability information. If the test at step 102 shows that there are flights (found in step 96) with seats, processor 18 at step 104 stores the earliest arrival time of a flight with seats found at that stage, and at step 106 checks if the itinerary under consideration has two connecting points (i.e., if it is a 3-leg itinerary). If there are two connect points, at step 108 processor 18 interrogates tariff file 20 to find all connecting flights from connect point 1 (at the end of the first leg) to the next connect point which is on the desired departure date and is in the time span from the earliest arrival time stored at step 104 to, say, two hours after the time window desired for this trip (and set at step 46, FIG. 3). If any flights are found in the search at step 108, as determined in the test at step 110, processor 18 at step 112 interrogates the airline reservation system for seat availability, by class, on the flights found in step 108 and temporarily stores the seat availability information. If there are such flights with seats, as shown by the test at step 114, processor 18 at step 116 stores the earliest arrival time of such a flight with seats, and at step 118 interrogates tariff file 20 to find direct flights from the last-considered connect point to the destination of the trip which is on the desired departure date and is in the time span from the earliest arrival time stored at step 116 to, say, two hours from the desired time window for this trip. Note that step 118 can be reached directly from step 106 if the test there gives a negative answer, i.e., if that test shows that the itinerary under consideration has only 2 legs. If the test at step 120 shows that the search so far was successful in finding suitable flights for the second or third leg of the itinerary under consideration, at step 122 processor 18 interrogates the airline reservation system for seat availability on each of these flights and stores the seat availability information (by class). If the test at step 124 shows that there are such flights (found in step 118) with seats, at step 126 processor 18 lists all combinations of flights which meet the connecting time requirements discussed above at each connecting point of the route found through the last run through steps 92-124, and goes to step 128 to similarly process the next connecting route from the list sorted at step 80. Note that step 128 can be reached directly from any one of steps 98, 110, 114, 120 and 124 if the tests there give the indicated results leading directly to step 128 (i.e., if the consideration of one connecting route shows that it is not suitable, the process goes to step 128 to start checking another such route). If the test at step 130 shows that there are yet-to-be-processed connecting routes in the list sorted at step 80, processor 18 returns to step 94 to start similarly processing the next route from that list. If the test at step 130 shows that all of the multi-leg routes sorted at step 80 list have already been processed, processor 18 goes to step 132, which can also be reached directly from any one of the tests at steps 90 and 94 if the tests there lead directly to step 132 as indicated. If the test at step 132 shows that no itineraries were found in the desired time window for the trip request being processed, the test at step 134 checks if the time window is as wide as possible, e.g., if it is the entire desired day for the trip. If it is, the process ends because it was not possible to find a satisfactory itinerary given the constraints of the trip being processed (another trip request can be started as in FIG. 3, with different parameters). If step 134 shows that the time window for the trip is not all day, processor 18 widens it at step 136 by a set period, say, two hours, but not out of the desired day, and the process returns to step 82 to look for an itinerary conforming to the same trip request but with the widened time window. If the test at step 132 shows that there are itineraries which meet the desired trip parameters, at step 138 processor 18 interrogates these itineraries to find the one with the lowest number of stops and connections and the least trip time, and at step 140 checks the list of possible itineraries remaining after step 132 and the traveller file (the relevant policy record and traveller record for the trip being processed) and eliminates all itineraries which have more stops or connections than allowed by the particular policy and/or traveller record (or override entries at FIG. 3) or take more than a set amount of time longer than the quickest itinerary, again on the basis of the parameters set in the particular policy and/or traveller record and/or overrides. For each of the candidate itineraries which remains after step 140, the processor at step 142 calculates a "non-preference" rank and at step 144 calculates a "preference" rank, e.g., by using the calculations illustrated at steps 142 and 144, respectively, in the drawing. The non-preference ranking addresses generally desirable or undesirable aspects of travel while the preference ranking addresses the particular preferences of the traveller being serviced. For example, at step 140 an itinerary is ranked by adding to its initial rank of 1000 points (10 in this example) if only wide-body aircraft is used in it, subtracting 10 points for each stop in the itinerary, etc. At step 144, the rank starts with the rank resulting from step 142 and point are added or subtracted depending on the personal preferences of the particular traveller: e.g., add 100 points for each flight leg in the itinerary on an airline which this traveller prefers but subtract 100 points for each leg on an airline which this traveller dislikes, etc. These personal preferences can be entered in the FIG. 3 procedure, or they can be made a part of the traveller record or policy record for that traveller in traveller file 22 and extracted therefrom as needed by processor 18. If the test at step 146 shows that there are more flight requests entered through the procedure of FIG. 3 (e.g., an outbound trip can be one request and an inbound trip can be another request), processor 18 returns to step 58 to start similarly processing the next trip request entered in the FIG. 3 procedure; if there are no more flight (or trip) requests the process of searching for suitable itineraries ends and processor 18 goes to the fare search process illustrated in FIG. 5 to find the best fares for the candidate itineraries. In FIG. 5 the purpose is to find the best (lowest) valid fare for each of the candidate itineraries (direct flight and multi-leg routes) remaining after the FIG. 4 procedure, so that this information can be used in the procedure in FIG. 6 to find the several best itineraries from which the travel arranger can select the one to be used for this trip. The procedure in FIG. 5 finds the least costly but still valid fare for each leg of each multi-leg route which is still a candidate, the least costly but still valid sums of segment fares for each such multi-leg route (and thus the cost of each candidate itinerary using connecting flights), and the least costly but still valid end-to-end (or through) fare for each itinerary (direct or connecting) which is still a candidate for the trip request being processed. The FIG. 5 process starts at step 148 with the first flight request which was entered in the process of FIG. 3 and processed through the steps of FIG. 4, and at step 150 checks if the process of FIG. 4 produced any connecting flight itineraries which are still candidates for this trip (as ranked at steps 142 and 144 there). If it did, processor 18 at step 152 starts with the first connecting route for which the process of FIG. 4 found a candidate itinerary, and at step 154 starts with the first segment of that route where a "segement" is a direct flight between two airports. An example is an itinerary consisting of a direct flight from Washington, D.C. (DCA) to Chicago (ORD), connecting within two hours from arrival at Chicago to a direct flight from ORD to San Francisco (SFO), with an overnight stay in San Francisco and a direct return flight from SFO to DCA. This is a round-trip itinerary which has two segments in the outbound part from DCA to SFO and one segment in the inbound part from SFO to DCA. In this example, the invented system checks if the "sum-of segments fare" resulting from adding the individual fare for the direct flight from DCA to ORD and the individual fare for a flight from ORD to SRO, would provide a greater benefit than, say, using a one-way fare from DCA to SFO or a round-trip from DCA to SFO and back to DCA. At step 156 processor 18 interrogates tariff file 20 to find the all fares for the city pair at the origin and destination of this route segment, starting with the lowest fare. At step 158 processor 18 checks tariff file 20 to see if the fare found in step 156 is a round-trip fare, or if the flight of interest at the time is outside of the effective dates for the fare. Because round trip fares are considered undesirable at this stage of the process, and because flights outside the effective date for the segment fare are not of interest at this time, if the answer at step 158 is yes this fare should not be kept as a candidate and processor 18 therefore jumps to step 180 to see if there are any more fares for this segment of this route. If the answer at step 158 is no (i.e., this fare is still a candidate), at step 160 processor 18 starts with the first flight with that fare which is used in at least one of the itineraries which are still candidates, and at step 162 checks if the lowest valid fare for that flight has been found yet (by interrogating tariff file 20). If the answer at step 162 is no (and the process is forced to answer no for the first pass through that step 162), at step 164 processor 18 checks if the fare is current for the airline in question and, if it is, gets the routing and footnotes for that fare form tariff file 20 at step 166 and then checks at step 168 if the route used is invalid and if the route used or the flight date violate a footnote, the check being against the routing and footnotes extracted at step 166. If the answer at step 168 is no (i.e., if the route is valid and no footnote is violated), at step 170 processor 18 gets from tariff file 29 the rule for that fare and at step 172 checks the fare to see if it is valid for the flight and date under consideration at that time, if any penalty fares are allowed (as determined by the trip request; a penalty in this context is, e.g., a trip cancellation penalty) and if the fare is a non-penalty fare. If the answer is yes (i.e., the fare is valid for this flight and date and either it is not a penalty fare or penalties are allowed for this trip), processor 18 stores this fare at step 174 for later use in the process, calling it at this time "the lowest valid fare" for the flight. At step 176 processor 18 checks if it has already found the lowest valid fare for all flights in the itinerary under consideration and, if the answer is no, checks at step 178 if there are more flights for this leg of the trip. If there are no more such flights step 180 checks if there are any more fares to be checked; if there are no more such fares, step 182 checks if there are any more segments in the itinerary under consideration and, if there are no more such segments, the process goes to step 184, where processor 18 uses information from step 174 to compute the sum of the lowest segment fares for each of the itineraries which are still candidates at this stage of the process. If the test at step 186 shows that there are no more connecting routes with candidate itineraries to be processed at that stage, at step 188 processor 18 gets from tariff file 20 all the fares which are through, or end-to-end, fares for routes from the origin to the destination of the flight request being processed (as distinguished from multi-leg routes assembled in accordance with the process described above), and at step 190 starts with the lowest of the through fare found at step 188 and sets a variable "highest allowed fare" to a high value unlikely to be exceeded by a real-life fare (e.g., to $10,000). At step 192 processor 18 checks if the current through fare under consideration is higher that the highest allowed fare and if so jumps to step 220 to find the best itineraries. if not, processor 18 checks at step 194 if same current through fare under consideration is a round-trip fare and if the flight date is outside the effective date range for that fare. If the answer to both questions is no, processor 18 starts at step 196 with the first itinerary which is still a candidate and at step 198 checks if the current through fare under consideration is more than the sum of the segment fares for the same itinerary or is more than the lowest through fare found up until that time for the same itinerary. If the answer is no to both questions, processor 18 at step 200 checks if the fare is for the correct airline and checks at step 202 if the route used is invalid and if the route or flight date violate the relevant footnotes in tariff file 20. If all answers at step 202 are negative (i.e., the fare is still a candidate), processor 18 starts at step 204 with the first rule containing this fare (in the tariff file) and at step 206 checks if the through fare under consideration is valid, and if penalty fares are allowed for this trip request or the fare is not a penalty fare. If the answer is no to any of these questions (i.e., the fare is not valid, or the fare is a penalty fare and penalty fares are not allowed for this trip request), the process loops through all the rules (from tariff file 20) which may apply, by going through step 208 and returning to step 206 from there, until the test at step 208 shows that there are no more rules containing the fare. When the answer at step 208 is no, this means that this fare cannot be used, and the process goes to step 216 to see if there are more itineraries to consider. If step 206 gives a yes answer, this means that this through fare is still a good candidate, and the process jumps to step 210 to save this fare as the lowest through fare for this itinerary. At step 212 processor 18 checks if this is the lowest penalty adjusted fare so far (using for this calculation the information on penalty adjustments contained in the policy record in traveller file 22) and adds the fare allowances specified in the policy record to find the new, updated "highest allowable fare." If the test at step 214 shows that the lowest fare has not been found for all of the itineraries which are still candidates for the trip request being processed, the process checks at step 216 if there are any more candidate itineraries and, if the answer is no, checks at step 218 if there are any more fares to be checked through a similar process. If the answer at step 218 is no, the process checks at step 218 if there are any more flight requests to process similarly and, if the answer is no, goes to step 220, which is an exit to the "best flight search" illustrated in FIG. 6. The best fare search process illustrated in FIG. 5 loops as needed depending on the answers at the test points, in the manner illustrated in the drawing, to ensure that the fares and itineraries remaining for use in the best flight search process are still candidates which conform to the constraints of the tariff file, the traveller record and the policy record for the trip being processed and, of course, the parameters of the trip entered during the process illustrated in FIG. 3. Thus, if the answer at step 150 is no, the process jumps to step 188 to start looking at through fares because step 150 has shown that there are no multi-leg itineraries found through the process of FIG. 4. If the answer at step 158 is yes (i.e., this fare is not suitable), the process jumps to step 180, to see if there are any more fares to consider. The process jumps to step 178 to see if there are any more flights to consider: if the answer at step 162 is yes (i.e., the lowest fare for this flight has already been found), or the answer is no at step 164 (i.e., this is not a current fare for this airline), or the answer is yes at step 168 (i.e., this route is not suitable or the flight date is not good), or the answer at step 172 is no (i.e., this fare is not valid for this flight and this date, or this is a penalty fare but penalty fares are not allowed for this trip). If the answer at step 176 is yes (i.e., the lowest fare has already been found for all flights in this segment of this route), the process jumps to step 182 to see if there are any more segments in this route so they can be similarly processed. If &:he answer at step 178 is yes (i.e., there are more flights for this segment or leg of this route), the process returns to step 162 to see if the lowest fare for the next candidate flight has been found yet. If the answer at step 180 is yes (i.e., there are more fares for this leg of this route), the process returns to step 150 to start checking the next fare for this leg of this route to see if it should remain a candidate fare. If the answer at step 182 is yes (i.e., there are more segments in this route), the process returns to step 156 to start processing the next candidate segment in this route. If the answer at step 186 is yes (i.e., there are more connecting routes with itineraries which are still candidates), the process returns to step 154 to start processing the next candidate route. If the answer at step 192 is yes (i.e., this through fare is higher than the highest allowed fare at that stage), the process jumps to step 220 because the through fare clearly could not be more desirable. If the answer at step 194 is yes (i.e., this through fare is a round trip fare or the flight is outside the effective date range for this trip request), the process jumps to step 218 to see if there are any more fares to process similarly. FIG. 6 illustrates the process which searches for the best itineraries which have remained as candidates for this flight request after the process of FIG. 5. The product of this process is a selected small set of candidate itineraries (e.g., six) from which the travel arranger can select one to be actually ticketed. The process of FIG. 6 starts at step 222 with the first of the candidate itineraries remaining after the process of FIG. 4, and at step 224 checks if the penalty adjusted fare (found at step 210) for this itinerary is higher than the maximum fare allowed (found in step 212) for this flight request. If it is not (i.e., if the fare now being considered is still a good fare), step 226 checks if the itinerary is within the time window set for this trip and, if it is, step 228 checks if this itinerary has the highest non-preference rank so far (as computed at step 142). If it does, this itinerary is saved at step 230 as the "best non-preference" itinerary. At step 232 the process checks the same itinerary to see if it has one of the six best preference ranks found so far and, if its does, it is saved at step 234 as one of the six best "preference" itineraries, and the process goes to step 240, to check if there are any more candidate itineraries to be processed similarly. If there are, the process returns to step 224 and starts with the next candidate itinerary. If at step 226 the test shows that the itinerary being processed is not inside the desired time window for the trip, the process jumps to step 236, to check if this itinerary is one of the two best preference rank itineraries outside the desired time window for this trip and, if it is, it is stored as such at step 238. If the test at step 228 shows that the itinerary being tested does not have the highest preference rank so far, the process jumps to step 232 for the check if this itinerary has one of the six highest preference ranks so far, and if it does not, the process jumps to step 240 to see if there are more itineraries to be processed. Similarly, if the itinerary tested at step 236 is not one of the two best preference itineraries outside the desired time window for this trip, the process jumps to step 240 to see if there are more candidate itineraries to consider. Once the test at sep 240 shows that all candidate itineraries have been processed through this step of FIG. 6, the process at step 242 selects the two best preference itineraries outside the desired time window (as saved at step 238, or the single such itinerary if only one was found, or none if none was found) and at step 244 selects the best non-preference itinerary saved at step 230, but deletes it from the list of candidate itineraries if it is also one of the six best preference itineraries saved at step 234. At step 246 processor 18 selects as many of the best preference itineraries (from step 234) as are needed to bring the total selected itineraries (selected in steps 242, 244 and 246) to six, or selects all of the best preference itineraries if there are not enough other selections to bring the selections to a total of six, and at step 248 processor 18 sorts the selected itineraries by departure time and displays those itineraries, together with the best fares for them, on the screen of the travel arranger's equipment (where they can be printed out if desired). At this stage the processor has supplied to the travel arranger up to six candidate itineraries, of which (1) up to two are the best "preference" itineraries which are outside the time window for this trip request (i.e., the up to two least costly candidate itineraries given the various constraint discussed above, including the personal tastes of the traveller for factors such as choice of airlines and airports), (2) up to one "non-preference" itinerary (i.e., the least costly candidate itinerary given all the same constraints but not the personal tastes of the needed to bring the total number to six) of the best "preference" itineraries. The itineraries in category (1) are presented so that the travel arranger can decide if the cost is attractive enough to justify changing the trip request (e.g., if the original trip request said that there should be no departures earlier than 7 A.M. but the itinerary in category (1) starts with a 6:50 A.M. flight and is much cheaper than the others, the traveller may elect to take it). FIG. 7 illustrates an optional process for finding the least costly round-trip itinerary for a trip request, for example so that it could be compared with a trip using separate outbound and inbound fares or so that the round trip fare could be used in case the traveller would accept the restrictions that may be attached to such a fare. In the process of FIG. 7, at step 250 processor 18 searches tariff file 20 to find the candidate end-to-end fares for the city or airport pair specified in the trip request (e.g., JFK-O'Hare) in the trip initialization process of FIG. 3. At step 252 the process searches tariff file 20 to get the N (where N is a selected positive integer, e.g., six) sums each resulting from adding the lowest outbound one-way fare to the lowest inbound one-way fare for the trip request (e.g. JFK to O'Hare and O'Hare to JFK), and sets N respective variables called "lowest-fares-so-far" equal to these sums. At step 254 the process starts with the lowest candidate round trip (end-to-end) fare found in step 250 and compares it to the lowest-fares-so-far, and tests at step 256 which is higher. If the candidate round trip fare is higher, the process ends, because there is no price advantage to possibly offset the restrictions and inconvenience of a round trip fare. If the candidate round trip fare turns out to be less costly in the test at step 256, the process checks at step 258 if there are any flight dates in the trip being processed which are outside of the effective dates for the round trip fare being considered. If there are trip dates outside the effective dates for the candidate round trip fare, this round trip fare is not suitable, and the process jumps to step 294, to see if there are other round trip fares to be considered and, if there are, another round trip fare starts being processed back at step 256. If the test at step 258 shows that there are no flight dates outside the effective dates for the currently evaluated round trip fare, i.e., that this round trip fare is still a candidate, the process starts at step 260 with the first outbound itinerary for the trip being processed, and at step 262 checks if this round trip fare is valid for this itinerary, using the checking process discussed in connection with the fare search operations illustrated in FIG. 5. If the test at step 262 shows that this round trip fare is not valid for this first outbound itinerary the process jumps to step 290 to check if there are any more outbound itineraries. If the round trip fare is valid for the outbound itinerary the process in steps 260 through 270 checks whether the round trip fare is also valid for any inbound itinerary. If so it is saved at step 268 as one of the N "lowest-fares-so-far" and the process checks at step 270 if there are any more candidate inbound itineraries. If the answer is no, the process starts with the next round trip fare and checks at step 274 if the sum of this fare and this outbound fare is higher that the N lowest-fares-so-far. If the answer is no, the process checks at step 275 if the flight dates are outside the effective dates for this fare and, if the answer is no, checks if this inbound fare can be combined with this outbound fare. If the answer is yes, the process starts with the first inbound itinerary at step 280 and at step 282 checks if the fare is valid for this itinerary, using the fare search process discussed in connection with FIG. 5. If this test shows that this fare is valid, it is saved as one of the N lowest-fares-so-far at step 284. If it is not, the process checks at step 286 if there are any more inbound itineraries; if the answer is no, it checks at step 290 if there are any more outbound itineraries to be considered and, if the answer is no again, repeats the same procedure but this time starting with the inbound itineraries. After exiting from step 292, the process checks at step 294 if there are any more fares to consider and, if the answer is no, displays at step 296 the N itineraries with fares at the screen of the travel arranger's equipment. FIG. 8 illustrates the final stage in the processing of a trip request, the building up of what the industry calls a passenger name record or PNR. This stage is entered after the best itinerary has been selected automatically in accordance with this example of the invention and the travel arranger has been presented with the several best choices and has selected one of them for this trip. The process of FIG. 8 starts with the first flight leg of the selected itinerary at step 300 and at step 302 carries out the protocol for selling this flight leg using the appropriate airline reservation system format (e.g., the Apollo format). At step 304 processor 18 checks if there are any more legs (flights) in this itinerary, and loops through steps 302 and 304 until all flight legs have been sold in the same manner. At step 306 processor 18 supplies the name of the passenger (from the trip request entered in the procedure of FIG. 3), and in step 308 constructs a normal ticket delivery date, for example two weekdays before the trip or the number of days specified in the policy record which applies to this trip. Processor 18 then displays at step 310 the delivery date on the screen of the travel arranger's equipment, and asks the travel arranger to key in any change that may be desirable. At step 312 the processor asks the travel arranger for a delivery address such as the traveller's business or home address, or a special address (if such an address is allowed by the policy), or allows the travel arranger to specify that the ticket will be picked up at the airport from which the traveller will be leaving (as long as the traveller is not charging the trip to someone else). At step 314 processor 18 uses the information from the current traveller record and/or policy file to enter the indicated information in the transaction record. starting with the first sold flight at step 316, enters at step 318 a seat and boarding pass request for each passenger into the airline reservation system (e.g., Apollo). If at step 320 the Apollo system responds with an error message (because boarding passes are not allowed for this flight at this time), the process at step 322 enters into Apollo the seat request for all passengers without boarding passes, and checks at step 324 if there are any more flights in this itinerary. If there are no more such flights, at step 326 processor 18 enters into the Apollo system the frequent flier numbers of all passengers for all airlines, and at step 328 checks the trip request (and, if desired, the traveller and policy records) any special requests, such as special meals or meet-and-assist requests. If there are such requests, the process starts at step 330 with the first flight in this itinerary and at step 332 enters into Apollo the relevant special requests and loops through all flights in the itinerary until it exits through the negative answer at step 336. At step 338 processor 18 enters into the record for this itinerary the full price for a regular ticket for this trip, the savings because of the actual price for the itinerary selected through the invented process and the date of the trip, and also enters any remarks that may be required to be entered into this trip record by the pertinent policy record. At step 342 the PNR process is ended, the itinerary normally provided by the reservation system is printed (and, if desired and allowed at that location, the ticket is printed as well) and the printed material is placed in an appropriate queue for any further manual processing that may be appropriate. As a simplified example of processing a particular trip request in accordance with the invention, consider a form used to make a flight request:
______________________________________
From: NYC-NEW YORK CITY
To: LAX-LOS
Date: 2/3/88 ANGELES INTL.
Departure time Arrival time
Earliest: 8:00 A.M. Earliest:
Latest: 10:00 A.M. Latest: 3:00 P.M.
Preferred: 9:00 A.M. Preferred:
Allow penalty fares: N
______________________________________
The above flight request is from any New York City airport (NYC is the code used by the airline industry for New York City) to Los Angeles International Airport (LAX is the code used by the airline industry for that airport) on February 3rd, 1988. The traveller wishes to depart no earlier than 8 a.m. and no later than 10 a.m., and would prefer to leave as close to 9 a.m. as possible. The traveller further wishes to arrive at LAX no later than 3 p.m. The use of penalty fares (i.e. fares with a penalty for changing or cancelling flights) are not allowed for this trip. To provide a simple example of how the exemplary system finds the appropriate itineraries, assume further that the travel policy being used allows the traveller to travel first class and does not allow the use of connecting flights if direct flights are available. The process would be as follows: 1. Find all cities to which there are direct flights from any New York City airport assume that there are 120 such cities. 2. Find all cities from which there are direct flights to Los Angeles International airport--assume there are 105 such cities. 3. Find all cities that are in both lists found in steps 1. and 2. assume that there are 40 such cities. 4. Sort the possible routes (including flying direct) by mileage. 5. From the tariff file find all direct flights from any New York Airport to Los Angeles International on Feb. 3rd, 1988, departing between 6 a.m. and noon and arriving no later than 5 p.m. (the time window by two hours in each direction). Suppose that there are 15 such flights. 6. Send a seat availability request to Apollo for flights from NYC to LAX on February 3rd, 1988 departing from 6 a.m. on. This returns seat availability for up to eight flights. Ask for seat availability for eight more flights, and continue to do so until seat availability for all 15 flights has been found or there are no more flights for February 3rd. 7. Eliminate any of the 15 flights for which there are no first class seats available. Suppose that 2 such flights are eliminated, leaving 13 possible flights. 8. Suppose that 8 of the 13 flights are non-stop, that the fastest one takes 5 hours 30 minutes, and that the travel policy allows no extra stops, and a maximum time of 2 hours more than the fastest flight. This eliminates any flight that has a stop and any flight that takes more than 7 hours 30 minutes, leaving say 8 flights. 9. Compute the preference and non-preference ranks for each flight. In the non-preference ranking wide-body jet flights leaving close to 9 a.m. will have the highest rankings. Suppose that the traveller likes United Airlines, and would rather not leave from Newark Airport. Then in the preference ranking the flights on United Airlines would have 100 additional points. The highest ranked flights would be United Airlines flights leaving from JFK airport close to 9 a.m. Note that the highest non-preference rank might be a Continental Airlines flight leaving Newark at 9 a.m. precisely, but that the highest preference rank might be a United Airlines flight leaving JFK at 9:30 a.m. 10. From the tariff file get all the possible fares from NYC to LAX. Suppose that there are 2,000 such fares. Start at the lowest such fare--say $180. 11. Check if the valid dates for the fare include Feb. 3rd, 1988, and that the fare is not a round trip fare. If so, for each itinerary check if the fare is for the right airline, and is valid according to the footnote, routing and rules for the flight. In this case, since the request is for a non-stop first class flight the fare might be rejected because it is not a first class fare or because it requires a connection or both. 12. Continue looking through the list of fares until a valid fare is found for an itinerary most fares will be rejected because they are not first class, eventually there might be a fare that is a first class fare but which requires that the flight be a `night flight` by the airlines definition. If one of the 8 flights left is a ,night flight, perhaps departing at 6 a.m. the fare will be valid for that flight, but not for other flights for the same airline leaving later in the day. Another first class fare might be valid only for flights between the Continental U.S. and Hawaii, and will be rejected for that reason. 13. Eventually a valid fare will be found for a flight within the time window--say for $600. Suppose that the travel policy allows the Trip Planner to use a fare that, after applying any penalties, is no more than $100 above the lowest penalty adjusted fare (in this case $600) found. The search for the lowest valid fare on each itinerary (in this case flight) will continue until such a fare is found for each itinerary, or until the next fare in the list is more than $700. Suppose that when that happens fares have been found for 7 of the 8 flights. 14. Among the flights left, find the two best flights outside the 8 a.m. to 10 a.m. departure window or outside the up to 3 p.m. arrival window that have the best preference ranks. This might be a 7:30 a.m. United flight from JFK and an 11 a.m. United flight from JFK. Also find, among the flights that are inside the departure and arrival window, the one with the best non-preference rank--perhaps a 9 a.m. Continental flight from Newark. Since 3 flights have been selected so far now choose from among those flights inside the departure and arrival windows the 3 flights (other than the flight chosen as having the best non-preference rank) with the best preference ranks. These might be a United 9:30 a.m. flight from JFK, an American 8 a.m. flight from JFK and a United 9:15 a.m. flight from Newark. 15. Sort the 6 chosen flights by departure time and display them to the travel arranger as shown below:
__________________________________________________________________________
Airline Flight
From
Time To Time Fare
__________________________________________________________________________
UA-UNITED 101 JFK 7:30 A.M.
LAX
10:30 A.M.
$550
AA-AMERICAN
212 JFK 8:00 A.M.
LAX
11:00 A.M.
$700
CO-CONTINENTAL
057 EWR 9:00 A.M.
LAX
12:00 NOON
$625
UA-UNITED 156 EWR 9:15 A.M.
LAX
12:15 P.M.
$650
UA-UNITED 105 JFK 9:30 A.M.
LAX
12:30 P.M.
$650
UA-UNITED 110 JFK 11:00 A.M.
LAX
2:00 P.M.
$650
__________________________________________________________________________
UA, AA and CO are the codes used by the airline industry for United Airlines, American Airlines and Continental Airlines respectively. The travel arranger can then choose one of the flights shown--probably United flight 105, but possibly United flight 101, since it is $100 cheaper and leaves only 30 minutes outside the departure window. As further background information, attached are: Appendix A, which illustrates definitions for translating (formatting) the rules supplied from a commercial service auch as ATPCO into the novel form which makes these rules useful in practicing the invention; Appendix B, which is an example of definitions of rule parameters; Appendix C, which is an example of footnotes as supplied by a commercial supplier such as ATPCO; Appendix D, which is an example of routings as supplied by a commercial supplier such as ATPCO; and Appendix E, which is a listing of an example of programs in FORTRAN which, when used in conjunction with a suitable mainframe computer, such as the equipment available from IBM under the designation 4341 (VM-CMS operating system), can carry out an example of the invented process described above.
|
Same subclass Same class Consider this |
||||||||||