3

Is there an established method for running multiple shortest path analysis based on multiple start and end points?

I have a model outputting coordinate data and a road network with varying road types. I need to be able to run multiple shortest path calcs and have those routes plotted.

I am fairly new to qgis and python.

Improve this question

2 Answers 2

Reset to default
1

You may try to use GDAL GNM functionality (see. http://gdal.org/gnm_tut.html and http://gdal.org/gnm_arch.html).

But you need GDAL build with GNM support (by now it disabled by default). You can grab GDAL with GNM here: http://nextgis.com/borsch/

If you prefer GUI utility, there is a plugin for QGIS - QNetwork (https://plugins.qgis.org/plugins/qnetwork/) which utilize GDAL GNM. But there are some limits in plugin now (you need at least to layers - lines connected points). Also you need QGIS build with GDAL GNM - get it here: http://nextgis.com/nextgis-qgis/

Improve this answer
2
  • Hi, Thanks for the input. I am trying to use the QNetwork plugin. However i am unable to create or load a network and the Options in this plugin window remains grey'd out. Is this due to a lack of supported layers that may be required?
    – Thomas
    Commented Sep 1, 2016 at 10:31
  • This is because your QGIS based on GDAL without GNM. Plugin check if GNM is available and if no GNM, all buttons and menus marked disabled.
    – Dmitry Baryshnikov
    Commented Sep 1, 2016 at 11:12
1

I've done this by batch use of Processing> NetworkAnalysis> ShortestPath(PointToLayer). This can be run in batch. I found the easiest way is to prepare the batch was to use a JSON file. The core of JSON can be prepared using a spreadsheet. Then concatenate the requires fields, copy & dump into a JSON editor to tweek the top and tail into the correct format. What is key to this is organising, preparing the data and the use of directories or folders. It considerable reducing calculation time if you constrain the network and potential start and/or end points to reasonable possibilities. I sieved out the road network and end points to within a 20km circumference. I finished up process about 15,000 start/end combinations in under one second per pair. So just over 4 hrs processing (best done overnight).

Improve this answer
1
  • I'm doing this, and this solves. but it is not as efficient as expected because each shortest path process must create a graph first. if it's the same graph, then you're making the same graph over and over again which is quite unnecessary.
    – sutan
    Commented Mar 16, 2022 at 13:29

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.