Question

Calculating the shortest route to travel ALL roads in a network

  • 5 August 2022
  • 8 replies
  • 26 views

Badge

Hey there,

 

Trying to figure out of this is possible with the current data I have. I have a road network that looks like this of which I generated points for the mid-points of the segments. The road network does have froms and tos.

Essentially we have a camera on a car that needs to traverse this network in the same direction every time to make comparisons going forward. So ideally im looking for the quickest way to travel this route hitting ALL of the roads and have something that can be repeated every month where the driver is going the same direction every time. Is there an article on this I can't find?

road network


8 replies

Userlevel 1
Badge +11

Hi @tslack​ You need the end-points as well as the mid-points. Use Snippers to get the end-points, then remove the duplicate points with a Matcher. Make the From-To line with a LineBuilder from the unique points. Then in the ShortestPathFinder reorder the From-To line (under Optimization).

Badge

Hey @DanAtSafe thanks for getting back to me. Im still struggling a bit as I looked into the data supplied and a lot of the froms and to's are missing/not complete. Does it make more sense to run my road network through TopologyBuilder? I notice this creates edges and nodes that are properly filled out.

I was hoping I could just plug the edges and nodes into ShortestPathFinder.

Most of the examples im seeing are for 5 or 6 specific stops when I want to cover every single road in the network, just in the most efficient way possible. This was my obviously failed attempt. I was hoping I could just treat every node as a stop? Any time I run any points through line builder its a disjointed mess because the nodes dont know the network structure (curves of the roads etc which leads me to believe I am misunderstanding a step)

image 

Thanks again

Badge +2

@tslack​ The From-To has to be a vector/line. You're just inputting points. You can use the LineBuilder to string all the nodes together into an un-ordered line. But you also have to add a start and end point for the car. I agree with @danatsafe​ , I think you'll get better results if you use mid-points. If you only use endpoints you might miss a segment.

In ShortestPathFinder, use the Reorder From-To Line (Intermediate Points ONly. For optimization, I just used After Single Round of Iterations.

I've attached a small example. (FME 2021.2) Hopefully this gives you some ideas.

Badge

@tslack​ The From-To has to be a vector/line. You're just inputting points. You can use the LineBuilder to string all the nodes together into an un-ordered line. But you also have to add a start and end point for the car. I agree with @danatsafe​ , I think you'll get better results if you use mid-points. If you only use endpoints you might miss a segment.

In ShortestPathFinder, use the Reorder From-To Line (Intermediate Points ONly. For optimization, I just used After Single Round of Iterations.

I've attached a small example. (FME 2021.2) Hopefully this gives you some ideas.

Hey thanks @Mark Stoakes​ this was really helpful in getting a better understanding of how this works.

 

Just a quick question, is there supposed to be that many results in the Unused table of ShortestPathFinder?

 

EDIT: never mind I think I get it. My brain was expecting turn by turn directions

Badge +2

@tslack​ I've done a little more investigation and I don't think the example I gave you will give you the results you want. Let us do a little more testing here and we'll see if ShortestPathFinder can give you what you need.

Badge

@tslack​ I've done a little more investigation and I don't think the example I gave you will give you the results you want. Let us do a little more testing here and we'll see if ShortestPathFinder can give you what you need.

Thanks @Mark Stoakes​ I'll continue to play around with it while waiting for your response.

Badge +2

@tslack​ I don't think it's possible with the current algorithms we're using in the ShortestPathFinder. At the moment you can't use both:

  • "Allow U-Turns" AND
  • Re-order From-To Line : Intermediate Points only

I've attached my revised workspace (FME 2022.1) that fixes some errors in the early version, but it doesn't return a path because it can't get to all the line mid-points without U-turns

You might find a solution in "R" using RCaller. I'd open a new community thread if you want to pursue that. Sorry about that.

 

Badge

Thanks @Mark Stoakes​ really appreciate the help here

Reply