<div dir="ltr">Hi,<div><br></div><div>Maybe you could have a look at v.net.salesman from GRASS.</div><div><br></div><div>Please note that GRASS can be reached while using R with spgrass06 package.</div><div><br></div><div>Best,</div><div><br></div><div>mathieu</div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-03-28 19:01 GMT+01:00 Mike <span dir="ltr"><<a href="mailto:aspiringbodhisattva@gmail.com" target="_blank">aspiringbodhisattva@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi all, <div><br></div><div>I'm relatively new to the listserv, but learning a lot. Please excuse me if this is a semi-related question.</div><div><br></div><div>As part of a public health project to survey an area for tobacco retailers, we're attempting to investigate a systematic, complete, and reasonably efficient (not necessarily perfect) traversal of all the roads in a certain catchment area. This is an application of the classic "postman" problem - traversing all the edges of a graph - related to the canonical Traveling Postman Problems / TSPs. Specifically, we'd be taking regions of VA and breaking that up into volunteer catchment areas - a county or two - to drive the area.</div><div><a href="http://en.wikipedia.org/wiki/Route_inspection_problem" target="_blank">http://en.wikipedia.org/wiki/Route_inspection_problem</a><br></div><div><br></div><div>I've a proof of concept plot and code below that takes a shape file of regions (in this case, of VA counties) and traverses them in a reasonably efficient way... but this uses centroids of shapes and creates a distance matrix off of that, instead of working with the road shape file itself, which is currently stumping me.</div><div><br></div><div>(Below is me muddling through a test case using the counties as a whole, code and picture.)</div><div><br></div><div>I know this is not at all a trivial problem. Any guidance or expertise here? I could make accessible more useful test cases/datasets (like a single county's roads) if that were helpful. Or perhaps there are packages that do this out of the box besides what I'm using?</div><div><br></div><div>Best wishes and much respect,</div><div>Mike Fliss</div><div>UNC Epidemiology PhD student.<br></div><div><br></div><div><br></div><div><img src="cid:ii_14c618528ec42a41" alt="Inline image 1" width="544" height="398"><br></div><div><br></div><div><div>library("maptools")</div><div>library("spdep")</div><div>library("sp")</div><div>library("TSP")</div><div>#data("USCA312")</div><div><br></div><div>VAcounties = readShapeSpatial("E:/Mike/GIS/Base shape files/VA Counties/VA Counties.shp")</div><div>plot(VAcounties, border="grey")</div><div>neighbors <-poly2nb(VAcounties)</div><div>plot(neighbors, coordinates(VAcounties), line="grey", add=TRUE)</div><div><br></div><div>VApoints = read.csv("E:/Dropbox/Community/Driving VA/vapoints.csv")</div><div>VA.SPDF = SpatialPointsDataFrame(VApoints[,2:3], VApoints[1], proj4string = CRS("+proj=longlat"))</div><div><br></div><div>vamatrix <- read.csv("E:/Dropbox/Community/Driving VA/vacountymatrix.csv", stringsAsFactors=FALSE)</div><div>va2 = as.matrix(vamatrix)</div><div>dimnames(va2) = list(names(vamatrix), names(vamatrix))</div><div><br></div><div>vatsp = TSP(va2)</div><div>vatsp=insert_dummy(vatsp, label="cut")</div><div><br></div><div>#tour = solve_TSP(vatsp, method="repetitive_nn", control=list(start=1))</div><div>tour = solve_TSP(vatsp, method="2-opt", control=list(rep=100))</div><div>path = cut_tour(tour, "cut")</div><div><br></div><div>head(labels(path))</div><div><br></div><div>plot(VAcounties, border="grey")</div><div>plot(VA.SPDF, pch=16, cex=.4, col="red", add=T)</div><div>path_line = SpatialLines(list(Lines(list(Line(VA.SPDF[path,])), ID="1")))</div><div>plot(path_line, add=T, col="black")</div><div>points(VA.SPDF[c(head(path,1), tail(path,1)),], pch = 19, col = "black")</div><div><br></div>-- <br><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div style="font-size:12.8000001907349px"><div dir="ltr" style="font-size:12.8000001907349px"><div style="font-size:12.8000001907349px">---</div><div style="font-size:12.8000001907349px">Mike Dolan Fliss, MSW</div><div style="font-size:12.8000001907349px"><a href="mailto:mike.dolan.fliss@gmail.com" target="_blank">mike.dolan.fliss@gmail.com</a></div><div style="font-size:12.8000001907349px"><div style="font-size:small"><span style="font-family:arial,helvetica,sans-serif">UNC-CH Epidemiology PhD student</span></div><div style="font-size:small"><span style="font-family:arial,helvetica,sans-serif">NC public health advocate!</span><br></div></div><div style="font-size:12.8000001907349px"><font face="arial, helvetica, sans-serif">-------------------</font></div>"We work on ourselves in order to help others, <br>but also we help others in order to work on ourselves."<br> - Pema Chodron<br><br>“Upon this gifted age, in its dark hour<br>Rains from the sky a meteoric shower<br>Of facts…they lie, unquestioned, uncombined.<br>Wisdom enough to leach us of our ill<br>Is daily spun; but there exists no loom<br>To weave it into a fabric.”<br> - Edna St. Vincent Millay, 1939</div><div dir="ltr" style="font-size:12.8000001907349px"><br></div><div style="font-size:12.8000001907349px">There are two kinds of people in the world:</div><div style="font-size:12.8000001907349px">Those who can extrapolate from incomplete data.</div></div></div></div></div></div></div></div></div>
</div></div>
<br>_______________________________________________<br>
R-sig-Geo mailing list<br>
<a href="mailto:R-sig-Geo@r-project.org">R-sig-Geo@r-project.org</a><br>
<a href="https://stat.ethz.ch/mailman/listinfo/r-sig-geo" target="_blank">https://stat.ethz.ch/mailman/listinfo/r-sig-geo</a><br>
<br></blockquote></div><br></div>