Traveling Salesman Approach to Visiting Data-loggers
Posted: Saturday, December 20th, 2008
Premise:
Several data-loggers in steep terrain; how can we visit all of them in the most efficient manner such that we traverse the least cumulative slope gradient? In a sense this is a traveling salesman style problem, with travel costs defined by slope gradient. The v.net.salesman module in GRASS can be used to compute the optimal route between data-loggers, given: 1) a network of lines connecting all points to be visited and 2) transferal of slope cost information to the network. An example approach is listed below. Note that due to a bug in v.net.salesman, we need to use one extra step-- details below.
Approach:
- generate a delaunay network between points
- densify the line segments along the network (v.split)
- convert the network to a 3D, by sampling a DEM along vertices (v.drape)
- save the slope of each line segment on the network to its attribute table (v.to.db)
- use the squared slope as the travel cost
- re-connect the new attribute table from the 3D map, to the original 2D map (v.db.connect)
- connect data-logger points to delaunay network (v.net)
- solve the traveling salesman problem (v.net.salesman)
Room for Improvement:
- generate a cost surface using a combination of slope map and known walkable trails / roads
- add support for lines to v.what.rast -- this would allow us to sample a more realistic cost surface, generated with r.cost
- fix v.net.salesman so that it can use 3D input maps
mplementation in GRASS:
# generate simple network connecting all points
v.delaunay --o -l in=temperature_sites_maybe out=tri
# densify line segments
v.split --o in=tri out=tri_2 length=5
# add categories
v.category --o in=tri_2 out=tri_3 option=add type=line
# convert to 3d, using our elevation model
v.drape --o in=tri_3 out=tri_4 rast=rtk_elev_var_smooth@rtk
# add a table
v.db.addtable map=tri_4 columns="cat integer, cost double"
# use the slope between line segments as the cost
v.to.db map=tri_4 type=line layer=1 option=slope columns=cost
# make all slopes positive
echo "UPDATE tri_4 set cost = cost * cost" | db.execute
# connect table from 3D map to original 2D map:
v.db.connect map=tri_3 table=tri_4
# make a copy, which brings over a copy of the linked table
g.copy --o vect=tri_3,triangulation
# clean-up
g.remove vect=tri,tri_2,tri_3,tri_4
# make a network
v.net --o in=triangulation points=temperature_sites_maybe out=net --o operation=connect thresh=10
# check network-- has categories?
v.category net op=report
# solve traveling salesman problem
# does not work with 3D maps (ticket # 406)
v.net.salesman --o in=net out=salesman acol=cost ccats=1-33
Links:
Spatial Clustering of Point Data: Spearfish Example
Vector Operations
Software
- General Purpose Programming with Scripting Languages
- LaTeX Tips and Tricks
- PostGIS: Spatially enabled Relational Database Sytem
- PROJ: forward and reverse geographic projections
- GDAL and OGR: geodata conversion and re-projection tools
- R: advanced statistical package
- GRASS GIS: raster, vector, and imagery analysis
- Generic Mapping Tools: high quality map production