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>enMon, 11 Jun 2012 19:45:53 +0100Comment by Jaume Figueras on Vincent de Phily's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13435<p>No, the bridges are not equivalent to length. If you want to model a network into a graph, the bridges are the edges and the connection between bridges are the nodes. In Königsberg problem, the classic modeling of the network does not take into account distances because the problem does not depend on distances. You try to find a circuit independently of the distances. In CPP you should take into account oneways (directed graph) and distances (marking of the edges)</p>Jaume FiguerasMon, 11 Jun 2012 19:45:53 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13435Comment by pmbooks on Vincent de Phily's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13375<p>So, are Euler's "bridges" equivalent to the lengths of street between intersections?</p>pmbooksSat, 09 Jun 2012 14:17:55 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13375Comment by pmbooks on Jaume Figueras's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13310<p>BTW, I live in Redlands, home to ESRI. You might expect I would know someone there who could help solve this, but I don't.</p>pmbooksThu, 07 Jun 2012 19:11:22 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13310Comment by pmbooks on Jaume Figueras's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13306<p>Thank you for your comment, Juame. </p>
<p>I read the wiki entry and I agree the problem is less TSP than CPP. It appears, since my problem cannot be solved without some repetition (cul-de-sacs, and likely some out-and-back for some roads extending beyond the city's perimeter), it will not be a Eulerian path or circuit. However, having said that, it would be possible to provide a program with a graph of the streets excluding the cul-de-sacs. </p>
<p>Again, thanks for reflecting on my challenge. My plan is to complete the course over several days; although my desire is to complete it as quickly as possible (thus a run), I will break for some sleep each day.</p>pmbooksThu, 07 Jun 2012 18:55:22 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13306Answer 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/13262Comment by Circeus on Vincent de Phily's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13260<p>Going through the roads is the exact same problem in term of description by graph theory. Your problem is just the Traveling Salesman as applied to the <a href="http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg">Seven Bridges of Königsberg</a>.</p>CirceusTue, 05 Jun 2012 04:26:03 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13260Comment by pmbooks on Vincent de Phily's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13214<p>Yet, one variation between the traveling salesman's problem and my own is that the former concerns hitting points (cities) that must be connected via the shortest distance, while my problem covers roads that must be traversed. There may be 300 miles of roads in the city, but with cul-de-sacs, etc., there will necessarily be more distance covered. I can start at any point in the city, and I will take breaks along the way (I will need to return to the point where I left the "course."</p>pmbooksSun, 03 Jun 2012 05:56:51 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13214Comment by pmbooks on Vincent de Phily's answerhttps://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13211<p>Nice, thank you for the link, Vincent. It is, as you point out, a classic problem (The Travelling Salesman Problem). I would think that there must be some mapping software out there for this problem. (I'm think of trash pick-up and mail delivery being a couple of instances where the route needs this optimization.</p>pmbooksSat, 02 Jun 2012 22:54:45 +0100https://help.openstreetmap.org/questions/13197/how-do-i-determine-the-shortest-path-that-traverses-all-streets-within-a-city#13211Answer 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