Find the shortest path

Question

I have the exact same problem as explain in this post. I'm trying to find the shortest path between each building on a map (shp multipolygon) to any transformation plant (shp multipoints) by following a network (shp multipolyline).

As suggested in the answer given to the OP, I was thinking of using pgr_dijkstra() but I think it won't work. The thing is, if I'm not mistaken, pgr_dijkstra() return the shortest path between 2 points. In this case, we do not know which electric transformation plan we're looking to reach, the goal is to find the shortest path to any transformation plant on the network.

In order to use pgr_dijkstra(), we would have to first assign an electric transformation plant to each building (minimum radial distance around it for example) but there could be situations in which the closest transformation plant in radial distance is not at all the closest by the network.

Does anyone knows if there is a way, with pgRouting or something else, to find the shortest path to any of the electrical transformation plant on the network (I've already managed to connect each building to the closest line on the network in order to be able to look for the shortest path between points which already are on the network, cf. this post).

Answer 1

I actually found a way of doing it.

I used pgr_dijkstraCost() which now has a Many-to-Many implementation and exactly does what I want.

My query is :

SELECT start_vid as building, end_vid as plant, agg_cost as junction_length from pgr_dijkstraCost
(
'SELECT gid as id, i as source , j as target , length as cost from   network_edges'
, array(SELECT id from "network_nodes" where buildingID IS NOT NULL)
, array(SELECT id from "network_nodes" where plant_name IS NOT NULL)
, false
)

Where network_nodes comes from a SHP MultiPoints file with every points of the network. It has attributes such as id, buildingID, plant name. Some points, which represent buildings have not NULL buildingID, some others, the plants have not NULL plant_name. Finally, some points does not have anything else than an ID and they represent vertices of the network.

The network_edges comes SHP PolyLine file and represent the network itself. It has i, j and length attributes. i and j represent, respectively, source and targed vertices of the edge and length is obviously the length of it.

I used the Networks plugin to create my graph (nodes and edges) and shp2pgsql to import it in my database.

Answer 2

My first thought is that you should calculate the network distance for any (or at least the 5 closest) points to the houses, because you can only know which one is shortest after calculating the distance.

Another approach could be to calculate service areas for each of the transformation plants based on the network. Than you know which house should be assigned to which transformator. After that you can calculate the shortest distance.

How to calculate Network Service Areas in QGIS?

I hope this helps.