4 ms·

Computational Complexity of Air Travel Planning (2003) [pdf]

lunchladydoris 8y ago
In the excellent book Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal, about the life of J.C.R. Licklider, there is the story of how SAGE, the system used for command-and-control strategic planning, was modified to become SABRE, the first airline reservation system. This has been a computational problem for a long time.
paidleaf 8y ago
I'd assume it has the same complexity that all scheduling problem have ( like the canonical college classes scheduling that most of us learn about ).
dmichulke 8y ago
I'm working on a similar project (kind of "Uber for air travel via private chartering") with a few different variables but still huge dimensionality for a set of aircraft and pilots, among them relations between airport (AP), pilot (P), aircraft (AC) - AC can take off/land on AP (runway is long enough, runway material is compatible, flight rules are ok) - P is close enough (by car) to AP - P is allowed to fly to AC - P is available during out/inbound flight - AP opening hours are respected - AP fees (depending on AC and passengers) are respected - AC is available during out/inbound flight - travel time affects many of the above criteria, e.g., faster machines might fly to different airports (more because they're still open, less because they require longer/better runways) - when changing countries you need to go through an airport with customs - when travelling long ranges, you need to refuel - weights of passenger + luggage + fuel don't exceed predefined aircraft weight constraints - You may need to fly your AC to AP1 to pick up the passengers, then refuel at AP2 and declare your goods there and deliver all at AP3 and then go back efficiently (possible skipping AP1 and/or AP2) or stay there and wait for the passengers to go back using a different AP when declaring your goods upon reentry into your original country. I'm doing this mostly using application logic (travel planning) and postgres queries (finding travel legs) and it works well for 1k airports and 300 machines but if anyone has suggestions or questions, I'll be happy to share details.
- jpalomaki 8y ago
  Might be interesting to use logic programming (for example Prolog) or some rule engine to deal with these. Put in the requirements and then ask what options are available. For example Prolog can do this via backtracking. I was once doing research for an optimization task and found out the related term is "integer programming". Compared to linear optimization the difference is that you have integer constraints. Like the plane either flies or it does not, you can't use 0.9 of this plane and 0.1 of the other. It was also revealing to find out the problem is NP-complete, so there's no easy solution or some magical algorithm. In your case, the proper thing might be mixed-integer programming. Setting some constraints as integers (you need to have 2 pilots, they need to be the same for the whole flights) and others like travel speed as linear. I was checking these years ago and at least back then there was not too many open source packages for this kind of optimization. Various commercial packages did exist.
  - wenc 8y ago
    There is a bit of an art to formulating a correct and efficient mixed integer program (MIP) of non-trivial size, and in my experience, it's not something that can be picked up easily. It's easy to formulate toy problems (most of us use this guide [1]), but formulating large complex problems efficiently requires quite a bit of know-how and years of study (e.g. convex hull relaxations, custom cuts, heuristics, decomposition, leveraging randomness, etc.) This kind of thing lie in the domain of specialists (operations research folks) rather than software developers. The performance of commercial solvers (Gurobi, CPLEX, Xpress) has improved a lot and many are used in things like airline crew scheduling. The best open-source MIP solver is currently CBC (SCIP is better but only free for non-commercial use), but commercial solvers beat these by a mile. Even so large-scale MIPs are still complex beasts. It's worth noting that if the problem doesn't require any optimization (merely constraint satisfaction), MIPs might be overkill. A rules engine would probably be easier to implement and maintain. Even SQL (which is set theory in disguise) will often get you most of the way there. And if optimization was needed, a greedy algorithm would probably work most of the time. There are many successful commercial applications of MIPs but typically they are in circumscribed areas. MIPs are best deployed when there is a definite need for an optimal result, and when there is expertise available to maintain the resulting complex models. (Note: even ITA software in the linked article didn't attempt to model the problem as an MIP) [1] https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf
essayist 8y ago
Possibly relevant: https://systemswe.love/videos/life-of-an-airline-flight https://systemswe.love/videos/life-of-an-airline-flight
chasd00 8y ago
i'm on a conference call right now about this very subject. No one understands how complex scheduling systems are or can become. It's easy to think about but difficult to automate.
- User23 8y ago
  I'd say it's actually not the easy to think about. There is a lot of complexity it's easy to just ignore when your brain keeps dragging you back to the trivial, computationally, scheduling concerns in your own life. It's a good example of how the brain can have a basically wrong model that is good enough for a tiny part of the problem space commonly encountered.
User23 8y ago
One neat thing is that their fallback mechanism is to have a human being sort out the mess. There are offices full of people whose job it is to find a workaround or at least smooth ruffled feathers. Sometimes it doesn't work out.

In the excellent book Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal, about the life of J.C.R. Licklider, there is the story of how SAGE, the system used for command-and-control strategic planning, was modified to become SABRE, the first airline reservation system. This has been a computational problem for a long time.

paidleaf 8y ago

I'd assume it has the same complexity that all scheduling problem have ( like the canonical college classes scheduling that most of us learn about ).

dmichulke 8y ago

I'm working on a similar project (kind of "Uber for air travel via private chartering") with a few different variables but still huge dimensionality for a set of aircraft and pilots, among them relations between airport (AP), pilot (P), aircraft (AC) - AC can take off/land on AP (runway is long enough, runway material is compatible, flight rules are ok) - P is close enough (by car) to AP - P is allowed to fly to AC - P is available during out/inbound flight - AP opening hours are respected - AP fees (depending on AC and passengers) are respected - AC is available during out/inbound flight - travel time affects many of the above criteria, e.g., faster machines might fly to different airports (more because they're still open, less because they require longer/better runways) - when changing countries you need to go through an airport with customs - when travelling long ranges, you need to refuel - weights of passenger + luggage + fuel don't exceed predefined aircraft weight constraints - You may need to fly your AC to AP1 to pick up the passengers, then refuel at AP2 and declare your goods there and deliver all at AP3 and then go back efficiently (possible skipping AP1 and/or AP2) or stay there and wait for the passengers to go back using a different AP when declaring your goods upon reentry into your original country. I'm doing this mostly using application logic (travel planning) and postgres queries (finding travel legs) and it works well for 1k airports and 300 machines but if anyone has suggestions or questions, I'll be happy to share details.

jpalomaki 8y ago
Might be interesting to use logic programming (for example Prolog) or some rule engine to deal with these. Put in the requirements and then ask what options are available. For example Prolog can do this via backtracking. I was once doing research for an optimization task and found out the related term is "integer programming". Compared to linear optimization the difference is that you have integer constraints. Like the plane either flies or it does not, you can't use 0.9 of this plane and 0.1 of the other. It was also revealing to find out the problem is NP-complete, so there's no easy solution or some magical algorithm. In your case, the proper thing might be mixed-integer programming. Setting some constraints as integers (you need to have 2 pilots, they need to be the same for the whole flights) and others like travel speed as linear. I was checking these years ago and at least back then there was not too many open source packages for this kind of optimization. Various commercial packages did exist.
- wenc 8y ago
  There is a bit of an art to formulating a correct and efficient mixed integer program (MIP) of non-trivial size, and in my experience, it's not something that can be picked up easily. It's easy to formulate toy problems (most of us use this guide [1]), but formulating large complex problems efficiently requires quite a bit of know-how and years of study (e.g. convex hull relaxations, custom cuts, heuristics, decomposition, leveraging randomness, etc.) This kind of thing lie in the domain of specialists (operations research folks) rather than software developers. The performance of commercial solvers (Gurobi, CPLEX, Xpress) has improved a lot and many are used in things like airline crew scheduling. The best open-source MIP solver is currently CBC (SCIP is better but only free for non-commercial use), but commercial solvers beat these by a mile. Even so large-scale MIPs are still complex beasts. It's worth noting that if the problem doesn't require any optimization (merely constraint satisfaction), MIPs might be overkill. A rules engine would probably be easier to implement and maintain. Even SQL (which is set theory in disguise) will often get you most of the way there. And if optimization was needed, a greedy algorithm would probably work most of the time. There are many successful commercial applications of MIPs but typically they are in circumscribed areas. MIPs are best deployed when there is a definite need for an optimal result, and when there is expertise available to maintain the resulting complex models. (Note: even ITA software in the linked article didn't attempt to model the problem as an MIP) [1] https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf

essayist 8y ago

Possibly relevant: https://systemswe.love/videos/life-of-an-airline-flight https://systemswe.love/videos/life-of-an-airline-flight

chasd00 8y ago

i'm on a conference call right now about this very subject. No one understands how complex scheduling systems are or can become. It's easy to think about but difficult to automate.

User23 8y ago
I'd say it's actually not the easy to think about. There is a lot of complexity it's easy to just ignore when your brain keeps dragging you back to the trivial, computationally, scheduling concerns in your own life. It's a good example of how the brain can have a basically wrong model that is good enough for a tiny part of the problem space commonly encountered.

User23 8y ago

One neat thing is that their fallback mechanism is to have a human being sort out the mess. There are offices full of people whose job it is to find a workaround or at least smooth ruffled feathers. Sometimes it doesn't work out.