Writing an airline routing algorithm efficiently

Question

Given:

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

Questions:

• What would be the most efficient algorithm for enumerating a service between two cities if the departure time does not matter? Think that we want to minimize downtime (but still above the nominal minimum, i.e. 20 minutes), and minimize the number of stops (if there is a non-stop route, this is trivial, but if not, then search for routes of one connection in two -connection, etc., with a reasonable stopping time, less trivial).
• If at all possible, I don’t want to specifically label any airports as hubs so as not to open up the possibilities of point-to-point route networks.
• There should be an option to indicate the desired (approximate) departure time. This is normal if it has its own algorithm different from the first one.

The code language for this project has not yet been selected (possibly the .NET language, since quick forms will be useful), so pseudo-code algorithms are preferred. I will follow up on further questions if additional information can help.

Answer 1

In the database, you will consider your city network as a tree, with the outgoing city as the root, and each outgoing flight is a pointer to a child. You will do a recursive depth search using the tree to find all the paths to the destination, but checking the loop when you go and interrupting any path that leads to the loop.

When you find possible paths, you can either just save the shortest, but find it as the only solution; or keep a higher subset of the paths found, stratified by some criteria regarding departure time, if you want to choose on this basis.

Depending on the specifics of the database and nodes, you can also use other rules to reduce your search for paths, for example, if you know that the departure and destination are located at a distance of 1000 miles and your trace is still flying at 3000 miles, and you're still not there, spin it, go to the next search path.

Answer 2

Dijkstra or A * , scales are a kind of fine for a long waiting time and many stops.

Answer 3

After breaking up the answers, I try to use an algorithm based on manually marking the airports that “connect” the airports. It saves by looking through potentially hundreds of airports that can't connect anywhere (when was the last time you connected from New York to Tokyo via Cedar Rapids?). It covers up to 2 layovers, after 2 layovers I will go using special case algorithms, complete tree search or mark the route “not served” (which is a lot of real airlines, but for the game it has to be a custom player anyway.

The current model looks like this:

Find Nonstop!

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

No non-stop connection?

• Collect all flights from the airport of origin to the “connecting” airports (all nodes and focal cities).
• Collect all flights arriving at the destination airport from these “connecting” airports (all centers and focal cities).
• Create all possible paths (Origin-Connection-Destination)
• Trim this list to all "possible" paths (exclude connections that are not sequential, exclude all paths with shims less than 20 minutes).
• Sort this list by total trip time (flight time + downtime).

No single connection?

• Collect all flights from the airport of origin to the “connecting” airports (all nodes and focal cities).
• Collect all flights arriving at the destination airport from ANY “connecting” airport (all hubs and focus cities).
• Collect all flights between the “connecting” airports from where the arrival airport departs and the “connecting” airports that depart to your destination. (Concentrator-to-concentrator)
• Create all possible paths (Origin-Connection-Connection-Destination)
• Trim this list to all "possible" paths (exclude connections that are not sequential, exclude all paths with shims less than 20 minutes).
• Sort this list by total trip time.