How to fix unreachable nodes in QGIS GRASS network?

Question

I have created a network with the GRASS module v.net. But when I try to create the travelling salesman path with v.net.salesman, I get:

Destination node 9383 is unreachable from node 9398

If I put the topo lines or points from the network into QGIS I can find the two nodes, but I can't manually figure out why one is unreachable from the other. The Topology Checker shows no errors. I know that the v.net.salesman works because I was able to create the path with another dataset. This dataset is faulty, even though v.net created a network. Is there a tool either in GRASS or QGIS that I can use to fix this problem?

Answer 1

I finally got the traveling salesman tool to work by using the v.clean.break tool, which in the QGIS GRASS dialog is under Vector->Develop Map-Toolset for cleaning topology of vector map. In QGIS there are no options for tolerance, you just enter the street vector layer.

The v.clean.break tool breaks the lines at intersections, as shown. First, the unbroken line. .

And here, the broken line.

Finally, the traveling salesman line!

I am just guessing as to why this works; perhaps when it says the node is "unreachable" it means unreachable by the shortest path? The shortest path might be the one that is not accessible because one line does not break at the line that would provide the shortest path?

Answer 2

In general, I think this is a topology problem. The destination node cannot be reached from the source node. According to its documentation, v.net.salesman

calculates the optimal route to visit nodes on a vector network

By definition of the traveling salesman problem, this route is a tour that must be connected. So, as the message suggests, if one of the nodes is unreachable from another, i.e. if two nodes are on two components of the graph, no tour can be constructed.

The fact that v.net.salesman worked on another set of nodes means that those nodes are in one component of the graph. It doesn't guarantee that the current set of nodes are in the same component.

You probably know the cause already. I can't speak for QGIS/GRASS. But at least I know you can use ArcGIS to identify the problem (I guess there should be a similar solution in QGIS/GRASS):

You can compute single source shortest path from each of the two nodes, respectively, by constructing a (Geomertic) network. Then looking at the distance label for network nodes, you can see the components that these two nodes resides in respectively. From there, maybe you can figure out the spot at which the network is disconnected, and move and snap features to connect the two components (if it's a data quality issue). Or if one of the nodes is just not snapped to the network, you can snap it to the network.

-- EDIT --

To clarify, you can e.g. compute network accessibility from each of the two nodes and generate buffers like this in the ESRI website:

Then by observing the shape of the buffer of a large distance, you will be able to see if one of the nodes in question is isolated from the rest of the network or identify the problem site on the graph. While I am not familiar with QGIS/GRASS, I don't believe Open Source GIS should have a problem computing shortest paths. The principle is the same. That is, in essence, you can diagnose the topological problem by checking connectivity between the problem nodes.

While tools like v.clean can sometimes fix the problem automatically, e.g. by breaking lines at each intersection, they might occasionally be topologically incorrect e.g. by confusing an overpass with an at-grade intersection or by snapping features incorrectly, giving you infeasible routes. But I guess one can always visually investigate the changes made by an automatic cleaning and determine if they are appropriate.