Routing: A way to link to a router for Chinese Postman routing?

General talk
1

Hey! I am working on a community page that will show me OSM street segments that require a fresh set of Mapillary Images. Right now, this is “just” a visual page. However, I wonder how I could connect this to some (external) routing.

I read about Valhalla supporting this

However, I am wondering if there is a community routing service out there, that I could link to from my website. For example by providing the streets in question as URL param.

Here is a sneak peek of what the page will show:
(The pink segments require fresh Mapillary images. Those are the once that a router should put into the most efficient route for me…)

image
image746×742 167 KB

2

If only a subset of the street segments need to be visited and not all of them, this becomes the Rural Postman Problem which is NP-hard again.

Here’s a paper about solving it which also references older literature: GW Groves, JH van Vuuren, 2004: Efficient heuristics for the Rural Postman Problem.

1 Like
3

I did some research on this in the past and found this article: Sleeping Giant Rural Postman Problem – andrew brooks

1 Like
4

Not a website but QMapShack can do this for you and I use it to plan a route for delivering mailing to selected addresses through a part of the city.

QMapShack Optimize route

For your use you would have to export a list of waypoints with the middle of each “road” you want to finish, import those and create a route from the start to the endpoint passing through all the other given waypoints. Then chose Optimize and QMS will run s an approximation algorithm for solving this problem.

2 Likes
5

Yeah, in my limited optimization experience, this is a different problem than what that wretched Valhalla PR tried to solved. AFAIK the problem with these postman problems is that they need to have access to a graph, not only routing results as e.g. TSP, which is why we decided back then to incorporate it into Valhalla. Typically you’d like to avoid that with VRPs, see VROOM. But I’d suspect the same to be true for this rural one. FWIW, I’d like to clean up camptocamp’s mess of a PR, but it’s abysmally far down the priority list :wink:

6

I was looking at the very same issue a couple years back as i have the same issue, not just for revisiting but also for initial riding for mapillary.

I could find any “point and click solution” on a website. As the problem is NP hard (As was already mentioned) there can only be algorithmical estimations which must not necessarily be the best solution.

the issue i was thinking through is that in one ride i typically to 20-40km - so ist halve the distance (as i do all streets both way). So we are talking about 10-20km of highway/road/path segments.

Putting a small area like this into a graph an solving that by brute force should be doable pretty easy.

In the end it wasnt that of a needed solution as most of the time i segment citys by higher class road boundaries and mostly do the riding by brute force.

Flo

7

If you look for algorithms, check if they are for the “undirected” or “directed” variant.

Nice, you found the next harder problem :wink: Given the set of street segments to visit, find k tours such that none is longer than 40 km while minimizing the sum of tour lengths.

Found another nice paper: Kaj Holmberg, 2015: Heuristics for the Weighted k-Chinese/rural Postman Problem with a Hint of Fixed Costs with Applications to Urban Snow Removal. He even has a UI tool to run and visualize the different algorithms: Vineopt. Couldn’t find it for download, though :cry:. Here’s a video about it: vineopt intro.