Computational Complexity of Air Travel Planning (2003) [pdf]
Key topics
A 2003 paper on the computational complexity of air travel planning is discussed, with commenters exploring the implications for airlines' revenue optimization and potential simplifications, as well as related problems like user-friendly travel planning tools.
Snapshot generated from the HN discussion
Discussion Activity
Light discussionFirst comment
4d
Peak period
5
96-108h
Avg / period
3
Based on 12 loaded comments
Key moments
- 01Story posted
Nov 4, 2025 at 6:33 AM EST
about 2 months ago
Step 01 - 02First comment
Nov 8, 2025 at 8:39 AM EST
4d after posting
Step 02 - 03Peak activity
5 comments in 96-108h
Hottest window of the conversation
Step 03 - 04Latest activity
Nov 9, 2025 at 7:41 PM EST
about 2 months ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
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.
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.
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.
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.
6 months ago
> 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/