Answers to: How do I determine the shortest path that traverses all streets within a city?https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city<p>In order to meet a particular challenge (to run all of Redlands' city streetsâ€”excluding freeways [and ramps] and Redlands property not contiguous to the city centerâ€”in the shortest distance and following one unbroken path) I need to determine 1) how many miles of public roads within a particular city (Redlands, CA), and 2) the most efficient (shortest number of miles) path for covering the complete distance. The second challenge is likely more difficult than the first, but perhaps there is some software I could access. I want to run all the roads (no freeway on or off ramps, and no private roads). I understand that there will necessarily be some doubling of distance (for all cul-de-sacs), and I expect that some of the roads that cross over outside the city limits may need to be travelled in order to get over to the adjacent road (in the name of minimizing the overall distance). It's like finding the shortest distance to cover all the roads without lifting up the pencil.</p>
<p>Any suggestions where to begin? I'm completely new to OSM and would appreciate finding a tutorial or two for my project.</p>
<p>Thanks for any and all suggestions, Paul</p>enThu, 07 Jun 2012 10:27:46 +0100Answer by Jaume Figuerashttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13300<p>Hi,</p>
<p>this is not the TSP problem, in TSP you find the shortest path that connect different nodes in a graph. Paul is asking for an algorithm that visits all edges in a graph with minimum repetition, this is the CPP - Chinese Postman Problem. You will fins information at <a href="http://en.wikipedia.org/wiki/Chinese_postman_problem">wikipedia</a></p>
<p>You will have some challenges at 'cul-de-sacs'. And no, there is no relation with TSP.</p>Jaume FiguerasThu, 07 Jun 2012 10:27:46 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13300Answer by frabronhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13262<p>GRASS GIS has a travelling saleman implementation, but I don't know if you can apply it to roads. Afaik it takes a point layer and a network layer as input, but you might try and see </p>frabronTue, 05 Jun 2012 08:43:31 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13262Answer by Vincent de Philyhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13209<p>You're trying to solve a <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">classic problem of computer science</a> which has no easy answers. Good luck :p</p>Vincent de PhilySat, 02 Jun 2012 22:28:48 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city/13209