[R-sig-Geo] Complete traversals: Postman problem with shape files

[Mathieu Rajerison]

Hi,

Maybe you could have a look at v.net.salesman from GRASS.

Please note that GRASS can be reached while using R with spgrass06 package.

Best,

mathieu

2015-03-28 19:01 GMT+01:00 Mike <aspiringbodhisattva at gmail.com>:

> Hi all,
>
> I'm relatively new to the listserv, but learning a lot.  Please excuse me
> if this is a semi-related question.
>
> 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.
> http://en.wikipedia.org/wiki/Route_inspection_problem
>
> 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.
>
> (Below is me muddling through a test case using the counties as a whole,
> code and picture.)
>
> 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?
>
> Best wishes and much respect,
> Mike Fliss
> UNC Epidemiology PhD student.
>
>
> [image: Inline image 1]
>
> library("maptools")
> library("spdep")
> library("sp")
> library("TSP")
> #data("USCA312")
>
> VAcounties = readShapeSpatial("E:/Mike/GIS/Base shape files/VA Counties/VA
> Counties.shp")
> plot(VAcounties, border="grey")
> neighbors <-poly2nb(VAcounties)
> plot(neighbors, coordinates(VAcounties), line="grey", add=TRUE)
>
> VApoints = read.csv("E:/Dropbox/Community/Driving VA/vapoints.csv")
> VA.SPDF = SpatialPointsDataFrame(VApoints[,2:3], VApoints[1], proj4string
> = CRS("+proj=longlat"))
>
> vamatrix <- read.csv("E:/Dropbox/Community/Driving VA/vacountymatrix.csv",
> stringsAsFactors=FALSE)
> va2 = as.matrix(vamatrix)
> dimnames(va2) = list(names(vamatrix), names(vamatrix))
>
> vatsp = TSP(va2)
> vatsp=insert_dummy(vatsp, label="cut")
>
> #tour = solve_TSP(vatsp, method="repetitive_nn", control=list(start=1))
> tour = solve_TSP(vatsp, method="2-opt", control=list(rep=100))
> path = cut_tour(tour, "cut")
>
> head(labels(path))
>
> plot(VAcounties, border="grey")
> plot(VA.SPDF, pch=16, cex=.4, col="red", add=T)
> path_line = SpatialLines(list(Lines(list(Line(VA.SPDF[path,])), ID="1")))
> plot(path_line, add=T, col="black")
> points(VA.SPDF[c(head(path,1), tail(path,1)),], pch = 19, col = "black")
>
> --
> ---
> Mike Dolan Fliss, MSW
> mike.dolan.fliss at gmail.com
> UNC-CH Epidemiology PhD student
> NC public health advocate!
> -------------------
> "We work on ourselves in order to help others,
> but also we help others in order to work on ourselves."
>   - Pema Chodron
>
> “Upon this gifted age, in its dark hour
> Rains from the sky a meteoric shower
> Of facts…they lie, unquestioned, uncombined.
> Wisdom enough to leach us of our ill
> Is daily spun; but there exists no loom
> To weave it into a fabric.”
>   - Edna St. Vincent Millay, 1939
>
> There are two kinds of people in the world:
> Those who can extrapolate from incomplete data.
>
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://stat.ethz.ch/pipermail/r-sig-geo/attachments/20150330/bc856b59/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 21119 bytes
Desc: not available
URL: <https://stat.ethz.ch/pipermail/r-sig-geo/attachments/20150330/bc856b59/attachment.png>