|
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. Any suggestions where to begin? I'm completely new to OSM and would appreciate finding a tutorial or two for my project. Thanks for any and all suggestions, Paul |
|
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 |
|
Hi, 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 wikipedia You will have some challenges at 'cul-de-sacs'. And no, there is no relation with TSP. Thank you for your comment, Juame. 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. 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.
(07 Jun '12, 18:55)
pmbooks
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.
(07 Jun '12, 19:11)
pmbooks
|
|
You're trying to solve a classic problem of computer science which has no easy answers. Good luck :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.
(02 Jun '12, 22:54)
pmbooks
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."
(03 Jun '12, 05:56)
pmbooks
1
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 Seven Bridges of Königsberg.
(05 Jun '12, 04:26)
Circeus
So, are Euler's "bridges" equivalent to the lengths of street between intersections?
(09 Jun '12, 14:17)
pmbooks
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)
(11 Jun '12, 19:45)
Jaume Figueras
|
