5 ms·

I have always really wondered how airline scheduling software works. Despite being pretty good with algorithms, I just have no idea how you'd make a system that

I have always really wondered how airline scheduling software works. Despite being pretty good with algorithms, I just have no idea how you'd make a system that's robust to weather and mechanical delays.

castratikron 4y ago
Sounds like they don't have much of an idea either.
twawaaay 4y ago
I don't have experience with airline scheduling but I have experience with software in large financial corporations like banks. The situation with banks (at least the ones I worked with) is that there is a huge amount of software maintained mostly by mediocre to bad teams. These teams fail a lot, the software fails a lot, and yet everything seems to keep going. It is not about code or algorithm quality, it is about procedural side of things -- how the organisation is "programmed" to respond to failures. I use the word "programmed" in a very broad sense -- for me setting up a paper checklist and being able to rely on people to follow it is the same as programming. I suspect the main difference between airlines and banks is that banks can afford to throw money on the problem and just get things done regardless of how inefficiently. Airlines are in the much worse position -- they were able to afford being inefficient and throwing money at the problem in the past but can't do it anymore. They work with old, outdated software that wasn't built with efficiency in mind but now don't have funds to change it and are forced to maintain what they have. This may also be the answer to why sometimes they just don't have capacity to react to problem and let it cascade to bring everything to a halt.
- blevin 4y ago
  Instead of framing this as saying they "don't have" the funds and were "forced" into inaction, another framing that the board of directors must consider is that current SWA leadership failed in their responsibility to recognize, prioritize, and manage the actual needs of their decades old business.
  - twawaaay 4y ago
    I am unable to speak for the management because I have no knowledge of their particular situation or extensive experience in the matter. I can only speak about the forces that act on development teams and what could most likely in my mind explain the current situation.
htag 4y ago
One important component is slack. Every airline at every airport should have a certain number of crews and airplanes capable of providing service in place of a delayed flight. Running on maximum efficiency for airplanes and staff means unexpected delays will cause cascading failures. Weather can be forecasted, and additional crews can be routed to replace probable future cancelled flights. Temporary staff and increased hours can be utilized for peak demand seasons. We saw similar problems with manufacturing failures when the supply chain became unreliable because of a lack of slack. This type of slack can be seen as an inefficiency and costs money, so it's unsurprising to see budget airlines struggling. Another important component is disaster recovery. How quickly can the system recover from missed flights? What is the game plan for dealing with crews/airplanes that are out of place. How will they return to normal operations? Often times having a play book everyone is working from can lead to faster recoveries than dealing with each individual crisis as it happens, often with either too much micromanagement from leadership or too little coordination between departments. The play book generates a conciseness before the system is stressed.
- sokoloff 4y ago
  > Every airline at every airport should have a certain number of crews and airplanes capable of providing service in place of a delayed flight. Airline pax are probably not willing to pay for spare standby aircraft and flight and cabin crews at every airport every airline operates from. Southwest’s original low-cost carrier business innovation was to run an all-737 fleet and make business-wide efforts to optimize for fast ground-turns, in order to get more flights out of each aircraft.
  - bronson 4y ago
    Certainly not, that would destroy profit and competitiveness. Spare airplanes are mostly in for non-essential maintenance, and spare crews can be called up in an hour or two. That's good enough. Catastrophic outages every few years still cost less than building decent redundancy into all operations. This is partly because airlines are still externalizing a good portion of the cost onto their customers, who need to rebook at short-term pricing. I'd love to see legislation to address this loophole.
jasonpeacock 4y ago
The field of science (math) that studies this (and applies it) is called "Operations Research"[0] and it's about optimization & planning. About 30yrs ago they started applying it to airline scheduling, here's a few random papers I found: https://www.researchgate.net/publication/245236750_Airline_Scheduling_An_Overview https://www.researchgate.net/publication/245236750_Airline_S... https://www.sciencedirect.com/science/article/abs/pii/0305048374900875 https://www.sciencedirect.com/science/article/abs/pii/030504... [0] https://en.wikipedia.org/wiki/Operations_research https://en.wikipedia.org/wiki/Operations_research
eightysixfour 4y ago
I know a bit about this with airlines - there's a lot of thinking that goes in to making the system appropriately robust but just as much, if not more investment, in optimizing recovery for minimal damage as well. They have optimizers that figure out the minimal damage from a plane being taken out of schedule, and airport halting flights due to weather, or whatever the issue may be. What's cool is the math that goes into "minimal damage" with regards to passengers, crews, bags, etc. You can poke around at the website for SlickOR (https://www.slickor.com/ https://www.slickor.com/) to get an idea of the surface level work that goes into this.
ttcbj 4y ago
I worked on the medical resident scheduling problem for a while, and there is a giant body of work on all kinds of staff scheduling problems going back to the 1960s at least. The two classes of solutions that I considered where optimization solvers (see Gurobi Optimization for example), and meta-heuristics (see the book Metahueristics: From Design to Implementation). If I remember correctly, the people at Gurobi started at a previous company which was spun out of an airline, but I might be confused. All the algorithms in both classes of solutions are so nuanced that it can take years to begin to grasp how their strengths and weaknesses interact with your particular scheduling challenge, and how the way you formulate the problem interacts with the ability of the algorithm to solve it. All that said, the real problem for me was a human one: If you produce a viable schedule X, the organization involved will always want to alter the rules to stretch the available resources to cover more, and simultaneously all the schedule staff will want more flexibility and nuance in expressing their preferences. You, as the author of scheduling software, are caught between them. Neither side is ever happy with the result. I occasionally daydream about revisiting resident scheduling (I don't recommend it, the people who use your software leave every year, are not business oriented, and don't understand the complexity of the task until they've tried it on their own their first and only attempt). If I did, I would focus less on algorithms, and more on incentives to reconcile the tension between the organization, which wants to cover the most shifts with the fewest people at the cost of flexibility and preferences, and the staff, who want more flexibility and more preferences satisfied. I think that is the core problem at a business level.
- bombcar 4y ago
  The easiest way to solve the tension is probably to add additional money into the mix - the hard to fill shifts get paid a bonus, etc. someone would figure out how to game it of course but you already have this somewhat when overnights pay more.
  - linuxftw 4y ago
    I was thinking similarly. Have people bid on shifts.

castratikron 4y ago

Sounds like they don't have much of an idea either.

twawaaay 4y ago

I don't have experience with airline scheduling but I have experience with software in large financial corporations like banks. The situation with banks (at least the ones I worked with) is that there is a huge amount of software maintained mostly by mediocre to bad teams. These teams fail a lot, the software fails a lot, and yet everything seems to keep going. It is not about code or algorithm quality, it is about procedural side of things -- how the organisation is "programmed" to respond to failures. I use the word "programmed" in a very broad sense -- for me setting up a paper checklist and being able to rely on people to follow it is the same as programming. I suspect the main difference between airlines and banks is that banks can afford to throw money on the problem and just get things done regardless of how inefficiently. Airlines are in the much worse position -- they were able to afford being inefficient and throwing money at the problem in the past but can't do it anymore. They work with old, outdated software that wasn't built with efficiency in mind but now don't have funds to change it and are forced to maintain what they have. This may also be the answer to why sometimes they just don't have capacity to react to problem and let it cascade to bring everything to a halt.

blevin 4y ago
Instead of framing this as saying they "don't have" the funds and were "forced" into inaction, another framing that the board of directors must consider is that current SWA leadership failed in their responsibility to recognize, prioritize, and manage the actual needs of their decades old business.
- twawaaay 4y ago
  I am unable to speak for the management because I have no knowledge of their particular situation or extensive experience in the matter. I can only speak about the forces that act on development teams and what could most likely in my mind explain the current situation.

htag 4y ago

One important component is slack. Every airline at every airport should have a certain number of crews and airplanes capable of providing service in place of a delayed flight. Running on maximum efficiency for airplanes and staff means unexpected delays will cause cascading failures. Weather can be forecasted, and additional crews can be routed to replace probable future cancelled flights. Temporary staff and increased hours can be utilized for peak demand seasons. We saw similar problems with manufacturing failures when the supply chain became unreliable because of a lack of slack. This type of slack can be seen as an inefficiency and costs money, so it's unsurprising to see budget airlines struggling. Another important component is disaster recovery. How quickly can the system recover from missed flights? What is the game plan for dealing with crews/airplanes that are out of place. How will they return to normal operations? Often times having a play book everyone is working from can lead to faster recoveries than dealing with each individual crisis as it happens, often with either too much micromanagement from leadership or too little coordination between departments. The play book generates a conciseness before the system is stressed.

sokoloff 4y ago
> Every airline at every airport should have a certain number of crews and airplanes capable of providing service in place of a delayed flight. Airline pax are probably not willing to pay for spare standby aircraft and flight and cabin crews at every airport every airline operates from. Southwest’s original low-cost carrier business innovation was to run an all-737 fleet and make business-wide efforts to optimize for fast ground-turns, in order to get more flights out of each aircraft.
- bronson 4y ago
  Certainly not, that would destroy profit and competitiveness. Spare airplanes are mostly in for non-essential maintenance, and spare crews can be called up in an hour or two. That's good enough. Catastrophic outages every few years still cost less than building decent redundancy into all operations. This is partly because airlines are still externalizing a good portion of the cost onto their customers, who need to rebook at short-term pricing. I'd love to see legislation to address this loophole.

jasonpeacock 4y ago

The field of science (math) that studies this (and applies it) is called "Operations Research"[0] and it's about optimization & planning. About 30yrs ago they started applying it to airline scheduling, here's a few random papers I found: https://www.researchgate.net/publication/245236750_Airline_Scheduling_An_Overview https://www.researchgate.net/publication/245236750_Airline_S... https://www.sciencedirect.com/science/article/abs/pii/0305048374900875 https://www.sciencedirect.com/science/article/abs/pii/030504... [0] https://en.wikipedia.org/wiki/Operations_research https://en.wikipedia.org/wiki/Operations_research

eightysixfour 4y ago

I know a bit about this with airlines - there's a lot of thinking that goes in to making the system appropriately robust but just as much, if not more investment, in optimizing recovery for minimal damage as well. They have optimizers that figure out the minimal damage from a plane being taken out of schedule, and airport halting flights due to weather, or whatever the issue may be. What's cool is the math that goes into "minimal damage" with regards to passengers, crews, bags, etc. You can poke around at the website for SlickOR (https://www.slickor.com/ https://www.slickor.com/) to get an idea of the surface level work that goes into this.

ttcbj 4y ago

I worked on the medical resident scheduling problem for a while, and there is a giant body of work on all kinds of staff scheduling problems going back to the 1960s at least. The two classes of solutions that I considered where optimization solvers (see Gurobi Optimization for example), and meta-heuristics (see the book Metahueristics: From Design to Implementation). If I remember correctly, the people at Gurobi started at a previous company which was spun out of an airline, but I might be confused. All the algorithms in both classes of solutions are so nuanced that it can take years to begin to grasp how their strengths and weaknesses interact with your particular scheduling challenge, and how the way you formulate the problem interacts with the ability of the algorithm to solve it. All that said, the real problem for me was a human one: If you produce a viable schedule X, the organization involved will always want to alter the rules to stretch the available resources to cover more, and simultaneously all the schedule staff will want more flexibility and nuance in expressing their preferences. You, as the author of scheduling software, are caught between them. Neither side is ever happy with the result. I occasionally daydream about revisiting resident scheduling (I don't recommend it, the people who use your software leave every year, are not business oriented, and don't understand the complexity of the task until they've tried it on their own their first and only attempt). If I did, I would focus less on algorithms, and more on incentives to reconcile the tension between the organization, which wants to cover the most shifts with the fewest people at the cost of flexibility and preferences, and the staff, who want more flexibility and more preferences satisfied. I think that is the core problem at a business level.

bombcar 4y ago
The easiest way to solve the tension is probably to add additional money into the mix - the hard to fill shifts get paid a bonus, etc. someone would figure out how to game it of course but you already have this somewhat when overnights pay more.
- linuxftw 4y ago
  I was thinking similarly. Have people bid on shifts.