Steiner tree problem: Optimal routes for Fibre planning on road network

Question

I am trying to solve a large optimization problem where I have a set of nodes on a road network that need to be connected using fibre using the shortest possible amount of fibre.

The problem is a classical Steiner tree problem. Grass has a function called v.net.steiner but my road network consists of 20,000 edges connecting intersections and the number of Steiner nodes (points to be connected by fibre) is about 1500. I tried this on a 32-bit Linux OS with 4 GB of memory and I got an out of memory error.

Any suggestions on how to solve this with a desktop PC - or do I need to send the problem to a super-computer

I've attached an image of the problem - don't worry I will trim the dangle-roads but that only shaves off about 1000 road segments

Answer 1

Here I made an R package that could handle this problem. This tool uses that v.net.steiner algorithm, but uses it iteratively in order to get just the lines of the network that are relevant. Alfter iterate over n samples of your terminals, it calculates a new optimal Steiner Tree for the whole network.

So in resume, you will save ram because: - You don't need to open the whole QGIS interface. - Iterations of Steiner Tree are saved in the HDD (in a working grassdata folder). - The global Steiner Tree is calculated just with useful lines of the network.

Here is the R package: https://github.com/cesarkero/IterativeSteinerTree

Here is a simple code to use it (just change l and p for your lines and points layer):

Here you have an example of how to use it.

update.packages()
library(devtools)
install_github("cesarkero/IterativeSteinerTree")

library(IterativeSteinerTree)

# basic setGRASS (based on iniGRASS params but simplified)
setGRASS(gisBase = "/usr/lib/grass78", epsg= 25829)

# load sldf (l) and spdf (p)
data("l"); data("p")

# calculate Steiner Tree
IST <- IterativeSteinerTree(l, p[1:100,], th=1000, iterations = 25,
                            samples = 10, clean = TRUE, rpushbullet=FALSE)

The only problem is that this package just work in linux.

Answer 2

You can get an optimal solution to this problem by using the Steiner tree solver SCIP-Jack, see https://www.scipopt.org/doc/html/STP_MAIN.php, which is part of the SCIP Optimization Suite, see https://www.scipopt.org/.

You just need to write the problem in the .gr format (see https://pacechallenge.org/2018/steiner-tree/ Appendix A), to be able to solve it with SCIP-Jack.