Sep 9, 14, 5:54 am
Last edit by: mbwmbw
All files are available for download at: http://mbw.name/Files/FlyerTalk/Delta_Class_Action/
Furthermore, each document has been linked to the download location.
For a full download of the complaint and attachments click here.
Date Filed # Docket Text
08/07/2014 1 COMPLAINT with Jury Demand; against Delta Airlines, Inc. by Darla Opper. ( Filing Fee PAID $400 receipt number 0757-1939172) (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Civil Cover Sheet, # 9 Summons)(Shah, James)
08/07/2014 NOTICE Regarding assignment of this matter to Chief Judge William C Griesbach ;Consent/refusal forms for Magistrate Judge Duffin to be filed within 21 days;the consent/refusal form is available on our web site ;pursuant to Civil Local Rule 7.1 a disclosure statement is to be filed upon the first filing of any paper and should be filed now if not already filed (jcl)
08/07/2014 2 DISCLOSURE Statement by Darla Opper. (Shah, James)
08/08/2014 Summons Issued as to Delta Airlines, Inc. (mec)
08/20/2014 3 Refusal to Jurisdiction by US Magistrate Judge by Darla Opper. (Shah, James)
08/25/2014 4 SUMMONS Returned Executed by Darla Opper. Delta Airlines Inc served on 8/14/2014, answer due 9/4/2014. (Shah, James)
08/29/2014 5 Unopposed MOTION for Extension of Time by Delta Airlines Inc. (Smith, Renee)
08/29/2014 6 DISCLOSURE Statement by Delta Airlines Inc. (Smith, Renee)
09/02/2014 TEXT ONLY ORDER GRANTING 5 Unopposed MOTION for Extension of Time filed by Delta Airlines Inc., signed by Chief Judge William C Griesbach on 09/02/2014. The deadline for filing its responsive pleading is extended 14 days, until September 18, 2014. (cc: all counsel)(Griesbach, William)
09/18/2014 7 MOTION to Dismiss by Delta Airlines Inc. (Balassa, Gabor)
09/18/2014 8 BRIEF in Support filed by Delta Airlines Inc re 7 MOTION to Dismiss . (Attachments: # 1 Exhibit A - Best Fare Guarantee, # 2 Exhibit B - Best Fare Guarantee Claim Form, # 3 Exhibit C - Tabatabai v. West Coast Life Ins. Co, # 4 Exhibit D - Marine Travelift, Inc. v. Marine Lift Sys., Inc, # 5 Exhibit E - Tilstra v. Bou-Matic, LLC, # 6 Exhibit F - PNC Bank, N.A. v. Van Hoornaar, # 7 Exhibit G - NIIJII Entmt, LLC v. Troha) (Balassa, Gabor)
10/03/2014 9 Unopposed MOTION for Extension of Time by Darla Opper. (Shah, James)
Furthermore, each document has been linked to the download location.
For a full download of the complaint and attachments click here.
Date Filed # Docket Text
08/07/2014 1 COMPLAINT with Jury Demand; against Delta Airlines, Inc. by Darla Opper. ( Filing Fee PAID $400 receipt number 0757-1939172) (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Civil Cover Sheet, # 9 Summons)(Shah, James)
08/07/2014 NOTICE Regarding assignment of this matter to Chief Judge William C Griesbach ;Consent/refusal forms for Magistrate Judge Duffin to be filed within 21 days;the consent/refusal form is available on our web site ;pursuant to Civil Local Rule 7.1 a disclosure statement is to be filed upon the first filing of any paper and should be filed now if not already filed (jcl)
08/07/2014 2 DISCLOSURE Statement by Darla Opper. (Shah, James)
08/08/2014 Summons Issued as to Delta Airlines, Inc. (mec)
08/20/2014 3 Refusal to Jurisdiction by US Magistrate Judge by Darla Opper. (Shah, James)
08/25/2014 4 SUMMONS Returned Executed by Darla Opper. Delta Airlines Inc served on 8/14/2014, answer due 9/4/2014. (Shah, James)
08/29/2014 5 Unopposed MOTION for Extension of Time by Delta Airlines Inc. (Smith, Renee)
08/29/2014 6 DISCLOSURE Statement by Delta Airlines Inc. (Smith, Renee)
09/02/2014 TEXT ONLY ORDER GRANTING 5 Unopposed MOTION for Extension of Time filed by Delta Airlines Inc., signed by Chief Judge William C Griesbach on 09/02/2014. The deadline for filing its responsive pleading is extended 14 days, until September 18, 2014. (cc: all counsel)(Griesbach, William)
09/18/2014 7 MOTION to Dismiss by Delta Airlines Inc. (Balassa, Gabor)
09/18/2014 8 BRIEF in Support filed by Delta Airlines Inc re 7 MOTION to Dismiss . (Attachments: # 1 Exhibit A - Best Fare Guarantee, # 2 Exhibit B - Best Fare Guarantee Claim Form, # 3 Exhibit C - Tabatabai v. West Coast Life Ins. Co, # 4 Exhibit D - Marine Travelift, Inc. v. Marine Lift Sys., Inc, # 5 Exhibit E - Tilstra v. Bou-Matic, LLC, # 6 Exhibit F - PNC Bank, N.A. v. Van Hoornaar, # 7 Exhibit G - NIIJII Entmt, LLC v. Troha) (Balassa, Gabor)
10/03/2014 9 Unopposed MOTION for Extension of Time by Darla Opper. (Shah, James)
Class Action Federal Lawsuit Aginst Delta RE: Best Fares Available
Sep 10, 14, 5:44 pm
#106
Join Date: Jan 2013
Location: 대한민국 (South Korea) - ex-PVG (上海)
Programs: UA MM / LT Gold (LT UC), DL SM, AA PLT (AC), OZ, KE; GE and Korean SES (like GE); Marriott Gold
Posts: 1,996
I never knew we had so many mathematical and computer science wizs on here
Last edited by relangford; Sep 10, 14 at 7:07 pm Reason: typo
Sep 10, 14, 5:56 pm
#107
Join Date: Jun 2004
Location: ATL
Programs: Delta PlM, 1M
Posts: 6,282
DaDaDa, by your math it would take about (15x1500)x(15x1500) searches at .1 sec to find the cheapest 1 stop from the BDA (Bemuda) to JFK. That would be almost 2 years.
Given that there are 2 routes to start with, and then must take a direct flight afterwards, I am reasonably certain I could solve this by phone queries a tad faster.
EDIT: Missed your correction.
By your new math my example comes in at 15^3000 searches. The real world is about 30x120 or so.
Given that there are 2 routes to start with, and then must take a direct flight afterwards, I am reasonably certain I could solve this by phone queries a tad faster.
EDIT: Missed your correction.
By your new math my example comes in at 15^3000 searches. The real world is about 30x120 or so.
Last edited by exwannabe; Sep 10, 14 at 6:07 pm
Sep 10, 14, 6:51 pm
#108
Join Date: Dec 2007
Posts: 1,688
Originally Posted by exwannabe
DaDaDa, by your math it would take about (15x1500)x(15x1500) searches at .1 sec to find the cheapest 1 stop from the BDA (Bemuda) to JFK. That would be almost 2 years.
Given that there are 2 routes to start with, and then must take a direct flight afterwards, I am reasonably certain I could solve this by phone queries a tad faster.
EDIT: Missed your correction.
By your new math my example comes in at 15^3000 searches. The real world is about 30x120 or so.
Given that there are 2 routes to start with, and then must take a direct flight afterwards, I am reasonably certain I could solve this by phone queries a tad faster.
EDIT: Missed your correction.
By your new math my example comes in at 15^3000 searches. The real world is about 30x120 or so.
1. My language is imprecise. I said a non-stop flight, but I really meant a "one fare component" flight or something like that (I'm not hip to all of the travel industry terminology...I just dabble).
Basically, if there is a published fare from AAA-BBB that counts as one "segment" as I wrote above. There will be published fares between two cities even if there are no non-stop flights.
So, even for BDA, where there may only be non-stop flights to a few US cities, there may be a published fare BDA-SFO, which would require a connection. And then another SFO-JFK.
2. My calculation assumes there's a published fare from every city to every other city with an airport (that has scheduled commercial service). I'm not actually sure if this is true. It could be that for some city pairs, you have to use two fares. That said, I just checked on EF for some weird city pairs, and they came up. For example SWF (Stewart Airport, NY) to REP (Siem Reap, Cambodia) has 16 published fares.
Which got me thinking: Looking at more popular city pairs, my estimate of, on average, 15 fares seems extremely low. There are 275 JFK-LHR fares.
3. The reality is that the actual search engines aren't exhaustive. They don't check every possibility. They use heuristics to get you a very good answer that is very, very likely to be the best fare, but not certainly the best fare.
Btw, I don't ask that you believe my math -- I don't have a math degree either. I just suggest you trust the published accounts from those that do have math degrees and have actually worked on this problem. But, I'm also happy to try to explain.
Sep 10, 14, 8:07 pm
#109
FlyerTalk Evangelist
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy LT Gold, Hyatt Explorist, IHG Diamond, others
Posts: 12,015
Originally Posted by 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.
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.
In the real world, the problem is solved, so there must be a solution.
(BTW, your assumption about exponential complexity doesn't hold: look at my matrix algorithm. By squaring each time, the number of operations is reduced.)
I'd do a cheapest-first (breadth-first) search. Start by getting a fare (whatever the airline quotes). Then find all cities you can get to in one hop (fare component). Eliminate anything that's already too expensive. Starting at the cheapest, find all two-hop minima, reducing the "known cost" of a city whenever a cheaper way to get there is found. Since each step "fixes" one city (the cheapest to get to), there are at most N steps; each step requires checking all single-hop fares from that city, and can't affect an already-fixed city.
Yes, this is still constructing a one-way fare out of one-way fares. But it wouldn't be that hard to include round-trip fares (easier if you don't allow hidden city transactions and the like).
Sep 10, 14, 8:09 pm
#110
FlyerTalk Evangelist
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy LT Gold, Hyatt Explorist, IHG Diamond, others
Posts: 12,015
Originally Posted by relangford
I, too, am impressed (and bewildered) by the math seen above. I am not as smart as these posters, but, here's a wierd and unacceptible (for the airlines) thought: make airfares like bus fares, where one pays $x to go from A to B and $y to go from B to C with everybody on the plane paying the same number of dollars (for the same class of service). I had a friend in the DL IT department who once told me that it is possible that every single person on a plane had paid a different fare. I know there are geniuses in resource management, but why can't fares be a fixed amount from A to B and from B to C with A to C being the total of the other two, eliminating the married segment problem? I guess I'm too dumb to understand these things. My head hurts!
Sep 10, 14, 9:17 pm
#111
Join Date: Dec 2007
Posts: 1,688
Originally Posted by sethb
In the real world, the problem is solved, so there must be a solution.
Using the techniques of complexity theory, de Marcken
showed that for a given fare, it can be NP-hard just to know what existing flights satisfy restrictions. But even if the flights are fixed,
the problem of choosing fares to cover those flights is NP-hard.
showed that for a given fare, it can be NP-hard just to know what existing flights satisfy restrictions. But even if the flights are fixed,
the problem of choosing fares to cover those flights is NP-hard.
Originally Posted by sethb
(BTW, your assumption about exponential complexity doesn't hold: look at my matrix algorithm. By squaring each time, the number of operations is reduced.)
I'd do a cheapest-first (breadth-first) search. Start by getting a fare (whatever the airline quotes). Then find all cities you can get to in one hop (fare component). Eliminate anything that's already too expensive. Starting at the cheapest, find all two-hop minima, reducing the "known cost" of a city whenever a cheaper way to get there is found. Since each step "fixes" one city (the cheapest to get to), there are at most N steps; each step requires checking all single-hop fares from that city, and can't affect an already-fixed city.
I'd do a cheapest-first (breadth-first) search. Start by getting a fare (whatever the airline quotes). Then find all cities you can get to in one hop (fare component). Eliminate anything that's already too expensive. Starting at the cheapest, find all two-hop minima, reducing the "known cost" of a city whenever a cheaper way to get there is found. Since each step "fixes" one city (the cheapest to get to), there are at most N steps; each step requires checking all single-hop fares from that city, and can't affect an already-fixed city.
Sep 10, 14, 10:01 pm
#112
Join Date: Dec 2007
Posts: 1,688
This Carl deMarcken guy has a website:
http://www.demarcken.org/carl/
There's a link to a presentation that discusses various aspects of the problem, including discussing the problem being NP-hard or worse.
http://www.demarcken.org/carl/
There's a link to a presentation that discusses various aspects of the problem, including discussing the problem being NP-hard or worse.
Sep 11, 14, 7:28 am
#113
FlyerTalk Evangelist
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy LT Gold, Hyatt Explorist, IHG Diamond, others
Posts: 12,015
If you are constructing fares by adding segments and their costs, it doesn't make sense to say "the cheap fares are at the end". Breadth-first by cost handles that issue.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
Sep 11, 14, 8:52 am
#114
FlyerTalk Evangelist
Join Date: Jul 2003
Posts: 20,596
Originally Posted by sethb
Airlines would go broke if they tried that. They need to charge people who are willing to pay more higher fares; if they charged everybody the average fare, they'd have half-empty planes (all the people who want cheap fares and buy early would go to their competitors, they'd get the expensive last-minute ticket buyers only; and they'd charge them less, so they'd lose money on the flight. If they raised fares, they'd get even fewer customers.)
The non-network carriers such as WN and NK do actually have some resemblance to this model. They are more focused on O&D traffic and you will see a fair amount of correlation between distance and price. Of course there are frequent exceptions due to competitive pressures or attempting to build new markets, etc.
Sep 11, 14, 9:59 am
#115
Join Date: Dec 2007
Posts: 1,688
Originally Posted by sethb
If you are constructing fares by adding segments and their costs, it doesn't make sense to say "the cheap fares are at the end". Breadth-first by cost handles that issue.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
For example, you will get fare information like this:
For travel between JFK and LHR,
Fare WXYZ, round trip, $450, list of restrictions
Fare ABCD, one way, $750, list of restrictions
Fare EFGH, one way, $850, list of restrictions
Fare IJKL, one way, $850, list of restrictions
.....
The first letter of the fare indicates the fare inventory code. You'll need to find flights where those codes are available in a separate search:
Flight 1234 I4 E3 A1 W0 <-- eg, on this flight you cannot use WXYZ
Flight 5678 I4 E0 A0 W0
Flight 9012 I9 E9 A9 W9
.....
Then, once you pick flights that are open for the fares you want to use AND (critically) you have assembled the entire ticket, you have to check against all of the fare restrictions on all of the fares used on the entire ticket. Fare restrictions on one fare can impact the usability of other fares on the ticket. Examples include:
Saturday stay
Combinability rules
Prohibitions on flights on certain (competing) carriers
Restrictions on the valid flight numbers
....and on and on.
My point about the cheap fares being "at the end" refers to the fact that if you pull all the available fares and take the first one at $450, this might look good now, but will ultimately be invalidated for use. Then you have to go to the next cheapest. It could be that the cheapest usable fare is the last one, which would mean you would need to check every single one in ascending order before you found one that worked.
Like I said, look at Carl deMarcken's web site. He's got a Ph.D. in computer science from MIT and was co-founder and Chief Scientist of ITA Software, one of the first modern fare search engines, which used algorithms he developed to get very good -- but not best -- fares (and better than what the prior brute-force methods got).
If you really think he's wrong, feel free to send him an email and let us know what happens.
Sep 11, 14, 1:23 pm
#117
Join Date: Apr 2011
Location: DC
Programs: DL PM
Posts: 147
Originally Posted by sethb
If you are constructing fares by adding segments and their costs, it doesn't make sense to say "the cheap fares are at the end". Breadth-first by cost handles that issue.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
However, with arbitrary constraints on fares, it's easy to make the problem NP-hard. I made the assumption that you can start with all published fares (that is, those the airline will tell you about). If you start with less data, the problem can be much harder.
Sep 12, 14, 4:09 am
#118
Join Date: Jul 2010
Posts: 1,150
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.
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.
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).
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
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.
Last edited by WhiskeyBravo; Sep 12, 14 at 5:11 am
Sep 12, 14, 5:25 am
#119
Join Date: Aug 2013
Location: LAS HNL
Programs: DL DM, 5.7 MM, UA 3.1 MM, MARRIOTT PLATINUM, AVIS FIRST, Amex Black Card
Posts: 4,479
Just stick with A-B on WN domestic - win -win. This lawsuit is garbage. I'll give you the best price = Priceline.com. Do I use it on flts? - No. Have I saved a ton on hotels or car rentals using Priceline - yes.
Did I find flts on Delta.com on 12/26/2013. (What else do you do on the day after Christmas with the in-laws - search the internet). You bet I went to delta.com to escape! Aloha from F traveling on DL with full miles for around $100.00 each! Mai Tai in hand.
I should have booked 10 trips.
HNL: Car rental ($19.00 or less per day) (I got Hertz). Hotel 3* ($59.00 or less per day). Hotel 4* ($79.00 a day) on the beach. (taxes/fees not included).
This lawsuit is going nowhere.
Did I find flts on Delta.com on 12/26/2013. (What else do you do on the day after Christmas with the in-laws - search the internet). You bet I went to delta.com to escape! Aloha from F traveling on DL with full miles for around $100.00 each! Mai Tai in hand.
I should have booked 10 trips.
HNL: Car rental ($19.00 or less per day) (I got Hertz). Hotel 3* ($59.00 or less per day). Hotel 4* ($79.00 a day) on the beach.
(taxes/fees not included).This lawsuit is going nowhere.
Sep 12, 14, 7:07 pm
#120
FlyerTalk Evangelist
Join Date: Jun 2004
Location: MSP
Programs: DL PM, MM, NR; HH Diamond, Bonvoy LT Gold, Hyatt Explorist, IHG Diamond, others
Posts: 12,015
I see the disagreement: I was constructing a one-way fare by putting together known (published) fares. That's the easy problem.
If the airline can make arbitrary rules, and you are putting together a round-trip fare, then it's easy to be NP-hard (or even harder, if the rules can be that hard to check; e.g. refer to other rules).
If the airline can make arbitrary rules, and you are putting together a round-trip fare, then it's easy to be NP-hard (or even harder, if the rules can be that hard to check; e.g. refer to other rules).
