Computational Complexity of Air Travel Planning (2003) [pdf]
ai.mit.edu80 points by arnon 6 days ago
80 points by arnon 6 days 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.
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.
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.
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.
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.
I don't think that point to point is necessarily dead or even really correlated to all the airlines' declines. Rather, the entire category of US low cost carrier and ultra-low cost carrier is suffering, and that just happens to be all the point to point airlines. But this is happening even to the more hub-focused LCCs, like JetBlue (which is busy trying to upgrade into a traditional class-based carrier).
Now that every single legacy airline has a "basic economy", which is often competitive with the LCCs in pricing, there is no moat for the LCCs anymore. Legacy basic economy can be more attractive simply because of mileage programs and better frequencies (even if there is a connection); and legacy airlines have more wiggle room to lower prices in basic economy by raising prices in their premium classes.
It also does not help that the 737MAX fiasco hit some LCCs like Southwest particularly hard due to the practice of going all in on an aircraft type.
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.
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?
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/