4

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?

  • 1
    I haven't used GRASS often but I have used the v.clean function to fix certain errors in a couple of my vector maps. Or have you already tried this? – Joseph Oct 2 '14 at 9:44
  • I think the clean process happens already when you use v.in or v.net. At any rate I have tried separate v.clean processes to no effect. – Jim Oct 2 '14 at 14:39
  • Is there any kind of one-way or no U-turn restriction in the attributes of the network or analysis settings that might be causing the path failure? – Chris W Oct 2 '14 at 19:06
4

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. unbroken line.

And here, the broken line. broken line

Finally, the traveling salesman line!

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?

  • In a network when two lines cross that doesn't mean there is actually an intersection or junction. A turn (or transfer in multi-modal networks) can only be made at a junction. In order for a junction to occur both lines must have a vertex at a common point. Even if one line has a vertex snapped to the other edge, it won't work - they both have to have one. Furthermore, the network implementation can say that junctions can only occur at nodes (endpoints) and not intermediate vertices. Unreachable means just that - there is no network path, shortest or otherwise, that can reach the point. – Chris W Oct 3 '14 at 21:23
  • In GRASS 7.2.1 the [v.clean] can be found under Vector -> Topology maintenance -> Clean vector map – knutella Feb 3 '18 at 22:42
1

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:

enter image description here

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.

  • When you create the network, GRASS also creates a point, line, and node layer. However, it does not show "component". I am able to isolate the points that are unreachable, but to my eyes there are lots of lines to connect them. When I use v.net.path to create the shortest path, there is no output. At any rate, shouldn't the topology clean process happen when you use v.net? – Jim Oct 2 '14 at 14:42
  • Thanks for sharing the ArcGIS tool. My concern is for QGIS. If there is not a way to solve this situation with Open Source, there is a problem with using Open Source. However, the solution that I detailed above, using v.clean.break works, at least this time. – Jim Oct 4 '14 at 3:29
  • Sure. Open Source GIS shouldn't have any problem calculating shortest path. The principle is the same. You can identify the problem by checking connectivity. – tinlyx Oct 4 '14 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.