Optimisation

[adivea]

Hi Mark, we discussed optimizing dodgr for cascading travel scenarios, such as during sheltering/evacuation, when people run form residences/workplaces to the nearby shelters. The optimisation should prevent people from queing up at shelters that are over-capacity.

[mpadge]

Thanks so much for the inspiring conversations @adivea. I'll start work on this asap, and let you know here when it's implemented and usable.

[mpadge]

@adivea It's all implemented in a new dodgr_flows_optalloc() function. Here is some code to simulate a result between random points. Note that the input data are in dodgr_streetnet_sc() format, which gives much more accurate routing that standard (sf-format) dodgr_streetnet()):

library (dodgr)
net <- readRDS ("Aarhus-sc.Rds") |>
    weight_streetnet (wt_profile = "foot")
net <- net [which (net$component == 1), ] # Largest connected component

set.seed (123L)
n_from <- 100L
n_to <- 50L
from <- sample (net$.vx0, size = n_from)
to <- sample (net$.vx1, size = n_to)
to <- to [!to %in% from]
source_densities <- runif (n_from)

Direct aggregation to nearest points

Without this new algorithm, flow aggregation can only be calculated to nearest target (to) points. This code finds the nearest to point for each from, and allocates full source_densities along lines connecting those - so everybody going to nearest point only, regardless of capacity:

dmat <- dodgr_dists (net, from = from, to = to)
nearest_i <- apply (dmat, 1, which.min)
fmat <- array (0, dim = c (n_from, n_to))
fmat [cbind (seq_len (n_from), nearest_i)] <- source_densities
net_aggr <- dodgr_flows_aggregate (net, from = from, to = to, flows = fmat)

net_aggr then has a flow column of aggregated flows from each from to the nearest to point.

Aggregation via optimal allocation

To use the new function, we need some target_capacities, plus a scaling line to make sure that the total target_capacities exceeds the total source_densities:

target_capacities <- runif (length (to))
target_capacities <- target_capacities *
    1.2 * sum (source_densities) / sum (target_capacities)

The function then works just like this:

net <- dodgr_flows_optalloc (
    net,
    from = from,
    to = to,
    source_densities = source_densities,
    target_capacities = target_capacities
)

And the flow column of that now describes the flows under optimal allocation. The directly aggregated flows to nearest target locations can also be added:

net$flow_aggr <- net_aggr$flow

The relationship between the flows can then be visualised:

library (ggplot2)
pt_col <- "#ff44dd55"
ggplot (net, aes (x = flow_aggr, y = flow)) +
    geom_point (col = pt_col) +
    geom_smooth (
        method = "lm",
        formula = "y ~ x",
        se = FALSE,
        lwd = 1.5,
        col = "skyblue") +
    geom_abline (
        intercept = 0,
        slope = 1,
        col = "skyblue",
        lty = 2,
        lwd = 1) +
    theme (theme_minimal ())

And you can see that most of the directly aggregated flows are zero, while network edges that do have non-zero flows have values far larger than the optimal flows. Conversely, the flows under optimal allocation are generally about an order or magnitude less than under direct aggregation to nearest target points. In other words, optimal allocation results in flows that are much more widely dispersed throughout the entire network.

Flowmaps

Finally, flowmaps can be plotted showing densities of flows along each network edge. The flowmaps from aggregation to nearest points are unhelpful, as non-zero flows only exist on short segmeents of the entire network (reflected in the huge number of zero values in the plot above). The optimallya-allocated flows are, however, much more diffused throughout the city.

Note that it's helpful to reduce the graph down to only those edges with flows > 0:

index <- which (net$flow > 0 | net$flow_aggr > 0)
net0 <- net [index, ]

Plus extract the coordinates of target vertices:

v <- dodgr_vertices (net)
v_to <- v [which (v$id %in% to), ]

And finally, use the 'mapdeck' package to produce an interactive visualisation of the flows. Note that I'm explicitly controlling both colour palette and linewidths.

library(mapdeck)

net0$col <- colourvalues::colour_values(max (net0$flow) - net0$flow, palette = "viridis")
net0$lwd <- net0$flow * 250

mapdeck(style = mapdeck_style("light")) |>
  add_line(net0,
    origin = c(".vx0_x", ".vx0_y"),
    destination = c(".vx1_x", ".vx1_y"),
    stroke_colour = "col",
    stroke_width = "lwd",
    layer_id = "zero"
  ) |>
  add_pointcloud(
    data = v_to,
    lon = "x",
    lat = "y",
    radius = 5,
    fill_colour = "#ff22ee55",
    update_view = FALSE
  )

And a couple of screenshots of that look like this, first for the whole city:

And then zoomed-in on the densest flows along these ways:

Note that the network at the start was constructed for pedestrian routing, and should very accurately reflect the ways that pedestrians are actually likely to choose.

Let me know what you think, and whether there are any ways this might be improved or refined.

[adivea]

This is excellent, Mark. I reran this on my dataset and the resulting flows align with my previous simulation results. Your maps are beautiful. I used my pre-existing map scheme, but yours is very usable, too.

[mpadge]

Great to hear; thanks @adivea. Let me know if there's anything else you need, or any way I can improve the function for you.