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

JoeBe
  • 1,230
  • 1
  • 9
  • 20

3 Answers3

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

Vicky
  • 439
  • 2
  • 4
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.

Uffe Kousgaard
  • 2,543
  • 15
  • 24
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

dkastl
  • 4,786
  • 17
  • 21
  • 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: https://gitter.im/pgRouting/pgrouting – dkastl Nov 27 '20 at 00:11