Chinese Postman Problem Solver

Yes citystriding runs requires so much attention to memorize the streets you have covered, i went to the conclusion that Osm itself coupled with a small algorithm (have a look at the CCP code it looks so pure and simple) could make the process of covering a maximum number of street in a minimum distance easily.

There is no need to update Osm , i did it because my first attempt to build a route was based on the citystride streets list query.

i tested a different query to build the route: a less restrictive overpass query that retrieves small pathes, roundabouts, bridgeways that citystrides excludes in his query (in my example excluding pathways with noname)

At this point i imagine the following process

  • point a starting point , a distance
  • query a list or uncovered streets, put a Weight on them
  • query highways to improve connecting points ignored by citystrides

(By quey i mean overpass query)

The main concern is to improve connections points between streets without generating to much secondary or residential ways : sometimes you need to cross a railway for example but that path is not covered by citystrides . That bridge could save a lot of distance.

1 Like

Oh yes and you can download the quickosm plugin which helps to retrieve data from Osm with overpass quey (you can cut and paste the official query and play with exclusions, it’s a good starting point)
It’s amazing the progress i made in building a gpx route in a few days with that method

1 Like

Interesting idea, I read that Ricky Gates used some sort of algorithm from the post office to help plan. On a personal idea part of the challenge for me is to figure out my own approach to this

2 Likes

Nice write-up of someone taking this approach to finish their city 2020: RATS In Houghton – Gowtham

It includes some helpful details/definitions for anyone interested in learning more.

4 Likes

I wrote a python script that takes inputs of:

  1. an open street map query to get all nodes
  2. a starting node

It then will then solve the Chinese Postman Problem and then do an optimization to get the minimum number of U-turns of that given Euler Circuit. It then generates a gpx file for you and also print a map.

All of the solving was done using GitHub - brooksandrew/postman_problems: Graph optimization solvers for the Postman Problems
and I just hacked together some stuff around it.

6 Likes

@matt.wongkee this is… incredible.
I’m a bit of Python noob but do have a compiler.

Unfortunately it wasn’t as simple as copying & pasting. Code broke at Line 210:

ModuleNotFoundError: No Module named ‘router_utils’

Is that a module that needs to be added to my compiler?

my repo is pretty messy. router_utils is in the main directory. You need to setup your PYTHONPATH properly or maybe execute from that directory

1 Like

I had a similar question to Dave Morin’s OP here, but the subsequent discussion went over my head pretty quickly… I’m wondering if there have been any developments towards a tool for dummies like me to use to plan optimized routes?

3 Likes

Good question, Wondering if @davemorin is going to chime in?

Hi all,

Over the [UK] lockdown I got interested in this [running] challenge and as mathematicians and software engineer I come up with this web app: http://www.everystreetchallenge.com which tries to solve the CPP on OpenStreetMap. Hopefully it will solve some of your problems, even though it is not perfect as it considers only public streets accessible for cars.

11 Likes

Hi Matej,

Thanks for sharing. I’ll definitely be giving this a go. Even if it doesn’t account for footpath-shortcuts I’m sure it’ll still be a lot more efficient (and less time consuming) than my current route planning!

Hi Sean, happy to hear that :slight_smile:

Yeah, the footpaths are a real hassle. I could turn layer walk on but unfortunately there are many more problems with having it, e.g. many town consider a road with footpath on both sides as 2 separates streets.

I am happy and open to suggestions how to make the algorithm better :slight_smile:

If you are super super interested in the algorithm I wrote some rough theoretical summary [1] and there is a GitHub repo with an algorithm sketch [2].

[1] http://www.everystreetchallenge.com/everystreet_algorithm.pdf
[2] GitHub - matejker/everystreet: An algorithm finding #everystreet route on Open Street Map (OSMnx)

2 Likes

Hi Matej,
thanks for making this, it looks really nice and seems to work well on the examples I’ve tried! I also really like the ability to export the route as a GPX file, having some form of navigation will definitely be necessary for me to be able to follow the ideal path :smile: At the moment I’m building my routes as much for ease of execution as for efficiency as I’m just memorizing them, but I will give this a try when I get the chance (and if my watch can handle the navigation).

1 Like

@99aad85097beec3cac01 Just started playing with your URL. That’s pretty cool!

1 Like

This is awesome!

1 Like

Great tool! I have some ideas for improvement, as you have stated you are open to that.

OSMNX will allow for a custom filter, so you could use a filter that matches exactly the filter used at Citystrides, that would be a nice touch and keep from trying to route us onto roads inappropriate for running.
Docs: https://osmnx.readthedocs.io/en/stable/osmnx.html?highlight=custom%20filter#osmnx.graph.graph_from_polygon
It appears the details of that query can be found here: Overpass Street Query

It would also be great if the starting node for the Eulerian circuit could be specified. So that one could aim to start at a good parking location for instance.

Hi Troy,

glad to hear that.

OSMNX will allow for a custom filter, so you could use a filter that matches exactly the filter used at Citystrides, that would be a nice touch and keep from trying to route us onto roads inappropriate for running.

Yeah thats a really good call! I was also annoyed that it is routing onto motorways… I didn’t know that you can specify the highway that specifically within OSMnx. I added a “issue” in the github repo, will try to fix it Thanks!

It would also be great if the starting node for the Eulerian circuit could be specified. So that one could aim to start at a good parking location for instance.

The route would be the same, only the starting / ending node will be different. I had this idea as well, it shouldn’t be hard to set different point.

Thanks again! I would kindly recommend to raise the issues in the github repo, if you are not github member feel free to raise here or DM :slight_smile:

1 Like

Hey there. I really like this and am happy just watching it map out streets I have already run more efficiently than I did!
I tried to use it today in a section on lewisham, nsw, australia - and it worked except that it ignored the lanes that city strides definitely includes.
Any way to adjust the parameters?

Closing this out based on our conversations in Automatically Generate Routes

2 Likes