8 ms·

Crew scheduling is complex. At the large airline I used to work for (not AA), they ran network solvers that took months to optimally resolve. Intermediate solut

Crew scheduling is complex. At the large airline I used to work for (not AA), they ran network solvers that took months to optimally resolve. Intermediate solutions were available, but the constraints of union contracts, labor laws, the location of people, and the changing schedule of flights meant that optimally solving for minimum labor costs, and impact to our crews' lives, was not trivial.

kevinmhickey 9y ago
I too have worked on airline crew scheduling. The merging of union contracts, federal regulations, company policies and, like you said, the changing flight schedule, created insane complexity. The fact that the whole system at all airlines is essentially auction-based with seniority being the currency of the realm is pretty interesting. The low-rank crew seeing time off available those days had to be pretty shocking.
jimnotgym 9y ago
I wonder how far away we are from self flying planes? Whilst there is the added problem of the third dimension over cars, perhaps this domain suffers less from the problem of lots of disorderly users in the same space?
- MengerSponge 9y ago
  It'll never happen. Modern planes are mostly self-flying, but you must have a human expert able to intervene if something goes wrong. https://99percentinvisible.org/episode/children-of-the-magenta-automation-paradox-pt-1/ https://99percentinvisible.org/episode/children-of-the-magen... Actually, let me correct that. We already have self-flying planes. They're called drones! We don't use them to transport anything as valuable as humans though.
  - JumpCrisscross 9y ago
    > you must have a human expert able to intervene if something goes wrong Similar things were said about cars. Humans make mistakes at certain rates, in predictable as well as novel situations. When the autopilot performs, on average, better, humans will become a safety liability.
    - MengerSponge 9y ago
      The autopilot has to outperform trained experts with hundreds of flight hours and an exceptionally high code of personal conduct. Self driving cars have to outperform the average person who drives like a 100-year-old blind dog who’s texting while driving and drinking a smoothie. Also, their failure mode is easier and much less expensive.
      - JumpCrisscross 9y ago
        It’s a difficult problem that we have not solved. But you said “must”. That’s a strict word to use for a problem that can be solved within a decade or two.
        yladiz 9y ago
        As someone who isn't afraid of flying (except in the case where the pilot has to suddenly drop the airplane due to turbulence) I still wouldn't trust a pilotless airplane until it's safer then with a pilot, which will be very difficult to prove. I feel also that I'm not alone and many people who fly would be extremely wary of a pilotless system. On the other hand, I would be much more likely to trust a self driving car. The main reason is that, if a self driving car malfunctions, the risk of my death is present but not absolutely guaranteed and with all of the safety features in a car it's likely I would still be alive after a crash, even at high speeds. A plane that has an autopilot malfunction, with no human present, without changes to the safety during a crash, would be essentially guaranteed to kill everyone on board. Until a plane can crash from the sky without killing all passengers in most scenarios, I wouldn't fly in a pilotless airplane.
        ramzyo 9y ago
        Agreed, my primary gripe with the original comment was that the OP used the word “must.”
    - mveety 9y ago
      Airline passengers don't generally care about it being safer on average. If the autopilot can't make a landing in a 30 kt crosswind all of the time people won't fly on that plane. People have much higher standards for acceptable safety with aircraft than cars. Also, autopilot isn't really designed to replace the pilot. Its designed to reduce workloads during departure and approach and make cruise less shitty. Autopilots are entirely unable to handle even simple failures and even in many cases do simple things like climb at a specific airspeed or do wind drift corrections. Car are just much simpler, have fewer consequences, and have lower expectations of safety. Until we get more versatile autopilots, aircrew acceptance, and/or lower expectations of safety, I don't see self-flying airliners anytime soon.
  - ramzyo 9y ago
    Wait, how does the article support your statement? The article concludes with this bit from it’s quoted “expert”: “Langewiesche thinks that we are ultimately heading toward pilotless planes. And by the time that happens, the automation will be so good and so reliable that humans, with all of their fallibility, will really just be in the way.” Also, I don’t have a hard number for this, but most commercial aviation crashes (like the Air France one, Colgan Air in 2009, AirAsia a few years ago) are due to pilot error or factors that don’t have to do with automation vs pilots (Malaysian Air that was shot down over Ukraine, TWA 800, and others)
    - sokoloff 9y ago
      You can't just look at the crashes without giving offsetting credit for crashes avoided by human intervention. (USAir 1549 or United 232 as possible examples.)
      - ramzyo 9y ago
        True, those are good counter examples, thanks for sharing. Here’s a reference from the BBC (sourcing a Boeing report from 2003) that states that approximately 80% of commercial aviation accidents were caused by pilot error (when the study was performed in 2003). http://www.bbc.com/travel/story/20130521-how-human-error-can-cause-a-plane-crash http://www.bbc.com/travel/story/20130521-how-human-error-can...
        lostboys67 9y ago
        Blaming the dead pilots is easy as my Uncle (ex Merchant Marine) said about the Concordia sinking - they always crucify the captain.
        kk_cz 9y ago
        You mean that guy who brought the ship dangerously close to an island (300m vs the planned 8km), because he watned to impress his girlfriend and then "accidentaly" fell into a lifeboat and left the sinking ship? Not the best example IMHO.
- danso 9y ago
  I assume for that to happen, we'd have to have mostly self-automated air control operations. Besides the technological improvements (which might be relatively minor), there would likely be the "human" delay, e.g. you can't just fire the vast majority (assuming towers will always have some human help) of air control operators within a few years or even a decade.
  - DigitalJack 9y ago
    Reagan did. https://www.history.com/this-day-in-history/reagan-fires-11359-air-traffic-controllers https://www.history.com/this-day-in-history/reagan-fires-113...
- tjmc 9y ago
  When someone can say with a straight face that the passengers of US Airlines flight 1549 and Qantas flight QF32 would be alive without the heroes they had up front.
  - gibybo 9y ago
    QF32 is tricky, but I don't see why a computer couldn't have easily landed US Air 1549. It would have known exactly whether it was capable or not of returning to the airport and immediately deciding on an alternative landing location if not. Handling an engine failure during takeoff and landing on water are both textbook training scenarios for all airline pilots, they would surely be handled by any self flying plane designed to operate without a human pilot.
    - imajes 9y ago
      in the NTSB investigation, it appeared that there was literally only about 30 seconds at the outset to evaluate returning, and even then, with immediate returns, pilots were only able to return 7 out of 13 tests. Textbook and theory doesn't always supercede knowledge of the area and novel thinking.
- Merad 9y ago
  The main reason we don't have them is that people don't want them. Autopilots date back to 1912 (yep, you read that right) and the first flight off an aircraft controlled 100% by autopilot happened in 1947. US Navy carriers and aircraft have been capable of automatic landings since the 1960s. IIRC today most larger airliners have autopilots capable of handling the entire flight after take off (they don't bother to include auto takeoff, because no one uses it). Aircraft are downright trivial to automate compared to cars, at least until something goes wrong. The vast majority of the time a car can drop into a fairly reasonable failsafe mode of "steer straight and apply brakes." Aircraft, not so much.
  - JumpCrisscross 9y ago
    > people don't want them The one thing American travellers are consistent on is choosing the cheapest flight. Autopiloted flights, at a discount, would sell tickets. That said, I don’t think we there yet technologically.
    - Merad 9y ago
      Pilots just aren’t that expensive, to be honest. Assuming your flight crew is costing $400 per hour combined (on the high side according to some googling) and you have a 6 hour flight with 300 passengers, eliminating the crew only drops prices by $8 per ticket.
      - JumpCrisscross 9y ago
        The most common commercial plane in America is the Boeing 737 [1]. It seats 100 to 200 passengers [2]. Delta officers and first captains make $320 and $200 thousand, respectively, and fly about 1,000 hours a year [3]. So 520 per hour, between the two of them. A main-cabin ticket to New York from San Jose, California about 2 months out costs $146. (Its SJC to MSP leg happens to be on a 737.) Flight time is about 6 hours. Assuming 175 (one-class 737-800 configuration) paying passengers we have about $25,000 in revenues. The captain and first officer’s pay is roughly 12% of that. That’s a lot. [1] http://www.fi-aeroweb.com/US-Commercial-Aircraft-Fleet.html http://www.fi-aeroweb.com/US-Commercial-Aircraft-Fleet.html [2] https://en.m.wikipedia.org/wiki/Boeing_737 https://en.m.wikipedia.org/wiki/Boeing_737 [3] http://onemileatatime.boardingarea.com/2016/12/01/delta-pilot-pay-raise/ http://onemileatatime.boardingarea.com/2016/12/01/delta-pilo...
applecrazy 9y ago
I've always wondered how the algorithms behind scheduling different events work given certain constraints. Are there resources (papers, articles, etc.) where I can learn about these algorithms, or even just a search query I can try that will point me in the right direction? EDIT: spelling
- mlevental 9y ago
  clrs has plenty on it.
  - applecrazy 9y ago
    thanks, but I was looking for the specific name of the algorithm. I don't even know what to call it, a dependency graph solving algorithm or something?
    - Kliment 9y ago
      a constraint solver, they're used heavily in CAD as well
    - ddinh 9y ago
      I imagine you could encode the problem as a CSP with each of the legal/contractual factors as a constraint. Despite NP-hardness of CSPs in general, CSP solvers are pretty efficient if the constraints are sparse enough and not chosen adversarially.
    - mmillin 9y ago
      A basic start would be looking at network flow problems. While they don't extend to the complexity of real world airline scheduling, you can construct a simplified airline scheduling problem with it. Additionally, one of the methods to solve these problems, linear programming, does extend to integer linear programming which can be used to solve the more complicated cases (in non-deterministic polynomial time).
vailripper 9y ago
No kidding - I worked on a project for a large airline optimizing reserve levels for flight crews and it was pretty fascinating work. The complexity explodes once you scratch past the surface.

kevinmhickey 9y ago

I too have worked on airline crew scheduling. The merging of union contracts, federal regulations, company policies and, like you said, the changing flight schedule, created insane complexity. The fact that the whole system at all airlines is essentially auction-based with seniority being the currency of the realm is pretty interesting. The low-rank crew seeing time off available those days had to be pretty shocking.

jimnotgym 9y ago

I wonder how far away we are from self flying planes? Whilst there is the added problem of the third dimension over cars, perhaps this domain suffers less from the problem of lots of disorderly users in the same space?

MengerSponge 9y ago
It'll never happen. Modern planes are mostly self-flying, but you must have a human expert able to intervene if something goes wrong. https://99percentinvisible.org/episode/children-of-the-magenta-automation-paradox-pt-1/ https://99percentinvisible.org/episode/children-of-the-magen... Actually, let me correct that. We already have self-flying planes. They're called drones! We don't use them to transport anything as valuable as humans though.
- JumpCrisscross 9y ago
  > you must have a human expert able to intervene if something goes wrong Similar things were said about cars. Humans make mistakes at certain rates, in predictable as well as novel situations. When the autopilot performs, on average, better, humans will become a safety liability.
  - MengerSponge 9y ago
    The autopilot has to outperform trained experts with hundreds of flight hours and an exceptionally high code of personal conduct. Self driving cars have to outperform the average person who drives like a 100-year-old blind dog who’s texting while driving and drinking a smoothie. Also, their failure mode is easier and much less expensive.
    - JumpCrisscross 9y ago
      It’s a difficult problem that we have not solved. But you said “must”. That’s a strict word to use for a problem that can be solved within a decade or two.
      - yladiz 9y ago
        As someone who isn't afraid of flying (except in the case where the pilot has to suddenly drop the airplane due to turbulence) I still wouldn't trust a pilotless airplane until it's safer then with a pilot, which will be very difficult to prove. I feel also that I'm not alone and many people who fly would be extremely wary of a pilotless system. On the other hand, I would be much more likely to trust a self driving car. The main reason is that, if a self driving car malfunctions, the risk of my death is present but not absolutely guaranteed and with all of the safety features in a car it's likely I would still be alive after a crash, even at high speeds. A plane that has an autopilot malfunction, with no human present, without changes to the safety during a crash, would be essentially guaranteed to kill everyone on board. Until a plane can crash from the sky without killing all passengers in most scenarios, I wouldn't fly in a pilotless airplane.
      - ramzyo 9y ago
        Agreed, my primary gripe with the original comment was that the OP used the word “must.”
  - mveety 9y ago
    Airline passengers don't generally care about it being safer on average. If the autopilot can't make a landing in a 30 kt crosswind all of the time people won't fly on that plane. People have much higher standards for acceptable safety with aircraft than cars. Also, autopilot isn't really designed to replace the pilot. Its designed to reduce workloads during departure and approach and make cruise less shitty. Autopilots are entirely unable to handle even simple failures and even in many cases do simple things like climb at a specific airspeed or do wind drift corrections. Car are just much simpler, have fewer consequences, and have lower expectations of safety. Until we get more versatile autopilots, aircrew acceptance, and/or lower expectations of safety, I don't see self-flying airliners anytime soon.
- ramzyo 9y ago
  Wait, how does the article support your statement? The article concludes with this bit from it’s quoted “expert”: “Langewiesche thinks that we are ultimately heading toward pilotless planes. And by the time that happens, the automation will be so good and so reliable that humans, with all of their fallibility, will really just be in the way.” Also, I don’t have a hard number for this, but most commercial aviation crashes (like the Air France one, Colgan Air in 2009, AirAsia a few years ago) are due to pilot error or factors that don’t have to do with automation vs pilots (Malaysian Air that was shot down over Ukraine, TWA 800, and others)
  - sokoloff 9y ago
    You can't just look at the crashes without giving offsetting credit for crashes avoided by human intervention. (USAir 1549 or United 232 as possible examples.)
    - ramzyo 9y ago
      True, those are good counter examples, thanks for sharing. Here’s a reference from the BBC (sourcing a Boeing report from 2003) that states that approximately 80% of commercial aviation accidents were caused by pilot error (when the study was performed in 2003). http://www.bbc.com/travel/story/20130521-how-human-error-can-cause-a-plane-crash http://www.bbc.com/travel/story/20130521-how-human-error-can...
      - lostboys67 9y ago
        Blaming the dead pilots is easy as my Uncle (ex Merchant Marine) said about the Concordia sinking - they always crucify the captain.
        kk_cz 9y ago
        You mean that guy who brought the ship dangerously close to an island (300m vs the planned 8km), because he watned to impress his girlfriend and then "accidentaly" fell into a lifeboat and left the sinking ship? Not the best example IMHO.
danso 9y ago
I assume for that to happen, we'd have to have mostly self-automated air control operations. Besides the technological improvements (which might be relatively minor), there would likely be the "human" delay, e.g. you can't just fire the vast majority (assuming towers will always have some human help) of air control operators within a few years or even a decade.
- DigitalJack 9y ago
  Reagan did. https://www.history.com/this-day-in-history/reagan-fires-11359-air-traffic-controllers https://www.history.com/this-day-in-history/reagan-fires-113...
tjmc 9y ago
When someone can say with a straight face that the passengers of US Airlines flight 1549 and Qantas flight QF32 would be alive without the heroes they had up front.
- gibybo 9y ago
  QF32 is tricky, but I don't see why a computer couldn't have easily landed US Air 1549. It would have known exactly whether it was capable or not of returning to the airport and immediately deciding on an alternative landing location if not. Handling an engine failure during takeoff and landing on water are both textbook training scenarios for all airline pilots, they would surely be handled by any self flying plane designed to operate without a human pilot.
  - imajes 9y ago
    in the NTSB investigation, it appeared that there was literally only about 30 seconds at the outset to evaluate returning, and even then, with immediate returns, pilots were only able to return 7 out of 13 tests. Textbook and theory doesn't always supercede knowledge of the area and novel thinking.
Merad 9y ago
The main reason we don't have them is that people don't want them. Autopilots date back to 1912 (yep, you read that right) and the first flight off an aircraft controlled 100% by autopilot happened in 1947. US Navy carriers and aircraft have been capable of automatic landings since the 1960s. IIRC today most larger airliners have autopilots capable of handling the entire flight after take off (they don't bother to include auto takeoff, because no one uses it). Aircraft are downright trivial to automate compared to cars, at least until something goes wrong. The vast majority of the time a car can drop into a fairly reasonable failsafe mode of "steer straight and apply brakes." Aircraft, not so much.
- JumpCrisscross 9y ago
  > people don't want them The one thing American travellers are consistent on is choosing the cheapest flight. Autopiloted flights, at a discount, would sell tickets. That said, I don’t think we there yet technologically.
  - Merad 9y ago
    Pilots just aren’t that expensive, to be honest. Assuming your flight crew is costing $400 per hour combined (on the high side according to some googling) and you have a 6 hour flight with 300 passengers, eliminating the crew only drops prices by $8 per ticket.
    - JumpCrisscross 9y ago
      The most common commercial plane in America is the Boeing 737 [1]. It seats 100 to 200 passengers [2]. Delta officers and first captains make $320 and $200 thousand, respectively, and fly about 1,000 hours a year [3]. So 520 per hour, between the two of them. A main-cabin ticket to New York from San Jose, California about 2 months out costs $146. (Its SJC to MSP leg happens to be on a 737.) Flight time is about 6 hours. Assuming 175 (one-class 737-800 configuration) paying passengers we have about $25,000 in revenues. The captain and first officer’s pay is roughly 12% of that. That’s a lot. [1] http://www.fi-aeroweb.com/US-Commercial-Aircraft-Fleet.html http://www.fi-aeroweb.com/US-Commercial-Aircraft-Fleet.html [2] https://en.m.wikipedia.org/wiki/Boeing_737 https://en.m.wikipedia.org/wiki/Boeing_737 [3] http://onemileatatime.boardingarea.com/2016/12/01/delta-pilot-pay-raise/ http://onemileatatime.boardingarea.com/2016/12/01/delta-pilo...

applecrazy 9y ago

I've always wondered how the algorithms behind scheduling different events work given certain constraints. Are there resources (papers, articles, etc.) where I can learn about these algorithms, or even just a search query I can try that will point me in the right direction? EDIT: spelling

mlevental 9y ago
clrs has plenty on it.
- applecrazy 9y ago
  thanks, but I was looking for the specific name of the algorithm. I don't even know what to call it, a dependency graph solving algorithm or something?
  - Kliment 9y ago
    a constraint solver, they're used heavily in CAD as well
  - ddinh 9y ago
    I imagine you could encode the problem as a CSP with each of the legal/contractual factors as a constraint. Despite NP-hardness of CSPs in general, CSP solvers are pretty efficient if the constraints are sparse enough and not chosen adversarially.
  - mmillin 9y ago
    A basic start would be looking at network flow problems. While they don't extend to the complexity of real world airline scheduling, you can construct a simplified airline scheduling problem with it. Additionally, one of the methods to solve these problems, linear programming, does extend to integer linear programming which can be used to solve the more complicated cases (in non-deterministic polynomial time).

vailripper 9y ago

No kidding - I worked on a project for a large airline optimizing reserve levels for flight crews and it was pretty fascinating work. The complexity explodes once you scratch past the surface.