Hey there,
Can someone give me some guidance. I'm looking for the right algorithm to use when solving this problem. I want to find the distance and shortest path to 11 schools for about 15,000 students. Does the many to many flavor of dijkstra scale up to these numbers? Is there a better way to solve this?
Thanks,
Brian
--
Brian DeRocher
http://brian.derocher.org
http://mappingdc.org
On 11/14/2016 2:12 AM, Brian DeRocher wrote:
Hey there,
Can someone give me some guidance. I'm looking for the right
algorithm to use when solving this problem. I want to find the
distance and shortest path to 11 schools for about 15,000 students.
Does the many to many flavor of dijkstra scale up to these numbers?
Is there a better way to solve this?
Hi Brian,
Checkout
http://docs.pgrouting.org/2.2/en/src/dijkstra/doc/pgr_dijkstraCost.html
It has a many to one function.
Regarding performance, that depends on a lot of issues but I would think if your limiting your edge table to the roads in the school district that you should get reason able performance.
You might want to try running it with 10, 100, 1,000, 15,000 so you have some idea of the performance at various numbers of nodes.
you will need to map the locations to the node ids in the network, then pass the node ids to the function.
Ask if you need more explicit help.
-Steve W
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Hi Brian,
I would use the pgr_drivingDistance function starting from your 11 schools (containing the area of your 15.000 students):
http://docs.pgrouting.org/latest/en/src/driving_distance/doc/pgr_drivingDistance.html#pgr-drivingdistance
Then you get the distance for each point in your network area to each school, and you jut need to select the school with the minimum distance.
Best regards,
Daniel
On Tue, Nov 15, 2016 at 7:08 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:
On 11/14/2016 2:12 AM, Brian DeRocher wrote:
Hey there,
Can someone give me some guidance. I’m looking for the right
algorithm to use when solving this problem. I want to find the
distance and shortest path to 11 schools for about 15,000 students.
Does the many to many flavor of dijkstra scale up to these numbers?
Is there a better way to solve this?Hi Brian,
Checkout
http://docs.pgrouting.org/2.2/en/src/dijkstra/doc/pgr_dijkstraCost.html
It has a many to one function.
Regarding performance, that depends on a lot of issues but I would think if your limiting your edge table to the roads in the school district that you should get reason able performance.
You might want to try running it with 10, 100, 1,000, 15,000 so you have some idea of the performance at various numbers of nodes.
you will need to map the locations to the node ids in the network, then pass the node ids to the function.
Ask if you need more explicit help.
-Steve W
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: https://georepublic.info
Hello,
Does the many to many flavor of dijkstra scale up to these numbers?
as long as you dont go like trying to load a big graph, I think you are ok.
Is there a better way to solve this?
If your data (students location & school location) is not a vertex in the routing graph, you can use these:
http://docs.pgrouting.org/latest/en/src/withPoints/doc/pgr_withPoints.html#pgr-withpoints
http://docs.pgrouting.org/latest/en/src/withPoints/doc/pgr_withPointsDD.html#pgr-withpointsdd
You would need to calculate the nearest edge and the fraction that corresponds to it.
There is this function, not part of the release, bacuse it has some issues) but it gives reasonable results.
https://github.com/pgRouting/pgrouting/blob/master/src/common/sql/findClosestEdge.sql
sorry, no documentation on that one
I think its a many to many in the dijkstra/withPoints and a many start points on the driving distance.
regards
Vicky
On Mon, Nov 14, 2016 at 6:05 PM, Daniel Kastl <daniel@georepublic.de> wrote:
Hi Brian,
I would use the pgr_drivingDistance function starting from your 11 schools (containing the area of your 15.000 students):
http://docs.pgrouting.org/latest/en/src/driving_distance/doc/pgr_drivingDistance.html#pgr-drivingdistanceThen you get the distance for each point in your network area to each school, and you jut need to select the school with the minimum distance.
Best regards,
Daniel
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
–
On Tue, Nov 15, 2016 at 7:08 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:
On 11/14/2016 2:12 AM, Brian DeRocher wrote:
Hey there,
Can someone give me some guidance. I’m looking for the right
algorithm to use when solving this problem. I want to find the
distance and shortest path to 11 schools for about 15,000 students.
Does the many to many flavor of dijkstra scale up to these numbers?
Is there a better way to solve this?Hi Brian,
Checkout
http://docs.pgrouting.org/2.2/en/src/dijkstra/doc/pgr_dijkstraCost.html
It has a many to one function.
Regarding performance, that depends on a lot of issues but I would think if your limiting your edge table to the roads in the school district that you should get reason able performance.
You might want to try running it with 10, 100, 1,000, 15,000 so you have some idea of the performance at various numbers of nodes.
you will need to map the locations to the node ids in the network, then pass the node ids to the function.
Ask if you need more explicit help.
-Steve W
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: https://georepublic.info
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](https://georepublic.info)
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl