OpenStreetMap
I’ve stumbled across Mapillary and wondered how to cover an area completely. Sadly, Mapillary help pages themselves weren’t very useful[1]: > Plan your route in advance. If you aim to cover a big area, divide it into smaller sections and think through how much you can do at a time.
What it doesn’t say however, is how to actually plan your route. My thought was that especially within areas with mapped streets you could get a route as GPX-file to follow.
Research
In my efforts I first had to learn what problem I am actually facing. It is not “Traveling Salesman Problem”[2] but actually “Route Inspection Problem”[3]. Both problems are computationally hard, i.e. NP-hard. This means you can’t solve them for larger data within any reasonable time. In this case even a “small” road network (some hundred streets) was too much for my desktop computer. However for special cases good algorithms do exist for this problem. One that I’ve found is for non-directed graphs written in Python as a plugin for QGIS, but runnable on its own[4].
Planning a route
This actually works, however you have to convert OSM-streets into usable CSV-files first. I’ve done this using a short Python script and Overpass-turbo. All steps can be seen here: https://gist.github.com/nmxcgeo/739e87333f61234aff5a32bbf735cef7
Shortcomings
There are several shortcomings of my procedure so far.
- It includes turning, where it is unlikely to be physically possible.
- It doesn’t value oneways
- and includes some links between streets that aren’t necessary to visit separately in practice.
- It doesn’t check for connectivity of all roads to the same network and doesn’t necessarily pick the largest network.
Especially because of oneways I currently wouldn’t use it in practice. You might consider it for developing countries or desaster mapping if oneway doesn’t play a role within your region.
Instead I am looking for a library that can handle directed graphs or I might write one myself. Comments on this are welcome.
[1]https://help.mapillary.com/hc/en-us/articles/115001485805-Getting-an-area-photo-mapped
[2]https://en.wikipedia.org/wiki/Travelling_salesman_problem
Discussion
Comment from gnesss on 8 February 2019 at 11:00
This is great. Thanks. I presume you’ve already looked at networkx ? It doesnt do routing as far as i’m aware, but will happily find you simple sequences on a directed graph.
Comment from Nmxosm on 10 February 2019 at 11:12
In fact I haven’t. This looks very interesting. Converting OSM-data to graphs will be possible in some way so I might come back to it when I’ve got time.
Thank you.