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

[3]https://en.wikipedia.org/wiki/Route_inspection_problem

[4]https://github.com/rkistner/chinese-postman