1

My topic is to minimize the cost of construction line digging. Starting from a source point I have several households that need to be connected to the that line. My plan was to calculate the shortest path for each source -> house and then cutout the overlapping lines.

In the example below I would then have a route on the Eastern street that goes from house 1-4, where the line for house 4, for instance, only reaches to house 3 and not the whole way to the source point (red) as I cutout its shortest path with the shortest pathes from houses 1 to 3. However, for house 5 the shortest path would have been the Western road, which is why it doesn't intersect with any other shortest path. But practically a connection from house 4 would have been more cost efficient. How can I include this consideration into my algorithm using PostGIS and pgrouting?

enter image description here

1

City network

Lets make an approximation of the steiner-tree: Suppose that

  • the sources are 1 & 10 the edges
  • the houses are 2,3,4,5,6,7,8,9,11,12,13 (from the information of the sample data 14, 15, 16, & 17 are disconnected from the rest of the graph, those nodes need to be connected before considering them)
  • Because visually all lengths look the same, let the edges weights the id number of the edge

Steps:

  • The nearest house(2,3,4,5,6,7,8,9,11,12,13) to the sources(1,10) is 2 (using edge 1)
  • The nearest house(3,4,5,6,7,8,9,11,12,13) to the sources(1,10,2) is 3 (using edge 2)
  • The nearest house(4,5,6,7,8,9,11,12,13) to the sources(1,10,2,3) is 4 (using edge 3)
  • The nearest house(5,6,7,8,9,11,12,13) to the sources(1,10,2,3,4) is 5 (using edge 4)
  • The nearest house(6,7,8,9,11,12,13) to the sources(1,10,2,3,4,5) is 6 (using edge 5)
  • The nearest house(7,8,9,11,12,13) to the sources(1,10,2,3,4,5,6) is 8 (using edge 7)
  • The nearest house(7,9,11,12,13) to the sources(1,10,2,3,4,5,6,8) is 7 (using edge 6)
  • The nearest house(9,11,12,13) to the sources(1,10,2,3,4,5,6,8,7) is 9 (using edge 9)
  • The nearest house(11,12,13) to the sources(1,10,2,3,4,5,6,8,7,9) is 11 (using edge 11) So the resulting graph up to this point is edges(2,3,4,5,6,7,8,9,11)
  • etc

The function pgr_dijkstraNear is on the develop version (3.2.0-dev) of pgRouting. To use it you would need to compile and build the branch develop of the repository.

Documentation: Have not got time to publish latest documentation of that develop branch, as soon as its available I will post it here in another comment

On the meantime you can read the non processed documentation file here: https://github.com/pgRouting/pgrouting/blob/develop/doc/dijkstra/pgr_dijkstraNear.rst

The examples mentioned in that file are here: https://github.com/pgRouting/pgrouting/blob/develop/docqueries/dijkstra/doc-pgr_dijkstraNear.result

0

It is a steiner tree you are looking for, explained here: https://blog.routeware.dk/2018/05/29/steiner-tree/ I don't think it is part of pgrouting.

0

If you're looking for an Open Source solution maybe you can make use of the "Minimum Spanning Tree" function(s) of pgRouting. There are a few options: https://docs.pgrouting.org/dev/en/spanningTree-family.html

2
  • thanks. It is close to what I want. However, for me I also need to include source and targets. The tree should be then applied among the targets with the closest connection to any of the sources. Something like a forest instead of a single tree – JoeBe Nov 26 '20 at 23:24
  • I'm not sure I understand exactly the use case, but feel free to also share it on our pgRouting chat channel, because most developers are active there and maybe someone can help: gitter.im/pgRouting/pgrouting – dkastl Nov 27 '20 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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