Optimize Surface Link Split to Support Large Airport Map

TL;DR We proposed several optimizations for surface link generation. The new implementation produces the same links as before but takes 99.7% less time (sfo-terminal-2 from 43.54s down to 0.13s).

Background

Surface reads the nodes (gates and spot positions) and links (pushback ways, taxiways and runways) from the airport surface map. In order to build a node-link graph for RoutingExpert, we need to split links at intersections. The following image shows some of the splits (red dots).

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 43.54s to finish. The number is used as a baseline across all optimizations. For the expanded map (sfo-all-terminals) with 101 gates, all taxiways and 4 runways, it takes 2 hours and a half.

Previous Design

The previous implementation handles all cases that any node or link endpoint interacts with any link.

all_nodes = self.nodes

for link in self.links:
    all_nodes.append(link.start)
    all_nodes.append(link.end)

while self.__break_next_link(all_nodes):
    pass

# function __break_next_link
for node in all_nodes:
  # Runways
  for runway in self.runways:
  	if runway.contains_node(node):
    	# ... break link
        return True
  # ... Same for taxiways and pushback ways
return False

The time complexity is O(B * N * L * n(L)), 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. L is the number of links and L = R + T + P, and R, T, P represents the number of runways, taxiways and pushback ways respectively. n(L) represents the segments on the link. B is the number of splits.

Optimization

We proposed three optimizations as follows:

Baseline	1️⃣	2️⃣	3️⃣	1️⃣ + 2️⃣ + 3️⃣
43.54s	33.87s (22.2%⬇)	2.90s (93.3%⬇)	2.82s (93.5%⬇)	0.13s (99.7%⬇)

1️⃣ Remove Redundant Information

On airport surface, gates and gates will not intersect with any other link for sure. So we can remove them from all_nodes.

Also, runways are relatively simple. We can also skip checking runways if we can mannually make sure the taxiways do not intersect with runways. For arrival flights (future plan), we can manually add additional taxiways to connect runways and other taxiways.

The updated time complexity is O(B * N * L * n(L)), where N = 2*L and L = T + P.

2️⃣ Pre-Calculate Link Coverage Boundary

The airport surface is pretty sparse. So most nodes will not intersect with one specific link. It takes O(n(L)) to check if a node intersects with a link. There are often more than one (and maybe more) segments on a link. The idea is to make the check O(1) with pre-processing. For example, to intersect with the link, the node must be in the area the link covers, i.e. the blue box. If the node is not in the boundary, we can return early. Otherwise, we check each segment on the link.

To avoid the case where a node is close to one link but is out of the boundary, the implementation extends the boundary by a tolerance threshold ("close_node_link_threshold"). It is defined in the config and was used to check if the node is on a link. When caulculating the boundary, the threshold will be converted from feet to geo position (latitude and longtitude) using Vincenty's formulae.

The average time complexity is O(B * N * L) and worst-case time complexity is O(N * L * n(L)).

3️⃣ Remove Nodes After No More Splits Found

The previous design checks one node every time even if it no longer intersects with other links. We can remove it after it is intersection-free.

The updated time complexity is O(N * L * n(L)).

Conclusion

With all three optimizations combined, the updated (average) time complexity is O(N * L), where N = 2*L and L = T + P.

The optimized implementation has a significantly better performance, especially for large data set.

• For sfo-terminal-2, the runtime is reduced from 43.54s to 0.13s.
• For sfo-all-terminals, the runtime is reduced from 143 minutes to 42s.

References

1. Wikipedia contributors. (2018, September 14). Vincenty's formulae. In Wikipedia, The Free Encyclopedia. Retrieved 06:41, October 2, 2018, from https://en.wikipedia.org/w/index.php?title=Vincenty%27s_formulae&oldid=859499868