Shortest path (Network Analysis)

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Shortest path (Network Analysis)

Tsering W. Shawa
I am trying to find a tool in QGIS that will allow me to calculate shortest path between two layers (number of hospitals to number of addresses) using road network data. There are two plugins (Networks and QNEAT3) and Network analysis tools in Processing Toolbox but none of them allow me to calculate shortest path between two layers. Either the tools will allow me to find the shortest route between a layer (multiple locations) to a single location by picking interactively an origin or a destination location or interactively picking one an origin and a destination location. However, none of the tools will allow a person to upload or select two layers that has multiple point locations to calculate the shortest path.

Any recommendation for tools to solve my problem?

Thanks,
-Wangyal



_______________________________________________
Qgis-user mailing list
[hidden email]
List info: https://lists.osgeo.org/mailman/listinfo/qgis-user
Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-user
Reply | Threaded
Open this post in threaded view
|

Re: Shortest path (Network Analysis)

Nicolas Cadieux
Hi,

Is there an all-paires options?  If so, you can put the source and destination in the same file and all possible source and destinations will be done.  You will then need to filter of what you don’t need.  How many routes are you dealing with?

I may have something for you but it’s not published OpenSource yet.  Could be useful if you have millions of routes to calculate.

Nicolas

Le 4 oct. 2019 à 09:59, Tsering W. Shawa <[hidden email]> a écrit :

I am trying to find a tool in QGIS that will allow me to calculate shortest path between two layers (number of hospitals to number of addresses) using road network data. There are two plugins (Networks and QNEAT3) and Network analysis tools in Processing Toolbox but none of them allow me to calculate shortest path between two layers. Either the tools will allow me to find the shortest route between a layer (multiple locations) to a single location by picking interactively an origin or a destination location or interactively picking one an origin and a destination location. However, none of the tools will allow a person to upload or select two layers that has multiple point locations to calculate the shortest path.

Any recommendation for tools to solve my problem?

Thanks,
-Wangyal


_______________________________________________
Qgis-user mailing list
[hidden email]
List info: https://lists.osgeo.org/mailman/listinfo/qgis-user
Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-user

_______________________________________________
Qgis-user mailing list
[hidden email]
List info: https://lists.osgeo.org/mailman/listinfo/qgis-user
Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-user
Reply | Threaded
Open this post in threaded view
|

Re: Shortest path (Network Analysis)

Paul Wittle-3
In reply to this post by Tsering W. Shawa
Hi,

I've also been investigating this sort of work over the last two weeks and have largely come to the same conclusion. I don't think there is a way to do it directly at present without a chargeable plugin but I can't help but feel that it might be possible to create a processing toolbox script which achieves traveling sales using the tools available. QNEAT3 allows you to create a distance matrix and it is not difficult to merge two point layers to get a matrix with the required information. Once you have a distance matrix then in theory there should be algorithms / documented methods somewhere by which we can extract an optimal route order from the results.

That said, I've not had the time to look at this myself and of bigger concern is the lack of support for turn restrictions in the default routing tools. This means that the standard QGIS tools (and I assume QNEAT3 although I've not really looked at Networks) will be jumping off bridges and recommending banned turns.

It would be interesting to know if any of the stuff I've mentioned above is being looked at as I might be interested in working with others to develop some improvements at some point; subject to finding time and employer approval.

Sorry I can't be more helpful but perhaps it will give you a manual method in the short term,
Paul

https://www.jstor.org/stable/167205?seq=1#page_scan_tab_contents (example academic paper)

Message: 2
Date: Fri, 4 Oct 2019 13:59:36 +0000
From: "Tsering W. Shawa" <[hidden email]>
To: "[hidden email]" <[hidden email]>
Subject: [Qgis-user] Shortest path (Network Analysis)
Message-ID:
        <[hidden email]>

Content-Type: text/plain; charset="iso-8859-1"

I am trying to find a tool in QGIS that will allow me to calculate shortest path between two layers (number of hospitals to number of addresses) using road network data. There are two plugins (Networks and QNEAT3) and Network analysis tools in Processing Toolbox but none of them allow me to calculate shortest path between two layers. Either the tools will allow me to find the shortest route between a layer (multiple locations) to a single location by picking interactively an origin or a destination location or interactively picking one an origin and a destination location. However, none of the tools will allow a person to upload or select two layers that has multiple point locations to calculate the shortest path.

Any recommendation for tools to solve my problem?

Thanks,
-Wangyal


This e-mail and any files transmitted with it are intended solely for the use of the individual or entity to whom they are addressed. It may contain unclassified but sensitive or protectively marked material and should be handled accordingly. Unless you are the named addressee (or authorised to receive it for the addressee) you may not copy or use it, or disclose it to anyone else. If you have received this transmission in error please notify the sender immediately. All traffic may be subject to recording and/or monitoring in accordance with relevant legislation. Any views expressed in this message are those of the individual sender, except where the sender specifies and with authority, states them to be the views of Dorset Council. Dorset Council does not accept service of documents by fax or other electronic means. Virus checking: Whilst all reasonable steps have been taken to ensure that this electronic communication and its attachments whether encoded, encrypted or otherwise supplied are free from computer viruses, Dorset Council accepts no liability in respect of any loss, cost, damage or expense suffered as a result of accessing this message or any of its attachments. For information on how Dorset Council processes your information, please see www.dorsetcouncil.gov.uk/416433
_______________________________________________
Qgis-user mailing list
[hidden email]
List info: https://lists.osgeo.org/mailman/listinfo/qgis-user
Unsubscribe: https://lists.osgeo.org/mailman/listinfo/qgis-user