Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Optimized system and method for finding best fare

Optimized system and method for finding best fare description/claims

This application is a continuation of U.S. patent application Ser. No. 09/825,451, filed Apr. 2, 2001.

1. Field of the Invention

The present invention relates in general to on-line transportation reservation processing and, in particular, to a system, apparatus and method for providing automatic determination of the best fares for an on-line reservation or fare inquiry.

2. Description of the Related Art

Communication networks are well known in the computer communications field. By definition, a network is a group of computers and associated devices that are connected by communications facilities or links. Network communications can be of a permanent nature, such as via cables, or can be of a temporary nature, such as connections made through telephone or wireless links. Networks may vary in size, from a local area network (“LAN”) consisting of a few computers or workstations and related devices; to a wide area network (“WAN”) which interconnects computers and LANs that are geographically dispersed; to a remote access service (“RAS”) which interconnects remote computers via temporary communication links. An internetwork, in turn, is the joining of multiple computer networks, both similar and dissimilar, by means of gateways or routers that facilitate data transfer and conversion from various networks. A well-known abbreviation for the term internetwork is “internet.” As currently understood, the capitalized term “Internet” refers to the collection of networks and routers that use the Internet Protocol (“IP”) along with higher level protocols such as the Transmission Control Protocol/Internet Protocol (“TCP/IP”) or the Uniform Datagram Packet/Internet Protocol (“UDP/IP”) to communicate with one another.

The Internet has recently seen explosive growth by virtue of its ability to link computers located throughout the world. As the Internet has grown, so has the World Wide Web (“WWW” or “Web”). The Web is a vast collection of interconnected or “hypertext” documents in HyperText Markup Language (“HTML”) that are electronically served at “Web sites” throughout the Internet. The Web has quickly become a popular method of disseminating information due in large part to its simplicity and its ability to deliver information in a variety of formats. To make information available over the Web, a user typically composes a set of “Web pages” which are posted on a Web site by an Internet Service Provider (“ISP”). A Web site resides on a server connected to the Internet that has mass storage facilities for storing hypertext documents, a.k.a. “Web pages,” and that runs administrative software for handling requests for those stored hypertext documents. A hypertext document normally includes a number of hyperlinks, i.e., highlighted portions of text which link the document to another hypertext document possibly stored at a Web site elsewhere on the Internet. Each hyperlink is associated with a Uniform Resource Locator (“URL”) that provides the exact location of the linked document on a server connected to the Internet and describes the document. Thus, whenever a hypertext document is retrieved from any Web server, the document is considered to be retrieved from the Web.

A user is allowed to retrieve hypertext documents from the Web, i.e., a user is allowed to “surf the Web,” via a Web browser. A Web browser, such as NETSCAPE NAVIGATOR®, MICROSOFT® Internet Explorer or phone.com's UP.link microbrowser, is a software program implemented by a Web client, i.e., the user's computer, cell phone or other client device, to provide a graphical user interface (“GUI”) to the Web. Upon request from the user via the Web browser, the Web client accesses and retrieves the desired hypertext document from the appropriate Web server using the URL for the document and a protocol known as HyperText Transfer Protocol (“HTTP”). HTTP is a higher-level protocol than TCP/IP and is designed specifically for the requirements of the Web. It is used on top of TCP/IP to transfer hypertext documents between servers and clients.

At the advent of the Web, the information stored on the Internet was generally static in nature and if one wanted to change the information provided on a Web site it was necessary to manually configure the Web site by rewriting its HTML code. However, at the present stage of development on the Web, many Web sites provide dynamic content that changes depending on a user's interaction between the Web browser on the user's client device and the Web site. These dynamic hypertext documents are well known in the art and may be produced in a myriad of different manners, such as by using Common Gateway Interface (“CGI”) scripts processed by a Web server or local scripts just as JAVAScript processed by a Web browser.

The present invention relates to network-based, and Internet-based travel services, such as a travel service offering tickets for transportation, including airline tickets, train tickets, bus tickets, ferry tickets, etc. to customers over the Internet. With such a service, a customer, using a computer connected to the travel service via the Internet, can purchase items from a dynamically changing inventory including airline tickets, train tickets, bus tickets, ferry tickets, etc., or combinations thereof. Typically, a travel service cooperates with a centralized computer reservation system (“CRS”). A CRS is a system/service that communicates with travel agents transportation providers or services for the purpose of providing up-to-date fare (price for the trip or combination of routs comprising a trip), schedule (date and time of arrival and departure of a trip or flight), rules (which fares are valid under which circumstances) and availability (capacity for a particular trip or flight to provide accommodation at a particular fare) in response to a query. This information is provided to the CRS by the transportation carriers, typically through third parties; however, a travel service can also cooperate with other databases, such as a local database reflecting specific relationships between carriers and the travel service, such as discount contracts or incentive programs. Accordingly, an Internet-based service can have access to many sources of carrier inventory and prices.

The business environment of a travel service is such that there are numerous ways of providing the same or a similar end product to the consumer at a variety of prices. Due to carrier-driven preferences, it may be cost effective to price similar inventory differently. For example, in the case of airline reservations, the number of ways that a consumer can travel from point A to point B is great when the number of airline carriers, different travel paths, hub locations and other particulars are considered. For this reason, the price of a particular generic segment from point A to point B may vary considerably across time, airline carriers, and the like. Further, compounding price variations are price sensitivities, which can reflect, e.g., an increase in demand for tickets reserved proximate to departure time. Additionally, incentive and discount programs negotiated with individual carriers can further affect the price offered by a travel service. Also, certain classes of inventory may have associated high or low demands, or high or low volume sales.

In addition, there are numerous consumer driven preferences which can affect pricing as well. Some consumers will value individual characteristics of a given item of inventory differently. For example, in the case of airline tickets, a consumer may not value when the flight (flying from one place to the next) takes place whereas another consumer may value a particular carrier over all others. These preferences can be factored into flights offered when the consumer specifies the preference. For these reasons and others, there are numerous factors that can affect the value of the same or similar end product.

Furthermore, in a conventional Internet-based travel service, a consumer enters very specific information concerning desired supplier inventory, and the internet-based travel service queries a CRS for inventory that matches that specific query. The CRS performs a search of its database to find matches for the query and returns a result set to the Internet-based travel service for viewing by the consumer. However, a traditional CRS search in response to a query is limited.

One limitation results from the fact that there are numerous ways of providing the same end product to the consumer. For example, there are an incalculable number of ways to travel from point A to point B when different suppliers, travel routes, and other particulars are considered. Thus, for economic reasons, the CRS typically spends a fixed amount of time searching its database for information fulfilling the query. Consequently, when a CRS returns results to a travel service in response to a query, the CRS returns very limited and usually non-optimized results for that particular query, simply because not every permutation or combination of possible inventory elements can be searched. As a result, some inventory that matches the query does not appear in the result set returned by the CRS. Thus, it would be beneficial to provide a service capable of a more exhaustive inquiry without incurring substantial or prohibitive increases in CRS search time and computing power. The provision of such a benefit would enrich the consumer experience and consequently could attract additional consumers and secure repeat customers.

Additionally, it is well known in the art to search for fares by only examining fares for routes that pass through a small set of connection points between an origin and a destination. Then, by explicitly enumerating all the possible combinations of routes between the origin, connection points and destination, it is possible to find the least costly (in both time and price) route(s). However, this approach is still costly and is also inexact and inflexible. As new routes are scheduled or removed by carriers, all the predetermined connection point sets need to be recalculated. Even if only a limited number of connection points are provided, it may still be computationally prohibitive to explicitly enumerate even a limited set of route/fare combinations. Additionally, if only a limited number of connections are examined, then it may be possible to miss the optimal solution if the optimal solution passes through a connection point that is not among the predetermined connection points.

There are other heuristic approaches known to those of ordinary skill in the art to arrive at inexact determinations of a best fare from an origin to a destination; however, these heuristic approaches are still not exact solutions, as heuristic algorithms are inexact by their very nature.

Therefore, there is a need for an approach to find best fares in a computationally non-prohibitive manner that is also exact and does not ignore possible route/fare combinations unless it is known that they are not best fares.

The present invention solves the problem of finding best fares in a non-prohibitive manner by utilizing a query server with a branching and bounding based technique to implicitly enumerate possible travel solutions to arrive at best fare solutions. By using an implicit enumeration, the

In one exemplary method of finding best fares for a trip, the fares are found by determining a set of partial fare solutions for the trip, adding trip information to the partial fare solutions in order to define a set of complete fare solutions and as trip information is added to the partial fare solutions, eliminating partial fare solutions that are non-optimal partial solutions. Then, returning a subset (either a predetermined number or an exhaustive set) of said complete fare solutions as the best fares for the trip.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws