WO2001029693A2

WO2001029693A2 - Method and apparatus for searching for a low fare for travel between two locations

Info

Publication number: WO2001029693A2
Application number: PCT/US2000/041340
Authority: WO
Inventors: Yanjun Zhang; Alan Walker; Dirk Guenther; Joseph Babis; Maria-Rosario Sai; Mahannop Jomtanawat; Michele Chadwick; Leann Perez; Doug Hanson; Taesik Sohn; Jin Hwan Chung; Nancy Lillo; Shannon Eickstaedt; Kenneth Butters; Scott Healy; Binh Tran; Lorenzo Laohoo, Jr.
Original assignee: Sabre Inc
Current assignee: Sabre Inc
Priority date: 1999-10-21
Filing date: 2000-10-20
Publication date: 2001-04-26
Anticipated expiration: 2002-04-21
Also published as: AU2467401A; WO2001029693A3

Abstract

A method for searching for a low fare is presented. An itinerary including an origin and destination is received. A virtual network is constructed representing one or more paths between the origin and destination. One or more paths are traversed between the origin and destination in search of a lowest cost path. Constraints are applied to each traversed path. After which, a traversed path between the origin and destination is designated as the lowest cost path. Paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

Description

II

METHOD AND APPARATUS FOR SEARCHING FOR A LOW FARE FOR TRAVEL BETWEEN TWO LOCATIONS

FIELD OF THE INVENTION The present invention relates to the field of computerized reservation systems such as airline reservation systems used by airline ticket agents and travel agents. More particularly, the invention relates to a method for performing a low fare search in a computer-based network.

BACKGROUND OF THF. INVENTION || A computerized reservation system (CRS) provides a communications network for travel agents and other users to book airline reservations. Travel-related businesses and other j; companies may interface their computer systems with a CRS in order to make information i; i| concerning their services available via the CRS. For example, a hotel company may interface its ι! ij reservation system with a CRS so that when a person books an airline reservation, he or she may i i, ;; also make a hotel reservation through the same network.

|i

The major computerized reservation systems currently in use throughout the world share a common heritage. They also have common business assumptions that were true nearly two ij decades ago. Examples of such reservation systems arc known or referred to under the following : trade names and service marks: SABRE; AMADEUS; WORLDSPAN; SYSTEM ONE; APOLLO; GEMINI; GALILEO; and AXESS. Under these systems, a customer chooses an itinerary, based on their desired travel dates and times, and books the itinerary through the CRS. A pricing system then computes a price for this itinerary. Pricing systems typically allow a user ι I!I l|

'I to vary their selection based on the class of service, thus enabling a user to select the cheapest

II fare for a fixed itinerary. Tins was ideal prior to airline deregulation and still works well for I certain business travelers. || Sabre led the industry by introducing Tripsearch, which combines fare and availability information in a single query. The user specifics a list of cities to visit on specific dales and

Tripsearch returns a list of itineraries and prices that may be booked in a single step. This works better for leisure travelers who are willing to trade itinerary for price. These mainframe system are used today over the Internet by Travelocity, Expedia and others.

Tripsearch uses heuristic techniques to create a small number of itineraries, which are then sent to the pricing system. A number of other companies have produced systems that are

jj similar to Tripsearch and give approximately the same functionality to the end user. The major characteristics of these systems arc: fixed date in each city (i.e., alternate dates arc not considered); fixed cities (i.e., the user cannot specify general geographic areas); solutions

.' sometimes miss low-fare opportunities that arc obvious to experienced travel agents; and the ' system provides no guidance to the end-user as to how to find a cheaper fare, or what the lowest

,i fare in the market is. The Sabre pricing algorithm relies in part on depth-first searching, mixed with other search techniques, on fare components that were retrieved and validated from disk.

The algorithm is tied to pricing a single itinerary and was not designed to search across a wide

' range of airlines and itineraries. Also, the previous systems were schedule led and could end up |l repeatedly exploring the same fares. Furtheπnore, the previous systems did not efficiently

:; consider the sum-of-locals. For example, it may be less expensive to fly from A to B, and then ιi from B to C, than to fly directly from A to C.

I i j Accordingly, there is presently a need for a system or process for efficiently searching for the lowest fare across a wide range of airlines and itineraries.

SUMMARY OF THE INVENTION A method consistent with the present invention searches for low fares. In this method, an itinerary including an origin and destination is received. A virtual network is constructed representing one or more paths between the origin and destination. One or more paths are traversed between the origin and destination in search of a lowest cost path. Constraints are applied to each traversed path. After which, a traversed path between the origin and destination is designated as the lowest cost path. Paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

An apparatus consistent with the present invention searches for a low fare. The apparatus has a memory having program instructions and a processor responsive to the program

instructions. The processor receives an itinerary including an origin and destination, constructs a virtual network representing one or more paths between the origin and destination, traverses the one or more paths between the origin and destination in search of a lowest cost path, applies constraints to each traversed path, and designates a traversed path between the origin and destination as the lowest cost path. Paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings are incorporated in and constitute a part of this specification and, together with the description, explain the advantages and principles of the invention. In the

drawings,

FIG. 1 is a diagram of an exemplary computer network environment in which the features jj and aspects of the present invention may be implemented; i! i FIG. 2 is an exemplary flow chart of a low fare search process consistent with the present i| invention;

I _j!I FIG. 3 is an exemplary flow chart of a process for developing a network representation consistent with the present invention;

FIG. 4 is an exemplary network representation consistent with the present invention; and FIG. 5 is another exemplary network representation consistent with the present invention.

DETAILED DESCRIPTION '' The following detailed description of the invention refers to the accompanying drawings.

^■; While the description includes exemplary embodiments, other embodiments are possible, and j| changes may be made to the embodiments described without departing from the spirit and scope " of the invention. The following detailed description docs not limit the invention. Instead, the scope of the invention is defined by the appended claims and their equivalents.

The search technique of the present invention provides efficient searches by using a combination of lower and upper bounds on fares and fare combinations, thus enabling it to

;; implicitly enumerate the search space. In this manner, a large number of possibilities can be ij considered without actually generating them all explicitly. By implicitly enumerating the search |l space, the search is much less computationally burdensome and time consuming than ι| conventional approaches that explicitly enumerate the search space. i- The search technique of the present invention also extends the reasoning travel agents use

^'] to find low cost itineraries for a traveler, by considering 'sum of local' opportunities. The search r finds opportunities to reduce travel costs by traveling through an intermediate city not stated in the itinerary. FIG. I is a diagram of a network environment 100 including one or more CRS's. CRS's arc networks permitting access to, for example, travel-related information for making reservations or obtaining such information. CRS's may use and provide other types of

^! information, depending upon the computer systems interfaced with a particular CRS or the information accessible by the CRS. CRS's are commonly referred to as computer reservation i systems or central reservation systems. In European countries, for example, CRS's are often li referred to as global distribution systems. The term "computerized reservation system" and the i'

II abbreviation "CRS" are intended to encompass computerized reservation systems, computer

|i i, reservation systems, central reservation systems, and global distribution systems. Examples of j^p CRS's include those known by the following trade names and service marks: SABRE; AMADEUS; WORLDSPAN; SYSTEM ONE; APOLLO; GEMINI; GALILEO; and AXESS. l i

Network environment 100 illustrates how customers or service providers may be linked together through computerized reservation systems, such as CRS 1 12 or 126. For example, customer machines 101 and 102 may represent machines located at a particular business or other ^!; entity for providing travel-related and other services for that business or entity. Customer |_j machines 101 and 102 are typically interfaced through a frame relay 103 and a router 104 to a j!

_|! server machine 105. Router 104 provides for routing of a protocol over frame relay 103 for long distance communication. Server machine 105 provides necessary interaction between the ii ultimate customer machines and a CRS, for example, CRS 126. Server machine 105 is typically interfaced through a universal data router (UDR) 106 to a network 1 10. UDR 106 may include several servers, as explained below, for performing data conversion for server 105 to communicate with a CRS, for example, CRS 126. Network 1 10 > may represent a private network such as the Socictc Internationale Telecommunications Acronautiques (SITA) network. Network 1 10 interfaces UDR 106 with a front end processor 1 1 1, which provides an interface to a CRS 1 12. A CRS may include a front end processor,

which is a known mainframe component, providing functionality for interfacing the CRS with a network. Customer machines 101 and 102 may also be interfaced with other CRS's through I UDR 106. Therefore, when a person at customer machine 101 or 102 desires to, for example, ji book a travel-related reservation or access other types of information, a communications link is

.1

I established through the various elements between the customer machine and CRS 1 12 or 126.

In addition, network 1 10 may interface travel agent machines 1 14 and 1 15 with CRS 1 12 ji or 126. In particular, network 1 10 may interface a iocal area network (LAN) 1 13 connected to i travel agent machines 1 14 and 1 15. Travel agent machines 1 14 and 1 15, if located overseas, may also be linked into CRS 1 12 or 126. In such a case, network 1 10 may interface token ring LAN 1 13 through an international telephone or computer network (not shown). Other companies or service providers may also provide information available via CRS 1 12. Such information may be provided, for example, by interfacing service provider !■ machines or other computer systems 124 and 125 through UDR 120 to front end processor 1 1 1. ι! UDR 120, which may include several servers, provides data conversion to interface the service provider machines 124 and 125 in accordance with the protocol used by CRS 1 12. Alternatively, service provider machines 124 and 125 may interface with UDR 106 and/or CRS 126.

FIG. 2 is an exemplary flow chart depicting the method by which the present invention searches for the lowest fare. This method can be executed either on the mainframe itself (i.e., the CRS machine) or off-line on a Unix or NT based (or other operating system) station. For example, the method of the present invention could be executed on CRS 1 12, front end processor 1 1 1 , server machine 105, or UDR 120. Note that the method of the present invention is not limited to the network environment of FIG. 1 and could be used in alternate network environments and business environments.

The search of the present invention is based on a k-shortest path approach in fare space. This approach differs from the standard schedule-led approach that is conducted in flight space. This reduces the computation by investigating different fare options, rather than looking at the fares associated with a number of different flight options, many of which yield the same fare totals.

The first step of the method is to develop a network representation (i.e., a virtual network) for a given origin and destination (step 205). This network can be developed in accordance with the method of FIG. 3. First, a customer supplies an itinerary to the system (step 305). The itinerary includes the origin and destination, along with other information that is usually part of a request sent to a CRS (i.e., dates, target price, class of service, etc.). Various other information is also needed in order to properly develop a network. This information includes schedules, fares, availability, and rules (step 310). Once the information has been acquired, virtual nodes are established that correspond to the origin and destination (step 315). Generally, nodes represent cities or airports. In order for the search method of the present invention to properly consider sum-of-local fares, intermediate cities need to be represented in the network. Before nodes can be established

I' that correspond to those intermediate cities, the relevant intermediate cities for a given origin and destination must be determined (step 320). The intermediate cities arc determined by accessing a table that contains the connection cities for each market. This table is maintained in a database >' and can be updated whenever there arc fare and schedule changes in accordance with one preferred embodiment of the invention. Alternatively, the intermediate cities can be calculated dynamically (i.e., perform a search based on schedule information and build connections as you go). Once the relevant intermediate cities have been determined, nodes can be established that i correspond to these cities (step 325). With all the nodes in place, arcs between each node can be j| established (step 330). These arcs represent fares between a given pair of nodes. At this point, .' the network representation has been developed and further processing can proceed. Generally, ιι the development of the network may include multi-airport or multi-city options, and it could ;■ ultimately be extended to meet more abstract requirements (coastal city, ski destination, etc.). FIG. 4 is an exemplary simple network representation that could be created by the method of the present invention. The nodes A, B, C, D, and E represent various cities or aiφorts. Specifically, nodes A and E represent the origin and destination, respectively. The nodes B, C, and D are various intermediate cities that have been selected by the method of the present invention. The arcs between the nodes each have a dollar amount associated with it to indicate that the arcs represent the various fares between nodes. The fact that there could be multiple ■' fares between any given pair of cities is represented by FIG. 5, which is another exemplary ,, network representation. There are a plurality of arcs between each of the nodes, indicating that there is more than one fare associated with the different city-pairs.

¹ The search will be explained with reference to FIG. 2. Note that the search of the present

I invention is not only for a single origin, single destination, and single intermediate city. It is I readily extended to more complex itineraries including a series of aiφorts (or more abstract i designations - city, ski resort, FL beach, etc.) and an arbitrary number of intermediate points.

Before the search can actually start, bounds for the search must be developed (step 210). The bounds are lower bounds on fares between locations and are determined in a manner similar to the determination of the intermediate cities. Each lower bound is associated with an arc from the network representation. In one embodiment, the lower bounds can be based on lower bound fare amounts maintained in a table that is maintained in a database. The table contains the lowest fare for each market and can be updated in a manner similar to the table for storing intermediate cities. The actual fares that arc available and applicable will be at least as much as the values in Ij the lower bounds table. Alternatively, the lower bounds can be determined dynamically using ij backwards recursion on arc bounds. After the bounds have been determined, a check is made to

II

I¹ see whether or not all of the bounds exceed a customer's target price (i.e., a customer's ji designated maximum price). If they do, then the search can be terminated immediately. If not, then the search can continue. The target price is an upper bound on the search. The search continues by progressively developing paths through the network in search of the lowest cost path, based on an A* search. The A* search is a well-known tree-searching algorithm originating in the artificial intelligence literature, N. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill, 1971. The search is sequential with the best path extended with each iteration. This path is known as the best partially expanded path. The

path is considered to be only partially expanded because the path has not yet been completed. The term "best" means the path with the lowest associated fare/cost. This cost is computed recursively by summing branch costs associated with each path transition from the start node to the current node. The algorithm includes a provision for eliminating inferior paths when it has been determined that a given path can no longer possibly be the best path. The algorithm also provides for the inclusion of a cost associated with completing the path from the current node to some specified goal node. If this completion cost is a lower bound on the minimal cost path from the current node to the goal, then the algorithm will find an optimal, minimum cost path to the goal. Only minimum cost paths are expanded, so the A* search locates the best path without I having to search all possible paths.

In the context of the present invention, once the lower bounds have been determined, the i best partially expanded path is chosen (step 215). This path corresponds to the path with the j_; lowest cost that has not yet been eliminated. Next, a lower bound arc is expanded to correspond to an actual fare or set of fares (step 220). It is possible to have one lower bound arc expand to j multiple fares. The actual fares that arc found in this step are fares that are anticipated to be valid in terms of availability, applicability, and combinability. These fares can be acquired from a table that holds city pair pricing information. Due to differences between lower bound fares and

I¹ actual fares, the best path can vary after expansion to actual fares. When the arc is expanded, a ji place holder is left in the search tree, in case further expansion is required. In this way, the || partial expansion technique of the present invention can resume where il left off without having

I to go all the way back to the beginning again.

Once the actual farc(s) for a given arc have been determined, the estimated path cost for the present path and other paths generated by the bound expansion are revised (step 225). In this step, various rules and restrictions (i.e., applicability information) and availability information are applied to the path. If a given path is either not applicable or not available, then that path can no longer be the lowest fare path, and it is eliminated as being infeasiblc or undesirable. Alternatively, availability and applicability could be at least partially considered while developing the network and not while developing the paths (note that availability and applicability information were available while constructing the network). Generally, availability and applicability may be based on the traveler (senior citizen, youth, military, etc.) or based on the itinerary (origin and destination yield management considerations, restrictions on routings, seasons, black-outs, advance purchase, day of week, flight specific restrictions, combinability with other fares, etc.).

Next, it is determined whether or not a complete fare path has been developed (step 230). A complete fare path has been developed if the path consists entirely of actual fares rather than lower bound fares. If a lower bound estimate still exists in the path, then a new best partially expanded path must be chosen, and that path must be processed in accordance with steps 220, 225 and 230. The place holder is utilized here to return to where the search left off. Every time the search considers a new best partially expanded path, a check is made to see if all of the remaining lower bounds exceed the target price (upper bound). If they do exceed the upper bound, then the search can be stopped. If the path has no more lower bound estimates (e.g. complete fare path), then a final validation of applicability, availability, and price must be performed on the path (step 235). This is a necessary step because with some itineraries and in some environments, it is more difficult to verify availability, and it needs to be left as a side I constraint. Also, in other cases, the rule processing is very cumbersome and should be left as a side constraint to be validated only once the availability is confirmed. Other constraints can only be validated when the full itinerary is known. Sometimes, there arc surcharges and the like that _li could inflate the fare. All of these constraints and surcharges arc left as part of the final

I¹ validation. In this step, feedback on solutions that did not work could also be provided to the customer, as explained below. The general principle behind determining what should be left for the final validation step is to get as much information as efficiently as possible, balancing the ease of validation with the expected value of the information. If it is difficult to check availability, but it is more apt to be the constraining factor, it may be worth determining this first. The precise order of processing is a matter of tuning for the system and for different classes of itineraries.

<^[ As stated above, solutions that did not work can provide feedback to the customer. For i '

,ι example, if a given itinerary is not applicable to the customer, that information can be returned to ij the customer, and there is no need to pursue that fare on another day. If the search finds a

I feasible fare that is not available for the stated itinerary, the customer may elect to change his or her travel date(s). If the search recognizes that a fare could not be obtained due to rules associated with the itinerary (i.e., Saturday night stay), then that feedback can be returned and the j_l itinerary modified.

Iι

: After final validation, a determination is made as to whether or not there are lower or li additional fare paths to pursue (step 240). For example, so called "plus-ups" and/or "loose j| il bounds", which reflect fares that were not available, applicable or combinable, may inflate the fare so that other lower cost alternatives must be developed. If there are lower or additional paths to pursue, then a new best partially expanded path must be chosen, and that path must be processed in accordance with steps 220, 225 and 230. If there are no lower or additional paths to pursue, then the operation is over, and the lowest fare has been found. Note that when determining whether or not the there are additional paths to pursue, it is possible to look for slightly higher cost solutions that may still be desirable to the customer. For example, after the low fare has been found, all of the options within a certain dollar amount of the low fare, or a certain percentage within the low fare can be considered. Also, more complex criteria such as whether there would be an itinerary with fewer stops or less transit time or on a preferred carrier within a certain amount of the low fare, etc., can be considered.

While the present invention has been described in connection with a preferred embodiment, many modifications will be readily apparent to those skilled in the art, and this application is intended to cover any adaptations or variations thereof. For example, the method can be extended to consider multiple days. It can also be extended to generalize the origins and destinations according to multi-aiφort, multi-city, or other aggregations or abstractions. Other extensions can include multi-modal transport or the construction of complete holiday packages that include air, land and/or sea components, along with accommodation and other facilities and services. Furthermore, the search could be applied when the search is not simply for fare. For example, the search could be used to find the shortest time between two points, simply by substituting travel and connection times for costs. The search could also be used to optimize a multi-attribute objective function (reflecting time, cost, mode, route, carrier, etc.). One skilled in

the art will appreciate that all or part of the systems and methods consistent with the present invention may be stored on or read from computer-readable media, such as secondary storage devices, like hard disks, floppy disks, and CD-ROM; a carrier wave received from a network such as the Internet; or other forms of ROM or RAM. This invention should be limited only by the claims and equivalents thereof.

Claims

WHAT IS CLAIMED IS:

1. A method for searching for a low fare comprising the steps, performed by a processor, of: receiving an itinerary including an origin and destination; constructing a virtual network representing one or more paths between the origin and destination; traversing the one or more paths between the origin and destination in search of a lowest cost path; applying constraints to each traversed path; and designating a traversed path between the origin and destination as the lowest cost path, wherein paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

2. The method of claim 1, wherein the virtual network includes nodes representing locations, and arcs connecting the nodes and representing fares between nodes.

3. The method of claim 2, said constructing step further comprising: determining intermediate locations.

4. The method of claim 3, wherein the intermediate locations are determined based on a table stored in a database.

5. The method of claim 3, wherein the intermediate locations are determined dynamically.

6. The method of claim 3, said traversing step further comprising: determining lower bounds for the paths, the arcs each having at least one lower bound associated with it.

7. The method of claim 6, wherein the lower bounds are determined based on a table stored in a database.

8. The method of claim 6, wherein the lower bounds are determined dynamically.

9. The method of claim 3, said traversing step further comprising: eliminating arcs and/or paths using availability and/or applicability information.

10. The method of claim 3, said constructing step further comprising: eliminating arcs and/or paths using availability and/or applicability information.

11. The method of claim 6, said developing step further comprising: choosing a best partially expanded path; expanding a lower bound arc to correspond to an actual fare;

eliminating arcs and/or paths using availability and/or applicability information; and determining whether a complete path has been developed.

12. The method of claim 1, further comprising: providing feedback on failed paths.

13. The method of claim 1, wherein said processor is one of a computerized reservation system (CRS) and a processor external to a CRS.

14. A data processing system for searching for a low fare, comprising:

a memory having program instructions; and a processor responsive to the program instructions to: receive an itinerary including an origin and destination; construct a virtual network representing one or more paths between the origin and destination; traverse the one or more paths between the origin and destination in search of a lowest cost path; apply constraints to each traversed path; and designate a traversed path between the origin and destination as the lowest cost path, wherein paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

15. A computer-readable medium containing instructions for performing a method for searching for a low fare comprising the steps, the method comprising: receiving an itinerary including an origin and destination; constructing a virtual network representing one or more paths between the origin and destination; traversing the one or more paths between the origin and destination in search of a lowest cost path; applying constraints to each traversed path; and designating a traversed path between the origin and destination as the lowest cost path, wherein paths that include a location located between the origin and destination omitted from the itinerary are considered when searching for the lowest cost path.

16. The computer-readable medium of claim 15, wherein the virtual network includes nodes representing locations, and arcs connecting the nodes and representing fares between nodes.

17. The computer-readable medium of claim 16, said constructing step further compπsing: determining intermediate locations.

18. The computer-readable medium of claim 17, wherein the intermediate locations are determined based on a table stored in a database.

19. The computer-readable medium of claim 17, wherein the intermediate locations are determined dynamically.

20. The computer-readable medium of claim 17, said traversing step further comprising: determining lower bounds for the paths, the arcs each having at least one lower bound associated with it.

21. The computer-readable medium of claim 20, wherein the lower bounds are determined based on a table stored in a database.

22. The computer-readable medium of claim 20, wherein the lower bounds are determined dynamically.

23. The computer-readable medium of claim 17, said traversing step further comprising: eliminating arcs and/or paths using availability and/or applicability information.

24. The computer-readable medium of claim 17, said constructing step further comprising: eliminating arcs and/or paths using availability and/or applicability information.

25. The computer-readable medium of claim 20, said developing step further comprising: choosing a best partially expanded path; expanding a lower bound arc to correspond to an actual fare; eliminating arcs and/or paths using availability and/or applicability information; and determining whether a complete path has been developed.

26. The computer-readable medium of claim 15, wherein said method further comprises: providing feedback on failed paths.

27. The computer-readable medium of claim 15, wherein said processor is one of a computerized reservation system (CRS) and a processor external to a CRS.