I’m en route to the March Meeting in Portland, which involves a three-hour layover in Chicago, between two flights on Southwest, my preferred airline. I’m always impressed by how much more efficient Southwest seems that the other major airlines.
One weird manifestation of that efficiency is the flight plans that Southwest uses. Where most flights on other airlines seem to go back and forth between two cities over and over, Southwest’s routes tend to roam all over the country. This morning’s flight from Albany to Chicago continued on to San Antonio, TX, Phoenix, and San Jose. Another recent trip involved a flight from Albany to Baltimore, Kansas City, San Antonio, Las Vegas, and San Jose.
This always makes me wonder about the computation behind these flight plans. There’s got to be some logic to it, that allows them to get all the planes they need to the places they need them, presumably as cheaply as they can manage. The result is most likely derived empirically from crunching some numbers on existing flight networks, then optimizing the results, but it’s kind of amusing to imagine that the folks at Southwest are sitting on a solution to the Traveling Salesman Problem, and using it to gain an advantage over their competitors…
(It’s also a good idea for a throw-away element of a science fiction story about Singularity-type stuff, but I’m not the guy to write that…)
flight scheduling is actually a classic example of a use of the network flow class of algorithms which have exact solutions. They aren’t trying to find a Hamiltonian path, so the problem is somewhat relaxed.
Travelling salesman is part of it, but the whole problem that the airlines (all of them) are trying to solve is a lot more complicated than that. (Speaking informally about complexity, not in the complexity-theory sense.)
Trying to optimize on miles flown to it a particular tour of cities is a well-understood problem, even if we have no good solution for useful instances of it. Adding a bunch of different customers with route preferences that change over time doesn’t make it easier.
But the big under-appreciated factors are the scare resources of runway availability for departure and arrival, and the scarce resource of airport gates on the ground… and those come with different values since some gates are at the ass end of nowhere (comparatively speaking) and some are right up front, and some aircraft need more runway length than others.
Then, on top of that, recall that the airlines are in competition with each other, pursuing their own various strategies to please their customers and maximize revenue.
It is a hugely complex problem, and if memory serves some of the early work in auction theory and mechanism design fell out of some desperate attempts to come up with good collective solutions that didn’t tear the system apart.
As for Southwest, bear in mind that their meandering routes might be the solution to a different problem (fewer aircraft to dedicate to short routes) under some other looser constraints (willingness to take cheaper slots at farther terminals in smaller, regional airports.) It’s a good strategy for private fliers, but I wouldn’t want to use them for business trips because the extra hour I spend wandering from place to place in the airport is an hour spent not working, thus not charging my time, thus eaten by me personally.
The biggest difference, I imagine, is that Southwest only flies one type of plane. So they can use any plane on any route, which encourages meandering paths. On other airlines you see much more specialization – large planes flying long routes plus smaller plans on regional hops.
Josh has it right. Add that crew scheduling is at least as hard as equipment scheduling (there are possibly more FAA constraints on crew scheduling than on equipment scheduling) and that when you have multiple aircraft types, crew schedules create a constraint on equipment schedules (and vice versa): a pilot that’s used to flying Airbuses will be unhappy if dumped into a Boeing; it’s no wonder that airline schedulers look for simple, if suboptimal, solutions. SWA, by having a single aircraft type, starts with the setup that all legs are equivalent, all runways are equivalent, all gates are equivalent, all aircraft are equivalent and all crews are equivalent. They can then seek to optimize crew and equipment schedules subject to FAA constraints.
Modern computers can brute force solutions to these problems; probably nobody has bothered to code it. Or they already have :
Doazic @5.
Alas, no. Brute force solutions tend to take rather a long time for these sorts of problems. `Long time’ as in many powers of ten times the current age of the universe.
Try a simple brute force solution to this problem. Given a word, enumerate all distinct permutations of the letters in the word. In a few hours you could have the program up and running. Now try it on supercalifragilisticexpialidocius. If you want to stay awake until it finishes, you are going to need an awful lot of coffee.
Hi,
I’m Brazilian and crazy about science.
I’d like to congratulate you for the very interesting contents of this blog.
I have a science blog, written in Portuguese (soon it’ll have posts in English as well). Take a look at this link:
http://imperativocientifico.blogspot.com/
I hope we can change information, or develop a good “blogger” relationship. My e-mail address is: rtmatosribeiro@yahoo.com.br.
How can I keep contact with you?
Embraces,
Rafael Tadeu de Matos Ribeiro – Brazil
The other big difference between Southwest and other major airlines is that Southwest does not use the hub-and-spoke strategy. Most airlines will fly you from someplace like Albany to a hub city (depending on airline this could be Chicago/ORD, Atlanta, Newark, Philadelphia, etc.) from which they offer connecting flights to many other destinations. This system is great if you live in a hub city and somebody else is paying your airfare, because you get nonstop service to so many places. It’s bad for people who pay their own way, as the dominant airline can charge a premium for all of that nonstop service, and not so good for people at the ends of the spokes, who have to change planes to get to anywhere other than the handful of hubs. Oh, and you have to hope the weather isn’t too bad at the hub airport, or the airline’s schedule can become seriously hosed for up to 48 hours (been there, done that). Southwest’s approach is to offer nonstop flights from all of their airports to any other airport in their network for which they can feasibly offer service. I’ve had Southwest flights through Baltimore, Chicago/MDW, Las Vegas, and Phoenix; I could go to Orlando or Tampa, but I have no particular desire to visit Florida.
I did some work on airline scheduling back in the mid-90s. The typical scheduler did a simple next available allocation of aircraft to all the scheduled flights. This preserved topology and provided a solution, but an awful one. Then the algorithm tried swapping aircraft against aircraft for each segment. You can almost think of it as a kind of braiding, except that you could take two strands, cross them over like genes and substitute, and see if that raised the aircraft utilization factor. (I never really worked out the details, but I did play with a neat demo program that animated this type of search.) One improvement under consideration was using a Metropolis algorithm that allowed certain levels of degradation, randomly allowed subject to a “temperature” parameter. By slowly lowering the temperature and allowing fewer and smaller degradations, the solution would be “annealed”. That was supposed to avoid local minimum traps in the solution.
That was 15 years ago. P=NP is still an open question, but I gather that the same general approach is used.
Interestingly, the first thing the airlines did was schedule the flights, since that is what they sell. Then they’d schedule the aircraft. Then they’d schedule the flight crews who are highly specialized and subject to all sorts of complicated rules guaranteeing them a chance to sleep somewhere other than in the cockpit. Finally, they’d schedule the cabin crews who had their own constraints. Needless to say, as soon as any flying would start everything would go straight to hell.
It sounds like Southwest simplifies their scheduling given their use of a single type of aircraft, but the price has to be rougher schedules for crew – since fewer back-and-forth flights will leave crew away from home more often, or needing to deadhead more often.
You also have to look at servicing the aircraft. All aircraft take a certain amount of daily maintenance not to mention more invasive periodic inspections. The plane has to routed to an airport where the airline has mechanics, or has contracted mechanics, support equipment, facilities, and parts. Many inspections are based on flight hours or cycles (a take off followed by a landing). You need to manage it so all of your planes are not out of service at the same time.
Having a plane out of service at a remote airport is even worse. It greatly disrupts your carefully made schedules and having to fly equipment, parts, and sometime mechanics costs still more money.
I’ve always wondered that too, why they first send you to some city that’s completely in the other direction that you were going THEN send you back the other way. Nice post!
Sometimes the problems the airlines encounter are even harder than NP-complete. Sometimes they are undecidable
http://magic.aladdin.cs.cmu.edu/2006/02/02/ri-seminar-2006-02-07/ 🙂
The Traveling Salesman Problem is quite solvable. It of course scales exponentially (unless you believe P=NP), which means it’s impractical when the number of points gets large, but with enough cleverness and enough computers you can handle larger problems than you might think. Solutions have in fact been calculated for up to tens of thousands of points.
There are also pretty good approximation algorithms.