Skip to content

osmnxr 0.1.4

Latest

Choose a tag to compare

@milkway milkway released this 26 Oct 14:00
· 20 commits to main since this release

New: ox_route_tsp() — travelling-salesman routes over the street network

Solves a short route through a set of stops, in the spirit of sfnetworks::st_network_travel() (#4, requested by @talegari):

  • The asymmetric network-distance matrix (one Dijkstra per stop, one-way streets respected) and the visiting order are both computed in the bundled Rust core.
  • The solver is a deterministic iterated local search: nearest-neighbour construction, then an or-opt + swap + 2-opt descent — every move evaluated exactly on the asymmetric matrix — restarted from double-bridge perturbations.
  • Supports closed tours (end = start, default), open routes (end = NULL) and a pinned final stop; returns an sf tibble with one row per leg (cost, node path, merged street geometry).

Benchmarked against TSP::solve_TSP() (the backend st_network_travel() uses) on identical cost matrices over the bundled real networks (Olinda, Manhattan, Rome): matched or beat it in all 80 random instances (8–50 stops), by ~1% on average at 8 stops up to ~10% at 50. A 50-stop route solves in under a second in a release build.

Full details in NEWS.md.