1

For a project I am trying calculate the shortest path (marked by points, not lines) connecting a point of origin to a destination point (different feature layer) and automate this for several segments/paths.

The output should be the respective points as a new feature layer/shapefile and not lines, just the points with sequential number (from origin to destination).

I am familiar and have access to ArcGIS Pro/ArcMap, ArcPy or ModelBuilder/Geoprocessing tools.

Below I more detailed example:

enter image description here

I already considered using the near function from the ArcGIS geoprocessing options to calculate the distances between the Origin and closest points. However, simply following the closest distance of respective (blue) points, does not allow to construct the path that I marked in red. The yellow line is just for illustration, and should not have a function in the analysis

I would have to iterate/loop a near function for every consecutive blue point, while also simultaneously keep the angle (in line with the destination point) into account.

For example, if I would draw a line from nearest to consecutive nearest point, after the first blue point, the line would go down, instead of in line with the destination point. Which ultimately would be the shortest path.

6
  • 1
    You could try generate a Delaunay triangulation desktop.arcgis.com/en/arcmap/10.3/manage-data/tin/… and use methods in desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/… to solve for a path passing through all your points - if you have all the appropriate licenses.. Feb 22, 2021 at 1:55
  • 1
    This is called traveling sales person problem. Not that easy as you think
    – FelixIP
    Feb 22, 2021 at 2:48
  • If you want to ask a similar question about PotGIS and QGIS then please do that using separate questions.
    – PolyGeo
    Feb 22, 2021 at 2:49
  • 1
    This question needs some more explanation as to why you want to include some points along the way and not others. For example, why don't you want you line to jump straight from the origin to the second-last point along your sample line? That would be shorter, and more in-line with the direct line. You used just such an argument to avoid the point further down, but why not for the preceeding point? What are your criteria for deciding on which points can and cannot be included in a your line/route? Feb 22, 2021 at 3:10
  • @MichaelStimson Thanks for your answer that is a great suggestion and didn't consider that. After doing some initial tests, I think that an OD Matrix (connecting every point to every point in the entire Network dataset) would probably work even better to determine most effective route strategy.
    – PGerrits
    Feb 22, 2021 at 12:12

1 Answer 1

3

The correct way to perform shortest path is to use Travelling Salesman algorithm, ( as per FelixIP comment) - which has been implemented in ArcGIS in the Network Analyst extension.

https://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/algorithms-used-by-network-analyst.htm

You would need to create some network data first though, this could be achieved in various ways, Point-line geoprocessing tool as an example.

https://pro.arcgis.com/en/pro-app/latest/tool-reference/data-management/points-to-line.htm

So you would have lines from every point, joining to every other point - Michael Stimson's triangulation solution in the comments might be useful as part of the process.

The only issues with the above are your access to the ArcGIS Pro extensions in question.

2
  • Thank you very much for your answer. I agree I think that the traveler sales algorithm (TSP) in combination with traingulation solution from @Michael Stimson would be suitable for my task. However, I have one question regarding that. As far as I can tell, TSP takes into account all places and finds the optimal route among them, this isn't exactly what I had in mind. I would like to know if it is also possible to visit only the places that are on the shortest route from A to B (like shown on the image above.) Thank you again!
    – PGerrits
    Feb 22, 2021 at 9:21
  • 2
    yer thats ok, there are other tracing algorithms available in Network Analyst extension. if you don't have access to it, you can achieve it using open source solutions instead.
    – nr_aus
    Feb 23, 2021 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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