exwannabe

Yes, but the issue I am saying is that the published AAA-CCC fares need to be validated across all possible routes (not just 2 legs). That in itself will be a shortest path calc. And same for AAA-BBB fares ...

The answer is 25387776. Question was, "how many Angels can dance on the head of a pin"? :-)

sethb

There are some published fares, including direct flights and connections. Those are all input to the program. It is then an easy algorithm to find all least-cost routings between cities.

rylan

To the plaintiff: Thanks for ruining EF access for the rest of us who weren't out to make some point trying to stick it to DL.

DaDaDan

I'll admit it...I was wrong. ...The problem is actually NP-hard, not NP-complete. But everything else I said is still true. If you have an algorithm to solve an NP-hard problem in polynomial time, you have proven that P=NP and that wins you the $1 million. (An NP-complete problem can be verified in polynomial time, but that's not the case here.)

The problem with your logic is that you're still assuming that the price of the ticket only increases as fare components are added. This is not true. You cannot reliably price a ticket until the entire ticket is known, or even make claims such as "the ticket will be at least $X." For example, adding a fare component can change which location is considered the destination vs. the stop over. Adding a fare component can change whether or not the ticket qualifies as round/circle trip. Adding a fare component can exceed a minimum stay requirement or fulfill a Saturday stay requirement.

See this article: http://www.msri.org/people/members/s...s/airfares.pdf

Obviously, if you bound the problem by saying "I only want to see non-stop fares" or "I won't leave the US to connect on an otherwise domestic itinerary" or "my itinerary must be complete within X days" then you can solve the problem in a reasonable period of time. But, that doesn't mean its not still NP-hard. It just means you've reduced the problem to a degree where all of the possibilities can be checked.

xliioper

A "published" fare, does not mean an "available" fare. Ultimately, you need to query the GDS systems to see what's actually available in the fare buckets. You can cache the data, but how stale do you let the cached inventory to get before you refresh it? What if some of the published fares you are searching haven't had their bucket availability instantiated in your cache yet?

LaserSailor

this doesn't address this

at all, but you are right that this thread is basically useless 1s and 0s

DaDaDan

As I noted above, the problem is that extending a route can lower its price.

And delta doesn't need to fly 1000000000 routes a day to cause this issue. Even with Delta's current route structure, and limiting yourself just to DL-marketed flights, there are already sufficiently many ways to get from A to B that you cannot practically check them all.

mother-

No DaDaDan extending broken fare routes can not lower the price. This problem requires solving the "what is the lowest AAA-ZZZ fare available" and then looking for combinations of fares that get you from AAA to BBB without going over that price.

So:
(1) Lowest available "married segment" fare to destination
(2) Find fares (married or individual flight) from origin airport that are lower than fare found in (1)
(3) Find fares (married or individual flight) from connecting airport found in (2) which combine to be less than the currently best fare or combination of fares
(4) For each fare or combinations of fares found in (3) iterate (3) until at destination

The reality is that you could stop at a couple connections for practical purposes...

DaDaDan

Taking a step back, all the claims about this actually being very simple are contradicted by the folks in the industry who have actually had to design these algorithms, as discussed in the article I posted above.

The reality of course is that you can generate algorithms that are very good. They definitely find very good fares. And they probably find the best fare. But, they can't be certain of it.


Separately, looking at your algorithm, I don't think it is comprehensive. If the problem is to fly AAA to BBB, there are also round trip fares from AAA to NNN that allow an open jaw where the "return" can be to BBB. If you price AAA-NNN alone, as suggested in your Step 2, the price could be a high OW fare, at which point your algorithm will stop exploring this option. Only by adding the segment NNN-BBB, do you find that it qualifies as a RT with OJ.

This is at least one way where searching fares progressively fails. At least one other one is creating an itinerary that, by adding a leg, qualifies for RTW pricing.

mother-

(With the caveat that I'm really only thinking about domestic flights and not all the crazy extra fees and complexity for Intl)
I think that once again you're not talking about broken fares but fares from origin to destination, and that type of fare (married segments if connecting) is exactly the logic that would be in step 1 of what I outlined, and is what Delta.com already does.

And

DaDaDan

The linked article notes a case where there was a massive last minute fare sale on flights to London from the East Coast that allowed open jaw returns to major US cities. E.g., NYC-LHR-BOS was allowed. In this scenario, it would be very possible that a flight NYC-LHR-BOS (qualifying as RT with OJ) is cheaper than a last minute OW fare NYC-BOS or even NYC-BOS. The algorithm above would not find this because the cheaper fare is filed as a RT fare NYC-LHR, but the algorithm only looks for:

1. NYC-BOS fares
2. Fares to other airports that are lower (just NYC-LHR is an expensive OW fare and not cheaper)


(Btw, I know you excluded international fares. I used LHR just because it is referenced in the article. The same facts could apply domestically as well. There aren't as many cases in practice since most RT are just 2xOW domestically these days. But, that hasn't always been the case. And there's nothing stopping an occasional violation of this norm.)

sethb

Any algorithm assumes its input data exists and is correct.

Here's a least-cost all-routes algorithm:

There are N cities. Create an NxN matrix; the entries are the airline's published fare from AAA to BBB, with 0 on the diagonal (it's free to say in the same place). Call that M1 (cheapest route with 1 or fewer fares).

Do a "matrix multiply" using min over plus (standard matrix multiply is plus over times) M1 x M1. Call the result M2, it's the cheapest route with 2 or fewer fares.

Do that again, M2 x M2. Call the result M4, it's the cheapest result with 4 or fewer fares.

Continue until Mn, where n>=N. That takes ceiling(log2(N)) steps. The result is the cheapest routes from any city to any other. Total time is clearly polynomial in N.

For those looking at broken round-trips, hidden cities, etc., those technically aren't allowed by the airlines. But if they are to be allowed in this problem, it's easy to include them. When the airline quotes a fare from AAA to BBB, check the routing, and include that as the fare from AAA to any CCC along the route if lower than already found.

The real-world problem is a bit harder, because we need to consider connections, minimum time, etc. However, that's still feasible: let each node be an airport at a time, where the times are arrival+MCT for each flight. Waiting at an airport is free. It's still polynomial in the number of flights.

DaDaDan

So, I'll start by reiterating the fact that your assertion contradicts the published accounts of folks who have actually built fare engines. Now, maybe they were wrong, and you're right. But it's been published by mathematical research groups. So, I tend to believe them.


More specifically, you've made several assumptions here that are not true in practice:

1. There is only one published fare between two city pairs (or at least the cheapest fare is trivial to observe).

This allows you to reduce the problem to the shortest distance problem where we know in advance the distance between any two locations.

This is not true in our case. There are many published fares for any route, and the ability to use one may depend on a number of conditions, including conditions dependent on other fare components. E.g., it must be part of a round trip, requires Saturday stay, etc. Each fare must be checked and all conditions validated against the attributes of the entire ticket.

You also have to determine availability on any particular flight segment.

This means you need to determine the time complexity not just in number of segments (as you have done) but also in number of fare rules filed and in flights offered. In order to determine the minimum price between two points, you need to check every fare rule and every flight's availability. As connections are added, the universe of relevant fare rules and feasible flights whose availability must be checked grows.

Even ignoring the availability issue, it grows very quickly.

[Edited to add: So apparently in FT land, the symbol for exponentiation is ^. Please interpret accordingly!]

Assume:
F = number of fares filed per city pair
C = number of cities
n = number of segments

I want to fly AAA-BBB.

For a non-stop flight (n=1), there are F fare rules to check.

For exactly one connection, AAA-ZZZ-BBB, there are F fare rules to check for AAA-ZZZ and F fares to check for ZZZ-BBB. So, for one connection city (n=2), there are F^2 fares to check times C-2 cities (you cannot connect in AAA or BBB).

For exactly two connections, AAA-YYY-ZZZ-BBB, you check F^3 fares times (C-2)^2 connection points. This assumes that you allow connections such as AAA-YYY-AAA-BBB, which in theory is necessary. For example, you could be flying on a RT fare AAA-YYY with an OJ return ending at BBB, and the segment from your "destination" YYY to BBB requires a connection at AAA. This could price lower than the OW fare AAA-BBB.

Ok, for arbitrarily many F, C, and n, you have:

summation(1,N) of [F(C-2)^(n-1)]^n

This definitely grows faster than polynomial time.

As an example:

F will vary by city pair, but let's say it is 15 fare rules per city pair
C is something like 1500 commercial airports in the world
Let's assume N is 5 segments.

This yields 2.5 x 10^69 fares to calculate. If you assume you can check 10 fares per second, that's 7.8 x 10^60 years.

And it gets worse...

2. Any stay in a city is just like any other.

This assumption again reduces the complexity, but does not hold in practice. Your stay in any city can be termed a connection, a stopover, or a destination. Which category it falls into depends on the timing of the flights into and out of the city, the remaining segments on the ticket, the fare rule you're using, and in some cases your option.


3. Taxes, fees, carrier-imposed surcharges, etc. are irrelevant.

These can only be calculated knowing the entire ticket and all of its attributes, including small things like point of sale, plating carrier, etc., some of which you can manipulate to get a lower price.

mbwmbw

I never knew we had so many mathematical and computer science wizs on here .

DaDaDan

I think I got my equation wrong actually, but it's still in the "impossible" range. So wizz-1 for me.

Should be:

Summation(1,N) of [F^n (c-2)^(n-1)]

Still takes 1.2 x 10^10 years to calculate.