"Computational Complexity of Air Travel Planning"; excerpts:
"...There are more than 4000 airports served by commercial airlines worldwide. Averaged uniformly, each airport has an outgoing degree of 8 (it has flights to 8 other airports), and is served by 4 airlines. However large airports dominate the system: re-weighted by their number of departures, airports average degree 64. This reflects the hub-and-spoke system used by many airlines, wherein for a given airline one to four airports account for half of their departures. Despite the high connectivity amongst the major airports, the shortest path between two airports chosen uniformly averages 3.5 flights in the United States and 5 worldwide. Amazingly, the graph diameter is often as high as 20: there are airports that can take 20 flights minimum to get between, over 4 days (typically this will be a small airport in Alaska or Canada to another small airport in Africa or Indonesia). Commercial airliners take off about once per second worldwide, and most are large jets more than half full, resulting in close to a million people in the air at times.
Why this mess? Why so many fares, such complicated rules, the logic of priceable units, and so on? The answer is often called variable pricing. Various airline economists make the following claim: there is no price such that the price times the demand at the price equals the cost of flying a large jet. There are a lot of technical issues that can be raised with their argument, but leaving those aside the argument is that if the airline charges $1 per ticket of course the plane will fill, but the total revenue of $150 barely pays for an hour of a pilot’s salary. If they charge $1000 a ticket then if they could fill the plane they’d make a fortune, but only a small number of people are willing to fly at that price, so again they can’t equal the fixed costs of flying a plane. But if the airline can make those who are willing to pay it pay $1000, and others pay $800, and others $500, maybe down to $100 or so, then the sum total over all passengers is sufficient to pay for the fixed costs. In fact, some estimates put the incremental cost of flying a single passenger as low as $30 (for the meal and baggage and ticket handling), so that once the airline has committed to flying the plane it is in their interest to sell a ticket for $30 rather than let a seat go empty. But they must keep those who can pay more from buying their ticket at low prices, a tough balancing act.
...MIT's operations research (OR) community participates heavily. Most work is based on linear programming models but simulation techniques are gaining in popularity. One fundamental result is that complicated revenue management techniques only significantly increase profits when planes are flying near capacity.
Some Complexity Results:
• Single fixed fare, fixed route, variable flights is NP-hard
• Fixed flights, fixed PUs, variable fares is NP-hard
• Fixed flights, fixed fares, variable PUs is NP-hard
• Full search is EXPSPACE-hard (simpler proof)
• Full search is undecidable (more difficult)
• Proofs rely only on fundamental parts of the pricing framework
• All proofs reduce standard problems to travel queries over specially constructed flight and fare databases
And except the last one, all the proofs are fairly simple and reduce standard computer science problems known to be difficult to the question of whether there is a valid ticket for a query over specially constructed flight and fare databases.
1. Even if the airlines publish only a single fare (with every ticket a single one way PU), and all the airports in a passenger’s itinerary are fixed, so that the only remaining choice is what flights to use between the consecutive airports, deciding whether there is a valid ticket is NP-hard.
2. Fixing the flights and priceable units, but leaving open the choice of fares to pay for each flight, deciding whether there is a valid ticket is NP-hard.
3. Removing bounds on the size of solutions, the general question of whether there is a ticket for a query is EXPSPACE-hard. That is, air travel planning is at least as hard (it might be harder) as deciding whether a computer program that can use space exponentially bigger than the input halts. EXPSPACE-hard problems are (thought to be) much harder than NP-complete problems like the traveling salesman problem, and even much harder than PSPACE-complete problems like playing games optimally. There is no practical hope that computers will ever be able to solve EXPSPACE-hard problems perfectly, even if quantum computing becomes a reality.
4. The final result shows that just finding out whether there is a valid solution for a query is actually harder then EXSPACE-complete: it is unsolvable (undecidable). The question of whether a valid ticket exists can not be solved for all databases and all queries no matter how long a computer thinks. However the full proof of this result is considerably more complex than the EXPSPACE-hard proof without offering any greater understanding of the problem.
One interesting result not written up here is that even completely fixing the flights and fares of a ticket, so that the only remaining question is how to partition the fares into priceable units, is NP-complete. This is interesting because only flight and fare information makes its way onto printed tickets, not the grouping of fares into PUs. Therefore the problem of just validating a printed ticket is worst-case NP-complete, though it is rarely difficult in practice."
#computationalcomplexity #computerscience #airplane
"...There are more than 4000 airports served by commercial airlines worldwide. Averaged uniformly, each airport has an outgoing degree of 8 (it has flights to 8 other airports), and is served by 4 airlines. However large airports dominate the system: re-weighted by their number of departures, airports average degree 64. This reflects the hub-and-spoke system used by many airlines, wherein for a given airline one to four airports account for half of their departures. Despite the high connectivity amongst the major airports, the shortest path between two airports chosen uniformly averages 3.5 flights in the United States and 5 worldwide. Amazingly, the graph diameter is often as high as 20: there are airports that can take 20 flights minimum to get between, over 4 days (typically this will be a small airport in Alaska or Canada to another small airport in Africa or Indonesia). Commercial airliners take off about once per second worldwide, and most are large jets more than half full, resulting in close to a million people in the air at times.
Why this mess? Why so many fares, such complicated rules, the logic of priceable units, and so on? The answer is often called variable pricing. Various airline economists make the following claim: there is no price such that the price times the demand at the price equals the cost of flying a large jet. There are a lot of technical issues that can be raised with their argument, but leaving those aside the argument is that if the airline charges $1 per ticket of course the plane will fill, but the total revenue of $150 barely pays for an hour of a pilot’s salary. If they charge $1000 a ticket then if they could fill the plane they’d make a fortune, but only a small number of people are willing to fly at that price, so again they can’t equal the fixed costs of flying a plane. But if the airline can make those who are willing to pay it pay $1000, and others pay $800, and others $500, maybe down to $100 or so, then the sum total over all passengers is sufficient to pay for the fixed costs. In fact, some estimates put the incremental cost of flying a single passenger as low as $30 (for the meal and baggage and ticket handling), so that once the airline has committed to flying the plane it is in their interest to sell a ticket for $30 rather than let a seat go empty. But they must keep those who can pay more from buying their ticket at low prices, a tough balancing act.
...MIT's operations research (OR) community participates heavily. Most work is based on linear programming models but simulation techniques are gaining in popularity. One fundamental result is that complicated revenue management techniques only significantly increase profits when planes are flying near capacity.
Some Complexity Results:
• Single fixed fare, fixed route, variable flights is NP-hard
• Fixed flights, fixed PUs, variable fares is NP-hard
• Fixed flights, fixed fares, variable PUs is NP-hard
• Full search is EXPSPACE-hard (simpler proof)
• Full search is undecidable (more difficult)
• Proofs rely only on fundamental parts of the pricing framework
• All proofs reduce standard problems to travel queries over specially constructed flight and fare databases
And except the last one, all the proofs are fairly simple and reduce standard computer science problems known to be difficult to the question of whether there is a valid ticket for a query over specially constructed flight and fare databases.
1. Even if the airlines publish only a single fare (with every ticket a single one way PU), and all the airports in a passenger’s itinerary are fixed, so that the only remaining choice is what flights to use between the consecutive airports, deciding whether there is a valid ticket is NP-hard.
2. Fixing the flights and priceable units, but leaving open the choice of fares to pay for each flight, deciding whether there is a valid ticket is NP-hard.
3. Removing bounds on the size of solutions, the general question of whether there is a ticket for a query is EXPSPACE-hard. That is, air travel planning is at least as hard (it might be harder) as deciding whether a computer program that can use space exponentially bigger than the input halts. EXPSPACE-hard problems are (thought to be) much harder than NP-complete problems like the traveling salesman problem, and even much harder than PSPACE-complete problems like playing games optimally. There is no practical hope that computers will ever be able to solve EXPSPACE-hard problems perfectly, even if quantum computing becomes a reality.
4. The final result shows that just finding out whether there is a valid solution for a query is actually harder then EXSPACE-complete: it is unsolvable (undecidable). The question of whether a valid ticket exists can not be solved for all databases and all queries no matter how long a computer thinks. However the full proof of this result is considerably more complex than the EXPSPACE-hard proof without offering any greater understanding of the problem.
One interesting result not written up here is that even completely fixing the flights and fares of a ticket, so that the only remaining question is how to partition the fares into priceable units, is NP-complete. This is interesting because only flight and fare information makes its way onto printed tickets, not the grouping of fares into PUs. Therefore the problem of just validating a printed ticket is worst-case NP-complete, though it is rarely difficult in practice."
#computationalcomplexity #computerscience #airplane