No idea what SkySolver actually does in totality, I'm sure it's complicated but I would think a flight crew could indicate where they are right now and then it could maybe pickup the next possible course they could perform. Not sure why the phone lines "jam up" exactly, don't you have a hierarchical management structure for this sort of thing? Or do 1000 pilots all report to one person?
They've got like 1000 planes and like 100-150 destinations, it's not the traveling sales man problem, an optimal plan isn't needed now so much as a functional one.
Of course, it's easy to bitch about it not being hard when I've never seen the code. Maybe is also tracks hours and does payroll and a dozen other functions.
If the duty time rules only count time after takeoff, or only time after doors are closed, those both offer a different set of times.
The resumption itself.
> Not sure why the phone lines "jam up" exactly, don't you have a hierarchical management structure for this sort of thing? Or do 1000 pilots all report to one person?
It's not a problem of management (well it is a problem of 15 years of management fuckup which is the root cause), it's a problem of the scheduling system needing manual updates when things didn't go to plan.
At this point it's completely screwed, so it needs to be completely reset, as in the entire scheduling system needs to be reconfigured from empty, more or less.
And because SouthWest operates entirely on point to point, the same cascading properties which led to its complete collapse mean it needs to restart in a somewhat synchronised manner, otherwise you fly 3 planes, there's no followup, and you're hosed again.
> They've got like 1000 planes and like 100-150 destinations, it's not the traveling sales man problem, an optimal plan isn't needed now so much as a functional one.
The system completely lost track of crews, so all of them need to be relocated, their work cycles reworked, flight slots need to be reallocated, flights need to be re-encoded.
Then next earnings release - when they post shareholders profits - that’s exactly how much they were willing to hold back to fix this, trading profit for people stuck for days.
Accrue a few billion for refunds, depreciate your software to zero, and start to set aside a few billion for new cloud whatever.
Basically, take this as a huge loss and communicate that you’ve lost a lot of goodwill and trying to make passengers whole is #1 priority (after safety, of course).
https://www.forbes.com/sites/advisor/2020/07/15/how-airlines...
And loyalty programs are bigger business for the higher end airlines that cater to business travels and the more affluent.
On top of that, the top 3 airlines make a lot of money off a first class and business travelers who are using other people’s money.
If they have operating income of eight to ten billion a year, spending a third of a billion to upgrade systems seems like it would have been a reasonable investment instead of buying back shares and increasing the dividend.
- use a tree traversal algorithm with a lot of built-in optimizations and pruning. Google OR-Tools is one well-known solver.
- use a set of meta-heuristics (Tabu search, simulated annealing, etc.) against arbitrary predicate expressions. The best example of this kind of silver is OptaPlanner.
The advantage of tree traversal is that it is exhaustive and guaranteed to be optimal; but it requires a fixed computing budget for a given set of constraints. Given a large compute cluster it's ideal, but on individual machines/servers these solutions tend to take hours or days. Southwest's system would likely require a significant supercomputer to run its scheduling through an exhaustive optimizing constraint solver, since it would have to re-run the entire solution (or significant numbers of subtrees) when any variable changes (which happens likely several times per second).
Meta-heuristics are more flexible and allow for all sorts of interesting, convenient features that can be very helpful when your compute budget is less than a Tiobe-500 supercomputer. They offer time-constrained solving, real-time monitoring of a solution in progress (you can watch it get better as more of the solution space is searched), and over-constrained solving (where the requested solution is impossible, but we need to make a best-effort attempt).
Fun Fact: google-ortools was written by the same people that wrote ILOG. You used to have to "bring your own search" when using ortools, which I used to assume was to avoid conflict with IBM. I haven't used it in a while, but looks like there's a one-size-fits-all search algorithm now. I'd be curious to try it sometime.
I use to write field service software for ruggedized Windows CE devices.
"In one example during the storm, the system assigned a pilot to deadhead on a flight from Baltimore to Manchester, N.H., and then back to Baltimore the next day, without ever flying a plane"*
* The article defines deadheading as sending a pilot as a passenger to get to another location.
It would be interesting to look at what the system is trying to optimize for to make such choices.
Or (more likely, I think) the first deadhead was planned to have the pilot take over a flight which was then cancelled after the pilot was already underway.
Very few software shops I am aware of that do anything like this.
It's quite feasible to get within a factor of 2 of the optimal solution (with much less processing power), which sounds great from a CS algorithm analysis standpoint, but a factor of 2 looks like an awful schedule from a human standpoint.
Having a (relative) bunch of surplus critical-task workers, forever being shuffled to where they system guesses they're most likely suddenly be needed, makes perfect sense.
(Yes, you'd have to be a bit more sophisticated, so your surplus pilots got enough flying time to stay certified. And didn't get pissed and quit. Assume that I know why RAID 5 is better than RAID 4:)
That could also be the result of thrashing after they were really far into the mess. That is, the solver maybe did output something sensible, but that solution has to get into the system that's used at runtime. Someone may have run another solution, or did manual updates while it was too overwhelmed to get all the changes posted. The solvers also depend on other context that's changing underneath them.
My understanding is that the full system reboot wouldn't have taken all that long, it's just the the company was trying to do a major fix while keeping whatever was still sort-of-working running. As any sysop will tell you, patching a running system is all kinds of crazy risky.
That being said, the software sucks. Southwest may have lost track of where their employees are. The ground crews are quitting. I wouldn’t be utterly shocked if management doesn’t even have a good overview of their the planes are.
(Obviously anyone halfway competent could hack up a script to find all the planes based on ADS-B data in a few hours. And it wouldn’t be terribly hard to text a link to all crew asking them to fill out a simple form with their location, nearest airport, and when they can get there. But this requires competence and agility.)
The problem is nothing like writing a script to scrape ADS-B data. This is the classic fallacy of a programmer thinking the most cartoonish imagination of the technology is the problem while being completely blind to the fundamental difficulty of organizing large groups of humans in some activity.
The problem of recovery is also extensively studied. But it seems like SW did not put enough effort into having fault tolerant restart.
This whole event is a management decision.
As for ADS-B, that's hopelessly naive. ADS-B tracks planes, not people. The problem Southwest is having is trying to figure out who is legal to work and where they are. Tracking equipment is so trivial in comparison it's largely a secondary concern.
Once that complexity tipping point is reached (and other comments suppose that SA competitors were more aggressive at cancellations, avoiding that point in their systems) the system takes on a life of its own.
What follows, for those running the system, is called a "Significant Emotional Event".
I'm confused, maybe my calibration of the scale involved here is wrong, but how do you not see this process taking days? Even if you had perfect information of where all the planes and crews were and where they should be, just coordinating with various airports to schedule the flights would take days; and that's assuming every plane is (1) flying empty, (2) fueled and (3) isn't carrying any passenger luggage.
If you are running a little video game that plots flight charts, sure perhaps you could write such a script. You cannot, however, script a bunch of logisitics support together across disparate, independent, multinational airports.
Add the obligitary paperwork (we don't really want to be shipping people around in coffins, enabling human trafficking or illegal substance smuggling, trust me), and add your standard bit of managerial incompetence managed from an excel document and sharepoint, and it's actually downright impressive if it's only a couple days to completely reboot the system.
Arguably, management doing the standard "oh that will never happen" is probably why it's not even better - you would think the airports would be able to automatically "fix" themselves with a self healing protocol, but that was probably deemed too expensive and left out of the feature set.
Of course this will introduce complexity. But it will also need decently less than a normal day’s number of operations.
If I were designing a solver for where to move aircraft and crews (which is apparently what SkySolver does), I would test it on random and malicious inputs. If it’s initialized with every crew member and every plane at an independent random airport in the US (where Southwest has service) with a few broken for good measure and a few airports shut down, it should still find a solution. Waiting 12-24 hours to start so none of the crew is timed out could be part of a valid solution.
It's simple to say, "oh it would be this easy..." and not consider a single real life scenario.
> problem could be simplified to getting every plain and every crew home to where they would spend the night under a normal schedule
This alone would take days under your own recommendation.
He's ignorant and naive and disrespectful of the workers involved.
And you can't just say "go to your usual starting airport". Flights are 24/7. Days of the week matter. Holidays matter. Even your local burger joint doesn't have cast-in-stone schedules. Much less a huge interconnected network that's trying to reboot. Even if 80% of the crew could go to a "usual airport", how would you know if you were in the 20%? Oh... everybody has to phone in, or the system has to send a huge number of notifications out. System crash. (Remember, normally the system depends on scheduling in advance, and only a few last-minute changes need to be handled.)
And how do these what, 20k+ people get where they should be? If they aren't already at that airport, then normally by hopping on a SWA flight. Which aren't happening. So now what? Book flights on other airlines? Who's going to be doing the booking? How does it get paid? How many employees have a company credit card (any?) Use the employee's cards? How many are maxed out for Christmas?
So let's suppose you're scheduled everyone and everybody knows where there's supposed to be and when. What happens when 10% call back in (without crashing the system!) and say they can't get there on time. (Remember, many SWA customers are stuck and are having a hard time arraning alternate travel. Crew without access to SWA flights would have the same trouble.) You're going to either apply massive changes to the existing schedule, or start all over and reschedule everyone. Which is exactly the problem they're currently having. They can't handle massive corrections. What's worse, a crew member may think they're good, and then their travel gets delayed somehow.
How sensitive is the scheduling? If 10% of the crew are no-show or delayed then about 9% of the planes are affected; every 8 hours 90 planes will have the following 8 hours of flights cancelled or delayed (throwing further monkey wrenches in the schedule). About 40 of those planes will be missing a pilot, which means they can't even be deadheaded to where they're supposed to be next.
So how to reboot? They've had to cancel two-thirds of their flights, so apparently they're able to keep 1/3 of them going. Keep those flying so they can shuttle crew around. You're initially only scheduling 1/3 of the crew, so the poor overloaded system can handle it. 2/3 of the flights are just outright cancelled, days in advance, so the customer support load is reduced. ("I'm sorry, your flight has been cancelled. We can't reschedule you until x days from now." vs. much back-and-forth trying to find something with an overloaded system.) Slowly add additional crew and flights so the number of phone-ins is kept manageable.
But this is HN, and, from an optimization / constraint satisfaction problem perspective / scale perspective, it’s really not a very large problem. The “going home” problem is a standard programming contest problem. This is more constrained, but a globally optimal solution isn’t needed. Southwest literally has a program called SkySolver. It should work.
So you need to choose destinations for a few thousand planes? Pick the place you would normally have them at 4 AM two days hence. Need captains familiar with the airports? Surely the captains who would normally fly from a given airport at 4 AM two days hence are familiar with those airports. This gives a good starting solution for further optimization.
You need to get a message to ~20k people? Great, Twilio will do that with minimal effort.
Will a budget of a couple million dollars, this is not hard. There are good SMT solvers available for free. CPLEX is expensive but not on this scale. Managing test cases on this scale is straightforward.
Even in an emergency, something good enough to get to the point where SkySolver starts working again should be doable.
People who manage electric grids have protocols for “black starts”. These protocols are messy and complicated, but they are developed in advance, and they work. Airlines should have the equivalent capability.
Finally, even with perfect communication there's the problem of getting people where they need to be when the transport system is very flaky. I think that's probably the issue when the CEO said 'they would get things manually set up, and then something would happen and we'd have to start all over again.'
The pilot's union and others have been critizing SWA for not investing in infrastructure. The previous CEO, responding to the previous melt-down, said something about 'you can't test for these kind of scenarios.' That's wrong. You can't do it easily or cheaply, but it is possible. They haven't done it, they haven't developed robust systems, and now they can't instantly resolve the problem.
i can't even begin to imagine what the utility function _alone_ must look like.
the solver can't just produce a blank slate solution every time, it's got to optimize... something, subject to some constraints about not changing too much from the previous plan it came up with. and it's probably got to do this every time there's new real world input.
> The “going home” problem is a standard programming contest problem.
the hubris and handwaving on here is hitting epic levels.
this is certainly a complicated situation.
it’s really not a very large problem
So you need to choose destinations for a few thousand planes?
Ostensibly Southwest operates a fleet of Boeing 737s with two subfleets (ETOPS and non). The ETOPS planes can be used anywhere but the others cannot be used to Hawaii. Some of the ETOPS routes require the range of the MAX and some do not. Some of the airports Southwest flies into can only handle the smallest planes. It's entirely possible that everything stuck in Oakland is too big to fly into Burbank for instance. Or its entirely possible that all of the ETOPS fleet is stuck in Hawaii (so all of the routes too Hawaii are no-gos).
Then you've got to figure out what's broken on each plane. Depending on what's inoperative a plane may not be able to fly into a specific airport if the weather is anything but perfect. If enough stuff is broken the plane may be stuck away from a maintenance base and illegal to fly in revenue service. There goes a plane and a flight crew. These are laws, not optimizations.
And finally you need to figure out where all the diverted flights went. No idea what's normal but Southwest had to divert two flights today (one due to mechanical issues and one due to an unruly passenger). So there's at least one plane that's out of position and unable to fly until it's been repaired.
Need captains familiar with the airports?
Then you've gotta do the same with the cabin crew. And then you've gotta make sure none of this runs afoul of the various CBAs.
And you haven't even addressed the issue of out of position luggage. It's not just that luggage is piling up at airports, but Southwest's actually flown some of the luggage without the passengers.
When that's all said and done you're going to need to handle everything that goes tits up as service resumes. As I pointed out earlier, Southwest had at least two diversions today. So now you have two more out of position planes, crews, and more out of position luggage and passengers.
It's a massively complex, dynamic problem. If a couple million bucks would solve things, Southwest would've spent it already. List price on a single 737 is around $40 million. Even if Southwest got half off you're still talking tens of millions of dollars per plane.
People who manage electric grids have protocols for “black starts”. These protocols are
messy and complicated, but they are developed in advance, and they work. Airlines should
have the equivalent capability.
You still have to contend with the laws of physics. AKA the speed of aircraft and distance between airports. Compound that thousands of planes making potentially cross country trips and it will take days to do what you are suggesting, leading to the same problem SWA is already facing.
And getting into a tech company and having high compensation doesn’t require “top talent”. Just the ability to memorize DS&A (junior to mid) and memorize system design and being able to regurgitate answers to behavioral questions showing “scope” and “impact”.
It takes knowing two or three well known algorithms to implement the scheduling problem they are trying to solve and system design chops to know how to scale it.
But, as far as having to be on hold for hours, that’s a staffing issue.
Most of their issues are symptoms of poor management - not software engineers.
Like I said earlier in the thread - there are many bad engineers that are overpaid and many good engineers that are underpaid. On average though, compensation and quality are correlated. In the absence of additional information, compensation is the best metric we have to asses the quality of the underlying engineering talent. It also passes the sniff test - try using the Southwest Airlines app!
And it doesn’t take a $400K senior developer that can reverse a binary tree on the whiteboard while juggling bowling balls while riding a unicycle on a tightrope to make a mobile app.
How much do you think Delta developers make in Atlanta (hint: they aren’t making over 200K). Their app is excellent.
It never ceases to amaze me how little most people on HN know about compensation throughout the industry.
2) COLA matters. $174k in, say, Southwest HQ in Dallas is roughly equated to $422k in SV.
I don’t think COLA matters all that much. The reason SV pays such high salaries reflects the underlying higher productivity of those engineers. The fact that much of that income goes to landlords in the Bay Area is orthogonal to the underlying quality of the engineers.
Like so many strong claims made online, it's an overly simplified mental model for something that is much more complex in reality. Like you said, we need more information before making strong claims.
It seems to me that just like pre-staged inventory helps in logistics management, that extra planes and crews in the rotation could improve operations under these circumstances.
I don't know how this is handled at Southwest, who does not fly hub-and-spoke and thus doesn't have a bunch of pilots sitting reserve around a base at, say, Atlanta.
That lack of slack is hell. It makes any disruption, even minor ones, require the other workers to work more time. Major disruptions mean soul-crushing crunch level hours to just get by.
Slack _must_ be planned into a system, otherwise there won't be any safety / recovery margin, and you're seeing the results live with Southwest's implosion.
Interesting. You don't say how far before Christmas you were traveling. Had this crazy weather system already started moving from West to East at that point? Or was the system buckling just from passenger volume at the point i.e similar to the Summer meltdown that Southwest had?
We had days like that in the UK but with the rail system. And it when it happens it’s also due to snow. We’ve seen it on global scale recently due to covid putting ships in the wrong places so that optimised shipping routes become a mess.
Anecdotally, I flew Southwest just before Christmas. The network was already buckling and we had major delays, but we were lucky and made it through. Despite the stress, the SWA crews were helpful, empathetic, and polite. They handled it better than I would have if I had been in their shoes.