It's essentially an optimizing constraint solving problem. As far as I know, there are 2 main known approaches to this class of problem:
- 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).
Other paid constraint solvers are Gurobi and IBM’s Cplex. I only have experience with the later - scheduling giant chemistry and biology experiences into a robotic factory - there are a ton of foot guns in this space.
IBM has ILOG as well which is likely a better match for scheduling problems.
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.
- 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).