Shortest path finder returning different routes for same from-to locations

The only real way is to add more repetitions/iterations, or more verifications.

The thing is, the algorithm starts randomly each time. So it picks a random route and spends a bunch of iterations trying to better that route. It's tweaking that route, like, will it be shorter if I move that turn point north by a block?

Then for each verification it will start with a different random route and iterate through as before. The idea is that we hope it validates the original route as being the best, while acknowledging a different starting position might produce a better result.

In short, if it validates the original route, then all is good. If it finds something shorter, then we start validating that route instead. This continues until we have x verifications (where the user sets x).

The reason for all this is that it's an incredibly difficult problem to solve for large amounts of data, and so it makes sense to seed each process with a different route.

So what I think is happening is that it picks a route for you, but there aren't enough iterations to reduce it to the best route. Or, it validates the route with another that is exactly the same length, so it doesn't matter which is chosen. I suspect the first of those is true.

So try and change the number of iterations or verifications if you can.

To be honest, I'm not altogether sure why the iterations parameter isn't available unless you choose to reorder the line. But if you have only a start and end point - and nothing in between - then I don't think it should matter if you do choose to reorder, and it gives access to those parameters. So it can't hurt to give it a try.

The one thing to be aware of is... I'm working from memory here, but don't have very few iterations and then include multiple validations. Because if you do, it will be really, really difficult to validate the route (there aren't enough iterations to recreate it) and the process will take ages. Stick to a high number of iterations, because it runs faster than you'd expect, and a small number of verficiations (one or even zero).

I hope this helps.

@afod As @ebygomm and @mark2atsafe point out, the distance around the blocks / grids is the same so either can be used. ShortestPathFinder doesn't track which network segments have been already been used and each path is independent of the previous paths. Unless...

In some cases it's important to re-use network segments. For example, if you're laying cable and dig a trench, it's cheaper to re-use that trench for the next cable rather than dig a second trench (as we would in your example). I've been experimenting with this type of 'poor mans' optimization. If you can alter your network to lower the 'cost' of the networks segments for the current path, then subsequent paths will use those segments in preference to new ones. It looks something like this:

• split your workspace into two parts (parent and child)
• Parent workspace will read the vectors and sort them by length - process the shortest from-to vectors first. Add a WorkspaceRunner to call the child workspace, one from-to vector at a time.
• Child workspace has your ShortestPathFinder logic. Add some additional logic to alter the 'cost' and update the network records with the revised (lowered) cost values.

Obviously, this will be somewhat slower since the child workspace will reload the network for each from-to vector, but for some shortest path problems you may get a better result.

I'll upload an example if you share a small sample dataset.

@jgamm15​ I've attached the example workspaces and some example data, curtesy of City of Vancouver Open Data Portal. In the zip file:

• CreateData.fmw will re-build the roads and from-to tables in a geopackage form the CoV source data (included)
• ShortestPathFinder_Start.fmw - run this workspace to trigger the shortest path optimizer
• ShortestPathOptimizer.fmw - creates the shortest path for one from-to vector at a time (so it's a little slow). For each shortest path created, the optimizer updates the source public-street table, reducing the cost attribute (length) and also adding a 'count' for how many times this segment has been used.
• CoVStreets.gpkg - this contains the results with the shortest paths (CreateData.fmw will overwrite this GeoPackag)

Why do this? For example, if you need to trench a cable conduit, then you want to give preference to a segment that has already been trenched, rather than digging a new trench on a parallel street. So the 'cost' of each street segment is reduced each time you reuse that segment