My route plan seems to be complete, so why is the routing engine telling me my emergency vehicle will not be able to pass?
There is a road. A line has been drawn. In every view (zoom) that you would typically use to view the area, the junction appears to be perfect. However, a routing engine does not look at a map. It looks at a graph. Graphs only know if two lines are connected by having a common vertex.
We've written about a very nice, smooth-looking model of the ground which has no ditch. We also wrote about an extremely clear orthomosaic that does not show where the boundary is. This pattern continues to repeat itself with many data sets that are "correct" but are actually answering a completely different question than the one we wanted answered.
Why Visually Connected Roads May Be Disconnected in GIS
A map draws lines. A network is created with geometry that matches. Within Esri's network dataset, connectivity depends upon the endpoints and vertices being coincident and the connectivity policy you assign to every edge source: either End Point or Any Vertex. This same documentation states clearly the result: if crossing lines do not contain at least one coincident endpoint or vertex, no connectivity policy can produce a junction at their intersection.
In other words, the problem with this error is that it is very difficult to find. A 1 meter gap at a scale of 1:10,000 would be 0.1 millimeters in width. This means that if you were to draw a line on a piece of paper representing a road, the gap between the two line ends would be narrower than the line itself. If you looked at an open junction on your computer screen or in a printed map, you would think it was closed because of how narrow the gap would appear. However, to the routing engine, this junction would be a barrier.
Dangling Endpoints, Gaps, Overshoots and Undershoots
Most connectivity errors fall into a handful of patterns:
- Dangle (dangling endpoint): A line end that has no connection to another point. A "true" dead end or cul-de-sac is an acceptable dangle, and some state NG911 data-acceptance criteria (such as Kansas') will permit a dangle when a road actually ends.
- Gap or undershoot: a line stops short of the road it should join.
- Overshoot: a line crosses the road it should join and carries on past it.
- A bridge crosses over another road (or train track), and there are no vertices in common. A regular intersection of roads also crosses without a common vertex, but it is considered a fault.
- Duplicates/overlaps: Two segments have been created along a single road. The Oklahoma NG911 guidelines for road centerlines state that there should be no gaps, overlaps, or duplicate lines, and that segments must connect node to node.
These patterns are exactly what is checked by the standard topology checking tools. The old function in pgRouting (which is now deprecated in newer releases) that was used to analyze graphs would identify isolated segments, dead ends, possible gaps around dead ends, ring geometries, and intersections. Regardless of which tool you choose to use, this is a good checklist to refer to.
Bridges, Underpasses and Grade-Separated Intersections Require Special Attention
At this point, the rule is reversed. An intersection can only occur at-grade. A road passing over another may not intersect with the lower road, unless the two are connected by a ramp. As stated in Esri documentation, a road going underneath a bridge will only be connected to the bridge if the two are given a common junction by the geometry, which is exactly how you would like to have it work. The NENA centerline standard summarizes the rule in both ways: at every at-grade intersection there should be node-to-node segmentation, and grade separations should remain without junction nodes.
Two failure modes follow:
- A false connection. A false connection exists when a network allows a vehicle to make a left-hand turn from a bridge to the street below, when such a turn does not actually exist. Although the route appears correct, it is impossible for a person to drive on this route.
- A missing link. A ramp does not connect with a road on each side. The computer system sees the bridge and the road as separate, so the path will take a different direction or be unresolvable.
To address this, there are elevation fields; however, there are also problems associated with them. Esri's Support Team states that Any Vertex connectivity combined with field-based elevation may lead to unwanted connectivity, as only edge endpoints contain elevation values and all other vertices within the edge do not. To correct this problem, Esri suggests splitting edges at each point where they cross each other and then using End Point connectivity. In addition, if you do not have elevation fields in your dataset, an Esri Community Answer suggests verifying that overpasses do not share a common endpoint or vertex with the road beneath them so that you will not accidentally create a connection between the two features.
This becomes particularly important in areas where roads, rivers, and steep slopes are closely spaced together, such as the mountainous road corridors that were discussed previously, where there are many bridges, river crossings, and switchbacks within just a few hundred yards of each other.
How Snapping Tolerances Can Fix Some Errors While Creating Others
The most effective solution for closing the gaps in your drawing appears to be "snapping." With snapping, you define a tolerance limit. If any of the endpoints fall below this limit, they will be drawn toward their nearest neighbor. This closes the gap; however, it can also cause unintended movement of other elements in your drawing.
Esri has been careful with their documentation regarding their Integrate tool. The Integrate tool will modify the input data, cluster vertices that are located within the tolerance, and provide a warning that setting the tolerance to a value other than the default could cause features to either shift too far or not enough. Esri suggests allowing the XY tolerance to remain at the default, using a smaller tolerance if necessary, and running the tool during an editing session in order to allow the user to undo any modifications.
It's simple to imagine what happens when there is an error in the system. If you've got a 10-meter tolerance on a service road that runs parallel to the highway 6 meters away, then you could pull that service road over the highway and create a nonexistent intersection. You may combine two ramps close to each other. You may lose a small part of a valid road segment. You may also connect a true dead end to the road directly behind it. Every time you correct an issue with the system, you're introducing another issue with the system, and those new issues are more difficult to find since the system appears to look "cleaner."
As an alternative, a more conservative strategy is to utilize tolerance to identify issues rather than to resolve them. For instance, the pgRouting analysis uses a tolerance specifically to indicate possible gaps in close proximity to dead ends, allowing you to decide how to proceed. It can be set based on the level of precision of the input data, a subject that was addressed in our earlier post regarding the distinction between resolution and accuracy. Centimeter-level drone-generated centerlines require vastly different tolerances than thirty-year-old digitized street segments.
Building and Validating a Routable Road Network
- Define the goal of the dataset. Emergency dispatch, delivery routing, and planning analysis require different data attributes, different levels of accuracy, and different frequencies of updates. This is the exact same "fit-for-purpose" issue that was addressed previously when considering the use of engineering datasets.
- First, clean your source geometry. Delete all duplicate or overlapping elements. Then divide each line segment by splitting them at each at-grade intersection. Your final result should be that every segment extends from one node to another.
- Explicitly mark grade separation. Bridges, tunnels, and underpasses should have an explicit height/elevation attribute or have their geometry explicitly designed so they do not connect to other features, but rather have ramps connect to them at each end.
- Perform checks on topology. Check for dangles, gaps that occur near the end of a line, overshoots, crossings that do not contain a node, isolated segments, and duplicate items. Rather than automatically correcting each of these issues, review them individually.
- The rules a router needs. Travel direction of one-way roads, turn restrictions, road classes, speed limits, and access. A fully interconnected network with incorrect one-ways will result in sending ambulances down the wrong road.
- After you create the network using a specific connectivity policy, make sure to rebuild the network each time you modify it. According to Esri, when you change a connectivity policy, you must rebuild the network dataset so that the new connectivity is established.
- I would recommend testing your connectivity in general. Then identify which parts of your network are disconnected, and go through each of those parts (excluding the primary part of your network) to see why they are disconnected.
- Run a predetermined list of starting locations and ending locations to see how well they match up against routes you have previously verified as being accurate.
Practical QA Checks Before Using the Network for Emergency Response or Logistics
- Count the islands. A road network must contain exactly one dominant connected component. List all of the smaller components, then determine which ones are actual islands, which ones are private roads, and which ones are errors. Routing engines deal with this issue on a regular basis. According to GraphHopper's forums, OSM-based networks contain "islands" that cannot be accessed from any other part of the network; therefore, GraphHopper provides options to filter out islands that are smaller than a certain threshold.
- Watch for silent failures. When we remove islands, a start point that was in an island will now connect to another properly connected road. The route can be successfully completed; however, it will begin on the wrong road. Just because a route can return doesn't mean your network is correct.
- Test one-way islands. Many roads can only be reached in one direction. A relevant thread in GraphHopper discusses the difference between clearly defined islands and those which are reached via a single-direction path. Verify that each of the critical paths has been tested in both directions.
- I want you to look at every dangle and classify each one as either a true dead end, a gap, or an overshoot. Only the first type of dangle will be accepted.
- Check every crossing that does not have a node. Every crossing will need to be verified as being either a bridge, tunnel or underpass.
- Route a vehicle under a bridge and verify that the vehicle will not be able to turn onto the bridge. Route a vehicle over a bridge and verify that the vehicle will not be able to turn onto the road below the bridge unless there is a ramp.
- The destination is also checked along with the route. All address locations and facility types must align with the accurate road section and the correct component. States such as Utah have established NG911 programs that require consistency between address point locations and road centerline positions, as well as periodic Quality Assurance/Quality Control (QA/QC) of the data.
- Field/imagery check. A quick method for confirming that roads, closures, and bridges have been built in reality is with an up-to-date drone orthomosaic. This will tell you if those items are actually located in the physical world, but it will not indicate whether your network model represents the relationship between them, which is the same as the distinction we made with our boundary posts.
- Keep a regression test set. Run those same critical paths each time you update your data. The National 911 Program warns that using poor quality GIS data will create undocumented errors, therefore, it is important to use the same tests as before.
The Actual Takeaway
Road maps that appear to be connected are simply those which have successfully met the criteria established by the human eye. Routing engines require a more stringent set of criteria for connection, including but not limited to, common node identification; proper grade separation; correct directionality; and the establishment of a "main" network that includes all relevant features. Snapping may correct one disconnection, but simultaneously create another error; therefore, correcting the error is an iterative process of identifying, evaluating, and validating the error correction, rather than a single adjustment of tolerances.
Our team of GIS and drone imaging and processing professionals can validate your road network (whether you're building one or evaluating an existing one) for use in applications such as routing, emergency response and/or logistics by comparing it to actual routes that have been taken by vehicles. Our team will also update your road network using up-to-date drone imagery.