Computational Complexity of Air Travel Planning (2003) [pdf]

http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf

by arnon • 9 months ago

81 12 9 months ago

ai.mit.edu

toinewx• 9 months ago

https://news.ycombinator.com/item?id=43739547

6 months ago

hinkley2• 9 months ago

I saw a video recently that submitted that the beginning of the end for SouthWest started because their rerouting software was even worse than the intrinsic complexity of the problem.

During a blizzard, their system fell so far behind trying to route planes and crews around it to make sure uncancelled flights could still be honored that they had to do it by hand and they were stranding crews and passengers all over the US by not reacting fast enough to new closures.

After that hit to their reputation the ownership and board shifted to a more extractive model and they have continued to spiral.

bobthepanda2• 9 months ago

Most US airline systems are very old. Southwest’s particular problem is that because they run a point to point model compared to the hub and spoke of legacy airlines, it is a lot harder to cold start the network from scratch. The legacy airlines can more or less just send everyone back to the hub and take inventory there.

hinkley2• 9 months ago

They said all the point to point airlines failed to recover after Covid.

That’s bad news for Boeing as well because their latest refresh for pretty much their entire fleet adds about 500 miles range to each aircraft (not 500 best case, but 500 FAA miles, safety margins and all), so the notion was that more point to point flights would happen, relieving congestion at the hub airports and reducing connecting flights.

But then your inventory and employees are spread everywhere. At least with crew if they move to the hub city they have an easier time.

SpicyUme• 9 months ago

Was this during a storm a few years ago? I used to fly Southwest a decent amount but I haven't in several years now. I've heard worse things about them in the last couple years.

drob518• 9 months ago

This proves to me that companies will pursue revenue optimization to the most absurd lengths, limited only by what the technology can support. And even a bit beyond. I knew this was a difficult problem, but this demonstrates just how difficult it is. That said, I wonder if airlines and other industries aren’t tripping themselves up with complexity. Would a simplified pricing model, going back to basics, allow them to make more?

rafabulsing2• 9 months ago

One problem I have on the back of my mind to try solving sometime is this, from the perspective of the user.

I usually have quite a bit of flexibility when traveling. Exploring multiple options with current tools (at least the ones I'm familiar with) can be slow and annoying.

So what I think would be better is a constraint based system. Rather than simple departure and return dates, you'd input more abstract info like

- Trip must take place between October and November

- Trip must last between 10 and 15 days

- Trip must contain 2 full Tuesdays at the destination

And so on and so forth. Then come up with all possible flights that meet these criteria, and let me sort by price, or by least time spent on transfers, or any number of parameters.

From the small digging I've done, seems like the real hard part of this is getting the actual flight data. I wouldn't even want to necessarily book the flight through this service, just giving me the info about the flights would be enough. But airlines seem to be really stingy with that data. Which kinda makes sense, but damn, is it annoying.

Maybe scraping could be ok. I'd refrain from doing that in the past, but with the AI craze, I guess I'd barely affect the background noise levels of bot activity hitting their servers. Certainly if I built this for me only, and didn't release it, or just released the source for people to run it themselves.

mft_• 9 months ago

I’ve played with this a lot in the past for similar hobby reasons, and you’re right that getting hold of the flight routing data is prohibitively difficult: it’s seen as data with value, meaning it’s guarded and, if you go to official providers, expensive. Scraping is possible if you find a website that exposes the routing data you need in a format close to accessible (very rare) but it’s also complex, as the availability of each route can (and does) change at random times, multiple times per year.

Terretta• 9 months ago

Hipmunk used to handle trips like this. Except the "two full Tuesdays"... The "least agony" sort was amazing.

rafabulsing2• 9 months ago

Oh man, that looks incredible. Such a shame that it doesn't exist anymore.

consumer451• 9 months ago

Somewhat related, regarding ideal boarding theory:

Optimal boarding method for airline passengers (2008)

https://arxiv.org/abs/0802.0733

I just heard about this paper via one of the best podcasts in the Local Group: https://coolworldslab.podbean.com/

Computational Complexity of Air Travel Planning (2003) [pdf]

Related Stories