Originally Posted by
DaDaDan
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.
ok...
Originally Posted by
DaDaDan
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).
Not sure I agree.
Based on your above definitions of F,C, and n -- for one intermediate city there are F fare rules to check for AAA-ZZZ and F fare rules to check for ZZZ-BBB, plus the married segment rules. This means you have 2F+F fare rules to check, not F^2.
AAA-ZZZ
ZZZ-BBB
AAA-BBB
This is because e.g. once I've checked the B fare AAA-ZZZ, I don't have to check it again when I search for each fare of ZZZ-BBB. The 'married segment' fares, if they exist, then are checked once (the extra +F).
Originally Posted by
DaDaDan
For exactly two connections, AAA-YYY-ZZZ-BBB
By my logic this would be C=4
singles
AAA-YYY
YYY-ZZZ
ZZZ-BBB
married
AAA-BBB
AAA-ZZZ + ZZZ-BBB(already checked)
AAA-YYY(already checked) + YYY-BBB
Thus the general form is ((C-1) + SIGMA( C from 1,(C-2) )) * (F fare rules)
where SIGMA is summation notation
Thus we have O(C^2) complexity which is polynomial time.
For C=5, =>
AAA-XXX-YYY-ZZZ-BBB
singles
AAA-XXX
XXX-YYY
YYY-ZZZ
ZZZ-BBB
married
AAA-BBB
AAA-XXX(ac) + XXX-BBB
AAA-XXX(ac) + XXX-ZZZ + ZZZ-BBB(ac)
AAA-YYY + YYY-BBB
AAA-ZZZ + ZZZ-BBB(ac)
This handles the one-way case. The return case is either a simple return ticket (F fare rules), or a limited set of open-jaw + one-ways.
We now introduce a new variable D= max number of potential connection cities and D >= C-2
We would check the following scenarios in order.
C=2,D=0
AAA-BBB-AAA
C=3,D=1
AAA-ZZZ-BBB-ZZZ-AAA
AAA-ZZZ-BBB-ZZZ + ZZZ-AAA
AAA-ZZZ-AAA + ZZZ-BBB-ZZZ
AAA-ZZZ + ZZZ-BBB-ZZZ + ZZZ-AAA
C=3,D=2
repeat C=3,D=1 for YYY
AAA-ZZZ-BBB-YYY-AAA
AAA-ZZZ-BBB-YYY + YYY-AAA
AAA-ZZZ + ZZZ-BBB-YYY + YYY-AAA
AAA-ZZZ,YYY-AAA(as OJ) + ZZZ-BBB-YYY
AAA-YYY-BBB-ZZZ-AAA
AAA-YYY-BBB-ZZZ + ZZZ-AAA
AAA-YYY + YYY-BBB-ZZZ + ZZZ-AAA
AAA-YYY,ZZZ-AAA(as OJ) + YYY-BBB-ZZZ
For the sake of brevity i'll stop here. Suffice to say, within the DL system, and within sane pricing and timing maximums, the number of possibilities is quite low. C is at most 6 (4 connections? many domestic fare rules limit this to 2 or 3) D is most likely usually 4 or 5 of ATL,DTW,MSP,SEA,LAX,JFK? As C is at most 6 even if it scales as O(n^n), thats only 46xxx combinations which is easily computable.
Furthermore, many of these search branches can quickly be eliminated as the price is optimized, e.g. if AAA-YYY costs more than the current 'most optimal' route, all routes which require an AAA-YYY one-way can be eliminated. Timing rules hack away further at this with a 4 hour max connection time on domestic searches. Lastly, some fares are not combinable, and for DL's sake we will say that this all needs to be issued in one ticket.