#30DayMapChallenge Day 2: Lines

The traveling free book salesman problem

Show code

library(httr2)
library(jsonlite)
library(tidyverse)
library(sf)
library(tmap)

“Lines” is the theme for day 2 of the #30DayMapChallenge. I figured I should do a follow up to yesterday’s post about public bookcases. After making my post I went out for a walk to collect photos of a few more bookcases. I half-jokingly told my SO that maybe I should use a traveling salesman algorithm to optimize my Sunday walk. Well, I didn’t do it before my walk, but why don’t I do for today’s challenge?

I’m using the GraphHopper Route Optimization API. They have a free tier available but you do need an API key.

Construct the query

I’ll use an updated dataset of the bookcases, taking into account the bookcases for which I added photos yesterday and a few new ones I found. To speed things up I filter for nodes without photos right in the Overpass query:

  [out:json][timeout:60];
  {{geocodeArea:Madison, Wisconsin}}->.a;
  node["amenity"="public_bookcase"][!panoramax](area.a);
  out center;

This results in 228 bookcases without photo.

Show code

bookcases <- st_read("data/overpass_export.geojson")

Reading layer `overpass_export' from data source 
  `/Users/kliems/website/_posts/2026-11-02-traveling-free-bookcase-salesman/data/overpass_export.geojson' 
  using driver `GeoJSON'
Simple feature collection with 228 features and 19 fields
Geometry type: POINT
Dimension:     XY
Bounding box:  xmin: -89.55776 ymin: 43.00753 xmax: -89.25676 ymax: 43.15342
Geodetic CRS:  WGS 84

There doesn’t seem to be an up-to-date package for interacting with the Graphhopper route optimization API endpoint from R and so I need to use httr2. The API needs json with the locations as its input. I’m going to do this quick and dirty, and just copy and paste together some stuff. Here’s the code to create the list of destinations (called “services” in the API) from the Overpass output:

Show code

location_json <- bookcases |> 
  # head(3) |> 
  mutate(id = str_remove(id, "node/")) |> 
  rowwise() |> 
  mutate(address = tibble(
    location_id = "test",
    lon = st_coordinates(geometry)[1],
    lat = st_coordinates(geometry)[2]
  )) |> 
  select(id, name, address) |> 
  st_drop_geometry() |> 
  jsonify::to_json() |> 
  clipr::write_clip()

Then there’s a bunch of json to specify the type of vehicle, start location, etc. I save all this and the locations in json file.

Now we feed the file to the API and save the response:

Show code

base_url <- "https://graphhopper.com/api/1/vrp"
key <- Sys.getenv("GRAPHHOPPER_API")

req <- request(base_url) |> 
  req_url_query(
    key = key) |> 
  req_body_file("data/bookcase.json", type = "application/json") |> 
    req_error(is_error = \(r) FALSE)   # let us inspect 400s ourselves

resp <- req |> req_perform()

Next I parse the response into two sf objects: One multi-linestring of all segments between the bookcases, as the crow flies. And one dataframe with the ordered stops themselves. I’m really not good at parsing and converting deeply nested json and used an LLM to help with this part of the code.

Show code

solution <- resp_body_json(resp)

# multilinestring
route <- solution$solution$routes[[1]]

coords <- map(route$activities, \(a) c(a$address$lon, a$address$lat)) |>
  do.call(rbind, args = _)

segments <- lapply(seq_len(nrow(coords) - 1), \(i) coords[i:(i + 1), ])

route_sf <- st_sf(
  vehicle_id = route$vehicle_id,
  distance_m = route$distance,
  geometry   = st_sfc(st_multilinestring(segments), crs = 4326)
)

# stop locations
stops <- as_tibble(coords) |> 
  rowid_to_column(var = "stop") |> 
  rename(lat = V1, 
         lon = V2) |> 
  st_as_sf(coords = c("lat", "lon")) 

Now we can make a map! First a static map with just the lines:

Show code

tmap_mode("plot")
tm_basemap(server = "Stadia.StamenTonerLite", api = Sys.getenv("STADIA_API_KEY")) +
  tm_shape(route_sf) +
  tm_lines(col = "orange", lwd = 2) +
  tm_title("Shortest bike route to all Madison public book cases that don't have a photo")

And now an interactive one that includes the stops and the number for the order they’re in:

Show code

tmap_mode("view")
tm_shape(route_sf) +
  tm_lines(col = "orange", lwd = 2) +
  tm_shape(stops) +
  tm_dots(fill = "darkblue", size = .4) +
  tm_text(text = "stop", col = "darkblue", xmod = .08) +
  tm_title("Shortest bike route to all Madison public book cases that don't have a photo")

The full route would be 207.9 km (129.1830725 mi) long (the actual bike route, not the as-the-crow flies route shown on the map).