Finding an available low flight fare can be very difficult and a significant amount of often very fluid data is required to find it. However, there are different levels of complexity to the problem, so first we should assess the dimensions of the problem that we need to solve.
Different problem dimensions
A. Finding the cheapest fare on complex routings with any fare to and from anywhere in the world.
B. Finding the cheapest fare from anywhere in the world to anywhere in the world.
C. Finding the cheapest fare on a limited and controlled list of routes.
D. Finding the cheapest fare where we are confident that it will be a negotiated fare.
Travel agents (especially flight only agents) usually have problems A and/or B and tour operators usually have problems C and/or D.
Tour operators, whilst having a more limited set of destinations (and therefore slightly smaller problem dimensions), do have additional problems related to fitting the flight around sometimes fixed-itinerary ground product (i.e. we don’t want the customer having to chase the tour bus down the street because we haven’t correctly taken into account the time required to get to the tour bus).
Knowing which problem we are trying to solve is vital in choosing a solution. I will come back to the options on this once we understand why this is such a difficult problem.
Flight search – the Basic Problem
The flight problem basically arises from:
1) The number of potential routes between any two given points, and
2) The fact that fares are not normally calculated “point-to-point” or for each flight sector, but are calculated for a combination of sectors.
1) The number of routes problem:
ITA Software (purchased for $1bn. by Google) wrote a very good white paper, which shows a set of simple, intra-day routes from San Francisco to Boston. Obviously, in order to find a return flight, 10,000 x 10,000 = 100 million options can be found. Faring, marking up and checking availability for this number of options is unfeasible within sensible search timescales. The problem must either be simplified, or estimation or numerical methods must be used.
Whilst there are millions of potential one-way routings between Boston and San Francisco, and consequently billions of potential solutions to the problem of finding a return flight, there are some ways in which we can make the problem easier for ourselves.
The options open to us in this area depend on whether we have all (or much of, in which case we may be able to use approximations) the required fare and availability data.
1) If we only sell negotiated fares then it is likely that we can get hold of all the requisite fare data.
2) If we only use a small number of published fares in specific circumstances then we may be able to handle those fares fairly easily.
3) If there are lots of published fares required then we will need to get hold of some more data. This can be expensive and complex.
Availability information is more fluid than fare information and consequently harder to obtain.
1) If we only sell allocations then everything is going to be very easy, especially if most of the flights we need are point-to-point flights. In terms of fare search, we can build a local availability database and use that for search. From a tour operations point of view, this can be treated just as a charter airline would be treated.
2) If we have a very close commercial relationship with a single carrier which carries almost 100% of our passengers then we should try to obtain a real-time availability feed from that carrier. If this is not possible then we must proceed to deal with the more complex problem.
3) Assuming that we cannot obtain a real-time feed of all required availability information and that we do not operate solely by allocation then we need a GDS and/or public feeds of availability information.
If we are to solely use a GDS there are two options:
1) Simply ask the GDS for availability when we need to know it. This approach is fraught with issues and should only be used on very limited point-to-point routings with simple negotiated fare in a local database and should be backed up with a good route-finding algorithm (q.v.).
2) Use an observed availability cache: ask the GDS for the availability when we need to know it and store that information for the next time that we need to know it. This approach can be slightly complex but is sometimes the only option. It is most effective in a tour operations market, particularly if there are many passengers on few routes.
A note on point-of-sale availability control
Some airlines have a simple mapping between their inventory database, which means that availability information is more static and that a single database can be maintained.
However, many larger airlines use some kind of point-of-sale availability, meaning that they are willing to sell more seats in some classes of service to certain points-of-sale than others.
Point-of-sale control can be at any level of granularity, for instance Lufthansa control availability to specific pseudocities, whilst Virgin Atlantic control this by the country of the departure airport of the first sector of the itinerary.
Two specific implementations of point-of-sale control exist, one called “bid-pricing” in which all availability is controlled in this way, and one called “last seat availability” in which only the availability of the final seat (or few seats) are controlled in this way. For our purposes, these two implementations can be treated similarly.
If an airline with point-of-sale control is a significant part of the inventory which we need to sell then two additional things must be taken into account:
1) That any cached information is only applicable to its point-of-sale, in which case the cache must be partitioned by point-of-sale (if there is more than one) and that this reduces the amount of data available in each partition, and
2) That inventory feeds, even if they could be obtained from a particular airline, are unsuitable to build an availability database.
A note on allocations
For the purpose of this algorithm, allocations on flights can be treated as simple and relatively static availability databases. So long as the flight search application has an integrated allocation management application, this should not cause any difficulties.
Other important data
SSIM (Standard Schedules Information Manual) is published as a standard file format and is available from a number of different airline data suppliers. It can be obtained at any frequency but should be obtained at least weekly for use in robust search applications.
Minimum connect point data
This information (known as MCT) describes how much time is required to reliably transfer between any two flights. It is not very fluid and does not need to be updated more than once a month for most applications.
Decode data (airline, airport, equipment type, equipment sub-type etc.)
All of this information is available from IATA and other airline data suppliers. It is available in reliable, fixed formats and it is unlikely that this data will require update more than once or twice annually.
Time zone and daylight saving time data
This information is available from IATA and other airline data suppliers. It is available in reliable, fixed formats and it is unlikely that this data will require update more once per annum.
Connect point data
Connect point tables (CPT) can be obtained from a number of suppliers and can assist in simplifying the route-finding algorithm (q.v.). It is not complex but the format of the data is not fixed.
If connect point data is not available then fare data (or the pre-processing of a schedule, ideally along with whatever fare data is available) can make up for, or even surpass the effectiveness of this data in route-finding.
Fare search algorithms
Problem Dimension A: Finding the cheapest fare on complex routings with any fare to and from anywhere in the world.
No-one has yet solved this problem very well.
Solving this problem is likely to require a non-linear algorithm, such as a genetic algorithm or a neural network.
If one is looking to buy, rather than to build, a solution to this problem, then the approach taken should largely depend on whether any of the other problem spaces govern the majority of other sales.
Deciding that it’s all too hard and that someone else might be better at it
Simple solutions for small specialist tour operators
Summary: Many software companies sell software which claims to perform low fare searches of scheduled airlines. Most of these applications have some sort of fare database and then request availability information as required from a GDS. This can be adequate for small, specialist tour operators but is not appropriate for larger scale operations.
Examples: @Core (what used to be the ‘FareSearch’ product – I’m not sure what it’s called now).
Pros: The simplest implementation. Satisfactory for low volumes where a degree of manual intervention is acceptable. Will not create excessive bookability issues. Price (these applications tend to be simple, cheap and easily maintainable). Useful for multi-centre bookings.
Cons: Not scaleable. Low fare finding capabilities are limited where a large number of fare options exist.
Hybrid solutions for larger specialist tour operators
Summary: These applications have a fare database and then request availability information as required from a GDS but cache data where possible. Some have more or less complex algorithms to reduce polling to a minimum. This can suffice a larger specialist tour operator but does not solve the problem well and has a number of potential serious flaws.
Examples: CodeGen TravelBox, DataLex, OpenJaw.
Pros: Usually have better low fare finding capabilities. Usually more scaleable. Usually these applications are relatively cheap to run. The best application style for complex multi-centre bookings.
Cons: Complexity of maintenance and setup. Depending on the quality of the implementation this type of application can introduce bookability issues. Depending on the quality of the implementation and complexity of setup, this type of application can make it more difficult to find the lowest available fare on a route. Usually these applications are relatively expensive to buy as they tend to be specialist implementations within an expensive, larger application.
Summary: These applications have a full negotiated and published fare database and a complete local copy of availability information from all airlines, usually made up of information from a combination of availability sources, with direct polling to supplement information. They are really designed to solve the all fares, all routes problem and are largely targetted at the high-volume, low margin online travel agency market.
Examples: ITA QPX (now Google), Amadeus MasterPricer, TravelPort ePricing.
Note that many other companies claim to compete in this arena but I believe that this is a complete list of potential solutions. Please let me know if I’m wrong.
Pros: Usually these have the best low fare finding capabilities. They are also generally significantly more scaleable and reduce airline polling to a minimum, sometimes to zero.
Cons: Price (these applications are expensive to create and they consequently tend to be expensive to the user). They can sometimes be slightly restrictive in terms of functionality and usually have relatively limited multi-centre capabilities.