Fundamentally this is a simple application of some of the shortest path algorithms that are studied at university computer science and mathematics departments adnausium.<br><br>There are however a bunch of complications that make it a little less simple, and is likely best worked out in each individual instance.<br>

<br>(You already know this, but for completness:) The way it's generally done at mapping parties is to cut the area up intuitively into a bunch of areas, naturally divided up by natural boundaries (such as main roads, rivers etc) let volunteers allocate themselves areas by ersonal preference. (cutting the cake)<br>

<br>However due to the huge number of variables involved, I'd be surprised if there was any way a computer could do it faster or better:<br><br>Someone says "I like driving, so I'll take the furthest away bit";<br>

Someone say "I have a bike, so i can do that little area with lots of foot paths";<br>someone says "I like trees, and I know there are lots of trees in that area" (OK, that's a slight exaggeration);<br>

When you arrive on the ground you can find that there are names only at one end of a grid of streets, and your carefully pre planned route breaks.<br>There are so many different kinds of areas (grid patterns; modern curvey estates, terraced areas, industrial parks, one way systems) that routing algorithms would have to be tweaked for each area;<br>

<br>You could however call every intersection a node, and come up with an algorithm to visit each node once. This is almost the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">Travelling_salesman_problem</a> though extra complexity is added when you find that some streets only need one end visited. While there are severe problems with finding a perfect solution to the TSP, there are plenty of shortcuts that can be taken in this case.<br>

<br>Now reading between the lines of your problem, there are a few questions -- are you willing to assume that if you drive past one end of a street, it's captured, or does both ends need to be captured? Or is some live update system going to be implemented so that volunteers can enter information about when they get a street name, and the route can be recalculated?<br>

<br>Are you willing to accept that if a road changes name part way though, and that missing this is a reasonable error?<br><br>Is it reasonable to assume that all volunteers are especially the same (they all have a car, and have no specific preferences)?<br>

<br>Is it reasonable to assume that everyone starts and finishes at a predetermined "base"?<br><br>Is it reasonable ot assume that if someone finds a 1 way system, or other restriction, that the route will go wrong, and this is ok?<br>

<br>How large an area are we dealing with here? most algorithms for this type of thing get proportionately slower the more data is put in, and as such, will have a point at which they simply fall over or get so slow that it would be quicker to use a pencil and some brain cells.<br>

<br>In short: I'd recommend just using intuition, but if that's not an option, give a load more details, and we can work something out.<br><br>On to a related subject, are there any tools that have been developed to assist with cake cutting tasks? I have personally been tairing my hair out for the last few days trying ot get josm to display cake segments for yahooing tiger data.<br>

<br>Thanks,<br>JR<br><br><br><div class="gmail_quote">On 24 March 2010 10:52, John Smith <span dir="ltr"><<a href="mailto:deltafoxtrot256@gmail.com">deltafoxtrot256@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

This is a routing problem, hopefully someone has already solved it.<br>
<br>
If there is a suburb of streets mapped from aerial imagery and you<br>
have several volunteers how do you work out the most efficient path<br>
for all the voluneteers to take to grab street names with minimal<br>
overlap etc.<br>
<br>
_______________________________________________<br>
dev mailing list<br>
<a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br>
<a href="http://lists.openstreetmap.org/listinfo/dev" target="_blank">http://lists.openstreetmap.org/listinfo/dev</a><br>
</blockquote></div><br>