Writing an Airline Routing Algorithm Efficiently

Question

Given:

• A database of flights (departing city, arrival city, departure time, arrival time).

Questions:

• What would be the most efficient algorithm for listing service between two cities, if departure time is unimportant? Consider that we want to minimize layover time (but still above a nominal minimum, i.e. 20 minutes), and minimize the number of stopovers (if there is a nonstop route, this is trivial, but if not, finding one-connection routes over two-connection and so on, with reasonable stopover times, less trivial).
• If at all possible, I don't want to have to specifically label any airports as hubs, so as to leave open the possibility of point-to-point route networks.
• There should be an option to specify a desired (approximate) departure time. It is OK if this has its own algorithm separate from the first.

Code language for this project hasn't been chosen yet (probably a .NET language, since quick forms will come in handy), so pseudocode algorithms are preferred. I'll keep an eye out for follow-up questions if added info might help.

Answer 1

At the base, you're going to view your city network as a tree, with departing city as root, and each departing flight being a pointer to a child. You'll do a recursive depth-first search through the tree to find all paths to the destination, but checking for a cycle as you go and aborting any path that results in a cycle.

As you find feasible paths, you can either just keep the shortest yet found as a singular solution; or keep a larger subset of paths found, stratified by some criteria around departure time if you want to select on that basis.

Depending on the specifics of the database and nodes, you can also throw in other rules for cutting short your path searches, e.g., if you happen to know that departure and destination are 1000 miles apart, and your path traced so far has you flying 3000 miles and you're still not there, screw it, move on to the next path search.

Answer 2

Dijkstra or A*, the weights being some kind of penalty for long waiting times and many stops.

Answer 3

After breaking down the responses, I'm trying an algorithm based on marking down manually airports that are "connecting" airports. This saves looking through potentially hundreds of airports that can't possibly connect anywhere (when is the last time you connected from New York to Tokyo via Cedar Rapids?). This covers up to 2 layovers, after 2 layovers I'll go with special case algorithms, a complete tree search, or mark the route "not served" (which a lot of real airlines do, but for a game this should be player customizable anyways.

The current model goes like so:

Find Nonstop!

• Is there a direct route from the origin airport to the destination airport? Excellent! Return the non-stop list (the requesting algorithm can decide what to do with it).

No nonstop connection?

• Assemble all flights from the origin airport to "connecting" airports (all hubs and focus cities).
• Assemble all flights arriving at the destination airport from these "connecting" airports (all hubs and focus cities).
• Create all possible paths (Origin-Connection-Destination)
• Trim this list to all "possible" paths (eliminate connections that are not sequential, eliminate all paths with layovers under 20 minutes).
• Sort this list by total travel time (flight time + layover time).

No one-stop connection?

• Assemble all flights from the origin airport to "connecting" airports (all hubs and focus cities).
• Assemble all flights arriving at the destination airport from ANY "connecting" airports (all hubs and focus cities).
• Assemble all flights between "connecting" airports the origin airport flies to, and "connecting" airports that fly to the destination. (Hub-to-Hub)
• Create all possible paths (Origin-Connection-Connection-Destination)
• Trim this list to all "possible" paths (eliminate connections that are not sequential, eliminate all paths with layovers under 20 minutes).
• Sort this list by total travel time.