3.4 Connecting the Waypoints Into a Graph

Overview

In the previous section we identified all the enroute waypoints in our search corridor from Cold Bay (PACD) to Valdez Pioneer Field (PAVD). In this section we will connect these waypoints into a network.

Some Graph Theory

The field of math or computer science which deals with these types of problems is called Graph Theory. For simplicity we can say that graph is a collection of points we can call vertices, connected by lines we can call edges. Now, if you have a collection of points and try to connect them into a graph, you will quickly realize that there are many different ways you could do this. 

To create our graph we need only consider the following criteria:

• our requirements in section 1.1 say that each leg should take between 5 to 15 minutes of flight time; at a typical groundspeed for a Being 737, let's say this works out to about 30 to 80 nautical miles per leg 

• we do not need to optimize for fuel or speed, so we can set the edge weights to be equal to the physical distance between the waypoints

• we need to make sure the departure waypoint is connected to the arrival waypoint 

Now, we could run a loop where we compare the distance of each waypoint to all the other points, and discard all those that aren't within 30 to 80 Nmi, but this would take a while to run. The clever people who study graph theory tell us that, for a collection of n vertices, the maximum number of connection lines would be:

Visually, this relationship is plotted below, where the x-axis is the number of nodes, and the y-axis is the number of connections:

So for our 137 vertices, that would be 9,316 distances to check. But we know that since each sector is 90 Nmi long, vertices that are more than 2 sectors apart will never connect to each other. So to cut down on processing time, we should not bother with checking distance for waypoints more than 2 sectors apart. 

Graph Building Process

We write a process that builds the graph in stages, checking only the distances of vertices across adjacent sectors. That process will go something like this:

When run:

Remarks

• We used PyGeodesy to compute distances between waypoints

• We used a loop to compute distances. Loops can be slow. If we need more speed, we could try to upgrade our process to be array-based instead of using a loop. However, the total construction time for all the routes I've tested is usually about 2 or 3 seconds, which meets the speed requirements listed in section 1.1.

• There is some randomness in how our process works. If the waypoints table was sorted another way, for example, we would probably get a slightly different looking network. But this does not matter, because we are looking for a route, not the perfect route.

Visualization

We can modify the .kml exporter from earlier to draw the graph:

Here's the result: