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

[Mike]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://stat.ethz.ch/pipermail/r-sig-geo/attachments/20150328/cfd8f3df/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/20150328/cfd8f3df/attachment.png>