[prev in list] [next in list] [prev in thread] [next in thread]
List: r-sig-geo
Subject: Re: [R-sig-Geo] Complete traversals: Postman problem with shape files
From: Mathieu Rajerison <mathieu.rajerison () gmail ! com>
Date: 2015-03-30 13:55:14
Message-ID: CAGfc75negAsXVd7a+Xyixynm1zHqvhfbADpcDWWzKfX52i-nNw () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/related)]
[Attachment #4 (multipart/alternative)]
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@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@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@r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>
>
[Attachment #7 (text/html)]
<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><di \
v>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>
--001a11c32086dd1c4d051281d481--
["image.png" (image/png)]
_______________________________________________
R-sig-Geo mailing list
R-sig-Geo@r-project.org
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic