Chinese Postman Problem Solver

Ideas
1

Idea
Create functionality to provide users with optimized routes for completing desired streets

Imagined Interface
-Separate map interface
-User can select a general area, or specific streets
-Toggle option to require hitting all selected streets or only the currently incomplete streets of those selected
-Option to define starting point
-Toggle option for requiring end point to be the same as starting point, or not

Imagined Output
-Map with proposed paths drawn over it
-List of directions

Challenges
-This is an extremely complex issue
 CPP is known to be NP-hard
-Complexity of finding optimal solution increases exponentially with node/street counts: some upper limit would almost definitely be needed
-Besides the upfront time for UI development & solution scripting, the ongoing computational demands to provide solutions for users would be significant
-The whole topic may be entirely tangential to what CityStrides is, and what the community wants

Nonetheless, thought there may be some other users here who have wondered about this so I wanted to start a thread to discuss.

(fun fact, it was in applying this problem in one of Vancouver’s parks that ultimately introduced me to CityStrides! Thanks, @supermitch)

@ccottell mentioned the ideas of TSP/CPP in a recent thread, but was focused on UI changes that would help compare completed iterations of cities, not actually solving how best to do them.
Continuing the discussion from Time based filtering and challenges:

2

This idea also pairs well with (replaces?) Add a route suggester/builder

I like that your idea includes an imagined interface - this helps a lot!

I’ve been researching third party tooling/software that I might be able to use to achieve this. It was a little while ago, now, but I did get a (not incredibly functional) proof-of-concept working with Mapbox Directions.

One hurdle I have is that each Street’s Nodes aren’t in “order”, so there’s no default first/last Node or an inherently ordered “next” Node from any given Node. So I couldn’t toss a bunch of Nodes at the routing engine and say “give me a route from [starting point], past all of these nodes, and back to [ending point]”. One approach I tried was to use first/last Nodes, but that ended up with the same trouble – although – I’ve had another idea of splitting my Streets up into pieces (in the database/not in a way that’s visible to users), because that’s how OpenStreetMap stores them. Those pieces may have better-defined starts/ends, so that approach could solve the problem (or at least help). :man_shrugging:

2 Likes
3

Its a real challenge because the main difficulty of street coverage is to find an optimal path and optimize the running distance.
I am using the beta CPP Solver released as a QGIS plugin. I don’t think that tool can be used at a larger scale but maybe the released code can help in some way.
This solver needs to create a layer, so I first download the streets of my city boundaries with the useful QuickOSM plugin that create the overpass query and download data directly a s a layer in QGIS (highway=’*’)

Then I select the linestrings layer,

in this layer, I use the selection tool to select an area

Now I launch the CPP Solver (use a small area because it can be time consuming)

Then I can select the layer

and right click to export the CPP layer in GPX Format
Now I have just to download the route to my watch with the upload tool

Screenshot_2020-02-11-10-40-18-818_com.stt.android.suunto(2)
Screenshot_2020-02-11-10-40-18-818_com.stt.android.suunto(2)1080×2340 1.5 MB
(Suunto Android App, but same method works with garmin with a quick gpsies fix)

1 Like
4

I think this confirms my idea of using the pieces of streets that OSM stores. I’ll check out that code - thanks.

I haven’t used QGIS yet, but it’s interesting how similar your process is to the overall CityStrides process. If you have access to the underlying Overpass query, you might benefit from: Overpass Street Query

5

I agree with you that OSM and the street query are the main reliable source of data.
as a novice in overpass, for my personal use i used the query generated by the point and click “QuickOSM plugin” which has a lot of garbage : cycleways, pathways, private ways
image

I will try to figure out how to use the citystrides overpass query to retrieve my area streets in QGIS to proof the experimental CPP solver. Overpass Turbo is a great tool to convert your Overpass query in xml for my proof of concept

image
image693×482 22.3 KB

The solver seems to produce pretty good routes

OVERPASS_CPP
OVERPASS_CPP766×561 59.7 KB

Thanks to the author Ralf Kirstner.

I have just noticed some strange isolated links like “track” “living_street” highway. Maybe to be discussed in overpass thread.
residential
This is caused by the entrance that has a “private” acess but the other inner highway do not.
private
I Noticed also an unconnected road towards a roundabout, but this seems to be an OSM issue
rondpoint

1 Like
6

I have updated OSM data by setting a name on the small road parts around the roundabout.
OSM_Corrected

Now the topology should be better and results to a better generated route (i.e. smaller)
Note that if you plan to use an algorithm like the CPP Solver the efficiency of the results (i.e. the lengh of the generated route compared to the length of the streets) will rely on a very good topology and a good acquisition on crossing data. I had a quick look at the python code, although I am not a programmer i saw it uses a networkx package function to calculate things like “maxcardinality” of nodes" so a higher cardinality should maybe results to more efficient routes.

Also to avoid long calculation time , a good Idea would be to have a strong selection of the streets limited to a certain distance. : the user could point a starting mark and an approximative run distance, then a first pass could select a set of streets in the area : uncovered streets could have a better weight, also choosing nodes could result in a better execution of the solver and a minimum of distance overhead.
My tests convinced me that maybe a solver may need more highways than your standard overpass streets query and a slightly different query with more highways types like “footways” or “pathways” that can provide the necessary links or path to have an efficient route.
Without those links, you would be missing nodes and therefore “cardinality” resulting in larger distance :missing_links
(in example above, the railway would be difficult to cross without exluded “highways” and generate longer running routes.

1 Like
7

@christophe.cr92 Holy Smokes! This is definitely more information & ideas than I thought I would get out starting this thread. I’m currently downloading QGIS, and at some point will try checking out the plugin you mentioned as well. Thank you!!

8

@christophe.cr92 I really like the idea of using a starting mark and run distance, and letting the program figure out where to go/ how to do it, that’s an interesting inversion of the problem I’ve never considered.

Obviously in the example you provided there were quite a few edits required in OSM- have you often found this to be the case? I wonder if using this generally requires fixes like that. I guess maybe the cost of having that functionality is improving OSM all over our desired runs :man_shrugging:

9

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
10

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
11

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
12

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
13

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
14

@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?

15

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
16

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
17

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

18

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
19

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!

20

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