-
Notifications
You must be signed in to change notification settings - Fork 11
Redesign RoutingExpert to Support Large Airport Map
TL;DR We changed the algorithm RoutingExpert uses to find the shortest path from Floyd–Warshall to Shortest Path Faster Algorithm. It speeds up the running time by 98.5% (
sfo-terminal-2from 169.89s down to 2.46s).
RoutingExpert calculates the shortest path given two nodes on the airport surface. Its slow performance blocks the use of larger airport map. Previously, a small map (sfo-terminal-2) with only 14 gates, limited taxiways and 1 runway will take 169.89s to calculate the routing table. For the expanded map (sfo-all-terminals) with 101 gates, all taxiways and 4 runways, it can't finish within one hour.
The previous design treats the problem as a multiple-source shortest path problem. Furthermore, it chose to use Floyd–Warshall to calculate the shortest path given two arbitrary nodes on the airport surface. The time complexity is O(N^3), where N is the number of nodes and N = 2*L + S + G. L, S, G represents the number of links, spot positions and gates respectively.
The previous design puts too much effort calculating useless routes. The airport surface planning is a special case of the shortest path problem. The scheduler always schedules the whole route, i.e. from the current location of the aircraft to the runway (or to the gate for arrival flights). We don't need to know other routes, e.g. how to get from one gate to another.
Therefore, we can treat the planning as a single-source shortest path problem. Bellman–Ford algorithm is a suitable algorithm that runs in O(N*M) for one source node, where N and M are the numbers of nodes and links. Given that the airport surface graph is sparse -- there are more nodes than links, we decided to use the Shortest Path Faster Algorithm (SPFA), an improved version of the Bellman–Ford algorithm. The average time complexity is O(L) for one source node, where L is the number of links. The worst-case complexity of SPFA is the same as that of Bellman–Ford. Overall, to calculate the routes from any arbitrary node to any runway, the time complexity is O(L * R).
The performance of the algorithm is strongly determined by the order in which candidate nodes are used to relax other nodes. Therefore, Small Label First (SLF) technique is used here to rearrange the order of elements queue so that nodes closer to the source are processed first.
Generate Adjacency Map
Generate an adjacency map from the node-link model. It stores the shortest link between two nodes.
adjacency_map[start][end] = Link-
Link Close Nodes: Same as the previous design. Link two nodes with really short distance (using
is_close_tomethod). -
Add Existing Nodes: Same as the previous design. Add the links to the adjacency map.
Run SPFA to Find Shortest Routes
All runway nodes are filtered out and then stored as runway_nodes. For each runway node, run SPFA to find the shortest path from any arbitrary node to the runway node. The paths are stored in a routing table.
routing_table[runway_node][other_node] = RouteSLF Optimization
To enable SLF optimization, the candidates to relax other nodes are stored with a CandidateNeighbors. It provides queue-alike APIs including pop(), push(node), has(node), length() and re_order(). Internally, the candidate nodes are stored with a linked list and a hash set. The linked list allows O(1) pop and push operation while the hash set allows O(1) lookup operation for has(node).
The redesigned RoutingExpert significantly improves its performance, especially for large data set.
- For
sfo-terminal-2, the runtime is reduced from 169.89s to 2.46s. - For
sfo-all-terminals, the runtime is reduced from one hour+ to 36.37s.
- Wikipedia contributors. (2018, July 22). Shortest Path Faster Algorithm. In Wikipedia, The Free Encyclopedia. Retrieved 03:27, October 2, 2018, from https://en.wikipedia.org/w/index.php?title=Shortest_Path_Faster_Algorithm&oldid=851454606