I have a road network where I have to cover every road for visual inspection. I need to design a route map for this task.
What tools are available to a QGIS user? How would you describe the workflow in this situation?
Answer
This is not a true answer, but a collection of information and observations from my attempts over the past few days to find one. I've worked mostly with ArcGIS's Network Analyst, so my approach was to try and solve the problem there and then translate that to QGIS. Since I didn't arrive at a full solution the below will stay in the ArcGIS mindset, but everything should have a comparable tool in QGIS - pgrouting and the v.net.salesman mentioned in the comments come to mind.
The problem you are trying to solve is actually the inverse of what most network analysis routing aims to do - minimize network edges traveled rather than maximize them. I'm not aware of a network analysis that works with lines as inputs (not talking about barriers or the network itself, but rather stops). They all use points to establish locations on the network and then solve for navigation between those points. In order to traverse an entire network, you have to create a series of stops that would force that occurrence.
The only quick way I could think to do that would be to create points at the midpoints of all network edges. Because my test network has some loops in it, the way I generated the points wound up with some not really in the middle (ie, a centroid forced to snap to a line may not actually be at the midpoint). The resulting route would then go out to the point but turn around and go back to the intersection because that was shorter than going all the way around. Similarly, with a dead end or dangle it would do the same - not go to an end. So I decided to add more points at the beginings/ends of edges and not just midpoints. That did improve the coverage result, but still had issues with 'centroid not the midpoint'. I also tried converting every vertex to a point, but because of my network (winding mountain roads) that created an exponential number of stops, which goes to the next issue.
The other big issue was processing time. Even with a very small network (edges < 500) you still end up with a tremendous number of stops. I'm sure it would have finished processing if I'd walked away for a while, but have no idea how long it would take. Around 400 stops took 5-10 minutes. 800 stops didn't finish in any time window I allowed; my 'every vertex' option generated 3500 stops (for 159 edges).
So to continue attacking this problem, the first thing I would do is create an abstracted/simplified version of the network. If you're breaking it into four sections, create four networks with just those section edges. Then use some generalization tools to further reduce/minimize the number of vertices edges have. This will have an impact on the length (and therefore distance impedence you use to optimally solve the route), but whatever balance you can make between data to process and accuracy is going to help here.
Once you've got the network as simplified as possible, create points out of either all vertices or just the ends and mids. You'll want to run some sort of duplication detection since one edge start is another's end, and you don't want two stops in the same place. When you have your reduced set of points, you can run a routing network analysis and then check the results. It may take a long while to process - hours, or overnight even. You may want to do some small test cases to get an idea of processing time and results before committing to the whole section.
If there are still a few segments that aren't covered (for instance a halfway out and back scenario as described above) you could manually fix them or just note to the navigating crew that they should always turn around only at an intersection (this will make sense if you see it).
No comments:
Post a Comment